Multi-agent large language model (LLM) systems enable complex, long-horizon reasoning by composing specialized agents, but practical deployment remains hindered by inefficient routing, noisy feedback, and high interaction cost. We introduce REDEREF, a lightweight and training-free controller for multi-agent LLM collaboration that improves routing efficiency during recursive delegation. REDEREF integrates (i) belief-guided delegation via Thompson sampling to prioritize agents with historically positive marginal contributions, (ii) reflection-driven re-routing using a calibrated LLM or programmatic judge, (iii) evidence-based selection rather than output averaging, and (iv) memory-aware priors to reduce cold-start inefficiency. Across multi-agent split-knowledge tasks, we show that while recursive retry alone saturates task success, belief-guided routing reduces token usage by 28%, agent calls by 17%, and time-to-success by 19% compared to random recursive delegation, and adapts gracefully under agent or judge degradation. These results demonstrate that simple, interpretable probabilistic control can meaningfully improve the efficiency and robustness of multi-agent LLM systems without training or fine-tuning.
Figures & tables
Figure 1: System architecture of REDEREF . Queries pass through belief-guided delegation, agent execution, and judge evaluation. Upon success (top path), the posterior is updated and stored in memory before producing the final answer. Upon failure (bottom path), the query is refined and re-routed, with candidates aggregated using evidence-based selection.
Figure 2: Evaluation framework. Research questions, testable hypotheses, and associated metrics. Each dimension targets a distinct property of the routing mechanism.
Figure 3: Performance comparison across delegation strategies. (a) Task success rates (mean ± 95% CI) are saturated by recursive retry. (b) Output quality at convergence. REDEREF primarily improves efficiency (fewer calls/tokens) while maintaining comparable success. Error bars represent 95% confidence intervals.
Figure 4: Collaboration dynamics and specialization. (a) Average quality gain versus number of contributing agents, showing peak composition efficiency at 3–5 agents. (b) Decline in rounds required to select the Electrical Engineering expert across task sequence, demonstrating specialization via posterior concentration.
Method
Success (%)
Tokens ( ↓ )
Agent Calls ( ↓ )
Time-to-Success ( ↓ )
Random Delegation
96.46
1.00 ×
1.00 ×
1.00 ×
REDEREF (Full)
96.65
0.72 ×
0.83 ×
0.81 ×
Table 1: Efficiency comparison at matched task success. Tokens, Agent Calls, and Time-to-Success are reported as ratios normalized to Random Delegation; lower is better.
Method
Bad Agent Uses
Good Agent Uses
Total Attempted
Random Delegation
6.62 ± 0.4
4.92 ± 0.2
11.54 ± 0.5
REDEREF (Full)
5.65 ± 0.3
5.01 ± 0.2
10.67 ± 0.4
Table 2: Routing behavior with and without belief updates (mean ± 95% CI).
Metric
Normal
Impaired
Average Belief Score
0.35 ± 0.02
0.23 ± 0.03
Agent Contributions
12 ± 1.1
0
Final Output Score
84.52 ± 0.7
81.80 ± 0.9
Table 3: Adaptability under impairment: Biology agent performance before and after enforced degradation (mean ± 95% CI).
Figure 5: Adaptability under agent impairment. Belief score trajectories for the Biology agent under normal versus systematically impaired conditions. The system rapidly detects degradation and down-weights the compromised agent, demonstrating real-time adaptability.
Multi-agent large language model (LLM) systems often rely on a controller to coordinate a pool of heterogeneous models, yet existing controllers are typically limited to one-shot routing: they select a model once and return its output directly. Such routing-only designs provide no mechanism to critique intermediate drafts or support iterative refinement. To address this limitation, we propose a critique-and-routing controller that casts multi-agent coordination as a sequential decision problem. At each turn, the controller evaluates the current draft, decides whether to stop or continue, and, if needed, selects the next agent for further refinement. We formulate this process as a finite-horizon Markov Decision Process (MDP) with explicit agent-utilization constraints, design a composite reward for controller decisions across turns, and optimize the controller via policy gradients under a Lagrangian-relaxed objective. Extensive experiments across multiple heterogeneous multi-agent systems and seven reasoning benchmarks show that our method consistently outperforms state-of-the-art baselines and substantially narrows the gap to the strongest agent, while using it for fewer than 25% of total calls.
Multi-agent LLM systems have shown promise for complex reasoning, yet recent evaluations reveal they often underperform single-model baselines. We identify a structural failure mode in sequential fine-tuning of shared-context teams: updating one agent shifts the team's context distribution, and when subsequent updates are evaluated on cached rollouts, this mismatch compounds. We formalize this as the compounding occupancy shift and prove that stale-occupancy evaluation incurs a penalty that scales quadratically with the number of agents. In contrast, intermediate-occupancy evaluation reduces this to linear scaling. We propose TeamTR, a trust-region framework that resamples trajectories after each component update and enforces per-agent divergence control, yielding rigorous per-update and per-stage improvement lower bounds. Experiments show that TeamTR outperforms single-agent and sequential baselines with 7.1% on average, mitigates coordination regressions, and supports plug-and-play component replacement. Code is available at https://github.com/Yydc/TeamTR.
Yi Xie, Siao Liu, Falong Fan +3
Department of Electrical & Computer Engineering, University of Arizona · Future Science and Engineering College, Soochow University · INSAIT, Sofia University ”St. Kliment Ohridski” +1
Large language model (LLM)-based multi-agent systems tackle complex reasoning by orchestrating how multiple agents are configured and how they collaborate. A central challenge is to adapt orchestration to the evolving collaboration state. Routing from the query alone cannot adapt to intermediate progress or errors, which hurts accuracy. Routing from the complete execution history supplies this missing context, but forces later decisions to process every prior step, including redundant or low-utility ones. This creates an execution-history overload that inflates cost. Effective orchestration instead requires a compact state that captures useful progress without accumulating redundant context. We propose Gated-Memory Routing, which conditions each decision on the query and a learned execution memory. A learned Memory Write Gate commits only non-redundant reasoning steps, and a learned Retrieval Gate supplies each agent a compact, relevant subset, so every decision conditions on a clean, informative state. At each step, the system selects the next role and backbone from this memory, while an Adaptive Halting Controller stops execution once the memory contains sufficient evidence for answering. Across five reasoning and code-generation benchmarks, our framework is both effective and efficient: it attains the best average accuracy, exceeding the strongest baseline by 2.44 points, while reducing HumanEval inference cost by 31.9% relative to that baseline. Code is available at https://github.com/rajibrhasan/gated-memory-routing