# Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in Serving systems and request scheduling, one of 12 directions in Efficient LLM inference and serving.
- Builds on 45 of its 74 references that are in the map.
- First posted on arXiv 2 Sep 2025.

## Placed in

- Efficient LLM inference and serving / [Serving systems and request scheduling](https://mlsanity.com/inference/serving-systems-and-request-scheduling/)

## Builds on (most cited first, 30 of 45)

- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [Towards General Text Embeddings with Multi-stage Contrastive Learning](https://mlsanity.com/paper/2308.03281/) (2023)
- [BARTScore: Evaluating Generated Text as Text Generation](https://mlsanity.com/paper/2106.11520/) (2021)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [C-Pack: Packed Resources For General Chinese Embeddings](https://mlsanity.com/paper/2309.07597/) (2023)
- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [Mathematical Capabilities of ChatGPT](https://mlsanity.com/paper/2301.13867/) (2023)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [MuSR: Testing the Limits of Chain-of-thought with Multistep Soft Reasoning](https://mlsanity.com/paper/2310.16049/) (2023)
- [Large Language Model Routing with Benchmark Datasets](https://mlsanity.com/paper/2309.15789/) (2023)
- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)
- [Routing to the Expert: Efficient Reward-guided Ensemble of Large Language Models](https://mlsanity.com/paper/2311.08692/) (2023)
- [Large Language Model Cascades with Mixture of Thoughts Representations for Cost-efficient Reasoning](https://mlsanity.com/paper/2310.03094/) (2023)
- [AutoMix: Automatically Mixing Language Models](https://mlsanity.com/paper/2310.12963/) (2023)
- [RAGBench: Explainable Benchmark for Retrieval-Augmented Generation Systems](https://mlsanity.com/paper/2407.11005/) (2024)

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

- [AutoSOTA: An End-to-End Automated Research System for State-of-the-Art AI Model Discovery](https://mlsanity.com/paper/2604.05550/) (2026)
- [Dynamic Model Routing and Cascading for Efficient LLM Inference: A Survey](https://mlsanity.com/paper/2603.04445/) (2026)
- [GenRouter: Unified Workflow Routing for Agentic Image Generation](https://mlsanity.com/paper/2608.16721/) (2026)
- [Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints](https://mlsanity.com/paper/2603.26796/) (2026)
- [Optimal Splitting of Language Models from Mixtures to Specialized Domains](https://mlsanity.com/paper/2603.19149/) (2026)
- [The Routing Plateau: Understanding the Accuracy Limits of LLM Routers](https://mlsanity.com/paper/2606.07587/) (2026)
- [RouteBalance: Fused Model Routing and Load Balancing for Heterogeneous LLM Serving](https://mlsanity.com/paper/2606.17949/) (2026)
- [The Capability Frontier: Benchmarks Miss 82% of Model Performance](https://mlsanity.com/paper/2606.26836/) (2026)
- [Training-Free versus Training-Based Intent Classification in LLMs: Accuracy, Robustness, and Failure Modes](https://mlsanity.com/paper/2608.02415/) (2026)
- [Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy](https://mlsanity.com/paper/2605.07171/) (2026)
- [Capturing LLM Capabilities via Evidence-Calibrated Query Clustering](https://mlsanity.com/paper/2605.17110/) (2026)
- [Online Linear Programming for Multi-Objective Routing in LLM Serving](https://mlsanity.com/paper/2607.03948/) (2026)
- [Unified AI Gateway: A Framework for Joint Model Routing and KV Cache Management](https://mlsanity.com/paper/2609.06940/) (2026)

## Abstract (arXiv)

Increasing demand for Large Language Models (LLMs) services imposes substantial deployment and computation costs on providers. LLM routing offers a cost-efficient solution by directing queries to the optimal LLM based on model and query features. However, existing works primarily focus on offline scenarios and struggle to adapt to online settings with high query volume and constrained token budgets. In this work, we introduce the first training-free algorithm for online routing scenarios. Our algorithm leverages approximate nearest neighbor search to efficiently estimate query features and performs a one-time optimization over a small set of initial queries to learn a routing strategy that guides future routing. We provide theoretical guarantees demonstrating that our algorithm achieves a competitive ratio of 1 - o(1) under natural assumptions, which is further validated by extensive experiments across 3 benchmark datasets and 8 baselines, showing an average improvement of 3.55× in overall performance, 1.85× in cost efficiency, and nearly 4.25× in throughput. Our code is available at https://github.com/fzwark/PORT.