Shared Prefixes, Better Credit: Adaptive Routing for Multi-Agent Reasoning
2026-08-03 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors introduce TreeCredit, a new method to improve how multiple reasoning steps work together by better figuring out which steps are most useful. Instead of judging decisions only by the final outcome, TreeCredit compares different choices from the same point in the reasoning process to assign credit more precisely. This helps the system pick better next steps while using less computing power. Tests on six problems show it slightly improves accuracy and cuts costs compared to other similar methods.
multi-agent reasoningcredit assignmentadaptive routingcollaboration treeoperator utilitypairwise state routerinference costreasoning benchmarks
Authors
Yiqing Liu, Zihao Wang, Hantao Yao, Wu Liu, Yongdong Zhang
Abstract
Multi-agent reasoning (MAR) improves reasoning reliability through iterative solution exchange and refinement. Existing adaptive MAR methods typically learn routing decisions from query-level labels or trajectory-level returns, but such coarse supervision cannot accurately estimate the state-conditioned utility of individual operators in multi-step collaboration. We propose TreeCredit, a shared-prefix credit assignment framework for efficient adaptive MAR. Its core insight is to estimate operator utility through state-matched downstream comparisons, rather than directly attributing trajectory-level outcomes to preceding decisions. TreeCredit constructs shared-prefix collaboration trees by expanding candidate operators from the same intermediate state and assigns each state--operator pair a correctness-prioritized suffix credit based on the terminal correctness and cumulative additional cost of its complete continuation. These structured credits are converted into state-local operator preferences to train a lightweight pairwise state router, which dynamically selects the next admissible operator during inference. Experiments on six reasoning benchmarks show that TreeCredit modestly improves accuracy while substantially reducing inference cost, achieving a better accuracy--cost trade-off than representative MAR methods.