- 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- candidate need not contain incorrect literals. Under a negative-evidence-only membership interface, a candidate with incorrect literals has pruning probability 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 support the proposed depth-based approximation?
- Can controlled interventions on reporting and experiment duplication isolate the suggested mechanisms?
3 comments
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!
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
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>dc (right of the vertical line that indicates dc for each LLM policy), showing that search success is well predicted by dc. 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
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 qt follows a roughly linear relationship with t/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
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 dc, 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
The dc 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.