Routing Should Pay for Itself: Sparse Supervision for Economical LLM Routing
Guannan Lai, Gelin Bian, Hao-Xuan Ma, Jun-Peng Jiang, Long Chen, Jian-Dong Liu, Zhi-Hao Tan, Han-Jia Ye
cs.AI
2026-09-29
SaveRouter trains LLM routers on 33-41% of query-model labels, matching or beating dense methods on four benchmarks while cutting break-even volume by 1.9-9.5x.
A supervised LLM router typically buys a full query-model quality matrix before it saves anything in production. With N training queries and M candidates that is up to N×M model runs. Most papers start the clock after that matrix already exists, and only score the serving quality-cost curve.
The construction bill delays payback. On LLMRouterBench the fastest fully supervised baseline, OmniRouter, needs 11.5K served queries to recover its labels; RMSoftmax needs 20.2K. Quality also saturates early. EmbedLLM reaches 99% of its fully supervised accuracy with 30% of the labels, kNN with 60%. Routing only has to pick the model with the best cost-adjusted utility. Extra cells that do not change the argmax add little. Filling the whole matrix is over-buying.
SaveRouter chooses which cells to buy and how to read capability from the sparse set. The main setting evaluates K=4 models per training query, about 33-41% of available training feedback.
Queries are grouped first, because related prompts often share model-performance patterns. If training task labels are predictable, a logistic classifier maps new queries into those groups; otherwise MiniBatchKMeans clusters frozen embeddings. Grouping uses inputs only, never quality scores. LLMRouterBench has 10 groups, MMR-Bench 7, RouterBench 85. Mixinstruct is forced into a single global group.
Acquisition runs K passes, one previously unseen model per query per pass. A group-level mean is shrunk toward the model's global skill, then scored with a UCB bonus so strong and under-sampled models both get budget. Unseen group-model pairs are drawn first so each pass has basic coverage. After K passes the observation set holds at most NK distinct pairs.
Estimation is hierarchical. A two-way additive Ridge prior (global difficulty, group effect, model effect) shares structure across sparse cells. Local group-model means shrink toward that prior: lots of samples follow the data, few samples follow the prior. Within-group leftovers are fit with leave-one-out residuals and a light Ridge on TF-IDF features, with CLIP concatenated on MMR-Bench. At serving time the router selects argmax ŷm(x) − λ ĉ/Cmax, sweeping λ for the quality-cost frontier.
Shared structure carries the sparse regime. The residual is only allowed to explain what the group cannot, so the method does not try to reconstruct the full matrix from a handful of cells.
All four benchmarks use an in-domain 20%/80% split. Dense baselines include EmbedLLM, kNN, OmniRouter, TRouter, UniRoute, and InferenceDynamics. Sparse or partial-feedback baselines are WISERouter, BaRP, and SemiRouter. Peak Score (Ps) is the best test quality on the frontier. Cost Ratio (CR) is serving cost relative to the best single model once quality hits that model's score Qb. SA-BEP is the deployment volume that recoups supervision spend. SA-CR@1M amortizes that spend over one million served queries. Unreachable Qb or non-positive savings are recorded as infinity.
| Benchmark | SaveRouter Ps / CR / SA-BEP | Fastest fully supervised baseline |
| LLMRouterBench | 0.6338 / 0.2320 / 5.3K | OmniRouter 11.5K (CR 0.3564, Ps 0.6218) |
| Mixinstruct | 0.7498 / 0.9359 / 1.23M | kNN 11.63M (CR 0.9814) |
| MMR-Bench | 0.7540 / 0.7765 / 18.2K | TRouter 34.1K (CR 0.8396, Ps 0.7536) |
| RouterBench | 0.8084 / 0.6810 / 42.6K | EmbedLLM 326.4K (CR 0.9296) |
Versus the fastest fully supervised router, break-even volume drops by about 1.9-9.5×. SaveRouter also posts the highest Ps on all four sets. On Mixinstruct every method sits near Ps 0.75, so the gap is cheaper labels rather than a higher peak. BaRP can match quality, but counting every bandit pull as a fresh model call leaves SA-BEP at 114.0K, 44.66M, 640.8K, and 3.25M, roughly an order of magnitude slower. WISERouter and SemiRouter miss Qb on several sets, so the amortized metrics are infinity.
Ablations on LLMRouterBench at K=4: dropping the query residual cuts Ps from 0.6338 to 0.6175 and lifts CR from 0.2320 to 0.3484. Collapsing all queries into one group drops Ps to 0.5985. Random-K pays back sooner (3.8K vs 5.3K) but loses on Ps and long-horizon SA-CR. Earliest payback and cheapest long-run serving are different operating points. At K=2 (16.7% labels) quality is already close to full supervision. On MMR-Bench, K=7 minimizes CR while K=2 minimizes SA-BEP. Buying more labels is not always the cheaper plan. When the quality target is relaxed to 0.90Qb, WISERouter pays back earlier because its labeling bill is tiny, but it cannot reach 0.95Qb. At full Qb, SaveRouter has the lowest CR and SA-CR on both LLMRouterBench and MMR-Bench.
For a team training a router over a model pool, the main setting keeps a usable quality-cost frontier with a third to two-fifths of the labels, and payback arrives up to about 9.5× earlier. The accounting may outlive the architecture. SA-BEP and SA-CR put construction spend and serving savings on one ledger, so a cheap-to-serve router that was expensive to label shows up immediately.
This is a supervision policy for predictive routers, not a new serving stack. On Mixinstruct, SA-CR@1M is still 1.0148 and break-even sits at 1.23M queries. If traffic never reaches that scale, building the router can lose money even when serving looks efficient.
There is no standalone Limitations section. C0 counts only model runs used to collect feedback; router training is omitted. Cost fields do not share a currency, so SA-BEP is not dollars across datasets. WISERouter, BaRP, and SemiRouter are reimplementations. The main BaRP numbers use fresh-feedback accounting, charging every repeat pull, which is harsh for bandits. InferenceDynamics builds task profiles from recorded eval names, while SaveRouter predicts groups from the query, so that comparison is not fully matched. The main split is in-domain 20/80; raising the train fraction to 80% on LLMRouterBench moves Ps only from 0.6338 to 0.6416, while C0 jumps from 181.09 to 834.13 and SA-BEP from 5.3K to 22.7K. Quality is not strictly monotonic in K. The MMR-Bench frontier does not dominate every baseline at every cost. Mixinstruct uses one group, so the grouping branch contributes almost nothing there.