# RouteGuard: Certifying Routing Gain in LLM Multi-Agent Systems When Complementarity Is Not Enough

arXiv: https://arxiv.org/abs/2608.07583 · HTML: https://mlsanity.com/paper/2608.07583/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use.
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Placed in

- LLM agents and tool use / [Agent threats, guardrails and governance](https://mlsanity.com/agents/agent-threats-guardrails-and-governance/)

## Builds on (most cited first, 20 of 20)

- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025)
- [Consistent Estimators for Learning to Defer to an Expert](https://mlsanity.com/paper/2006.01862/) (2020)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer](https://mlsanity.com/paper/1711.06664/) (2017)
- [Which Agent Causes Task Failures and When? On Automated Failure Attribution of LLM Multi-Agent Systems](https://mlsanity.com/paper/2505.00212/) (2025)
- [Where LLM Agents Fail and How They can Learn From Failures](https://mlsanity.com/paper/2509.25370/) (2025)
- [AgenTracer: Who Is Inducing Failure in the LLM Agentic Systems?](https://mlsanity.com/paper/2509.03312/) (2025)
- [MasRouter: Learning to Route LLMs for Multi-Agent Systems](https://mlsanity.com/paper/2502.11133/) (2025)
- [Universal Model Routing for Efficient LLM Inference](https://mlsanity.com/paper/2502.08773/) (2025)
- [Learning to Defer to Multiple Experts: Consistent Surrogate Losses, Confidence Calibration, and Conformal Ensembles](https://mlsanity.com/paper/2210.16955/) (2022)
- [Causal LLM Routing: End-to-End Regret Minimization from Observational Data](https://mlsanity.com/paper/2505.16037/) (2025)
- [Abduct, Act, Predict: Scaffolding Causal Inference for Automated Failure Attribution in Multi-Agent Systems](https://mlsanity.com/paper/2509.10401/) (2025)
- [Cer-Eval: Certifiable and Cost-Efficient Evaluation Framework for LLMs](https://mlsanity.com/paper/2505.03814/) (2025)
- [When Routing Collapses: On the Degenerate Convergence of LLM Routers](https://mlsanity.com/paper/2602.03478/) (2026)
- [Why Do AI Agents Systematically Fail at Cloud Root Cause Analysis?](https://mlsanity.com/paper/2602.09937/) (2026)
- [Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap](https://mlsanity.com/paper/2201.04469/) (2022)
- [Towards Fair and Comprehensive Evaluation of Routers in Collaborative LLM Systems](https://mlsanity.com/paper/2602.11877/) (2026)
- [Proactive Routing to Interpretable Surrogates with Distribution-Free Safety Guarantees](https://mlsanity.com/paper/2603.14623/) (2026)

## Built on by (most cited first, 1 of 1)

- [What Can Component-Replacement Evidence Establish? A Critical Scoping Review of Local Decisions in LLM Agents](https://mlsanity.com/paper/2609.39989/) (2026)

## Abstract (arXiv)

Multi-agent LLM systems route among model-backed advisors, yet a deployer rarely knows before shipping whether routing will help at all. Prevailing routers optimize a gate's AUC and presume that advisor complementarity suffices. We show that neither determines the deployable gain. We introduce RouteGuard, a deployment-certification framework. Routing gain decomposes as G = π DeltaE, and the achievable gain is governed by a conditional-regret functional Phi, not by AUC. A finite-sample certification bracket comes with a matching Le Cam lower bound, constant-sharp over the fixed-activity class, and a robustness phase transition. On two benchmarks the framework acts as a guardrail. On RouterBench (11 cross-family models) the verdict depends on the sampling unit: the protocol certifies a gain over GPT-4 under prompt-level sampling and withholds it under workload-cluster resampling, because the gain rests on 3 of 86 workload cells. On OpenRCA (three Gemini advisors) the advisors are statistically redundant: the realized oracle sits at or below the independence baseline in all pools we tested (221 RouterBench pools and three OpenRCA distributions), so the protocol correctly refuses to certify. A pre-registered semi-synthetic control confirms calibration: the protocol certifies a genuine gain once m ≥ m^star and does not certify a true null. Code and frozen artifacts will be released with the published version.