RouteGuard: Certifying Routing Gain in LLM Multi-Agent Systems When Complementarity Is Not Enough
Anchen Sun, Kaiqi Yang
stat.ML, cs.LG
Submitted: 2026-08-05
Updated: 2026-08-11
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: Multi-agent LLM systems route among model-backed advisors, yet a deployer rarely knows before shipping whether routing will help at all.
Terminology
Abstract
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 = pi E, and the achievable gain is governed by a conditional-regret functional, 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 and does not certify a true null. Code and frozen artifacts will be released with the published version.
Sources
- MasRouter: Learning to Route LLMs for Multi-Agent Systems
- Which Agent Causes Task Failures and When? On Automated Failure Attribution of LLM Multi-Agent Systems
- Why Do Multi-Agent LLM Systems Fail?
- Where LLM Agents Fail and How They can Learn From Failures
- Abduct, Act, Predict: Scaffolding Causal Inference for Automated Failure Attribution in Multi-Agent Systems
- AgenTracer: Who Is Inducing Failure in the LLM Agentic Systems?
- Causal LLM Routing: End-to-End Regret Minimization from Observational Data
- Universal Model Routing for Efficient LLM Inference
- RouterBench: A Benchmark for Multi-LLM Routing System
- Towards Fair and Comprehensive Evaluation of Routers in Collaborative LLM Systems
- When Routing Collapses: On the Degenerate Convergence of LLM Routers
- FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance
- Proactive Routing to Interpretable Surrogates with Distribution-Free Safety Guarantees
- Cer-Eval: Certifiable and Cost-Efficient Evaluation Framework for LLMs
- Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap
- Why Do AI Agents Systematically Fail at Cloud Root Cause Analysis?
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- Scalable Posterior Uncertainty for Flexible Density-Based Clustering
- A Transport Geometry of Benign Overfitting
- Efficient quadratic entropy with distance sketches