Source-linked AI summary
Streaming Communication in Multi-Agent Reasoning
Zhen Yang, Xiaogang Xu, Wen Wang, Cong Chen, Xander Xu, Ying-Cong Chen
TL;DR
Multi-agent systems typically wait for complete upstream responses, leaving inter-agent streaming and its effect on reasoning quality underexplored. StreamMA forwards reasoning steps immediately to pipeline agents, and across eight benchmarks it improves effectiveness while reducing latency versus serial execution.
Problem
Existing multi-agent systems generally use generate-then-transfer communication, while partial inter-agent streaming and its effect on effectiveness remain underexplored.
Method
StreamMA forwards each reasoning step immediately across agents, and formalizes effectiveness, speedup, and cost through closed-form analyses.
Results
+7.3 pp average effectiveness versus Serial across eight mathematics, science, and code benchmarks, while reducing latency.
Takeaways & Limitations
Increasing per-agent reasoning steps consistently improves both effectiveness and speedup, establishing a step-level scaling axis complementary to agent-count scaling.
Takeaways & Limitations
StreamMA is strictly preferable only for head-strong, tail-weak step-correctness profiles; serial or single execution may otherwise match or exceed it.
Abstract
from arXiv · showhide
Multi-agent reasoning systems adopt a "generate-then-transfer" paradigm that forces end-to-end latency to scale linearly with pipeline depth. We introduce StreamMA, a multi-agent reasoning system that streams each reasoning step to downstream agents as soon as it is generated, pipelining adjacent agents and thus reducing latency. Surprisingly, this pipelining also improves effectiveness: because multi-step reasoning quality is non-uniform and early steps are more reliable than later ones, working with these reliable early steps instead of the full chain prevents error-prone late steps from misleading downstream agents. We formalize both advantages with the first closed-form joint analysis of stream, serial, and single protocols, deriving the effectiveness ordering, speedup upper bound, and cost ratio. Across eight reasoning benchmarks spanning mathematics, science, and code, two frontier LLMs (Claude Opus 4.6 and GPT-5.4), and three topologies (Chain, Tree, Graph), StreamMA outperforms both baselines (avg. +7.3 pp, max +22.4 pp on HMMT 2026; Claude Opus 4.6-high). Beyond these contributions, we discover a "step-level scaling law": increasing per-agent steps consistently improves both effectiveness and efficiency, a new scaling dimension orthogonal to and composable with agent-count scaling.
1 Introduction
StreamMA replaces generate-then-transfer communication with reasoning-step streaming, enabling pipelined multi-agent execution that improves both latency and effectiveness. Its theory and experiments show consistent gains across protocols, models, topologies, and a new step-level scaling axis.
- Empirics: +7.3 pp average effectiveness gain over Serial and +22.4 pp peak gain on HMMT 2026 with Claude Opus 4.6-High accompany reduced latency.Across eight benchmarks in mathematics, science, and code, StreamMA outperforms Serial while reducing waiting.
- Mechanism: Stream benefits downstream reasoning because early steps are more reliable, whereas Serial exposes downstream agents to error-prone later steps before they form independent reasoning.Streaming lets downstream agents begin from a reliable prefix, reducing the influence of degraded late steps.
- Protocol: Stream forwards each reasoning step upon completion, replacing complete-response transfer and pipelining upstream and downstream agents over arbitrary DAG topologies.This addresses serial communication, which leaves downstream agents idle and makes latency scale with pipeline depth.
- Theory: The theory gives an effectiveness ordering, a speedup upper bound, and an exact cost ratio for Stream, Serial, and Single protocols.This is presented as the first closed-form joint analysis of the three protocols.
- Discovery: +5.3 pp effectiveness at A=64 when S scales to 64, together with 26.9× speedup, establishes step-level scaling complementary to agent-count scaling.At fixed agent count, increasing per-agent steps consistently improves effectiveness and speedup.
2 Related Work
Prior multi-agent reasoning research has advanced communication topology, granularity, and agent coordination, while streaming inference has developed within and across agents. StreamMA reframes communication around reasoning steps, leveraging position-dependent step quality to introduce per-agent step count as a new scaling axis and protocol-design principle.
- Multi-Agent Reasoning and Communication: Multi-agent reasoning has progressed along orthogonal axes including communication topology and communication granularity.StreamMA refines granularity from full responses to reasoning steps.
- Multi-Agent Reasoning and Communication: Per-agent step count is a new design axis orthogonal to agent-count scaling, with more steps improving both effectiveness and speedup.This relationship is identified as the step-level scaling law.
- Step-Level Reasoning Quality: Prior step-by-step, refinement, supervision, and debate methods improve reasoning quality, but position-dependent step reliability had not shaped inter-agent protocols.StreamMA lifts this property into protocol design through a closed-form effectiveness ordering of Single, Serial, and Stream.
- Pipeline Parallelism and Streaming Inference: Pipeline parallelism is established in distributed training, while LLM streaming inference spans intra-agent techniques and inter-agent approaches.The cited intra-agent examples include speculative decoding, Group Think, and Multi-Stream LLMs; inter-agent work includes skeleton expansion.
3 Method
StreamMA streams each generated reasoning step to concurrent downstream agents, enabling pipeline execution across chains and DAGs. Its analysis characterizes when streaming improves effectiveness and derives bounds for latency speedup and cost relative to Serial.
- 3.1 Algorithm: StreamMA uses streaming calls to push completed steps immediately, letting downstream agents process step s while upstream agents generate step s + 1.The method is analyzed on a chain of A agents, each producing S steps, with downstream calls reusing prior-step context.
- 3.2 Effectiveness: sCorr_stream > sCorr_serial > sCorr_single when early steps exceed p∗, late steps fall below p∗, and the overall mean ¯p exceeds p∗.Streaming benefits because downstream reasoning starts from reliable early steps, while degraded late steps have diluted impact; Serial still exceeds Single when the full response is on average helpful.
- 3.2 Effectiveness: sCorr_serial > sCorr_stream > sCorr_single when all steps are above p∗, whereas Single leads when upstream steps are broadly harmful.Serial benefits from complete helpful context; Single avoids harmful upstream influence when every step falls below p∗.
- 3.1 Algorithm: StreamMA extends from chains to arbitrary DAGs by broadcasting queries to source nodes and pushing each step to all direct successors without predecessor synchronization.Multi-predecessor nodes process incoming steps immediately upon arrival.
4 Results
Across benchmarks, controlled studies, roles, tools, scaling, and cost, STREAMMA consistently improves reasoning effectiveness over Serial while preserving its streaming-latency advantage. The gains are largest when Serial is weaker or errors occur in later steps, and step-level scaling adds benefits beyond agent-count scaling.
- Benchmarks: STREAMMA outperforms Single and Serial in every reported Avg. cell across eight benchmarks, three topologies, and three backbones.The evaluation spans competition mathematics, graduate-level science, and program understanding.
- Benchmarks: +7.3 pp is STREAMMA’s average accuracy lift over Serial on Claude Opus 4.6, peaking at +22.4 pp on HMMT 2026, Chain.Prompt content, decoding hyperparameters, and runtime settings remain identical to Serial apart from the streaming boundary and root-agent preamble.
- Benchmark analysis: STREAMMA’s gain increases as Serial weakens: Claude gains are +3.38 at Serial Avg. 79.43, +8.22 at 73.48, and +10.42 at 72.92.The same inverse-strength trend appears across GPT-5.4 and GLM-5.2, while near-ceiling cells move by less than 0.6 pp.
- Theorem 1 verification: Stream wins by forwarding reliable prefixes before unreliable tails: a GPQA-Diamond case has Agent2 re-derive the correct answer before the tail arrives.This behavior matches Theorem 1’s predicted Stream-advantage regime.
- Theorem 1 verification: Tail perturbations favor Stream by up to +24.0 pp, whereas head perturbations favor Serial by down to −36.0 pp.Mirror pairs reverse Stream’s gap from +24.0 to −34.0 pp, exposing the head–tail asymmetry.
- Generalization: +0.76 to +9.85 pp are STREAMMA’s improvements over Serial across all ten role–backbone cells.The result generalizes across five role protocols, varying agent counts, DAG structures, and role semantics.
- Scaling: At A=64, increasing S from auto to 64 raises accuracy from 68.2% to 73.5%, showing step-level scaling beyond agent-count scaling.The experiment sweeps A ∈ {2, 4, 8, 16, 32, 64} and S ∈ {2, 4, 8, 16, 32, 64, auto}.
5 Conclusion
STREAMMA replaces generate-then-transfer with immediate per-step forwarding in multi-agent LLM reasoning. Streaming both reduces latency and improves effectiveness because the timing of context arrival matters more than its quantity.
- STREAMMA replaces generate-then-transfer with immediate per-step forwarding for multi-agent LLM reasoning.
- Streaming reduces latency and improves effectiveness because context timing matters more than context quantity.The proposed mechanism is attributed to the non-uniform quality structure of multi-step LLM reasoning.
6 Limitation
StreamMA applies to tasks whose solutions admit step decomposition, but its stream protocol is not universally optimal. Theorem 1 identifies when streaming is strictly preferable and provides a principled protocol-selection boundary.
- Task scope: StreamMA applies to step-decomposable tasks, while open-ended creative writing and single-token classification fall outside this regime.Mathematics, code, and science generally satisfy step decomposition under chain-of-thought prompting.
- Protocol optimality: Theorem 1 finds streaming strictly preferable only for head-strong, tail-weak step-correctness profiles.Across the remaining five regimes, serial or single execution may match or outperform streaming.
- Protocol optimality: Theorem 1 provides a principled protocol selector based on agents’ step-correctness profiles.Its boundary characterizes when stream, serial, or single execution is preferable rather than weakening StreamMA.
A Appendix · Appendix Contents · A.1 Notation Summary
The appendix provides a notation summary for the theoretical analysis and organizes detailed effectiveness and speedup analyses. Its derivations use a chain topology as a running example while addressing general DAGs at the ends of proof sections.
- A Appendix: The appendix contains detailed effectiveness and speedup analyses, including proofs, practical-scenario discussion, and a numerical speedup example.The contents list A.2 Detailed Effectiveness Analysis and A.3 Detailed Speedup Analysis, with their associated subsections.
- Appendix Contents: The appendix contents include proofs of core identities, Theorem 1, and Theorem 2.These proof sections are explicitly listed under the effectiveness and speedup analyses.
- A.1 Notation Summary: Table 4 summarizes notation for the theoretical effectiveness and efficiency analyses.The efficiency analysis covers speedup and cost parameters.
- A.1 Notation Summary: The notation summary covers parameters used in the effectiveness, speedup, and cost analyses.These are the parameter categories identified for the theoretical analysis.
- A.1 Notation Summary: Appendix derivations use a chain topology as a running example.This convention is stated for the derivations in the appendix.
- A.1 Notation Summary: The theoretical analysis generalizes from the chain example to arbitrary DAGs at the end of each proof section.The passage specifies that this generalization is discussed at the end of each proof section.
A.2 Detailed Effectiveness Analysis
The analysis defines mean downstream step-level correctness as a task-effectiveness proxy and derives six sCorr orderings across stream, serial, and single modes. The preferred mode depends on how p̄, p_head, and p_tail compare with p*.
- Effectiveness metric: sCorr_mode measures mean downstream step-level expected correctness and is positively correlated with task-level accuracy.A higher fraction of correct reasoning steps makes a correct final answer more likely.
- Effectiveness Ordering: Theorem 1 partitions sCorr orderings among stream, serial, and single modes into six cases based on p̄, p_head, p_tail, and p*.The cases group into stream, serial, or single advantage regimes.
- Stream advantage: Under stream advantage, sCorr_stream exceeds both baselines; the ordering is sCorr_stream > sCorr_serial > sCorr_single when p̄ > p*, and sCorr_stream > sCorr_single > sCorr_serial when p̄ < p*.This regime requires p_head > p* and p_tail < p*.
- Serial and single advantage: Under serial advantage, sCorr_serial leads; under single advantage, sCorr_single leads, with the remaining stream-versus-baseline ordering determined by p_head or p_tail.Serial advantage requires p̄ > p* and p_tail > p*; single advantage requires p_head < p* and p̄ < p*.
A.2.1 Proof of Core Identities
The proof models downstream correctness changes from added upstream steps using gains for correct steps and losses for incorrect ones. This yields a breakeven threshold and establishes the ordering among Single, Stream, and Serial from head, mean, and tail correctness.
- Mode comparison: The three modes differ only in which upstream reasoning steps are visible when the downstream agent generates each output step.The adjacent-agent setup considers an upstream agent producing S-step reasoning and a downstream agent producing outputs.
- Expected correctness change: The expected correctness change from adding step j is µ_j = p_j(δ + ε) − ε, where δ is the gain from a correct step and ε the loss from an incorrect one.The parameters are assumed step-position-independent; the generalization uses vectors (δ_j, ε_j).
- Breakeven condition: The breakeven threshold p∗ = ε/(δ + ε) makes µ_j positive exactly when step correctness p_j exceeds p∗.Single sees no upstream steps, Stream sees a prefix, and Serial sees all S steps.
- Mode comparison: Summing the corresponding µ_j values relative to Single gives Stream and Serial step-level correctness gains, whose averages yield the sCorr gaps.Single is the baseline for both gain and gap calculations.
- Ordering theorem: The signs of the resulting comparisons depend on whether head, mean, and tail per-step correctness exceed p∗, fixing the ordering among Single, Stream, and Serial.Equality at any condition yields the corresponding equality in the ordering.
A.2.2 Proof of Theorem 1
The proof derives all six possible sCorr orderings by mapping the signs of identities (a)–(c) to conditions on phead, ¯p, and ptail relative to p∗. It also extends the argument edgewise to general DAG topologies, where upstream contributions combine additively by linearity of expectation.
- Sign-based proof: Each target sCorr ordering is obtained by inverting identities (a)–(c), whose signs determine conditions on phead, ¯p, and ptail relative to p∗.The variables are derived by the proof, with parametric definitions absorbing the resulting coefficients.
- Stream-advantage cases: The stream-advantage regimes require either ¯p > p∗ and ptail < p∗, or phead > p∗ and ¯p < p∗.These conditions yield sCorrstream > sCorrserial > sCorrsingle and sCorrstream > sCorrsingle > sCorrserial, respectively.
- Serial-advantage cases: The serial-advantage regimes occur when phead > p∗ and ptail > p∗, or when ¯p > p∗ and phead < p∗.They produce sCorrserial > sCorrstream > sCorrsingle and sCorrserial > sCorrsingle > sCorrstream, respectively.
- Single-advantage cases: The single-advantage regimes require phead < p∗ and ptail < p∗, or ¯p < p∗ and ptail > p∗.These yield sCorrsingle > sCorrstream > sCorrserial and sCorrsingle > sCorrserial > sCorrstream, respectively.
- DAG extension: For general DAG topologies, the proof applies independently to each directed edge, while multiple predecessor contributions compose additively by linearity of expectation.Thus Theorem 1 applies per edge, with each ordering determined by that edge’s phead, ¯p, and ptail.
A.2.3 Discussion of Practical Scenarios … A.12 Artifact Statement
StreamMA’s practical analysis explains when streaming wins by exploiting reliable early reasoning, and formalizes its latency and cost tradeoffs under realistic caching and serving assumptions. Case studies and implementation materials show both its corrective benefit and the risk that perturbed intermediate steps can mislead downstream agents.
- A.2.3 Discussion of Practical Scenarios: Stream beats Serial when early steps are reliable but later steps degrade, while its ranking against Single depends on whether the full-chain average is above or below p∗.Case I.a yields Stream > Serial > Single when p̄ > p∗; Case I.b yields Stream > Single > Serial when p̄ < p∗.
- A.2.3 Discussion of Practical Scenarios: Serial leads when every step helps, whereas Single leads when upstream context is broadly harmful; self-correction corresponds to a less common mixed regime.Cases II.a, III.a, and III.b establish these orderings, while Cases I.a and I.b are most frequently observed and II.b captures self-correction.
- A.3 Detailed Speedup Analysis / A.3.1 Latency of Serial Protocol / A.3.2 Latency of Stream Protocol / A.3.3 Proof of Theorem 2: The speedup theorem bounds Stream’s advantage over Serial, reaching AS/(S + A −1) when cache reads, prefill, and cached-context overheads are negligible.The derivation uses a pipelined critical path in which the first step traverses agents serially and later steps are governed by the bottleneck agent.
- A.4 Detailed Cost Analysis / A.4.1 Cost of Serial Protocol / A.4.2 Cost of Stream Protocol / A.4.3 Proof of Theorem 3: The cost theorem gives an exact Stream-to-Serial ratio, and Stream is cheaper in decode-dominated, equal-output, or sufficiently cache-efficient regimes.Under prefix caching, the stated condition is r_ccp S < 1.
- A.5 Case Study of Theorem 1 / A.9 System Prompts: The GPQA-Diamond case study shows Stream recovering gold answer B while Serial outputs incorrect D because streaming enables independent verification before harmful late steps arrive.Both protocols share Agent1’s pivotal error, but Stream’s per-step checks reject the later mistake and re-enumerate direct-neighbor proton counts.
- A.6 Step-Level Perturbation Materials / A.7 Testing Setup and Files / A.8 Stream Protocol on DAGs / A.9 System Prompts / A.11 Potential Risks / A.12 Artifact Statement: Step-level perturbations can steer downstream agents toward wrong answers, motivating verification defenses; released artifacts include evaluation configurations, DAG execution changes, and no automated perturbation tooling.The testing setup specifies OpenCompass files and GPT-5.4 as judge, while DAG execution broadcasts queries, pushes steps to successors, and avoids multi-predecessor synchronization.