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

TL;DR - TreeCredit is a credit-assignment framework for adaptive multi-agent reasoning that scores individual operators via state-matched downstream comparisons instead of coarse query- or trajectory-level labels, yielding a better accuracy–cost trade-off across six reasoning benchmarks.

• Core idea: estimate operator utility by expanding candidate operators from the same intermediate state into shared-prefix collaboration trees, then compare their complete continuations rather than back-attributing trajectory outcomes.
• Each state–operator pair gets a correctness-prioritized suffix credit derived from terminal correctness plus cumulative additional cost, capturing state-conditioned utility that trajectory-level returns miss.
• Credits become state-local operator preferences used to train a lightweight pairwise state router that dynamically picks the next admissible operator at inference time.
• Reported results: modest accuracy gains with substantial inference-cost reduction versus representative MAR baselines (no specific numbers given in the abstract).