After a weak verifier accepts a large-language-model response, a second call may resample or reroute. Because correctness is hidden, action selection is an identification problem. We order three gates: recoverable stopping debt, two-sided FIT action support, and held-out value from an outcome-blind selector. In a pinned 152-query MBPP+ experiment, a Qwen2.5-14B Base-only false-positive stop leaves +2.592 percentage points of Qwen2.5-7B recovery (query-cluster 95% interval [+1.618, +3.664]). Separately, after 7B Base-test rejection, fixed escalation to 14B exceeds leave-one-out 7B resampling by +2.882 points [+0.931, +5.201]; this is fixed-action ranking, not conditional selection. An all-episode audit produces a +2.697-point realized-maximum gap, but for two actions this statistic equals (1/2)E|Delta| - (1/2)|E Delta| and contains no observable-history term. It lies inside an exact-fold exchangeable reference (mean +3.158; 95% interval [+2.434, +3.947]). The audit unconditionally acts on 1,520 episodes: 1,240 observable stops and 280 verifier rejections; 198 stops are evaluator-only false positives. Neither tested outcome-blind controller improves on fixed rerouting. A separate LiveCodeBench ladder has all-zero FIT action advantages despite exclusive TEST rescues. A preregistered BigCodeBench support gate then finds only 23/19 and 22/19 signed episodes/queries against minima of 25/20, so L1-L4, DEV, and TEST stay unopened. Stopping debt exists, but current evidence does not identify when to resample rather than reroute.
Large language models (LLMs) achieve impressive performance across multiple domains, but using the most capable model for every query is prohibitive at scale. LLM routing exploits diversity in model capability and cost by assigning each query to a suitable model to balance utility and budget. Current methods have two limitations: (i) they either use heuristics that do not always enforce the budget constraint or impose a fixed per-query budget that cannot adapt across the workload and leads to suboptimal performance; (ii) they require supervised learning on a dense dataset with statistics for every query-model pair, which is expensive to collect. To address these challenges, we formulate LLM routing as a constrained contextual multi-armed bandit problem and introduce WISERouter (WR for short), a framework that supports offline learning from historical interactions as well as online learning with exploration. We further prove that WR-Online achieves a sublinear regret bound of O(T) over a time horizon T. Empirical results on RouterBench and SWE-Bench demonstrate that (i) WR-Offline surpasses existing baselines in performance under a fixed budget and adheres more closely to budget constraints, and (ii) WR-Online achieves comparable performance to the baselines, while using substantially less exploration data.
Sampling multiple responses improves language model reasoning, but uniform compute allocation is inefficient: easy questions are over-sampled while hard questions remain under-explored. We propose Uncertainty-Aware Budget Allocation (UAB), a concave integer optimization framework that reallocates a fixed sampling budget based on per-question uncertainty estimated at no additional inference cost. In Phase 1, every question receives one generation; its average negative log-likelihood (ANLL), extracted directly from output log-probabilities, serves as a difficulty signal while the generation contributes to the final vote. In Phase 2, the remaining budget is allocated by a marginal-greedy algorithm that solves a concave coverage-maximization surrogate exactly: uncertain questions receive more sampling budget while confident questions receive fewer additional samples. Evaluated on six open-weight and black-box models spanning 1.5B to 27B parameters and five reasoning benchmarks covering math, logic, and preference tasks, UAB outperforms baselines by up to +3% in average accuracy and up to +5% on individual benchmarks, with the largest gains in low-resource settings, requiring no auxiliary model or additional LLM call. Code is publicly available at https://github.com/manhitv/UAB.
Test-time compute scaling, the practice of spending extra computation during inference via repeated sampling, search, or extended reasoning, has become a powerful lever for improving large language model performance. Yet deploying these techniques under finite inference budgets requires a decision that current systems largely ignore: which inputs deserve more compute, and which can be answered cheaply? We formalize this as a constrained optimization problem (maximize expected accuracy subject to an average compute budget) and solve it with a two-stage Solve-then-Learn pipeline. In the solve stage, Lagrangian relaxation decomposes the global constraint into per-instance sub-problems, each admitting a closed-form oracle action that optimally prices accuracy against cost. We prove that the induced cost is monotone in the dual variable, enabling exact budget targeting via binary search. In the learn stage, a lightweight classifier is trained to predict oracle actions from cheap input features, amortizing the allocation rule for real-time deployment. We establish that the task-level regret of the learned policy is bounded by its imitation error times the worst-case per-instance gap, yielding a clean reduction from constrained inference to supervised classification. Experiments on MATH and GSM8K with three LLMs (DeepSeek-V3, GPT-4o-mini, Qwen2.5-7B) show that our method consistently outperforms uniform and heuristic allocation baselines, achieving up to 12.8% relative accuracy improvement on MATH under matched budget constraints, while closely tracking the Lagrangian oracle upper bound with over 91% imitation accuracy.