StreamMA: Streaming Communication in Multi-Agent Reasoning

> Paper: Streaming Communication in Multi-Agent Reasoning > Authors: Zhen Yang, Xiaogang Xu, Wen Wang, Cong Chen, Xander Xu, Ying-Cong Chen > Published: 2026-06-03, arXiv:2606.05158 > Institutions: HKUST (Guangzhou), Alibaba, Zhejiang University > Project page: https://zhenyangcs.github.io/StreamMA-website/ > Code: https://github.com/EnVision-Research/StreamMA

The Counterintuitive Finding

Multi-agent systems typically follow "generate-then-transfer": the upstream agent finishes its full reasoning chain before passing it downstream. Latency grows linearly with agent count, but the assumption is that downstream agents benefit from complete context.

The StreamMA authors argue this is wrong. Their change is simple: forward each reasoning step to downstream agents the moment it is produced, forming a pipeline. The result: lower latency *and* higher accuracy — an average of +7.3 percentage points, and up to +22.4 pp (Claude Opus 4.6-high on HMMT 2026: Serial 63.26% → StreamMA 85.61%).

Why Full Context Can Be Harmful

LLM reasoning quality is uneven across steps. Due to error accumulation, early steps tend to be reliable (e.g., ~90% correct) while later steps — built on earlier mistakes — degrade (e.g., ~40%). Serial mode forces downstream agents to consume a mixture of high- and low-quality steps, where the noisy tail misleads them.

Core insight: more context is not necessarily better — what matters is when it arrives.

The Streaming Approach

• Serial: Agent A writes all steps → transfers to B → B starts.
• StreamMA: A writes Step 1 → B receives it immediately → B starts reasoning while A continues writing.

All agents run in parallel. Downstream agents form their own reasoning trajectories from the reliable early steps, so they are less influenced when unreliable later steps arrive.

A controlled experiment confirms the mechanism:

| Upstream output | Stream | Serial | Gap | |---|---|---|---| | ✓✓✓× (tail error) | 91.0% | 67.0% | +24.0 | | ×✓✓✓ (head error) | 63.0% | 97.0% | −34.0 |

The asymmetry shows StreamMA exploits the structure of multi-step LLM reasoning: early steps are more reliable.

Three Closed-Form Theorems

Theorem 1: Effectiveness Ordering

With per-step correctness p_j, three averages are defined: p̄ (uniform), p_head (head-weighted), p_tail (tail-weighted). Across six cases, streaming is optimal when p_head > p* and p_tail < p* — exactly the regime of multi-step LLM reasoning with error accumulation.

Theorem 2: Speedup Bound

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

With A = S = 64: theoretical max 32.3×; measured 26.9× (83% of bound).

Theorem 3: Cost Ratio

Stream/Serial cost ratio ≈ 0.925 in typical settings; with KV-cache hits, 0.58 (42% savings).

Evaluation: 8 Benchmarks, 2 Models, 3 Topologies

• Benchmarks: AIME 2025/2026, HMMT 2026, GPQA-Diamond, HLE, LCB-G/E/T
• Models: Claude Opus 4.6 (high), GPT-5.4 (medium)
• Topologies: Chain, Tree, Graph

Claude Opus 4.6 (High), average across benchmarks:

| Topology | Serial | StreamMA | Gain | |---|---|---|---| | Chain | 73.48% | 81.70% | +8.22 pp | | Tree | 79.43% | 82.81% | +3.38 pp | | Graph | 72.92% | 83.34% | +10.42 pp |

Gains are inversely correlated with Serial baseline strength. Largest single-benchmark gain: HMMT 2026, Chain, Claude Opus 4.6-high (+22.35 pp). GPT-5.4 gains are smaller (+1.5 pp) because baselines are already near ceiling.

Cost–Accuracy Pareto Dominance

Using actual Claude Opus 4.6 pricing ($5/$25/$0.50 per MTok for input/output/cache):

| Configuration | Cost | Accuracy | |---|---|---| | Stream × 4 | $2.75 | 90.9% | | Serial × 16 | $5.46 | 89.4% | | Stream × 1 (full cache) | $0.34 | 78.8% | | Serial × 1 | $0.40 | 70.5% |

Stream × 4 beats Serial × 16 at roughly half the cost — strictly Pareto-dominant.

Step-Level Scaling Law

A notable discovery: increasing per-agent step count (S) improves both accuracy and speed under streaming — the opposite of the usual "more steps = slower" intuition, because more steps means more pipeline parallelism.

On HMMT 2026 (GPT-5.4-medium):

| Configuration | Accuracy | Speedup | |---|---|---| | A=2, S=auto | 58.3% | baseline | | A=64, S=auto | 68.2% | — | | A=64, S=64 | 73.5% | 26.9× |

This is a new scaling dimension, orthogonal and composable with agent-count scaling.

Practical Takeaways

1. Latency and accuracy are not a trade-off here — faster can be more accurate in multi-agent settings. 2. Don't wait for upstream to finish. Streaming only changes the communication protocol, not the models or topology. 3. KV-cache matters. StreamMA's cost savings rely on prefix-shared cache reuse; add caching first. 4. Chain topology benefits most (lowest Serial baseline there). 5. Not universal: if errors appear in *early* steps, StreamMA can underperform — but for typical multi-step LLM reasoning, it usually wins.

Limitations

1. Only Claude and GPT models tested; other families unverified. 2. Only 8 benchmarks; other domains (e.g., creative writing) unexplored. 3. Only 3 static topologies; dynamic/adaptive graphs untested. 4. Theorems assume step independence; real LLMs have self-attention coupling. 5. Speedups depend on parallel execution capability.

Why It Matters

StreamMA replaces "think-then-speak" with "think-while-speak" — mirroring how human conversation actually works. By letting downstream agents engage with the most reliable information early, streaming is not just faster, but smarter. It may be the first "streaming revolution" for multi-agent systems.

Links:

• Paper: https://arxiv.org/abs/2606.05158
• Project page: https://zhenyangcs.github.io/StreamMA-website/
• Code: https://github.com/EnVision-Research/StreamMA