Priors Beat Policies in LLM Test-Time Compute Allocation
Give Up to Get More: Priors, Not Policies, Govern Test-Time Compute Allocation
The practical shift is that budget allocation is an information problem: gains come from knowing which inputs are solvable, not from a smarter scheduling rule. Teams running batched evaluation or inference can redirect effort from fancy policies toward building verifier plus prior pipelines. The stated requirement — prior rank correlation above roughly 0.3 to 0.55 and rare false acceptances — gives a concrete feasibility check before deploying such methods.
An arXiv paper (2611.06372) studies how to split a fixed budget of repeated LLM attempts across inputs. Difficulty-proportional rules that give harder inputs more attempts capture at most 13% of oracle gain on hard workloads, versus half or more on easy ones. Among 221 surveyed allocation papers, at least 13 use such rules, which are near-optimal only at easier budgets. With a verifier and a prior from a related model's past runs, Thompson Sampling raises the solved share on the hardest workload from 14% to 27%; without a prior, no tested policy beats round-robin. The pattern holds on new Qwen2.5 samples, and tempering the prior avoids losses on easy workloads.
Give Up to Get More: Priors, Not Policies, Govern Test-Time Compute Allocation
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.