Paper deep dive
Absorbing State Phase Transitions in Multi-Agent Search
Wenwen Zheng, Yuzhe Yang, Helen Qu, Xin Eric Wang, Haewon Jeong
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 10/1/2026, 7:05:14 AM
Summary
This paper investigates multi-agent search dynamics using the formalism of absorbing state phase transitions. The authors taxonomize search tasks into four types (needle, chain, hierarchical, and factorizable) and theoretically derive a critical communication degree ($d_c$) required for search success. Empirical evaluations on LLM-based agents in factorizable search tasks (toy example, TCAS debugging, physical mechanism discovery) reveal mixed agreement with theory, as LLMs often fail to communicate effectively or engage in individual strategizing that hinders collaboration.
Entities (12)
Relation Signals (8)
Absorbing State Phase Transitions → usedtomodel → Multi-Agent Search
confidence 95% · In this paper, we focus on predicting the success of multi-agent search tasks using the formalism of absorbing state phase transitions.
Factorizable Search → hascriticaldegree → d_c
confidence 93% · We theoretically derive d_c for all four search task classes... d_c exists for tree and factorizable search
Chain Search → hascriticaldegree → infinity
confidence 90% · d_c^chain(C,T) = infinity, T<C.
Needle Search → hascriticaldegree → 0%
confidence 90% · We denote this absence of a positive threshold by d_c^needle=0.
TCAS → isexampleof → Factorizable Search
confidence 90% · We run empirical experiments on three factorizable search problems... Configuration fault localization (TCAS).
LLM Agents → exhibitsbehavior → Individual Strategizing
confidence 88% · LLM agents may not communicate with their neighbors and can develop strategies that are individually beneficial but limits the benefits of collaboration.
LLM Agents → exhibitsbehavior → Herding Behavior
confidence 85% · current LLMs exhibit behaviors under which theoretical assumptions break down, such as... herding behavior amongst agents
Qwen3.5-4b → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Nontrivial dynamics can emerge in large language model (LLM)-based multi-agent systems, and preliminary evidence exists that formalisms from statistical mechanics can be effective at modeling and predicting such behaviors. In parallel, designing multi-agent communication topology for optimal task-solving is an active research question. In this paper, we focus on predicting the success of multi-agent search tasks using the formalism of absorbing state phase transitions. We first taxonomize search tasks into four types, informed by classical results in combinatorial search. We then theoretically derive a critical communication degree $d_c$, the minimum number of agents each agent can communicate with, above which incorrect hypotheses do not proliferate uncontrollably and the search enters the solved state. Finally, we evaluate frontier LLM-based multi-agent systems on real-world search and discovery tasks, software configuration debugging and physical mechanism discovery, and find that agreement with theory is mixed. LLM agents may not communicate with their neighbors and can develop strategies that are individually beneficial but limits the benefits of collaboration.
Tags
Links
- Source: https://arxiv.org/abs/2609.38327v1
- Canonical: https://arxiv.org/abs/2609.38327v1
Trouble viewing inline? Open PDF directly →
Full Text
73,215 characters extracted from source content.
Expand or collapse full text
Absorbing State Phase Transitions in Multi-Agent Search Wenwen Zheng †thanks: Equal contribution. Affiliation: University of California, Santa Barbara Email: wenwenzheng@ucsb.edu Yuzhe Yang11footnotemark: 1 Affiliation: University of California, Santa Barbara Email: yuzheyang@ucsb.edu Helen Qu11footnotemark: 1 Affiliation: Flatiron Institute Email: hqu@flatironinstitute.org Xin Eric Wang Affiliation: University of California, Santa Barbara Email: ericxwang@ucsb.edu Haewon Jeong Affiliation: University of California, Santa Barbara Affiliation: Flatiron Institute Email: haewon@ucsb.edu Abstract Nontrivial dynamics can emerge in large language model (LLM)-based multi-agent systems, and preliminary evidence exists that formalisms from statistical mechanics can be effective at modeling and predicting such behaviors. In parallel, designing multi-agent communication topology for optimal task-solving is an active research question. In this paper, we focus on predicting the success of multi-agent search tasks using the formalism of absorbing state phase transitions. We first taxonomize search tasks into four types, informed by classical results in combinatorial search. We then theoretically derive a critical communication degree dcd_c, the minimum number of agents each agent can communicate with, above which incorrect hypotheses do not proliferate uncontrollably and the search enters the solved state. Finally, we evaluate frontier LLM-based multi-agent systems on real-world search and discovery tasks, software configuration debugging and physical mechanism discovery, and find that agreement with theory is mixed. LLM agents may not communicate with their neighbors and can develop strategies that are individually beneficial but limits the benefits of collaboration. 1 Introduction AI agents are increasingly being deployed in multi-agent systems, in which agents communicate, interact, and cooperate to complete tasks. Multi-agent systems have been shown to improve over single agents across a variety of domains and task types (Wu et al., 2023; Guo et al., 2024; Hong et al., 2024; Qian et al., 2024; Du et al., 2024; Kim et al., 2024; Agashe et al., 2025). However, comparatively little is known about their collective dynamics, such as emergent or nonlinear behavior; and effective modeling of these phenomena could improve the system’s capability and safety. While recent work suggests that formalisms like the Ising model from statistical mechanics (Ising, 1925, e.g.) can be effective at modeling nonlinear multi-agent system dynamics (El et al., 2026; Niu et al., 2026; Xie et al., 2026), these works have focused only on consensus formation and error propagation. Beyond opinion dynamics, search problems provide another important setting for understanding collective behavior in multi-agent systems. In his famous Bitter Lesson post, Sutton wrote that “Search and learning are the two most important classes of techniques for utilizing massive amounts of computation in AI research" (Sutton, 2019). Many tasks, from program synthesis (Gulwani et al., 2017) to scientific discovery (Morales et al., 2026), involve exploring a space of candidate solutions through successive refinement and verification. In cooperative search, agents can explore different regions simultaneously and share findings that guide one another’s exploration. Understanding these dynamics could help predict when collaboration accelerates discovery and when it leads to redundant effort or the propagation of unproductive search directions. A crucial question in the design of multi-agent systems is inter-agent communication topology design (Zhang et al., 2024; Zhu et al., 2025; Kim et al., 2025). A fully dense communication graph may seem like a clear choice, but this is often prohibitively computationally expensive and can underperform sparser topologies (Li et al., 2024). Recent work has also shown that the optimal topology depends on the type of task the agents are asked to solve (Rizvi-Martel et al., 2025; Kim et al., 2025; Tang et al., 2025; Qian et al., 2025; Yang et al., 2025). Inter-agent communication should be most beneficial to solving search problems when evidence produced by one agent can affect the search space of others; however, there is little work demonstrating the effect of different inter-agent communication regimes on different search task types. In this paper, we investigate multi-agent search dynamics through absorbing state phase transition theory, where search success guarantee is the absorbing state. We introduce a taxonomy for search problems informed by classical results in parallel search and constraint satisfaction (Dechter, 1986; Lai and Sahni, 1984; Dechter and Mateescu, 2007), distinguishing four task types: needle, chain, hierarchical, and factorizable search (Section 2.3). We derive theoretical values for the critical communication degree dcd_c for each of these task types (Section 3), finding that factorizable search benefits the most from inter-agent communication due to the potential for information reuse across disparate parts of the search graph. Finally, we evaluate on three factorizable search tasks using deterministic agents as well as LLM-based agents (Section 4). We find that deterministic, rule-based agent behaviors agree with theory, but current LLMs exhibit behaviors under which theoretical assumptions break down, such as individual strategizing to choose the best candidates, herding behavior amongst agents, and failure to communicate with their neighbors (Section 5). 2 Setup 1 Select2 Verify3 Receive4 Pruneℓ1,1 _1,1candidate with asingle hypothesisℓ1,1≡(q1=1) _1,1≡(q_1=1)branchb=3b=3ℓ1,1 _1,1ℓ2,1 _2,1ℓ2,2 _2,2ℓ2,3 _2,3ℓ1,1 _1,1ℓ2,1 _2,1×ℓ2,2 _2,2✓ ℓ2,3 _2,3ℓ1,1 _1,1ℓ2,1 _2,1×ℓ2,2 _2,2✓ ℓ2,3 _2,3× m=2m=2incorrect active: 2incorrect active: 2incorrect active: 0from d neighbors:ℓ1,1,ℓ2,3\ _1,1, _2,3\ × Figure 1: Schematic of our multi-agent search setup. Agents begin with candidates each containing a single hypothesis, or literal ℓ (in this example, the literal asserts the answer to question q1q_1 is 1). This candidate branches into b new candidates that add each a new hypothesis. In one search round, an agent (1) selects m of its active candidates to be verified; (2) runs the verification mechanism on the selected candidates to test whether they are consistent with the search target; (3) receives information about verification results from neighboring agents; and (4) the agent prunes incorrect candidates based on all available evidence. The next round begins by branching b new candidates from every surviving candidate of the current round. 2.1 Problem Setup: Search Tasks We consider multi-agent systems applied to solving search tasks. We formalize search tasks as a graph (,ℰ)G(C,E) consisting of nodes C, representing the set of search candidates, and a set of directed edges ℰE indicating dependency between candidates. We assume the graph has branching factor b. There is a single correct answer c⋆c , the target of the search. We assume there exists a verification mechanism (e.g., empirical experiments in a scientific discovery context, or code execution in a debugging context) that returns a binary signal indicating whether the candidate c is consistent with the target c⊆c⋆c c . The search concludes successfully if c⋆c is found and verified. A candidate c is a set of literals ℓi,v _i,v, where each literal expresses a single assertion about the target. Let q1,…,qMq_1,…,q_M denote the questions defining a task, with V1,…,VMV_1,…,V_M denoting their possible answer sets; when these have uniform size, we write |Vi|=K|V_i|=K. Then we an define a literal as ℓi,v≡(qi=v),ℒ=ℓi,v:i∈1,…,M,v∈Vi. _i,v≡(q_i=v), =\ _i,v:i∈\1,…,M\,\ v∈ V_i\. The first index identifies the question, while the second represents the proposed answer. Each candidate branches into b child candidates by adding an additional literal, e.g., a candidate c0=ℓ0,αc_0=\ _0,α\ can branch into c1=ℓ0,α,ℓ1,αc_1=\ _0,α, _1,α\ and c2=ℓ0,α,ℓ1,βc_2=\ _0,α, _1,β\ assuming α,β∈V1α,β∈ V_1 and b=2b=2. We assume a system of N agents. Agents traverse the graph in T rounds, indexed by t=1,2,…,Tt=\1,2,...,T\, where each round consists of performing verification of at most m leaf candidates (i.e., candidates located at level t) and pruning candidates that fail verification. Agent aia_i can communicate their verification results with any neighboring agent aja_j, and aja_j can use these results to prune candidates that aia_i has verified (see Section 3.2). We parameterize agent communication topology simply with a single communication degree parameter d, representing the number of other agents each can communicate with. A schematic of a round is illustrated in Figure 1. 2.2 Modeling Search Success: Absorbing State Phase Transitions An absorbing-state phase transition occurs when changing a system parameter determines whether activity persists or eventually stops permanently (enters the absorbing state). They are typically characterized by a sharp, nonlinear transition from activity to absorbing state at a critical value of the system parameter. In our setting, we measure the search activity as a function of communication degree d, and the absorbing state corresponds to a “solved search”. We define this state by parameterizing search activity as the number of active incorrect search candidates AtA_t, summed over all agents. The absorbing state is reached when AtA_t decays toward zero: eventually the correct candidate will be all that’s left, and verification of c⋆c is guaranteed within the round budget T. We wish to derive the critical communication degree dcd_c: for d<dcd<d_c the incorrect-candidate population grows over the search horizon, whereas for d>dcd>d_c it contracts; sufficiently strong accumulated decay of wrong hypothesis drives the system toward the solved absorbing state. 2.3 Search Task Taxonomy Communication helps search when evidence produced by one agent can remove incorrect hypotheses that others are exploring. We argue that only certain types of search tasks have the property of evidence reusability, leading us to introduce a taxonomy for search tasks (Figure 2) inspired by parallel search, AND/OR search regimes, and branch-and-bound algorithms (Karp and Zhang, 1993; Dechter and Mateescu, 2007; Lai and Sahni, 1984). literal pool ℒLℓ1,1 _1,1ℓ1,2 _1,2ℓ1,3 _1,3ℓ1,4 _1,4ℓ1,5 _1,5 c⋆c refuting ℓ1,3 _1,3 rules outone answer and nothing else (a) Needle. All candidates have only one literal, so branching is impossible. ∅ ℓ1,1 _1,1ℓ1,1ℓ2,1 _1,1 _2,1ℓ1,1ℓ2,1ℓ3,1 _1,1 _2,1 _3,1q1q_1q2q_2q3q_3c⋆c qi+1q_i+1 is available only once qiq_i is answered,and one answer is admissible at each step (b) Chain. The questions are forced into a single order, so there is one sequence of candidates. ∅ ℓ1,1 _1,1ℓ1,2 _1,2ℓ1,3 _1,3ℓ1,1ℓ2,1 _1,1 _2,1ℓ1,1ℓ2,2 _1,1 _2,2ℓ1,2ℓ3,1 _1,2 _3,1ℓ1,2ℓ3,2 _1,2 _3,2ℓ1,3ℓ4,1 _1,3 _4,1ℓ1,3ℓ4,2 _1,3 _4,2then asks q2q_2then asks q3q_3then asks q4q_4q1q_1c⋆c refuting ℓ1,3 _1,3 kills one subtree (c) Tree / hierarchical. The next question depends on the previous answer, so e.g., q4q_4 is asked only under ℓ1,3 _1,3. ∅ ℓ1,1 _1,1ℓ2,1 _2,1ℓ3,1 _3,1ℓ4,1 _4,1ℓ1,1ℓ2,1 _1,1 _2,1ℓ1,1ℓ3,1 _1,1 _3,1ℓ1,1ℓ4,1 _1,1 _4,1ℓ2,1ℓ3,1 _2,1 _3,1ℓ2,1ℓ4,1 _2,1 _4,1ℓ3,1ℓ4,1 _3,1 _4,1any question, in any orderc⋆c refuting ℓ3,1 _3,1 kills every candidate holding it (d) Factorizable. Literals can combine in any order, leading to increasing overlap as the graph grows. Figure 2: Our search task taxonomy. Orange marks the target c⋆c , and red dashes mark what refuting a single literal can remove. The classes differ in how literals can be combined, and that difference determines evidence reusability and branching behavior. Needle and chain search (Figure 2(a), 2(b)) are characterized by a branching factor b=1b=1: the population of incorrect candidates cannot grow. Needle search is purely an OR search space in which candidates cannot be further decomposed, so there is no branching behavior, and refuting a candidate has no effect on other candidates. For example, a wrong guess for an unknown password provides no information about untested guesses. In chain search, each of C experiments must be done in sequence, e.g., following an unknown sequence of pointers when each query reveals the next. Needle search is coverage-limited, so scaling agents helps but communication won’t; while chain search is depth-limited, so parallelism cannot help at all. Hierarchical and factorizable search (Figures 2(c), 2(d)) introduce branching, but differ in the scope of reusable evidence. In our coarse-to-fine hierarchical model, which represents tasks such as localizing a faulty component or buggy commit, candidates are specific to their parents, so an incorrect candidate can only prune its corresponding subtree. In our factorizable model, on the other hand, literals recur across paths, so refuting one literal can eliminate candidates in other parts of the graph. Unlike distributing a fixed computation across agents, communicating verification results between agents can reduce the total work required by subsequent search. Parallel branch-and-bound provides a classical example: an improved solution discovered by one worker supplies a bound that allows others to prune unexplored subtrees, potentially producing superlinear speedup relative to a sequential search (Lai and Sahni, 1984). Section 3.2 models this interaction between candidate proliferation and evidence-driven pruning. 3 Theoretical Results We theoretically derive dcd_c for all four search task classes. We show that needle and chain search tasks will never reach a phase transition in communication degree (Section 3.1), whereas dcd_c exists for tree and factorizable search (Section 3.2). 3.1 Search without phase transitions 3.1.1 Needle search Needle or unstructured search (Figure 2(a)) is characterized by unrelated candidates: excluding one candidate provides no information about any others, and there is no persistent production of new incorrect candidates. Communication can reduce redundant verification, but there is no branching–pruning balance and hence no nontrivial critical degree. We denote this absence of a positive threshold by dcneedle=0.d_c^needle=0. (1) 3.1.2 Chain search Chain or sequential search (Figure 2(b)) requires C experiments in sequence, where candidate j+1j+1 becomes available only after verification of candidate j is complete. Under the assumption that only one sequential experiment can be completed per round, communication cannot shorten this dependency chain. Thus, dcchain(C,T)=0,T≥C,∞,T<C.d_c^chain(C,T)= cases0,&T≥ C,\\ ∞,&T<C. cases (2) 3.2 Search with phase transitions Hierarchical and factorizable tasks share a balance between branching and verification. Let AtA_t denote the expected total number of active incorrect candidates across all N agents, counting copies separately. With branching factor b, normalized budget parameter m (corresponding to a total round budget NmNm), and communication degree d, the mean-field dynamics are At+1≃rt(d)(At−mN),rt(d)=b(1−mqt)d,A_t+1 r_t(d)(A_t-mN), r_t(d)=b(1-mq_t)^d, (3) where qtq_t is the probability that a single communicated verification result eliminates a given incorrect candidate at a receiving agent. This approximation assumes that the full system-wide budget NmNm is used each round and allocated among eligible agents, and that experiments are selected randomly and independently. For At≫mNA_t mN, self-pruning is subleading, giving AT≃A1e(T−1)λ¯T(d)A_T A_1e^(T-1) λ_T(d), where λ¯T(d)≡(T−1)−1∑t=1T−1lnrt(d). λ_T(d)≡(T-1)^-1 _t=1^T-1 r_t(d). (4) The finite-horizon critical degree, defined by λ¯T(dc)=0 λ_T(d_c)=0, is therefore dc=−(T−1)lnb∑t=1T−1ln(1−mqt)≃(T−1)lnbm∑t=1T−1qt,d_c=- (T-1) bΣ _t=1^T-1 (1-mq_t) (T-1) bmΣ _t=1^T-1q_t, (5) where the approximation holds for mqt≪1mq_t 1 at every round. Below dcd_c, incorrect candidates proliferate (AT>A1A_T>A_1); above dcd_c, they decay (AT<A1A_T<A_1). Under the additional idealization of uniform final selection from these incorrect candidates and one retained correct candidate, Psucc(d)≃11+AT(d)≃11+A1e(T−1)λ¯T(d).P_succ(d) 11+A_T(d) 11+A_1e^(T-1) λ_T(d). (6) Success is below 1/(1+A1)1/(1+A_1) for d<dcd<d_c and above it for d>dcd>d_c. The limits Psucc→0P_succ→ 0 and Psucc→1P_succ→ 1 follow when the accumulated log reproduction (T−1)λ¯T(d)(T-1) λ_T(d) tends to +∞+∞ and −∞-∞, respectively; finite horizons give a smooth crossover. 3.2.1 Hierarchical search In hierarchical coarse-to-fine search, evidence transfers only between candidates sharing the refuted path. Under uniform, independent selection among btb^t depth-t paths, qt=b−t,dc≃(T−1)(b−1)lnbm[1−b−(T−1)].q_t=b^-t, d_c (T-1)(b-1) bm [1-b^-(T-1) ]. (7) Here and below, we use the weak-pruning approximation ln(1−mqt)≃−mqt (1-mq_t) -mq_t, valid when mqt≪1mq_t 1 at every round. For hierarchical search, this requires m/b≪1m/b 1. Cumulative overlap ∑t=1T−1b−t _t=1^T-1b^-t saturates at 1/(b−1)1/(b-1), while branching continues each round. As search deepens, agents spread across increasingly many branches, and their evidence becomes less mutually relevant. Consequently, dc∝Td_c T at large T: deeper search requires more communication, but dcd_c cannot exceed N−1N-1. 3.2.2 Factorizable search In factorizable search, a depth-t candidate contains t literals from a pool ℒL. Refuting a literal eliminates every candidate containing it, regardless of its refinement path. Since a depth-t candidate contains t literals from a pool ℒL, a uniformly sampled literal overlaps with it with probability t/|ℒ|t/|L|. qt≃t|ℒ|,∑t=1T−1qt≃T(T−1)2|ℒ|,dc≃2|ℒ|lnbmT.q_t t|L|, _t=1^T-1q_t T(T-1)2|L|, d_c 2|L| bmT. (8) Unlike hierarchical search, cumulative overlap grows quadratically with T while branching grows only linearly. Thus, dc∝T−1d_c T^-1: deeper candidates contain more components and thus offer more opportunities for pruning through reusable component-level evidence. 4 Experiments We run empirical experiments on three factorizable search problems evaluate the applicability of our theoretically predicted critical communication degree dcd_c to LLM agents. 4.1 Tasks Simple toy example. Agents search for a hidden configuration of T literals, each taking one of K values. A candidate is a partial configuration, and branching occurs by adding an additional literal (see Figure 2(d)), meaning that a candidate at depth t in the graph will have t literals. A candidate passes verification if it is a subset of the target configuration. The task is solved when a candidate is verified to exactly match the hidden configuration. Configuration fault localization (TCAS). We test on a module of the Traffic Collision Avoidance System (TCAS) benchmark (Hutchins et al., 1994; Do et al., 2005; Kuhn and Okun, 2006), which takes M=12M=12 multi-valued inputs encoding aircraft altitude and separation data, to determine whether to issue an upward, downward, or no resolution advisory. Similar to the toy example, branching occurs through adding a literal, and the task is solved when a specific hidden configuration is discovered. Physical mechanism discovery. We test on symbolic discovery of a dynamical law z˙=f⋆(z,t) z=f (z,t), abstracting the interactive discovery setting of ODEBench (d’Ascoli et al., 2024) and NewtonBench (Zheng et al., 2026). We constructed a simple dynamical-system discovery environment with a fixed library of 16 symbolic force terms || (e.g., x, x3x^3, sinx x, x˙ x, cos(ωt) (ω t)), from which four are sampled to define each hidden equation, and agents work off of the resulting physical trajectories. Following SINDy-style support recovery (Brunton et al., 2016), the search target is the sparse subset S⋆⊆||S of active terms. Verification is testing for membership of a single term in S⋆S , and the task is solved when S⋆S is discovered and verified. 4.2 Experimental Procedure Models. We evaluate deterministic non-LLM agents alongside agents based on four LLMs spanning open-weight and closed-source models: Qwen3.5-4B, Qwen3.5-9B, GPT-5.4 nano, and GPT-6 luna. All models were evaluated with sampling temperature 1. For GPT-6 luna, we additionally compare five reasoning-effort settings: none, low, medium, high, and xhigh. Multi-agent search procedure. We use the same search protocol for synthetic, TCAS, and physics-discovery tasks. Deterministic agent experiments are purely rule-based: a total round budget of NmNm candidate verifications is allocated across agents with eligible candidates each round. Inter-agent communication of verification results and pruning of incorrect branches occur automatically. We relax some of these assumptions in our LLM experiments. Agents decide which experiments to perform and how/what to prune within the same total round budget NmNm. To probe the role of 1) cooperation-focused prompting, and 2) free vs. automatic communication of verification results, we consider three policies outlined in Table 1. Experimental configurations. All benchmarks use N=40N=40 agents, branching factor b=2b=2, per-agent verification budget m=1m=1, and each agent starts with n0=8n_0=8 candidates. The task-specific search spaces have |ℒ||L| valid literals and target depth T: (|ℒ|,T)=(16,4)(|L|,T)=(16,4) for the toy task, (46,6)(46,6) for TCAS, and (16,4)(16,4) for physical mechanism discovery. For the toy task, the 16 literals arise from M=8M=8 components with K=2K=2. For TCAS, the 12 parameters have heterogeneous value cardinalities, with Kmax=10K_ =10 and 46 valid literals in total. For mechanism discovery, we use M=16M=16 candidate equation components with each literal defined as a binary inclusion choice. Table 1: LLM communication policies tested. Policy Prompted objective Communication rule Team-Auto Team performance Automatically transmit the true verdict of every experiment to d neighbors (same as for deterministic agents). Team-Free Team performance The agent chooses which of d neighbors to communicate with, what to report (deception is allowed), plus optional text. Indiv-Free Individual performance Same as C1. Evaluation. Within each benchmark, all policies use the same set of communication degree d∈0,8,16,24,39d∈\0,8,16,24,39\ and six task seeds. We estimate the cumulative incorrect-lineage reproduction factor by pooling counts across agents and tasks: λ(d)=∑t=1T−1log(∑eCt(e)(d)∑eAt−1(e)(d)).λ(d)= _t=1^T-1 ( _eC_t^(e)(d) _eA_t-1^(e)(d) ). (9) Here e indexes tasks, At−1(e)A_t-1^(e) counts incorrect hypotheses at the start of round t, and Ct(e)C_t^(e) counts their children, deduplicated within each agent, after pruning and branching. Children descended only from correct parents are excluded from the numerator. We estimate dcd_c from the per-round average λ¯(dc)=0 λ(d_c)=0 by linearly interpolating λ¯(d) λ(d) between consecutive sampled degrees. 5 Results and Discussion 5.1 Deterministic Models Agree With Theory To ensure that our theory models real-world factorizable search problems, we evaluate deterministic multi-agent systems on our 3 factorizable search tasks. We find very good agreement between theoretically predicted critical communication degree dcd_c and measured dcd_c from our experiments across all tasks (Figure 3). Measured dcd_c tracks theory closely in all three environments (Lin’s C = 0.93, 0.97 and 0.94 for the toy example, TCAS, and mechanism discovery; respectively). The mechanism discovery task shows the most disagreement, where measured dcd_c exceeds theory by an average of 17%. We note that in this task, literals are binary since each candidate mechanism is either present or absent. The literals in the TCAS task, on the other hand, take one of several mutually exclusive values; and we tested the toy task in both binary and multi-valued settings. Settings with binary literals consistently produce higher dcd_c than predicted by theory. Figure 3: Deterministic agents recover theoretical dcd_c prediction across all tasks. Filled points represent task configurations with multi-valued literals (|Vi|>2|V_i|>2), such as in the TCAS task. Open points represent |Vi|=2|V_i|=2, such as in the physical mechanism discovery task where each symbolic term either is or is not in the true equation. 5.2 Experiments on LLM Agents Comparison with theoretical prediction. Through these experiments, we wished to understand whether capable LLMs can discover strategies that are better than the theoretical setup, such as cooperation or intelligent candidate selection, and thus achieve a dcd_c lower than theory. While the best agent-policy combinations approach theoretical prediction, we do not observe a statistically clear improvement over theory in any tested case. We find that agents tend to add literals that have already been validated, leaving previously introduced incorrect components untested, and overlapping experimental choices further produce redundant evidence. Table 2: Empirical critical communication degrees d^c d_c for four LLM families. Estimates are obtained from pooled incorrect-lineage reproduction counts over six task seeds; error bars denote 95% task-level bootstrap confidence intervals. Lowest dc d_c values are bolded, and the theoretical prediction for dcd_c for each task is shown below each task name for comparison. Synthetic TCAS Physics dctheory=6.10d_c^theory=6.10 dctheory=10.90d_c^theory=10.90 dctheory=6.10d_c^theory=6.10 Model Team- Auto Team- Free Indiv- Free Team- Auto Team- Free Indiv- Free Team- Auto Team- Free Indiv- Free Qwen3.5-4B 6.55 6.2–6.9 12.82 12.2–13.4 13.47 11.6–16.0 12.79 11.4–13.7 17.69 16.5–25.1 20.13 16.8–24.8 8.77 7.7–10.0 13.94 12.2–14.6 14.31 11.5–16.9 Qwen3.5-9B 6.64 6.2–7.0 16.01 13.8–17.4 16.06 14.1–18.2 12.90 10.9–15.2 29.15 23.6–37.3 27.31 24.8–29.6 8.34 7.7–8.8 17.07 15.0–18.9 16.77 14.2–18.5 GPT-5.4 Nano 6.39 5.8–7.1 7.87 7.0–9.0 7.29 6.8–7.8 10.52 8.7–11.6 12.88 9.8–14.5 14.41 9.7–16.1 10.95 9.8–12.0 13.04 11.3–16.7 12.79 11.8–13.4 GPT-6 Luna 6.88 6.4–7.3 7.06 6.8–7.3 6.46 6.0–7.0 10.05 9.6–11.2 13.71 10.0–18.0 13.13 9.3–14.9 8.17 7.3–9.0 8.48 7.9–9.2 7.88 7.4–8.8 Incomplete communication leads to higher dcd_c. While the GPT models have slightly lower dc d_c values compared to the Qwen models, the difference is most pronounced under free communication policies (Team-Free and Indiv-Free). Free communication can further reduce effective pruning because agents often do not report all experimental outcomes, especially negative evidence that could eliminate incorrect hypotheses (Table 3). We find that the relative increase in dcd_c under free communication, quantified by dcTeam-Free/dcTeam-Autod_c^Team -Free/d_c^Team -Auto is strongly negatively correlated (r=−0.91r=-0.91) with the rate at which agents report their experimental results (Figure 11). Higher reasoning effort increases dcd_c. We ablate GPT-6-luna’s reasoning effort, and find that higher reasoning effort either has minimal effect or actually increases the required dcd_c, moving the result further away from the theoretical prediction (Figure 4). We find that more reasoning capability led agents to herd into the most informative paths, but this decreases the diversity of explored paths and diminishes the realized benefits of communication. The average number of unique literals tested by agents decreases from 25.5→11.325.5→ 11.3 in the TCAS task, and 14.2→8.814.2→ 8.8 for the physics task. However, agents individually are either just as likely or more likely to complete the search task with higher reasoning (Figure 12). Figure 4: Higher reasoning effort on GPT-6-luna almost always raises the critical communication degree dcd_c across all policies and tasks. Sampling temperature has model- and task-dependent effects. We test the effect of sampling temperature by comparing T=0.2T=0.2 with the default T=1T=1 for three of the four models, as T=0.2T=0.2 is not available for GPT-6 Luna (Figure 5). We find that higher temperature makes agents select more wider range of candidates, allowing them to reap the benefits of communication. T=0.2T=0.2 produced a particularly noticeable dcd_c increase for the physical mechanism discovery task for GPT-5.4-Nano specifically, while making relatively insignificant changes to the results of other tasks and model families. This may be due to the inherent differences in task difficulty: e.g., adding a linear damping term is very obvious for the physical trajectory given, while few clues exist at the start when searching for a hidden configuration. Figure 5: Changing the sampling temperature can produce very different dcd_c for certain models and tasks. We test T=0.2T=0.2 (filled point) against the default temperature setting T=1T=1 (open circle) on all policies and tasks. 6 Related Works Multi-agent search. A growing literature uses systems of LLM agents to improve search efficiency through coordination and parallelization. Several works contribute orchestration strategies for multi-agent information seeking and evidence gathering (Song et al., 2026; Prabhakar et al., 2025; Chen et al., 2025; Jin et al., 2025) and benchmark such strategies (Wong et al., 2026). The line of work most relevant to us is search over possible solutions (Yang et al., 2026), hidden transformations from input to output (Li et al., 2026), and autoresearch on ML algorithm performance optimization (Jin et al., 2026). Our work analyzes the dynamics of multi-agent search problems from a theoretical lens as well as contributes empirical observations from LLM-based systems. Role of task structure and communication in multi-agent systems. The choice of communication topology in multi-agent systems has a significant impact on downstream task solving ability and efficiency (Kim et al., 2025; Zhu et al., 2025), and substantial research effort has been dedicated to designing (or learning) the optimal topology for a given problem (Zhang et al., 2024; Zhuge et al., 2024; Jiang et al., 2026; Shen et al., 2025; Zhou et al., 2026a; Zhou et al., 2026b, e.g.,). Task structure and complexity also plays a major role in the success of the multi-agent system, and different tasks have been found to require different communication protocols (Rizvi-Martel et al., 2025; Kim et al., 2025; Tang et al., 2025; Qian et al., 2025; Yang et al., 2025). Our work contributes a theory-grounded taxonomy of search task types and investigates the dependence of communication degree on task type. Collective dynamics and phase transitions in multi-agent systems. Recent works have applied the machinery of statistical mechanics and phase transitions to model the dynamics of LLM multi-agent systems. Existing works primarily leverage statistical physics theory to understand the formation of collective opinion or consensus in these systems (El et al., 2026; Okawa, 2026; De Nobili, 2026; Ashery et al., 2025; De Marzo et al., 2026; Flint et al., 2026) or the propagation and amplification of errors through communication in multi-agent systems (Niu et al., 2026; Xie et al., 2026). In contrast, our focuses on the problem of multi-agent search. Classical foundations: cooperative search, absorbing state search theory. Our work directly builds off foundational work on absorbing state phase transitions (Hinrichsen, 2000) and its applications to search problems (Semerjian and Monasson, 2003; Lee et al., 2010). Our taxonomy of search tasks is informed by classical work on search task decomposition (Dechter and Mateescu, 2007; Dechter, 1986) and the role of evidence reusability (Clearwater et al., 1991; Hamadi et al., 2009), as well as parallel branch-and-bound search (Lai and Sahni, 1984; Marinescu and Dechter, 2009). 7 Conclusion We developed an absorbing-state framework for multi-agent search that connects task structure and evidence reuse to the critical communication degree required to suppress the proliferation of incorrect candidates. Experiments on three factorizable search tasks show close agreement with theory for deterministic rule-based agents, while LLM agents exhibit deviations associated with incomplete reporting and redundant exploration. These findings motivate designing communication protocols jointly with agents’ search strategies, so that shared evidence supports both effective pruning and diverse exploration. Acknowledgmments This work was supported by the National Science Foundation (NSF) under grant number 2341055. The Flatiron Institute is funded by the Simons Foundation. References Agashe et al. (2025) S. Agashe, Y. Fan, A. Reyna, and X. E. Wang Llm-coordination: evaluating and analyzing multi-agent coordination abilities in large language models. In Findings of the Association for Computational Linguistics: NAACL 2025, p. 8053–8072. Cited by: §1. Ashery et al. (2025) A. F. Ashery, L. M. Aiello, and A. Baronchelli Emergent social conventions and collective bias in LLM populations. Science Advances 11 (20), p. eadu9368. External Links: Document, Link Cited by: §6. Brunton et al. (2016) S. L. Brunton, J. L. Proctor, and J. N. Kutz Discovering governing equations from data by sparse identification of nonlinear dynamical systems. Proceedings of the National Academy of Sciences 113 (15), p. 3932–3937. External Links: Document Cited by: §4.1. Chen et al. (2025) Z. Chen, K. Liu, Q. Wang, J. Liu, W. Zhang, K. Chen, and F. Zhao MindSearch: mimicking human minds elicits deep AI searcher. In International Conference on Learning Representations, External Links: Link Cited by: §6. Clearwater et al. (1991) S. H. Clearwater, B. A. Huberman, and T. Hogg Cooperative solution of constraint satisfaction problems. Science 254 (5035), p. 1181–1183. External Links: Document Cited by: §6. De Marzo et al. (2026) G. De Marzo, C. Castellano, and D. Garcia AI agents can coordinate beyond human scale. Science Advances 12, p. eaea6091. External Links: Document, Link Cited by: §6. De Nobili (2026) C. De Nobili Collective alignment in LLM multi-agent systems: disentangling bias from cooperation via statistical physics. External Links: 2605.10528, Link Cited by: §6. Dechter and Mateescu (2007) R. Dechter and R. Mateescu AND/OR search spaces for graphical models. Artificial Intelligence 171 (2–3), p. 73–106. External Links: Document Cited by: §1, §2.3, §6. Dechter (1986) R. Dechter Learning while searching in constraint-satisfaction-problems. In Proceedings of the Fifth National Conference on Artificial Intelligence, p. 178–183. External Links: Link Cited by: §1, §6. Do et al. (2005) H. Do, S. Elbaum, and G. Rothermel Supporting controlled experimentation with testing techniques: an infrastructure and its potential impact. Empirical Software Engineering 10 (4), p. 405–435. External Links: Document Cited by: §4.1. Du et al. (2024) Y. Du, S. Li, A. Torralba, J. B. Tenenbaum, and I. Mordatch Improving factuality and reasoning in language models through multiagent debate. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 11733–11763. External Links: Link Cited by: §1. d’Ascoli et al. (2024) S. d’Ascoli, S. Becker, P. Schwaller, A. Mathis, and N. Kilbertus ODEFormer: symbolic regression of dynamical systems with transformers. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §B.3, §4.1. El et al. (2026) B. El, J. Paeng, F. Dinc, S. Su, M. Erdogan, A. Pappu, H. Ye, W. Zhao, S. Ganguli, and J. Zou Physics of agents: statistical mechanics predicts collective behavior of ai agents. External Links: 2608.16578, Link Cited by: §1, §6. Flint et al. (2026) A. Flint, L. M. Aiello, R. Pastor-Satorras, and A. Baronchelli Group size effects and collective misalignment in LLM multi-agent systems. Proceedings of the National Academy of Sciences 123 (34), p. e2531697123. External Links: Document, Link Cited by: §6. Ghandehari et al. (2013) L. S. G. Ghandehari, M. N. Borazjany, Y. Lei, R. N. Kacker, and D. R. Kuhn Applying combinatorial testing to the Siemens suite. In 2013 IEEE Sixth International Conference on Software Testing, Verification and Validation Workshops (ICSTW), p. 362–371. External Links: Document Cited by: §B.2. Gulwani et al. (2017) S. Gulwani, A. Polozov, and R. Singh Program synthesis. Vol. 4, NOW. External Links: Link Cited by: §1. Guo et al. (2024) T. Guo, X. Chen, Y. Wang, R. Chang, S. Pei, N. V. Chawla, O. Wiest, and X. Zhang Large language model based multi-agents: a survey of progress and challenges. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, p. 8048–8057. Note: Survey Track External Links: Document, Link Cited by: §1. Hamadi et al. (2009) Y. Hamadi, S. Jabbour, and L. Sais ManySAT: a parallel SAT solver. Journal on Satisfiability, Boolean Modeling and Computation 6, p. 245–262. External Links: Link Cited by: §6. Hinrichsen (2000) H. Hinrichsen Non-equilibrium critical phenomena and phase transitions into absorbing states. Advances in Physics 49 (7), p. 815–958. External Links: Document Cited by: §6. Hong et al. (2024) S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, J. Wang, C. Zhang, S. Yau, Z. Lin, L. Zhou, et al. MetaGPT: meta programming for a multi-agent collaborative framework. In International Conference on Learning Representations, Vol. 2024, p. 23247–23275. Cited by: §1. Hutchins et al. (1994) M. Hutchins, H. Foster, T. Goradia, and T. Ostrand Experiments on the effectiveness of dataflow- and controlflow-based test adequacy criteria. In Proceedings of the 16th International Conference on Software Engineering (ICSE), p. 191–200. Cited by: §B.2, §4.1. Ising (1925) E. Ising Beitrag zur theorie des ferromagnetismus. Zeitschrift für Physik 31 (1), p. 253–258. External Links: Document Cited by: §1. Jiang et al. (2026) E. H. Jiang, L. Li, F. Wan, X. Liang, S. Yin, Y. Wu, X. Li, Y. Sun, W. Wang, K. Chang, and Y. N. Wu Dynamic generation of multi LLM agents communication topologies with graph diffusion models. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), M. Liakata, V. P. Moreira, J. Zhang, and D. Jurgens (Eds.), San Diego, California, United States, p. 38042–38060. External Links: Link, Document, ISBN 979-8-89176-390-6 Cited by: §6. Jin et al. (2026) J. Jin, Y. Hu, K. Qiu, Q. Dai, C. Luo, G. Dong, X. Li, T. Zhao, X. Ma, G. Zhang, Z. Wu, B. Liu, Z. Yang, L. Li, L. Wang, H. Qian, Y. Zhu, and Z. Dou Toward generalist autonomous research via hypothesis-tree refinement. arXiv preprint arXiv:2606.11926. External Links: 2606.11926 Cited by: §6. Jin et al. (2025) J. Jin, X. Li, G. Dong, Y. Zhang, Y. Zhu, Y. Zhao, H. Qian, and Z. Dou HiRA: a hierarchical reasoning framework for decoupled planning and execution in deep search. External Links: 2507.02652, Link Cited by: §6. Karp and Zhang (1993) R. M. Karp and Y. Zhang Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM 40 (3), p. 765–789. Cited by: §2.3. Kim et al. (2025) Y. Kim, K. Gu, C. Park, C. Park, S. Schmidgall, A. A. Heydari, Y. Yan, Z. Zhang, Y. Zhuang, Y. Liu, M. Malhotra, P. P. Liang, H. W. Park, Y. Yang, X. Xu, Y. Du, S. Patel, T. Althoff, D. McDuff, and X. Liu Towards a science of scaling agent systems. External Links: 2512.08296, Document, Link Cited by: §1, §6. Kim et al. (2024) Y. Kim, C. Park, H. Jeong, Y. S. Chan, X. Xu, D. McDuff, H. Lee, M. Ghassemi, C. Breazeal, and H. W. Park MDAgents: an adaptive collaboration of LLMs for medical decision-making. In Advances in Neural Information Processing Systems, Vol. 37, p. 79410–79452. External Links: Document, Link Cited by: §1. Kuhn and Okun (2006) D. R. Kuhn and V. Okun Pseudo-exhaustive testing for software. In 2006 30th Annual IEEE/NASA Software Engineering Workshop, Vol. , p. 153–158. External Links: Document Cited by: §4.1. Lai and Sahni (1984) T. Lai and S. Sahni Anomalies in parallel branch-and-bound algorithms. Commun. ACM 27 (6), p. 594–602. External Links: ISSN 0001-0782, Link, Document Cited by: §1, §2.3, §2.3, §6. Lee et al. (2010) S. H. Lee, M. Ha, C. Jeon, and H. Jeong Finite-size scaling in random K-satisfiability problems. Physical Review E 82 (6), p. 061109. External Links: Document Cited by: §6. Li et al. (2026) X. Li, Y. Zhou, X. Wei, Z. Shi, H. Wan, Y. Gong, F. Liu, and J. Li LLM inductive reasoning through multi-agent enhanced Monte Carlo tree search. In Findings of the Association for Computational Linguistics: ACL 2026, p. 23548–23562. External Links: Document, Link Cited by: §6. Li et al. (2024) Y. Li, Y. Du, J. Zhang, L. Hou, P. Grabowski, Y. Li, and E. Ie Improving multi-agent debate with sparse communication topology. In Findings of the Association for Computational Linguistics: EMNLP 2024, p. 7281–7294. Cited by: §1. Marinescu and Dechter (2009) R. Marinescu and R. Dechter AND/OR branch-and-bound search for combinatorial optimization in graphical models. Artificial Intelligence 173 (16–17), p. 1457–1491. External Links: Link Cited by: §6. Morales et al. (2026) I. E. Morales, D. Hinz, M. Alberts, G. Krawezik, H. Jeong, and S. Ho NMR elucidation as an agentic search problem, not a modeling problem. arXiv preprint arXiv:2607.19406. Cited by: §1. Niu et al. (2026) R. Niu, X. Shu, and Y. Zhao Reliability-contagion feasibility in LLM multi-agent networks. arXiv preprint arXiv:2607.21912. External Links: 2607.21912 Cited by: §1, §6. Okawa (2026) M. Okawa Emergence of biased consensus in multi-agent LLM debates. In Proceedings of the 43rd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 306. External Links: Link Cited by: §6. Prabhakar et al. (2025) A. Prabhakar, R. Ram, Z. Chen, S. Savarese, F. Wang, C. Xiong, H. Wang, and W. Yao Enterprise deep research: steerable multi-agent deep research for enterprise analytics. arXiv preprint arXiv:2510.17797. External Links: Document, Link Cited by: §6. Qian et al. (2024) C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, J. Xu, D. Li, Z. Liu, and M. Sun ChatDev: communicative agents for software development. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Bangkok, Thailand, p. 15174–15186. External Links: Document, Link Cited by: §1. Qian et al. (2025) C. Qian, Z. Xie, Y. Wang, W. Liu, K. Zhu, H. Xia, Y. Dang, Z. Du, W. Chen, C. Yang, Z. Liu, and M. Sun Scaling large language model-based multi-agent collaboration. In International Conference on Learning Representations, External Links: Link Cited by: §1, §6. Rizvi-Martel et al. (2025) M. Rizvi-Martel, S. Bhattamishra, N. Rathi, G. Rabusseau, and M. Hahn Benefits and limitations of communication in multi-agent reasoning. arXiv preprint arXiv:2510.13903. External Links: 2510.13903 Cited by: §1, §6. Semerjian and Monasson (2003) G. Semerjian and R. Monasson Relaxation and metastability in a local search procedure for the random satisfiability problem. Physical Review E 67 (6), p. 066103. External Links: Document Cited by: §6. Shen et al. (2025) X. Shen, Y. Liu, Y. Dai, Y. Wang, R. Miao, Y. Tan, S. Pan, and X. Wang Understanding the information propagation effects of communication topologies in LLM-based multi-agent systems. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, C. Christodoulopoulos, T. Chakraborty, C. Rose, and V. Peng (Eds.), Suzhou, China, p. 12347–12361. External Links: Link, Document, ISBN 979-8-89176-332-6 Cited by: §6. Song et al. (2026) X. Song, L. Zhang, K. Zhao, Y. Zhu, Z. Wang, G. Dong, J. Yang, H. Li, K. Gai, J. Wen, and Z. Dou WebSwarm: recursive multi-agent orchestration for deep-and-wide web search. arXiv preprint arXiv:2607.08662. External Links: Document, Link Cited by: §6. Sutton (2019) R. Sutton The bitter lesson. Cited by: §1. Tang et al. (2025) B. Tang, H. Liang, K. Jiang, and X. Dong On the importance of task complexity in evaluating LLM-based multi-agent systems. External Links: 2510.04311, Document, Link Cited by: §1, §6. Wong et al. (2026) R. Wong, J. Wang, J. Zhao, L. Chen, Y. Gao, L. Zhang, X. Zhou, Z. Wang, K. Xiang, G. Zhang, W. Huang, Y. Wang, and K. Wang WideSearch: benchmarking agentic broad info-seeking. In International Conference on Learning Representations, p. 10012–10086. Cited by: §6. Wu et al. (2023) Q. Wu, G. Bansal, J. Zhang, Y. Wu, B. Li, E. Zhu, L. Jiang, X. Zhang, S. Zhang, J. Liu, et al. Autogen: enabling next-gen llm applications via multi-agent conversation. arXiv preprint arXiv:2308.08155. Cited by: §1. Xie et al. (2026) Y. Xie, C. Zhu, X. Zhang, T. Zhu, D. Ye, M. Qi, H. Chen, and W. Zhou From spark to fire: modeling and mitigating error cascades in llm-based multi-agent collaboration. arXiv preprint arXiv:2603.04474. External Links: 2603.04474 Cited by: §1, §6. Yang et al. (2025) J. Yang, M. Zhang, Y. Jin, H. Chen, Q. Wen, L. Lin, Y. He, S. Kumar, W. Xu, J. Evans, and J. Wang Topological structure learning should be a research priority for LLM-based multi-agent systems. External Links: 2505.22467, Document, Link Cited by: §1, §6. Yang et al. (2026) S. Yang, Y. Li, W. Lam, and Y. Cheng Multi-LLM collaborative search for complex problem solving. In Findings of the Association for Computational Linguistics: ACL 2026, p. 42599–42614. External Links: Document, Link Cited by: §6. Zhang et al. (2024) G. Zhang, Y. Yue, X. Sun, G. Wan, M. Yu, J. Fang, K. Wang, T. Chen, and D. Cheng G-Designer: architecting multi-agent communication topologies via graph neural networks. arXiv preprint arXiv:2410.11782. External Links: 2410.11782 Cited by: §1, §6. Zheng et al. (2026) T. Zheng, K. K. Tam, N. H. K. Nguyen, B. Xu, Z. Wang, J. Cheng, H. T. Tsang, W. Wang, J. Bai, T. Fang, Y. Song, G. Y. Wong, and S. See NewtonBench: benchmarking generalizable scientific law discovery in llm agents. In International Conference on Learning Representations, External Links: Link Cited by: §B.3, §4.1. Zhou et al. (2026a) H. Zhou, X. Wan, R. Sun, H. Palangi, S. Iqbal, I. Vulić, A. Korhonen, and S. Arik Multi-agent design: optimizing agents with better prompts and topologies. In International Conference on Learning Representations, Vol. 2026, p. 15844–15872. Cited by: §6. Zhou et al. (2026b) H. Zhou, X. Wan, R. Sun, H. Palangi, S. Iqbal, I. Vulić, A. Korhonen, and S. Ö. Arık Multi-agent design: optimizing agents with better prompts and topologies. In International Conference on Learning Representations, Note: MASS; arXiv:2502.02533 Cited by: §6. Zhu et al. (2025) K. Zhu, H. Du, Z. Hong, X. Yang, S. Guo, Z. Wang, Z. Wang, C. Qian, X. Tang, H. Ji, and J. You MultiAgentBench: evaluating the collaboration and competition of LLM agents. arXiv preprint arXiv:2503.01935. External Links: 2503.01935 Cited by: §1, §6. Zhuge et al. (2024) M. Zhuge, W. Wang, L. Kirsch, F. Faccio, D. Khizbullin, and J. Schmidhuber GPTSwarm: language agents as optimizable graphs. arXiv preprint arXiv:2402.16823. External Links: 2402.16823 Cited by: §6. Appendix A Additional Theoretical Analysis A.1 Concentration of Agents Using the same notation as in Section 3.2, the round-dependent mean-field dynamics are At+1≃rtMF(d)(At−mN),A_t+1 r_t MF(d) (A_t-mN ), with rtMF(d)=b(1−mqt)d.r_t MF(d)=b (1-mq_t )^d. Here the pruning and overlap probabilities are evaluated at step t. As in the main text, AtA_t counts active incorrect candidates across all agents, with copies held by different agents counted separately. This description assumes sufficient experiment supply and approximately homogeneous, independent pruning opportunities from different neighbors. Initialization can affect both assumptions through the width and composition of the local hypothesis frontiers. We distinguish two possible sources of initialization sensitivity: frontier extinction, which reduces experiment supply, and correlated or redundant evidence, which reduces the pruning value of communication. These mechanisms provide possible explanations for deviations from mean-field predictions; a shift in the critical degree alone does not identify either mechanism. A.1.1 Frontier extinction An agent with a narrow hypothesis frontier may lose all of its surviving branches after receiving valid evidence, even when a large unexplored hypothesis space remains globally. Without frontier replenishment, the agent can no longer propose experiments from surviving hypotheses. Communication can therefore reduce the subsequent supply of evidence through the sequence incoming evidence evidence ⇒local pruning⇒frontier extinction \;local pruning\; \;frontier extinction ⇒candidate depletion⇒budget underuse. \;candidate depletion\; \;budget underuse. Initial frontier width and composition affect the number of alternative branches available after early pruning events. This mechanism does not require different agents to occupy the same hypothesis: distinct local frontiers can be exhausted independently. Moreover, an empty frontier does not itself certify task success, since the correct branch may also be absent. Define the budget-utilization fraction and active-agent fraction by ut=BtusedNm,at=NtactN,u_t= B_t usedNm, a_t= N_t actN, where BtusedB_t used is the number of experiments performed in round t, and NtactN_t act counts agents with at least one eligible experiment immediately before experiment allocation. When the total budget can be redistributed among active agents, at<1a_t<1 does not necessarily imply ut<1u_t<1. The remaining agents may absorb the unused allocations, provided their candidate capacity is sufficient. To account for reduced experiment supply, we define qt,eff≡ut−1qt,q_t, eff≡ u_t-1q_t, so that the effective communication-induced reproduction factor becomes rt,eff(d)=b(1−mut−1qt)d.r_t, eff(d)=b (1-mu_t-1q_t )^d. The index t−1t-1 reflects one-round delayed communication; an initially empty inbox contributes no communication pruning. The mean-field supply assumption corresponds to ut−1≃1u_t-1 1. When ut−1<1u_t-1<1, communication provides less pruning than predicted by mean field, shifting the critical degree toward dcempirical>dcMF.d_c empirical>d_c MF. A.1.2 Correlated evidence Even when experiment supply is sufficient, the assumption of independent neighbor evidence can fail at large communication degree. Different agents may receive strongly overlapping sets of evidence. Their exact hypothesis frontiers need not become similar, but their accumulated constraints can become correlated. Consequently, different neighbors may send duplicate or already implied evidence. The possible feedback is summarized schematically as d↑ d ⇒shared evidence↑⇒constraint overlap↑ \;shared evidence \; \;constraint overlap (10) ⇒redundant evidence↑⇒communication efficiency↓. \;redundant evidence \; \;communication efficiency . Duplicate observations alone do not establish this mechanism, since independent experiments can also coincide. Let scomm(t,d)s_ comm(t,d) be the survival probability of an incorrect candidate present immediately before communication. We define an effective communication degree through scomm(t,d)=(1−mqt)deff(t,d).s_ comm(t,d)= (1-mq_t )^d_ eff(t,d). When the reference probability is accurate and neighbor pruning is approximately homogeneous and independent, deff≃d_ eff d. Redundancy can instead give deff<d_ eff<d. This inequality is not universal: deffd_ eff is a descriptive diagnostic and can also reflect inaccuracies in the reference probability or heterogeneity among candidates. Holding the remaining reproduction dynamics fixed, weaker pruning can shift the candidate-growth crossing toward dcempirical>dcMF.d_c empirical>d_c MF. A.2 Parent-locked Reference The parent-locked regime remains useful as an analytically tractable reference, but it should not be interpreted as the typical state of the synthetic system. In this limit all active agents share the same parent hypothesis at the beginning of a round, Ht(1)=Ht(2)=⋯=Ht(N),H_t^(1)=H_t^(2)=·s=H_t^(N), while independently sampling children from that common parent. At depth t, the number of possible children is St=K(M−t+1).S_t=K(M-t+1). If an active agent generates b children, the probability that a specific child h is generated is P(h∈ℬt(j))=bK(M−t+1).P(h _t^(j))= bK(M-t+1). Assume that the total experimental budget NmNm can be fully used and redistributed among active agents. In the regime where its candidate capacity is sufficient to use this allocation, P(h tested∣h∈ℬt(j),jactive)≃matb.P($h$ tested h _t^(j),j\ active) ma_tb. A randomly selected neighbor is active with probability ata_t. Therefore, the pruning probability contributed by one nominal neighbor is mqtlock=atbK(M−t+1)matb=mK(M−t+1),mq_t lock=a_t bK(M-t+1) ma_tb= mK(M-t+1), The active fraction and branching number cancel as long as the total experimental budget can indeed be used. For T≪MT M and the standard full-depth approximation, this gives the scaling dclock≃MKlnbm=|ℒ|lnbm.d_c lock MK bm= |L| bm. The parent-locked limit should therefore be regarded as a reference regime in which agents share the same parent but retain independent child sampling. In the concentrated regime, the critical communication degree is bounded by 2|ℒ|lnbmT≲dcconc≲|ℒ|lnbm. 2|L| bmT d_c conc |L| bm. Appendix B Task Details We consider three tasks: synthetic component search, TCAS configuration-fault localization, and physical mechanism discovery. All use the same branching-and-pruning protocol, but differ in the meaning of a hypothesis, the experimental interface, and the evidence available for pruning. Throughout, H⋆H denotes the hidden mechanism, T its number of components, and hth_t a hypothesis containing t components. Hypotheses are sets, so different refinement orders can reach the same node. The examples below are therefore partial views of a confluent hypothesis graph; blank nodes and ellipses indicate omitted hypotheses. B.1 Synthetic Search Task Hidden mechanism and hypotheses. The task has M candidate components, each with a value set V of size K. We write ℓj,a _j,a for the atomic assignment “component j takes value a,” where j∈1,…,Mj∈\1,…,M\ and a∈a . The hidden mechanism is H⋆=ℓj1,a1⋆,…,ℓjT,aT⋆,T≤M,H =\ _j_1,a_1 ,…, _j_T,a_T \, T≤ M, with distinct component indices j1,…,jTj_1,…,j_T. These indices are sampled uniformly from the size-T subsets of 1,…,M\1,…,M\, and their values are sampled uniformly from V. A depth-t hypothesis contains t assignments to distinct components; there are (Mt)Kt MtK^t possible hypotheses at depth t. A partial hypothesis is truth-compatible exactly when ht⊆H⋆h_t H . Experiments and evidence. An experiment tests one proposed atomic assignment ℓj,a _j,a. A refuted assignment prunes every local hypothesis containing it and is not regenerated; communicated experimental records allow neighbors to apply the same pruning rule. A run succeeds when at least one agent uniquely identifies H⋆H at depth T. Success criterion. A run succeeds when at least one agent identifies the complete ground-truth mechanism H⋆H at depth T and its constituent assignments are supported by the accumulated experimental evidence. depth 0depth 1depth 2depth 3∅ ℓ1,1 _1,1ℓ2,0 _2,0ℓ3,1 _3,1⋯·sℓ1,1ℓ3,0 _1,1 _3,0ℓ1,1ℓ3,1 _1,1 _3,1ℓ1,1ℓ2,0 _1,1 _2,0ℓ2,0ℓ3,1 _2,0 _3,1⋯·s⋯·sℓ1,1ℓ2,0ℓ4,0 _1,1 _2,0 _4,0ℓ1,1ℓ2,0ℓ3,1 _1,1 _2,0 _3,1ℓ1,1ℓ2,0ℓ4,1 _1,1 _2,0 _4,1⋯·s same hypothesis up to order == same node experiment:test if correctexperiment:test if correct Figure 6: Synthetic hypothesis search graph. Each symbol ℓj,a _j,a denotes the atomic assignment that component j takes value a. Each refinement adds one previously unassigned component–value pair. Different assignment orders can reach the same hypothesis node, and experimentally refuted assignments prune all hypotheses that contain them. B.2 TCAS Configuration-Fault Localization Hidden mechanism and hypotheses. We use the configuration space of tcas from the Siemens test suite as a controlled fault-localization benchmark [Hutchins et al., 1994, Ghandehari et al., 2013]. There are M=12M=12 categorical parameters. Parameter pjp_j has a legal value set jV_j of size KjK_j. The parameter cardinalities are seven binary, two ternary, one four-valued, and two ten-valued, giving ||=∏j=112Kj=460,800,S=∑j=112Kj=44.|X|= _j=1^12K_j=460,800, S= _j=1^12K_j=44. Here |||X| counts complete configurations, whereas S counts atomic parameter–value assignments. The hidden mechanism H⋆H is a failure-inducing combination of T assignments to distinct parameters. A depth-t hypothesis is ht=pj1=va1,…,pjt=vat,h_t=\p_j_1=v_a_1,…,p_j_t=v_a_t\, and each refinement assigns one previously unassigned parameter. Different assignment orders can therefore reach the same partial configuration, as illustrated in Fig. 7. Experiments and evidence. An experiment tests a complete configuration x=(x1,…,xM)∈x=(x_1,…,x_M) compatible with a proposed refinement and returns y(x)∈pass,faily(x)∈\pass,fail\. We write h⊆xh x when x satisfies every assignment in h. The configuration–outcome table can be precomputed, so an experimental query is implemented as a table lookup. Under the conjunctive fault model, a passing configuration rules out every candidate sufficient failure-inducing combination contained in it: y(x)=pass,h⊆x⟹h is ruled out as a sufficient failure condition.y(x)=pass, h x h is ruled out as a sufficient failure condition. A failing configuration does not identify which subset of assignments caused the failure and therefore does not, by itself, refute a particular atomic assignment. Agents communicate the records (x,y(x))(x,y(x)), allowing neighbors to apply the same evidence to their own candidate hypotheses. Unlike the synthetic component test, this experiment therefore returns a verdict on a complete configuration rather than on one atomic assignment. Success criterion. A complete candidate h predicts failure when h⊆xh x and pass otherwise; denote this prediction by y^h(x) y_h(x). It is evaluated on a separate held-out configuration set ℰtestE_test using D(h,H⋆)=1|ℰtest|∑x∈ℰtest[y^h(x)≠y⋆(x)],D(h,H )= 1|E_test| _x _test1\! [ y_h(x)≠ y (x) ], where y⋆(x)y (x) is the hidden system’s outcome. A run succeeds when at least one agent reaches a depth-T hypothesis with D(h,H⋆)<ϵD(h,H )<ε that is also consistent with the configuration–outcome evidence accumulated during search. depth 0depth 1depth 2depth 3∅ 1=v1p_1=v_1p3=v2p_3=v_2p7=v1p_7=v_1⋯·sp1=v1,p6=v3p_1=v_1,\;p_6=v_3p1=v1,p9=v4p_1=v_1,\;p_9=v_4p1=v1,p3=v2p_1=v_1,\;p_3=v_2p3=v2,p7=v1p_3=v_2,\;p_7=v_1⋯·s⋯·sp1=v1,p3=v2,p6=v3p_1=v_1,\;p_3=v_2,\;p_6=v_3p1=v1,p3=v2,p8=v1p_1=v_1,\;p_3=v_2,\;p_8=v_1p1=v1,p3=v2,p10=v2p_1=v_1,\;p_3=v_2,\;p_10=v_2 Figure 7: TCAS configuration-fault hypothesis graph. Each child adds one parameter–value assignment to its parent. Different assignment orders that produce the same partial configuration correspond to the same hypothesis node. Blank nodes and ellipses indicate additional hypotheses omitted for clarity. B.3 Physical Mechanism Discovery Task Hidden mechanism and hypotheses. Following the dynamical-system discovery setting of ODEBench and the interactive probing setting of NewtonBench [d’Ascoli et al., 2024, Zheng et al., 2026], we consider a hidden equation of motion x¨=f⋆(x,x˙,τ)=∑c∈H⋆c(x,x˙,τ),|H⋆|=T. x=f (x, x,τ)= _c∈ H c(x, x,τ), |H |=T. Here τ denotes physical time, to distinguish it from search depth t. Candidate terms come from M symbolic component families, each with K allowed parameter choices. An atomic component specifies both a symbolic family and its parameter choice. Examples include a linear restoring force, a cubic restoring force, linear or state-dependent damping, and periodic forcing. A depth-t hypothesis ht=c1,…,cth_t=\c_1,…,c_t\ contains t components, and a refinement adds one new symbolic component. Addition order does not affect the resulting mechanism, as illustrated in Fig. 8. Experiments and evidence. Before the first communication round, each agent receives a different short trajectory from the same hidden system. These local observations probe different regions of state space and are held fixed across communication degrees. An experiment selects an initial state z0=(x0,x˙0)z_0=(x_0, x_0) and starting time τ0 _0 from a fixed experiment bank and returns ℰ(z0,τ0)=(τℓ,z(τℓ))ℓ=1L,τℓ∈[τ0,τ0+Δτ],E(z_0, _0)=\( _ ,z( _ ))\_ =1^L, _ ∈[ _0, _0+ τ], where z=(x,x˙)z=(x, x). The observation duration Δτ τ, number of measurements L, and measurement precision are fixed. Experiments are chosen to help distinguish a proposed component from the current hypothesis. In the controlled rule-based version, experimental evidence is reduced to the idealized component-level outcome y(c)=[c∈H⋆].y(c)=1[c∈ H ]. This is the stipulated evidence interface for the controlled experiment, not a claim that an arbitrary short trajectory uniquely identifies a term. Negative evidence removes every hypothesis containing c; positive evidence confirms c and excludes incompatible parameter choices in the same family. The testing agent keeps the physical trajectory private and communicates only the component-level record (c,y(c))(c,y(c)). Success criterion. A run succeeds when at least one agent discovers a depth-T mechanism that is consistent with the experimental evidence accumulated during search and predicts a separate set of held-out trajectories with error D(h,H⋆)<ϵ.D(h,H )<ε. Here D denotes held-out trajectory prediction error, distinct from the configuration-classification error used for TCAS. depth 0depth 1depth 2depth 3∅ −ax-ax−bx3-bx^3−cx˙-c x⋯·s−ax,−cx˙-ax,\,-c x−ax,+Acos(ωt)-ax,\,+A (ω t)−ax,−bx3-ax,\,-bx^3−bx3,−cx˙-bx^3,\,-c x⋯·s⋯·s−ax,−bx3,−cx˙-ax,\,-bx^3,\,-c x−ax,−bx3,−cx˙1+dx2-ax,\,-bx^3,\,- c x1+dx^2−ax,−bx3,+Acos(ωt)-ax,\,-bx^3,\,+A (ω t) Figure 8: Physical-mechanism hypothesis graph. Each child adds one atomic symbolic component to its parent. Different addition orders can reach the same mechanism. Blank nodes and ellipses indicate additional hypotheses omitted for clarity. Appendix C Additional Results C.1 Sharpening of the Success Crossover We test whether the success crossover becomes sharper as the search horizon T increases. We use the synthetic benchmark and vary only T, while fixing N=80,M=8,K=4,b=3,m=1.N=80, M=8, K=4, b=3, m=1. For a given communication degree d, we define an episode as successful if at least one agent recovers the true hypothesis with supporting evidence. The empirical success probability is therefore Psucc(d)=1E∑e=1E[at least one agent succeeds in episode e],P_succ(d)= 1E _e=1^E1\! [at least one agent succeeds in episode e ], (11) where E=8E=8 episodes are evaluated at each degree. Consequently, the empirical probabilities take values in increments of 1/81/8. Figure 9 shows the raw empirical Psucc(d)P_succ(d) for three representative horizons, T=3,4,5T=3,4,5. The crossover is broad at T=3T=3 and becomes progressively more concentrated in d as T increases. Figure 9: Empirical success probability Psucc(d)P_succ(d) as a function of communication degree d for representative horizons T=3,4,5T=3,4,5 in the synthetic benchmark. Each point is the observed success fraction over eight independent task seeds, where an episode is successful if at least one agent recovers the ground-truth hypothesis with supporting evidence. Dashed vertical lines indicate the fitted crossover midpoint d1/2d_1/2. As T increases, the crossover shifts to lower communication degree and becomes visibly sharper. To quantify this sharpening, we fit the episode-level binary success outcomes with a logistic crossover, Pfit(d)=11+exp[−(d−d1/2)/w],P_fit(d)= 11+ [-(d-d_1/2)/w], (12) where d1/2d_1/2 is the degree at which the fitted success probability equals 1/21/2, and w controls the crossover width. Let dpd_p denote the degree at which Pfit(dp)=pP_fit(d_p)=p. We define the 10%10\%–90%90\% width as Δd10–90=d0.9−d0.1=wln81. d_10--90=d_0.9-d_0.1=w 81. Because the location of the crossover shifts substantially with T, we use the dimensionless relative width wrel≡Δd10–90d1/2=wln81d1/2.w_rel≡ d_10--90d_1/2= w 81d_1/2. (13) Smaller wrelw_rel corresponds to a sharper crossover. Across the full scan T=3,…,8T=3,…,8, we obtain T345678wrel1.5600.8270.5740.4430.4360.069. array[]c|cT&3&4&5&6&7&8\\ w_rel&1.560&0.827&0.574&0.443&0.436&0.069. array The relative width decreases strongly with T, with only a small finite-sample variation between T=6T=6 and T=7T=7. Figure 10: Relative crossover width versus search horizon. The relative 10%10\%–90%90\% width wrel=(d0.9−d0.1)/d1/2w_rel=(d_0.9-d_0.1)/d_1/2 obtained from logistic fits to the episode-level success outcomes. The width decreases strongly as T increases, indicating progressive sharpening of the finite-size success crossover. The line connecting the points is included only as a guide to the eye. Together, Figs. 9 and 10 show that increasing the search horizon systematically sharpens the finite-horizon success crossover in communication degree. This progressive narrowing is consistent with increasingly phase-transition-like behavior as T grows, while the transition remains smooth at the finite horizons considered here. C.2 LLM Communication Behavior under Free Communication Table 3 shows a detailed breakdown of how agents chose to communicate under free communication policies Team-Free and Indiv-Free. Both conditions allow free-form messages, and the prompt explicitly permits agents to withhold a result or to report an outcome different from the one they observed. A very small percentage of Qwen agents misreported, but the most noticeable result is that Qwen models are generally more reticent than GPT models. Qwen models communicate positive verification results 49-66% of the time, while GPT models do 75-84% of the time. Qwen models are also more unlikely to disclose negative verification results (35-53%), compared to 69-84% by GPT models. Table 3: Communication behavior under Team-Free and Indiv-Free policies, pooled over six task seeds and three environments. Qwen3.5-4B Qwen3.5-9B GPT-5.4 Nano GPT-6 Luna Metric Team- Free Indiv- Free Team- Free Indiv- Free Team- Free Indiv- Free Team- Free Indiv- Free Structured reports sent 6,702 6,921 5,081 4,975 8,965 8,556 9,103 9,004 Misreported outcomes 0.81% 0.87% 0.98% 1.19% 0.09% 0.09% 0.00% 0.00% Sent nothing 13.8% 15.2% 27.4% 30.5% 13.3% 17.7% 5.7% 16.3% Used free text 68.8% 63.2% 68.7% 64.8% 75.5% 64.9% 89.9% 70.1% Positive findings disclosed 66.1% 65.6% 49.8% 49.0% 80.3% 75.5% 84.0% 82.5% Negative findings disclosed 51.5% 53.2% 36.1% 35.4% 72.5% 69.1% 84.3% 82.4% Table 4 shows dc(ColumnName)−dc(Team-Auto)d_c(ColumnName)-d_c(Team-Auto): the difference between dcd_c for each free-commmunication policy and the baseline, automatic communication. Figure 11 shows the correlation between the ratio of dcd_c measured from Team-Free and Team-Auto policies (representing the difference in dcd_c that perfect communication makes) and the rate at which models report their findings to their neighbors. Table 4: Each entry is Δdc d_c, the paired difference in critical degree between a free-communication policy (Team-Free or Indiv-Free) and the fixed-communication baseline Team-Auto: positive means free communication raises dcd_c, so more communication is needed to suppress incorrect lineages. Intervals are exact 95% cluster bootstraps over those six seeds. Entries are Δ−lower+upper ^+upper_-lower. Synthetic TCAS Physics Model Team- Free Indiv- Free Team- Free Indiv- Free Team- Free Indiv- Free Qwen3.5-4B 6.27−0.56+0.486.27^+0.48_-0.56 6.92−1.90+2.556.92^+2.55_-1.90 4.90−0.58+6.774.90^+6.77_-0.58 7.33−2.66+4.167.33^+4.16_-2.66 5.17−1.48+1.095.17^+1.09_-1.48 5.54−3.10+2.885.54^+2.88_-3.10 Qwen3.5-9B 9.37−2.03+1.059.37^+1.05_-2.03 9.42−2.08+2.009.42^+2.00_-2.08 16.24−5.47+5.0216.24^+5.02_-5.47 14.40−1.99+1.2014.40^+1.20_-1.99 8.73−2.18+1.698.73^+1.69_-2.18 8.43−2.13+1.728.43^+1.72_-2.13 GPT-5.4 Nano 1.48−0.84+1.381.48^+1.38_-0.84 0.90−0.63+0.660.90^+0.66_-0.63 2.35−1.62+0.872.35^+0.87_-1.62 3.88−3.16+0.823.88^+0.82_-3.16 2.09−1.97+3.232.09^+3.23_-1.97 1.84−1.19+0.861.84^+0.86_-1.19 GPT-6 Luna 0.18−0.57+0.600.18^+0.60_-0.57 −0.42−0.64+0.67-0.42^+0.67_-0.64 3.66−3.25+3.513.66^+3.51_-3.25 3.08−3.46+0.963.08^+0.96_-3.46 0.32−0.97+0.840.32^+0.84_-0.97 −0.28−0.54+0.67-0.28^+0.67_-0.54 Figure 11: Correlation between ratio of Team-Free and Team-Auto dcd_c values and the rate at which models report their findings to their neighbors. C.3 Effect of Increasing Reasoning Effort Figure 12 shows a nuance to the story that increased reasoning effort leads to worse results (higher dcd_c). While dcd_c increases and deviates further from theory with more reasoning, reasoning often improves agents’ ability to solve the task (especially on physical mechanism discovery task). This effect is true at higher communication degrees as well, suggesting that communication still helps. Figure 12: Fraction of agents completing the search increases with reasoning in GPT-6-luna.