Shared Prefixes, Better Credit: Adaptive Routing for Multi-Agent Reasoning

• URL: http://arxiv.org/abs/2608.02291v1
• Date: Mon, 03 Aug 2026 14:22:23 GMT
• Title: Shared Prefixes, Better Credit: Adaptive Routing for Multi-Agent Reasoning
• Abstract summary: Multi-agent reasoning (MAR) improves reasoning reliability through iterative solution exchange and refinement.<n>Existing adaptive MAR methods typically learn routing decisions from query-level labels or trajectory-level returns.<n>We propose TreeCredit, a shared-operator credit assignment framework for efficient adaptive MAR.
• Score: 72.49938949082117
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Contrastive Branch Policy Optimization [16.16893757028268]
  Reinforcement learning with verifiable rewards (RLVR) enables language models to learn multi-turn interaction with external tools.<n>Existing methods tend to conflate two distinct problems: allocating a fixed rollout budget and translating branch outcomes into token-level credit.<n>We introduce Contrastive Branch Policy Optimization (CBPO), which disentangles these two problems and assigns a dedicated mechanism to each.
  arXiv  Detail & Related papers  (2026-08-25T09:25:55Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• The Hidden Bias of Process Reward Models:PRISM for Rewarding the Right Reasoning [54.0056619145783]
  Process Reward Models (PRMs) improve credit assignment for reasoning by providing step-level feedback.<n>We identify a hidden bias in PRMs caused by severe imbalance in step-level training data.<n>We propose PRISM, a policy-aware PRM training framework that learns from contrastive step-level comparisons.
  arXiv  Detail & Related papers  (2026-06-08T06:22:33Z)
• Co-ReAct: Rubrics as Step-Level Collaborators for ReAct Agents [6.89645931986174]
  We introduce Co-ReAct, a rubric-guided action-selection framework.<n>At each decision step, Co-ReAct injects a rubric into the agent's context to guide the next Reason-or-Act decision.<n>We train a dedicated rubric generator with GRPO to make this guidance reliable.
  arXiv  Detail & Related papers  (2026-05-22T12:59:16Z)
• Contextual Counterfactual Credit Assignment for Multi-Agent Reinforcement Learning in LLM Collaboration [22.269718913202595]
  We introduce Contextual Counterfactual Credit Assignment (textbftextttC3)<n>Instead of distributing rewards across an entire episode, textbftextttC3 isolates the causal impact of individual messages.<n>textbftextttC3 improves terminal performance over established baselines.
  arXiv  Detail & Related papers  (2026-03-06T20:25:11Z)
• ORCH: many analyses, one merge-a deterministic multi-agent orchestrator for discrete-choice reasoning with EMA-guided routing [0.6445605125467574]
  ORCH is a framework for discrete-choice reasoning that orchestrates heterogeneous language models.<n>It uses fixed rules for task decomposition and answer aggregation, keeping the pipeline predictable, reproducible, and training-free.<n>Experiments on MMLU, MMLU-Pro, and GSM8K show that ORCH consistently outperforms single-model baselines and a majority-vote ensemble.
  arXiv  Detail & Related papers  (2026-02-02T08:27:58Z)
• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• ArenaRL: Scaling RL for Open-Ended Agents via Tournament-based Relative Ranking [84.07076200941474]
  ArenaRL is a reinforcement learning paradigm that shifts from pointwise scalar scoring to intra-group relative ranking.<n>We construct an intra-group adversarial arena and devise a tournament-based ranking scheme to obtain stable advantage signals.<n>Experiments show that ArenaRL substantially outperforms standard RL baselines.
  arXiv  Detail & Related papers  (2026-01-10T08:43:07Z)
• Arbitrage: Efficient Reasoning via Advantage-Aware Speculation [71.45710345765528]
  Speculative Decoding accelerates inference by employing a fast but inaccurate draft model to autoregressively propose tokens.<n>But due to unnecessary rejections caused by token mismatches in semantically equivalent steps, traditional token-level Speculative Decoding struggles in reasoning tasks.<n>We propose Arbitrage, a novel step-level speculative generation framework that routes generation dynamically based on the relative advantage between draft and target models.
  arXiv  Detail & Related papers  (2025-12-04T17:50:53Z)
• In-Token Rationality Optimization: Towards Accurate and Concise LLM Reasoning via Self-Feedback [38.915062716409686]
  InTRO is a new framework that enables both token-level exploration and self-feedback for accurate and concise reasoning.<n>InTRO consistently outperforms other baselines, raising solution accuracy by up to 20% relative to the base model.<n>Its chains of thought are notably more concise, exhibiting reduced verbosity.
  arXiv  Detail & Related papers  (2025-11-13T01:47:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.