Dual-Pool Token-Budget Routing for Cost-Efficient and Reliable LLM Serving

Xunzhuo Liu; Bowei He; Xue Liu; Andy Luo; Haichen Zhang; Huamin Chen

cs.CLApr 9, 2026

Dual-Pool Token-Budget Routing for Cost-Efficient and Reliable LLM Serving

Authors: Xunzhuo Liu, Bowei He, Xue Liu, Andy Luo, Haichen Zhang, Huamin Chen

Organizations: vLLM Semantic Router Project · MBZUAI · McGill University · Mila ·

Abstract

Production vLLM fleets typically provision each instance for the worst-case context length, leading to substantial KV-cache over-allocation and under-utilized concurrency. In practice, 80-95% of requests are short, yet are served under configurations optimized for long contexts, wasting 4-8 $\times$ throughput capacity and triggering reliability issues such as OOM crashes, preemption, and request rejections. We identify a common root cause for these inefficiencies: configuration-traffic mismatch. We propose dual-pool token-budget routing, a lightweight dispatch mechanism that partitions a homogeneous fleet into two specialized pools: a high-throughput short-context pool and a high-capacity long-context pool. Each request is routed based on its estimated total token budget, computed using a per-category bytes-to-token ratio that is learned online via exponential moving average from usage.prompt_tokens feedback, eliminating the need for a tokenizer. We also develop a simple analytical model that predicts fleet-level cost savings from workload characteristics and measured throughput differences, enabling practitioners to estimate benefits prior to deployment. Evaluations on real-world traces from the Azure LLM Inference Dataset and LMSYS-Chat-1M, serving Llama-3-70B on A100 GPUs, show that our approach reduces GPU-hours by 31-42%, corresponding to $2.86M annual savings at fleet scale, while lowering preemption rates by 5.4 $\times$ and improving P99 TTFT by 6%. A case study with Qwen3-235B-A22B on AMD MI300X at 10,000 req/s projects $15.4M in annual savings. The method incurs only O(1) dispatch overhead, adapts automatically to heterogeneous workloads, and composes seamlessly with existing optimizations such as PagedAttention, continuous batching, and prefill-decode disaggregation.

Figures & tables

Panel of Figure 1 — Figure 1: KV-cache waste under homogeneous provisioning. Each slot reserves $C_{\max}$ tokens regardless of actual usage. Short requests (80%+ of traffic) use $<$ 5% of their allocated space. An 8K pool uses 5 $\times$ more of each slot.

Panel of Figure 2 — Figure 2: Concurrency comparison: the same GPU memory holds 16 sequences at 64K context or 128 sequences at 8K — an 8 $\times$ difference in throughput capacity.

Panel of Figure 3 — Figure 3: Prefill head-of-line blocking. Top: a single 32K prefill stalls all queued short requests. Bottom: token-budget routing isolates the long prefill in a separate pool; short requests proceed without delay.

Panel of Figure 4 — Figure 4: Chunked prefill: compute vs. memory. Top: chunked prefill interleaves long-prefill chunks with decode iterations, preventing head-of-line blocking. Bottom: the KV cache is still allocated for the full 32K sequence, not the chunk size. The memory footprint, concurrency limit, and fleet size are unchanged.

Panel of Figure 5 — Figure 5: Token-budget pool routing with closed-loop calibration. Each request’s total token budget $L_{\text{total}}$ is estimated using calibrated $\hat{c}_{k}$ and compared against threshold $B_{\text{short}}$ . Responses feed back usage.prompt_tokens to refine the per-category ratio. A spillover path handles burst overloads.

Pool	$C_{\max}$	$N_{\text{seq}}$	$B_{\text{batch}}$	$\mu$ (req/s/inst)
Homogeneous	65K	16	8K	2.8
Short $\mathcal{P}_{s}$	8K	128	16K	11.2
Long $\mathcal{P}_{l}$	65K	16	8K	2.8

Table 1: Pool configurations.

Trace	Method	GPUs	Savings	P99 TTFT
Azure	Homogeneous	358	—	1.82 s
Azure	Token-budget	208	41.9%	1.71 s
LMSYS	Homogeneous	358	—	1.45 s
LMSYS	Token-budget	246	31.3%	1.48 s

Table 2: GPU instances and savings at 1,000 req/s (

B_{\text{short}}{=}8192

Method	Preemption ‰	OOM events/hr	Rejection rate	Success rate
Homogeneous	47.3	2.1	0.31%	99.69%
Short pool	1.2	0.0	0.00%	100.0%
Long pool	38.6	1.8	0.24%	99.76%
Overall	8.7	0.4	0.05%	99.95%

Table 3: Reliability at 1,000 req/s, 90% utilization (Azure trace).

	TTFT (s)		TPOT (ms)
Method	P50	P99	P50	P99
Homogeneous	0.42	1.82	28	67
Token-budget	0.28	1.71	25	62

Table 4: Latency at 1,000 req/s (Azure trace).

Category	True $c_{k}$	$\hat{c}_{k}$ at $n{=}50$	Rel. error	Mis-route rate
English prose	4.48	4.41	1.6%	0.3%
Source code	3.52	3.47	1.4%	0.2%
CJK text	2.01	2.08	3.5%	0.8%
Mixed / other	3.81	3.74	1.8%	0.4%
Global static ( $c{=}4$ )	—	4.00	—	4.1%

Table 5: Per-category EMA convergence on the Azure trace (

\beta{=}0.95

\gamma{=}1.0

Panel of Figure 6 — Figure 6: Savings vs. threshold. Any $B_{\text{short}}$ in 4K–16K delivers $>$ 80% of peak savings. The threshold is forgiving.

Deployment	Nodes	GPUs	Annual cost	Savings
Homogeneous	197	1,576	$50.6 M	—
Token-budget	137	1,096	$35.2 M	$15.4 M/yr

Table 6: Fleet projection: Qwen3-235B on MI300X at 10,000 req/s ($3.67/GPU-hr cloud rate).

LLM Serving

Large language model serving studies how to deliver model responses with low latency, high throughput, and efficient use of compute and memory.

See all 207 papers

Token-Budget-Aware Pool Routing for Cost-Efficient LLM Inference
Mar 13, 2026Huamin Chen, Xunzhuo Liu, Junchen Jiang +2LLM Inference Efficiency LLM Routing
vLLM Semantic Router Project · Tensormesh Inc / UChicago · MBZUAI / McGill University
TokenRouter: Efficient Serving System for Token-Level LLM Routing
Oct 8, 2026Tianyu Fu, Tengxuan Liu, Ruoxi Wang +4LLM Serving LLM Routing
Tsinghua University · Carnegie Mellon University
TokTier: Exact Stateful CPU+GPU Tokenization for Agentic LLM Serving
Jul 31, 2026Zhenyu Zhang, Zhichao CaoLLM Serving LLM Inference Acceleration
Arizona State University · Tempe, Arizona, USA

Mar 13, 2026J/K move · Enter open · S save

Token-Budget-Aware Pool Routing for Cost-Efficient LLM Inference

Huamin Chen, Xunzhuo Liu, Junchen Jiang, Bowei He+1

vLLM Semantic Router Project · Tensormesh Inc / UChicago · MBZUAI / McGill University

LLM Inference Efficiency LLM Routing Cost-Aware Inference LLM Request Scheduling

Open paper AskPDF arXiv

Production vLLM fleets provision every instance for worst-case context length, wasting 4-8x concurrency on the 80-95% of requests that are short and simultaneously triggering KV-cache failures -- OOM crashes, preemption storms, and request rejections. Both problems share a single root cause: configuration-traffic mismatch. We propose token-budget-aware pool routing: estimate each request's total token budget using a self-calibrating per-category bytes-per-token ratio, then dispatch it to one of two vLLM pools -- a high-throughput short pool or a high-capacity long pool -- each right-sized for its workload class. The ratio is learned online via exponential moving average from usage.prompt_tokens feedback, requiring no tokenizer. A closed-form cost model, savings = alpha * (1 - 1/rho), predicts fleet-level GPU savings from two observable quantities: the short-traffic fraction alpha and the throughput gain ratio rho. On traces from the Azure LLM Inference Dataset and LMSYS-Chat-1M serving Llama-3-70B on A100 GPUs, token-budget routing reduces GPU instances by 17-39% ($1.2-2.0M/yr at 1,000 req/s), with savings verified by a self-contained discrete-event simulator. A case study projecting Qwen3-235B-A22B on AMD MI300X at 10,000 req/s shows $15.4M/yr in savings. The algorithm adds O(1) dispatch overhead, self-calibrates across content types without a tokenizer, and composes with PagedAttention, continuous batching, and prefill-decode disaggregation.

Abstract

LLM Serving

Explore similar work

Token-Budget-Aware Pool Routing for Cost-Efficient LLM Inference

TokenRouter: Efficient Serving System for Token-Level LLM Routing

TokTier: Exact Stateful CPU+GPU Tokenization for Agentic LLM Serving