ExComm: Exploration-Stage Communication for Error-Resilient Agentic Test-Time Scaling

🕒 Published (v1): 2026-05-21 07:38 UTC · Source: Arxiv · link

Why this paper was selected

ExComm: exploration-stage communication reduces error propagation in long-horizon agents

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

ExComm is an exploration-stage communication protocol layered on top of parallel agentic test-time scaling, designed to detect and correct factual errors while they are still forming — before they contaminate final answers. It combines an Online Belief Consistency Module (cross-agent conflict detection + tool-verified resolution) with a Trajectory Diversification Module (plan-level redundancy detection + orthogonal redirection). On AIME 2024/2025 and GAIA, ExComm yields average gains of 5.7% and 5.0% over the strongest baselines with Gemini-2.5-Flash-Lite and Qwen3.5-4B.

Problem

In long-horizon agentic reasoning, factual errors introduced at intermediate steps persist in an agent's belief state and corrupt all subsequent planning and tool use. Existing test-time scaling methods — parallel sampling, tree search, sequential self-revision — either rely on self-detection (unreliable), prune branches post-hoc, or intervene only after the error has already shaped the trajectory. There is no mechanism for early, cross-agent error correction during the exploration stage itself.

Method

ExComm wraps any stateful agent loop \(A := (B, P, T)\) (belief, plan, toolkit) executing via a ReAct-style step sequence. After each execution step, two centralized modules fire over the \(N\) parallel agents:

Online Belief Consistency Module: Collects beliefs \(\{B_i\}_{i=1}^N\), extracts structured conflict objects listing mutually exclusive factual claims across agents, then runs an independent ReAct tool-use loop to resolve each conflict. Each resolution \(r \in R\) is sent only to the agents involved in that conflict. Agents apply a soft update: the resolution is appended to \(B_i\) as an external suggestion rather than overwriting the original belief, preserving the ability to recover from verifier errors.

Trajectory Diversification Module: Collects plans \(\{P_i\}_{i=1}^N\), jointly identifies redundant strategies and unexplored directions, and emits structured diversification directives \(D\). Each directive targets one agent and specifies how its plan should shift orthogonally. Unlike belief updates, plan directives are enforced (hard redirect) since they target distinct agents and thus cannot induce mode collapse.

Both modules use a targeted, privacy-preserving design: agents never inspect each other's full belief or plan; they receive only the artifact relevant to their own conflict or redundancy.

Key Contributions

• Empirical observation that 67–71% of intermediate errors in parallel agentic reasoning manifest as detectable cross-agent factual conflicts, motivating the design.
• Online Belief Consistency Module: asynchronous, tool-augmented conflict detection and resolution integrated inside the agent loop (not post-hoc).
• Soft belief update mechanism that appends corrections without overwriting, tolerating imperfect verifier outputs.
• Trajectory Diversification Module that operates at the plan level to counteract diversity collapse induced by information sharing.
• Demonstration that exploration-stage communication achieves a better performance-cost trade-off than tree search and adapted communication baselines (Multi-Agent Debate, Mixture-of-Agents).

Results

• AIME 2024 (Gemini-2.5-Flash-Lite): ExComm 72.5% vs. Tree Search 67.2% (+5.3pp), Independent Scaling 65.3%.
• AIME 2025 (Gemini-2.5-Flash-Lite): ExComm 60.6% vs. Tree Search 53.9% (+6.7pp).
• GAIA Average (Gemini-2.5-Flash-Lite): ExComm 46.2% vs. best baseline 40.5% (+5.7pp average over all benchmarks).
• Qwen3.5-4B average: ExComm +5.0% over best baseline.
• Error Recovery Rate (Gemini): ExComm 38.7% vs. Independent+SR 19.9%, Tree Search 12.9%.
• Error Recovery Rate (Qwen): ExComm 61.8% vs. best baseline 57.7%.
• Model scaling (Qwen3-235B): ExComm 63.0% average vs. 59.5% (Independent+SR).
• Agent scaling (N=8, Gemini): ExComm 50.5% vs. best baseline 44.7%.

Limitations

• Evaluated only on AIME and GAIA; generalization to other long-horizon domains (coding, scientific reasoning) is undemonstrated.
• The conflict-resolution loop is itself an independent ReAct agent — its errors can introduce incorrect resolutions that propagate if soft updates fail to trigger re-examination.
• 29–33% of errors are non-conflicting (common or neutral) and thus invisible to cross-agent comparison; these remain unaddressed.
• Cost analysis is described as favorable but not fully quantified in the excerpted text; scaling to large \(N\) or very long trajectories may erode the efficiency advantage.
• Results averaged over only three runs; variance on AIME-style competition math can be high.

Relevance to Harnesses / Meta-Harnesses

ExComm is structurally a meta-harness: it sits above a fleet of stateful sub-agents, periodically auditing their internal states and issuing corrections or redirections without modifying the agents' core execution logic. This is precisely the harness pattern — a coordination layer that owns the inter-agent control flow while delegating task execution downward. The Online Belief Consistency Module functions as a monitor/verifier harness sub-agent, and the Trajectory Diversification Module functions as a planner harness sub-agent, both operating on extracted agent state representations. For researchers building multi-agent harnesses, ExComm provides a concrete, evaluated blueprint for how to insert error-recovery and diversity-control into the orchestration layer between execution steps, with soft-update semantics that prevent verification errors from corrupting the sub-agent fleet.