Research map / Large language models / Reasoning and chain of thought
Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PORT, a training-free online LLM routing algorithm that uses ANNS over historical data to estimate query performance/cost and learns dual weights from a small random-routed sample, with a 1-O(eps+delta) competitive guarantee.
Problem
Routing queries to multiple LLMs under a constrained token budget in high-volume online settings, where queries arrive sequentially and existing routers are model-based (requiring training) or computationally heavy and assume offline conditions.
Approach
Treat the dual variable of the routing LP as per-LLM learnable weights, fit them once on a small initial sample of queries (randomly routed) using ANNS-estimated performance and cost from a historical dataset, then route subsequent queries by maximizing alpha*d_hat - gamma*g_hat.
Key results
- Averaged over benchmarks, the method improves performance 3.55x, performance-per-cost 1.85x, and throughput about 4.25x over the 8 baselines.
- Against the strongest baseline BatchSplit, it achieves about 33% higher performance, 38% better cost efficiency, and 24% higher throughput.
- Achieves 75.99% to 84.66% of the offline approximate optimum's performance across the three benchmarks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PORT instead of BatchSplit routing | Online LLM routing · RouterBench, SPROUT, and Open LLM Leaderboard v2 | Performance: 33% higher performance | Helped |
| Use PORT instead of BatchSplit routing | Online LLM routing · RouterBench, SPROUT, and Open LLM Leaderboard v2 | Performance per Cost: 38% better cost efficiency | Helped |
| Use PORT instead of BatchSplit routing | Online LLM routing · RouterBench, SPROUT, and Open LLM Leaderboard v2 | Throughput: 24% higher throughput | Helped |
| Vary the embedding model used for ANNS (ablation) | PORT · RouterBench, SPROUT, and Open LLM Leaderboard v2 | Performance | No clear effect |
| Increase α (ablation) | PORT · Routing benchmarks | Performance | Hurt |
| Increase ε from low values (ablation) | PORT · Routing benchmarks | Performance | Mixed |
| Increase the historical-data size used for ANNS and KNN (ablation) | PORT and KNN baselines · RouterBench | Performance | No clear effect |
| Increase the ANNS and KNN candidate pool size (ablation) | PORT and KNN baselines · RouterBench | Performance | Helped |
Surprising findings
- The relaxed LP optimality gap versus the MILP is only 0.016% on SPROUT, 0.086% on RouterBench, and 0.3% on Open LLM Leaderboard v2.
Limitations
- Only performance and cost are modeled; operational-state features such as traffic or load are not handled.
- Relies on the assumption that similar queries have similar performance and cost (Lipschitz-type Assumption), and on the random-order arrival model.
- Costs for baselines are predicted, since true remaining budget is not observable during online routing.
Experimental setup
Datasets: RouterBench SPROUT Open LLM Leaderboard v2
Benchmarks: RouterBench SPROUT Open LLM Leaderboard v2
Metrics: performance performance per cost throughput relative performance
Baselines: Random routing Greedy-Perf Greedy-Cost KNN-Perf KNN-Cost BatchSplit Roberta-Perf-routing Roberta-Cost-routing
Builds on: HNSW RouterBench BatchSplit KNN routing PAC learning
Closest papers by meaning
- BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute (ICML 2025 · similarity 0.91)
- Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing (ICLR 2024 · similarity 0.89)
- Online Linear Programming for Multi-Objective Routing in LLM Serving (ICML 2026 · similarity 0.89)
- TokenRouter: Efficient Serving System for Token-Level LLM Routing (NeurIPS 2026 · similarity 0.88)
- MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees (NeurIPS 2025 · similarity 0.88)
- Ada-K Routing: Boosting the Efficiency of MoE-based LLMs (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.