# ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 50 references that are in the map.
- First posted on arXiv 31 Mar 2026.

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

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [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)
- [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)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering](https://mlsanity.com/paper/1809.02789/) (2018)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [Replacing Judges with Juries: Evaluating LLM Generations with a Panel of Diverse Models](https://mlsanity.com/paper/2404.18796/) (2024)
- [How is ChatGPT's behavior changing over time?](https://mlsanity.com/paper/2307.09009/) (2023)
- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [MixLLM: Dynamic Routing in Mixed Large Language Models](https://mlsanity.com/paper/2502.18482/) (2025)
- [OmniRouter: Budget and Performance Controllable Multi-LLM Routing](https://mlsanity.com/paper/2502.20576/) (2025)
- [LLM Bandit: Cost-Efficient LLM Generation via Preference-Conditioned Dynamic Routing](https://mlsanity.com/paper/2502.02743/) (2025)
- [Adaptive LLM Routing under Budget Constraints](https://mlsanity.com/paper/2508.21141/) (2025)
- [(Why) Is My Prompt Getting Worse? Rethinking Regression Testing for Evolving LLM APIs](https://mlsanity.com/paper/2311.11123/) (2023)
- [Cost-Aware Contrastive Routing for LLMs](https://mlsanity.com/paper/2508.12491/) (2025)
- [Learning to Route LLMs from Bandit Feedback: One Policy, Many Trade-offs](https://mlsanity.com/paper/2510.07429/) (2025)
- [CARE: Confounder-Aware Aggregation for Reliable LLM Evaluation](https://mlsanity.com/paper/2603.00039/) (2026)
- [Jump Starting Bandits with LLM-Generated Prior Knowledge](https://mlsanity.com/paper/2406.19317/) (2024)
- [Lookahead Routing for Large Language Models](https://mlsanity.com/paper/2510.19506/) (2025)
- [One Head, Many Models: Cross-Attention Routing for Cost-Aware LLM Selection](https://mlsanity.com/paper/2509.09782/) (2025)
- [PROTEUS: SLA-Aware Routing via Lagrangian RL for Multi-LLM Serving Systems](https://mlsanity.com/paper/2601.19402/) (2026)

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

- [Zero-Shot Confidence Estimation for Small LLMs: When Supervised Baselines Aren't Worth Training](https://mlsanity.com/paper/2605.02241/) (2026)
- [Latency-Quality Routing for Functionally Equivalent Tools in LLM Agents](https://mlsanity.com/paper/2605.14241/) (2026)
- [Learning to Assign Prediction Tasks to Agents with Capacity Constraints](https://mlsanity.com/paper/2605.27999/) (2026)
- [Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory](https://mlsanity.com/paper/2610.05659/) (2026)

## Abstract (arXiv)

Multi-model LLM serving operates in a non-stationary, noisy environment: providers revise pricing, model quality can shift or regress without notice, and new models arrive regularly. More than a dozen recent methods have proposed learned routers to navigate the resulting quality--cost tradeoff across portfolios spanning a ~530× cost range. Despite this activity, two gaps in the current solution space limit routing effectiveness under these conditions: no existing router enforces a dollar-denominated cost ceiling in closed loop over an open-ended request stream, and none provides principled online adaptation to post-deployment shifts in pricing or model quality. We present ParetoBandit, an open-source adaptive router built on cost-aware contextual bandits that addresses both gaps. Its core contributions are: (1) an online primal--dual budget pacer that enforces a per-request cost ceiling without a known horizon, and (2) geometric forgetting on sufficient statistics that gives the bandit bounded memory for tracking quality and cost shifts. A hot-swap model registry further supports runtime model changes with budget-controlled exploration. On 1,824 benchmark prompts with a three-model portfolio, the router maintains budget compliance within 0.4%, adapts to price and quality shifts with up to +0.071 quality lift, and integrates a cold-started model within ~142 steps.