Skip to content

Streaming Communication in Multi-Agent Reasoning

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Agent
Keywords: multi-agent reasoning, streaming communication, pipeline parallelism, step-level scaling law, inference acceleration

TL;DR

STREAMMA replaces the prevailing "generate-then-transfer" multi-agent protocol with step-level streaming communication, exploiting the position-dependent reliability of reasoning chains to pipeline execution for up to 26.9× speedup while preventing error-prone late steps from misleading downstream agents, boosting reasoning accuracy by an average of 7.3 percentage points across diverse benchmarks.

Background & Motivation

Multi-agent systems powered by large language models (LLMs) have established themselves as an effective paradigm for tackling complex tasks spanning formal mathematics, code synthesis, and multi-hop reasoning. In these systems, specialized agents are commonly arranged as nodes within a directed acyclic graph (DAG), propagating intermediate rationales and verification signals across edges. Despite diverse topological designs, virtually all existing frameworks operate under the same implicit communication premise: an upstream agent must finish generating its entire response before transmitting the complete text block downstream. This "generate-then-transfer" serial paradigm forces downstream agents into prolonged idle states, causing end-to-end latency to scale linearly with pipeline depth and tacitly presuming that fuller context invariably yields superior decisions.

However, the internal quality of multi-step reasoning is non-uniform across its sequential positions. Recent investigations into process supervision and token-level uncertainty reveal that upstream reasoning steps exhibit distinct position dependency: early reasoning steps are generally rigorous and highly reliable, whereas later steps suffer from accumulated hallucinations, arithmetic drift, and cognitive distraction. In standard serial execution, downstream agents must condition on the entire upstream response, exposing them directly to these degraded tail steps and triggering destructive error cascading. In contrast, streaming each reasoning step downstream the moment it is finished allows the receiver to begin reasoning immediately on clean, reliable initial premises; by the time flawed trailing steps eventually arrive, the downstream agent has already established an independent, robust reasoning trajectory, naturally diluting the corruptive influence of late-stage errors.

Recognizing that when context arrives can matter more than how much context arrives, this paper rethinks the fundamental communication granularity between agents. The core idea is to shift the transmission unit from complete responses to individual reasoning steps, pipelining upstream generation and downstream processing over arbitrary DAGs to both dilute late-stage reasoning errors via reliable early prefixes and achieve substantial latency speedups.

Method

Overall Architecture

STREAMMA orchestrates step-level streaming execution across arbitrary DAG topologies \(G=(V, E)\). At system initialization, the input problem \(Q\) is broadcast to all source agents (nodes with in-degree 0). All agent nodes execute concurrently in the background. Upstream agents are prompted to emit an explicit delimiter (such as END_STEP) upon completing each coherent reasoning step. The moment a step finishes, it is pushed non-blockingly into the FIFO input queues of all immediate successor agents without waiting for subsequent steps. Downstream agents ingest incoming steps as they arrive, immediately updating their context and advancing their own reasoning. This sequential appending naturally forms a shared context prefix across iterations, maximizing KV-cache reuse in modern inference serving engines.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    Input["Input Query Q<br/>Broadcast to DAG source nodes"] --> StepStream["Step-Level Streaming & Pipeline Execution<br/>Forward step upon completion / eliminate idle wait"]
    StepStream --> PrefixDilution["Prefix Noise Immunity & Reasoning Dilution<br/>Condition on reliable head / dilute degraded tail"]
    PrefixDilution --> ScalingServing["Step-Level Scaling & Cache-Aware Serving<br/>Scale per-agent steps S / KV-cache reuse cuts cost"]
    ScalingServing --> Output["Output Final Response<br/>High accuracy paired with low latency"]

Key Designs

1. Step-Level Streaming & Pipeline Execution: Breaking the Serial Transmission Bottleneck To eliminate the severe downstream idle latency inherent to blocking API calls in the serial paradigm, STREAMMA shifts the inter-agent transmission unit to individual reasoning steps. During generation, an upstream agent pushes each completed step (demarcated by END_STEP) directly into the successor's FIFO queue. The downstream agent begins computing immediately, overlapping its processing of step \(s\) with the upstream agent's generation of step \(s+1\). For a chain of \(A\) agents with each producing \(S\) steps, once the first step traverses the pipeline, all subsequent steps execute concurrently with latency governed only by the bottleneck stage. The theoretical latency speedup over serial execution is upper-bounded by:

\[\text{Speedup} = \frac{A(S + r_{po})r_{vdp} + S}{(S + A - 1)(1 + \alpha r_{vdp} + \beta r_{vdc})}\]

where \(r_{vdp} = v_d / v_p\) and \(r_{vdc} = v_d / v_c\) denote decode-to-prefill and decode-to-cache-read speed ratios, \(r_{po} = \bar{P}/\bar{O}\) represents the prompt-to-per-step-output length ratio, and \(\alpha, \beta\) capture uncached and cached context tokens per output token. Under typical serving regimes where cache reads and prefill are orders of magnitude faster than decode (\(v_c \gg v_p \gg v_d\), meaning \(r_{vdp} \to 0\) and \(r_{vdc} \to 0\)), the speedup upper bound simplifies to:

\[\text{Speedup} \le \frac{AS}{S + A - 1}\]

This closed-form formulation demonstrates that STREAMMA breaks the linear latency scaling barrier of deep agent pipelines, turning deep multi-agent collaboration into an operationally viable low-latency workflow.

2. Prefix Noise Immunity & Reasoning Dilution: Exploiting Step Quality Asymmetry Addressing the phenomenon where late-stage reasoning errors mislead downstream agents in serial communication, this design establishes temporal noise immunity. Let step \(j \in \{1, \dots, S\}\) have correctness probability \(p_j\). A correct step provides expected benefit \(\delta > 0\), while an incorrect step inflicts harm \(\varepsilon > 0\). The expected step-correctness change from step \(j\) is \(\mu_j = p_j\delta - (1-p_j)\varepsilon\), which is positive if and only if \(p_j > p^* \triangleq \frac{\varepsilon}{\delta + \varepsilon}\). Downstream step correctness \(s\text{Corr}\) reflects the cumulative expectation over visible steps. Theorem 1 establishes the exact ordering among Stream, Serial, and Single modes according to the relationship of the uniform mean \(\bar{p}\), head-weighted mean \(p_{\text{head}}\), and tail-weighted mean \(p_{\text{tail}}\) relative to \(p^*\).

In complex multi-step reasoning, the predominant empirical profile is head-strong and tail-weak (Case I: \(p_{\text{head}} > p^*\) and \(p_{\text{tail}} < p^*\)). Under the serial protocol, the downstream agent must digest the entire rationale including degraded tail steps. Under the stream protocol, the agent immediately absorbs the reliable prefix (\(p_j > p^*\)) and initiates independent derivation; by the time the unreliable late steps (\(p_j < p^*\)) arrive, the downstream agent's own cognitive path has already crystallized, diluting the corruptive influence of late-stage errors. Theorem 1 proves: - When the overall rationale is helpful on average (\(\bar{p} > p^*\)), the ordering is \(s\text{Corr}_{\text{stream}} > s\text{Corr}_{\text{serial}} > s\text{Corr}_{\text{single}}\) (Case I.a); - When trailing errors overwhelm the overall rationale (\(\bar{p} < p^*\)), the ordering becomes \(s\text{Corr}_{\text{stream}} > s\text{Corr}_{\text{single}} > s\text{Corr}_{\text{serial}}\) (Case I.b).

This formal proof explains why receiving partial, timely information regularly outperforms receiving complete but delayed rationales.

3. Step-Level Scaling Law & Cache-Aware Serving: Orthogonal Compute Scaling with Cost Efficiency Prior work scaled multi-agent reasoning predominantly along the agent-count axis \(A\), while leaving step granularity to model discretion (\(S=\text{auto}\)), which tends to be coarse. This paper uncovers a complementary "step-level scaling law": at fixed agent count \(A\), prompting models to expand the per-agent step count \(S\) systematically improves task effectiveness while pushing pipeline parallelism toward the theoretical maximum \(\frac{AS}{S+A-1}\).

To prevent multiple intermediate API invocations from inflating serving expenses, STREAMMA structures successive calls to share growing prefixes, fully unlocking modern prefix-caching capabilities (e.g., vLLM, SGLang). The exact cost ratio between Stream and Serial is:

\[\frac{\text{Cost}_{\text{stream}}}{\text{Cost}_{\text{serial}}} = \rho \cdot \frac{r_{cpd}(\alpha + r_{ccp}\beta) + 1}{r_{cpd}(1 + r_{po}/S) + 1}\]

where \(\rho\) is the output token ratio, \(r_{cpd} = c_p/c_d\) is the prefill-to-decode price ratio, and \(r_{ccp} = c_c/c_p\) is the cache-to-prefill price ratio. Because decode pricing dominates modern APIs (\(c_d \gg c_p \gg c_c\)), evaluating Claude Opus 4.6 pricing (\(c_p=\$5, c_d=\$25, c_c=\$0.50\) per million tokens) with \(A=4, S=4\) yields a cost ratio of \(0.925\rho\). When output token volumes are comparable (\(\rho \approx 1\)), Stream is actually 7.5% cheaper than Serial while delivering 2.30× speedup, refuting the assumption that streaming incurs financial overhead.

A Worked Example

Consider question #98 from GPQA-Diamond, which asks to identify an unknown carboxylic acid from FTIR (broad band at 3000 cm\(^{-1}\), strong carbonyl at 1700 cm\(^{-1}\)) and \(^1\text{H}\) NMR splitting patterns showing one doublet of triplets of quartets (DTQ) and one doublet of triplets of triplets (DTT) among four candidates (A, B, C, D).

  • Serial Execution Trace: Agent 1 generates an 8-step rationale. Steps 1–2 correctly confirm the carboxylic acid functionality and identify two non-equivalent methine protons. However, at Step 4, Agent 1 commits a pivotal conceptual error: it asserts that ethyl-substituted methines cannot yield a clean quartet, eliminating the correct candidate B en bloc. In Steps 5–7, Agent 1 invents non-physical long-range coupling to force option D. When Agent 2 receives the full 8-step response, it points out the suspect long-range phrasing but uncritically adopts the en-bloc elimination of B from the upstream context, concluding with incorrect answer D.
  • STREAMMA Execution Trace: As soon as Agent 1 completes Steps 1–2, Agent 2 receives this clean prefix and immediately initiates independent structural validation. Armed with the reliable premise that two distinct methines must reproduce DTQ and DTT, Agent 2 rigorously enumerates vicinal coupling partners across all four molecules. When Agent 1's flawed Step 4 and fabricated Step 7 arrive, Agent 2 has already established that option B's left methine couples to a chain-terminal methyl (3H), an ethyl methylene (2H), and the neighboring methine (1H), perfectly matching DTQ, while its right methine matches DTT. Agent 2 rejects the flawed upstream exclusion and confidently returns gold answer B.

Key Experimental Results

Main Results

Evaluation spans eight demanding benchmarks across competition mathematics (AIME 2025/2026, HMMT 2026), science (GPQA-Diamond, HLE), and code comprehension (LiveCodeBench: LCB-G generation, LCB-E execution, LCB-T test output) across three frontier backbones (Claude Opus 4.6-High with thinking, GPT-5.4-None, GLM-5.2-None) and three canonical DAG topologies (Chain, Tree, Graph). All cells average 3 runs (8 runs on AIME and HMMT due to small test sets):

Model Topology Method AIME25 AIME26 HMMT26 GPQA-D HLE LCB-G LCB-E LCB-T Avg. Accuracy (%)
Claude Opus 4.6 – Single 67.50 60.00 48.11 83.67 18.60 90.25 77.94 84.31 66.30
Claude Opus 4.6 Chain Serial 80.42 72.08 63.26 85.86 23.90 91.33 78.64 92.38 73.48
Claude Opus 4.6 Chain STREAMMA 92.50 89.58 85.61 87.37 26.97 91.50 84.41 95.63 81.70 (+8.22)
Claude Opus 4.6 Tree Serial 86.25 86.25 75.00 85.18 24.82 91.92 88.45 97.59 79.43
Claude Opus 4.6 Tree STREAMMA 93.34 87.92 82.20 85.86 25.07 94.00 94.57 99.55 82.81 (+3.38)
Claude Opus 4.6 Graph Serial 77.92 71.67 61.75 85.69 22.17 90.08 75.78 98.27 72.92
Claude Opus 4.6 Graph STREAMMA 95.83 87.92 82.58 86.53 27.68 92.17 95.27 98.72 83.34 (+10.42)
GPT-5.4 – Single 55.83 71.25 40.53 77.95 12.08 91.08 92.48 96.68 67.24
GPT-5.4 Chain Serial 60.00 70.42 54.55 75.08 14.66 90.08 97.43 99.02 70.16
GPT-5.4 Chain STREAMMA 61.25 72.50 59.10 80.30 14.94 91.17 99.30 99.47 72.25 (+2.09)
GPT-5.4 Tree Serial 59.17 75.83 56.07 76.77 14.83 88.33 93.81 99.25 70.51
GPT-5.4 Tree STREAMMA 62.08 75.83 58.34 78.12 15.74 89.50 94.78 99.17 71.70 (+1.19)
GPT-5.4 Graph Serial 60.00 74.17 52.65 78.45 14.04 92.25 99.51 98.80 71.23
GPT-5.4 Graph STREAMMA 62.50 75.42 56.44 79.63 16.13 93.08 99.79 99.32 72.79 (+1.56)
GLM-5.2 – Single 40.42 44.17 32.19 69.02 7.83 80.08 70.77 78.05 52.82
GLM-5.2 Chain Serial 61.25 65.84 57.20 77.61 12.13 85.92 76.34 97.36 66.71
GLM-5.2 Chain STREAMMA 75.42 78.75 67.05 79.63 15.18 89.67 75.71 97.66 72.38 (+5.67)
GLM-5.2 Tree Serial 61.25 64.17 48.11 76.94 12.31 87.75 83.09 96.15 66.22
GLM-5.2 Tree STREAMMA 76.25 80.83 65.16 79.13 16.17 88.92 84.13 96.61 73.40 (+7.18)
GLM-5.2 Graph Serial 52.92 61.67 50.76 77.27 11.94 85.67 74.53 96.00 63.85
GLM-5.2 Graph STREAMMA 73.75 84.17 65.16 77.94 15.12 89.25 77.87 97.29 72.57 (+8.72)

Ablation & Deep Dives

1. Step-Level Scaling Law Grid
On HMMT 2026 with GPT-5.4-None, sweeping agent count \(A \in \{2, 4, 8, 16, 32, 64\}\) and per-agent steps \(S \in \{2, 4, 8, 16, 32, 64, \text{auto}\}\) over 4 independent runs:

Agent Count \(A\) \(S=2\) Acc (%) \(S=4\) Acc (%) \(S=8\) Acc (%) \(S=16\) Acc (%) \(S=32\) Acc (%) \(S=64\) Acc (%) \(S=\text{auto}\) Acc (%) Measured Speedup (\(S=64\)) Upper Bound Speedup
\(A=2\) 51.5 49.2 57.6 59.1 61.4 63.6 58.3 1.95× 1.97×
\(A=4\) 59.9 62.1 61.4 64.4 62.9 62.1 62.9 3.82× 3.82×
\(A=8\) 62.9 62.9 68.2 68.9 65.2 68.9 62.9 7.15× 7.21×
\(A=16\) 62.9 64.4 66.7 74.3 69.7 75.0 66.7 13.5× 13.0×
\(A=32\) 65.9 67.4 68.2 72.0 73.5 69.7 67.4 21.4× 21.6×
\(A=64\) 68.9 66.7 67.4 68.2 72.0 73.5 68.2 26.9× 32.3×
Marginal Avg 62.0 62.1 64.9 67.8 67.4 68.8 64.4 – –

2. Controlled Step-Level Perturbation Analysis (Validating Theorem 1)
On a 2-agent chain (\(S=4\) steps), systematically swapping clean and perturbed steps into Agent 1 across 100 runs per pattern:

Perturbation Family Step Pattern (Steps 1–4) Theorem 1 Regime Serial Acc (%) Stream Acc (%) Gap (pp)
Tail Perturbed clean-clean-clean-pert Case I.a 67.0 91.0 +24.0
Tail Perturbed clean-clean-pert-pert Case I.a 63.0 82.0 +19.0
Tail Perturbed clean-pert-pert-pert Case I.b 76.0 81.0 +5.0
Head Perturbed pert-clean-clean-clean Case II.b 97.0 63.0 -34.0
Head Perturbed pert-pert-clean-clean Case II.b 100.0 64.0 -36.0
Head Perturbed pert-pert-pert-clean Case III.b 98.0 65.0 -33.0

Key Findings

  • Gain Scales Inversely with Serial Baseline Strength: Across all backbones and topologies, STREAMMA provides the largest improvements on tasks where Serial struggles (e.g., +22.4 pp on HMMT 2026 with Claude Chain, baseline 63.26%), whereas near ceiling performance (LCB-T with GPT-5.4 at ~99%) gains compress to <0.6 pp, exactly matching the theoretical prediction of Theorem 1.
  • Strict Empirical Asymmetry between Head and Tail: In controlled perturbation, corrupting only the tail leaves Stream ahead by up to +24.0 pp due to prefix noise dilution; inverting the perturbation to the head flips the gap to -36.0 pp, verifying Theorem 1's boundary conditions.
  • Orthogonal Scaling Power: Scaling agent count \(A\) from 2 to 64 improves HMMT accuracy from 58.3% to 68.2%; simultaneously scaling step count \(S\) from auto to 64 further boosts accuracy to 73.5% alongside a 26.9× empirical speedup (reaching 83% of the theoretical upper bound).
  • Strict Pareto Frontier Dominance: When using multi-replica majority voting, Stream×4 (\(2.75 cost, 90.9% accuracy) outperforms Serial×16 (\)5.46 cost, 89.4% accuracy) with half the total cost despite running 4× fewer replicas.

Highlights & Insights

  • Turning Communication Latency into Error Resistance: Where distributed systems traditionally view communication latency as an operational friction, this work demonstrates that the temporal order of information arrival functions as a natural noise filter, turning early delivery into reasoning robustness.
  • Unified Closed-Form Triad: The paper introduces the first complete closed-form analytical triad encompassing effectiveness ordering (Theorem 1), latency speedup bounds (Theorem 2), and exact serving cost ratios (Theorem 3).
  • Unlocking the Step Dimension in Agent Systems: The discovery that LLMs default to suboptimal coarse step counts (\(S=\text{auto}\)) when collaborating, and that explicitly prompting for finer step granularity unlocks massive complementary gains in both reasoning depth and pipeline parallelism, provides a practical recipe for agent engineers.

Limitations & Future Work

  • Dependency on Step-Decomposable Tasks: STREAMMA requires tasks amenable to sequential step decomposition (e.g., mathematics, coding, science); atomic classification or single-token completion benchmarks cannot benefit from step-level pipelining.
  • Vulnerability to Corrupted Head Steps: If an upstream model hallucinates catastrophically from Step 1, downstream agents can form premature flawed commitments before corrections emerge (Case II/III); integrating adaptive streaming confidence gates is an important next step.
  • Heterogeneous Model Pipelining: Current experiments focus on homogeneous LLM backbones; exploring elastic step boundaries across heterogeneous model pairs (e.g., edge small models feeding cloud reasoning models) remains open.
  • vs. Graph Topology Optimization (GPTSwarm, AFlow): Prior topological methods optimize inter-agent edges and routing, but pass monolithic text blocks along those edges; STREAMMA operates orthogonally at the sub-node message transmission granularity.
  • vs. Skeleton-of-Thought & Speculative Agent Execution: While prior streaming efforts viewed partial output generation strictly as a latency optimization trick, STREAMMA proves that step-level streaming fundamentally enhances reasoning effectiveness by dampening error propagation.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Inverting the common intuition that complete context is strictly superior, formulating step-level streaming and the step-level scaling law.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorous coverage across 8 benchmarks, 3 major models, 3 topologies, formal mathematical proofs, and micro-level perturbation probes.
  • Writing Quality: ⭐⭐⭐⭐⭐ Seamlessly integrates motivation, closed-form theoretical proofs, and empirical validation into an exemplary narrative.
  • Value: ⭐⭐⭐⭐⭐ Delivers immediate operational value for reducing serving latency and API costs while boosting agent reasoning accuracy.