Give Up to Get More: Priors, Not Policies, Govern Test-Time Compute Allocation

📌 Highlights

The paper's central claim is that test-time compute allocation should follow marginal value, not difficulty alone. Under a binary success objective, the value of another independent attempt is highest for inputs of intermediate solvability. The optimal static curve is therefore inverted-U shaped: hopeless inputs should be deprioritized, moderately solvable inputs should receive extra attempts, and nearly solved inputs need little additional budget.

The empirical results are strongest on hard workloads. At u=16, the best published calibration rule captured 0% of oracle headroom on MATH with Pythia-1.4B and Pythia-6.9B, 1% on CodeContests with Llama-3-8B, and 13% on MATH with Gemma-2B, despite receiving true pass rates. The same class of rule captured 50% to 102% on higher-pass-rate workloads, where monotone allocation is closer to the optimum.

With a verifier, the decisive factor was prior information. On hard workloads, Thompson Sampling, UCB, and the Bayes-myopic index gained over round-robin when supplied with related-model history, but none reliably helped with an exchangeable prior. On the hardest MATH workload, a related history nearly doubled solved share from 14% to 27% at 16 attempts per problem.

The main engineering caveat is calibration. Gains decline with prior rank correlation, can disappear below roughly 0.3 to 0.4 for Thompson Sampling in the reported Pythia experiments, and are highly sensitive to false acceptance. The paper's evidence favors round-robin when no informative history or reliable verifier is available.

• Harder-gets-more is near-optimal mainly when the planned budget is large relative to workload difficulty.
• Related-model histories are substantially more useful than text-only difficulty estimates or charged samples from smaller models.
• False acceptances are more damaging than false rejections because an incorrectly accepted input leaves the allocation pool.
• Tempering protects easy workloads from an imperfect prior, but the fixed 0.75 weight is illustrative rather than a validated universal default.

🎯 Introduction

The paper addresses a recurring systems problem: a model must make repeated attempts on a fixed collection of inputs while the total sampling budget is limited. This appears in repeated benchmark sampling, reinforcement learning with verifiable rewards, regression testing, unit-tested code generation, and formal-proof generation. A natural heuristic is to estimate difficulty and allocate more attempts to harder inputs. The paper asks when that heuristic is actually justified, what information is required for adaptive allocation, and how the answer changes when a verifier can remove solved inputs from the pool.

The prior limitation is not simply inaccurate difficulty estimation. Even when the rules receive true per-input pass rates, difficulty-proportional allocation can be nearly useless on hard workloads. The reason is that an input with a very small success probability may be effectively hopeless at the available budget, so spending extra attempts there has low marginal value. Conversely, easy inputs may already be solved with high probability. The paper therefore reframes difficulty allocation as a marginal-value problem and connects the result to classical search, crowdsourcing, solver scheduling, and allocation theory.

The paper's objective is practical rather than to introduce a new learned allocator. It measures when reallocation pays, compares static and sequential policies, quantifies how informative a prior must be, tests verifier and cost imperfections, and turns the findings into calibration checks for practitioners. Its evidence focuses on binary, verifiable success in math, code, and formal proofs, with stored samples from the Large Language Monkeys, PRM800K, and Weaver releases plus one fresh Qwen2.5 replication.

🔬 Methodology

The static problem assumes N inputs, pass rate p_i for input i, independent repeated attempts, and a total budget S=uN. If input i receives k_i attempts, its probability of being solved is 1-(1-p_i)^{k_i}. The paper maximizes expected solved-input coverage subject to the budget and a minimum of one attempt per input. The incremental value of the (k+1)-th attempt is Δ(p,k)=p(1-p)^k. Because this value is concave in the number of attempts for a fixed input, a greedy marginal-value allocation is optimal under the stated assumptions. Reparameterizing with r=-ln(1-p) gives the continuous solution k*(r)=max(0,ln(r/λ)/r), where λ is set by the budget. This solution first rises with solvability, peaks at intermediate difficulty, and then falls for very easy inputs. The paper also uses the share of inputs on the left branch of this curve as a diagnostic, while noting that mean pass rate performs similarly on the tested workload combinations.

The sequential problem assumes a verifier that accepts successful attempts and removes solved inputs from the pool. Round-robin over unsolved inputs is the baseline because, under an exchangeable prior and no input-specific information, unsolved inputs with the same failure count are indistinguishable. The evaluated policies are Thompson Sampling, an upper confidence bound rule, and a Bayes-myopic index. Their informative prior is built from a related model's historical pass rate on the same inputs, grouped by history-signal quintile and calibrated with cross-fitting. A tempered prior mixes that input-specific distribution with the exchangeable distribution, allowing the system to reduce overconfident specialization. The paper degrades history signals with logit noise, varies rank correlation, and tests verifier false acceptance, false rejection, and output-length charging.

For static experiments, the authors replay identical stored samples so that allocation rules are compared on the same attempt pools. The primary sources are Large Language Monkeys samples for MATH, GSM8K, CodeContests, and MiniF2F across Pythia, Gemma, and Llama-3 models; PRM800K MATH samples; and Weaver GSM8K samples from GPT-4o-mini. For sequential experiments, the paper uses programmatic verification where available, stored reward-model scores for MATH500 and GPQA, and newly generated hard MATH-500 samples from Qwen2.5-0.5B-Instruct, Qwen2.5-Math-1.5B-Instruct, and Qwen2.5-Math-7B-Instruct. This design separates the allocation mechanism from the model-generation pool while exposing the assumptions that may limit deployment.

📊 Experiments

The experiments cover MATH, GSM8K, CodeContests, MiniF2F formal proofs, PRM800K MATH, MATH500, GPQA, MMLU-Pro, and freshly generated hard MATH-500 samples from the Qwen2.5 family. The static evaluation uses public stored samples, with each problem's pool pass rate defining its coverage curve. Every allocation spends uN attempts and gives every input at least one attempt; uniform allocation is the baseline, while the oracle uses true pass rates and greedy marginal gains. The compared static rules include IAS calibration, k(1-p), another difficulty-proportional rule, and 21:30:45 pass-rate tiers.

Table 1 shows the core hardness effect. At u=16, IAS captured 0% of oracle headroom on MATH with Pythia-1.4B and Pythia-6.9B, 1% on CodeContests with Llama-3-8B, and 13% on MATH with Gemma-2B. On MATH with Llama-3-8B and Llama-3-70B, it captured 50% and 74%, respectively; on GSM8K with Llama-3-8B it captured 93%. The paper reports that the best difficulty-proportional rule captured at most 13% on hard workloads but at least half on workloads the model mostly solves. With realistic history signals, only the marginal-value rule gained consistently, while IAS and k(1-p) were near zero and tiers lost up to 3.1 points.

The verifier experiments change the baseline to round-robin over unsolved inputs. With related-model history, all three sequential policies improved hard workloads, with gains up to 14.1 points in the 20-replay comparison and up to 14.2 points in the 100-replay comparison. Without the history prior, no policy beat round-robin by more than 0.3 points across the reported cells. Controlled degradation showed gains falling smoothly as prior rank correlation declined: on the Pythia workloads, gains moved from roughly +12 to +14 points at rank correlation 0.93, to +4 to +6 around 0.67, and to approximately zero or negative values near 0.3 to 0.4. Policy differences were smaller than prior-quality effects.

The fresh Qwen2.5 replication preserved this pattern. For a 0.5B target with 1.5B history at u=4, Thompson Sampling gained +2.4 points over round-robin; with 7B history it gained +1.8 points. For an already-easy 1.5B target with 7B history, untempered Thompson Sampling lost 1.6 points at u=4 and 4.2 points at u=16, while UCB lost 5.2 and 10.9 points. Tempering reduced or eliminated these losses. Verifier stress tests found that 20% false rejection left gains intact or larger, whereas 5% false acceptance reduced gains to at most 0.6 points on the tested hard workloads. Learned reward models on GPQA and hard MATH500 often had insufficient discrimination, so the strongest positive results remain associated with programmatic verifiers and informative histories.

fig:1

Caption: Optimal attempts versus pass rate for three budgets, compared with a ``harder gets more'' rule ($k 1-p$). The optimum gives nothing to inputs that are hopeless at the given budget, and its peak moves toward harder inputs only as the budget grows.

Why It Matters: This figure is the central conceptual result: the optimal allocation is non-monotone in difficulty, and the region where harder-gets-more is appropriate expands only as the average budget grows relative to workload difficulty.

fig:3

Caption: Solved share relative to round-robin at $u=16$. With a history prior, all three policies gain on hard workloads. Without it (grey), none does. The surveyed rule (dark) never helps.

Why It Matters: The comparison isolates prior quality from policy choice: standard policies improve hard workloads when given related-model history, while the same policies do not improve round-robin with an exchangeable prior.

🔮 Conclusion

The paper concludes that harder-gets-more is conditionally correct, not generally correct. It works when the average budget is large relative to difficulty, but fails on hard workloads because the optimal allocation is inverted-U shaped and avoids spending heavily on hopeless inputs. In verifier-based allocation, the main source of improvement is an informative prior from related-model history, not fine distinctions among Thompson Sampling, UCB, and the Bayes-myopic index. The practical default is round-robin without a validated prior, followed by tempered Thompson Sampling when calibration demonstrates useful predictive rank correlation and the verifier has rare false acceptances.

The reported evidence supports this conclusion across stored samples and a fresh Qwen2.5 replication, but the authors explicitly limit the claim to recurring inputs with binary, verifiable success in math, code, and formal proofs. Frontier models, open-ended tasks, and novel inputs remain unresolved.

🛠️ Future Research Improvements

The most direct next experiment is live generation with a frontier reasoning model on a recurring benchmark, using the previous release's per-input outcomes as the history prior. That would test whether the reported gains transfer beyond open models up to 70B parameters and beyond replayed samples. The paper also motivates calibrated learned verifiers that use historical outcomes, repeated acceptance checks, or other mechanisms to keep false acceptance rare on hard inputs; this could make adaptive allocation useful when programmatic verification is unavailable.

For novel inputs, future work should seek priors that exceed the reported break-even range at acceptable cost. Text features, strong-LLM difficulty judgments, dissimilar-model histories, and charged proxy samples produced weak or negative results on the hardest settings. A useful extension would compare semantic, retrieval-based, and small-pilot signals under an explicit cost budget, then evaluate whether combining them with a tempered exchangeable prior transfers across domains.

The allocation theory should also be extended to correlated attempts, continuous reward objectives, heterogeneous latency, and policies that learn jointly with the verifier. The present experiments treat attempts as independent and test only four policies. Evaluating adaptive generators, feedback-conditioned retries, and compute spent within a single reasoning trace would clarify where the paper's whole-attempt abstraction stops being predictive.

🏭 Potential Industry Use Scenarios

In reinforcement learning with verifiable rewards, teams repeatedly revisit the same prompt pool across epochs. Per-prompt pass histories can become a nearly free prior because the sampling has already occurred, allowing rollout budgets to favor prompts that are solvable but not yet saturated. The paper's inverted-U result also supports dropping prompts that are always solved or always failed when the objective is to obtain useful binary reward signals.

For code-generation evaluation and continuous integration, unit tests provide the kind of programmatic verifier assumed by the sequential experiments. A system could retain per-test or per-problem histories across model checkpoints, use calibration data to decide whether the history predicts the new model, and allocate more retries to unsolved cases with credible success probability. The same pattern applies to formal theorem proving with proof checkers and to recurring math benchmark suites with answer keys.

Regression-testing systems should be especially cautious on easy suites. An imperfect history prior can starve the small number of difficult cases that remain, producing lower solved share even when the average score is already high. Tempering toward an exchangeable prior and measuring false acceptance before deployment are therefore operational safeguards. For open-ended customer queries without reliable verification or recurring-input history, the paper provides no evidence that adaptive allocation will outperform uniform sampling.

💬 Critical Analysis

The paper's strongest feature is the separation of three factors that are often conflated: workload hardness, prior informativeness, and policy choice. The static experiments give difficulty-based heuristics their most favorable setting by supplying true pass rates, yet still show near-zero gains on hard workloads. The sequential experiments then hold the policy family relatively standard and vary the prior, demonstrating that input-specific information accounts for the largest effect. The controlled degradation study is particularly useful because it turns a qualitative claim about prior quality into a measurable calibration relationship.

The theory is also well matched to the reported results. The marginal-value expression explains why an input with very low pass rate may be a poor target even when it is labeled difficult, while the verifier analysis explains why false acceptance is more damaging than false rejection. The fresh Qwen2.5 experiment strengthens the argument beyond stored replay, and the tempering experiment gives builders a concrete response to prior misspecification.

There are important reasons to avoid overgeneralizing. The static setting assumes independent attempts with a fixed per-input pass rate, excluding feedback-conditioned retries and within-attempt search. The sequential setting assumes a verifier whose acceptances determine removal from the pool, and its most convincing positive cases use programmatic verification. Learned reward models were weak on several hard subsets, so the paper does not establish a general recipe for neural verification. The history prior also requires recurring inputs; the weak results from text-only and proxy-model signals leave novel-input allocation largely unresolved.

The survey evidence is informative but not a precise prevalence estimate because candidate screening and parts of the coding were LLM-assisted, inclusion screening was automated, and the strict count is described as an approximate lower bound. The empirical scope is likewise limited to selected benchmarks, open models, four policy families, offline replays, and one fresh-model replication. The paper's recommendations are therefore best interpreted as calibration hypotheses: measure rank correlation and verifier false acceptance on the intended workload, compare against round-robin, and verify that improvements persist under real cost, latency, and model-release conditions.