Give Up to Get More: Priors, Not Policies, Govern Test-Time Compute Allocation
Organizations: Department of Industrial and Management Engineering, Hankuk University of Foreign Studies, Yongin, Republic of Korea
Abstract
When many inputs share a budget of repeated attempts by a large language model (LLM), a common rule gives harder inputs more. On public math, code and formal-proof samples, the best published difficulty-proportional rule captures half or more of the oracle gain on benchmarks the model mostly solves, but at most 13% on hard workloads, even given true pass rates. Because the value of one more attempt peaks at intermediate difficulty, the optimal static allocation is inverted-U and gives little to inputs that are hopeless at the current budget. In a strict survey of 221 LLM allocation papers, at least 13 give the hardest inputs the most attempts; their easier settings sit at budgets where this is near-optimal, so the cost appears on harder workloads. Acting on it requires knowing which inputs are solvable, so information, not the policy, drives the gain. With a verifier and a prior from a related model's past runs on the same inputs, Thompson Sampling raises the solved share on the hardest workload from 14% to 27%; without such a prior, no policy we tested beats round-robin. For the policies we tested, the gain vanishes between prior rank correlations of about 0.3 and 0.55, which cheap text-based priors barely reach on the weakest models, and it requires a verifier whose false acceptances are rare relative to the pass rate. On new Qwen2.5 samples the pattern holds, and tempering the prior avoids losses on easy workloads. We turn these results into a decision guide.
Figures & tables
| workload | N problems | mean p | oracle gain (pts) | IAS | tiers | |
|---|---|---|---|---|---|---|
| MATH, Pythia-1.4B | 128 | 0.013 | +8.4 | 0% | 1% | 34% |
| MATH, Pythia-6.9B | 128 | 0.019 | +8.1 | 0% | 2% | 40% |
| CodeContests, Llama-3-8B | 140 | 0.021 | +4.8 | 1% | 1% | 0% |
| CodeContests, Llama-3-70B | 140 | 0.074 | +6.0 | 2% | 2% | 16% |
| MATH, Gemma-2B | 128 | 0.093 | +7.4 | 13% | 6% | 34% |
| MATH, Llama-3-8B | 128 | 0.268 | +6.3 | 50% | 40% | 15% |
| workload (history from) | u | RR solved | TS, exch. | TS, history | UCB, hist. | myopic, hist. | surveyed rule |
|---|---|---|---|---|---|---|---|
| MATH, Pythia-1.4B (Pythia-6.9B) | 16 | 14.1% | 0.2 | +12.5 | +12.7 | +12.1 | 0.0 |
| MATH, Pythia-6.9B (Pythia-1.4B) | 16 | 18.6% | +0.3 | +13.8 | +14.1 | +13.6 | 0.0 |
| MATH, Gemma-2B (Llama-3-8B) | 4 | 23.4% | +0.1 | +6.3 | +6.2 | +5.5 | 0.0 |
| MATH, Gemma-2B (Llama-3-8B) | 64 | 72.4% | 0.1 | +2.1 | +0.7 | 2.7 | 1.6 |
| CodeContests, Llama-3-8B (70B) | 16 | 5.5% | 0.1 | +4.0 | +3.8 | +3.7 | 0.0 |
| MiniF2F (Lean), Llama-3-8B (70B) | 16 | 40.0% | +0.2 | +2.1 | +1.7 | +0.2 | 4.4 |
| prior source | Spearman with true p | gain vs RR |
|---|---|---|
| TF-IDF regression on problem text | 0.05–0.23 | 0 |
| LLM features (bge-large embedding; Qwen2.5-1.5B difficulty rating, P(solvable), NLL) | 0.10–0.46 | 2.1 to 0.1 ( 0 when tempered) |
| Zero-shot difficulty judgments by strong LLMs (Gemini, Claude; ratings or listwise rankings of the problem text) | 0.36–0.40 (Pythia), 0.58 (Gemma-2B) | 0.1 to +1.7 |
| Past runs of a dissimilar model (Pythia history for Llama-3-8B) | 0.42 | 1.1 |
| 16 fresh samples from a smaller model, cost charged | — | 1.7 to 4.2 |
| Past runs of a related model | 0.69–0.93 | +3.4 to +13.7 |
| workload | rank corr. of prior | TS | UCB | myopic | TS UCB | TS myopic |
|---|---|---|---|---|---|---|
| MATH, Pythia-1.4B | 0.93 | +12.2 | +12.6 | +12.5 | 0.4 [ 0.6, 0.1] | 0.3 [ 0.7, +0.1] |
| 0.83 | +8.5 | +8.8 | +8.7 | 0.3 [ 0.7, 0.0] | 0.2 [ 0.6, +0.2] | |
| 0.67 | +4.2 | +4.6 | +5.1 | 0.4 [ 0.8, 0.1] | 0.8 [ 1.3, 0.3] | |
| 0.50 | +1.9 | +2.4 | +2.5 | 0.6 [ 0.9, 0.3] | 0.6 [ 1.1, 0.2] | |
| 0.42 | +0.6 | +1.1 | +1.4 | 0.5 [ 0.8, 0.2] | 0.7 [ 1.1, 0.4] | |
| 0.29 | 0.8 | 0.2 | 0.2 | 0.6 [ 0.9, 0.2] | 0.6 [ 1.1, 0.1] |
| target history | u | RR solved | TS, history | UCB, history | TS, exch. | |
|---|---|---|---|---|---|---|
| 0.5B Math-1.5B | 0.62 | 4 | 36.0% | +2.4 [+2.0, +2.8] | +2.6 [+2.2, +3.0] | 0.2 [ 0.4, 0.0] |
| 0.62 | 16 | 58.4% | 0.1 [ 0.5, +0.3] | 1.8 [ 3.1, 0.6] | 0.0 [ 0.1, +0.1] | |
| 0.5B Math-7B | 0.56 | 4 | 35.4% | +1.8 [+1.4, +2.2] | +2.2 [+1.8, +2.7] | 0.3 [ 0.4, 0.1] |
| 0.56 | 16 | 57.6% | +0.3 [0.0, +0.6] | 0.3 [ 1.1, +0.3] | 0.0 [ 0.1, +0.2] | |
| Math-1.5B Math-7B | 0.77 | 4 | 86.4% | 1.6 [ 2.3, 1.0] | 5.2 [ 6.5, 4.1] | 0.0 [ 0.1, 0.0] |
| 0.77 | 16 | 91.0% | 4.2 [ 4.9, 3.4] | 10.9 [ 12.1, 9.7] | 0.0 [0.0, 0.0] |
| target history | u | history (w = 1) | tempered (w = 0.75) | tempered (w chosen by CV) |
|---|---|---|---|---|
| 0.5B Math-1.5B | 4 | +2.9 | +2.4 | +1.6 |
| 0.5B Math-1.5B | 16 | 0.3 | +0.4 | 0.1 |
| Math-1.5B Math-7B | 4 | 1.7 | +0.4 | 0.5 |
| Math-1.5B Math-7B | 16 | 4.1 | 0.0 | 0.0 |
| workload | no errors | FA 1% | FA 2% | FA 5% | FR 20% | length-charged |
|---|---|---|---|---|---|---|
| MATH, Pythia-1.4B | +11.1 | +10.1 | +6.7 | +0.6 | +12.1 | +13.2 |
| MATH, Pythia-6.9B | +11.7 | +8.8 | +7.3 | +0.3 | +11.6 | +14.5 |
| MATH, Gemma-2B | +3.4 | +3.4 | +1.9 | 0.0 | +4.7 | +5.1 |
| CodeContests, Llama-3-8B | +3.3 | +2.7 | +1.9 | +0.3 | +3.1 | +3.6 |
| workload | verifier | FA target | RR solved | RR falsely accepted | TS gain |
|---|---|---|---|---|---|
| MATH500, hard (N = 173, mean p 0.13) | perfect | — | 25.6% | 0% | +2.5 [+1.0, +3.8] |
| Qwen PRM (min) | 1% | 3.5% | 1.5% | +1.1 [+0.2, +2.0] | |
| Qwen PRM (min) | 5% | 12.6% | 7.2% | +1.7 [ 0.1, +3.5] | |
| InternLM2 Reward 7B | 1% | 0.5% | 2.1% | +0.2 [ 0.2, +0.5] | |
| InternLM2 Reward 7B | 5% | 2.1% | 8.2% | +0.9 [+0.4, +1.4] | |
| GPQA, hard (N = 414, mean p 0.12) | perfect | — | 23.3% | 0% | 2.7 [ 3.7, 1.7] |
| workload | hopeless share | bound, FA 0 / 1% / 2% / 5% | TS (Table 7 ), FA 0 / 1% / 2% / 5% | |
|---|---|---|---|---|
| MATH, Pythia-1.4B | 0.64 | 0.88 | 17.1 / 11.6 / 7.4 / 0.5 | 11.1 / 10.1 / 6.7 / 0.6 |
| MATH, Pythia-6.9B | 0.55 | 0.84 | 17.5 / 12.0 / 7.9 / 0.2 | 11.7 / 8.8 / 7.3 / 0.3 |
| MATH, Gemma-2B | 0.34 | 0.60 | 15.6 / 9.3 / 4.7 / 0.0 | 3.4 / 3.4 / 1.9 / 0.0 |
| CodeContests, Llama-3-8B | 0.91 | 0.95 | 7.0 / 3.0 / 1.6 / 0.2 | 3.3 / 2.7 / 1.9 / 0.3 |
| MATH, Llama-3-8B | 0.15 | 0.29 | — | — |
| workload | verifier | FA target | measured FA | measured TA | predicted ratio | simulated TS ratio |
|---|---|---|---|---|---|---|
| MATH500, hard | Qwen PRM | 1% | 0.010 | 0.15 | 0.25 | 0.44 |
| MATH500, hard | Qwen PRM | 5% | 0.050 | 0.54 | 0.67 | 0.67 |
| MATH500, hard | InternLM2 RM | 1% | 0.012 | 0.02 | 0.03 | 0.07 |
| MATH500, hard | InternLM2 RM | 5% | 0.050 | 0.07 | 0.12 | 0.37 |
| GPQA, hard | ArmorRM | 1% | 0.010 | 0.03 | 0.05 | 0.05 |
| GPQA, hard | ArmorRM | 5% | 0.050 | 0.05 | 0.09 | 0.19 |
Appendix figures & tables19 assets
Supplementary material from the paper’s appendix.
Appendix
| domain | r(true headroom, Atkinson closed form) | r(true, optimum on fitted curves) | mean true headroom (%) |
|---|---|---|---|
| NCO cluster AM | 0.97 | 0.99 | 9.83 |
| NCO cluster SymNCO | 0.97 | 1.00 | 7.15 |
| NCO size AM | 0.92 | 0.97 | 0.83 |
| NCO size SymNCO | 0.93 | 0.98 | 0.77 |
| HPO-B all pairs | 0.80 | 0.93 | 13.80 |
| LLM GSM8K 4o-mini RM internlm | 0.96 | 0.98 | 1.27 |
| cell | objective | power-law R 2 | exp. R 2 | spread given level | level given spread |
|---|---|---|---|---|---|
| NCO cluster AM | continuous | 0.996 | 0.490 | +0.89 [+0.89, +0.91] | +0.41 [+0.26, +0.49] |
| NCO cluster SymNCO | continuous | 0.996 | 0.521 | +0.91 [+0.90, +0.91] | +0.34 [+0.24, +0.39] |
| NCO size AM | continuous | 0.998 | 0.568 | +0.54 [+0.51, +0.60] | -0.71 [-0.73, -0.64] |
| NCO size SymNCO | continuous | 0.999 | 0.568 | +0.80 [+0.74, +0.81] | -0.58 [-0.70, -0.51] |
| HPO-B all pairs | continuous | 0.992 | 0.723 | +0.76 [+0.75, +0.77] | +0.59 [+0.58, +0.66] |
| LLM GSM8K 4o-mini RM internlm | continuous | 0.998 | 0.784 | +0.93 [+0.93, +0.94] | +0.24 [+0.14, +0.28] |
| solver | reported in-sample estimate (MC curves) | true headroom (exact curves) | sample-split estimate | mean max MC curve error (pts) |
| POMO | 2.227 | 1.568 | 0.493 | 0.46 |
| AM | 2.567 | 1.122 | 0.168 | 3.68 |
| SymNCO | 2.206 | 1.193 | 0.215 | 6.93 |
| # | check | paper (arXiv) | allocation rule | verbatim fragment | section |
|---|---|---|---|---|---|
| 1 | confirmed | Make Every Penny Count (DSC), 2408.13457 | Easy: 1 sample. Hard: resample until a stopping criterion, else cap 40. | “For problems belonging to easy part, a single CoT sampling is performed” | Section 2 , Section 2 .3 |
| 2 | confirmed | Evolving in-context demonstrations, 2604.21018 | Unsolved queries keep sampling each round until T. Elimination uses a ground-truth oracle. | “focuses compute on harder queries as easier ones are resolved” | Section 4 .2.2, Alg. 1 |
| 3 | confirmed | Think Right, Not More, 2509.22101 | Level-0 claims: one shot. Level-1 claims (including persistently misclassified ones): expanded best-of-N. | “one-shot inference for level-0 claims, and expanded reasoning for level-1” | Section 3 .2 |
| 4 | borderline (a) | CoBa, 2608.07424 | One extra candidate at a time until the top answer is stable and highly scored, up to max. The extra compute also routes the top-K candidates to a strong verifier. | “Generate one additional candidate and score it” | Alg. 1 (Section 4 ) |
| 5 | confirmed | Scaling with Confidence (CAS), 2607.01612 | Sample until stop-probability exceeds a threshold or reaches N. The threshold is tuned on evaluation sets. | “otherwise, the inference continues with next generation” | Section 3 .3, Alg. 1 |
| 6† | borderline (a) | AttnRL, 2509.26628 | Trees per problem = ; zero pass rate gets the maximum. RL training. The unit is tree branches from shared prefixes. | “we expand different number of trees according to problem difficulty” | Section 3 .2.1, Eq. 9 |
| paper | setting | u (mean, per input) | (measure) | u |
|---|---|---|---|---|
| Self-Calibration (Huang et al., 2025) | 3 tasks 3 models | 16 (matched) | 0.58–0.90 (pass@1) | 9–14 |
| IAS (Park et al., 2025) | MATH500, 6 models | 15–41 | 0.23–0.80 (pass@1) | 9–15 |
| IAS (Park et al., 2025) | AIME24–25, 6 models | 58–64 | 0.004–0.14 (pass@1) | 0.3–8.7 |
| DSC, 2408.13457 | 6 tasks, GPT-4 / GPT-3.5 | 6–33 (from cost) | 0.49–1.00 (SC@40) | 6–17 |
| CAS, 2607.01612 | in-domain, OOD text, OOD multimodal | 5.2–10.9 | 0.45–0.71 (pass@1) | 3.2–7.0 |
| FSC (Yeom et al., 2026) | MATH500, AMC23, 4 models | 9–22 (from tokens) | 0.50–0.82 (SC@40) | 7–13 |
| workload | u | RR solved | TS exch. | UCB exch. | TS history | UCB history | myopic history |
|---|---|---|---|---|---|---|---|
| MATH_Pythia-1.4B | 4 | 4.8% | -0.4 | +0.0 | +7.9 | +8.0 | +7.9 |
| MATH_Pythia-1.4B | 16 | 14.1% | -0.2 | +0.0 | +12.5 | +12.7 | +12.1 |
| MATH_Pythia-1.4B | 64 | 34.7% | -0.1 | +0.0 | +12.3 | +12.2 | +11.8 |
| MATH_Pythia-6.9B | 4 | 6.5% | -0.5 | +0.0 | +8.7 | +9.3 | +8.9 |
| MATH_Pythia-6.9B | 16 | 18.6% | +0.3 | +0.0 | +13.8 | +14.1 | +13.6 |
| MATH_Pythia-6.9B | 64 | 41.6% | -0.1 | +0.0 | +12.3 | +13.5 | +13.9 |
| workload pair | u | RR solved | history | CV-tempered | chosen w | E2 online |
|---|---|---|---|---|---|---|
| MATH_Pythia-1.4B <- MATH_Pythia-6.9B | 4 | 4.8% | +8.5 | +7.5 | 0.61 | +0.0 |
| MATH_Pythia-1.4B <- MATH_Pythia-6.9B | 16 | 14.7% | +11.5 | +10.8 | 0.76 | +0.0 |
| MATH_Pythia-1.4B <- MATH_Pythia-6.9B | 64 | 33.4% | +13.2 | +11.9 | 0.86 | -0.3 |
| MATH_Gemma-2B <- MATH_Llama-3-8B-Instruct | 4 | 25.7% | +4.2 | +3.8 | 0.70 | +0.0 |
| MATH_Gemma-2B <- MATH_Llama-3-8B-Instruct | 16 | 46.2% | +2.9 | +1.8 | 0.56 | -0.6 |
| MATH_Gemma-2B <- MATH_Llama-3-8B-Instruct | 64 | 71.1% | -3.2 | -1.0 | 0.46 | -1.6 |
| workload pair | u | RR solved | history | CV-tempered | chosen w |
|---|---|---|---|---|---|
| MATH500 8B <- 70B | 4 | 93.5% | -0.0 | +0.0 | 0.52 |
| MATH500 8B <- 70B | 16 | 99.2% | -1.4 | -0.0 | 0.00 |
| MATH500 8B <- 70B | 64 | 99.2% | -0.9 | -0.0 | 0.00 |
| MATH500 70B <- 8B | 4 | 97.9% | -2.0 | -0.3 | 0.24 |
| MATH500 70B <- 8B | 16 | 98.6% | -3.2 | +0.0 | 0.00 |
| MATH500 70B <- 8B | 64 | 98.6% | -2.3 | +0.0 | 0.00 |
| workload | 3 bins | 5 bins | 10 bins |
|---|---|---|---|
| MATH_Pythia-1.4B | +11.0 | +12.4 | +11.6 |
| MATH_Pythia-6.9B | +12.2 | +13.1 | +13.4 |
| MATH_Gemma-2B | +3.0 | +5.1 | +2.2 |
| CodeContests_Llama-3-8B-Instruct | +2.1 | +3.7 | +3.9 |
| target proxy | m = 4 | m = 8 | m = 16 | m = 32 |
|---|---|---|---|---|
| MATH_Pythia-1.4B | -1.0 | -1.9 | -3.7 | -7.9 |
| MATH_Pythia-6.9B | -1.2 | -1.8 | -2.6 | -3.4 |
| workload | FR | FA | RR solved | RR falsely accepted | TS exch. RR | TS history RR | TS history falsely accepted |
|---|---|---|---|---|---|---|---|
| MATH_Pythia-1.4B | 0% | 0% | 14.6% | 0.0% | -0.3 | +11.1 | 0.0% |
| MATH_Pythia-1.4B | 0% | 1% | 13.6% | 15.4% | +0.2 | +10.1 | 17.3% |
| MATH_Pythia-1.4B | 0% | 2% | 14.2% | 30.3% | -0.1 | +6.7 | 31.3% |
| MATH_Pythia-1.4B | 0% | 5% | 12.7% | 79.4% | +0.1 | +0.6 | 78.4% |
| MATH_Pythia-1.4B | 0% | 10% | 8.4% | 91.6% | +0.0 | +0.0 | 91.6% |
| MATH_Pythia-1.4B | 20% | 0% | 11.2% | 0.0% | -0.2 | +12.1 | 0.0% |
| workload | mean length (chars) | correct samples | incorrect samples | Spearman(length, p) | RR solved | TS history RR (sd) |
|---|---|---|---|---|---|---|
| MATH_Pythia-1.4B | 606 | 349 | 609 | -0.27 | 14.4% | +13.2 (2.5) |
| MATH_Pythia-6.9B | 644 | 454 | 647 | -0.18 | 20.2% | +14.5 (3.0) |
| MATH_Gemma-2B | 551 | 323 | 574 | -0.47 | 44.8% | +5.1 (2.4) |
| CodeContests_Llama-3-8B-Instruct | 440 | 299 | 443 | -0.17 | 6.0% | +3.6 (1.4) |
| task | reward model | AUROC | AUROC (hard) | FA at =1% | TA at =1% | FA at =5% | TA at =5% |
|---|---|---|---|---|---|---|---|
| GPQA | weaver | 0.51 | 0.50 | 2.7% | 2.7% | 12.4% | 13.1% |
| GPQA | Skyworks | 0.57 | 0.52 | 2.3% | 4.7% | 4.8% | 9.9% |
| GPQA | ArmorRM | 0.57 | 0.52 | 1.0% | 5.1% | 5.4% | 11.7% |
| GPQA | QRM | 0.58 | 0.51 | 2.5% | 4.8% | 5.2% | 10.0% |
| GPQA | GRM | 0.58 | 0.52 | 2.3% | 4.0% | 5.2% | 8.9% |
| GPQA | URM | 0.57 | 0.50 | 2.2% | 4.4% | 4.8% | 10.0% |
| task | verifier | RR solved | RR falsely accepted | TS history RR [95% CI] |
|---|---|---|---|---|
| MATH500 | perfect | 97.7% | 0.0% | -0.3 [-0.8, +0.0] |
| MATH500 | QwenPRM_min, FA target 0.01 | 18.2% | 9.7% | +0.0 [-0.3, +0.3] |
| MATH500 | QwenPRM_min, FA target 0.05 | 46.0% | 38.4% | -0.1 [-0.6, +0.5] |
| MATH500 | InternLM2Reward7B, FA target 0.01 | 3.7% | 16.2% | +0.2 [-0.1, +0.6] |
| MATH500 | InternLM2Reward7B, FA target 0.05 | 11.7% | 53.0% | +0.2 [-0.2, +0.6] |
| GPQA | perfect | 90.0% | 0.0% | +0.0 [-0.2, +0.2] |
| workload | TS, exchangeable | TS, history | UCB, history | myopic, history |
|---|---|---|---|---|
| MATH, Pythia-1.4B | 0.1 [ 0.3, 0.0] | +12.0 [+11.5, +12.5] | +12.0 [+11.4, +12.5] | +12.0 [+11.4, +12.5] |
| MATH, Pythia-6.9B | 0.1 [ 0.2, +0.1] | +13.7 [+13.1, +14.3] | +14.2 [+13.6, +14.8] | +13.9 [+13.2, +14.6] |
| MATH, Gemma-2B | 0.1 [ 0.3, +0.1] | +3.4 [+2.9, +4.0] | +3.7 [+3.1, +4.3] | +2.6 [+1.8, +3.4] |
| CodeContests, Llama-3-8B | 0.0 [ 0.1, +0.1] | +3.5 [+3.3, +3.8] | +3.5 [+3.3, +3.8] | +3.5 [+3.2, +3.7] |
| MiniF2F, Llama-3-8B | 0.0 [ 0.1, 0.0] | +1.9 [+1.6, +2.2] | +1.4 [+1.0, +1.7] | +0.2 [ 0.5, +0.7] |
| MATH, Llama-3-8B | +0.1 [0.0, +0.2] | +0.6 [+0.2, +0.9] | +0.3 [ 0.1, +0.7] | 0.2 [ 0.6, +0.3] |
Inference-Time Compute Allocation
Inference-time compute allocation decides where, when, and how much computation models spend during prediction to improve quality under resource limits.
See all 91 papers