# The Erdős-Falconer distance problem in the tree setting

Thang Pham and Steven Senger and Dung The Tran  Hanoi University of Science,
Vietnam National University<EMAIL_ADDRESS>Department of
Mathematics, Missouri State University<EMAIL_ADDRESS>Department of Mathematics, National Taiwan Normal University
<EMAIL_ADDRESS>
###### Abstract.

The recent breakthrough of Guth, Iosevich, Ou, and Wang (2019) on the Falconer
distance problem states that for a compact set $A\subset\mathbb{R}^{2}$, if
the Hausdorff dimension of $A$ is greater than $\frac{5}{4}$, then the
distance set $\Delta(A)$ has positive Lebesgue measure. In a very recent
paper, Murphy, Petridis, Pham, Rudnev, and Stevens (2022) proved the prime
field version of this result, namely, for $E\subset\mathbb{F}_{p}^{2}$ with
$|E|\gg p^{5/4}$, there exist many points $x\in E$ such that the number of
distinct distances from $x$ is at least $cp$. The main purpose of this paper
is to provide extensions in a very general structure of pinned trees, which is
inspired by the recent work due to Ou and Taylor (2021).

##  1\. Introduction

For $A\subset\mathbb{R}^{d}$, we define its distance set by

$\Delta(A):=\\{|x-y|\colon x,y\in A\\}.$

The celebrated Falconer distance conjecture says that for any compact set
$A\subset\mathbb{R}^{d}$, if its Hausdorff dimension is greater than
$\frac{d}{2}$, then the distance set has positive Lebesgue measure, i.e.
$\mathcal{L}^{1}(\Delta(A))>0$. In a recent breakthrough paper, Guth,
Iosevich, Ou, and Wang [6] proved that for a compact set
$A\subset\mathbb{R}^{2}$, if $\dim_{H}(A)>\frac{5}{4}$, then
$\mathcal{L}^{1}(\Delta(A))>0$. This result has been generalized to higher
even dimensions by Du, Iosevich, Ou, and Wang in [5]. In odd dimensions, the
best known dimensional threshold is due to Du and Zhang [4] with
$\dim_{H}(A)>\frac{d}{2}+\frac{d}{4d-2}$.

More recently, Ou and Taylor [18] studied a generalization for the setting of
trees. More precisely, let $T$ be an arbitrary tree with $k+1$ vertices and
$k$ edges. Assume that $V(T)=\\{v_{1},\ldots,v_{k+1}\\}$, then the edge set of
$T$ can be enumerated as follows:

$\mathcal{E}(T)=\\{(v_{i_{1}},v_{i_{2}}),(v_{i_{3}},v_{i_{4}}),\ldots,(v_{i_{2k-1}},v_{i_{2k}})\\},$

where $i_{1}\leq i_{3}\leq\cdots\leq i_{2k-1}$, and $i_{2s}<i_{2t}$ if $s<t$
and $i_{2s-1}=i_{2t-1}$.

The edge-length vector of $T$ is defined by

$(|v_{i_{1}}-v_{i_{2}}|,|v_{i_{3}}-v_{i_{4}}|,\ldots,|v_{i_{2k-1}}-v_{i_{2k}}|)\in\mathbb{R}^{k}.$

Given a set $A\subset\mathbb{R}^{2}$, we say a tree $T^{\prime}$, with
vertices in $A$ given by $V(T^{\prime})=\\{x_{1},\ldots,x_{k+1}\\}$, is
isomorphic to $T$ if there is a map $\varphi\colon V(T^{\prime})\to V(T)$ such
that $(x,y)$ is an edge of $T^{\prime}$ iff
$\left(\varphi(x),\varphi(y)\right)$ is an edge of $T$. For $x\in
V(T^{\prime})$ and $v\in V(T)$, we say $(T^{\prime},x)$ is isomorphic to
$(T,v)$ if $T$ is isomorphic to $T^{\prime}$ and $\varphi(x)=v$. We say two
isomorphic trees $T$ and $T^{\prime}$ with $k$ edges are distinct if their
edge-length vectors are distinct. Ou and Taylor proved the following theorem.

######  Theorem 1.1.

Given a tree $T$ with $k\geq 1$ edges and an arbitrary vertex $v$, let $A$ be
a compact set in $\mathbb{R}^{2}$. If $\dim_{H}(A)>\frac{5}{4}$, then there
exists $x\in A$ such that the set of edge-lengths of trees $(T^{\prime},x)$
which are isomorphic to $(T,v)$ has positive Lebesgue measure.

The main purpose of this paper is to extend this theorem to the discrete
setting over finite fields and arbitrary fields.

Let $\mathbb{F}$ denote an arbitrary field. When we deal with the special case
that $\mathbb{F}$ is a finite field of order $q$, where $q$ is an odd prime
power, we use the notation $\mathbb{F}_{q}$. The characteristic of
$\mathbb{F}$ is denoted by $\mathtt{char}(\mathbb{F})$. We also use the
notation $X\gg Y$ to denote that there exists a constant $C>0$ such that
$X\geq CY$.

In the setting of arbitrary fields $\mathbb{F}$, the distance between two
points $x=(x_{1},\ldots,x_{d})$ and $y=(y_{1},\ldots,y_{d})$ in
$\mathbb{F}^{d}$ is defined by

$||x-y||=(x_{1}-y_{1})^{2}+\cdots+(x_{d}-y_{d})^{2}.$

The finite field analogue of the Falconer distance problem is known as the
Erdős-Falconer distance problem in the literature, which asks for the smallest
exponent $\alpha$ such that for any $E\subset\mathbb{F}_{q}^{d}$, if $|E|\geq
q^{\alpha}$, then the distance set $\Delta(E)$ covers a positive proportion of
or all possible distances, where

$\Delta(E):=\\{||x-y||\colon x,y\in E\\}.$

Iosevich and Rudnev proved in [9] that $\alpha\leq\frac{d+1}{2}$. They also
showed that the exponent $\frac{d+1}{2}$ is sharp in odd dimensions. In even
dimensions, it is also conjectured that the right exponent should be
$\alpha=\frac{d}{2}$. Some partial progress on this conjecture can be found in
[2, 14, 15]. In two dimensions over prime fields, Murphy, Petridis, Pham,
Rudnev, and Stevens [17] recently proved that $\alpha\leq\frac{5}{4}$, which
is directly in line with Guth, Iosevich, Ou, and Wang’s result for the
Falconer distance problem. We also note that Murphy et al. actually proved a
stronger statement, namely, if $|E|\geq p^{5/4}$, then there exist many points
$x\in E$ such that $|\Delta_{x}(E)|\gg p$, where
$\Delta_{x}(E)=\\{||x-y||\colon y\in E\\}$ is the set of pinned distances from
$x$. Our first theorem is a generalization of this result in the form of
Theorem 1.1.

######  Theorem 1.2.

Given a tree $T$ with $k\geq 1$ edges and an arbitrary vertex $v,$ let
$E\subset\mathbb{F}_{p}^{2}$ with $|E|\geq 5\cdot 2^{16k}\cdot p^{5/4}$. There
is a subset $E^{\prime}\subset E$ with $|E^{\prime}|\geq|E|/2^{24k+2}$ such
that for any $x\in E^{\prime}$, the number of distinct trees $(T^{\prime},x)$
which are isomorphic to $(T,v)$ is at least $\gg p^{k}$.

Our next theorem addresses the case of arbitrary fields.

######  Theorem 1.3.

Given a tree $T$ with $k\geq 1$ edges and an arbitrary vertex $v$, let
$E\subset\mathbb{F}^{2}$ with $|E|\gg 1$. If $\mathtt{char}(\mathbb{F})>0$,
then we also need the restriction that
$|E|\leq\mathtt{char}(\mathbb{F})^{4/3}$. We assume in addition that any
isotropic line contains at most
$M=4^{-1}(16K)^{-(k-1)}(\lfloor|E|/8\rfloor)^{\left(\frac{2}{3}\right)^{(k-1)}}$
points from $E$. Then there is a subset $E^{\prime}\subset E$ with
$|E^{\prime}|\geq c(k)|E|^{\left(\frac{2}{3}\right)^{k}}$ such that for any
$x\in E^{\prime}$, the number of distinct trees $(T^{\prime},x)$ which are
isomorphic to $(T,v)$ is at least $\gg|E|^{\frac{2k}{3}}$, where $c(k)>0$
depends on $k,$ but is independent of $E$ and $q$.

If $\mathbb{F}$ is a specific field, says $\mathbb{R}$, then one would expect
to have better bounds. For example, Guth and Katz [7] proved that any set of
$n$ points in $\mathbb{R}^{2}$ determines at least $n/\log n$ distinct
distances, but for the pinned version, the best current record is due to Katz
and Tardos [12] with the lower bound $n^{0.8641...}$. For $k=2$, the optimal
result over the reals was given by Rudnev in [19]. Namely, he showed that any
set of $n$ points in $\mathbb{R}^{2}$ determines at least $n^{2}/\log^{3}n$
distinct hinges. We conjecture that, in the form of Theorem 1.3, the optimal
lower bound should be $\gtrsim n^{k}$. For similar configurations, we refer
the reader to [1, 10, 11, 16] and references therein for more details.

##  2\. Preliminary: main lemmas

Theorems 1.2 and 1.3 will be proved by induction, but the argument is
complicated. The main difficulty arises from the property that a vertex might
have many neighborhoods in the tree, which makes the iteration procedure
become much harder.

In inductive steps, we need strengthened versions of the distance result from
Murphy et al. in [17] for two sets which play a crucial role. Because of the
peculiar effects of zero distances, we will frequently make use of the pinned
nonzero distance set, $\Delta^{*}_{x}(E)$, the set of nonzero distances
between a fixed point $x$ and points in $E$. More precisely, we define

$\Delta^{*}_{x}(E):=\\{||x-y||:y\in E,||x-y||\neq 0\\}.$

We first recall the following result from [17].

######  Theorem 2.1.

([17, Theorem 4]) Let $E$ be a subset in $\mathbb{F}_{p}^{2}$ with
$5p^{5/4}\leq|E|\leq p^{4/3}$. Let $\mathcal{T}^{*}(E,E,E)$, or in short
$\mathcal{T}^{*}(E)$, be the number of triples $(a,b,c)\in E\times E\times E$
such that $||a-b||=||a-c||$ and $||b-c||\neq 0$. Then

$\mathcal{T}^{*}(E)\leq\frac{|E|^{3}}{p}+5p^{2/3}|E|^{5/3}+5p^{1/4}|E|^{2}.$

######  Remark 2.1.

We note that the constant factor of the terms $p^{2/3}|E|^{5/3}$ and
$p^{1/4}|E|^{2}$ is not stated precisely as such in [17], but it can be
bounded by $5$ by carefully following the computations in the proof.

Using this theorem, we have a result on distances between two different sets.

######  Lemma 2.2.

Let $E$ and $F$ be two subsets in $\mathbb{F}_{p}^{2}$ with
$5p^{5/4}\leq|E|=|F|\leq p^{4/3}$, then there exists a set $F^{\prime}\subset
F$ such that $|F^{\prime}|\geq\frac{1}{2^{8}}(|F|+1)$ and
$|\Delta^{*}_{x}(E)|\gg p$ for any $x\in F^{\prime}$.

###### Proof.

Let $I$ be the number of isosceles triangles of the form $(x,a,b)\in F\times
E\times E$ such that $||x-a||=||x-b||\neq 0$. We now set $n=|E|=|F|.$ It is
clear that $I$ is bounded from above by $\mathcal{T}^{*}(E\cup F)$. So,
Theorem 2.1 gives

(1)
$I\leq\frac{(2n)^{3}}{p}+20p^{2/3}n^{5/3}+20p^{1/4}n^{2}\leq\frac{16n^{3}}{p}.$

Let $C_{\delta}$ be the circle centered at the origin of radius $\delta$. By
noticing that no point $x\in F$ can have a zero distance to more than $2p-1$
points in $E$, we see

(2) $\frac{|E||F|}{2}\leq|F|(|E|-2p+1)\leq\sum_{x\in
F}\sum_{\delta\in\Delta^{*}_{x}(E)}|E\cap(x+C_{\delta})|.$

Applying the Cauchy-Schwarz inequality to (2), we get

$\frac{n^{2}}{2}=\frac{|E||F|}{2}\leq\sum_{x\in
F}\sum_{\delta\in\Delta^{*}_{x}(E)}|E\cap(x+C_{\delta})|\leq\left(\sum_{x\in
F}|\Delta^{*}_{x}(E)|\right)^{1/2}\cdot\left(\sum_{x\in
F}\sum_{\delta\in\Delta^{*}_{x}(E)}|E\cap(x+C_{\delta})|^{2}\right)^{1/2}.$

Noticing that the double sum on the right hand side is $I^{\frac{1}{2}},$ we
apply (1) to get that this is bounded from above by

$\left(\sum_{x\in
F}|\Delta^{*}_{x}(E)|\right)^{1/2}\cdot\frac{4n^{3/2}}{p^{1/2}}.$

Combining these calculations, we get that

$\sum_{x\in F}|\Delta^{*}_{x}(E)|\geq\frac{np}{64}.$

Let $F^{\prime}:=\\{x\in F\colon|\Delta^{*}_{x}(E)|\geq p/129\\}$. Now for
contradiction, suppose that $|F^{\prime}|\leq|F|/129$.

Then we would have

$\sum_{x\in F}|\Delta^{*}_{x}(E)|=\sum_{x\in F^{\prime}}+\sum_{x\not\in
F^{\prime}}\leq\frac{np}{129}+\frac{np}{129}<\frac{np}{64}.$

This leads to a contradiction. Hence,

$|F^{\prime}|\geq|F|/129\geq(|F|+1)/2^{8}.$

∎

When the set is of large size, we have much more freedom when bounding the
number of isosceles triangles. More precisely, in the following lemma,
compared to Lemma 2.2, we do not require that $E$ and $F$ have the same size.

######  Lemma 2.3.

Let $E$ and $F$ be two subsets in $\mathbb{F}_{p}^{2}$ with $|E|\geq
4p,|F|\geq 8p$, and $|F||E|^{2}\geq 64p^{4}$, then there exists a set
$F^{\prime}\subset F$ such that $|F^{\prime}|\geq\frac{|F|}{24}$ and
$|\Delta^{*}_{x}(E)|\gg p$ for any $x\in F^{\prime}$.

###### Proof.

In this proof, we first follow an argument of Hanson, Lund, and Roche-Newton
for one set in [8]. Let $\mathcal{T}^{*}(F,E,E)$ be the number of triples
$(a,b,c)\in F\times E\times E$ such that $||a-b||=||a-c||$ and $||b-c||\neq
0$. We now show that

$\mathcal{T}^{*}(F,E,E)\leq\frac{|F||E|^{2}}{p}+p^{1/2}|F|^{1/2}\left(\frac{4|E|^{4}}{p^{2}}+10p|E|^{2}\right)^{1/2}.$

To prove this inequality, we first recall the definition of bisector energy
from [8]. For any two points $(a,b)\in E\times E$, we denote their bisector
line by $B(a,b)$, the bisector energy associated to $E$ is defined by

$Q(E):=\\{(a,b,c,d)\in E^{4}\colon B(a,b)=B(c,d),||a-b||\neq 0\\}.$

Hanson et al. proved in their Theorem 3 that

$Q(E)\ll\frac{|E|^{4}}{p^{2}}+q|E|^{2}.$

The explicit constant can be computed easily from their proof. Namely, in
their Lemma 13, one would have the upper bound
$\frac{|E|^{4}}{p}+2p^{2}|E|^{2}$ from Iosevich and Rudnev’s paper [9].
Substituting this upper bound to their Lemma 11 and Theorem 3 would give us

$Q(E)\leq\frac{4|E|^{4}}{p^{2}}+10p|E|^{2}.$

We now observe that the equation $||a-b||=||a-c||$ with $||b-c||\neq 0$ can be
viewed as an incidence between $a\in F$ and the bisector line $B(a,c)$. So our
problem is reduced to an incidence bound. Let $L$ be the multi-set of bisector
lines determined by pairs of points of non-zero distances in $E$. The above
observation tells us that

$\mathcal{T}^{*}(F,E,E)\leq\mathcal{I}(F,L),$

here $\mathcal{I}(F,L)$ means the number of incidences between points in $F$
and lines in $L$.

In [8, Lemma 9], it has been proved that

$\mathcal{I}(F,L)\leq\frac{|F||L|}{p}+p^{1/2}|F|^{1/2}\left(\sum_{\ell\in\overline{L}}m(\ell)^{2}\right)^{1/2},$

where $\overline{L}$ is the set of distinct elements in $L$ and $m(\ell)$ is
the multiplicity of $\ell$.

We also note that

$\sum_{\ell}m(\ell)^{2}=Q(E).$

In other words, we would obtain

$\mathcal{T}^{*}(F,E,E)=\mathcal{I}(F,L)\leq\frac{|F||E|^{2}}{p}+p^{1/2}|F|^{1/2}\left(\frac{4|E|^{4}}{p^{2}}+10p|E|^{2}\right)^{1/2}.$

So, if $|F|\geq 8p$ and $|F||E|^{2}\geq 64p^{4}$, we obtain

$\mathcal{T}^{*}(F,E,E)\leq\frac{2|F||E|^{2}}{p}.$

We now run the same argument as in Lemma 2.2 to conclude that there exists a
set $F^{\prime}\subset F$ with $|F^{\prime}|\geq|F|/24$ and for all $x\in
F^{\prime}$, we have

$|\Delta_{x}^{*}(E)|\geq\frac{p}{24}.$

∎

With the same approach, we obtain a similar result in the setting of arbitrary
fields $\mathbb{F}$. Before stating it, we need a version of Theorem 2.1 in
$\mathbb{F}^{2}$.

######  Theorem 2.4.

([17, Theorem 1.4]) Let $E$ be a set in $\mathbb{F}^{2}$. If
$\mathtt{char}(\mathbb{F})>0$ is prime, then we need the restriction that
$|E|\leq\mathtt{char}(\mathbb{F})^{4/3}$. Let $\mathcal{T}^{*}(E)$ be the
number of triples $(a,b,c)\in E\times E\times E$ such that $||a-b||=||a-c||$
and $||b-c||\neq 0$, then $\mathcal{T}^{*}(E)\leq K|E|^{7/3}$, for some
positive constant $K\geq 4$.

The next lemma is in line with Lemma 2.2 with Theorem 2.4 in place of Theorem
2.1.

######  Lemma 2.5.

Let $E$ and $F$ be two finite sets in $\mathbb{F}^{2}$ with $|E|=|F|=n$.
Assume that any isotropic line contains at most $M<n/4$ points from $E$. Then
there exists a set $F^{\prime}\subset F$ such that $|F^{\prime}|\geq
n^{2/3}/(8(K+1))$ and $|\Delta^{*}_{x}(E)|\gg n^{2/3}$ for any $x\in
F^{\prime}$, where the constant $K$ comes from Theorem 2.4.

###### Proof.

Let $C_{\delta}$ be the circle of radius $\delta$ centered at the origin. Let
$\Delta^{*}_{x}(E)$ be the set of non-zero distances from $x\in F$ to $E$.
Because we have no more than $M$ points on any isotropic line, we have

$\frac{n^{2}}{2}\leq|F|(|E|-2M+1)\leq\sum_{x\in
F}\sum_{\delta\in\Delta^{*}_{x}(E)}|E\cap(x+C_{\delta})|.$

Applying the Cauchy-Schwarz inequality as in the proof of Lemma 2.2, one has

$\frac{n^{2}}{2}\leq\left(\sum_{x\in
F}|\Delta^{*}_{x}(E)|\right)^{1/2}\cdot\left(\sum_{x\in
F}\sum_{\delta\in\Delta^{*}_{x}(E)}|E\cap(x+C_{\delta})|^{2}\right)^{1/2}.$

We now observe that

$\sum_{x\in F}\sum_{\delta\in\Delta^{*}_{x}(E)}|E\cap(x+C_{\delta})|^{2}$

is the number of triples $(x,y,z)\in F\times E\times E$ such that
$||x-y||=||x-z||\neq 0$. By applying Theorem 2.4 with $A=E\cup F$, and taking
into account the degenerate cases where $y=z,$ the number of such triples is
bounded by at most $K|A|^{7/3}+|A|^{2}\leq(K+1)|A|^{7/3}$.

Thus,

$\sum_{x\in F}|\Delta^{*}_{x}(E)|\geq\frac{1}{4(K+1)}n^{5/3}.$

Let $F^{\prime}:=\\{x\in
F\colon|\Delta^{*}_{x}(E)|\geq\frac{1}{8(K+1)}n^{2/3}\\}$. For contradiction,
suppose that $|F^{\prime}|<\frac{1}{8(K+1)}n^{2/3}$.

Then we would have

$\sum_{x\in F}|\Delta^{*}_{x}(E)|=\sum_{x\in F^{\prime}}+\sum_{x\not\in
F^{\prime}}<\frac{n^{5/3}}{8(K+1)}+\frac{n^{5/3}}{8(K+1)}<\frac{n^{5/3}}{4(K+1)}.$

This leads to a contradiction. Hence,

$|F^{\prime}|\geq\frac{1}{8(K+1)}n^{2/3}.$

∎

##  3\. Proof of Theorem 1.2

With lemmas in the previous section, we are ready to prove Theorem 1.2. We
fall in two cases: sets of medium size and sets of large size.

###  3.1. Sets of Medium size

###### Proof of Theorem 1.2 for sets of medium size.

We are going to prove the following stronger statement by induction:

######  Theorem 3.1.

Given a tree $T$ with $k$ edges and an arbitrary vertex $v$, let
$E,F\subset\mathbb{F}_{p}^{2}$ with $5\cdot 2^{16k}\cdot
p^{5/4}\leq|E|=|F|\leq p^{4/3}$. There is a subset $E^{\prime}$ of $E$ with
$|E^{\prime}|\geq|E|/2^{8k}$ such that for any $x\in E^{\prime}$, the number
of distinct trees $(T^{\prime},x)$ that are isomorphic to $(T,v)$ and have
$V(T^{\prime})\setminus\\{x\\}\subset F$ is at least $\gg p^{k}$.

We prove the theorem by induction on $k$. The case $k=1$ follows from Lemma
2.2. For any $k>1,$ we now assume that the theorem holds for any tree with at
most $k-1$ edges, then show that it also holds for the case of $k$ edges.

Case $1$: The degree of $v$ in $T$ is one. Assume that the neighbor of $v$ in
$T$ is $u$. Define $T_{1}:=T\setminus\\{v\\}$. By induction, we can find a
subset $F_{2}^{\prime}\subset F_{2}$ such that
$|F_{2}^{\prime}|\geq|F_{2}|/2^{8k-8}$ such that for any $y\in
F_{2}^{\prime}$, the number of distinct trees $(T_{1}^{\prime},y)$, which are
isomorphic to $(T_{1},u)$ and $V(T_{1}^{\prime})\setminus\\{y\\}\subset
F_{1}$, is at least $\gg p^{k-1}$.

We would like to apply Lemma 2.2 to $E$ and $F_{2}^{\prime},$ but they are not
the same size, so we will break $E$ up into pieces of the appropriate size.
Set $s=\lfloor|E|/|F_{2}^{\prime}|\rfloor\geq 2$. Now, for $j=1,\dots,s,$
greedily select disjoint subsets $G_{j}\subset E,$ of size $|F_{2}^{\prime}|.$
We apply Lemma 2.2 for $F_{2}^{\prime}$ and $G_{j}$ for $j=1,\dots,s$ to
conclude that there exists a subset $G_{j}^{\prime}\subset G_{j}$ such that

(3) $\displaystyle|G_{j}^{\prime}|\geq(|G_{j}|+1)/2^{8}$

and any $x\in G_{j}^{\prime}$, we have $|\Delta^{*}_{x}(F_{2}^{\prime})|\gg
p$. Now set

$E^{\prime}:=\bigcup_{j=1}^{s}G_{j}^{\prime}.$

Because the $G_{j}$ are disjoint, the size of the union is just the sum as $j$
ranges from $1$ to $s$. Combining (3), $|G_{j}|=|F^{\prime}_{2}|$, and
$|E|=|F|$, gives that

$\displaystyle\left|E^{\prime}\right|=$
$\displaystyle\sum\limits^{s}_{j=1}|G_{j}^{\prime}|\geq\sum\limits^{s}_{j=1}\frac{|G_{j}|+1}{2^{8}}=\sum\limits^{s}_{j=1}\frac{|F^{\prime}_{2}|+1}{2^{8}}$
$\displaystyle\geq$ $\displaystyle
s\left(\frac{|F_{2}|}{2^{8k}}+\frac{1}{2^{8}}\right)\geq
s\left(\frac{|E|-1}{2^{8k+1}}+\frac{1}{2^{8}}\right)$ $\displaystyle\geq$
$\displaystyle\frac{s}{2}\left(\frac{|E|}{2^{8k}}\right)\geq\frac{|E|}{2^{8k}}.$

Every $x\in E^{\prime}$, comes from some $G_{j},$ so the number of distinct
trees $(T^{\prime},x)$ that are isomorphic to $(T,v)$ and
$V(T^{\prime})\setminus\\{x\\}\subset F$ is at least $\gg p^{k}$.

Case $2$: The degree of $v$ in $T$ is more than one. Then we can partition the
tree $T$ into two smaller trees, say $T_{1}$ and $T_{2}$ with $k_{1}$ and
$k_{2}$ edges, respectively, sharing only the vertex $v$.

We will run the following argument for the sets $E_{1}$ and $E_{2},$
separately. For a fixed choice of $i$, applying the induction hypothesis for
the sets $E_{i}$ and $F_{1}$, we can say that there exists a subset
$E_{i}^{\prime}\subset E_{i}$ with $|E_{i}^{\prime}|\geq|E_{i}|/2^{8k_{1}}$
such that for any $x\in E_{i}^{\prime}$, the number of distinct trees
$(T^{\prime},x)$, which are isomorphic to $(T_{1},v)$ and
$V(T^{\prime})\setminus\\{x\\}\subset F_{1}$, is at least $p^{k_{1}}$.

We now pick a subset $F_{2}^{\prime}\subset F_{2}$ with
$|F_{2}^{\prime}|=|E_{i}^{\prime}|.$ The induction hypothesis guarantees that
there exists a subset $E_{i}^{\prime\prime}\subset E_{i}^{\prime}$ with

$|E_{i}^{\prime\prime}|\geq|E_{i}^{\prime}|/2^{8k_{2}}\geq|E_{i}|/2^{8(k_{1}+k_{2})}=|E_{i}|/2^{8k},$

such that for any $x\in E_{i}^{\prime\prime},$ the number of distinct trees
$(T^{\prime\prime},x),$ which are isomorphic to $(T_{2},v)$ and
$V(T^{\prime\prime})\setminus\\{x\\}\subset F_{2}^{\prime}$ is at least $\gg
p^{k_{2}}.$

It is clear that the number of distinct trees $(T^{\prime},x)$, which are
isomorphic to $(T,v)$ and $V(T^{\prime})\setminus\\{x\\}\subset F$ is at least
the product of the number of trees $(T^{\prime},x)$ and $(T^{\prime\prime},x)$
for any $x\in E_{i}^{\prime\prime}$, giving us at least $\gg
p^{k_{1}+k_{2}}=p^{k}$. By running this argument for both $E_{1}$ and $E_{2}$,
we complete the proof.

∎

###  3.2. Sets of large size

Using the same argument as in the case of sets of medium size and Lemma 2.3 in
place of Lemma 2.2, the next theorem is obtained.

######  Theorem 3.2.

Given a tree $T$ with $k$ edges and an arbitrary vertex $v$, let
$E,F\subset\mathbb{F}_{p}^{2}$ with $|E|=|F|\geq 4\cdot 2^{16k}\cdot p^{4/3}$.
There is a subset $E^{\prime}$ of $E$ with $|E^{\prime}|\geq|E|/2^{8k}$ such
that for any $x\in E^{\prime}$, the number of distinct trees $(T^{\prime},x)$
that are isomorphic to $(T,v)$ and have $V(T^{\prime})\setminus\\{x\\}\subset
F$ is at least $\gg p^{k}$.

###  3.3. Conclusion

Compared to the conclusion of Theorem 1.2, Theorems 3.1 and 3.2 are stronger
in the ranges $5\cdot 2^{16k}\cdot p^{5/4}\leq|E|\leq p^{4/3}$ and $|E|\geq
4\cdot 2^{16k}\cdot p^{4/3}$.

In the range, $p^{4/3}\leq|E|\leq 4\cdot 2^{16k}\cdot p^{4/3}$, we simply take
a subset of size $p^{4/3}$ and apply Theorem 3.1 to conclude that there exists
a subset $E^{\prime}\subset E$ with $|E^{\prime}|\geq|E|/2^{24k+2}$ such that
for any $x\in E^{\prime}$, the number of distinct trees $(T^{\prime},x)$ that
are isomorphic to $(T,v)$ and have $V(T^{\prime})\setminus\\{x\\}\subset F$ is
at least $\gg p^{k}$. This completes the proof of Theorem 1.2.

###  3.4. Remarks over arbitrary finite fields

The argument in the proof of Theorem 3.2 works not only over prime fields, but
also over arbitrary finite fields. Therefore, in the setting of arbitrary
finite fields $\mathbb{F}_{q}$, the following weaker result is achieved.

######  Theorem 3.3.

Given a tree $T$ with $k$ edges and an arbitrary vertex $v$, let
$E,F\subset\mathbb{F}_{q}^{2}$ with $|E|=|F|\geq 4\cdot 2^{16k}\cdot q^{4/3}$.
There is a subset $E^{\prime}$ of $E$ with $|E^{\prime}|\geq|E|/2^{8k}$ such
that for any $x\in E^{\prime}$, the number of distinct trees $(T^{\prime},x)$
that are isomorphic to $(T,v)$ and have $V(T^{\prime})\setminus\\{x\\}\subset
F$ is at least $\gg q^{k}$.

##  4\. Proof of Theorem 1.3

The idea for the proof of Theorem 1.3 is the same as that of Theorem 1.2, in
particular, we will make use of Lemma 2.5 instead of Lemma 2.2. For small sets
in an arbitrary field, we need to carefully run an analysis on the number of
intersection points between isotropic lines and the sets $E$ and $F$. We now
state and prove a more general statement.

######  Theorem 4.1.

Given a tree $T$ with $k$ edges and an arbitrary vertex $v$, let
$E,F\subset\mathbb{F}^{2}$ with $|E|=|F|$. If $\mathtt{char}(\mathbb{F})>0$,
then we need the restriction that $|E|\leq\mathtt{char}(\mathbb{F})^{4/3}$. We
assume in addition that any isotropic line contains at most
$M=4^{-1}(16K)^{-(k-1)}(\lfloor|F|/8\rfloor)^{\left(\frac{2}{3}\right)^{(k-1)}}$
points from $E$ or $F$. There is a subset $F^{\prime}$ of $F$ with
$|F^{\prime}|\geq(16K)^{-k}|F|^{\left(\frac{2}{3}\right)^{k}}$ such that for
any $x\in F^{\prime},$ the number of distinct trees $(T^{\prime},x)$ that are
isomorphic to $(T,v)$ with $V(T^{\prime})\setminus\\{x\\}\subset E$ is at
least $\gg|E|^{\frac{2k}{3}}.$

We proceed by induction on the number of edges in the tree. Lemma 2.5 yields
the desired result for one edge. For a tree with $k>1,$ we assume that the
statement of the theorem holds for any tree with at most $k-1$ edges. We will
again select two subsets $E_{1},E_{2}\subset E$ both of size
$\lfloor|E|/2\rfloor,$ and similarly select $F_{1},F_{2}\subset F.$

Case 1: The degree of $v$ in $T$ is one. In this case, we denote the neighbor
of $v$ in $T$ by $u$. Define $T_{1}:=T\setminus\\{v\\}.$ We now want to apply
the induction hypothesis for two sets $F_{1}$ and $F_{2}$ for the tree $T_{1}$
of $k-1$ edges. But first, we need to verify that $F_{1}$ and $F_{2}$ satisfy
the condition on the maximal number of points on each isotropic line with
respect to their sizes. Specifically, we need to check that the bound of no
more than $M$ points from $F$ on any isotropic line will guarantee that we do
not have too many points from any isotropic line on either $F_{i}$, in terms
of the size of the $F_{i}$, to apply the induction hypothesis. To be precise,
we need that

(4)
$\frac{1}{4}\left(\frac{1}{16K}\right)^{k-2}\left(\left\lfloor\frac{|F_{i}|}{8}\right\rfloor\right)^{\left(\frac{2}{3}\right)^{k-2}}\geq
M=\frac{1}{4}\left(\frac{1}{16K}\right)^{k-1}\left(\left\lfloor\frac{|F|}{8}\right\rfloor\right)^{\left(\frac{2}{3}\right)^{(k-1)}},$

which is true because

$(16K)^{\left(\frac{3}{2}\right)^{k-2}}\left\lfloor\frac{|F_{i}|}{8}\right\rfloor\geq\left\lfloor\frac{|F|}{8}\right\rfloor^{\frac{2}{3}}.$

Thus, we can find a subset $F_{2}^{\prime}\subset F_{2}$ such that
$|F_{2}^{\prime}|\geq(16K)^{-(k-1)}|F_{2}|^{\left(\frac{2}{3}\right)^{k-1}}$
such that for any $y\in F_{2}^{\prime}$, the number of distinct trees
$(T_{1}^{\prime},y)$ that are isomorphic to $(T_{1},u)$ and have
$V(T_{1}^{\prime})\setminus\\{y\\}\subset F_{1},$ is at least $\gg
n^{\frac{2(k-1)}{3}}.$

We would like to apply Lemma 2.5 to $E$ and $F_{2}^{\prime},$ but they are not
the same size, so as before we will break $E$ up into pieces of the
appropriate size. Set $s=\lfloor|F|/|F_{2}^{\prime}|\rfloor\geq 2.$ Now, for
$j=1,\dots,s,$ greedily select disjoint subsets $G_{j}\subset E,$ of size
$|F_{2}^{\prime}|.$ Notice that the $G_{j}$ and $F_{2}^{\prime}$ also satisfy
the condition of having no more than $M$ points on any isotropic line, as they
are subsets of $E$ and $F,$ respectively. Because
$M\leq|F_{2}^{\prime}|/4=|G_{j}|/4,$ we can apply Lemma 2.5 for
$F_{2}^{\prime}$ and each $G_{j}$ to conclude that there exist a subsets
$G_{j}^{\prime}\subset G_{j}$ such that

(5) $\displaystyle|G_{j}^{\prime}|\geq\frac{|G_{j}|^{\frac{2}{3}}}{8(K+1)}$

and for any $x\in G_{j}^{\prime}$, we have
$|\Delta^{*}_{x}(F_{2}^{\prime})|\gg|F_{2}^{\prime}|^{\frac{2}{3}}$. Now set

(6) $\displaystyle E^{\prime}:=\bigcup_{j=1}^{s}G_{j}^{\prime}.$

We are going to prove the following claim.

(7)
$\displaystyle|E^{\prime}|\geq(16K)^{-k}|E|^{\left(\frac{2}{3}\right)^{k}}.$

To prove (7), we see from (6), (5), $s\geq 2$, and $|G_{j}|=|F_{2}^{\prime}|$
that

$\displaystyle|E^{\prime}|=$
$\displaystyle\sum\limits^{s}_{j=1}|G_{j}^{\prime}|\geq\sum\limits^{s}_{j=1}\frac{|G_{j}|^{\frac{2}{3}}}{8(K+1)}=\sum\limits^{s}_{j=1}\frac{|F_{2}^{\prime}|^{\frac{2}{3}}}{8(K+1)}\geq
2\frac{\left((16K)^{-(k-1)}|F_{2}|^{\left(\frac{2}{3}\right)^{k-1}}\right)^{\frac{2}{3}}}{8(K+1)}$
(8) $\displaystyle\geq$
$\displaystyle(4K+4)^{-1}(16K)^{-\frac{2}{3}(k-1)}|F_{2}|^{\left(\frac{2}{3}\right)^{k}}\geq
4(16K)^{-k}|F_{2}|^{\left(\frac{2}{3}\right)^{k}}.$

It follows from $k\geq 2$, $|F_{2}|\geq\frac{|E|-1}{2}$ that

$\displaystyle|F_{2}|^{\left(\frac{2}{3}\right)^{k}}\geq$
$\displaystyle\left(\frac{|E|-1}{2}\right)^{\left(\frac{2}{3}\right)^{k}}=|E|^{\left(\frac{2}{3}\right)^{k}}\left(\frac{1}{2}\right)^{\left(\frac{2}{3}\right)^{k}}\left(1-\frac{1}{|E|}\right)^{\left(\frac{2}{3}\right)^{k}}$
(9) $\displaystyle>$
$\displaystyle|E|^{\left(\frac{2}{3}\right)^{k}}\left(\frac{1}{2}\right)^{\left(\frac{2}{3}\right)^{k}}\cdot\frac{1}{2}\geq\frac{1}{4}|E|^{(\frac{2}{3})^{k}}.$

Combining (4) and (4), we get (7), as claimed. This tells us that there exists
a subset $|E^{\prime}|\geq(16K)^{-k}|E|^{\left(\frac{2}{3}\right)^{k}}$ such
that for any $x\in E^{\prime},$ the number of distinct trees $(T^{\prime},x)$
which are isomorphic to $(T,v)$ with $V(T^{\prime})\setminus\\{x\\}\subset F$
is at least $\gg n^{\frac{2k}{3}}.$

Case $2$: The degree of $v$ in $T$ is more than one. Then we can partition the
tree $T$ into two smaller trees, say $T_{1}$ and $T_{2}$ with $k_{1}$ and
$k_{2}$ edges, respectively, sharing only the vertex $v$.

We will run the following argument for the sets $E_{1}$ and $E_{2},$
separately. For a fixed choice of $i$, applying the induction hypothesis for
the sets $E_{i}$ and $F_{1}$, we can say that there exists a subset
$E_{i}^{\prime}\subset E_{i}$ with
$|E_{i}^{\prime}|\geq(16K)^{-k_{1}}|E_{i}|^{\left(\frac{2}{3}\right)^{k_{1}}}$
such that for any $x\in E_{i}^{\prime}$, the number of distinct trees
$(T^{\prime},x)$, which are isomorphic to $(T_{1},v)$ and
$V(T^{\prime})\setminus\\{x\\}\subset F_{1}$, is at least $\gg
n^{\frac{2k_{1}}{3}}$.

We now pick a subset $F_{2}^{\prime}\subset F_{2}$ with
$|F_{2}^{\prime}|=|E_{i}^{\prime}|.$ Again, we notice that since
$E_{i}^{\prime}$ and $F_{2}^{\prime}$ are subsets of $E$ and $F,$
respectively, we are guaranteed that neither of them has more than $M$ points
on any isotropic line, but we must again check the conditions of the induction
hypothesis in order to apply it, as we did when verifying (4). Specifically,
we need to ensure that

(10)
$\frac{1}{4}\left(\frac{1}{16K}\right)^{k_{2}-1}\left(\left\lfloor\frac{|F_{i}|}{8}\right\rfloor\right)^{\left(\frac{2}{3}\right)^{k_{2}-1}}\geq
M=\frac{1}{4}\left(\frac{1}{16K}\right)^{k-1}\left(\left\lfloor\frac{|F|}{8}\right\rfloor\right)^{\left(\frac{2}{3}\right)^{k-1}},$

which is guaranteed as we recall $k=k_{1}+k_{2}$ and see

$(16K)^{k_{1}+\left(\frac{3}{2}\right)^{k_{2}-1}}\left\lfloor\frac{|F_{i}|}{8}\right\rfloor\geq\left\lfloor\frac{|F_{i}|}{8}\right\rfloor\geq\left(\left\lfloor\frac{|F|}{8}\right\rfloor\right)^{\left(\frac{2}{3}\right)^{k_{1}}}.$

The induction hypothesis tells us that there exists a subset
$E_{i}^{\prime\prime}\subset E_{i}^{\prime}\subset E$ such that for any $x\in
E_{i}^{\prime\prime},$ the number of distinct trees $(T^{\prime\prime},x)$
that are isomorphic to $(T_{2},v)$ and have
$V(T^{\prime\prime})\setminus\\{x\\}\subset F_{2}^{\prime}$ is at least $\gg
n^{\frac{2k_{2}}{3}}.$ Moreover, we also have

$\displaystyle|E_{i}^{\prime\prime}|\geq$
$\displaystyle(16K)^{-k_{2}}|E_{i}^{\prime}|^{\left(\frac{2}{3}\right)^{k_{2}}}\geq(16K)^{-k_{2}}\left((16K)^{-k_{1}}|E_{i}|^{\left(\frac{2}{3}\right)^{k_{1}}}\right)^{\left(\frac{2}{3}\right)^{k_{2}}}$
$\displaystyle\geq$
$\displaystyle(16K)^{-(k_{1}\cdot\left(\frac{2}{3}\right)^{k_{2}}+k_{2})}|E_{i}|^{\left(\frac{2}{3}\right)^{k_{1}}\left(\frac{2}{3}\right)^{k_{2}}}$
$\displaystyle\geq$ $\displaystyle
4(16K)^{-(k_{1}+k_{2})}\cdot|E_{i}|^{\left(\frac{2}{3}\right)^{k_{1}}\left(\frac{2}{3}\right)^{k_{2}}}=4(16K)^{-k}|E_{i}|^{\left(\frac{2}{3}\right)^{k}}\geq(16K)^{-k}|E|^{\left(\frac{2}{3}\right)^{k}},$

where the last inequality can be explained by the same argument as in (4).

It is clear that the number of distinct trees $(T^{\prime},x)$ that are
isomorphic to $(T,v)$ and have $V(T^{\prime})\setminus\\{x\\}\subset F$ is at
least the product of the number of trees $(T^{\prime},x)$ and
$(T^{\prime\prime},x)$ for any $x\in E_{i}^{\prime\prime}$, giving us at least
$\gg n^{\frac{2(k_{1}+k_{2})}{3}}=n^{\frac{2k}{3}}$. By running this argument
for both $E_{1}$ and $E_{2}$, we complete the proof.

##  5\. Acknowledgements

T. Pham would like to thank to the VIASM for the hospitality and for the
excellent working condition.

## References

  * [1] M. Bennett, J. Chapman, D. Covert, D. Hart, A. Iosevich, and J. Pakianathan, Long paths in the distance graph over large subsets of vector spaces over finite fields, Journal of the Korean Mathematical Society, 53(1), 115–126 (2016).
  * [2] J. Chapman, M. B. Erdogan, D. Hart, A. Iosevich and D. Koh,  Pinned distance sets, k-simplices, Wolff’s exponent in finite fields and sum-product estimates, Mathematische Zeitschrift, 271 (2012), no. 1-2, 63-93.
  * [3] X. Du, L. Guth, Y. Ou, H. Wang, B. Wilson and R. Zhang, Weighted restriction estimates and application to Falconer distance set problem, American Journal of Mathematics, 143(1), 175–211.
  * [4] X. Du and R. Zhang, Sharp $L^{2}$\- estimates of the Schrödinger maximal function in higher dimensions, Annal of Mathematics, 189 (2019), no. 3, 837–861.
  * [5] X. Du, A. Iosevich, Y. Ou, H. Wang and R. Zhang, An improved result for Falconer’s distance set problem in even dimensions, Mathematische Annalen, 380(3), 1215–1231.
  * [6] L. Guth, A. Iosevich, Y. Ou and H. Wang, On Falconer’s distance set problem in the plane, Inventiones mathematicae, 219(3), 779–830.
  * [7] L. Guth and N. H. Katz, On the Erdős distinct distances problem in the plane, Annal of Mathematics, 181(2) (2015), 155–190.
  * [8] B. Hanson, B. Lund and O. Roche-Newton, On distinct perpendicular bisectors and pinned distances in finite fields, Finite Fields and Their Applications, 37 (2016): 240–264.
  * [9] A. Iosevich and M. Rudnev, _Erdős distance problem in vector spaces over finite fields_ , Transactions of the American Mathematical Society, 359 (2007), 6127–6142.
  * [10] A. Iosevich and J. Passant, Finite Point Configurations in the Plane, Rigidity and Erdős Problems, Proceedings of the Steklov Institute of Mathematics, 303(1) (2018): 129–139.
  * [11] A. Iosevich, G. Jardine, and B. McDonald, Cycles of Arbitrary Length in Distance Graphs on $\mathbb{F}_{q}^{d}$, Proceedings of the Steklov Institute of Mathematics, 314(1) (2021): 27–43.
  * [12] N. H. Katz and G. Tardos, A new entropy inequality for the Erdős distance problem, Towards a theory of geometric graphs, contemporary mathematics, J. Pach (ed.), vol. 342, American Mathematical Society, Providence, RI, 2004, pp. 119–126.
  * [13] D. Koh and C-Y. Shen, Sharp extension theorems and Falconer distance problems for algebraic curves in two dimensional vector spaces over finite fields, Revista Matematica Iberoamericana, 28(1) (2012): 157–178.
  * [14] D. Koh, T. Pham, C-Y. Shen, and L. A. Vinh, A sharp exponent on sum of distance sets over finite fields, Mathematische Zeitschrift, 297(3) (2021): 1749–1765.
  * [15] D. Koh, T. Pham and L. A. Vinh, Extension theorems and a connection to the Erdos-Falconer distance problem over finite fields, Journal of Functional Analysis, 281(8) (2021): 109137.
  * [16] N. Lyall, A. Magyar, and H. Parshals, Spherical configurations over finite fields, American Journal of Mathematics, 142(2) (2020): 373–404.
  * [17] B. Murphy, G. Petridis, T. Pham, M. Rudnev and S. Stevens, On the pinned distances problem over finite fields, Journal of London Mathematical Society, 105(1) (2022): 469-499.
  * [18] Y. Ou and K. Taylor,  Finite point configurations and the regular value theorem in a fractal setting, arXiv:2003.06218, accepted in Indiana Journal of Mathematics (2021).
  * [19] M. Rudnev, Note on the Number of Hinges Defined by a Point Set in $\mathbb{R}^{2}$, Combinatorica, 40(5) (2020): 749–757.


# Self-Organized Agents: A LLM Multi-Agent Framework toward
Ultra Large-Scale Code Generation and Optimization

Yoichi Ishibashi
TsukushiAI
<EMAIL_ADDRESS>
&Yoshimasa Nishimura
TsukushiAI
<EMAIL_ADDRESS>

###### Abstract

Recent advancements in automatic code generation using large language model
(LLM) agent have brought us closer to the future of automated software
development. However, existing single-agent approaches face limitations in
generating and improving large-scale, complex codebases due to constraints in
context length. To tackle this challenge, we propose Self-Organized multi-
Agent framework (SoA), a novel multi-agent framework that enables the scalable
and efficient generation and optimization of large-scale code. In SoA, self-
organized agents operate independently to generate and modify code components
while seamlessly collaborating to construct the overall codebase. A key
feature of our framework is the automatic multiplication of agents based on
problem complexity, allowing for dynamic scalability. This enables the overall
code volume to be increased indefinitely according to the number of agents,
while the amount of code managed by each agent remains constant. We evaluate
SoA on the HumanEval benchmark and demonstrate that, compared to a single-
agent system, each agent in SoA handles significantly less code, yet the
overall generated code is substantially greater. Moreover, SoA surpasses the
powerful single-agent baseline by 5% in terms of Pass@1 accuracy. 111Our code
will be available at https://github.com/tsukushiAI/self-organized-agent.

Self-Organized Agents: A LLM Multi-Agent Framework toward
Ultra Large-Scale Code Generation and Optimization

Yoichi Ishibashi TsukushiAI<EMAIL_ADDRESS>Yoshimasa Nishimura
TsukushiAI<EMAIL_ADDRESS>

##  § 1 Introduction

In recent years, research on agents using Large Language Models (LLMs) Brown
et al. (2020); OpenAI (2023); Touvron et al. (2023), such as ReAct Yao et al.
(2023b), Reflexion Shinn et al. (2023), Toolformer Schick et al. (2023), and
AutoGPT 222https://github.com/Significant-Gravitas/, has been expanding the
possibilities of automating human tasks. These advancements have particularly
contributed to the rapid development of automatic code generation techniques
in the field of automated application and tool development Hong et al. (2023);
Dong et al. (2023); Huang et al. (2023). Compared to non-agent-based methods
Muennighoff et al. (2023); Li et al. (2023b), these research achievements have
led to remarkable performance improvements in automatic code generation Zhong
et al. (2024); Zhou et al. (2023).

Figure 1:  Left (single agent): A single agent is solely responsible for the
entire implementation. As the codebase grows larger, the load increases for
code generation, modification, and memory management, making it difficult to
manage and develop. The larger the entire codebase becomes, the more it puts
pressure on the context length during self-debugging, limiting the amount of
code that can be managed. Right (SoA): The implementation is distributed among
multiple agents. The agents are independent; code generation, modification,
and memory management are separated from other agents. Each agent manages only
its own part, allowing it to focus on the implementation regardless of the
complexity of the entire codebase. Furthermore, agents automatically multiply
according to the complexity of the problem. This allows for the generation and
modification of complex and large-scale code while maintaining a constant
amount of code management/generation/modification per agent.

Most recent research has focused on single-agent approaches for code
generation. These single-agent code generation methods face limitations,
especially in terms of scalability, when the implementation becomes complex
and requires a large codebase. The main reason for this technical difficulty
is that a single agent must manage the entire code generation process alone.
For instance, implementing a machine learning algorithm involves several
stages, such as data preprocessing, algorithm training, and result evaluation,
which include many functions and classes. When these complex components are
combined, the codebase inevitably becomes very large. However, there are
limitations to the context length of LLMs, and as the number of input tokens
increases, the inference performance decreases Levy et al. (2024); Shaham et
al. (2023); Li et al. (2023a). Consistently understanding and generating or
modifying appropriate code for such an extensive codebase poses a significant
challenge for a single agent in terms of comprehending and managing the
context. Consequently, the single-agent approach struggles to efficiently
generate and modify code as its complexity and size increase.

To tackle these challenges, we propose a self-organized multi agent framework
that can automatically generate and modify large-scale code (Figure 1). _Self-
organization_ Ashby (1947) is a phenomenon in which living organisms or matter
create an orderly, large structure as a result of their individual autonomous
behaviors, despite lacking the ability to oversee the entire system. In our
framework, self-organized agents, each responsible for different code parts or
tasks, independently generate and modify code. With the self-organization of
agents, a single agent no longer needs to comprehend the entire codebase,
making it possible to scale up large-scale code simply by increasing the
number of agents. Another feature of our framework is that agents
automatically multiply according to the complexity of the problem, allowing
the overall codebase to expand while keeping the amount of code handled by
each agent constant. These features enable the dynamic and flexible generation
and modification of large-scale code, which was impossible with the
traditional single-agent approach.

In our experiments, we evaluated the performance of this framework using
HumanEval Chen et al. (2021), a benchmark for code generation. The results
show that our self-organized multi-agent framework outperformed Reflexion
Shinn et al. (2023), an existing powerful code generation agent (§ 4.1),
demonstrating the effectiveness of our approach in generating and modifying
code. Furthermore, through a detailed analysis of the experimental results, we
revealed how agents automatically multiply according to the complexity of the
problem, effectively scaling up the overall code volume while keeping the code
generation per agent constant (§ 4.2). These experimental results support the
contribution of our framework, which overcomes the scalability issues faced by
single-agent approaches and provides a solution capable of handling larger
projects.

##  § 2 Code Generation Task

The code generation task involves generating Python functions from docstrings
Chen et al. (2021). In this task, an agent is given a docstring that defines
the types of the function’s inputs and expected outputs, as well as the
specific requirements that the function should meet. The agent is then
required to generate the code for a function that fulfills the specified
functionality. The generated code is verified for accuracy using unit tests,
and the quality of the code is evaluated based on its ability to pass the test
cases. As with previous studies Shinn et al. (2023); Zhong et al. (2024); Zhou
et al. (2023), we use the evaluation metric Pass@$1$ Chen et al. (2021), where
a problem is considered solved if any of the $k$ code samples pass all test
cases.

##  § 3 Self-organized Agent Framework

Our Self-organized Agents (SoA) framework enables efficient implementation of
large-scale and complex code by having self-organized agents independently
generate and modify small-scale and simple code. In this section, we introduce
the important components of SoA, namely the agents and the layers responsible
for more abstract processing than the agents, and finally introduce the code
generation and modification protocols in the SoA framework.

###  § 3.1 Child Agent

Child agents implement a given function based on its docstrings. As shown in
Figure 2, this agent has a simple structure consisting of two elements: an LLM
and memory. The LLM generates code from the given docstrings and modifies the
code based on the results of unit tests. The memory stores the code generated
by the agent itself and retrieves the latest code to be input to the LLM along
with the unit test feedback during code modification. If an agent has these
minimal specifications, it is possible to use an off-the-shelf agents (e.g.,
Reflexion) as a Child agent. We deliberately use a simple agent to verify the
effectiveness of SoA in a simple setup.

Figure 2:  Overview of code generation. Child agents generate executable
Python function from a given docstring. The Mother agent generates the
skeleton of the function. The Mother spawns a new initialized agent (Child or
Mother) and delegates unimplemented functions.

#### Code Generation

The main role of Child agents is to generate functions that meet the
specifications based on the given function’s docstrings. As shown in Figure 2,
the agent follows the instructions to generate the rest of the function and
complete it. The completed function implementation is stored in memory, and
the unit tests for the function are also stored as they form the basis for
future code modifications.

#### Code Modification: Empowering Child Agents with Self-Organization and
Adaptability

One of the most remarkable aspects of agents in the SoA framework is their
ability to autonomously improve their code based on the state of nearby agents
. This process sets SoA apart from traditional agent approaches and showcases
the power of self-organization in code modification. While existing agents
like Reflexion Shinn et al. (2023) rely solely on the results of unit tests,
Child agents in SoA go beyond this limitation by independently observing the
state of their mother agent, such as differences in modifications and
feedback. By gathering this invaluable information from their surrounding
environment, Child agents can adapt their behavior and make more informed
decisions about code modification, even without explicit instructions. The
modifications and feedback generated by the Mother agent serve as an important
source of information for the Child agents. Armed with these insights, Child
agents can more effectively modify their own code, contributing to the overall
improvement of the codebase in a way that is both efficient and adaptive.
Figure 3 illustrates this process, which begins with the execution of unit
tests and the retrieval of the latest implementation from memory. The Child
agent then harnesses the power of the LLM to create a code modification
proposal, seamlessly combining the information observed from the Mother agent
with the test results and the latest implementation details. By storing the
modified code in memory, Child agents create a feedback loop that continuously
refines and improves the codebase over time. This iterative process, driven by
the principles of self-organization and adaptability, enables SoA to tackle
complex code modification tasks with efficiency and effectiveness. As Child
agents work in harmony with their Mother agent, they contribute to the
creation of a more optimized and large codebase.

###  § 3.2 Mother Agent

The Mother is an agent that generates new agents (Mother or Child). Similar to
Child agents, the Mother agent independently implements the specific Python
function based on its given docstrings. The Mother has memory, code generation
capabilities, and self-debugging functions, as same as Child agents. The
unique feature of the Mother agent is its ability to generate multiple Child
agents according to the complexity of the problem and delegate parts of the
implementation to these agents. This structure allows the Mother agent to
focus on implementing abstract processes, while the Child agents generated by
the Mother agent concentrate on implementing concrete processes. This division
of labor enhances the overall efficiency and flexibility of the SoA framework.

Figure 3:  Overview of code modification. Agents (Mother/Child) observe the
state of Mother (feedback, old code, and updated code) and use this
information to improve the functions for which they are responsible. The state
of the upper agent is used to modify code by lower agents within the
hierarchy. This state propagation promotes collaboration and information
sharing throughout the hierarchy, enabling efficient code modification.

#### Code Generation

We explain the code generation process by the Mother agent using the
implementation example of the is_sum_of_odds_ten function shown in Figure 2.
The starting point is the function’s docstrings and unit tests, which are
memorized for reference in the later self-debugging phase. The first task of
the Mother agent is to generate a skeleton of the implementation from the
given docstrings, including subfunctions such as get_odd_numbers to extract
odd numbers and sum_of_numbers to calculate their sum. The number and types of
these subfunctions are automatically determined by the LLM based on the
complexity of the problem.

It is important to note that these subfunctions are unimplemented, and the
Mother agent does not directly implement them. Instead, it delegates the
implementation of the subfunctions to other agents, allowing the Mother agent
to focus on generating the skeleton and streamline its own code generation
process. After the docstrings and unit tests for the subfunctions are
generated, they are assigned to newly initialized agents for implementation.
These agents proceed with the implementation of their respective functions
without looking at the internals of the is_sum_of_odds_ten function
implemented by the Mother agent. Since agents within the same Mother can work
asynchronously, the overall code generation process is streamlined.

#### Code Modification

The Mother’s code modification is almost the same as the Child’s code
modification (Figure 3). It observes information from the upper Mother and
uses it to modify the functions it is responsible for. The only difference is
that the feedback it generates and the code before and after modification are
used by lower-level agents (Child or Mother).

###  § 3.3 Self-organized Agent Process

The Self-organized Agent (SoA) framework is a distributed framework in which
multiple agents (including Mother agents and Child agents) repeatedly generate
and modify functions. The core of this framework lies in the principle of
self-organization, where each agent functions independently without the need
to directly observe the entire codebase. The hierarchical combination of
Mother agents and Child agents forms an agent network that effectively
constructs a single large-scale codebase. In this hierarchical structure,
Mother agents decompose complex problems into more manageable smaller problems
by dividing tasks and delegating them to the agents they have generated.
Although each agent is independent, the agents as a whole can work efficiently
towards the implementation of a single function. Despite the fact that the
amount of code each agent generates, modifies, and manages is always small,
the number of agents scales, allowing the amount of code generated to be
increased indefinitely according to the difficulty of the problem. Detailed
algorithms are presented in Algorithm 1 in the appendix.

Figure 4:  Overview of the SoA framework. Mother agents and Child agents
hierarchically construct a network and perform function generation and
modification. Mother agents delegate tasks to other Mother agents or Child
agents, and each agent independently executes tasks while effectively
implementing a single function as a whole.

#### Code Generation

The code generation process in the SoA framework begins with the function’s
docstrings and unit tests. In the initial stage, there is only one initialized
Mother agent, which is the root of the tree structure. Based on the input
docstrings and unit tests, it generates docstrings and unit tests for subtasks
and passes them to other agents it generates (see § 3.2). If the tree
structure reaches a predetermined depth, the tasks are passed to Child agents;
otherwise, they are passed to newly generated Mother agents. By repeatedly
proliferating and increasing the number of agents until the last agent, it is
possible to generate large-scale code while keeping the amount of code managed
by individual agents constant.

#### Code Modification

Once code generation is complete, the process transitions to the code
modification phase. First, the implementations of all agents are combined to
create the final implementation. This final implementation is evaluated using
the unit tests provided to the root Mother, and feedback is generated from the
results. Since there are no agents higher than this root Mother, information
from higher-level agents as shown in Figure 3 is not used. The modification
process starts based on this feedback and propagates information from the root
Mother agent to the Child agents. Each agent updates its implementation based
on the received feedback, generates new feedback, and transmits it to lower-
level agents (see § 3.2). Finally, the Child agents update their own
implementations, and the process terminates (see § 3.1). This series of
processes is repeated until a predetermined maximum number of iterations is
reached.

##  § 4 Experiments

#### LLM Selection

We used GPT3.5-turbo333gpt3.5-turbo-1106 for code generation and feedback
generation.444GPT-4 was not selected due to the high experimental cost
required.

#### Baselines

We compare SoA with several state-of-the-art code generation methods including
AlphaCode Li et al. (2022), Incoder Fried et al. (2023), Codex Chen et al.
(2021), CoT Wei et al. (2022), and Gemini Pro Anil et al. (2023).
Additionally, we evaluate the performance of various GPT-3.5-based agents,
such as ChatGPT, Self-Edit Zhang et al. (2023), and Reflexion Shinn et al.
(2023). These baselines are chosen to represent a diverse range of approaches,
including single-agent and multi-agent systems, as well as those with and
without self-debugging capabilities.

#### Agent Configuration

To evaluate the effectiveness of the SoA framework, we selected the Reflexion
agent as a baseline. Reflexion iteratively modifies code based on the given
docstrings and automatically generated unit tests until it reaches the maximum
number of iterations or passes the unit tests. The main difference between
Reflexion and SoA is that Reflexion is composed of a single agent, while SoA
is composed of self-organized multiple agents. In the SoA configuration, we
set the maximum number of iterations for the learning loop to 8 and the
maximum tree depth to 2. Additionally, following Shinn et al. (2023), we
provided a few-shot trajectory to the LLM.

#### Data and Tasks

To evaluate the performance of automatic code generation, we used the
HumanEval Chen et al. (2021) benchmark. HumanEval is a set that includes
diverse programming problems designed to measure the functional correctness of
generated code. We used the Python language set for evaluation and followed
the evaluation methodology of Reflexion Shinn et al. (2023). In this process,
multiple test cases are created for each generated code, and $n$ test cases
are randomly selected to construct a test suite. This test suite is used to
verify whether the generated code functions correctly. We set 6 unit tests for
Reflexion and 1 unit test for SoA.

Method | SD | SO | Pass@1
---|---|---|---
AlphaCode Li et al. (2022) | ✘ | ✘ | 17.1
Incoder Fried et al. (2023) | ✘ | ✘ | 15.2
Codex Chen et al. (2021) | ✘ | ✘ | 47.0
Gemini Pro Anil et al. (2023) | ✘ | ✘ | 67.7
GPT-3.5 | CoT Wei et al. (2022) | ✘ | ✘ | 44.6
ChatGPT | ✘ | ✘ | 57.3
Self-Edit Zhang et al. (2023) | ✔ | ✘ | 62.2
Reflexion Shinn et al. (2023) | ✔ | ✘ | 66.5
SoA (ours) | ✔ | ✔ | 71.4
Table 1: Results of SoA and baselines on HumanEval. The score of ChatGPT is
taken from Dong et al. (2023). SD indicates whether the agent uses self-
debugging with unit tests, while SO denotes whether the agent employs self-
organized multi-agent collaboration.

###  § 4.1 Main Results

Table 1 compares the Pass@1 accuracy of the proposed method and the baseline.
Comparing SoA with Reflexion, a strong baseline, SoA outperforms Reflexion by
5% in Pass@1. Considering that each agent in SoA does not see the entire code,
this is a surprising result. This result suggests that self-organized agents
can generate code that functions well as a whole without needing to oversee
the entire code, by independently implementing the functions assigned to them.

###  § 4.2 Analysis

One of the most critical aspects of our study is the efficiency of the self-
organized multi-agent approach in large-scale code generation. To showcase the
superior performance of SoA, we conducted a comprehensive comparative analysis
between Reflexion, a state-of-the-art single-agent system, and our proposed
multi-agent system. Using the HumanEval benchmark, we meticulously examined
the overall scale of the code generated by both systems and the amount of code
each agent independently generated and memorized. To ensure a fair comparison,
we removed comments and docstrings from the HumanEval results and focused on
the number of characters and tokens of pure code.

Figure 5 presents a visualization of the average amount of code generated by
SoA and Reflexion from the perspective of individual functions and all
functions. In the context of HumanEval, which requires the implementation of a
single function, SoA’s code amount is calculated by summing the code generated
by each agent, while Reflexion’s code amount is based on a single function.
The _code amount per function_ in SoA refers to the code generated by each
individual agent, whereas in Reflexion, it is equivalent to the code amount of
a single function. The results unequivocally demonstrate SoA’s superiority
over Reflexion in terms of the number of tokens per final code and the average
number of characters per function. What is remarkable is that despite each
agent in SoA handling significantly fewer tokens/characters compared to the
single agent in Reflexion, the overall output generated by SoA is
substantially greater. This finding underscores the exceptional scalability of
SoA, indicating its ability to handle increasingly complex tasks by seamlessly
adding more agents to the system. Our results suggest that by increasing the
depth of the agent hierarchy and introducing more Mother agents, SoA can
generate even larger-scale code by efficiently distributing the workload among
multiple agents. As the tree structure becomes deeper, the system exhibits an
infinite scaling potential, enabling the generation of increasingly complex
and extensive codebases while ensuring that each agent handles a manageable
portion of the code. Each agent can maintain a manageable amount of code while
theoretically allowing for an indefinite increase in the overall code
generation capacity.

This distributed approach empowers SoA to significantly scale up its ability
to tackle large-scale and complex coding tasks with remarkable efficiency and
high quality, far surpassing the limitations encountered by single-agent
systems like Reflexion, where a sole agent is responsible for managing and
generating the entire codebase.

Figure 5:  Comparison of code generation amount between SoA (mulit-agent) and
Reflexion (single agent).

##  § 5 Related Work

#### LLM Agents

Recent advancements in LLM agents, such as ReAct Yao et al. (2023b), Reflexion
Shinn et al. (2023), Toolformer Schick et al. (2023), and Self-Refine Madaan
et al. (2023), have primarily focused on single-agent approaches, where one
agent is responsible for both generation and modification tasks. Among these,
Reflexion Shinn et al. (2023) has gained significant attention in the field of
code generation due to its outstanding performance. However, despite their
strengths, these single-agent approaches face inherent limitations when it
comes to generating and modifying large-scale codebases. To address these
limitations and push the boundaries of what is possible with LLM agents, we
propose SoA, a novel multi-agent framework that harnesses the power of self-
organization and collaboration. While we intentionally adopted simple agents
for SoA in this work, our framework is flexible enough to incorporate more
sophisticated and powerful methods Zhong et al. (2024); Zhou et al. (2023) and
other state-of-the-art LLMs 555https://claude.ai/, further enhancing its
potential for large-scale code generation and modification.

#### Multi-Agent Collaboration for Software Development

In recent years, several multi-agent-based approaches have emerged as
promising solutions for software development, such as MetaGPT Hong et al.
(2023), ChatDev Qian et al. (2023), Self-collaboration Dong et al. (2023), and
AgentCoder Huang et al. (2023). These methods typically personify agents and
assign them specific names or occupational roles, such as programmers, project
managers, or QA engineers, to allocate tasks. While this approach has shown
promise, our method takes a different and more flexible approach. Instead of
assigning fixed occupational roles, we subdivide agent capabilities based on
_code functionality_ , allowing each agent to demonstrate its expertise
without being constrained by predefined roles. This fine-grained task
allocation enables more flexible problem-solving and adaptation to the
complexity of the software development process. Moreover, by incorporating the
concepts of self-organization and self-proliferation, our agents can
dynamically scale up the overall code volume based on the difficulty of the
problem at hand, providing a highly adaptable and efficient framework for
large-scale code generation and modification.

#### Macro vs. Micro Perspectives

While both multi-agent-based methods Hong et al. (2023); Qian et al. (2023);
Dong et al. (2023); Huang et al. (2023) and our proposed SoA framework share
the common goal of automating software development, they address different
technical aspects of the process. Existing multi-agent methods primarily focus
on optimizing the macro structure of software development, such as project
management and task allocation. In contrast, our method takes a more micro-
level perspective, focusing on the elemental technologies of code generation
and modification. These approaches are not mutually exclusive but rather
complementary, offering a more comprehensive solution to the challenges faced
in automatic software development. By combining the strengths of both macro
and micro-level approaches, we can create a powerful and holistic framework
that efficiently handles the complexities of large-scale code generation and
modification.

#### Prompt Engineering

Tree-of-Thought (ToT) Yao et al. (2023a) and Skeleton of Thought (SoT) Ning et
al. (2023) are prompt engineering techniques that utilize tree-like
structures. ToT represents reasoning steps as nodes to explore correct
reasoning paths, while SoT generates a skeleton of the answer and completes
the contents in parallel to decrease generation latency. In contrast, SoA uses
a tree structure with agents as nodes, focusing on their collaboration and
self-organization to generate and modify code efficiently.

##  § 6 Conclusion

In this work, we introduced Self-organized Agents (SoA), a novel multi-agent
framework for efficient and scalable automatic code generation and
optimization using large language models (LLMs). SoA addresses the limitations
of single-agent approaches in handling large-scale, complex codebases by
leveraging the power of self-organization and distributed code generation. In
SoA, self-organized agents operate independently to generate and modify code
components while seamlessly collaborating to construct the overall codebase. A
key feature of our framework is the automatic multiplication of agents based
on problem complexity, allowing for dynamic scalability and enabling the
overall code volume to be increased indefinitely according to the number of
agents, while the amount of code managed by each agent remains constant.

We evaluated SoA on the HumanEval benchmark and demonstrated its superior
performance compared to Reflexion, a state-of-the-art single-agent system,
with SoA achieving a 5% improvement in terms of Pass@1 accuracy. Furthermore,
our in-depth analysis revealed SoA’s remarkable scalability, as each agent in
SoA handles significantly less code compared to the single-agent baseline, yet
the overall generated code is substantially greater. These results highlight
the effectiveness of SoA in generating and optimizing large-scale code
efficiently and with high quality.

However, it is essential to acknowledge the limitations of the current
implementation of SoA. The framework’s performance may be affected by the
choice of LLM and the quality of the generated unit tests. Additionally, SoA
has been evaluated on a limited set of programming tasks, and its
effectiveness in handling more complex, real-world software development
projects remains to be investigated. Furthermore, the communication and
collaboration mechanisms among agents in SoA can be further optimized to
improve efficiency and fault tolerance.

Despite these limitations, we believe that the SoA framework has significant
potential for future research and development in the field of automatic
software development.

## References

  * Anil et al. (2023) Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M. Dai, Anja Hauth, Katie Millican, David Silver, Slav Petrov, Melvin Johnson, Ioannis Antonoglou, Julian Schrittwieser, Amelia Glaese, Jilin Chen, Emily Pitler, Timothy P. Lillicrap, Angeliki Lazaridou, Orhan Firat, James Molloy, Michael Isard, Paul Ronald Barham, Tom Hennigan, Benjamin Lee, Fabio Viola, Malcolm Reynolds, Yuanzhong Xu, Ryan Doherty, Eli Collins, Clemens Meyer, Eliza Rutherford, Erica Moreira, Kareem Ayoub, Megha Goel, George Tucker, Enrique Piqueras, Maxim Krikun, Iain Barr, Nikolay Savinov, Ivo Danihelka, Becca Roelofs, Anaïs White, Anders Andreassen, Tamara von Glehn, Lakshman Yagati, Mehran Kazemi, Lucas Gonzalez, Misha Khalman, Jakub Sygnowski, and et al. 2023.  Gemini: A family of highly capable multimodal models.  _CoRR_ , abs/2312.11805.
  * Ashby (1947) W Ross Ashby. 1947.  Principles of the self-organizing dynamic system.  _The Journal of general psychology_ , 37(2):125–128.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harrison Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. 2021.  Evaluating large language models trained on code.  _CoRR_ , abs/2107.03374.
  * Dong et al. (2023) Yihong Dong, Xue Jiang, Zhi Jin, and Ge Li. 2023.  Self-collaboration code generation via chatgpt.  _CoRR_ , abs/2304.07590.
  * Fried et al. (2023) Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Scott Yih, Luke Zettlemoyer, and Mike Lewis. 2023.  Incoder: A generative model for code infilling and synthesis.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net.
  * Hong et al. (2023) Sirui Hong, Xiawu Zheng, Jonathan Chen, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, and Chenglin Wu. 2023.  Metagpt: Meta programming for multi-agent collaborative framework.  _CoRR_ , abs/2308.00352.
  * Huang et al. (2023) Dong Huang, Qingwen Bu, Jie M. Zhang, Michael Luck, and Heming Cui. 2023.  Agentcoder: Multi-agent-based code generation with iterative testing and optimisation.  _CoRR_ , abs/2312.13010.
  * Levy et al. (2024) Mosh Levy, Alon Jacoby, and Yoav Goldberg. 2024.  Same task, more tokens: the impact of input length on the reasoning performance of large language models.  _CoRR_ , abs/2402.14848.
  * Li et al. (2023a) Jiaqi Li, Mengmeng Wang, Zilong Zheng, and Muhan Zhang. 2023a.  Loogle: Can long-context language models understand long contexts? _CoRR_ , abs/2311.04939.
  * Li et al. (2023b) Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgenii Zheltonozhskii, Terry Yue Zhuo, Thomas Wang, Olivier Dehaene, Mishig Davaadorj, Joel Lamy-Poirier, João Monteiro, Oleh Shliazhko, Nicolas Gontier, Nicholas Meade, Armel Zebaze, Ming-Ho Yee, Logesh Kumar Umapathi, Jian Zhu, Benjamin Lipkin, Muhtasham Oblokulov, Zhiruo Wang, Rudra Murthy V, Jason Stillerman, Siva Sankalp Patel, Dmitry Abulkhanov, Marco Zocca, Manan Dey, Zhihan Zhang, Nour Moustafa-Fahmy, Urvashi Bhattacharyya, Wenhao Yu, Swayam Singh, Sasha Luccioni, Paulo Villegas, Maxim Kunakov, Fedor Zhdanov, Manuel Romero, Tony Lee, Nadav Timor, Jennifer Ding, Claire Schlesinger, Hailey Schoelkopf, Jan Ebert, Tri Dao, Mayank Mishra, Alex Gu, Jennifer Robinson, Carolyn Jane Anderson, Brendan Dolan-Gavitt, Danish Contractor, Siva Reddy, Daniel Fried, Dzmitry Bahdanau, Yacine Jernite, Carlos Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. 2023b.  Starcoder: may the source be with you! _CoRR_ , abs/2305.06161.
  * Li et al. (2022) Yujia Li, David H. Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. 2022.  Competition-level code generation with alphacode.  _CoRR_ , abs/2203.07814.
  * Madaan et al. (2023) Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. 2023.  Self-refine: Iterative refinement with self-feedback.  In _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023_.
  * Muennighoff et al. (2023) Niklas Muennighoff, Qian Liu, Armel Zebaze, Qinkai Zheng, Binyuan Hui, Terry Yue Zhuo, Swayam Singh, Xiangru Tang, Leandro von Werra, and Shayne Longpre. 2023.  Octopack: Instruction tuning code large language models.  _CoRR_ , abs/2308.07124.
  * Ning et al. (2023) Xuefei Ning, Zinan Lin, Zixuan Zhou, Huazhong Yang, and Yu Wang. 2023.  Skeleton-of-thought: Large language models can do parallel decoding.  _CoRR_ , abs/2307.15337.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 technical report.  _CoRR_ , abs/2303.08774.
  * Qian et al. (2023) Chen Qian, Xin Cong, Cheng Yang, Weize Chen, Yusheng Su, Juyuan Xu, Zhiyuan Liu, and Maosong Sun. 2023.  Communicative agents for software development.  _CoRR_ , abs/2307.07924.
  * Schick et al. (2023) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023.  Toolformer: Language models can teach themselves to use tools.  In _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023_.
  * Shaham et al. (2023) Uri Shaham, Maor Ivgi, Avia Efrat, Jonathan Berant, and Omer Levy. 2023.  Zeroscrolls: A zero-shot benchmark for long text understanding.  In _Findings of the Association for Computational Linguistics: EMNLP 2023, Singapore, December 6-10, 2023_ , pages 7977–7989. Association for Computational Linguistics.
  * Shinn et al. (2023) Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023.  Reflexion: language agents with verbal reinforcement learning.  In _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023_.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton-Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023.  Llama 2: Open foundation and fine-tuned chat models.  _CoRR_ , abs/2307.09288.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_.
  * Yao et al. (2023a) Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2023a.  Tree of thoughts: Deliberate problem solving with large language models.  In _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023_.
  * Yao et al. (2023b) Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R. Narasimhan, and Yuan Cao. 2023b.  React: Synergizing reasoning and acting in language models.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net.
  * Zhang et al. (2023) Kechi Zhang, Zhuo Li, Jia Li, Ge Li, and Zhi Jin. 2023.  Self-edit: Fault-aware code editor for code generation.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2023, Toronto, Canada, July 9-14, 2023_ , pages 769–787. Association for Computational Linguistics.
  * Zhong et al. (2024) Lily Zhong, Zilong Wang, and Jingbo Shang. 2024.  LDB: A large language model debugger via verifying runtime execution step-by-step.  _CoRR_ , abs/2402.16906.
  * Zhou et al. (2023) Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. 2023.  Language agent tree search unifies reasoning acting and planning in language models.  _CoRR_ , abs/2310.04406.

##  Appendix A Pseudocode

Algorithm 1 Generate Code with Self-organized Agent Framework

1:$docstrings$: Docstrings for the function, $unit\\_tests$: List of unit
tests, $max\\_depth$: Maximum depth of the agent hierarchy,
$max\\_iterations$: Maximum number of code modification iterations

2:The final generated code

3:

4:Initialize the root Mother agent with $docstrings$ and $unit\\_tests$

5:

6:function GenerateAgent($agent$, $depth$, $subtask\\_docstrings$,
$subtask\\_unit\\_tests$)

7: if $depth-1$ = $max\\_depth$ then

8: $next\\_agent\leftarrow$ new ChildAgent

9: else

10: $next\\_agent\leftarrow$ new MotherAgent

11: end if

12: Assign $subtask\\_docstrings$ and $unit\\_tests$ to $next\\_agent$

13: Generate($next\\_agent$, $depth+1$)

14:end function

15:

16:function Generate($agent$, $depth$)

17: if $depth$ = 1 then $\triangleright$ Root Mother

18: $skeleton\leftarrow$ Generate skeleton from $agent.docstrings$ and
$agent.unit_{t}ests$

19: $agent.code\leftarrow skeleton$

20: for each $subtask\\_docstrings$, $subtask\\_unit\\_tests$ in subtasks do

21: GenerateAgent($agent$, $depth$, $subtask\\_docstrings$,
$subtask\\_unit\\_tests$)

22: end for

23: else if $depth$ = $max\\_depth$ then $\triangleright$ Child

24: Generate code for $agent.subtask\\_docstrings$ and
$agent.subtask\\_unit\\_tests$

25: $agent.code\leftarrow$ generated code

26: else$\triangleright$ Mother

27: Generate code for $agent.subtask\\_docstrings$ and
$agent.subtask\\_unit\\_tests$

28: $agent.code\leftarrow$ generated code

29: for each $subtask\\_docstrings$, $subtask\\_unit\\_tests$ in subtasks do

30: GenerateAgent($agent$, $depth$, $subtask\\_docstrings$,
$subtask\\_unit\\_tests$)

31: end for

32: end if

33:end function

34:

35:function Modify($agent$, $test\\_result$, $upper\\_agent\\_observation$)

36: Generate feedback for $agent$ based on $test\\_result$ and
$upper\\_agent\\_observation$

37: Update $agent$’s code based on feedback

38: for each $subagent$ in $agent.subagents$ do

39: Evaluate $subagent.code$ using $subagent.unit\\_tests$ to get
$subagent\\_test\\_result$

40: Modify($subagent$, $subagent\\_test\\_result$, feedback and code changes)

41: end for

42:end function

43:

44:Start code generation with Generate($root\\_mother$, 1)

45:

46:for each iteration in $max\\_iterations$ do

47: Combine implementations from all agents to create $final\\_implementation$

48: Evaluate $final\\_implementation$ using $unit\\_tests$ to get
$test\\_result$

49: Modify the code starting from $root\\_mother$ with Modify($root\\_mother$,
$test\\_result$, None)

50:end for

51:

52:return The final implementation combined from all agents