ExComm: Exploration-Stage Communication for Error-Resilient Agentic Test-Time Scaling
Woomin Song, Beomjun Kim, Daewon Choi, Sai Muralidhar Jayanthi, Saket Dingliwal, Jinwoo Shin, Aram Galstyan, [4pt] KAIST · 2026
Read ExComm: Exploration-Stage Communication for Error-Resilient Agentic Test-Time Scaling by Woomin Song, Beomjun Kim, Daewon Choi, Sai Muralidhar Jayanthi, Saket Dingliwal, Jinwoo Shin, Aram Galstyan, [4pt] KAIST (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22102.txt.
Introduction
Woomin Song and co-authors present ExComm, exploration-stage communication for error-resilient agentic test-time scaling. A common failure in long-horizon agentic scaling is error propagation: factual errors or invalid deductions from intermediate steps persist and contaminate later reasoning. Existing methods give limited control, relying on agents to catch mistakes, choose among flawed paths, or refine solutions only after errors spread. ExComm communicates during exploration instead. Tests on AIME 2025 and GAIA with Gemini-2.5-Flash-Lite and Qwen3.5-4B show gains of 5.7 percent and 5.0 percent over baselines.
Catalog record
| CREATOR | Woomin Song, Beomjun Kim, Daewon Choi, Sai Muralidhar Jayanthi, Saket Dingliwal, Jinwoo Shin, Aram Galstyan, [4pt] KAIST |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53793 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22102
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ExComm: Exploration-Stage Communication for Error-Resilient Agentic Test-Time Scaling Woomin Song, Beomjun Kim, Daewon Choi, Sai Muralidhar Jayanthi, Saket Dingliwal, Jinwoo Shin, Aram Galstyan, [4pt] KAIST Abstract A common failure mode in long-horizon agentic test-time scaling is error propagation, where factual errors or invalid deductions introduced at intermediate steps persist in the agent’s belief state and contaminate later reasoning. Existing test-time scaling methods provide limited control over this process, as they often rely on agents to detect their own mistakes, select among flawed trajectories, or refine solutions only after errors have already shaped the reasoning path. We propose ExComm, a communication protocol for exploration-stage agentic test-time scaling. ExComm is motivated by the empirical observation that the majority of intermediate errors in parallel agentic reasoning produce detectable cross-agent factual conflicts. Leveraging the iterative structure of agentic workflows, ExComm periodically audits agent belief states to detect such conflicts, resolves them through a dedicated tool-based verification loop, and returns concise, targeted feedback to the involved agents. Corrections are incorporated through soft belief updates, which append verified feedback rather than overwriting existing beliefs. Furthermore, to prevent collapsing trajectory diversity due to communication, ExComm further introduces a trajectory diversification module that redirects redundant trajectories toward orthogonal strategies. Experiments on AIME 2024, AIME 2025, and GAIA with Gemini-2.5-Flash-Lite and Qwen3.5-4B show that ExComm consistently outperforms strong test-time scaling baselines, achieving average performance gains of 5.7% and 5.0% over the best-performing baselines, respectively. Further analyses demonstrate improved error recovery, favorable scaling behavior, stronger diversity than adapted communication baselines, and the best performance-cost trade-off among the evaluated methods. 0 0 footnotetext: † Work done at Amazon. 1 Introduction Test-time scaling has emerged as a powerful approach for improving LLM performance without additional training [ 17 ] . By allocating additional computation at inference time, methods such as sequential revision [ 11 , 9 ] , parallel sampling strategies including Best-of- N and Self-Consistency [ 4 , 3 ] , and tree search techniques [ 23 , 2 ] have achieved substantial gains across reasoning benchmarks. Recently, this paradigm has been extended to agentic workflows [ 29 , 26 ] , where models solve problems through multiple rounds of generation, tool use, and interaction with an environment. Figure 1: Overview of ExComm. ExComm augments a standard agentic test-time scaling loop with an exploration-stage communication step. After each execution step, the Online Belief Consistency Module gathers agent belief states \{B_{i}\}_{i=1}^{N} , detects factual conflicts, resolves them through tool-augmented verification, and produces a set of targeted resolutions \mathcal{R} . Each agent \mathcal{A}_{i} receives only the relevant subset \mathcal{R}_{i}\subseteq\mathcal{R} , which is applied as a soft belief update by appending verified feedback without overwriting the prior belief state. In parallel, the Trajectory Diversification Module analyzes agent plans \{P_{i}\}_{i=1}^{N} , identifies redundant strategies, and produces a set of diversification directives \mathcal{D} . When a directive is assigned to agent \mathcal{A}_{i} , it receives d_{i}\in\mathcal{D} and updates its plan to encourage orthogonal exploration. The updated agents then continue the base execution loop at the next exploration step. A common failure mode in long-horizon problem solving is error propagation, where factual errors or invalid deductions introduced at intermediate steps persist in the agent’s belief and contaminate later decisions. Existing test-time scaling methods provide limited control over this process. Parallel sampling relies heavily on agents detecting their own mistakes, which is often unreliable [ 7 , 8 ] . Tree search mitigates errors through branch selection rather than explicit correction. Therefore, errors that are not pruned can continue to shape downstream reasoning. Post-hoc aggregation or refinement methods intervene only after errors have already shaped the reasoning trajectory. At the same time, agentic workflows provide a natural point of intervention for error control. Unlike static reasoning, they involve dynamic interaction with an environment, where agents alternate between reasoning and actions such as tool calls while updating intermediate beliefs over multiple rounds. This iterative structure creates a natural opportunity for early error detection and correction during the exploration stage of agentic test-time scaling, where agents are still gathering evidence and forming their reasoning trajectories, before candidate solutions are created. We hypothesize that structured communication among parallel reasoning trajectories at this stage can help detect and resolve belief-level errors before they propagate, ultimately improving final answer quality. To this end, we propose ExComm, an exploration-stage communication protocol for agentic test-time scaling. ExComm is motivated by the empirical observation that the majority of intermediate errors in parallel agentic reasoning introduce cross-agent factual conflicts (67–71% across benchmarks, see Section 3.2 ), making them detectable without relying on self-correction. Figure 1 illustrates the core components of ExComm. When a conflict is detected, the Online Belief Consistency Module resolves the discrepancy using its own tool-based verification loop. The resulting correction is then returned to the involved agents as concise, targeted feedback. Each agent applies a soft belief update, appending the correction to its belief state rather than overwriting the original belief. This allows agents to benefit from verified information while retaining the ability to recover from potential verifier errors. A key challenge in exploration-stage communication is the risk of diversity collapse. Excessive information sharing can prematurely synchronize reasoning trajectories, undermining the benefits of parallel scaling. To avoid this, the consistency module provides targeted feedback that addresses only the specific inconsistency, rather than a broad summary of other agents’ beliefs. ExComm further incorporates a trajectory diversification module, which monitors high-level strategies across agents and encourages orthogonal directions when trajectories become overly similar. By combining targeted belief correction with explicit diversity preservation, ExComm mitigates error propagation while maintaining the benefits of parallel exploration. We evaluate ExComm on challenging tool-based reasoning setups, including AIME 2024 and AIME 2025 [ 1 ] with code interpreter access, and GAIA [ 12 ] with code interpreter, file management tools, and web search. Experiments on Gemini-2.5-Flash-Lite [ 5 ] and Qwen3.5-4B [ 19 ] show that ExComm consistently outperforms strong test-time scaling baselines, including sequential revision, parallel scaling, and test-time tree search. ExComm achieves average performance gains of 5.7% and 5.0% over the best-performing baselines with the two models, respectively. Further analysis shows that ExComm substantially improves error recovery during reasoning, supporting our claim that exploration-stage communication helps agents correct erroneous beliefs before they propagate. Additional analyses show that ExComm scales with both model size and the number of agents, consistently outperforming baselines across settings. We also compare against adapted communication protocols, including Multi-Agent Debate [ 6 ] and Mixture-of-Agents [ 21 ] , and show that ExComm achieves stronger accuracy while preserving higher trajectory diversity. Ablation studies validate the contributions of both the consistency module and the trajectory diversification module to accuracy and error recovery. Finally, efficiency analysis shows that ExComm achieves the best performance-cost trade-off among the evaluated methods, making it a practical approach for agentic test-time scaling. 2 Related Works LLM Agents. Large Language Models (LLMs) have evolved from static text generators into agents capable of solving complex, real-world tasks [ 24 , 15 , 22 ] . By integrating tools such as calculators, search engines, and APIs, agentic systems can extend standalone models with capabilities such as precise computation and real-time information retrieval [ 14 , 25 ] . Unlike static reasoning, agentic workflows are often implemented