Pareto Frontier of LLM Test-Time Compute: Adaptive Rollouts and Voting Under Token Budgets

Large language models improve their test-time accuracy by generating multiple rollouts and aggregating them to produce a final answer by voting. As each additional rollout incurs token costs, test-time compute entails a trade-off between accuracy and inference cost. This raises a question: given a limited token budget, how should the budget be allocated to maximize accuracy? Existing approaches typically adapt the number of rollouts to each query while keeping the voting rule fixed. However, the voting rule itself shall be adapted as well. In particular, commonly used schemes such as self-consistency and best-of-$n$ can be viewed as special cases of a broader Boltzmann voting family, and the choice of voting rule directly affects the attainable accuracy ceiling of test-time compute. Motivated by this observation, we formulate the rollout count and voting rule as joint, query-dependent decisions and optimize them under a token-budget constraint. We show that no fixed voting rule is uniformly optimal across all token budgets, whereas the adaptive voting rule yields a cost--accuracy Pareto frontier that dominates the frontier associated with any fixed rule. We further derive a closed-form characterization of the large-budget asymptotics of the Pareto frontier, identifying both the factors that determine the accuracy ceiling and those that govern the rate at which this ceiling is approached. Guided by these results, we propose PRICE (**P**riced **R**ollouts and **I**nference-time voting-rule **C**hoice under a token budg**E**t), an algorithm that jointly and adaptively selects the rollout count and voting rule as a function of the token budget. On MATH-500, PRICE consistently outperforms six test-time compute baselines across all evaluated budgets and achieves comparable accuracy using up to $2.8$--$3.5\times$ fewer token budgets.