Benefits and Limitations of Communication in Multi-Agent Reasoning
Authors: Michael Rizvi-Martel
Satwik Bhattamishra
Neil Rathi
Guillaume Rabusseau
Michael Hahn
Venue: ICLR 2026 Poster (2026)
Keywords: chain-of-thought prompting
multi-agent systems
reasoning
expressivity
inter-agent communication
scalability
large language models
algorithmic analysis
Primary area: learning theory
TL;DR: We introduce a theoretical framework for analyzing the expressivity of multi-agent reasoning systems, derive tradeoffs between agent count, communication, and scalability, and validate our predictions with controlled LLM experiments.

Abstract: Chain-of-thought prompting has popularized step-by-step reasoning in large language models, yet model performance still degrades as problem complexity and context length grow. By decomposing difficult tasks with long contexts into shorter, manageable ones, recent multi-agent paradigms offer a promising near-term solution to this problem. However, the fundamental capacities of such systems are poorly understood. In this work, we propose a theoretical framework to analyze the expressivity of multi-agent systems. We apply our framework to three algorithmic families: state tracking, recall, and $k$-hop reasoning. We derive bounds on (i) the number of agents required to solve the task exactly, (ii) the quantity and structure of inter-agent communication, and (iii) the achievable speedups as problem size and context scale. Our results identify regimes where communication is provably beneficial, delineate tradeoffs between agent count and bandwidth, and expose intrinsic limitations when either resource is constrained. We complement our theoretical analysis with a set of experiments on pretrained LLMs using controlled synthetic benchmarks. Empirical outcomes confirm the tradeoffs between key quantities predicted by our theory. Collectively, our analysis offers principled guidance for designing scalable multi-agent reasoning systems.

Published as a conference paper at ICLR 2026
BENEFITS AND LIMITATIONS OF COMMUNICATION IN MULTI-AGENT REASONING
Michael Rizvi-Martel Satwik Bhattamishra
Neil Rathi
Guillaume Rabusseau'
Michael Hahn
Mila & Université de Montréal
Unniversity of Oxford
Stanford University
"Saarland University
ABSTRACT
Chain-of-thought prompting has popularized step-by-step reasoning in large lan- guage models, yet model performance still degrades as problem complexity and context length grow. By decomposing difficult tasks with long contexts into shorter, manageable ones, recent multi-agent paradigms offer promising near- term solution to this problem. However, the fundamental capacities of such sys- tems are poorly understood. In this work, we propose theoretical framework to analyze the expressivity of multi-agent systems. We apply our framework to three algorithmic families: state tracking, recall, and k-hop reasoning. We derive bounds on (i) the number of agents required to solve the task exactly, (ii) the quan- tity and structure of inter-agent communication, and (iii) the achievable speedups problem size and context scale. Our results identify regimes where communi- cation is provably beneficial, delineate tradeoffs between agent count and band- width, and expose intrinsic limitations when either resource is constrained. We complement our theoretical analysis with a set of experiments on pretrained LLMs using controlled synthetic benchmarks. Empirical outcomes confirm the tradeoff's between key quantities predicted by our theory. Collectively, our analysis offers principled guidance for designing scalable multi-agent reasoning systems.
INTRODUCTION
Chain-of-thougle (CoT) prompting has become the de facto standard for tackling complex reasoning problems. By encouraging models to "think step-by-step", CoT significantly improves performance on tasks requiring mathematical and logical reasoning (Wei al., 2022). Building on this, recent approaches view reasoning as structured traversal over thoughts, exploring methods such as self- consistency (Wang et al. 2022), tree-of-thought (Yao al., 2023). and stream-of-seane (Gandhi et al., 2024). In parallel, post-training for large reasoning models (LRMs) increasingly relies on reinforcement learning over generated CoTs (OpenAl 2025 Guo et al. 2025).
Despite these advances, several limitations have emerged. The reasoning abilities of LRMs degrade as the complexity of problem instances increases or as the context length grows (Shojaee et al,) 2025 (Sun et al.) 2025). To address this, new approaches based on multi-agent collaboration (e.g., Zhang et al. 2024b; Tran et al. 20255) Xiao et al. 20255 Hsu et al. (025)) decompose complex tasks into simpler subproblems, coordinating multiple agents to achieve stronger performance. These frameworks offer promising near-term solutions, yet the theoretical underpinnings of their expres- sive capacity remain poorly understood. While the expressive power of Transformers with CoT prompting has been studied in depth (Merrill & Sabharwal] [2233 (2023 Amiri et al. 2025), little is known about the fundamental limits and tradeoff's of communication and resource allocation in multi-agent reasoning schemes. This gap motivates the central question of our work:
From an algorithmic perspective, are there tasks that provably benefit from communication and dynamic resource allocation in multi-agent reasoning systems?
We address this question by proposing theoretical framework for analyzing the expressivity of collaborative multi-agent reasoning strategies. Our analysis applies to settings where both problem
"Corresoonding author. Contact: mi chael rizvi -martel @mi quebec

---

Published as a conference paper at ICLR 2026
complexity and context size scale, and focuses three representative algorithmic families: state tracking, recall, and k-hop reasoning. For each task family, we establish bounds on the number of agents and the quantity of communication required, and we characterize the tradcoffss between these quantities. Finally, we complement our theoretical results with empirical validation using pretrained large language models. Our contributions are as follows:
We propose formalization of multi- auulti-agent reasoning systems grounded in the rich literature on Transformer expressivity.
For three distinct families of algorithmic tasks-recall, state tracking and k-hop reasoning-we derive bounds the number of agents and the communication required, highlighting the tradeoff's between these resources. These tasks capture key aspects of practical reasoning problems, making the results broadly applicable.
We provide empirical validation of our theoretical insights by implementing the optimal communication protocols given by theory. Our analysis shows the performance in terms of accuracy, communication and token usage closely aligns with theoretical predictions.
Our work focuses on Transformer-basee multi-agent systems which partition an input of size N equally between w agents, an abstraction of many settings where multiple agents cooperate by taking responsibility for different parts of the input, such as different document chunks in long-context summarization or question answering, corpus shards or knowledge-grast graph subgraphs multi-agent RAG, web pages or site sections in browser-style agents, and map-reduce pipelines where workers process disjoint partitions before a coordinator aggregates the partial results (c.g.. Zhou et al. 2025
Chang et al. 2025 Zhang al. [002aa] Guo et al. Salve et al. 2024 Yang et al. 2025b Xiao
ct al.
2025
Liu et al. 2025 Xu et al. 2025).
Our results reveal three distinct regimes for multi-agen tasks, each instantiated by natural tasks of broad relevance (Table []. First, some tasks require almost no communication overhead even when the input is partitioned between agents, such key-query retrieval. Second, some tasks not only allow partitioning but also benefit from it, achieving reduced wall-clock time compared to a single- agent setup; state tracking is prime example. Finally, some tasks can be solved through partitioning but require significant communication among agents, such as reasoning over multiple hops.
Size
Depth
Communication
Associative recall
((w)
((1)
(1)
State tracking
+ (NN)
( + log
ww)
k-hop reasoning
woo)
((k) (kk) (when w >
Table 1: Summary of results. w denotes the number of agents. N represents the length of the input. Size corresponds to total computation. Depth loosely corresponds wall-clock time. Communica- tion refers to the overall amount of communication between agents. We will define these formally in Section 3 (-) indicates existence of protocol; (-)) indicates that we prove it optimal.
2 MODEL OF TRANSFORMERS
We assume causally masked (decoder-only) unique hard attention Transformers (UHAT) (c.g.. Hahn
2020
Hao et al., 2022 Yang al.) 2024a Amiri al. 2025 Jerad et al. 2025a Bergsträßer al. 2024 a popular abstraction where attention heads concentrate attention on the position maximizing the attention score. Some work suggest that pretrained models concentrate their attention on only few positions VVoita et al. 2019 Clark et al. 2019). Importantly, UHAT subsumes expressivity of ordinary softmax Transformers with fixed precision (Jerad al. 2025a), making a plausible model of Transformers in the regime of long contexts and large reasoning problems (see Appendix D].
Each layer of Transformer has attention block followed by MLP block. The attention block takes as input X E Nxd and applies the operation Au(X) = f*"(XW Q W [ X)WV where We, WK, Wy E Bdxm and (-) = UHAT(.), where for any matrix A E NxM.
[ if = arg max Ai, else
UHAT(A)), =
(1)
2

---

Published as a conference paper at ICLR 2026
where in case of a tie, the rightmost element is selected. Multi-heas attention with H heads is defined
as y (X) = [Att (X) ( Att [X) where each Att, (X) has its own set of parameters. The matrix W o E Im xd projects the concatenated vector to vector of dimension d. For input X E NR xd the output of Transformer layer is (M (X)) ) E R xx where ub : Rd + TRd
corresponds the function computed by the MLP. The model has access to arbitrary positional embedding vectors Pj E IR_ for each i E [Nmazz] where Nma is the model's context window and [NN [Nmas] denotes {I,..., Nmaw
3 FORMALIZATION OF MULTI-AGENT SYSTEMS
We formalize multi-agent systems as graphs. with node representing an agent given timestep. and edges describing both the emission of CoT tokens, and communication between different agents. We discuss connections to applied systems Section 3.1 and illustrate the definition in Figure
Definition 3.1 (Multi-agent system). Let E be (finite or infinite) input alphabet and E E an the task, we're allowing both input and
(infinite) CoT alphabet. For broad generality, depending CoT alphabets to grow with the input length, such that Σn C Σ2 C ... C and E| C E2 C
E, where [x |x & (ppoly(N)). We write the set of input strings as S = UN (Ex)*. We reserve agent identifiers ID,,.... ID Ex.
A multi-agent system A maps strings x E S to labeled DAGs A(x) with w(x) < | agents where:
1. Each node is uniquely labeled as (1)), where i E [w(x)] and E N. Informally, it represents agent i's state time For each agent i E [w]x)]] there is D; N such that there are nodes T( exactly for t E [D:] and for no other f.
2. We define two types of edges:
(a) communication edges {c,o} (a E E from T: to (-(++) which represent com- municating symbol between two different agents (i 4)
(b) CoT' edges {a.o} (a E E/a)), which correspond to autoregressive decoding of the model from ( to T:((-1)
3. Every node T7(*) (4 1) has exactly one incoming edge.
4. Every node " can have (i) no outgoing edge, (ii) one outgoing edge, (ii) outgoing edges edge with the same label {c. o each other agent, j * i.
5. One agent E [w(x)] is designated as a manager agent.
By definition, agents can only send or receive single token E E at a time Every agent can only receive one incoming edge at time. Intuitively, the symbol provided by the incoming edge at time t (whether it is CoT communication edge) is appended the agent's context at this time step.
Definition 3.2 (Complexity of Multi-Agon System). We use the following notions to characterize the complexity of multi-agent system:
Computation depth is the length of the longest path in the graph, irrespective of edge type. We write Depth(N) for the maximum depth on any input æ of size | < N. Computation depth is a proxy for the wall-clock time.
the number of agents in the system. Typically we use w(N) when the number of agents is function of input length. As the input is partitioned into chunks of size N/w, we consider w(N) [N].
Width of the graph corresponds
Size corresponds to the number of nodes in the graph. We write Size(N) for the maximum size on any input of size N.
Communication budget is the number of nodes with an outgoing communication edge.
We say multi-agent system A computes function f S Σ if for all E S, the last CoT edge of the manager agent A(x) has the label f(x) E.
An extension to words of bounded length ESC would be straightforward, but we find it casiest to formalize the setup with single-token messages. Our theoretical results hold irrespective of this choice (App.
3

---

Published as a conference paper at ICLR 2026
10
01
00
fnendpjje
Z
4:C, 8:A 7:?
6:E, 1:H 7:2
7:D. 2:X 7:2
7
Z
Z
frienkai
Griendaa
71
ZJ
Answer: D
Answer: 0 (h) Example of a prefix sum protocol for state tracking (Sec. [4.3) input 11100100. Here T2 termediate managers composing to- gether the answers of 71 and T3 with their own. T4 also acts the final manager, providing the final output.
Anower
(a) Graphical representation of recall protocol (Sec. (Sec.F.22) Th, and T3 are worker agents given chunks of 2 key-value pairs. Only Ta has the query in its context and thus communicates the answer the manager Thr after reasoning.
(c) Example of the Iterative Query protocol (Sec. (.4)). Each agent holds one fact. The full query, friend(boss(t)), is man- aged by T2, which receives an- swers at = 3, and broadcasts followup queries at 2, 4.
act in-
Figure I: Graphical representations of the protocols analyzed Section
Definition 3.3 (Agent computation). Given multi-agent system A(x) on input x E S, for each agent E [w)))), we construct a string {(i) E (= Intuitively, this is the sequence of tokens that is processed by this agent over the course of reasoning. The string {(i) is constructed as follows:
1. First, take the input chunk 2 [1])- I.. [[a]]] 1+1
E
2. Then append ID; E E|m]
3. Then traverse the nodes associated to the agent, T
TT(
(a) If there is an incoming communication edge {c, r) append the token RECEIVE_.r
(b) there is an outgoing CoT edge {a, r). append the symbol o..
(c) If there is an outgoing communication edge,
i. Either the message is sent a single agent in this case, append the token SEND ID, or,
ii the message is broadcast to all agents, append the token BROADCAST a.
4. We append the EOS symbol.
We assume all tokens to be part of E| Transformer' T implements A(x) on input x E S if and only if each these strings (i) fits into the Transformer's context size, and the transformer predicts all tokens arising from outgoing edges and EOS (cases 3b,3c,4) when autoregressively on {(t)-
Intuitively, each reasoning step, the transformer generates the next token, unless overridden by incoming communication.
A protocol A is expressible in UHAT if, for each input length n, there is a UHAT Transformer T, implementing A(x) each input with length |ar| n, and the number of heads and layers uniformly bounded across all Transformers T₃,- We do not require the width to stay bounded; e.g.,
growing width can allow positional encodings keep unboundedly many positions distinct.
The above generalizes the setup of Amiri al. (225 to the multi-agent setup. Requiring the system to be implemented by models with bounded layers and heads across input lengths is a very weak assumption, much weaker than the uniformity of the Transformer across input lengths often required in theoretical work on CoT (e.g.. Pérez et al.) 2019; Merrill & Sabharwal 2023 nonetheless, it allows us prove essentially matching upper and lower bounds on the cost of multi-agent systems.
We assume single tokens for simplicity; they could be bounded-length words without change to results.

---

Published as a conference paper at ICLR 2026
3.1 CONNECTION TO APPLIED WORKS
Our formalization covers a broad range of LLM-based protocols which (i) split long contexts into non-overlapping chunks, (ii) process these chunks in parallel with worker agents, (ii) re- lay info to manager to generate the final answer. The primary distinctions lie in coordination: CoA (Zhng et al. 2024b), L.MMxMapeduuce (Zhou et al.
2025). NexusSum (Kim & Kim
2025 run workers in parallel with 2025 AgentSimp (Fang et al. 2025), and Multi (Cao et al.
minimal communication, whereas LongAgent (Zhao et al., 2024). XpandA (Xiao et al., 2025).
AgentGroupChat-V2 (Gu et al.) ).25), and certain task-specific pipelines (e.g., DocAgent (Yang
itt al., 2025a), Multi-Agent QG (Wang et al. 2025a)) support targeted message- communica- tion resolve conflicts. Each of these approaches be described by communication graph as in Figure | Notably, all of these implement communication using messages written to the recipient agent's context, consistent with our framework.
RESULTS
4.1 GENERAL RESULTS: THREE REGIMES FOR DEPTII AND COMMUNICATION
In this section, we present theoretical results which hold for all tasks and all multi-agent systems which follow from Definition 3.1 Throughout, by "multi-agent systems", we always refer to sys- tems computed by Transformers. The first result we present relates to the size of the system:
Proposition 4.1 (Conservation of size). Any protocol can be converted into an equivalent single- agent protocol with the same size up constant factor.
The proof idea is to construct a single agent that alternates between simulating each of the agents of the original protocol, see Appendix CC.2 Thus, the size of the protocol cannot be reduced using multiple agents beyond constant factor. However, will see that it may increase in some tasks with the number of agents. In a multi-agent protocol, two other key determinants of cost are (i) depth, and (ii) communication budget. There are fundamental priori considerations about these quantities. First, any protocol as defined in Definition 3.1 satisfies the inequality:
Size(N) ((N) < (Dept((N)
(2)
Proof. The size is upper-bounded by the number agents times the maximum number of nodes assigned to any individual agent, which is upper-bounded by the maximum length of any path. O
This inequality might lead one to hope that multi-agent protocols reduce depth even if size cannot be reduced. We show that such gain in depth is realizable in some tasks (Section 4.3) but there are other tasks where no asymptotic gain in depth is possible (Section 4.4). A second fundamental observation is that reduction in depth due multi-agent reasoning is only possible at an increase in communication. In fact, any task solvable at bounded communication cost can already be solved at bounded depth by a single agent, ruling out gains in depth from multi-agent setup:
Proposition 4.2. Consider a task with a aaeti- system whose communication budget O()) in N across all w E [N]. Then this task has single-agent CoT with depth (and hence size) O11).
See proof in Appendix C.2 Taken together, this leaves us with three distinct feasible regimes of multi multi-agent reasoning (Table 2). The first one (Section 4.2) is where both depth and communication are ((1) as the number of agents increases. In this setting, multi-agent setups simply enable processing larger contexts, with- out associated cost. The second regime (Section 4.3) is where depth can be reduced by using more agents (almost up to (2)) though at the cost of increased com- munication. That is, there is a depth--commuicattion tradeoff. The third regime (Section 4.4) is where, at
Communication
Depth
O(1)
increases
~Size/w
impossible
Section
No Gain
Section 4.2
Section
4.4
Figure 2: Three possible and one im- possible regimes for depth-commmuicatiio tradeoffs.
5

---

Published as a conference paper at ICLR 2026
least in the worst case, multi-agent setups require large amount of communication, without reduc- tion to the required depth. In this regime, multi-agent setups allow processing larger contexts, with high cost of communication and no reduction in depth. A seeming fourth regime, where commu- nication stays ((1) but depth decreases as (2), is impossible by Proposition 4.2 Importantly, we will next demonstrate that all three regimes are instantiated by naturalistic tasks.
4.2 ASSOCIATIVE RECALL
The first task we consider is simple, associative recall. In this setup, given multiple key value pairs, and a queried key, agents must return the associated value. In this case, multi-agent setups permit processing a larger input without associated cost in communication or depth:
Proposition 4.3. Given an imput consisting of N pairs (2i,y;) E Σn Σn, and query 3. consider the lask of retrieving the (unique) y such that (æ, y) appears in the imput. Assume that the inpul is partitioned disjointly into parts provided agents, which also have access the query. Then they can solve the task with depth (1) and commumication (1)).
Sketch of proof (Full proof in Appendix appears in the input, and uses an induction head to retrieve the associated y if it appears. By design, only one agent will find such a y; it then reports designated manager agent that outputs y. D
Each agent attention to check if the query
Tradeoffss for Simple Retrieval
Computation depth (())
Number of agents wxNN and chunk size: NN w(N)
Communication budget ((1)
4. Size: Oww(N)
is both realizable and optimal for retrieval.
4.3 STATE TRACKING
Another foundational task is state tracking. State tracking is at the heart of many reasoning problems, such as tracking chess moves in source-target notation, evaluating Python code, or entity tracking (Kim & Schuster) 2023 Merrill et al. 2024). State tracking can be conveniently formalized in terms of evaluation over finite monoids (e.g.. Merrill et al. 2024 Grazzi et al. 2025):
Definition 4.1 (State tracking problem). Let M be finite set, and (M, finite monoid (M with an identity element and associativity). state tracking problem on M is defined as sending a sequence mgmm1 ... my M to mg mi my E M. Here, the input alphabet is Σ M.
Elements of the monoid represent operations (e.g., list manipulation instructions in Python or chess moves). Composing them leads to new monoid elements (e.g., compositions of instructions, or a sequence of chess moves). This problem class subsumes deciding membership for all regular languages, such as PARITY, which corresponds showed that PARITY requires a CoT of length ((N). Can a multi-agent system with a large amount of total communication do better? In terms of the size of the graph, this cannot be the case:
the monoid (f0, 1}, @). Amiri et al. (2025)
Proposition 4.4. Any multi-agent system computing PARITY requires size ((N).
The proof is in Appendix C.4 However, if we consider a parallel computation budget, can obtain a speedup in the depth of the computation graph. We assume the setup where each agent receives a disjoint contiguous substring of the input. Then:
Proposition 4.5. Let M be finite monoid. There exists a communication protooto with w(N) = N, depth (log N) computing the state tracking for M.
The key idea for this protocol is compute the prefix sum (or recursive parallel scan) algorithm with the LLM agents, as shown in Figure [[c] The above protocol has width of N agents, but it can be generalized other widths given by some function (NN) of the input size N:
Proposition 4.6. Given a finite monoid M and any number of agents (w N + N with w(N) e [N],, there exists a (log w(N) + w(N5) depth and (NN) size multi-agent system computing state tracking M with communication budget woN)..
N

---

Published as a conference paper at ICLR 2026
This means that given enough parallel computation budget, we indeed recover speedup in terms of effective or wall-clock time. The proof for this result given in Appendix C.4, Proposition 4.5 is corollary. The above result is essentially optimal, in that essentially shorter depth is attainable:
Proposition 4.7 (Optimality, see App- C.4 for proof). Assume the finite monoid M is a nontriv- ial group, and A a mulli-agent system computing state tracking over M. Then A has (Ww(N)) communication budget, and computation depth Q2 ((N)
We summarize our results for state tracking below:
Tradeoffss for State Tracking Assume w(N) E [M] agents, each provided a disjoint contiguous portion of the input. Then
1. Computation depth O (log wr( N
w(N] 2. Number of agents: w(N) and chunk size: w[N]
N
Communication budget (ww(N)
4. Size: N
are realizable for performing state tracking. Communication budget and size are optimal. Com- putation depth is optimal at least up to (log w(N)).
4.4 MULTI-HOP REASONING
We instantiate the third regime with k-hop reasoning (e.g.. Yang et al., 2024b Wang al. 2025b Yao et al., 2025). this task, we have domain D of objects and vocabulary J, intended to denote functions. We have set of N facts f(x) y (f. y E 2n) contextually given, where for each and f at most one such fact included. Each agent receives a disjoint equal sized partition of the set of facts, and a common query of the form fi (fa(z)) where fi F, D. The overall
size of the input is N + k; each agent has N. facts and the k-hop query.
Proposition 4.8. Let the number of agents be w N + N (w(N) E [N]). The k-hop composition task with N facts can be solved with computation depth Okk). communication budget Okk), and size Oww(N) k). The communication budget is optimal. The computation depth O(k) is optimal least up to a log(N (N + factor.
The idea is that worker agents perform an iterative lookup, where each agent tries to find the next answer in the own context, with one step for each of the hops [z). fee- (f) .... (.... (fi(()))...) ...). The regime of this task is different from the previous ones; in the worst case, there is no reduction of computation depth when increasing the number of agents: Depending on how the facts distributed among the agents, computation depth and communication budget may be P(k) in the worst case, as long as more than one agent are involved. The intuition here that the relevant facts can be distributed between different agents, making iterative lookup the optimal strategy. We thus have;
The proof is in Section C.5
Tradeoff's for k-hop Composition for h-hopp composition and facts, when w(k) >
1. Computation depth (kk)
2. Number of agents: w(k) and chunk size: w(k)
Communication budget O(k)
4. Size: O(wk)
are realizable for k-hop composition. Communication budget is optimal. Computation depth is optimal least up log(N + k) factor.
EXPERIMENTAL VALIDATION
In this section, we experimentally validate whether the protocols of Section 4 work in practice and
computation depth and communication exhibit the three predicted regimes. We evaluate Llama-3.3- 70B-Instruct- Turbo and 1-8-a-...-B---Ittttme Turbo (results in Appendix F on associative recall, state tracking and k-hop reasoning tasks in order empirically validate each of the three regimes

---

Published as a conference paper at ICLR 2026
analyzed in theory. We employ pretrained LLMs which are prompted with their roles in the protocol and the instructions to solve the task. We use hard coded communication protocols similar to the protocol implementation of ZZaag et al. (2024b). For more details please refer to Section E
5.1 RECALL
We validate experimentally the abilities of different multi-agent systems to perform associative call using the needle-in-a-haystacc test (Kamradt) 2024). This task involves finding a "needle" (an answer some query) in large document (the "haystack"), We self-consistency with majority voting WWang et al., 2022) as our baseline and use an implementation of Chain-of-Agent (CoA) for the optimal protocol, given its similarity.
Nendle Degth dirsugg, deciment
Modle Dopth thruugh deoamoo
Campatadinn Trythh
LCS
EX
4000
50.00
175.0
1900
3000
Contort Length (words)
Contect Length (words)
Chank Siae (oumde)
(a) Heatmap of accuracy vs needle depths and context lengths for Major- ity Voting. Performance degrades for large contexts.
(b) Heatmap of accuracy vs needle depths and context lengths for CoA. Performance remains constant across context size.
(c) Token usage for CoA. Usage remains constant across chunk size and con- length, which is con- sequent with our theory.
Figure 3: Results for the needle-n--ahhaystack test.
Needle-in----hasstac Figure 3 shows the performance of both Majority Voting and CoA across needle depth (how far in the corpus the needle is) as well context length. As it can be seen across Figure 3(a) Majority Voting degrades in performance as sequence length increases. We also slightly problematic; Majority Voting also fails when needle is the beginning or end of the corpus. CoA does not suffer from such degradation: the "divide-and- conquer" strategy of the protocol makes the task more manageable.
note also that extremities
5.2 STATE TRACKING
We next experimentally evaluate aueti-agent systems on state tracking tasks. We evaluate models on PARITY i.c., determining if the number of Is in a bitstring is even or odd.
1.0
0.8
1800
64
Accuracy
Consatatiin Degth
125
0.6
1500
0.4
1200
0.2
800
0.0
128
512
500
Sequence Length
Profo
Total Communicaaion (Edlges)
(a) Llama-70B accuracy on PARITY for dif- ferent sequence lengths. Prefix Sum repre- sents the theoretically optimal communica- tion protocol.
(b) Computation depth against the total amount of com- munication used. This trend is consistent with the N (Nw(N) computation depth vs w(N) total communi- cation tradcoff predicted Section 4.3
Figure 4: Empirical validation for PARITY.
8

---

Published as a conference paper at ICLR 2026
Maady
Computation Depth
5% boll
Accutracy
Accuracy
Number Hops
Numbeer Hops
Number Hops
(a) Accuracy number of hops the query for 100 facts. Iterative Query outper- forms Majority Voting baseline as number of hops increases.
(b) Accuracy number of hops the query for 500 facts, The difference performance is more pronounced in this regime.
(c) Computation depth number of hops the query. Computation depth shows an increasing trend as hop count increases.
Figure 5: Empirical validation for k-hop reasoning.
Figure 4(a) shows that Prefix Sum consistently outperforms all other methods, especially as se- quence length grows. Compared to Majority Voting, CoA degrades less with longer sequences, supporting our intuition that chunking complex reasoning into shorter parts helps. In terms of com- munication, Figure (bb) shows the tradeoff between the computation depth and the total amount of communication for Prefix Sum, calculated by summing the average token usage at every level. This trend is consequent with the theoretically predicted tradeoff's between communication and computa- tion. Indeed, in Section 4.3 we predict tradeoff between depth N N/w( //w(N) and total communication wNN). We note, however. slight increase in computational depth for high levels of communica- tion. This is due to poor instruction following; models add a constant token overhead by repeating the query and explaining the procedure, especially noticeable in high-communication regimes.
5.3 --HOP REASONING
Finally, we evaluate models k-hop reasoning task, where agents are given facts (e.g.. "Paula is the boss of Mary") and query (e.g., "Who the boss of the friend of George?"). Task difficulty protocols: Majority Voting and
depends the number of facts and query hops. We compare Iterative Query, an implementation of the protocol proved optimal in Section 4.4 As we can see in Figure Iterative Query generally outperforms Majority Voting. This trend is accentuated as the number of hops increases. We note that for the smallest number of hops (four), there are cases where Majority Voting outperforms Iterative Query; we posit that the probability of failing a given round seems to outweigh the difficulty of retrieving facts in larger corpus in this regime. Finally, we analyze how the computation depth varies function of number of hops the query. As can be seen in Figure 5(c) the trend we observe is consistent with theory; as depth of queries increases, so does the computation depth.
DISCUSSION AND CONCLUSION
In summary, our work provides principled foundations for understanding the algorithmic benefits and limitations of collaborative multi-agent systems. By formalizing communication and resource tradeoffs, we bridge theoretical analysis with empirical observations, shedding light when collab- oration enhances reasoning efficiency and when imposes inherent costs. These results open new avenues for designing reasoning systems that balance scalability, expressivity, and performance..
Relationship to celf-Consistency Our results show that multi-agent systems with sophisticated communication protocols outperform majority-vote strategies; Mirtaheri et al. (2025) find that self- consistency with polynomially many agents yields limited gains on tasks hard for Transformers. In Appendix(H we show separation result between optimal protocol and majority voting strategies. We give a short rundown of this result here. Informally, we define a majority voting strategy using set of (NN agents, each of which is the full input and terminates with single-token

---

Published as a conference paper at ICLR 2026
response; the overall system returns the most common response. Using this definition, show super-polynomial separation between majority voting and PrefixSum:
Proposition 6.1 (Informal). Consider a majority voting scheme with w(N) agents computing PAR- ITY over length-N inputs with a Co'I' length (or computation depth) of Oloog N). This scheme must have wNN) 22(N5) agents for some constant e > O.
In contrast, PrefixSum attains perfect accuracy with computation depth Oloo N) and w(N) = N. The proof of this statement as well in-depth discussion of its implications can be found in Appendix H
Implications for Protocol Design Our results characterize depth (wall-clock time) and communi- cation cost, identifying three regimes of multi-agent systems (Figure with implications for multi- agent LLM design. Systems with many workers and a single manager (e.g.. CoA Zhang et al. (2024b), LLMx (Zhou et al. 2025), NexusSum (Kim & Kim 2025), AgentSimp (Fang al. 2025). Multi? (Cao et al. 2025j) only shift the context bottleneck to the manager, risking errors when aggregating many responses. To address this, we propose prefix-sum stulstyle cascade: iterative summarization reduces the final-agent bottleneck. with branching factor and depth as tun- able hyperparameters. We also believe the Iterative Query protocol for k-hop reasoning could have practical relevance. For complex queries, a similar architecture may promising: a manager first decomposes the main query into subqueries, each processed through iterative worker-manager com- munication rounds, with the manager updating the query after every round
Relation to Parallel Computing Frameworks. Our setting is related to classic models of par- allel and cooperative computation: communication complexity, PRAM (Fortune Wyllie 1978), Massively Parallel Computation (Im al. (023). BSP (Valiant 1990), and LOCAL (Peleg 2000 Conceptually, our measures of Computation Depth and Size mirror Time (parallel steps) and Work (total operations) in PRAM. The key difference is that the Transformer architecture. This formalization leads to the sharp contrast between Associative Recall (Section 4.2 which Transformer can perform in one attention step, and State Tracking (Section 4.3) wh which is more challenging and requires an explicit multi-step reasoning chain. Other agent choices yield different predictions: multi-agent systems instantiated with recurrent networks would make retrieval harder (Bhattamishra et al.) [024] Arora et al.) 2023) and may enable more efficient state tracking than Transformers; unconstrained agents solve both tasks in constant time; and Turing machines or RAM models require linear time for both. Frameworks that treat agents as unconstrained processors (with memory/communicatoo for both tasks, while frameworks that model agents RAM-like units predict high depth. It is only by considering the capabilities of Transformers that we achieve a more fine-grained analysis appropriate to Masedd multi-agent systems, predicting tradeoffs realized by actual LLMs.
analysis relies on the expressivity of
as the main bottleneck) predict low depth
Limitations and Future Work There are many directions in which this work could be extended. Empirically, ideas discussed in the above paragraph could be incorporated into the design of novel multi-agent systems. Theoretically, our work could be extended to different algorithmic tasks e.g.. graph reachability to different multi-agent paradigms such as adversarial games cooperative reinforcement learning tasks, where agents collaborate to reach a common goal.
REPRODUCIBILITY STATEMENT
We provide complete reproducibility package to facilitate replication of our results. Code to reproduce all experiments can be found at htttps:// http://tttttbbco/o... ccom/michan mwchheeeichaiiiiiec coa-algorithmig Appendix E details the experimental setup, including the hyperparame- ters and parameter ranges considered, as well as all system prompts used. Complete proofs for all propositions presented the paper are included in Appendix C.2
REFERENCES
Alireza Amiri, Xinting Huang, Mark Rofin, and Michael Hahn. Lower bounds for chain-of- tf-thuught reasoning in hard-attention transformers. Forty-second International Conference on Machine Learning, 2025.
10

---

Published as a conference paper at ICLR 2026
Simran Arora, Sabri Eyuboglu, Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, and Christopher Ré. Zoology: Measuring and improving recall in efficient language mod- cls. arXiv preprint arXiv: 04927, 2023.
James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich. The expressive power of voting polynomials. In Proceedings of the twenty-third annual ACM symposium on Theory of Comput- ing. pp. 402-409, 1991.
Pascal BergsträBer, Chris Köcher, Anthony Widjaja Lin, and Georg Zetzsche. The power of hard attention transformers on data sequences: A formal language theoretic perspective. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:// openreview net/ forum? -ddNnqliii NBQqVmfP44 4m
Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations the repre- sentational capabilities of transformers and recurrent architectures. In The Thirly-eighth Annual Conference on Neural Information Processing Systems, 2024.
Juntai Cao, Xiang Zhang, Raymond Li, Chuyuan Li, Shafiq Joty, and Giuseppe Carenini. Multi Multi-agent test-time scalable framework for multi-document processing. preprrreprin arXiv:2502.20592, 2025. doi: 10.48550/a2xi.25522200 20592. URL https: httpp:://axxxv..r0 abs/2502.20599
Chia-Yuan Chang, Zhimeng Jiang, Vineeth Rakesh, Menghai Pan, Chin-Chia Michael Yeh, Guanchu Wang. Mingzhi Hu, Zhichao Xu, Yan Zheng, Mahashweta Das, and Na Zou. MAIN-RAG: Multi-agent filtering retrieval-augmeentd generation. In Wanxiang Che, Joyce Nabende, Fka- terina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2607-2622, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8-89176- 251-0. doi: 10. 00.18653/w1/2225.adll act- long. 131. URL
131/
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D Manning. What does BERT look at? an analysis of BERT's attention. arXiv preprint arXiv: 1906. 04341, 2019.
Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston. Chain-of-veriffcation reduces hallucination in large language models. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Findings of the Association for Com-
putational Linguistics: ACL 2024, pp. 3563-3578, Bangkok, Thailand, August 2024. Associ-
ation for Computational Linguistics. doi: 18.18653/v 1/252//1//222......11 1/2024 1/2024..nndnggs- wwwdiiins-acll222 ac1.212. URL https:
7/aclanthology. htwpchhhoooyyor//222244443 wtq/2024..2.... htt.://22....iiinnnoeeeeeeeeeece fwwdingsnnnnin
2127
Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. Improving
factuality and reasoning in language models through multiagent debate, 2023. URL https:
//axxiv.org/aalel 2300..///223.... 14325
Dengzhao Fang, Jipeng Qiang, Xiaoye Ouyang, Yi Zhu, Yunhao Yuan, and Yun Li. Collaborative document simplification using multi-agent systems. In Owen Rambow, Leo Wanner, Marianna Apidianaki, Hend Al-Khalifa, Barbara Di Eugenio, and Steven Schockaert (eds.), Proceedings of the 31st International Conference on Computational Linguistics, pp. 897- Abu Dhabi, UAE, January 2025. Association for Computational Linguistics. URL brg//022 co inng-miinnmi 60/
Steven Fortune and James Wyllie. Parallelism in random access machines. In Proceedings of the tenth annual ACM symposium on Theory of computing, pp. 114-118, 1978.
Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman. Stream of search (SOS): Learning to search in language. arXiv preprint arXiv:2404.03688, 2024.
Riccardo Grazzi, Julien Siems, Arber Zela. Jörg KH Franke, Frank Hutter, and Massimiliano Pon- til. Unlocking state-tracking in linear RNNs through negative eigenvalues. In The Thirteenth International Conference Learning Representations, 2025.
11

---

Published as a conference paper at ICLR 2026
Zhouhong Gu, Xiaoxuan Zhu, Yin Cai, Hao Shen, Xingzhou Chen, Qingyi Wang, Jialin Li, Xi- aoran Shi, Haoran Guo, Wenxuan Huang, Hongwei Feng, Yanghua Xiao, Zheyu Ye, Yao Hu, and Shaosheng Cao. AgentGroupChatt system need. arXiv preprint arXiv:2506. 15451, 2025. doi: 20.48550/rXi..2506.554444 URL htttps://arxiv.ore org. 2506. 15451
Divide-and -nd-cuquuer is what Iim-based multi-agent
Daya Guo, Dejian Yang. Haowei Zhang, Junxiao Song. Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi. et al. DeepSeek-RI: Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv preprint arXiv:2501./2448, 2025.
Tiezheng Guo, Chen Wang. Yanyi Liu, Jiawei Tang, Pan Li, Sai Xu, Qingwen Yang, Xianlin Gao, Zhi Li, and Yingyou Wen. Leveraging inter-chunk interactions for enhanced retrieval in large language model-based question answering. 2024. doi: 20.48550 02907. URL
https: //tr///axiii/ org abss///////// abaaaa/s//// 2408. 02907v1 Version v1.
Michael Hahn. Theoretical limitations of self attentotnn neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 1716-71,660 2020.
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? arXiv preprint arXiv:2402.09963 2024.
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800-810, 2022.
Chan-Jan Hsu, Davide Buffelli, Jamie McGowan, Feng-Ting Liao, Yi-Chang Chen, Sattar Vakili, and Da-shan Shiu. Group think: Multiple concurrent reasoning agents collaborating token level granularity. arXiv preprint 1xXi::5505.11000 2025.
Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, et al. Massively parallel computation: Algorithms and applications. Foundations and Trends@ in Optimization, (4):340-41) 417, 2023.
Selim Jerad, Anej Svete, Jiaoda Li, and Ryan Cotterell. Unique hard attention: A tale of two sides. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Computational Linguis- ties (Volume 2: Short Papers), pp. 977 996, Vienna, Austria, July 2025a. Association for Com- putational Linguistics. ISBN 979- 811-8888977--222
doi: 10. aal6:////22255..lshhoor acl.-sort........ 767]
URL
htttps://aclaantoo.oo wwg.:/ogyoooooooooooooooo
Selim Jerad, Anej Svete, Jiaoda Li, and Ryan Cotterell. Unique hard attention: A tale of two sides. arXiv preprint arXiv:2503. 14611 2025b.
William B Johnson, Joram Lindenstrauss, et al. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics, 26( 261189-206)., 1984.
Greg Kamradt. Limtest needleinahaysttack: Doing simple retrieval from LLM models at vari- ous context lengths to measure accuracy.
Needle PiteleTnAAee InnallyttHHaaacccc 2024.
Hyuntak Kim and Byung-Hare Hak Kim. NexusSum: Hierarchical LLM agents for long-form narrative summarization. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher
Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 101 10157, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8-89116-251-44 doi: 10. N0.18863/v 1/202/ acl-long.500. URL httphhtts:/// httttss://aaaaathlloottoo org. 2025 acl Saadlloong..o long.500/]
Najoung Kim and Sebastian Schuster. Entity tracking in language models.
arXiv preprint
arXiv:2305.02333, 2023.
Jiaoda Li and Ryan Cotterell. Characterizing the expressivity of fixed-precision transformer lan- guage models. In The niith Annual Conference on Neural Information Processing Systems, 2025. URL wtt.::ttp///tt htttss://operrviit wttp://wwwweeeeeeeeo...reeeee.e.
12

---

Published as a conference paper at ICLR 2026
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749, 2022.
Pei Liu, Xin Liu, Ruoyu Yao, Junming Liu, Siyuan Meng, Ding Wang, and Jun Ma. HM-RAG:
Hierarchical multi-agent multimodal retrieval augmented generation, 2025. URL https://
otg/ abs/ 1t////5511111.1 12330
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. arXiv preprint arXIv:2310.07923, 2023.
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. arXiv preprint 4rXiv:2404.08819, 2024.
Parsa Mirtaheri, Ezra Edelman, Samy Jelassi, Eran Malach, and Enric Boix-Adsera. Let think! A long chain-of-thought can be worth exponentially many short ones. arXiv preprint arXiv:2505.2 1825, 2025.
Phuong Nguyen and Stephen Cook. Theories for TCO and other small complexity classes. Logical Methods in Computer Science, 2, 2006.
Thang Nguyen, Peter Chin, and Yu- tu-Wing Tai. Ma-rag: Multi-agent retrieval- genera- tion collaborative chain of of-thoughtthh reasoning. arXiv preprint arXiv:2505.20090 20096, 2025. URL
petps://arrii. wrg.orggaao abs / http://.s.//.5....2 20096
OpenAl. OpenAI o3 and o4-mini System Francisco, CA, April 2025.
Card.
Technical
report, https: cdn.
OpenAI, San
URL
openai. 2eteeaalccoo////222211---0-0000 000------79--00-----77770-0--00-
833-nd-- 24 oo--oo--iiiii-- -an card. pard
PDF available online.
David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000.
Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. arXiv preprint arXiv: wrXiv:/901.04444 1901.9349, 2019.
Michael Rizvi-Martel, Maude Lizaire, Clara Lacroce, and Guillaume Rabusseau. Simulating weighted automata over sequences and trees with transformers. In International Conference Artificial Intelligence and Statistics, pp.
PMLR, 2024.
Aniruddha Salve, Saba Attar, Mahesh Deshmukh, Sayali Shivpuje, and Amab Mitra Utsab. A collaborative multi-agent approach to retrieval-augmmented generation across diverse data. 2024. doi: (0.485500aaXin2241255333 URL vl.
/btp/ 05838
Version
Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar. The illusion of thinking: Understanding the strengths and limitations of reasoning models via the lens of problem complexity. arXiv preprint arXiv:2506. 2644::,506606941, 2025.
Yiyou Sun, Shawn Hu, Georgia Zhou, Ken Zheng, Hannaneh Hajishirzi, Nouha Dziri, and Dawn Song. Omega: Can Ilms reason outside the box in math? evaluating exploratory, compositional, and transformative generalization. arXiv preprint arXiv:2506. 18880, 2025.
Pascal Tesson and Denis Thérien. Diamonds are forever: The variety DA. In Semigroups, algo- rithms, automata and languages, pp. 475-499. World Scientific, 2002.
Khanh-Tune Tung Tran, Dung Dao, Minh-Duong Nguyen, Quoc-Viee Viet Pham, Barry O'Sullivan, and Hoang D Nguyen. Multi-agent collaboration mechanisms: A survey of 1lms. arXiv preprint arXiv:2501.06322 06322, 2025.
Leslie Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8): 103-111, 1990.
Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir. Size and depth separation in ap- proximating benign functions with neural networks. In Conference on Learning Theory, pp- 4195-4223, PMLR, 2021.
13

---

Published as a conference paper at ICLR 2026
Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. arXiv preprint arXiv:1905.09418, 2019.
Haotian Wang, Xiyuan Du, Weijiang Yu, Qianglong Chen, Kun Zhu, Zheng Chu, Lian Yan, and Yi Guan. Learning to break: enowledge-enhanced reasoning in multi-agent debate system, 2024a. URL www.i.owg...aaaaooooooo
04854
Junlin Wang, Jue Wang, Ben Athiwaratkun, Ce Zhang, and James Zou. Mixture-of-agents large language model capabilities, 2024b. URL wtt.:https:/rrxxte wttp//o////////////o /tttt/////aaxi..oorr//////////// 04666004699
entnannneeeeeeenneee enhances
Kesen Wang, Daulet Toibazar, Abdulrahman Alfulayt, Abdulaziz S. Albadawi, Ranya A. Alka- htani, Asma A. Ibrahim, Haneen A. Alhomoud, Sherif Mohamed, and Pedro Moreno. Multi- agent interactive question generation framework for long document understanding. arXiv preprint arXiv:2507.20145, 2025a. doi: 10448550/axxi.25572201555 URL httts://arxiv.oKr
abs /2077 20145
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou, Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203. 2022.
Zixuan Wang, Eshaan Nichani, Alberto Bietti, Alex Damian, Daniel Hsu, Jason D) Lee, and Denny Wu. Learning compositional functions with transformers from easy-to-hard data. arXiv preprint arXiv:2505.23683, 2025b.
Jason Wei, Xuezhi Wang, Dale Schuurmans. Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thoughh prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824 24837, 2022.
Sibo Xiao, Zixin Lin, Wenyang Gao, and Yue Zhang. Long context scaling: Divide and conquer via multi-agent question-driven collaboration. arXiv preprint arXiv:2505. 20625, 2025.
Zhen Xu, Shang Zhu, Jue Wang, Junlin Wang, Ben Athiwaratkun, Chi Wang, James Zou, and Ce Zhang. When does divide and conquer work for long context Ilm? noise decomposi- tion framework. 2025, doi: 10.48550/a2Xiv.25566 16411. URL httph:tts//ee //arxiv.///xvvvv.//a org/ /
2506. 16411v1
Version vl.
Andy Yang, David Chiang, and Dana Angluin. Masked hard-attention transformers recognize ex- actly the star-free languages. The Thirty-eighth Annual Conference on Neural Information Pro- cessing Systems, 2024a. URL https::/openxxeveew
htt::/fommmm?/m BMsBdHOyz
Dayu Yang, Antoine Simoulin, Xin Qian, Xiaoyi Liu, Yuwei Cao, Zhaopu Teng, and Grey Yang- Docagent: A multi-agent system for automated code documentation generation. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 3: System Demonstrations), pp. 460-471, Vienna, Austria, 2025a. Association for Computational Linguis- tics. /LLAttps///ccaattoooos wwtp//ooo.ooooooooooooe org. /twpg/2222.2222 acl-demo. 44/
Ruiyi Yang, Hao Xue, Imran Razzak, Hakim Hacid, and Flora D. Salim. Divide by question, conquer by agent: Split-rag with question-driven graph partitioning. arXiv preprint arXiv:2505.1 13994, 2025b. doi: 10.48850/arxiv.2555..532 139944 URL
org/ abs /bs./505.... 2505//5955111
Sohee Yang, Nora Kassner, Elena Gribovskaya, Sebastian Riedel, and Mor Geva. Do large lan- guage models perform latent multi-hop reasoning without exploiting shortcuts? arXiv preprint arXiv:2411. 1.6.6699, 2024b.
Shunyu Yao. Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in neural information processing systems, 36: 1809-11822. 2023.
Yuekun Yao, Yupei Du, Dawei Zhu, Michael Hahn, and Alexander Koller. Language models can learn implicit multi-hop reasoning, but only if they have lots of training data. arXiv preprint arXiv:2505. 0t..22555.7793.... 2025.
14

---

Published as a conference paper at ICLR 2026
Yizhou Zhang, Lun Du, Defu Cao, Qiang Fu, and Yan Liu. Prompting large language models with divide-and-conquer program for discerning problem solving. 2024a. doi: 10.48550/u2Xiv.442.. 05359. URL hattps://azxiv/
abs /tss/24422 05359v3 Version v3.
Yusen Zhang, Ruoxi Sun, Yanfei Chen, Tomas Pfister, Rui Zhang, and Serean Arik. Chain of agents: Large language models collaborating on long-context tasks. Advances in Neural Information Processing Systems, 37:132208- 132237. 2024b.
Jun Zhao, Can Zu, Xu Hao, Yi Lu, Wei He, Yiwen Ding, Tao Gui, Qi Zhang, and Xuanjing Huang. LONGAGENT: Achieving question answering for 128k-token-long documents through multi-agent collaboration. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Pro- ceedings of the 2024 Conference Empirical Methods in Natural Language Processing, pp- 16324, Miami, Florida, USA, November 2024. Association for Computational Linguis- tics. doi: 12.18663/1112224cmmmppp. 912. httpttss:: //acl anthology....... ogg.0g//......
emn emm.p-mminn 912/
Zihan Zhou, Chong Li, Xinyi Chen, Shuo Wang. Yu Chao, Zhili Li, Haoyu Wang, Qi Shi. Zhixing Tan, Xu Han, Xiaodong Shi, Zhiyuan Liu, and Maosong Sun. LLMx MapReduee Simplified long-sequence processing using large language models. In Wanxiang Che, Joyce Nabende, Eka- terina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 11664-27678, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8-89176. 251-0. doi: 10. 10.18653/v1/2025 acl- long......... 1341. URL http://:///aaaaahhlllogss wrgp:y/.rrg2222 acl-long.
15

---

Published as a conference paper at ICLR 2026
APPENDIX
A Use of Large Language Models
16
Clarifications
16
Proofs
18
Notation
18
Proofs for General Results (Section 4.1)
19
Proof for Associative Recall (Section
19
Proofs for State Tracking results (Section
C,5
Proofs for k-hop Reasoning (Section 4.4)
23
Parity Error Analysis
25
Experimental Details
26
E.
Associative Recall Task
26
Parity Calculation Task
27
E.3
Ss Permutation Tracking Task
29
Hop Reasoning Task
E.5
Needle-in-a-haystac,
33
Additional Experiments
33
Recall
33
Parity
F3
S Permutations
34
k k-Hop Reasoning
35
Beyond Single-Token Communication
39
Comparison to self-consistency and voting approaches
39
Implications for Fixed Precision Transformers
40
A USE OF LARGE LANGUAGE MODELS
We used a large language model (GPT-5) in two ways during the research and writing of this paper. First, we used it refine phrasing and to provide revision suggestions on draft manuscripts. Second, we used it to conduct preliminary literature reviews of the field. Research ideas, proof, and empirical analysis were conducted by the authors.
B CLARIFICATIONS
(i) Similar work has already been done in the parallel computation and communication com- plexity literatures. What is the key difference here?
16

---

Published as a conference paper at ICLR 2026
Indeed, there are various frameworks for modeling parallel and cooperative computation
(such as communication complexity. Parallel RAM (Fortune & Wyllie, 1978). Massively Parallel Computation (Im et al. 2023), BSP//alins
(1990), LOCAL PPeeg 2000)). There are some conceptual similarities, for instance our analysis of Computation Depth and Size mirrors the concepts of Time (number of parallel steps) and Work (total operations across all processors) in the Parallel RAM model.
Our work differs in making essential use of arguments about the expressivity of the Trans- former architecture, and no prior framework would have enabled us to show the set of results in this paper. For instance, the very different behavior between Associative Re- call (Section (.2) and State Tracking (Section 4.3) builds on properties of the Transformer architecture: A Transformer performs retrieval in one step with attention, whereas state tracking is challenging unless a full reasoning chain is used. In contrast, if one instanti- ates a multi-agent system based on recurrent networks, then retrieval would be challeng- ing (Bhattamishra et al., 2024 Arora et al. 2023) and state-tracking could perhaps be done more efficiently than a Transformer-
system. An unconstrained agent performs both in constant time; a Turing machine or RAM needs a linear number of steps in both cases. Models based on unconstrained individual agents (with memory and communication as the primary bottleneck, as in PRAM) predict low computation depth in both tasks; models where individual agents are based on RAM (as in PRAM) predict similarly high depth in both tasks. It is only by considering the specifie abilities of Transformers that we achieve more detailed analysis appropriate to LLM-based multi-agent systems, predicting tradeoffs realized by actual LLMs.
(ii) What are the impacts/takeaways of the experimental results for practitioners?
The main objective of our experiments is to validate the theoretical claims we provide. To this end, we provide experimental results which corroborate token usage with theoretical predictions about computation depth. Moreover, we report accuracy and compare consistency baseline in order to illustrate that using the optimal protocol for a given task can also lead to performance gains. We stress that the implementation of the protocols we use is kept simple. Our work is an analysis paper, not a methods paper and thus its main aim is to better understand the interplay of agent count, token usage and communication in multi-agent systems. Refinement and engineering of the considered protocols is left for future work
self-
(iil)
What is the practical impact of the results? Do the results relate to any specific NLP tasks? RECALL, PARITY and k-hop reasoning are fundamental problems that serve as simple models of reasoning tasks and are of broad interest. RECALL has been shown by Arora et al.. (2023) play in important part in the impressive linguistic abilities of modern transformer- based LLMs. PARITY and other state tracking problems are of great interest as they are directly connected reasoning problems such code evaluation, entity tracking in lin- guistics and generally require some form of world modeling abilities (Merrill et al. [024] Kim & Schuster 2023 Rizvi-Martel al.) 2024). Moreover, PARITY is a prime example of a sensitive function, which have been shown to be difficult for Transformer models (Hahn
2020 Hahn & Rotin 2024). Finally, k-hop reasoning foundational to many aspects of reasoning involving the composition of multiple reasoning steps.
(iv) Why are there no experiments large reasoning models such as OpenAl-o3 DeepSeek- RI?
In the experiments, we typically prompt models to use a specific reasoning strategy for consistency. LRMs typically reason in the way they see best, not necessarily respecting the reasoning strategy given in the prompt. Moreover, using the Together API, such models typically reason using a large CoT which is hidden to the user, thus rendering it impossible to monitor the exact CoT used by the model.
Moreover, in many experiments, we evaluate token usage as a proxy for certain metrics e.g. computation depth. The long reasoning chains produced by these models make difficult to see any trends in the token usage as problem complexity increases.
Section 3 assumes that each agent only receive bounded communication each step. What about protocols where each agent can see each other agent's 's tokens, as in Group- Think (ssu et al. 2025
17

---

Published as a conference paper at ICLR 2026
One of our key aims here is to understand the cost of communication introduced in multi- agent setups and how it trades off with computation depth, which is easiest to do if we consider framework that explicitly counts each communication link. In contrast, this is not straightforward in scenarios where all agents have access to the same information.
It may possible to extend the current framework to protocols with unbounded communi- cation, but this would require careful consideration of what it would mean for transformers to access the contexts of all agents, and how to quantify the amount and cost of communica- tion in scenarios where, at least in principle, all agents have access to the same information.
(vi)
The paper assumes that the input is partitioned between agents. What about frameworks such as agett debates and voting. where multiple agents process the same input?
Indeed, various papers have proposed strategies where different agents process the same input and solve the problem through mechanisms such as debating or voting (Wang et al., 2022 Dhuliawala et al., 2024 Du al. 2023 Wang et al.] 2024b). An important special case is Self-Consistency (Wang et al. (0022). where agents solve a problem independently and vote at the end.
These techniques fall outside of the scope of our research, which focuses on the expressiv- ity of collaborative and multi-agent reasoning strategies. In contrast, these strategies funda- mentally leverage the inherent stochasticity of trained LLMS to reduce noise and overcome failures. However, these techniques do not increase the intrinsic expressivity of the multi- agent system (e.g., using multiple agents to solve the same state tracking problem and performing voting may reduce error rate, but does not increase the worst-case expressivity of the model.). We further take this up in Appendix H
(vii) Some of the protocols described in the theory seem quite intricate. Can the protocols described in the theory be linked to protocols from the applied literature?
Indeed, results provide rigorous foundation for certain approaches that have links to ideas from the applied literature. Related to the first regime in our theory (Section 4.2
in various studies, a single query is broadcast and worker agents each inspect only their local shard for an answer, returning a candidate and confidence to a lightweight aggrega- tor that selects or fuses the outputs (e.g.. (Zhou et al. 2025| Chang et al., 2025 Zhang ett al.] [222aa] Salve et al.) 20244 Yang et al. 2025b). In our second regime (Section 4.3
recursive aggregation is optimal; this again related to some existing approaches the ap- plied literature: agents iteratively compose partial states via tree-structured reduce/merge operators (c.g., parallel scan/prefix-sie
and divide-and-cn andidd-edd-conuerr.. so global answer is as- sembled from local summaries with shallow, c.g. logarithmic, communication depth (c.g.,
our third prove sequential, multi-hop handoffs optimal; this again links to approaches where the system must iteratively query different agents' shards in a back-and- forth chain-passing intermediate facts as state so communication depth scales with the
(Kim & Kim 2025 Zhou et al. 2025): Xiao et al., 2025] Xu et al., (0255).
regime (Section 1
hop count (e.g.. Yang et al. (2025b): Liu et al. (2025). ) Nguyen et al. (2025) : Wang et al.
(2024a)).
Importantly, our results rigorously clarify in which regimes such communication protocols are optimal. Simultaneously, as discussed in Section 6) our results show how, in a rigorous sense, such more sophisticated protocols may improve over simpler but popular strategies such as chain-of-agents or majority voting.
C PROOFS
C.I NOTATION
We denote with N, and IR the set of natural, integers and real numbers, respectively. We use bold letters for vectors (e.g. E Rd),, bold uppercase letters for matrices (e.g. M E Rd Xd2). All vectors considered are column vectors unless otherwise specified. The i-th row and the j-th column of matrix M are denoted by M,, and M. Let Σ be a fixed finite alphabet of symbols, Σ the set of all finite strings (words) with symbols in Σ and Σ" the set of all finite strings of length n. We use e to denote the empty string. Given p, E Σ*, denote with ps their concatenation.
18

---

Published as a conference paper at ICLR 2026
C.2 PROOFS FOR GENERAL RESULTS (SECTION 4.1
Proposition C.I (Conservation of size, repeated from Proposition 4.1). Any protocol can be con- verted into an equivalent single-agent protocol with the same size up to constant factor.
Proof. By constructing single agent that alternates between simulating each of the agents of the original protocol, computed by Transformer SingleAgeet-
Recall that all agents have the same Transformer parameters, MultiAgent-
We extend E with tokens (AgentID), one for each agent ID. We assume some fixed arbitrary ordering over all agent IDs.
The tokens of the reasoning chain record for each step which agent it is associated with. alter- natingly consists of (AgentID) ID) and (CoT/commun htcc/oomiiiaaa.cccmccmc........a cation token). Say, the even positions are the Toommuuuniaa tokens (the nodes the original chains); the odd positions are agent indices.
Now, the transformer SingleAgent alternates between two modes, depending on the position.
At an (Agent ID) position, the transformer knows from the input which agent to simulate. It then restrict attention to those tokens that are relevant to this agent, and otherwise performs the compu- tations done by Multiiggen. The top layer then outputs whatever MultiAgent would have output.
In the other mode, TiigglAggett needs to figure out which agent's turn next: the first agent in the ordering which is higher than the last agent but hasn't terminated yet. To achieve this, first retrieve the last agent's last previous turn, using a single attention head. Then find the first non- TERMINATE action succeeding that turn; this gives the agent whose turn it is. The transformer then outpts this agent's 's ID as the next token.
Proposition C.2 (Repeated from Proposition 4.2p. Consider task with a multi-agent system whose communication budget is (1) in N across all w E [N). Then this task has single-agent CoT with depth (and hence size) (1).
Proof. We take towards N, so that the chunk size becomes 1. Assume that the communication budget is O(1) in N across all w E [N]] Then we can find a protocol with communication budget O(1) where the depth process, which can be hard-coded into a UHAT transformer.
N is (1), as each agent only has a bounded number of tokens to
this construct a protocol computing the function depth ((1) w To realize this, we increase the Transformer's number of layers to immediately compute the relevant agent's 's (1) computation steps when processing the input in the context window: code the agent identifiers into the positional embeddings. The only exception here is in the communication edges; for this, the transformer flags places where it would emit communication edge. After reading the full context, the transformer performs O(1) CoT steps to simulate the ((1) communication steps and re- se-siuulating the affected agents.
Now
We also present here technical lemma from the work of Vardi et al. (022) we will use for the MLPs some of our constructions
Lemma C.1 ((Adapted from Lemma 22 of Vardi et al. (221)) Let T' be threshold circuit with d inputs, q outputs, depth m and size s. There is a neural network with q outputs, depth m + 1 and size 2s + q, such that for every input {0, 10 we have N(x) = T(x). Moreover, for every imput
X E d the outputs of N are in [0, 1].
C.3 PROOF FOR ASSOCIATIVE RECALL (SECTION 4.2
Lemma C.2. Given an input consisting of N key-value pairs (x,, Vi), and queried key Xquery. there exists two layer Transformer with Ollog N) width which returns the associated value.
Proof. We consider that the Transformer agent receives the following input
x= [x]
Y1
Xn
Yn Xquery]
mp2n+1xx
(3)
19

---

Published as a conference paper at ICLR 2026
where x; is vector representing the key and y; is vector representing the value in sequence of key-value pairs. We assume that every key value x; has a unique associated value ys. We use the following embeddings for tokens:
x; (T)) T(yo) Pi(O) Pa(1I
(4)
y; 0 T(y:) Pi(t) P2(t),
(5)
where both vectors are of size log + log(n + 1) + 2, The first logn dimensions are Johnson- Lindenstrauss (J-L) vectors (Johnson et al. 1984) with the property that (T)) < 1/4 for i + j and (T(1), TG)) 2 3/4 for = These are used to embed the position and perform retrieval. The set of log(n + 1) dimensions value vector. These also satisfy the same property as above. Each unique value is embedded in a different vector. Moreover
used to embed the semantic information of each
also define Tyyo) to be the embedding vector corresponding
"no N and (2(1) = sin at N-
value found" Finally the positional encodings are defined as P1(() = cos ut Here, t corresponds the index of each token s.t. E [2n + 1]. Not that this should not be confused with i, which indexes key-value pairs. The proof uses 2-layer transformer model. The first layer copies the T(y:) vector from y; over to the corresponding x,. This is done with two heads which we index (L) and (R) (for left and right respectively. We set the following:
(L) = w(R)
( K
00 I2]
(6)
(L)
= 0 pol
(7)
K
where Pg is the rotation matrix given by
cos 0
sin 0
Po
sin 0
cos 0
(8)
and 0 is defined as
0
N
where N is the length of the full sequence. The three first matrices directly select the positional embeddings from the input, and the last matrix selects the positional embeddings and shifts them by 1. Finally, we set
I
0
0
((()
0
0
0
(10)
V
0
0
0 0
((()
0
I
(11)
0
The MLP for the first layer trivially computes an identity map. For the second layer, we use a construction similar to that of the retrieval heads used in the proof for Prop. 4.7 In essence we select the first log n dimensions of the vectors with both key and query matrices. This gives us an attention matrix which selects key-value vector which is equivalent to the query and puts it in the last component. Then, the MLP for the second layer extracts the T(y:) vector. The output matrix mapping tokens is defined s.t. each computing the dot product with the extracted J-L vector, the majority of the probability mass is put on the correct output token. If the key vector x; was not in the agent's chunk, the last token should still encode T(yo), which corresponds in the output matrix to a special "query not found" token. Using arg max decoding, this thus provides the correct behavior.
is J-L vector T(y:). Vi [n + 1]. Thus when
Note on MLPs Both computing the identity map and selecting a constant number of values in a vector are tasks that are trivially computable by TCO circuit. By appealing to Lemma C.I we can thus obtain RELU-FFNs that can also perform such operations.
Lemma C.3. Given a sequence of tokens {21...., T where all but one I; = Dg. there exists a one-layer Transformer which can retrieve x; $ x
20

---

Published as a conference paper at ICLR 2026
Proof. Consider the Transformer agent receives the following input
X1
xn]
Ruxdd
(12)
where for some 1" [n]. X,- is one-hot encoding of an entity in D and X otherwise. We use the following embeddings for tokens:
x, (T()) T(x;)),
(13)
where both vectors are of size log n + log(n i 1). The first log dimensions are J-L vectors similar
to those used the proof for Proposition 4.7, with the property that (T()). TG)) S 1/4 for + and (T) T()) 2 3/4 for = j. The second log(n+ 1) dimensions are J-1. vectors corresponding an encoding of each possible entity plus an encoding for the "not found" token zg. The construction
essentially the same as the second layer of Lemma C.2 The key difference being that there
just "value" vectors and no keys, thus the first layer which copies the one-hot vector for the value vectors to the key vectors is not necessary.
Proposition C.3. Given an input consisting of N pairs (I):Vs), and a query x, consider the task of retrieving the (unique) y such that (x., y) appears the imput. Assume that the input is partitioned disjointly into parts provided to k agents, which also have access to the query. Then they can solve the task with depth (1) and communication (1))
Proof. The proof follows from Lemmas
C.2 and
C.3
The protocol is follows:
Consider a setup with w agents, and an input consisting of key-value pairs. Thus each agent receives contiguous non-overlapping chunk of size N/w well as the same queried Each agent searches their subset of key-value pairs. The agent that finds the correct key communicates the associated value to a manager agent. All other agents return special "null" token indicating they did not find the key. The manager then searches through the worker outputs and returns the value.
The worker agents can be simulated using Lemma C22 and the manager agent extracting the correct answer from all returned agent tokens can be simulated using Lemma C.3
C.4 PROOFS FOR STATE TRACKING RESULTS (SECTION
Proposition C.4 ((Repeated from Proposition 4.4) Any multi-agent system computing PARITY quires size (NN).
Proof. By proposition 4.1 we know that any protocol computing PARITY can be converted into an equivalent single agent protocol with some CoT length L. By Theorem 4.2 of Amiri et al. (2025). we have that any UHAT CoT for PARITY has length (2(N).
Thus we must have 7. E S(NN).
Proposition C.5 (Repeated from Prop 4.6). Given a finite monoid M and any number of agents (w N + N with w(N) [N]). there exists O(log w<N) + +WNy) depth and O(N) size multi- agent system computing state tracking on M with communication budget wo (NN).
Proof. Let an input x of length N be given, where each symbol is an element of M. We assume for simplicity (otherwise padding) that N is a multiple of the number w of agents. We build DAG as follows.
The context given to agent j is :1.j...., IN/w EOS where EOS is the end of sequence (EOS) token. The context length of the sequence given to each agent is thus N/w+1 + (chunk size plus EOS token).
For each agent j. we create nodes ni n2. RN/wjj with CoT edges nid {t, ff..
+ 1441. with
call SENDo, where SEND is special token to transmit information other agents. Without loss of generality, we assume that this command transmits the symbol a to the next agent with ID 1. The final agent, which we call the receiver, only receives information and
An agent
21

---

Published as a conference paper at ICLR 2026
does not transmit. The protocol computes prefix algorithm with branching factor 2: at the beginning of runtime, all agents compute the composition of their N/w elements. Then the agents with odd indices j send their result to those with even indices, who compute the composition of their result with that of their odd index neighbor and so forth in a prefix sum fashion.
We show this is implementable in UHAT with 3 heads and single layer, with width Olog N). Essentially we use heads to extract the value of the monoid elements and then store them in the EOS token and use the MLP to perform the rest of the processing.
Embeddings We will use quasi-orthogonll vectors to keep track of the positions of different ele- ments in the sequence. Formally, let T (1),.... T(2N/w 1) be 2. 2N/ + vectors of dimension k == (log N) such that (i), TG)) & for i & and (T T(i)) 2 3/4 / for = j. Such vec- tors can be obtained using the Laanson-inddestrauss Lemma. We define E(o) ) be the embedding
vector of some symbol E E. Embeddings have the following structure
E = (ohe(o)
ohe(o)
T(i) 0 0
SEND],
(14)
| vectors, the two last dimensions are also of dimension le and where [send] E {0, 1} are flags which are set to 0 by default. Equally, we define the embedding of the end of sequence token
where ohe(ar E {0, 1] is the one hot encoding (OHE) of E, T(i)s are quasi orthogonal
E(EOS) 00 0
T(1) T(2) SEND]
(15)
Construction for composition of monoid elements The construction for composition requires one layer and three heads. The key idea of the construction to use two heads to extract the two given timestep. then concatenate them in the embedding of the $ token.
elements to be composed The MLP can then perform the composition, which it returns in the embedding of the last token. The third head is only there copy back the remaining embedding values. For the first head, we would have the following key, query and value matrices:
0
0
0
0
OOFO
W Q
O
W
W
0
1 0
(16)
0
0
The output of the attention layer is thus all zeros except for the embedding at the EOS symbol which would be
E(EOS) [ohe(a) 00 T(1) 0
SEND],
(17)
The construction for the second head is very similar, with the main differences being the query matrix has the all Os and identity at the last block and the value matrix is like that of the previous head with the two last columns swapped. This would give us a similar sequence of all vectors, except for the embedding at the EOS symbol which would be
(18) The third head trivially computes the identity matrix (but with Os the EOS position) by using both key and query matrices to extract the J-L vectors found at the "third" embedding block. We then use the W o matrix select the relevant parts of out of each head. Once this is done, we use the MIP to compute composition.
E(EOS) = [0 ohe(a) O O T(t) SEND],
MLP
The MLP computes a map as defined below. If SEND O: (ohe(a1) ohe(az) O T(ii) T(i2) SEND] +
(ohe(ar) oh)( ohe(a,) o ohe(az)
0 T(i +c) T(1 +) SEND],
where eis the token count between the first token and the EOS token, with ooo(d)))oe(()) +> ohe(ar)
and 0 + 0 in the last two J-L positions.
If T(i2 + c) T(2N/w), the model computes this slightly different map:
(ohe(02N/u-1) ohe(O2N\w) 0 T(2N/w- 1) T(2N/w) SEND +
(ohe(SEND) ohe(O2N/w-1) ohe(02N/w)
T(2N +1) T(2N/w +1) 0 SEND]
22

---

Published as a conference paper at ICLR 2026
Thus at the next step of decoding the final vector would stay the same.
If the SEND flag is equal to 1, the MLP simply swaps the values in the first [ dimensions with those in the second = dimensions. Thus, once it is time to communicate the model outputs SENDo.
Such a map can be defined by a threshold circuit. Composition clements from a finite monoid trivially be evaluated constant time by framing the problem constant lookup. The shifting of indices is also TCO as this is reducible to counting/addition which is known to be in TC0 Nguyen & Cook (2006). Finally, TCO is closed under boolean combination. Thus performing the conditional routing of which circuit to used based on the flag value is also in TCO. Finally, by Lemma C. we know that if such circuit exists, it can be converted into MLP which is linear in the circuit parameters.
Output matrix Every row of the output matrix is OHE of one of the symbols in The output matrix is a combined transformation which first selects the top |=| dimensions and uses the OHE vector found there to put at the underlying position in the output vocabulary vector. Only the last token is used for prediction.
Receiving and sending communication We assume all agents decode synchronously. When an agent receives a symbol, the protocol takes the agent's last symbol, and appends the received symbol as well as EOS token. For simplicity, we assume that each agent is given fresh new context at the beginning a new round of communication. The construction could easily be extended by adding a layer which zeros out the embedding values of vectors from the previous query. To make sure all the agents only send symbols at the appropriate time, one can casily change the number of J-L vectors which the agent receives as these decide at what point the agent sends information.
Proposition C.6. Let L be regular language over E. For each w N + N (w(N) E (N), there a multi agent system with w wNN) agents that computes membership in L.
Proof. This statement follows immediately as a consequence of Proposition 4.6
Proposition C.7 (Optimality (Repeated from Prop- Prop.44.p) Assume the finte monoid M is a nontrivial group, and A multi-agent system computing state tracking over M. Then Ow)(N) communica- tion budget, and computation depth Q
N are each optimal.
w(N)
Proof. Optimality of the communication budget holds because each agent's portion matters for the result: each agent must send at least one message, hence the communication budget scales linearly with the number of agents. The computation depth lower bound follows from the Proposition 4.1 on
size conservation:
= Size S Computation Agents
(19)
hence
N
S Computation- Deptth.
(20)
(NN)
From which the result follows.
C.5 PROOFS FOR --HOP REASONING (SECTION 4.4
Proposition C.8. Let the number of agents be : N N (w(NN [N]). The k-hop composition task with N facts can be solved with computation depth (k), communication budget Okk), and size (N. k)). The communication budget is optimal. The computation depth O(k) is optimal at least up to a log(NV N + k) factor.
Proof. We start by exposing the communication protocol which we prove optimal. Then, we give the constructions of the worker and manager agents which implement this protocol. The protocol is as follows:
Let N be the number of total key-value pairs in the context and let be the number of worker agents. Each worker agent receives a chunk N/w as well as first query fi (X.uury). In the first round, the each agent searches for fi (X.uerr) in its chunk. The agent that finds the queried key
23

---

Published as a conference paper at ICLR 2026
communicates its associated value to manager agent. The manager agent then updates the query s.t. fa(fi (Xquer)) = fi (Xquer) and broadcasts this new queried key to all worker agents. This process repeats l times in total until the entire k-hop query is resolved.
Worker agent construction vectors, letting
The worker agent essentially performs recall on a series of key-value
X = [f(x)
fxx.)
Yn f (Xquery)]
)| E IR 2n++
(21)
we can straightforwardly apply Lemma if simply append the new queried key to the end current sequence, the worker construction will return the value for the rightmost queried key. This is true because the construction uses rightmost tie-breaking in attention.
C.2
We note that the same agent can be used across hops;
Manager construction
The manager agent receives sequence of functions
f fn
Yquery E(#),,
(22)
where f; is an embedding of the function that sends an entity to another through their relationship. Yquery is the current known entity and E(#) is the embedding of the EOS token. The key idea of the manager construction is to compose together the last function with the query entity in order to return entity value. To do so, define transition map
Σ f(z)e, E ER IED
(23)
with the full embedding vector being
T(i) 0 2 N
(24)
where e,, is the canonical basis vector corresponding to the entity for some indexing I. Con- sequently, we have that Yquery 0 ei, +1 0) E 2|+2 lug i.c. a canonical basis vector with one in the position of the corresponding entity in the second half of the vector. Simi- larly to the worker agent construction, we define the embedding of EOS token as
E = 0 0 T(n)
T(n + +1]]
(25)
where T(1)..... 1(n+1) are J-L vectors s.t. (T(1), T()) S 1/4 for i + and (T T()) 2 3/4 for i = The attention layer is defined in a similar manner to that of the one in the proof for Proposition 4.7 and uses two heads to retrieve both the with and n 1th elements the sequence using the positional encoding given through J-L vectors.
The MLP then computes the composition of qn with e, and outputs the OHE vector of the resulting token. This can easily be done leveraging Lemma 5 of of et al. (2022).
Optimality The protocol described above has size @(wk), communication budget O(k), and com- putation depth @(k).
Optimality of the communication budget follows because composition of k permutations over (I.....5) 5} has communication complexity (2(k) in the model where one agent has the even po- sitions and the other the odd positions (Tesson Thérien 2002]. Thus, communication budget ((k) even when w( (N) = 2. Extension to larger w(N) follows by considering the case where all relevant facts happen to be distributed between two agents.
To prove that the depth is worst-case optimal up logarithmic factor, we consider the case where all relevant facts happen to be distributed between two agents. Hence, these two agents must jointly emit ((k) communication bits. Because agent emits only Oloo |N++l) = O(log( N + k)) bits at a step of time, the number of communication steps between these two agents (and hence the computation depth) must be lower-bounder by Ω Tog(N+
24

---

Published as a conference paper at ICLR 2026
D PARITY ERROR ANALYSIS
Definitions. Fix integers 2 2 and e 2 1, and set = k The Parity function P: (0, 7 (0. 1) is defined
P(r = I1 3 + 2m:
where @ denotes XOR addition in F2. Let {0, 1} {0, 1 be a randomized algorithm which takes input z of length exactly & and outputs P(x) with probability - c, and outputs 1 P(z) with probability other words, it computes the Parity function with error c. The function f() can also be written as,
(() = @(
where the node error {0, 1} equals 1 with probability and with probability different calls of f are independent (hence their error bits are i.d.d Bernoulli(E)).
Assume
Given input
{0, 1,m², define the composite algorithm F where first divide the input in N/k chunks of length k, and apply ff on each of them to get N/k outputs. We do this recursively to be
obtain the final output. The computation bits of 2); at each internal node, apply f to the outputs of its children. The output F(z) is the bit the root. The has M nodes where
k-ary tree of depth with N leaves (the
N N
M
Σ 1=0
Each internal node computed by an independent call to f.
Lemma D.1 (Error of a parity tree with i.i.d. flips). For every fixed E (0, let error of f be the probability that the algorithm makes an error is given by,
1 1 (1- 2
N -
Pr [F(2) P())
M
Thus the probability of making mistake using the Prefix sum protocol on string of length N, assuming a branching factor of l = 2 would be
2s)
Pr [(()) P(=)]
Note that as N - we asymptotically reach a probability of 1/2, even for very small e. However, for small & values, the number of tokens processed by each each is also very small and thus the performance only degrades for very large N. This is the regime in which operate in practice, thus corroborating this theoretical model to our experimental results.
Proof. We first show that the algorithm F makes an error if and only there are odd number of errors in the nodes of the computation tree.
For each node u, let s(u) denote the parity the leaves in the subtree of u, and let ((u) be the value computed by F at u. Define the node error indicator 5(u) := s(u) ① s(u) E {0.1). For an internal node with children ..,..., Uk. write e, for the (independent) error bit of the call to f at so that
3(u) ((((1),.... ...., 3(ux)) = P(s(u)). ,((s)) @ ex.
Using linearity of @,
b: a s(u)) = + 1=1
8(v) = ((u) ( D(v)) 3( s(u.) + ee))
+
6(u)) Be..
i=1
Since 6(leaf) = induction up the tree yields (root) and only if an odd number of node calls make
+, Ev. Thus, the algorithm errs
Let = 6(root) = O e, E {0. be the random variable which takes the value when F makes error and is 0 otherwise. We introduce another random variable Y, (-1)+v E {-1, +1). And let = (-1)8 = II. Y, by rewriting Parity as a product, which is quite standard to make calculations convenint.
25

---

Published as a conference paper at ICLR 2026
Since the calls are independent, we have
E II B[Y.] ((1 ((1-6) 1+ (-1)) M = -11-2
Since +1 iff S and = =1
E| = Pr[S = 0] Pr[S = 1l,
Pr[S - Pr(S = =
Solving the two equations above gives
Pr[$ = 1] + (1 22)
2
E EXPERIMENTAL DETAILS
General details:
All experiments were run on TogetherAl API
Models used: 3.Stt2t-Instruct
-atte-----77----ttttt--------- EXAONE-
All experiments 100 times with seed set 42 for consistency.
Three multi-agent architectures tested: Majority Voting, Shain-of-Agente and Prefix Sum
For all experiments, examples are generated on the fly given the length and difficulty pa- rameters specified in the script.
Throughout, we use agents in the majority voting setup. We ablated over [2, 16] agents across all considered tasks and found that past 8 agents, there was no significant improvement in any of the tasks. The choices for task specifie hyperparameters are discussed in their respective subsections.
E. ASSOCIATIVE RECALL TASK
Key-value strings are generated at random. A recall query is sampled uniformly from the keys. Models are prompted their roles (manager or worker) explaining what they must and the com- munication is handled deterministically.
In experiments, we test sequence lengths (i.e., the number of key-value pairs) as powers of two ranging from 2 to 21, We use 8 agents for Majority Voting. For Chain-of-Agents, we select the optimal chunk chosen from powers of two between and 64-for each sequence length.
Associative Recall Majority Vote Agent Prompt
You a reasoning agent responsible for analyzing portion of document. Your task detect specific value in sequence key-value pairs, given a corresponding key. Follow these steps:
1. Identify if the key is present in the sequence of key-value pairs.
If key is present, return value corresponding the key.
3. If the key is not present, return NOU.FOUND".
Present the final answer the format "The answer is: [your answer]"
You MUST use the following template. ONLY OUTPUT THE ANSWER. Here is example for "23 42 12 34 56 78 90 12 Query: 56":
The answer is: 78
26

---

Published as a conference paper at ICLR 2026
Associative Recall Chain-of-Agents Worker Prompt
You reasoning agent responsible for analyzing portion of document. Your task detect specific value in sequence key-value pairs, given a corresponding key. Follow these steps:
1. Identify if the key is present in the sequence of key-value pairs.
If key is present, return value corresponding the key.
3. If the key is not present, return "NOT FOUND".
4. Present the final answer the format "The answer is: Iyour answer]"
You MUST use the following template. ONLY OUTPUT THE ANSWER. Here is example for "23 42 12 34 56 78 90 12 Query: 56":
I'he answer 1s: 78
Associative Recall Chain-of- Agents Manager Prompt
You manager agent responsible for synthesizing information from multiple workers. Your task is combine their provided values and determine value corresponding to the query. compute final value, fallow these steps:
1. Collect the value results from all worker agents.
2. Each worker will return either a value or "NOT FOUNDD.
3. Exactly worker will return the value corresponding the query, the rest will return "NOT.FOUND".
4. Report the value corresponding to the query as output.
Present the final answer the format "The answer is: [your answer]"
You MUST use the following template. ONLY OUTPUT THE ANSWER. Here an example for "NOT_FOUND NOT_FOUNT 78 NOT_FOUND":
The answer is: 78
E.2 PARITY CALCULATION TASK
String of bits of fixed length sampled uniformly at random. Ground truth is computed with function which evaluates parity. Models are prompted their roles (manager or worker) explaining what they must do and the communication is handled deterministically.
The experiments test sequence lengths as powers of 2, ranging from 2 to 2 (i.e., length 8) with support for index hints aid model reasoning. We use Majority Voting over total of agents. For Chain-of-Age ofin-ntss,,, binary strings are split into chunks size 8, while Prefix Sum uses a branching factor of 4 for hierarchical processing. For Chain-of-Agents, the optimal chunk size determined by ablating over the range [2, 4, 8, 16). For Prefix Sum, the optimal branching factor was determined by ablating over the range [2, 4. 8]. The task evaluates models' ability to accurately count 1-bits and determine even/odd parity across different architectural approaches.
The data for the Pareto frontier plots (computation depth vs. total communication) was generated by ablating over the branching factor for the prefix sum protocol. The total communication (number of edges) is can be computed straightforwardly as the sum of all edges of the log-depth tree with the corresponding branching factor. Sequence lengths are taken to be powers of two. For each sequence length 2", we ablate over powers of two from to 2
Parity Majority Vote Agent Prompt
You are a reasoning agent responsible for analyzing portion of document. Your task is to provide analysis of the binary string provided in your chunk and determine if it is even odd parity. To compute the parity, follow these steps:
1. Count the number of I's in the binary string.
If count is even, return
3. If the count is odd, return
27

---

Published as a conference paper at ICLR 2026
4. Present the final answer in the format "The answer is: [your answer]"
You MUST use the following template. Here an example for "1011":
1: (count:
2: (count:
3: (count: 2)
4: (count: 3)
Final count: 3
The is:
Parity Prefix Sum Prompt
You a manager agent responsible for synthesizing results of previous workers. Your task is to return the parity the binary string provided by the worker agents. may think step by step, your final answer should be concise and clear. To compute the parity, follow these steps:
Collect the results from the worker agents. This should be list of binary digits (0 1).
2. If the parity of the list is even, return 0.
3. If the parity of the list is odd, return
4. Present the final answer on new line in the format "The answer is: [your answer]"
IMPORTANT: Show your work step by step demonstrate thorough analysis:
1. Go through each bit position and note its value
2. Keep running count of Is encountered
3. State the final count
Determine if the count is even or odd
You MUST use the following template. Here is an example for "1011":
0:
1:
1:
Final count: 3
The answer is:
Parity Chain-of-Agents Worker Prompt
You are worker agent responsible for analyzing a portion of document. Your task provide an analysis of the binary string provided in your chunk and determine if is even or odd parity. To compute the parity, follow these steps:
Count number of in the binary string.
2. If the count is even, return 0.
If count odd, return
4. Provide your result in clear and concise manner.
Present the final answer the format "The answer is: [your answer]"
You MUST use the following template. Here is example for "1011":
1:
0:
1:
1:
Final count: 3
The answer is:
28

---

Published as a conference paper at ICLR 2026
Parity Chain-of-Agents Manager Prompt
You manager agent responsible for synthesizing information from multiple workers. Your task to combine their provided parities and determine the overall parity of the hinary string. To compute the aggregate parity, follow these steps:
1. Collect the parity results from all worker agents.
2. Each worker will return either or 1.
3. Count the number of responses.
4. If the count responses is even, the overall parity is O.
5. If the count of 1 responses odd, the overall parity is 1.
6. Present the final answer the format "The answer is: [your answer]"
You MUST the following template. Here example for "1011":
1:
0:
1:
1:
Final count: 3
The answer is:
E.3 S₁ PERMUTATION TRACKING TASK
We frame the Ss permutations task word problem where each agent is given prompt explaining there are 5 balls distinct bins and a sequence swap commands such as "swap ball and swap ball 2 and 4". In this task the agents must return the correct value of the ball in each bin. The bin numbers are only given at the beginning of the task making this hard state tracking problem (Merrill et 2024).
The experiments test permutations with varying numbers of swaps ranging from 4 to 12 swaps with step size of 2. By default, the task is constrained to As (even permutations only) by foreing an even number of swaps. For Chain-of-Agent swap sequences are processed in chunks of 2 swaps per worker, while Prefix Sum uses branching factor of 2 with each worker handling exactly one swap operation. For both Chain-of-Agents and Prefix Sum, we tuned on the range [2,4] for the chunk size/branching factor respectively. Given the small sequence lengths used this task, larger chunk size/branching factor options were not feasible. The task evaluates models' ability to maintain accurate state tracking through sequential ball position updates.
Permutation Majority Vote Agent Prompt
You are a reasoning agent responsible tracking positions through a sequence of swaps. Your task is to determine the final position each after performing the given swap operations. Initial state: Each ball starts in its corresponding bin (ball in bin ball 2 bin 2, etc.).
To solve this problem:
First, identify which balls are mentioned in the swap operations ONLY track these balls
2. Start with balls in their initial positions (e.g., if balls 1, 2, 3 are mentioned: (1:1, 2:2, 3:33)
For each swap operation "Swap ball
Y":
Find the current bins of ball X and ball Y
Exchange their positions
Continue until all swaps are processed
5. Present your final answer as dictionary mapping ONLY the balls mentioned in swaps to their final positions
IMPORTANT: Only include balls that appear in the swap operations. Do not add extra balls. Present the final answer in the format "The answer is: binnl, ball2:bin2.... ...)" for only the balls involved in swaps.
29

---

Published as a conference paper at ICLR 2026
Permutation Chain-of-Agents Worker Prompt
You worker agent responsible for processing portion of swap operations in larger sequence.
Your task is to carefully track positions through your assigned swap operations and report precise current state.
You will receive:
Current ball positions as dictionary (e.g., [1:2, 2:1, 3:3})
A sequence of swap operations to process
Instructions:
1. Start with the EXACT positions given to you this is the state after previous swaps
Process each swap operation "Swap
ball Y" order:
Find the current bins of ball X and ball Y
Exchange ONLY their positions
Keep all other balls in their current positions
3. Track each swap carefully one mistake will affect the final result
4. Report the state after processing ALL your assigned swaps
CRITICAL: Only include the balls that present in the input positions. The exact balls,
more, no less.
Present the final answer the format "The answer is: [balll:binl, ball2:bin2,... ...]" with the exact same ball numbers as your input.
Permutation Chain-of-Agents Manager Prompt
You are a manager agent responsible determining the final ball positions from worker results, Your task is to identify the final state all balls after swap operations have heen processed by your workers.
You will receive position dictionaries from multiple workers who processed different portions of the swap sequence in order. The workers processed swaps sequentially. so: Instructions:
1. The workers processed swaps in chronological order (worker 1 -> worker - worker 3, etc.)
2. Each worker started with the positions left by the previous worker
3. The LAST worker's result contains the final positions after all swaps
4. Simply report the last worker's position dictionary as the final answer
CRITICAL: Take the position dictionary from the last (final) worker only. This represents the complete final state. Present the final answer in the format "The answer is: (balll:binl, ball2:bin2, ...)"" exactly as reported by the final worker.
Permutation Prefix Sum Worker Prompt
You worker agent in hierarchical system processing ONE swap operation. IMPORTANT: Initially, halls start their corresponding bins (ball in bin 1, ball 2 2, etc.). Through swaps, balls can move to different bins.
Your task is to apply exactly one swap operation and report the resulting ball positions with perfect accuracy.
You will receive:
Current ball positions as dictionary (e.g., {1:3, 2:1, 3:2, 4:5, 5:44)
ONE swap operation: "Swap ball
Y"
Process the swap step-by-step using this exact reasoning template:
Current state: [copy the input dictionary]
2. Operation: [copy the swap operation]
Ball currently [identify bin number]
30

---

Published as a conference paper at ICLR 2026
4. Ball Y is currently in bin: fidentify bin number]
After swap: Ball X moves to bin (Y's old bin], Ball moves to bin [X's old bin]
6. Verification: Check that only these two balls changed positions, all others remain the same
7. Final state: [complete updated dictionary]
CRITICAL CONCEPT: You tracking which BALL is in which BIN.
BALLS are the moving objects (numbered 1, 2, 3, 3)
BINS are the fixed locations (numbered 1, 2,
When you swap "ball X and ball Y". you move those balls to different bins
The bins stay in place only the balls move between them
CRITICAL: Include ALL balls from input with exact same ball numbers. One swap affects exactly
Two positions.
Present the final answer in the format "The answer is: (ball1:bin1, ball2:bin2, ...)" with all balls from your input.
Permutation Prefix Sum Manager Prompt
You are manager agent in hierarchical ball-tracking system combining results from workers. IMPORTANT: Initially, balls start in their corresponding bins (ball in bin 1, ball 2 in bin etc.). Through swaps, balls move to different bins.
Your task is to determine the final ball positions after your workers processed their assigned swaps in sequence.
You will receive position dictionaries from workers who processed swaps in chronological order. Each
worker:
Started with the ball positions left by the previous worker
Applicd exactly one swap operation
Reported the updated positions
Your job requires careful validation and explicit reasoning:
1. Validate that each worker's result is logical continuation of the previous worker's output from initial final
Show the complete sequence
3. Verify that each step represents exactly one swap operation
4. Report the last worker's result as your final output
Use this reasoning template:
Initial state: [first worker's input state]
2. After worker 1: [worker I's result] validate this is one swap from initial
After worker 2: [worker 2's result] validate this one swap from worker I's result
4. Final result: [last worker's result]
CRITICAL: Output exactly the position dictionary from the final (last) worker. This contains cumulative effect swaps. Present the final answer in the format "The answer is: [ball1:hinl, mall exactlyy as reported by the last worker.
E.4 k-HOP REASONING TASK
We create list of entities and list of relations. We create the fact base by sampling at random two entities and relation and then deterministically generating string. This procedure is done many times as the number of facts needed. Then relationships are sampled in order to form a valid query that has its answer in the fact base.
The experiments test the models' ability to follow multi-step reasoning chains with varying numbers of hops (relationships to traverse). We use 50 balanced single-toker entity names (25 male, 25 fe- male) and 20 diverse single-token relations (boss, instructor, teacher, etc.). For this task, we generate problems with & hops where l ranges from 4 to 20 hops with step size of 2. The experiment was
31

---

Published as a conference paper at ICLR 2026
repeated with 100, 200 and 500 total fact count. For the IterativeQurrAgeens approach, facts divided into chunks of 20 facts per worker. Across all three regimes, we ablated over the range [10, 20, 50] and found 20 yield the best accuracy.
K- hop Majority Vote Agent Prompt
You are expert logical reasoning and following relationship chains. Your task is answer questions about relationships between people by following chains of connections through the given facts. You will given:
1. A of facts describing relationships between people (e.g.. "Alice's boss is Bob")
2. A query asking about a multi-step relationship chain
Instructions:
Read all the facts carefully
Follow the relationship chain step by step
Track each connection to find the final answer
Output your answer in the exact format: Answer: [PersonName]
Example: Facts: "John's boss is Mary. Mary's supervisor Tom." Query: "Who is the supervisor of the boss of John?" Reasoning: John's boss is Mary + Mary's supervisor is Tom Answer: Tom Be systematic and double-check your reasoning chain.
K-hop IterativeQuery Worker Agent Prompt
You are a helpful assistant that answers questions based ONLY on the given facts. IMPORTANT: You have been given only small subset of all available facts. is very likely that the fact needed answer the query is NOT in your subset. You will be given:
1. A limited set of facts about relationships hetween people
A specific query about one relationship
Instructions:
ONLY look through the facts provided you
If you find the EXACT fact needed to answer the query, extract the answer
If exact fact NOT in your subset (which very common), respond with "Not Found"
DO NOT guess or infer answers from similar facts
DO NOT make assumptions about relationships not explicitly stated
DOUBLE CHECK: DOUBLE-CHECK: Before giving your final answer, carefully re-read the facts to ensure you have the correct match
Always format your response as: Answer: [YourAnswer]
Example (found): Facts: "John's 'ohnnssson boss is Mary. Alice's teacher is Bob." Query: "Who is John's boss?"
Response: Answer: Mary
Example (not found very common): Facts: "John's boss is Mary. Alice's teacher is Bob." Query:
"Who is Sarah's 's mentor?" Response: Answer: Not Found
Example (not found don't guess): Facts: "John's boss is Mary. Alice's 's teacher is Bob." Query: "Who
is Mary's supervisor?" Response: Answer: Not Found
CRITICAL: Before responding, double-check your work:
1. Re-read the query to understand exactly what is being asked
Scan through ALL facts again to verify your answer or confirm it's found
3. Make sure the relationship type matches exactly (c.g., "boss" vs "supervisor")
Only provide answer you are completely certain appears the facts
Remember: Most queries will not have their answer in your subset of facts. Only answer if the exact fact is present and you have double-checked it.
32

---

Published as a conference paper at ICLR 2026
K-hop IterativeQuery Manager Agent Prompt
You manager agent that coordinates multi-hop reasoning queries.
Your task is to take an answer from a previous query and generate the next query the reasoning chain.
You will be given:
The original multi-hop question
2. The current intermediate answer
3. The current step number
Instructions:
Use the intermediate answer to construct the next query
Format your response as: Next Query: [YourQuery]
boss John?" Current answer: "Mary" (John's 's boss) Response: Next Query: Who is Mary's supervisor?
Example: Original question: "Who is the supervisor
E.5 NEIDLE-IN---HAASSAAK
For the needle-in-a-haystack test, we follow the implementation given by Kamradt (2024). We use as query: "What is the best thing to do in San Francisco?", with associated answer "The best thing to do in San Francisco is eat a sandwich and sit in Dolores Park on a sumny day."). The text which the needle is embedded is the corpus of Paul Graham essays 14k words). For context lengths longer than 14k words, we simply concatenate the corpus multiple times until we achieve the desired length. The original implementation does the same. We repeat each experiment 10 times and report average accuracy across 10 runs. For Majority Voting, we use 8 agents, for CoA, we use a chunk size of 2000. Agent count is chosen from the range [3,5,8] and chunk size was chosen between [200, 1000, 2000]. Given the prohibitive number of datapoints for the full heatmap, we tuned hyperparameters on subset containing only the last context lengths and depths from 0% to 50% as those seemed, in the literature, to be the most problematic datapoints. We use Meta Llama- 3. 1--8B-Instren Instruct-- Turbo for considered experiments.
F ADDITIONAL EXPERIMENTS
In this section, we provide experiments from tasks and models that are not featured in the main paper.
F. RECALL
Figure shows accuracy for different sequence lengths. For shorter sequences (64-512), perfor- mance similar, with Majority Voting sometimes outperforming CoA, but the multi-agent approach gains an edge as length increases. This trend is consistent with theoretical understanding. Recall is task easily solved by Transformers, even with limited CoT (Arora et al. 2023 Bhattamishra al. 2024). Thus, at shorter sequence lengths, the communication overhead may be detrimental by e.g., leading to hallucinations in models that do not have the key-value pair in their context.
33

---

Published as a conference paper at ICLR 2026
Avorge AuciaaY
0.
0.0
123
256
512
1024
2048
Sequene Lengh
Figure 6: Llama-70B accuracy RECALL across sequence lengths. CoA is the theoretically opti- mal protocol.
F.2 PARITY
In this section, we provide PARITY results similar to those in the main text, but with Ilama-8B as the base model for agents. The plots here show trends similar to those in the main text. We note that Ilama-8B has poorer accuracy on the task; this is due to the deviating from the prompted guidelines and making mistakes (i.e. flipping bits) more frequently
Llama-SB: Computation vs Communication
1500
Computation Deptis
27 125
2 250
1000
500
100
200
300
400
500
Total Communication (Edges)
Figure 7: Communication vs Computation tradcoff for Llama-83 8B showing the relationship between communication budget and computation depth across different multi-agent protocols for the parity
task.
Llama-8B: Parity Accuracy
1.0
Mij Yodig
0.8
Coa
Accuracy
0.6
0.4
0.0
256
512
Sequence Length
Figure 8: Parity calculation accuracy for Llama-8B across different sequence lengths, comparing
single-agent multi agett performance.
F.3 Sy PERMUTATIONS
Figures 9 and 10 provide detailed comparisons between Llama-8B and Llama- 70B models across all three multi- agent approaches.
34

---

Published as a conference paper at ICLR 2026
LJama-8h Esact Match
LJama-NRR NR: Element Accuracy
1.0
1.0
Prito Sees
Froto San
Majuct Voltg
Majuit Vosee
68-
Chain Afyrra
03
Uhiie
Hewwatt Accuracy
6.-
0.6
9.4
Number
Number
(a) Exact match accuracy for Llama-8B So permutations task. Prefix Sum rep- resents the theoretically optimal communi- cation protocol. Majority Voting is self- consistency with majority voting decision, and CoA Chain-of-agents protocol. Perfor- mance degrades as the number of swaps in- creases, with Prefix Sum maintaining superior performance.
(h) Per-element accuracy for Llama-8B Ss permutations task. Element accuracy measures the fraction of correctly placed el- ements in the permutation. Shaded regions represent standard error bounds across mul- tiple runs.
Figure 9: Performance comparison of multi-agent approaches on the S₂ permutations task using Llama-8B.
Liuma-70B: Esact Malch
Llama-70B: Element Aveuracy
Accuray
Foact Match
6.6
0.6
0.4
0.4
02-
Tiels San
0.2
Masiiiy Srizz
Majetty Varee
Chass
Chan Agati
0.
16
0.0
16
Numaber of Swaps
Numaee of Swrpp
(a) Exact match accuracy for Llama-70B on the So permutations task. The larger model demonstrates consistently improved perfor- mance across all agent types compared to Llama-8B, with the performance gap being most pronounced for the Chain of Agents ap- proach.
(b) Per-element accuracy for Llama-70B on the S' permutations task. The improved rea- soning capabilities of the larger model help mitigate the composition complexity chal- lenges inherent to multi-agent coordination.
Figure 10: Performance comparison of multi-agent approaches on the S3 permutations task using Llama-70B.
F.4 НOP REASONING
35

---

Published as a conference paper at ICLR 2026
100 Facts
1.0
EXAONE MV
IQ
Liana
Liama 8D IQ
0.8
Accuracy
0.6
12
16
20
Number of Hops
Figure 11: Comparison of multi-agent approaches for k-hop reasoning with 100 facts. Shows per- formance across different hop lengths for Llama-8B and EXAONE models.
200 Facts
1.0
EXAONE MV
Liama 8D MV
Lamu-aR IQ
0.8
Accuracy
0.6
0.4
12
16
20
Number of Hops
Figure 12: Comparison of multi-agent approaches for k-hop reasoning with 200 facts. Shows per- formance across different hop lengths for Llama-8B and EXAONE models.
36

---

Published as a conference paper at ICLR 2026
500 Facts
1.0
EXAONE MV
Lama 8D MY
Liarna 8B 10
0.8
Accuracy
0.6
0.4
0.2
0.0
12
16
20
Number of Hops
Figure 13: Comparison of multi-agent approaches for k-hop reasoning with 500 facts. Shows per- formance across different hop lengths for Llama-8B and EXAONE models.
200 Facts
1.0
0.8
Accuracy
0.6
0.4
0.2
0.0
Number of Hops
Figure 14; Llama-70B k-hop reasoning accuracy with 200 facts.
37

---

Published as a conference paper at ICLR 2026
Token Usage Analysis: Llama-8B
100 facts
1200
200 facts
500
Computation Depth
800
400
10
12
14
16
18
20
Number of Hops
Figure 15: Computation depth vs. number of hops in the query for Lama- 8B.
38

---

Published as a conference paper at ICLR 2026
G BEYOND SINGLE-TOKER COMMUNICATION
Definition 3.1 assumes that agents can only send and receive a single token at each time step. This assumption 18 for mathematical convenience, and not fundamental to our results. Indeed, agents in real-world multi-agent systems may exchange messages spanning multiple tokens. Here, we explain how our analysis carries over to the setup where agents communicate multiple tokens in a message.
Formalization in the case of multi-token messages Assume an agent Ti aims to send a multi- token message 01 ... (each token in {/e) to agent 7 The simplest way of formalizing multi- token messages is to simply view these as multiple single-token messages: T; iteratively communi- cates d ...... ..... σ% over total of k time steps. We believe this to be natural and sensible approach, as transformer-base based agents can naturally produce and consume one token per time step.
If clear delineation of which sequences of single message tokens count as a multi-token message is desired, then natural formalization is for the sending agent to output "START MESSAGE" and "END MESSAGE" tokens before and after the message tokens.
Implications for Results Here, we discuss the implications for our theoretical results when mes- sages span multiple tokens. By the above discussion, we can equivalently translate protocol using multi-token messages into protocol with single-token messages, without change to the size, width, computation depth, or number of communication tokens. Thus, bounds on size, width, and compu- tation depth remain entirely unaffected by generalization to multi-token messages. The communica- tion budget, i.c., the number of message tokens, also remains unaffected. As a consequence, all of theoretical results remain unaffected even if the messages span multiple tokens.
H COMPARISON TO SELF-CONSISTENCY AND VOTING APPROACHES
As stated in the Introduction, our results concern the expressivity of multi-agent systems where each agent has access to a disjoint part of the input. Thus, the popular strategy of giving the same input to multiple agents and performing majority voting on their answers (c.g. [Wang et al., 2022) not in scope. Here, we show that multi-agent systems in our framework can achieve substan- tially better tradeoffs than majority voting-based approaches. Our argument is conceptually related to that in Mirtaheri et al. (2055). who however only compared voting (without any CoT) to long CoTTs (in a single agent, without any communication), and relied on unproven conjectures about TC". We instead compare majority voting and more sophisticated multi-agent system (PrefixSum, Section 4.3 when both are allowed the same computation depth.
We consider state tracking in the simple case of PARITY. We contrast PrefixSum to majority voting between agents, and in both cases allow a depth (number of sequentially produced tokens for each agent) of Olog N). We first give a general definition of majority voting in our framework. To make our result as strong as possible, and cover even voting among inhomogenous agents, we do not assume that the agents share parameters, but even allow voting among agents given by different models.
Definition H.1 (Majority Voting). Consider w(N) distinct agents, each given by UHAT transform- ers Ti...., Tw(N). For full generality, we allow each agent to have their own parameters. We only assume that the number of layers and heads is uniformly bounded across agents. We run each agent on the full input, producing a CoT of length (computation depth) depth(N). ending in a single-token response. We then output the most frequent response (with arbitrary choice in the case of ties).
Despite the generality of this formalization, we now show a super-polynomial separation between majority voting and PrefixSum, by giving a lower bound on the number of agents needed to compute PARITY in a majority voting scheme. We consider the setup where the multi-agent system aims to compute PARITY state tracking exactly. This is consistent with our overall framework, where expect that multi-agent systems perform tasks perfectly. Here, we show:
Proposition H.1. Consider majority voting scheme among w(N) agents computing PARITY over length-N inputs, with computation depth depth(NN = Ollo N).
This scheme must have w(N) = 22(N") agents, for some c > 0 depending on the number of heads and layers in the transformers representing the agents.
39

---

Published as a conference paper at ICLR 2026
The key takeaway here is the expreexponential lower bound on the number of agents, w(N) 20(N") In contrast, PrefixSum attains perfect accuracy with computation depth (log N) and w(N) = N. as we showed in Prop. 4.5 This thus leads to a super-polynomial separation, be- tween linear number of agents in PrefiXSum, and near-exponential number of agents in majority voting.
We note that the above result concerns majority voting schemes that exactly compute PARITY with zero errors, based on results on voting polynomials by Aspnes et al. (991). We conjecture that these techniques of can also be generalized to provide lower bounds on the number of agents needed for any voting scheme computing PARITY with good accuracy, though such a generalization is beyond our scope here. Importantly, given that PrefixSum solves PARITY deterministically, we believe that a bound on error-free computation is most relevant here.
Proof. Formally, we have w(N) UHAT agents who all produce a CoT of length (communication depth) (N) (log N).. For given string over the CoT alphabet, of length depth(LV). we can check in AC that it is produced by a UHAT transformer. The number of layers of this circuit bounded terms of number of layers and heads of the transformer; the size is polynomial in N.
The number of such strings is ((poly(N))oeee N) OoNCloggN) We now replicate this circuit once for every string, for each string checking if is produced by the transformer. Note that the transformer produces exactly one of these. The replicate that detects that the string matches the CoT produced by the transformer signals this and outputs the result (0 or 1); all other replicates output A single unbounded- fanin OR gate then extracts the answer from this one one replicate. We thus have obtained an AND-OR ADD-R circuit computing the output of single agent, with size O O(NCloR for some C Z 1, and with layers, for d bounded across N.
In order to perform majority voting, we now put together all agents with a majority gate at the root. This is a circuit of size a(N) = (wr(NN- - NC grClogN), with AND-OR gates and a single majority gate at the root providing the final output. Assume that this circuit correctly computes PARITY. By Lemma 5.4 in Aspnes et al. (199I), we have
s(N) 20(N1/400
(26)
We thus have
log w/( (N) + log NC N = 22(22((00)
(27)
or
log w/( N) + C. -log N)3 ((N11((4)
(28)
which means
log w (N) 12(11/(10) (log N)
(29)
and hence
w(N)= = 20(N110)
(30)
This proves the result.
I IMPLICATIONS FOR FIXED PRECISION TRANSFORMERS
Our theoretical results are shown for UHAT, a popular theoretical model using hard attention. A reviewer asks about the implications of our results to soft attention transformers with finite precision and fixed width. The expressive power of causal transformers with soft attention, fixed precision, and fixed width was studied by Li& & Cotterell (2025), who showed that their expressiveness corresponds to a subclass of the wwo-variable fragment of first-order logic over words, [<] This in turn can be simulated in UHAT, shown in Derad et al. (2025b). While they study the case of transformers without positional encoding (NoPE), expanding their results to absolute position encodings (APE) is straightforward:
Proposition I.1. Let T be soft-attention transformer with finite precision and finite width, and absolute positional encodings Pı.P2... ... E Idd with bounded norm, sup, l|p:ll2 < co. Then can be simulated by UHAT transformer.
40

---

Published as a conference paper at ICLR 2026
Proof. The assumptions imply that the vectors P1 P2.... traverse finite set A. which bijectively map to the set ......,AA[], Now to simulate the operation of on a string, we can view T is NoPE transformer operating index corresponding to pi E A. As this NoPE transformer can be translated to UHAT, we can then augment the resulting UHAT transformer with positional encodings to simulate the operations of the original APE transformer T'.
string where each position is annotated with the
a consequence, lower bounds on UHAT-based multi-agent systems in this paper transfer to such finite- setttepreeciion softmax transformers. On the other hand, experimental results in Section show that protocols attaining asymptotically optimal tradeoffs can indeed be implemented using real transformers.
41


Reviews:
[{"review_id": "3WxqnEVYDc", "reviewer": "Reviewer_PxAy", "summary": "The paper develops a formal framework to study multi-agent reasoning in LLMs, defining clear complexity measures such as width, depth, and communication. It analyzes three representative task families—associative recall, state tracking, and k-hop reasoning—and characterizes their optimal trade-offs. Both upper and lower bounds are derived, showing when communication helps and when it saturates. Empirical simulations with pretrained LLMs on synthetic tasks validate the theoretical predictions and illustrate the regimes where multi-agent protocols are beneficial.", "questions": "- Have you considered running simulations on more realistic tasks—such as multi-document summarization or noisy graph QA—to test whether the theoretical trade-offs observed in your framework persist in practical, large-scale reasoning settings?\n- How would your theoretical bounds change (if at all) when agents are allowed to overlap input chunks (i.e., share some context) or when messages can be multi-token (not just one token)? Have you thought about generalising to that regime, and do you expect qualitatively new regimes?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper lays out a clean formal model for multi-agent reasoning in LLM settings, making the resource trade-offs (width/depth/comm) precise.\n-It analyzes three task families with sharp trade-offs, and the table does a good job of clearly summarizing the regimes.\n- Both upper and lower bounds are provided in addition to constructions.", "weaknesses": "The paper does not include simulations on realistic tasks such as multi-document summarization or noisy graph question-answering, so it remains unclear how well the proposed framework extends to complex, real-world reasoning settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zR2NL4rjWs", "reviewer": "Reviewer_YPeN", "summary": "This paper aims to resolve: When and how does inter‑agent communication provably help LLM multi‑agent reasoning as problem size and context scale?  CoT and test‑time compute improve reasoning but degrade with long contexts; recent multi‑agent systems split tasks, yet their expressive capacity and resource tradeoffs lack theory. The work targets principled guidance for scalable designs by formalizing multi‑agent protocols as Transformer‑computable DAGs with size, computation depth (wall‑clock proxy), and communication budget, and asks for achievable/necessary tradeoffs across tasks.", "questions": "I'd like to discuss a few points with the authors:\n\nMulti-token messages. Your proofs assume single-token communication, and you mention that extension to bounded-length words is \"straightforward\" (Section 3). Could you clarify how the depth and communication lower bounds would change when messages are b-token words? Specifically, how do the results differ when b is constant versus when b = O(log N)?\n\nRobustness to asynchrony and failures. What happens if workers reply at different times or occasionally drop messages? Can the Conservation-of-size argument and Proposition 4.2 be recovered under such conditions, or does this break the O(1) single-agent simulation result? (Related to Appendix C.2)\n\nPractical cost model. The figures show \"computation depth\" versus \"communication edges,\" which are clean theoretical metrics. Could you provide a cost model that maps these to concrete latency (in terms of round-trips) and FLOPs? This would help designers choose w(N) under realistic compute budgets when implementing these protocols. (Related to Figure 6 and Appendix E)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Clear and actionable formalization (Section 3). The paper models multi-agent systems as Transformer-computable labeled DAGs and defines three concrete metrics: Depth(N), Size(N), and communication budget. Definitions 3.1–3.3 make the theoretical analysis both reproducible and extensible. This formalism is a valuable contribution to the emerging theory of LLM-based multi-agent systems. The approach seems inspired by work on GNN+MARL, such as https://arxiv.org/abs/2210.13148.\n\nProposition 4.1 (Conservation of size) and Proposition 4.2 (bounded communication implies O(1) single-agent CoT) together identify three feasible operating regimes. Importantly, they rule out the appealing but impossible scenario of \"O(1) communication with strong depth reduction.\" The accompanying figure and discussion in Section 4.1 and Figure 2 are clear and immediately applicable to system design.\n\nProtocol designs with matching bounds. The paper demonstrates that O(1) depth and communication is achievable (Proposition 4.3), providing formal justification for simple manager-worker designs on retrieval tasks (page 6). For more complex tasks, prefix-sum-style cascades achieve depth O(log w + N/w) with optimal communication Θ(w) and size Θ(N). The lower bounds in Proposition 4.7 match these upper bounds up to logarithmic factors (pages 6–7).\n\nThe experiments mirror the theoretical predictions well, which strengthens confidence in the framework's soundness. Figures 3–5 and the additional results in Appendix E (Figures 6–9) all align with the theoretical characterizations.", "weaknesses": "Idealized communication model. The theoretical model assumes single-token messages and uses a UHAT-style assumption. The proofs in Appendix C.2 rely on these idealizations to obtain the O(1) depth equivalences. It would strengthen the work to discuss robustness when messages span multiple tokens and agents don't perfectly adhere to the protocol. How much do the bounds degrade in more realistic settings?\n\nDepth lower bounds may underestimate practical costs. The authors acknowledge that instruction-following overhead (extra boilerplate tokens) affects depth lower bounds in practice (Section 5.2). However, the cost model doesn't explicitly price this overhead in terms of compute or latency units, which makes it harder to apply the theoretical predictions to real systems.\n\nLimited experimental scope. The experiments focus on synthetic tasks (recall, parity, k-hop reasoning) using Llama-3.* and EXAONE via TogetherAI. While these validate the theory, there's no evaluation on real-world long-context reasoning tasks like complex mathematical problem-solving, program synthesis, or long-document question answering. In these settings, memory management, tool use, and noisy communication patterns would provide a more complete picture of practical applicability (Section 5 & Appendix D).\n\nGap between theoretical metrics and practical deployment. While Definitions 3.1–3.3 are mathematically precise, an explicit mapping from \"edges/tokens\" to actual prompt token budgets and per-round latency would help practitioners. For example, when reading Figure 6, it would be valuable to understand how to translate the theoretical metrics into wall-clock predictions for system design.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uz3ug6pc8h", "reviewer": "Reviewer_6i2W", "summary": "This paper presents a theoretical framework for analyzing the expressivity of multi-agent systems in LLM reasoning tasks. The authors group multi-agent reasoning approaches in three algorithmic families (associative recall, state tracking, and k-hop reasoning) and propose theoretical claims on the number of agents required, the agents' communication structure, and speedups that can be achieved with respect to a problem and context size. The evaluation on synthetic benchmarks using Llama models provides the experimental evidence to support the theoretical claims.", "questions": "1. Justify the hyperparameter choices (see Weakness 2).", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The formalization of multi-agent systems as directed acyclic graphs in Definition 3.1provides a rigorous foundation for analysis. The distinction between CoT edges and communication edges is well-defined.\n2. Figure 1 effectively illustrates the three discussed communication protocols making it easier to understand the paper.\n3. The experimental results demonstrate that theoretical statements are closely aligned with practical evaluation results.", "weaknesses": "1. The Definition 3.1 states that the agents can only send/receive a single token at each time step. This restriction does not reflect the related work in multi-agent systems, where agents typically are not constrained to communicate through a single-token representation.\n2. While Appendix D provides prompts and hyperparameters, some choices lack justification. For example, why 8 agents are used for majority voting, why the specific chunk sizes were chosen?\n3. The framework explicitly excludes multi-agent debate, voting mechanisms, and self-consistency approaches, which are popular in related work. While the authors justify this by focusing on expressivity rather than stochasticity-based improvements, this limits the framework's applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ohngNwSNeT", "reviewer": "Reviewer_7TtA", "summary": "This paper studies the trade-off between expressive power and communication cost in multi-agent reasoning systems.", "questions": "1. How do the three types of protocols degrade under message loss/delay/content error? Can you provide an upper bound for noisy communication (e.g., converting O(k) rounds into a success probability with an error rate ε)?\n\n2. Does the main proposition still maintain optimality under soft attention, finite precision, and fixed width?\n\n3. Can you provide the token overhead required for training and inference in a specific scenario?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The ternary structure of Size/Depth/Communication is used to characterize the \"cost of scalability\" in multi-agent reasoning, and an \"impossible zone\" is proved: when communication is O(1), it is impossible to reduce the depth to O(Size/w) as the number of agents increases (Proposition 4.2). This has significant implications for system design.\n\n2. Section 3.1 and the discussion section map the three theoretical intervals to existing pipelines (such as CoA, LLM×MapReduce, LongAgent, hierarchical merging, etc.), making them operable.", "weaknesses": "1. The dataset is primarily synthetic and lacks specific comparisons on real-world document question answering, complex RAGs, or graph reasoning tasks.\n\n2. The robustness to noise and instruction following failure is only explained in §5.2 as a phenomenon of \"constant extra token overhead\", lacking a systematic analysis.\n\n3. Without integrating these protocols into actual multi-agent systems, it is impossible to observe their true guidance for MAS systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)