RouteGuard framework certifies LLM routing gains with finite-sample guarantees

Deploying a multi-agent LLM system is a gamble: routing among model-backed advisors may improve accuracy or quietly waste compute, and today's routers can't tell you in advance. A new arXiv paper from Anchen Sun and Kaiqi Yang tackles this with RouteGuard, a certification framework that rigorously determines whether routing will actually deliver gains before you ship. The key insight: optimizing a gate's AUC or assuming advisor complementarity is enough—neither determines the deployable gain. RouteGuard decomposes routing gain as G = πΔE, showing the achievable gain is governed by a conditional-regret functional Φ, not AUC.

RouteGuard provides a finite-sample certification bracket with a matching Le Cam lower bound, constant-sharp over the fixed-activity class, plus a robustness phase transition. Tested on RouterBench (11 cross-family models, 86 workload cells), the verdict depends on the sampling unit: it certifies a gain over GPT-4 under prompt-level sampling but withholds certification under workload-cluster resampling, because the gain rests on just 3 of 86 cells. On OpenRCA with three Gemini advisors, the advisors are statistically redundant—the realized oracle sits at or below the independence baseline across 221 RouterBench pools and three OpenRCA distributions—so RouteGuard refuses to certify. A pre-registered semi-synthetic control confirms calibration: correct certification when m ≥ m*, no certification for a true null. Code and frozen artifacts will be released.