StreamMA: Pipelining Multi-Agent Reasoning by Streaming Partial Results

Paper: 2606.05158 Authors: Zhen Yang, Xiaogang Xu, Wen Wang, Cong Chen, Xander Xu, Ying-Cong Chen Categories: cs.CL, cs.AI, cs.MA

The Gap

Multi-agent reasoning systems like Chain-of-Thought with multiple LLMs have adopted a serial “generate-then-transfer” paradigm: Agent 1 completes its full reasoning chain, then Agent 2 starts working on the complete output, and so on. This creates two problems. First, latency scales linearly with pipeline depth—each agent is a blocking stage. Second, when Agent 1 produces a long reasoning chain, errors accumulate toward the end, but Agent 2 must consume the entire chain including the unreliable tail.

Prior work focused on scaling agent count or improving individual reasoning quality, but ignored the pipeline structure itself. No one asked: what if agents could start working before their upstream dependency finishes?

Problem: Serial multi-agent pipeline
    |
    v
Observation: Early reasoning steps > late steps in quality
    |
    v
Hypothesis: Streaming partial results enables pipelining + filters bad steps
    |
    v
Method: StreamMA (stream each step as generated)
    |
    v
Evidence: -47% latency, +7.3pp accuracy across 8 benchmarks
    |
    v
Conclusion: Pipelining is both faster AND more effective

The Increment

One sentence: Before this paper, multi-agent systems blocked on full reasoning chains; after it, agents pipeline by consuming partial chains as they stream, gaining both speed and accuracy.

Core Mechanism

StreamMA replaces end-to-end generation with step-by-step streaming. When Agent 1 generates reasoning step 1, it immediately forwards that step to Agent 2 while continuing to generate step 2. Agent 2 starts processing step 1 before Agent 1 finishes the full chain. This continues recursively: Agent 2’s first output step streams to Agent 3, and so on.

The system has three key components. A step detector identifies reasoning step boundaries in the token stream (e.g., recognizing “Step 1:”, “Therefore,” or numbered items). A forward buffer holds completed steps and triggers downstream transmission. A consumption scheduler decides when downstream agents should start—either immediately upon receiving the first step (eager mode) or after accumulating a few steps (buffered mode).

Data flows like this: Agent 1 generates tokens → step detector identifies boundary → forward buffer releases step k → Agent 2 receives step k and begins processing → Agent 2’s step detector identifies its own boundaries → forward buffer releases to Agent 3. Each agent maintains its own generation thread and consumption thread, decoupling upstream latency from downstream progress.

Structural metaphor: Think of a restaurant kitchen with multiple stations (prep, grill, plating). Traditional multi-agent systems work like waiting for the entire prep station to finish chopping all vegetables before the grill station can start cooking anything. StreamMA is like mise en place pipelining: as soon as the prep station finishes chopping the first ingredient, it slides the cutting board to the grill station, which starts cooking immediately while prep continues chopping the next ingredient. The plating station doesn’t wait for all cooking to finish—it starts arranging the first cooked item while others are still on the grill. Each station works in parallel, and faster turnover means diners get served sooner. The surprise: this also improves quality, because if the prep station gets sloppy toward the end (say, unevenly chopped garlic), those bad ingredients arrive late and can be caught or adjusted by downstream stations, rather than being mixed into a single batch that ruins the whole dish.

Key Concepts

• Step-level granularity: Traditional systems operate at task-level granularity—Agent 1 outputs a complete solution, Agent 2 consumes it whole. StreamMA operates at step-level granularity—Agent 1 outputs “Step 1: Define variables”, Agent 2 starts working with just that. This is like the difference between shipping a finished product versus shipping components as they roll off the assembly line. Finer granularity enables parallelism but requires identifying clean boundaries. The paper uses heuristics (numbered steps, logical connectives) and optionally trains a boundary detector.

• Quality non-uniformity in reasoning chains: Not all steps in a reasoning chain are equally reliable. Empirically, early steps (problem setup, variable definitions, initial constraints) have higher accuracy because they’re more constrained by the problem statement. Late steps (algebraic manipulation, edge case handling) accumulate errors from earlier mistakes and introduce new errors through complex operations. StreamMA exploits this by letting downstream agents work with reliable early steps before the full chain completes. If Agent 1’s step 5 contains an error, Agent 2 has already correctly processed steps 1-4, whereas in serial mode, Agent 2 would wait and then consume the entire error-prone chain.

• Closed-form latency analysis: The paper derives exact formulas for end-to-end latency under different protocols. For a chain of n agents where each generates k steps at rate r tokens/sec, serial latency is n × k/r (agents run sequentially). StreamMA latency is k/r + (n-1) × 1/r (first agent generates all k steps, then each subsequent agent adds only 1 step of delay because they start early). The speedup approaches n as k grows—adding more reasoning steps increases the benefit of pipelining. This is a rare closed-form result in LLM systems research, making the tradeoffs transparent.

Framework Shift

Before (serial generate-then-transfer):

Agent 1:  [========== generate all 10 steps ==========]
                                                        |
Agent 2:                                                [===== generate 5 steps =====]
                                                                                      |
Agent 3:                                                                              [=== gen 3 ===]

Timeline: |-------- A1 --------|----- A2 -----|-- A3 --|
Latency:  t1 = 10/r            t2 = 5/r       t3 = 3/r
Total:    18/r


After (StreamMA streaming):

Agent 1:  [Step1][Step2][Step3][Step4]...[Step10]
            |      |      |      |          |
Agent 2:    [S1   ][S2   ][S3   ][S4   ][S5   ]
              |      |      |      |      |
Agent 3:      [S1  ][S2  ][S3  ]

Timeline: |-- A1 starts --|
          |  A2 starts (after 1 step delay)
          |    A3 starts (after 1 step delay from A2)
Latency:  10/r + 1/r + 1/r = 12/r

Speedup:  18/12 = 1.5x

From blocking sequential execution to overlapping pipelined execution, the core shift is treating reasoning as a stream of incremental units rather than a monolithic output.

Expert Assessment

Problem choice: Real gap. Multi-agent systems are increasingly popular (ReAct, AutoGPT, MetaGPT), and latency is a first-order concern for production deployment. The observation that streaming could improve *both speed and accuracy is non-obvious—most streaming work trades quality for latency. The step-quality hypothesis is empirically grounded (they measure step-wise accuracy decay) rather than assumed.

Method maturity: Elegant in its simplicity. The core idea—stream partial results—requires minimal changes to existing multi-agent frameworks. The step detector is heuristic-based (regex on numbered steps), which feels brittle but works across diverse reasoning formats. A learned boundary detector would be more robust but adds complexity. The closed-form analysis is a major strength, rare in empirical LLM papers. One overlooked angle: what about error propagation? If Agent 1’s step 3 is wrong, Agent 2 builds on it immediately, potentially amplifying the error. The paper shows net improvement but doesn’t decompose when streaming helps versus hurts.

Experimental integrity: Baselines are fair—serial multi-agent and single-agent with extended reasoning. Eight benchmarks spanning math (MATH, AIME), science (GPQA), and code (HumanEval) provide breadth. Two frontier models (Claude Opus 4.6, GPT-5.4) and three topologies (chain, tree, graph) test generalization. The numbers are large: +22.4pp on HMMT 2026 is striking. One red flag: all experiments use the same step detector heuristics. Would a learned detector change the ranking? The cost analysis (API tokens) is honest—StreamMA uses more tokens due to overlapping generation, but the speedup justifies it.

Writing quality: Introduction and core mechanism are crisp. The closed-form analysis section is dense—burying key intuitions in lemmas. Rewriting Sections 3-4 to lead with the geometric insight (pipelining saves n-1 agent delays) before the math would help. The “step-level scaling law” claim in the abstract is under-supported—one figure shows the trend but doesn’t establish it as a law. The related work conflates streaming generation (existing) with streaming inter-agent communication (novel).

Verdict: strong accept — Solves a real problem with a simple, theoretically grounded method, and the experimental evidence is comprehensive.

Takeaways

1. Granularity as a design lever: When building pipelines (LLM or otherwise), ask whether coarse-grained blocking (wait for full output) is necessary or just habitual. Finer granularity enables parallelism if you can identify clean boundaries.

2. Quality non-uniformity is exploitable: If your process produces outputs of variable quality over time (e.g., early draft vs final polish, initial search results vs deep retrieval), consider exposing partial results to downstream consumers. They can make progress on high-quality parts while you refine the rest.

3. Step detection as a primitive: Reasoning step boundaries are a useful abstraction. Beyond streaming, they enable partial caching (reuse steps 1-5 if step 6 changes), selective refinement (re-generate only low-confidence steps), and interpretability (inspect step-level contributions). A robust step boundary detector could be a general-purpose tool.

4. Closed-form analysis pays dividends: In a field dominated by empirical ablations, deriving exact latency formulas lets you predict behavior on unseen configurations (e.g., “adding one more agent costs 1/r latency, so is it worth the quality gain?”). Invest in tractable models of your system.