PETS: A Principled Framework Towards Optimal Trajectory Allocation for Efficient Test-Time Self-Consistency

Test-time scaling can improve model performance by aggregating stochastic reasoning trajectories. However, achieving sample-efficient test-time self-consistency under a limited budget remains an open challenge. We introduce PETS (**P**rincipled and **E**fficient **T**est-Time **S**elf-Consistency), which initiates a principled study of trajectory allocation through an optimization framework. Central to our approach is the *self-consistency rate*}, a new measure defined as agreement with the infinite-budget majority vote. This formulation makes sample-efficient test-time allocation theoretically grounded and amenable to rigorous analysis. We study both offline and online settings. In the offline regime, where all questions are known in advance, we connect trajectory allocation to crowdsourcing, a classic and well-developed area, by modeling reasoning traces as workers. This perspective allows us to leverage rich existing theory, yielding theoretical guarantees and an efficient majority-voting-based allocation algorithm. In the online streaming regime, where questions arrive sequentially and allocations must be made on the fly, we propose a novel method inspired by the offline framework. Our approach adapts budgets to question difficulty while preserving strong theoretical guarantees and computational efficiency. Experiments show that PETS consistently outperforms uniform allocation. On GPQA, PETS achieves perfect self-consistency in both settings while reducing the sampling budget by up to $75\\%$ (offline) and $55\\%$ (online) relative to uniform allocation.

When using large language models to solve problems, people often sample multiple answers for the same question and select the most likely answer through methods such as majority voting. This is done to improve the self-consistency of the response, under the assumption that the sampled answers reflect the model’s internal true answer. A basic strategy is to sample the same number of responses for every question. Our question is: can we allocate different numbers of samples according to the properties of different questions? To this end, we propose PETS (Principled and Efficient Test-Time Self-Consistency), which uses a warm-up stage to quickly capture the properties of each problem through a two-dimensional parameter, and then applies constrained optimization to allocate the sampling budget. Based on this intuition, we develop both online and offline methods. The online method produces a one-shot result for questions arriving sequentially, while the offline method is given the entire set of questions at once, allowing the budget allocation to be performed globally. Experimental results show that our algorithm achieves significant improvements across various datasets.