acceptodds
Under review as a conference paper at ICLR 2027

Absorbing State Phase Transitions in Multi-Agent Search

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 , 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
agents, multi-agent systems, statistical physics, search, scientific discovery

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_rPDgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper looks into the problem of multi-agent search via the proliferation and pruning of incorrect candidates. The paper divides multi-agent search into four categories: Needle, Chain, Hierarchical, and factorizable search, and derives a degree-based threshold for each search task. The authors utilize mean-field approximation to mimic the interaction of the multi-agent system, and introduce a taxonomy based on evidence reusability. The most interesting result is showing that the converge of multi-agent search is determined by a degree threshold and show that LLM agents deviate through incomplete reporting and redundant exploration. The authors also complete a comprehensive empirical study on the theoretical results.

Critical strengths
  • Evidence reusability is a useful organizing principle for understanding when communication can reduce search effort.

  • The branching–pruning model provides an interpretable hypothesis about collective search dynamics.

  • The communication-policy and reasoning-effort experiments identify an interesting interaction between individual strategies and collective exploration.

Critical weaknesses
  • My main concern is that suppression of incorrect candidates is not equivalent to successful search. Incorrect frontiers can disappear when the correct hypothesis was never present or when agents exhaust their candidates. Thus, the reproduction threshold is not generally a threshold for reliably solving the task. This distinction affects the central interpretation of the framework, and makes the theoretical results less meaningful.

  • The overlap approximation does not fully account for candidate composition. An incorrect depth-tt candidate need not contain tt incorrect literals. Under a negative-evidence-only membership interface, a candidate with uu incorrect literals has pruning probability u/∣L∣u/|L| under uniform literal testing. Positive evidence and mutually exclusive assignments introduce further dependencies. Selection and previous pruning also change the surviving population.

  • The degree metric should be distinguished from task performance. The paper reports that greater reasoning effort can increase task completion while also increasing the measured degree. This is an important result, but it weakens the interpretation of higher critical degree as poorer collaboration. Stronger agents may change the candidate distribution and violate the random-selection reference model.

  • Several specification inconsistencies hinder the theory–experiment correspondence. The main text uses 46 TCAS literals, whereas Appendix B.2 lists cardinalities summing to 44. Its full-configuration pass/fail interface also differs from an atomic membership oracle. For the stated toy parameters, Eq. 8 gives approximately 5.55, while Table 2 reports 6.10. Finally, the controlled physical-discovery experiment uses an ideal component-membership interface, limiting its interpretation as discovery from trajectories. Thus, can the authors provide an explanation for this?

Questions for authors
  • How does the reproduction threshold predict actual team success, cost, and correct-hypothesis retention?
  • Does directly measuring qtq_t support the proposed depth-based approximation?
  • Can controlled interventions on reporting and experiment duplication isolate the suggested mechanisms?
3 comments

We thank the reviewer for the helpful comments. Reviewer rPDg notes that our framework is “a useful organizing principle” and our results surface “potentially interesting interactions between individual strategies and collective exploration”. We address specific comments and questions below.

W1 & Q1

Suppression of incorrect candidates is not equivalent to successful search … How does the reproduction threshold predict actual team success, cost, and correct-hypothesis retention?

During the rebuttal period, we added Figure 4 to empirically demonstrate the relationship between critical degree and task success probability in Figure 4. Search success rate approaches 100% at d>dcd > d_c (right of the vertical line that indicates dcd_c for each LLM policy), showing that search success is well predicted by dcd_c. Intuitively, the reproduction threshold characterizes the statistical transition at which incorrect hypotheses change from being amplified to being suppressed. However, this transition directly corresponds to a transition in task success probability: once the communication degree exceeds the critical degree, incorrect hypotheses are systematically suppressed and the probability of success increases significantly.

W2 & Q2

The approximation (qt≃t/∣L∣q_t\simeq t/|L|) relates pruning probability to candidate depth. However, an incorrect depth-(t) candidate need not contain (t) incorrect literals. ... Does directly measuring qₜ support the proposed depth-based approximation?

Yes. For the experiments reported in the paper, the directly measured qₜ is consistent with the theoretically predicted depth-based approximation. During the rebuttal period, we added Figure 7 demonstrating that qtq_t follows a roughly linear relationship with t/Lt/L for the tasks in our paper. For real-world tasks that do not necessarily satisfy the assumptions behind our approximation, we need not assume the analytical form of qₜ. Instead, qₜ can be measured directly from the data and this empirical qₜ can be used to predict the corresponding critical degree.

W3 & Q3

The critical-degree metric can diverge from task performance. The paper reports that greater reasoning effort can increase task completion while also increasing the measured critical degree. This is an important result, but it weakens the interpretation of higher critical degree as poorer collaboration.

A search succeeds when any agent discovers the target, which is distinct from the fraction of agents that discover the target. In the case of increased reasoning effort, the overall search success rate is still low for communication degrees below dcd_c, but one agent succeeding seems to correlate with many agents succeeding. This makes some intuitive sense, as agents become more capable with increased reasoning ability and develop similar search strategies. Furthermore, more agents succeeding actually is a signal of suboptimal cooperation and search strategy. Instead of dividing and conquering, agents are herding towards the same region, which might lead to lower success rate if agents herd towards unproductive regions of the hypothesis tree. We thank the reviewer for this comment and have edited Section 5.2 and C.3 to make this distinction more clear.

W4 & Q4

Several specification inconsistencies hinder the theory–experiment correspondence. The main text uses 46 TCAS literals, whereas Appendix B.2 lists cardinalities summing to 44. Its full-configuration pass/fail interface also differs from an atomic membership oracle. For the stated toy parameters, Equation 8 gives approximately 5.55, while Table 2 reports 6.10; the correction used should be specified. Finally, the controlled physical-discovery experiment uses an ideal component-membership interface, limiting its interpretation as discovery from trajectories. Can the task interfaces, literal counts, and theoretical threshold calculations be reconciled?

The dcd_c values reported in Table 2 are computed from a delayed communication variant of Equation 5. Agents don’t communicate for the first round, since they have not yet proposed any hypotheses. This change simply starts the sum at t=2 rather than t=1. We thank the reviewer for pointing this out and have now updated Equation 5 to reflect this, and added text in the description of Table 2 to point to Equation 5. For TCAS, the experiments use the 46-literal parameterization (five binary, four ternary, one four-valued, and two ten-valued parameters). The parameters reported in Appendix B.2 were a mistake. We have corrected Appendix B.2 to match the parameterization used in the reported experiments.

I thank the authors for their rebuttal. While most of my concerns have been addressed, I remain concerned about W1 where the statement 'Suppression of incorrect candidates'' is not directly equivalent to 'successful search'. I agree that there could be an empirical correlation between the two; conceptually, these two can not be marked equivalent. However, given that most of my concerns are addressed, I am willing to stay neutral for this paper.

We thank the reviewer for acknowledging that our rebuttal successfully addressed your concerns.

I remain concerned about W1 where the statement 'Suppression of incorrect candidates'' is not directly equivalent to 'successful search'. I agree that there could be an empirical correlation between the two; conceptually, these two can not be marked equivalent.

During the rebuttal period, we updated the pdf to reflect the difference between these two concepts. Some examples of our changes:

In line 21 we replace "incorrect hypotheses do not proliferate uncontrollably and the search enters the solved state" with "hypothesis generation is suppressed, improving the probability of success."

In line 75, we define the absorbing state as "the extinction of incorrect hypotheses: as the number of incorrect hypotheses decays, success becomes extremely likely".

Hopefully this addresses the reviewer's final remaining concern!

Reviewer_UNmnOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

In this work, it uses the formalism of absorbing state phase transitions to predict the success of multi-agent search task. It introduces a new parameter, the communication degree dcd_c, that defines the minimum number of agents in communication. It derives the theoretical values of dcd_c for the tasks of needle, chain, hierarchical, and factorizable search. Experiments were conducted on real-world search and discovery tasks, including configuration fault localization and physical mechanism discovery, using non-LLM deterministic agents and 4 LLM agents. The results show that deterministic models agree with the derived theory. However, LLM agents show deviations and redundant explorations.

Critical strengths
  1. The idea of using statistical mechanics and using the formalism of absorbing-state phase transitions for LLM-based multi-agent system is interesting.

  2. The findings on the agreement between deterministic agents and the theory are informative.

  3. Different families of LLM agents and reasoning efforts have been studied, and it is good to know that the LLM models deviate from the theoretical value of dcd_c as shown in Table 2.

Critical weaknesses
  1. Besides finding the disagreement between LLM agents and deterministic agents with the theory dcd_c, I find the practical value of this work is very limited, and there are no findings that can lead to LLM agents better coordinating to achieve higher system performance. Therefore, this is a more theoretical analysis and evaluation work.

  2. There is no correlation study between dcd_c and whether the task is actually succeeded.

  3. The tasks studied in this work are less representative and do not cover the frontier tasks that actually judge the LLM agents' performance.

Questions for authors
  1. Have you studied larger API models? It is interesting to observe their relationship with dcd_c as LLM size grows.

  2. Could you please explain the weaknesses?

1 comment

We thank the reviewer for the thoughtful comments. Reviewer UNmn notes that “the idea [...] is interesting” and “the findings [...] are informative”. We address specific comments and questions below.

W1: Besides finding the disagreement between LLM agents and deterministic agents with the theory , I find the practical value of this work is very limited, and there are no findings that can lead to LLM agents better coordinating to achieve higher system performance.

The biggest practical value of our work is providing theory-grounded guidance on the communication network design of multi-agent systems. As highlighted in the third paragraph of the introduction, this addresses a critical gap in current multi-agent system design, where our understanding of communication network structures relies largely on empirical observations rather than theoretical foundations. To our knowledge, we are the first to provide theory-grounded framework for thinking about these problems.

W2: There is no correlation study between dcd_c and whether the task is actually succeeded.

During the rebuttal period, we added Figure 4 into the main text to show that success probability is well predicted by dcd_c. Search success rate approaches 100% at d>dcd > d_c (right of the vertical line, indicating dcd_c for each LLM policy). We agree that this is important to demonstrate and thank the reviewer for pointing this out.

W3: The tasks studied in this work are less representative and do not cover the frontier tasks that actually judge the LLM agents' performance.

During the rebuttal period, we experimented on a FormalMATH-derived task and find that GPT-5.4-Nano and GPT-6 Luna both exhibit a phase transition, with dcd_c values close to theory. We adapt a number theory problem from FormalMATH [1], a state-of-the-art benchmark for formal mathematical reasoning, into a factorizable search problem. We find the following dcd_c values, compared to dctheory=9.43d_c^{\text{theory}}=9.43:

ModelTeam-AutoTeam-FreeIndiv-Free
GPT-5.4-nano9.0110.5711.18
GPT-6-luna9.729.6710.93

This demonstrates that our framework is applicable to frontier tasks as well.

Q1. Have you studied larger API models? It is interesting to observe their relationship with d꜀ as LLM size grows.

During the rebuttal period, we added an experiment with GPT-6-Sol with medium reasoning. Our preliminary results on the synthetic task show that d_c does not appear to have clear correlation with capability (compared to GPT Luna, nano). We reproduce the other GPT results from Table 2 here along with our new GPT-6-Sol result (bold indicates the new result).

ModelTeam-AutoTeam-FreeIndiv-Free
GPT-5.4-nano6.397.877.29
GPT-6-luna6.887.066.46
GPT-6-Sol (medium reasoning)7.667.346.65

[1] FormalMATH: Benchmarking Formal Mathematical Reasoning of Large Language Models. Yu et al., 2025.

Reviewer_6oCrOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper models cooperative multi-agent search as a branching-and-pruning process. Each round, NN agents branch their surviving candidates bb ways, verify mm candidates, receive verification results from dd neighbors, and prune refuted candidates. The authors propose a taxonomy of four search task types:

  • Needle and chain search: no critical communication degree exists.
  • Hierarchical search: evidence prunes only a single subtree, giving dc∝Td_c \propto T.
  • Factorizable search: literals recur across paths, giving dc≈2∥L∥ln⁡bmTd_c \approx 2\|L\| \ln \frac{b}{mT}.

These results come from a mean-field recursion for the number of active incorrect candidates, with the critical degree dcd_c defined as the communication degree at which the per-round growth rate of incorrect candidates crosses one. The experiments cover three factorizable tasks (a toy task, TCAS configuration-fault localization, and physical mechanism discovery). Deterministic rule-based agents closely match the predicted dcd_c (Lin's CCC 0.93-0.97). LLM agents never improve on the prediction. Under free communication they frequently withhold results, especially negative ones, which raises dcd_c, and higher reasoning effort also raises dcd_c, which the authors attribute to herding onto the same search paths.

Critical strengths
  • The question of when does inter-agent communication help multi-agent search, and its dependence on task structure is important and timely. By connecting evidence reusability to the value of communication, the paper does a good job of proposing a formalization framework in which the contrasting predictions for hierarchical search (dc∝Td_c \propto T) and factorizable search (dc∝1Td_c \propto \frac{1}{T}) are clean and testable.

  • The LLM behavioral findings are interesting and potentially useful for agentic system design. The paper shows that the dcd_c increases as LLM agents disproportionately withhold negative evidence. dcd_c is also higher for higher reasoning effort that reduces the diversity of explored paths (unique literals tested fall from 25.5 to 11.3 on TCAS) even as individual success improves.

Critical weaknesses
  • The paper frames dcd_c as predicting search success (Eq. 6). However, Appendix C.3 and Fig. 12 show that higher reasoning effort raises dcd_c while increasing the fraction of agents that solve the task, including at high communication degrees. This suggests that incorrect-lineage reproduction rate is not a reliable proxy for performance with LLM agents, which weakens conclusions drawn from dcd_c alone (for example, "higher reasoning effort increases dcd_c"). Appendix C.1 points the same way: the fitted success midpoints d1/2=31.0,11.5,6.9d_{1/2} = 31.0, 11.5, 6.9 for T=3,4,5T = 3, 4, 5 fall much faster than the 1T\frac{1}{T} scaling of Eq. (8), which predicts roughly 23.4, 17.6, 14.1 for ∥L∥=32,b=3,m=1\|L\| = 32, b = 3, m = 1. This comparison is not discussed.

  • The paper's main theoretical contrast is between hierarchical (dc∝Td_c \propto T) and factorizable (dc∝1Td_c \propto \frac{1}{T}) search, yet all experiments use factorizable tasks. The predictions for hierarchical, needle, and chain search are never evaluated. The tasks are also more stylized than "real-world" suggests: TCAS evaluation is a precomputed table lookup, and the rule-based physics task reduces evidence to an oracle membership test y(c)=1[c∈H∗]y(c) = \mathbb{1}[c \in H^*].

Questions for authors
  1. With the stated parameters (b=2,m=1b = 2, m = 1), Eq. (8) gives dc≈5.55d_c \approx 5.55 for the toy and physics tasks (∥L∥=16,T=4\|L\| = 16, T = 4) and dc≈10.63d_c \approx 10.63 for TCAS (∥L∥=46,T=6\|L\| = 46, T = 6). The exact-log form of Eq. (5) gives 5.13 and 10.20. Table 2 reports 6.10 and 10.90. The literal count for TCAS also seems inconsistent: Section 4.2 states ∥L∥=46\|L\| = 46, while the parameter cardinalities in Appendix B.2 (seven binary, two ternary, one four-valued, two ten-valued) sum to 44. Could the authors specify how they computed these values and why there could be a discrepancy?

  2. Given that higher reasoning effort increases both dcd_c and the fraction of agents solving the task (Fig. 12), in what sense does dcd_c predict search success for LLM agents?

  3. Can the authors test the hierarchical-search prediction dc∝Td_c \propto T, ideally alongside a factorizable task with matched parameters, to validate the taxonomy's central contrast?

  4. In the free-communication policies, how often does "sent nothing" reflect a failed or malformed tool call rather than a deliberate choice? How do results change if the prompt does not explicitly permit withholding or misreporting?

1 comment

We thank the reviewer for the thoughtful comments. Reviewer 6oCr notes that “the question [...] is important and timely” and “the LLM behavioral findings are interesting and potentially useful”. We address specific comments and questions below.


W1 & Q2 address the result that higher reasoning effort leads to higher dcd_c while increasing the fraction of agents that solve the task, suggesting that incorrect-lineage reproduction rate is not a reliable proxy for performance with LLM agents.

Given that higher reasoning effort increases both dcd_c and the fraction of agents solving the task (Fig. 12), in what sense does dcd_c predict search success for LLM agents?

Response: A search succeeds when any agent discovers the target, which is distinct from the fraction of agents that discover the target. In the case of increased reasoning effort, the overall search success rate is still low for communication degrees below dcd_c, but one agent succeeding seems to correlate with many agents succeeding. This makes some intuitive sense, as agents become more capable with increased reasoning ability and develop similar search strategies. Furthermore, more agents succeeding could signal a suboptimal search strategy. Instead of dividing and conquering, agents are herding towards the same region, which might lead to lower success rate if agents herd towards unproductive regions of the hypothesis tree. We thank the reviewer for this comment and have edited Section 5.2 to make this distinction more clear.


W2 & Q3 address the other search types in our taxonomy.

Can the authors test the hierarchical-search prediction dc∝Td_c \propto T , ideally alongside a factorizable task with matched parameters, to validate the taxonomy's central contrast?

Response: During the rebuttal period, we added a hierarchical search-based empirical experiment with deterministic and LLM agents. In both deterministic and LLM experiments, we measure dcd_c values that agree very well with theory (R2=0.999 for deterministic and R2=0.993 for GPT-5.4-nano, Figure 18). We consider a network fault-localization task derived from the topology and fault types used in NetOpsBench [1]. Exactly one fault is injected at a hidden physical location, and the hypothesis space is organized hierarchically. A hypothesis hth_t at depth tt represents a physical network region that may contain the root cause. The root hypothesis contains the entire network, and refinement recursively divides a region into smaller subregions. Further details can be found in Appendix D.3.

[1] https://github.com/NetX-lab/NetOpsBench


Q1: With the stated parameters (b = 2, m = 1), Eq. (8) gives d꜀ ≈ 5.55 for the toy and physics tasks (|L| = 16, T = 4) and d꜀ ≈ 10.63 for TCAS (|L| = 46, T = 6). The exact-log form of Eq. (5) gives 5.13 and 10.20. Table 2 reports 6.10 and 10.90.

Response: The dcd_c values reported in Table 2 are computed from a delayed communication variant of Equation 5. Agents don’t communicate for the first round, since they have not yet proposed any hypotheses. This change simply starts the sum at t=2 rather than t=1. We thank the reviewer for pointing this out and have now updated Equation 5 to reflect this, and added text in the description of Table 2 to point to Equation 5.


Q1: The literal count for TCAS also seems inconsistent: Section 4.2 states |L| = 46, while the parameter cardinalities in Appendix B.2 (seven binary, two ternary, one four-valued, two ten-valued) sum to 44. Could the authors specify how they computed these values and why there could be a discrepancy?

Response: The experiments use the 46-literal parameterization (five binary, four ternary, one four-valued, and two ten-valued parameters). The parameters reported in Appendix B.2 were a mistake. We thank the reviewer for pointing this out. We have corrected Appendix B.2 to match the parameterization used in the experiments.


Q4 In the free-communication policies, how often does “sent nothing” reflect a failed or malformed tool call rather than a deliberate choice?

Response: The observed “sent nothing” cases reflect the actual communication behavior of the LLM agents rather than failed or malformed tool calls. We recorded some fine-grained detail about the agents’ communication contents and accuracy of experimental observations in Table 3.


Q4: How do results change if the prompt does not explicitly permit withholding or misreporting?

Response: Our Team-Auto experimental setup (described in Table 1) automatically reports all experimental results to all of an agent’s neighbors. As the results in Table 2 show, Team-Auto almost always has the lowest dcd_c value, which we attribute to the consistency and accuracy of the inter-agent communication.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.