🤖 machine learning

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

ParetoBandit is an open-source, adaptive routing system for non-stationary LLM serving that utilizes cost-aware contextual bandits with online primal-dual pacing and geometric forgetting to dynamically enforce dollar-denominated budgets while rapidly adapting to model price and quality shifts or integrating new models at runtime with minimal latency.

Original authors: Annette Taberner-Miller

Published 2026-04-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Annette Taberner-Miller

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you run a busy restaurant kitchen. You have three chefs:

Chef Cheap: Fast and cheap, but sometimes makes simple mistakes.
Chef Mid: A bit more expensive, but very reliable.
Chef Fancy: The most expensive, a genius, but costs a fortune.

In the world of AI, these are "Large Language Models" (LLMs). Companies want to use them to answer questions, but they have a strict daily budget. They can't just hire "Chef Fancy" for every order, or they'll go bankrupt. But they also can't use "Chef Cheap" for everything, or the food (the answers) will be bad.

The problem is that the kitchen is chaotic. Sometimes Chef Fancy gets a price cut. Sometimes Chef Cheap suddenly starts burning the toast (quality drops) without telling anyone. And sometimes a brand new chef joins the team.

ParetoBandit is the new, super-smart Head Waiter designed to solve this chaos.

The Problem: The "Set and Forget" Mistake

Old systems were like waiters who memorized a menu once a month and then never looked at it again.

If Chef Fancy dropped their prices, the old waiter kept charging the same high price.
If Chef Cheap started serving burnt toast, the old waiter kept sending orders there because they thought he was still good.
If a new chef joined, the old waiter didn't know how to handle them.

The Solution: ParetoBandit (The Adaptive Waiter)

ParetoBandit is a waiter that learns in real-time and never breaks the budget. It uses three clever tricks:

1. The "Smart Wallet" (Budget Pacer)

Imagine your wallet has a magical alarm.

Old Way: You try to guess how much you can spend all day. If you overspend in the morning, you might be broke by noon.
ParetoBandit: It checks your wallet after every single order.
- If you just spent a lot on Chef Fancy, the waiter immediately tightens the belt and says, "Okay, for the next few orders, we can only afford Chef Cheap."
- If Chef Fancy suddenly drops their price, the waiter instantly notices, "Hey, we have extra cash now! Let's treat ourselves to the Fancy chef for this order."
- The Magic: It ensures you never go over your daily budget, no matter how the prices change.

2. The "Short Memory" (Geometric Forgetting)

Imagine you are trying to learn a new dance.

Old Way: You remember every step you've ever taken, even the ones from 10 years ago. If the music changes, you keep trying to dance to the old song because your memory is too full.
ParetoBandit: It has a "short memory." It remembers the last few hundred orders very clearly, but it slowly forgets what happened 1,000 orders ago.
- Why? If Chef Cheap suddenly starts burning toast (quality drops), the waiter doesn't wait for a month to realize it. Because it "forgets" the old good data, it quickly realizes, "Wait, Chef Cheap is bad right now," and stops sending orders there. It adapts instantly to changes.

3. The "Trial Run" (Hot-Swapping)

Imagine a new chef walks in.

Old Way: You either ignore them or hire them immediately without testing.
ParetoBandit: It gives the new chef a strict, short trial. "You get 20 orders. If you are good, you stay. If you are bad or too expensive, you're out."
- It tests them carefully without blowing the budget. If the new chef is actually terrible, the system kicks them out automatically. If they are great, it starts using them more.

How Fast is It?

This system is incredibly fast.

Making a decision (which chef to pick) takes 22 microseconds. That is faster than a blink of an eye.
The whole process (including reading the order) takes less than 10 milliseconds.
To put that in perspective: The AI model itself takes about 1,000 milliseconds (1 second) to cook the meal. The waiter's decision takes up less than 1% of the total time. You won't even notice the waiter is there.

The Results

The paper tested this waiter in four scary scenarios:

Staying on Budget: It never went over the spending limit, even when prices changed wildly.
Price Drops: When the expensive chef got cheaper, the waiter immediately started using them more, getting better food for the same money.
Silent Failures: When a chef's quality silently got worse, the waiter noticed the bad food, stopped ordering from them, and switched to the others—all while staying within budget.
New Hires: It successfully tested and onboarded a new chef without crashing the system or breaking the budget.

The Bottom Line

ParetoBandit is like a self-driving car for your AI budget. It doesn't just follow a map; it watches the road, adjusts to traffic jams (price changes), avoids potholes (bad quality), and makes sure you never run out of gas (money), all while driving faster than you can blink.

1. Problem Statement

Production Large Language Model (LLM) serving increasingly relies on multi-model portfolios to balance quality and cost, where models can vary in price by a factor of ~530×. However, existing routing solutions face three critical operational gaps in real-world deployments:

Non-Stationarity: Model quality can regress silently (API updates), and pricing changes frequently (e.g., OpenAI price cuts). Most routers learn a fixed policy offline and fail to adapt to these shifts.
Budget Enforcement: Existing methods often optimize over a fixed prompt set or a known time horizon. They lack a mechanism to enforce a per-request cost ceiling (dollars per request) over an open-ended, unknown traffic stream.
Dynamic Portfolios: Adding or removing models at runtime (hot-swapping) without downtime or retraining is difficult for systems relying on static offline policies.

The core challenge is to design a router that simultaneously maximizes response quality, strictly adheres to a dollar-denominated budget, and autonomously adapts to price/quality drifts and model onboarding.

2. Methodology: ParetoBandit

ParetoBandit is an open-source, adaptive routing system built on cost-aware contextual bandits. It integrates four key components to address the challenges above:

A. System Architecture

Contextual Bandit Core: Uses LinUCB (Linear Upper Confidence Bound) to learn reward surfaces. The router observes a context vector $x_t$ (derived from the prompt via PCA-reduced embeddings), selects a model $a_t$ , and receives a reward $r_t$ (quality score) and cost $c_t$ .
Closed-Loop Budget Pacer: Replaces offline penalty tuning with an online primal–dual budget pacer.
- It maintains a dual variable $\lambda_t$ that acts as a Lagrange multiplier.
- $\lambda_t$ increases if recent spending exceeds the budget $B$ and decreases if spending is low.
- Two-Layer Enforcement:
  1. Hard Ceiling: If $\lambda_t > 0$ , models exceeding a dynamic cost threshold are excluded from the candidate set (circuit breaker).
  2. Soft Penalty: A cost penalty term $(\lambda_c + \lambda_t)\tilde{c}_a$ is subtracted from the UCB score, biasing selection toward cheaper models within the feasible set.
Geometric Forgetting: To handle non-stationarity, the system applies a forgetting factor $\gamma \in (0, 1]$ to the sufficient statistics ( $A_a, b_a$ $A_{a}, b_{a}$ ) of the LinUCB algorithm.
- This exponentially discounts old data, giving the system a bounded "effective memory."
- It allows the router to rapidly forget stale quality estimates or outdated price assumptions.
- Staleness Inflation: The system explicitly inflates the exploration bonus for arms that haven't been selected recently, ensuring re-exploration of potentially recovered models.
Offline-to-Online Warmup: To avoid cold-start regret, the system loads offline sufficient statistics (fitted on historical data) as priors. These priors decay naturally via geometric forgetting, ensuring the system eventually relies on live traffic.
Runtime Portfolio Management: Supports add_arm() and delete_arm() at runtime. New models undergo a brief forced-exploration phase (20 pulls) to bootstrap their posterior before standard UCB selection takes over.

B. Algorithmic Details

Objective: Maximize cumulative quality subject to $\limsup \frac{1}{T} \sum c_t \le B$ .
Selection Rule: The router selects the model maximizing:
$\text{Score} = \underbrace{\hat{\theta}_a^\top x_t}_{\text{Exploit}} + \underbrace{\alpha \sqrt{x_t^\top A_a^{-1} x_t}}_{\text{Explore}} - \underbrace{(\lambda_c + \lambda_t)\tilde{c}_a}_{\text{Cost Penalty}}$
Hyperparameter Tuning: Uses a Pareto knee-point procedure to jointly calibrate the forgetting rate ( $\gamma$ ) and exploration coefficient ( $\alpha$ ) based on a single practitioner-specified "adaptation horizon" (how quickly the system must react to a shift).

3. Key Contributions

First System for Closed-Loop Budget Pacing: Unlike prior work that assumes fixed horizons or offline optimization, ParetoBandit enforces a per-request cost ceiling over an open-ended stream using a smoothed dual-ascent update.
Principled Non-Stationarity Handling: It is the first LLM router to explicitly employ geometric discounting and evaluate performance under silent quality degradation and price shifts, demonstrating rapid adaptation without manual intervention.
Runtime Hot-Swapping: Introduces a mechanism to onboard new models at runtime with bounded exploration, ensuring the router discriminates based on live data rather than blindly adopting new endpoints.
Efficiency: The routing decision takes only 22.5 µs on a CPU, with end-to-end latency (including embedding) at 9.8 ms, which is less than 0.4% of typical LLM inference time.

4. Experimental Results

The system was evaluated on 1,824 benchmark prompts across a 3-model portfolio (spanning a 530× cost range) and various budget constraints.

Budget Compliance: Across all scenarios, the mean per-request cost never exceeded the target budget by more than 0.4%. Even under stress tests, it stayed within ~4% of the ceiling.
Adaptation to Price Drift: When the costliest model's price was cut by 50% mid-stream, ParetoBandit detected the change and shifted traffic, yielding a +0.071 quality lift while maintaining budget compliance.
Silent Quality Degradation: When a model's quality silently dropped by ~18%, the router detected the regression via the reward signal, reduced its allocation, and maintained budget compliance. Baselines without closed-loop control overspent by up to 6.9×.
Cold-Start Onboarding: A new model added at runtime reached meaningful adoption within ~142 steps without breaching the cost ceiling. The system correctly rejected low-quality models after a bounded exploration phase.
Robustness: The system's conclusions held across three different LLM judges (DeepSeek-R1, GPT-4.1-mini, Claude-3.7-Sonnet), confirming that the routing logic is robust to evaluator variance.

5. Significance and Impact

Operational Reliability: ParetoBandit solves the "open-ended" problem of production LLM serving, where traffic volume and model conditions are unknown and dynamic. It provides a safety net against cost overruns while maximizing quality.
Cost Efficiency: By dynamically mixing models based on real-time budget pressure and quality, it achieves a continuous Pareto frontier, allowing operators to set a dollar budget and automatically find the optimal quality mix.
Scalability: The low latency (sub-10ms) and CPU-only execution make it feasible to deploy as a middleware layer in high-throughput production environments without requiring dedicated GPU resources for routing.
Future-Proofing: The ability to hot-swap models and adapt to silent regressions makes it a critical component for maintaining service level agreements (SLAs) in an era of rapidly evolving LLM APIs.

In summary, ParetoBandit represents a shift from static, offline-optimized routing to adaptive, closed-loop control, ensuring that LLM serving remains both cost-effective and high-quality despite the inherent non-stationarity of the production environment.