mlsanityData to 7 Oct 2026

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

arXiv 2604.00136 ↗First posted 31 Mar 2026cs.LG cs.CLcited by 3

Not on the map. Why?

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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 31 of its 50 references that are in the map. First posted on arXiv 31 Mar 2026.

Builds on

31 of 50 references.

References · 31

  1. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  2. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,049
  3. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,393
  4. 2020Measuring Massive Multitask Language Understandingcited by 7,768
  5. 2018Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challengecited by 4,710
  6. 2019HellaSwag: Can a Machine Really Finish Your Sentence?cited by 4,018
  7. 2021TruthfulQA: Measuring How Models Mimic Human Falsehoodscited by 2,919
  8. 2018Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answeringcited by 2,114
  9. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Themcited by 1,767
  10. 2023FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performancecited by 791
  11. 2024RouteLLM: Learning to Route LLMs with Preference Datacited by 633
  12. 2024Hybrid LLM: Cost-Efficient and Quality-Aware Query Routingcited by 354
19 more
  1. 2024Replacing Judges with Juries: Evaluating LLM Generations with a Panel of Diverse Modelscited by 301
  2. 2023How is ChatGPT's behavior changing over time?cited by 265
  3. 2013Bandits with Knapsackscited by 163
  4. 2024GraphRouter: A Graph-based Router for LLM Selectionscited by 154
  5. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 84
  6. 2015Linear Contextual Bandits with Knapsackscited by 82
  7. 2025MixLLM: Dynamic Routing in Mixed Large Language Modelscited by 56
  8. 2025OmniRouter: Budget and Performance Controllable Multi-LLM Routingcited by 35
  9. 2025LLM Bandit: Cost-Efficient LLM Generation via Preference-Conditioned Dynamic Routingcited by 32
  10. 2023(Why) Is My Prompt Getting Worse? Rethinking Regression Testing for Evolving LLM APIscited by 21
  11. 2025Adaptive LLM Routing under Budget Constraintscited by 21
  12. 2025Cost-Aware Contrastive Routing for LLMscited by 16
  13. 2025Learning to Route LLMs from Bandit Feedback: One Policy, Many Trade-offscited by 13
  14. 2024Jump Starting Bandits with LLM-Generated Prior Knowledgecited by 11
  15. 2026CARE: Confounder-Aware Aggregation for Reliable LLM Evaluationcited by 10
  16. 2025Lookahead Routing for Large Language Modelscited by 5
  17. 2025One Head, Many Models: Cross-Attention Routing for Cost-Aware LLM Selectioncited by 4
  18. 2026PROTEUS: SLA-Aware Routing via Lagrangian RL for Multi-LLM Serving Systemscited by 4
  19. 202698× Faster LLM Routing Without a Dedicated GPU: Flash Attention, Prompt Compression, and Near-Streaming for the vLLM Semantic Routercited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Latency-Quality Routing for Functionally Equivalent Tools in LLM Agentscited by 1
  2. 2026Zero-Shot Confidence Estimation for Small LLMs: When Supervised Baselines Aren't Worth Trainingcited by 0
  3. 2026Learning to Assign Prediction Tasks to Agents with Capacity Constraintscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025xRouter: Training Cost-Aware LLMs Orchestration System via Reinforcement Learning
  2. 2026SeqRoute: Global Budget-Aware Sequential LLM Routing via Offline Reinforcement Learning
  3. 2025LLM Routing with Dueling Feedback
  4. 2026R2-Router: A New Paradigm for LLM Routing with Reasoning
  5. 2026Online Linear Programming for Multi-Objective Routing in LLM Serving
  6. 2026Learning to Route LLMs from Implicit Cost-Performance Preferences via Meta-Learning
  7. 2026From Sampled Outcomes to Capability Distributions: Rethinking Supervision for LLM Routing
  8. 2025Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving