Resample or Reroute? Budget-Aware Test-Time Model Selection for Large Language Models

Source: arXiv:2607.08665 · Published 2026-07-09 · By Teng-Ruei Chen

TL;DR

This paper addresses the problem of test-time model selection among a pool of large language models (LLMs) under a fixed per-query inference cost budget and an imperfect correctness verifier. Existing approaches either commit to one model per query or use best-of-K resampling of a single model but have not jointly optimized the trade-off between resampling one chosen model versus rerouting to a different model within a single budget constraint. The authors formalize budget-aware test-time model selection as maximizing expected correctness under a cost budget, given an imperfect verifier signal indicating candidate correctness but not ground truth. They propose an online, greedy Resample-or-Reroute (RoR) allocation policy that at each step spends budget unit where the marginal correctness gain per unit cost is highest, by either drawing an additional output from the committed model or discarding it to sample a new model. Extensive replay experiments on large multi-draw correctness datasets from an 11-model pool spanning multiple benchmarks (GSM8K, MATH-500, GPQA-Diamond, HumanEval+) show that RoR consistently achieves a better cost–quality Pareto front compared to baselines including single-model best-of-K, cascades, random allocation, and learned one-commit routers. Gains are largest on heterogenous, challenging benchmarks where rerouting can find model specialists, and shrink as verifier quality degrades. The proposed policy approaches an oracle allocation upper bound under perfect verification. The study also experiments with real provider price vectors and natural agreement-based verifiers, validating the policy’s applicability in practical scenarios. Overall, this work bridges the gap between theory and practice in adaptive LLM routing, quantifying how to allocate a fixed per-query compute budget between sampling and routing to maximize correctness.

Key findings

• On GSM8K (near saturated), RoR reaches 0.993 accuracy at mean cost 9.2, which is 24%–34% cheaper than cascade (12.1) and best-of-K (13.9), and 3.5x cheaper than single-route best model (32.0 cost) while improving accuracy by 2.7 points (0.993 vs 0.966).
• On GPQA-Diamond (hard, heterogeneous), RoR achieves 0.968 accuracy at cost 25.9, beating budget-aware best-of-K by +10.7 points (0.861), cascade by +4.1 points, and single-commit baseline by roughly +40 points.
• Verifier quality strongly gates RoR gains: at verifier quality q=0.6, accuracy on GPQA drops from 0.968 to 0.675 but still outperforms baselines (0.675 vs 0.648 best-of-K, 0.509 cascade).
• Under a partial agreement verifier for HumanEval+ code tests, RoR nearly matches perfect-verifier accuracy (0.897 vs 0.897 at budget 26) and outperforms best-of-K baseline (0.870), showing realistic verifier feasibility.
• Real-price replay using provider-calibrated $/token costs preserves RoR’s leading cost–accuracy tradeoffs relative to all baselines, showing robustness to economic cost shifts.
• RoR is adaptive and requires multiple sequential rounds per query (2.5–3.3 rounds), incurring latency cost but fewer rounds and better accuracy than cascade baselines at matched budgets.
• The UCB exploration variant does not outperform the simpler greedy marginal correctness gain rule and is thus not recommended.
• Offline prior pseudo-count hyperparameter s has limited impact on final performance (accuracy varies by ≤1.7 points across 16× range).

Methodology — deep read

1. Threat model & assumptions: The adversary is not explicitly modeled as this is a cost-quality optimization problem rather than a security threat paper. The system assumes access to a pool of diverse LLMs, each with unknown per-instance correctness probabilities, and an imperfect verifier which scores candidate outputs but does not reveal ground truth correctness. Budget constraints limit total per-query inference cost. 2. Data: The study uses regenerated multi-draw correctness tensors (k=30 draws per query/model cell) from a publicly available 11-model pool composed of open-weight LLMs spanning eight lineages including Mistral, Qwen, Phi, Llama, etc. Four benchmarks of varying difficulty and domain are used: GSM8K (500 queries, arithmetic, near-saturated), MATH-500 (500 queries, competition math, intermediate), GPQA-Diamond (198 queries, graduate-level science, heterogeneous/ challenging), and HumanEval+ (164 queries, code generation with execution test scoring). Data is split 50/50 for train/test; offline model accuracies are calibrated on train splits. 3. Algorithm: The proposed RoR policy maintains per-query Bayesian posterior mean estimates of correctness probabilities for each model based on offline prior accuracies and draws verified as correct by the verifier. At each step under budget B, the policy greedily selects the next action—either resample the current committed model or reroute to a new model—that maximizes estimated marginal correctness per unit cost, defined as the posterior estimated success probability divided by the model’s per-draw cost. Two variants are considered: a pure greedy policy and a UCB variant adding an exploration bonus to less sampled models. The choice effectively balances allocating budget between repeated draws of the same model (sampling) and switching to different models (routing). 4. Training and implementation: No training in the traditional sense; offline priors calibrated on train splits, others fixed hyperparameters such as pseudo-count s=2. The replay evaluation runs offline with precomputed draws and correctness labels to enable reproducibility without actual model inference. 5. Evaluation protocol: Policies are replayed on held-out test correctness tensors, simulating per-query budgeted allocations with early stopping. Performance is measured by expected accuracy (correctness probability) as a function of average cost, with multiple random draw orderings to estimate mean and variance. Baselines include single-route best model, learned one-commit router, budget-aware best-of-K (only resampling a single model), FrugalGPT-style cascades, random allocation, and non-deployable oracle allocation with perfect labels. Ablations vary verifier quality parametrically (q=1 perfect down to q=0 random), prior calibration fraction, pseudo-count, and real-price cost vectors. Additional real-verifier instantiations include agreement-based checking and partial test-suite verification for code. Latency in rounds of sequential draws is also reported. 6. Reproducibility: Code and regenerated correctness tensors are released for reproducing all replay experiments without requiring LLM inference or GPU. The study runs on CPU only for evaluation. Overall, the methodology rigorously simulates a realistic per-query cost-constrained environment with multiple LLM candidates and a noisy verifier, allowing precise measurement of how budget allocation policies trade off resampling vs rerouting to maximize end accuracy.

Technical innovations

• Formulation of test-time model selection as a budgeted correctness-maximization problem jointly allocating budget between resampling and rerouting actions under an imperfect verifier.
• Design of a simple marginal-gain greedy RoR policy that selects the next action maximizing estimated marginal correctness gain per unit cost from the candidate pool.
• Incorporation of a Bayesian per-query posterior belief update combining offline model priors with verifier signals to estimate success probabilities online.
• Empirical demonstration of the recoverability asymmetry between selection and sampling shaping the optimal allocation behavior, grounded in companion theoretical analysis.
• Extensive replay evaluation over high-fidelity multi-draw correctness tensors from a diverse 11-model pool on 4 benchmarks with real-price and real-verifier deployments.

Datasets

• GSM8K — 500 queries — public benchmark arithmetic dataset
• MATH-500 — 500 queries — public competition math dataset
• GPQA-Diamond — 198 queries — public graduate-level science dataset
• HumanEval+ — 164 queries — public code generation dataset

Baselines vs proposed

• Single-route best model on GSM8K: accuracy=0.966 at cost=32.0 vs RoR: 0.993 at 9.2 cost
• One-commit router on GPQA: 0.566 accuracy at cost=8.0 vs RoR 0.968 at 25.9 cost
• Budget-aware best-of-K on MATH-500: 0.867 accuracy at 25.5 cost vs RoR 0.887 at 26.4 cost
• FrugalGPT-style cascade on HumanEval+: 0.952 accuracy at 22.8 cost vs RoR 0.952 at 20.5 cost
• Random allocation on GPQA: 0.706 accuracy at 24.3 cost vs RoR 0.968 at 25.9 cost
• UCB variant versus greedy RoR on GPQA at low budget: 0.603 vs 0.744 accuracy

Limitations

• The study relies on offline replay of precomputed correctness draws; real-time interaction with live LLMs and verifiers may introduce additional challenges.
• Verifier assumptions impact performance strongly; situations with unreliable or no verifiers degrade RoR benefits and may invert rankings.
• Latency increases as RoR is sequential and adaptive, requiring multiple round trips per query, potentially limiting deployment where latency is critical.
• Cost proxy based on model parameter counts and snapshots of provider prices approximate but do not fully capture real world serving costs.
• The experiments focus on open-weight LLMs and established benchmarks; results may differ with proprietary models or other domains.
• No adversarial or robustness testing against attackers attempting to game the verifier or routing process is presented.

Open questions / follow-ons

• How would RoR perform in fully online deployment with live verifiers that have varying latency and reliability characteristics?
• Can the RoR approach be effectively combined with model compression or quantization techniques to further reduce inference costs?
• How sensitive is RoR to changes in model pool composition, such as adding or removing models dynamically or evolving model quality?
• What mechanisms could improve the verifier’s trustworthiness or enable learning a better verifier to amplify RoR gains?

Why it matters for bot defense

This work is highly relevant for bot-defense and CAPTCHA practitioners looking to deploy large language models cost-effectively under strict per-query compute budgets while maximizing response quality. The formalism and Resample-or-Reroute policy provide a practical framework to allocate inference budget optimally between repeated sampling of a committed model and rerouting to different models within a diverse LLM pool, guided by imperfect correctness verification signals. From a usage perspective, CAPTCHA or challenge-response systems aimed at robust bot differentiation can leverage this approach to balance accuracy gains from adaptive sampling against latency and serving costs. Furthermore, the insight into verifier quality gating the effectiveness of rerouting emphasizes the need for strong answer verification methods, a critical consideration when designing robust human-bot separation schemes. Finally, the replay-based evaluation methodology offers a blueprint for offline policy tuning in realistic serving contexts with diverse models and benchmarks.

Cite

@article{arxiv2607_08665,
  title={ Resample or Reroute? Budget-Aware Test-Time Model Selection for Large Language Models },
  author={ Teng-Ruei Chen },
  journal={arXiv preprint arXiv:2607.08665},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.08665}
}

Read the full paper

• arXiv:2607.08665 (abstract)
• arXiv:2607.08665 (PDF)