Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning
Abstract
Firms using large language models under fixed budgets must decide which model to call and whether to retry a failed task. Because a call's charge is revealed only after completion, one long response can exhaust the remaining budget and leave later tasks unserved. Our objective is to maximize the number of tasks solved before service stops. We develop a contextual bandit policy, ADP-HT, which learns each model's task-specific success probability and constructs conservative cost estimates from coarsened response-length labels on a quantile grid with 2K intervals. The policy weighs predicted success against these costs, adjusting the cost penalty to realized spending and the budget available per remaining task. Under calibration, local regularity, and grid-coverage conditions, we bound the excess allowance in the policy's conservative cost estimates. At a fixed sample size, increasing K reduces the discretization term but increases the estimation allowance. At the tightest tested budgets, ADP-HT solves more than twice as many MATH500 and GPQA tasks as the best implemented baseline. It achieves the highest mean cumulative score at ten of fourteen RouterBench budgets. On LiveCodeBench, it outperforms a deployed commercial router in both default and cost-saving modes at the three lowest test budgets.
Related
- Chance-Constrained Personalized LLM Routing with Online Preference Learning
- Which LLM for Which Work? Budgeted Model Allocation under Uncertain Evaluation
- Weighted Empirical Risk Minimization for Machine Learning under Long-Range Dependence: Exact Pathwise Rates and Learning-Error Geometry
- Learning Optimal Robust-Pathwise Control of Elliptic Equations with Random Coefficients
- HALO: Hierarchical Evidence Selection and Reinforcement Learning for Allocating Budgeted Label Optimization from Longitudinal Clinical Records
BibTeX
@misc{qin2026pathwisebudgeted,
title = {{Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning}},
author = {Hanzhang Qin and Sophie H. Yu and Yuewei Zhang and Zhi-Hai Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05835},
eprint = {2611.05835},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05835},
}
RIS
TY - UNPB
TI - Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning
AU - Hanzhang Qin
AU - Sophie H. Yu
AU - Yuewei Zhang
AU - Zhi-Hai Zhang
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.05835
UR - https://arxiv.org/abs/2611.05835
AB - Firms using large language models under fixed budgets must decide which model to call and whether to retry a failed task. Because a call's charge is revealed only after completion, one long response can exhaust the remaining budget and leave later tasks unserved. Our objective is to maximize the number of tasks solved before service stops. We develop a contextual bandit policy, ADP-HT, which learns each model's task-specific success probability and constructs conservative cost estimates from coarsened response-length labels on a quantile grid with 2^K intervals. The policy weighs predicted success against these costs, adjusting the cost penalty to realized spending and the budget available per remaining task. Under calibration, local regularity, and grid-coverage conditions, we bound the excess allowance in the policy's conservative cost estimates. At a fixed sample size, increasing K reduces the discretization term but increases the estimation allowance. At the tightest tested budgets, ADP-HT solves more than twice as many MATH500 and GPQA tasks as the best implemented baseline. It achieves the highest mean cumulative score at ten of fourteen RouterBench budgets. On LiveCodeBench, it outperforms a deployed commercial router in both default and cost-saving modes at the three lowest test budgets.
ER -