Paper deep dive
PETS: A Principled Framework Towards Optimal Trajectory Allocation for Efficient Test-Time Self-Consistency
Zhangyi Liu, Huaizhi Qu, Xiaowei Yin, He Sun, Yanjun Han, Tianlong Chen, Zhun Deng
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 7/21/2026, 2:10:56 AM
Summary
The paper introduces PETS (Principled and Efficient Test-Time Self-Consistency), a framework for optimizing trajectory allocation in Large Language Models (LLMs) to improve sample efficiency. It defines a 'self-consistency rate' as the probability that a finite-budget majority vote matches the infinite-budget population majority. PETS addresses both offline (batch) and online (streaming) settings. In the offline setting, it models trajectory allocation as a crowdsourcing problem using a Bayesian adaptive algorithm. In the online setting, it uses a one-shot allocation strategy based on estimated question difficulty. Experiments on GPQA show PETS achieves perfect self-consistency while reducing sampling budgets by up to 75% (offline) and 55% (online) compared to uniform allocation.
Entities (8)
Relation Signals (7)
PETS → uses → Self-Consistency Rate
confidence 95% · Central to our approach is the self-consistency rate... This formulation makes sample-efficient test-time allocation theoretically grounded
PETS → reduces → Sampling Budget
confidence 92% · PETS achieves perfect self-consistency in both settings while reducing the sampling budget by up to 75% (offline) and 55% (online)
PETS → evaluatedon → GPQA
confidence 90% · On GPQA, PETS achieves perfect self-consistency
PETS → outperforms → Uniform Allocation
confidence 90% · Experiments show that PETS consistently outperforms uniform allocation.
Offline PETS → modelsas → Crowdsourcing
confidence 88% · In the offline regime... we connect trajectory allocation to crowdsourcing... by modeling reasoning traces as workers.
Online PETS → usesstrategy → One-Shot Allocation
confidence 86% · In the online streaming regime... we propose a novel method... a one-shot allocation strategy
Offline PETS → usesalgorithm → Bayesian Adaptive Trajectory Allocation
confidence 85% · We adopt and extend a Bayesian adaptive trajectory allocation algorithm... that iteratively allocates additional trajectories
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 (Principled and Efficient Test-TimeSelf-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. Code is available at this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2602.16745v2
- Canonical: https://arxiv.org/abs/2602.16745v2
Trouble viewing inline? Open PDF directly →
Full Text
137,287 characters extracted from source content.
Expand or collapse full text
PETS: A Principled Framework Towards Optimal Trajectory Allocation for Efficient Test-Time Self-Consistency Zhangyi Liu Equal contribution. Stanford University Huaizhi Qu* UNC at Chapel Hill Xiaowei Yin* UNC at Chapel Hill He Sun Yale University Yanjun Han New York University Tianlong Chen UNC at Chapel Hill Zhun Deng Contact: zhundeng@cs.unc.edu UNC at Chapel Hill Abstract 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 (Principled and Efficient Test-Time Self-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%75\% (offline) and 55%55\% (online) relative to uniform allocation. Code is available at: this https URL. Figure 1: In this paper, we study how to allocate an LLM’s sampling budget across questions to best match the full-budget outcome under self-consistency. Our results show that PETS substantially reduces the required budget while maintaining accuracy. 1 Introduction Test-time scaling methods can substantially enhance LLMs’ reasoning performance Muennighoff et al. [2025]; Huang et al. [2025b]; Guo et al. [2025]; Snell et al. [2024]; Fu et al. [2025a]. Self-consistency Wang et al. [2022], adopted in Gemini’s Deep Think mode Thang Luong and Edward Lockhart , is a simple and effective approach but can be computationally expensive due to the need to sample many reasoning traces per query. A natural remedy is to allocate different sampling budgets across questions (Figure 1). Most existing methods rely on heuristic signals, such as trace-level confidence Fu et al. [2025a] or LLM-predicted difficulty Wang et al. [2025a], which typically lack theoretical guarantees and may use the budget inefficiently. Another line of work analyzes test-time scaling with external reward models or verifiers Snell et al. [2024]; Huang et al. [2025a]; Zuo and Zhu [2025]. However, reward models can be mis-specified in practice, especially on complex or out-of-distribution queries, leading to unreliable guidance. They also introduce additional training and deployment costs. These limitations motivate the need for theoretically principled test-time scaling methods that do not rely on auxiliary supervision, but instead leverage the intrinsic structure of self-consistency itself. Under this lens, we propose PETS, a Principled and Efficient Test-Time Self-Consistency framework for trajectory allocation. Our approach is inspired by the principle that sampling effort should be distributed according to the relative difficulty of different questions, rather than allocated uniformly. Central to PETS is the optimization of self-consistency rate, defined as the probability that majority voting with a finite budget B matches the population majority. Because questions at different difficulty levels θ exhibit distinct convergence behaviors, they require different numbers of traces to attain high self-consistency. Our goal is therefore to allocate traces across questions so as to maximize the aggregate self-consistency rate of the question set under a fixed budget. We study two settings: ❶ Offline batch setting, where the entire question set is available for optimization. In this regime, we connect trajectory allocation to crowdsourcing by modeling reasoning traces as workers. We adopt and extend a Bayesian adaptive trajectory allocation algorithm (Section 3) that iteratively allocates additional trajectories while maintaining a posterior over each question’s difficulty level. ❷ Online streaming setting, where questions arrive sequentially and allocation must be made without access to the full dataset. Inspired by the offline case. We propose a one-shot allocation strategy (Section 4), which can be cast into a supervised learning case as in the batch setting with the help of additional samples as the training set to estimate the distribution of question difficulties. We solve a constrained allocation problem to obtain a budget allocation plan over difficulty levels, and use a provably optimal procedure to instantiate per-question budgets upon arrival. Experiments show that PETS significantly improves the efficiency of self-consistency while maintaining accuracy, demonstrating its strong practicability. As shown in Figure 1, compared to naive uniform allocation, it requires substantially fewer trajectories to reach full self-consistency, achieves higher self-consistency under the same budget, and ultimately translates these gains into improved accuracy. Our contribution. To summarize, we develop theoretically principled test-time scaling methods that leverage the intrinsic structure of self-consistency. Specifically, – We introduce self-consistency rate, a new performance measure defined as agreement with the infinite-budget majority vote. This formulation provides a principled target for finite-budget inference and enables rigorous theoretical analysis of sample-efficient allocation policies in finite-budget regimes. – In the offline setting, we make the first connection between self-consistency trajectory allocation and optimal budget allocation in crowdsourcing. This allows us to employ a rich body of existing tools to maximize the expected gain in self-consistency rate per allocation decision. – In the online setting, we propose a novel one-shot allocation strategy that estimates the difficulty distribution from a small training set and solves a constrained optimization problem to determine per-question budgets for allocation upon arrival. – Extensive experiments show that PETS consistently reduces the traces needed to reach full self-consistency in both unweighted and weighted cases, improves self-consistency under fixed budgets, and yields higher accuracy than uniform baselines. 2 Setup We consider a collection of multiple-choice (or fill-in-the-blank) questions qii=1N\q_i\_i=1^N. For each question qiq_i, we assume access to a stochastic reasoning procedure. Each sampled reasoning trace produces a random answer YiY_i sampled from answer set Y. Without loss of generality, we use =1,…,MY=\1,…,M\ to denote the collection of possible answers. Reasoning traces are assumed to be i.i.d. conditioned on qiq_i. Majority voting and related concepts. Given a finite integer budget B∈N+B _+, for each question qiq_i, B reasoning traces Ti(1),Ti(2),⋯,Ti(B)T^(1)_i,T^(2)_i,·s,T^(B)_i are i.i.d. drawn and lead to B answers Yi(1),Yi(2),⋯,Yi(B)Y^(1)_i,Y^(2)_i,·s,Y^(B)_i. For each answer in y∈y , the corresponding vote count is Vi(y;B)=∑j=1BYi(j)=y.V_i(y;B)= _j=1^B 1\Y^(j)_i=y\. The final answer based on majority voting is denoted as YiMaj(B)=argmaxy∈Vi(y;B).Y^Maj_i(B)= _y V_i(y;B). Similarly, for each question qiq_i, we define weighted majority voting by considering the weighted vote count for weight vector i=(wi(1),wi(2),⋯,wi(B))⊤∈R+B w_i=(w^(1)_i,w^(2)_i,·s,w^(B)_i) _+^B of all j∈[B]j∈[B]. ViW(y;i,B)=∑j=1Bwi(j)Yi(j)=y.V^W_i(y; w_i,B)= _j=1^Bw^(j)_i 1\Y^(j)_i=y\. Correspondingly, we can define the final answer based on weighted majority voting as: YiWMaj(B)=argmaxy∈ViW(y;i,B).Y^WMaj_i(B)= _y V_i^W(y; w_i,B). In this paper, we mainly follow Fu et al. [2025a] so that for each question qiq_i, the corresponding weight wi(j)w^(j)_i depends only on Ti(j)T^(j)_i, so that the final weight vector takes the form i=(w(Ti(1)),w(Ti(2)),⋯,w(Ti(B)))⊤ w_i=(w(T^(1)_i),w(T^(2)_i),·s,w(T^(B)_i)) . We make a natural assumption111Traces are independently generated from the same question qiq_i without fixing a random seed. that the trace and answer pairs (Ti(j),Yi(j))j=1B\(T^(j)_i,Y^(j)_i)\_j=1^B are i.i.d. drawn from an unknown joint distribution iD_i. The marginal distribution of Yi(j)∈1,…,MY^(j)_i∈\1,…,M\ is given by a pmf i=(θi,1,θi,2,⋯,θi,M)⊤ θ_i=( _i,1, _i,2,·s, _i,M) , where θi,y=P(Yi=y) _i,y=P(Y_i=y) are unknown parameters. The pmf θ characterizes the uncertainty in LLM’s answer to the question qiq_i, and can thus represent the difficulty of each problem.222If the maximum coordinate argmaxy∈θy _y∈ Y _y is much larger than the remaining parts, then it shows that this problem is relatively easier. Figure 5 in Appendix C.3 shows how θ affects the self-consistency rate under different budget B. We further define yi∞=argmaxy∈θi,y^∞_i= *arg\,max_y _i,y and yiW,∞=argmaxy∈E(Ti,Yi)∼i[w(Ti)Yi=y],y^W,∞_i= *arg\,max_y E_(T_i,Y_i) _i[w(T_i) 1\Y_i=y\], which correspond to the population (weighted) majority label in the infinite sample limit for question qiq_i. yi∞y^∞_i and yiW,∞y^W,∞_i formalize the fundamental limit of test-time scaling. With an infinite sampling budget, aggregating infinitely many reasoning trajectories yields a well-defined consensus prediction given by the infinite-budget (weighted) majority vote. Given the above content, we can define the self-consistency rate of the answer obtained by majority voting for question qiq_i under budget B as SC(qi;B)=P(YiMaj(B)=yi∞|i)SC(q_i;B)=P(Y_i^Maj(B)=y_i^∞| θ_i) (1) and its weighted counterpart as SCW(qi;B)=P(YiWMaj(B)=yiW,∞|i).SC^W(q_i;B)=P(Y_i^WMaj(B)=y_i^W,∞|D_i). (2) Intuitively, self-consistency measures how likely a budget-B (weighted) vote recovers the population (weighted) majority label, providing a principled target for finite-budget inference. By defining self-consistency rate, we can rigorously study how test-time samples approximate infinite-budget behavior and design sample-efficient allocation strategies under realistic computational constraints. Moreover, the rate at which it improves with B provides a natural notion of question difficulty. Both quantities are monotonically increasing in B, and their growth is governed by i θ_i (or iD_i in the weighted case). Optimal trajectory budget allocation problem. Our general goal is to design budget allocation strategies that maximize self-consistency rate under a limited reasoning total budget in various settings. Loosely speaking, given a set of questions qii=1N\q_i\_i=1^N, our aim is to find a policy π to allocate budget for each question, i.e., number of reasoning traces for each question. maxπ _π ∑i=1NEi∼imeta(π)[SCW(qi;Bπ(qi))], _i=1^NE_D_i ^meta_i(π) [SC^W(q_i;B_π(q_i)) ], (3) s.t. ∑i=1NBπ(qi)Btotal. .t. _i=1^NB_π(q_i) B_total. Here, the joint distribution of (Ti,Yi)(T_i,Y_i) can be more complex than a fixed distribution iD_i as it might be dependent on the policy. For instance, in a Bayesian perspective, we can consider a meta distribution (distribution of distributions) and consider iD_i is drawn from imeta(π)D_i^meta(π). In Section 3, imeta(π)D^meta_i(π) can be a posterior distribution over parameters like i θ_i based on π. Details are specified in later sections. We study this problem under two different information settings that can both be unified under our above formulation. ❶ Offline batch setting: the full question set qii=1N\q_i\_i=1^N is known in advance, so the policy can allocate and adapt budgets globally across questions during execution. The outcome is summarized by a final per-question budget Bπ(qi)B_π(q_i) for each qiq_i. ❷ Online streaming setting: Questions q1,q2,…,qN\q_1,q_2,…,q_N\ arrive sequentially as i.i.d. draws from a latent distribution D and is not observable in advance. When qtq_t arrives, the policy must choose a budget Bt=Bπ(qt)B_t=B_π(q_t) immediately, without seeing future questions. 3 Offline PETS in the Batch Setting In this section, we study the problem of optimal trajectory allocation in the offline setting. Here, allocation proceeds sequentially, and the availability of all questions enables us to gradually assess their relative difficulties throughout the process. Building on our notion of the self-consistency rate, we establish an interesting connection to the fruitful and well-developed literature on crowdsourcing. Table 1 summarizes the correspondence. Specifically, under standard majority voting, the trajectory allocation problem is closely related to optimal budget allocation in crowdsourcing. Each reasoning answer Yi(b)Y_i^(b) can be viewed as a noisy worker label for question qiq_i, while allocating additional traces corresponds to assigning more labeling effort to an item under a global budget constraint. As a result, the offline trajectory allocation problem can be formulated as a learning-while-allocating problem, and we can directly adopt the Bayesian framework of Chen et al. [2013]. To sum up, the learner maintains a posterior over the answer distribution of each question, analogous to the posterior over item labels in crowdsourcing, and sequentially decides which question to sample next. Beyond standard majority voting, we extend the Bayesian allocation framework to confidence-weighted aggregation, a strategy that has recently gained popularity in test-time scaling and self-consistency methods, e.g., [Fu et al., 2025a]. We remark that the weighted majority voting formulation in [Fu et al., 2025a] differs from the worker-reliability weighting scheme considered in [Chen et al., 2013], and thus requires additional care when extending the crowdsourcing-based allocation framework. Table 1: Connection to crowdsourcing. Crowdsourcing Test-time self-consistency Item i, Worker label Yi(b)Y_i^(b) Question qiq_i, Trace answer Yi(b)Y_i^(b) Adaptive worker assignment to items Adaptive trajectory sampling for questions Posterior over labels and worker reliability Posterior over answers and confidence weights Worker-specific reliability Trace confidence without persistent worker ID Goal: infer the true label Goal: infer the population majority answer yi∞y_i^∞ (or yiW,∞y_i^W,∞) Bayesian Setup for Trajectory Allocation. We formalize offline allocation as a Bayesian decision problem. For each question qiq_i, each sampled trace yields an answer Yi∈Y_i and a confidence score Ci=w(Ti)∈R+C_i=w(T_i) _+. Let i∈M−1 θ_i∈^M-1 denote the (unknown) answer distribution, and let i=(μi,1,…,μi,M)∈RM μ_i=( _i,1,…, _i,M) ^M be the (unknown) class-conditional confidence means (we fix σ2=1σ^2=1 for simplicity). We make a natural assumption that answers follow a categorical distribution, and confidence is Gaussian with mean depending on the sampled answer. The joint likelihood for a single trace-induced pair (Yi,Ci)(Y_i,C_i) factorizes as p(y,c∣i,i)=p(y∣i)p(c∣y,i),p(y,c θ_i, μ_i)=p(y θ_i)\,p(c y, μ_i), Therefore, the weighted population-optimal label is yiW,∞=argmaxm∈θi,mμi,m.y_i^W,∞= _m _i,m _i,m. The weighted self-consistency rate (2) can equivalently writes in the following form SCW(qi;B)=P(YiWMaj(B)=yiW,∞|i,i),SC^W(q_i;B)=P\! (Y_i^WMaj(B)=y_i^W,∞\ |\ θ_i, μ_i ), (4) Since latent parameters (i,i)( θ_i, μ_i) are unknown and ground-truth labels are unavailable, a direct quantification of the objective (3) is unclear. We thus adopt a Bayesian framework that maintains a posterior over the latent parameters, for us to quantify self-consistency under posterior belief. Modeling as an MDP process. We model offline trajectory allocation as a finite-horizon Bayesian Markov Decision Process (MDP), following the crowdsourcing formulation of Chen et al. [2013], with adaptations to accommodate confidence-weighted traces. At stage t, the state StS^t summarizes the posterior beliefs over (i,i)( θ_i, μ_i) for each question via their respective posterior hyperparameters in the belief state. The action it∈[N]i_t∈[N] selects a question to which one additional trace is allocated. After allocating a trace to question iti_t, we observe (yt,ct)(y_t,c_t), which induces a conjugate Bayesian update of the posterior parameters in StS^t. The process has a fixed horizon H, corresponding to the total trace budget BtotalB_total. The terminal reward is defined as the sum of posterior self-consistency across all questions in the batch. y^ii=1N=argmaxy^i∑i=1NP(y^i=yiW,∞|SH)\ y_i\_i=1^N= _\ y_i\ _i=1^NP( y_i=y_i^W,∞|S^H) (5) which measures the posterior probability of recovering the (weighted) population-majority answer for each question. Please refer to Appendix B.1 for further details on MDP formulation in our paper. Lemma 3.1 (Bayes-optimal terminal decision). Given the terminal belief SHS^H, the Bayes-optimal decision for each question is therefore y^i∈argmaxm∈[M]P(yiW,∞=m∣SiH), y_i∈ _m∈[M]P\! (y_i^W,∞=m S_i^H ), (6) The posterior probability P(yiW,∞=m∣SiH)P(y_i^W,∞=m S_i^H) quantifies the posterior belief that class m is the population majority label, which can be estimated via Monte Carlo sampling. Under the terminal decision rule (6), we seek an allocation policy that maximizes the expected terminal utility: V(S0)=Eπ[∑i=1Nmaxm∈[M]Pr(yiW,∞=m∣SiH)],V(S^0)=E_π [ _i=1^N _m∈[M] \! (y_i^W,∞=m S_i^H ) ], (7) where the expectation is taken over all sample paths induced by policy π=(i0,…,iH−1)π=(i_0,…,i_H-1), which sequentially selects a question to allocate one additional budget at each time step. Approximation of dynamic programming. Exact dynamic programming of Equation (7) is intractable due to the exponentially growing belief space. Our PETS-Offline therefore similarly adopt the Optimistic Knowledge Gradient (OKG) heuristic [Chen et al., 2013], which selects the question with the largest optimistic one-step improvement in the terminal utility of Equation (7). We provide the details and full algorithm (Algorithm 2) in Appendix B.2. 4 Online PETS in the Streaming Setting The key idea of online allocation is to assign different numbers of samples to questions with different answer distribution parameters θ (i.e., difficulty vectors) in one shot upon seeing the question. Unlike the offline setting in Section 3, where θ and voting weights can be estimated during the allocation process, the main challenge in the online regime is the lack of information about how the current question’s difficulty compares to that of future questions, given the online nature. In this setting, we need to have access to a prior distribution over question difficulties via additional training data that are assumed to be drawn from the same distribution. Consequently, when a new question arrives, its budget could be determined immediately based solely on its estimated difficulty label and the prior distribution. To simplify the problem, we restrict our attention to the setting where we know that there will be N questions in the upcoming estimation period, although we do not know their exact content or arrival times. This assumption is common in practice, since model deployers can often estimate the query volume over a given time window, for example, based on historical usage statistics, service-level forecasts, or system capacity planning. Mathematical formulation. There are N questions q1,q2,…,qN\q_1,q_2,…,q_N\ arriving sequentially. Each question qtq_t is associated with a difficulty vector t=(qt) θ_t= θ(q_t) as defined in Section 2. With total budget BtotalB_total, upon observing t θ_t for question t, an allocation policy π assigns a budget Bt=Bπ(qt)=Bπ(t)B_t=B_π(q_t)=B_π( θ_t) without access to future questions or any intermediate feedback from other questions. Therefore, in the online setting, π can only depend on the realized prior distribution D and the current difficulty label t θ_t. 4.1 Execution Protocol We here describe the execution protocol of PETS-Online. At a high level, the procedure consists of estimating ❶ the distribution of problem parameters, ❷ the mapping from each incoming question to its corresponding parameter grid, and ❸ solving a budget allocation optimization problem based on these estimates to obtain the final allocation plan. This gives a two-stage architecture: a training-time stage that builds a small library of difficulty grids and their representative self-consistency curves, and a test-time stage that maps each streaming question to one grid and allocates its budget in one shot. Estimation of parameters and sample distribution. We estimate question difficulty in two steps. First, because the original (M−1)(M\!-\!1)-dimensional difficulty parameter i θ_i can be high-dimensional in the multi-choice case, we use a Gaussian-probit curve for the two-dimensional surrogate (ai,bi)(a_i,b_i): gai,bi(B):=(aiB+bi),g_a_i,b_i(B):= (a_i B+b_i), where is the standard normal CDF. This surrogate approximates the self-consistency curve SC(i;B)SC( θ_i;B) over different budgets B. The Gaussian approximation is motivated by applying a normal approximation to multinomial vote margins; in practice, (ai,bi)(a_i,b_i) is fitted by regression from a large pool of sampled answers for the training question. We then discretize the reduced space into K difficulty grids with prototype parameters ^jj=1K\ θ^j\_j=1^K; in the multi-choice implementation, ^j θ^j is represented by a prototype probit curve (a^j,b^j)( a_j, b_j). Second, we use a lightweight warm-up procedure to assign each incoming question to a grid, after which the corresponding budget is allocated in one shot. For a question q, we first draw 44 warm-up responses and let Cq(4)=(c1,c2,c3,c4)C_q^(4)=(c_1,c_2,c_3,c_4) be the sorted option-count vector in descending order, padded with zeros if fewer than four distinct options appear. These patterns induce a deterministic grid assignment Tq=g(Cq(4))∈1,…,K,T_q=g(C_q^(4))∈\1,…,K\, This construction is independent of the total number of answer options, since at most four distinct options can appear in four warm-up samples. See Appendix C.3 and Appendix C.4 for more details. Optimization framework. After discretization, the self-consistency rate in (3) for a question qiq_i under budget B can be approximated as333A weighted version can be defined analogously. Since weights are difficult to estimate in the online setting, in experiments, we use the unweighted version for policy optimization and apply weighted majority voting only at inference time. SC(buc(qi);B)=P(YiMaj(B)=yi∞∣buc(qi)).SC( θ^buc(q_i);B)=P\! (Y_i^Maj(B)=y_i^∞ θ^buc(q_i) ). (8) An online streaming policy π is therefore specified by integer grid budgets B1,…,BKB_1,…,B_K: any question assigned to grid j receives budget BjB_j. Over a horizon of N streaming questions with total budget BtotalB_total, the optimal allocation problem can be rewritten as maxBjj=1K∑j=1Kp^jSC(^j;Bj)s.t.∑j=1Kp^jBjB¯total, _\B_j\_j=1^K _j=1^K p_j\,SC( θ^j;B_j) .t. _j=1^K p_jB_j B_total, (9) where B¯total:=Btotal/N B_total:=B_total/N is the average budget per round, p^j p_j is the estimated distribution, and ^j θ^j is the representation parameter of the grid j. Finally, we note that although (9) is a static optimization problem, our final policy is a dynamic streaming policy which calls (9) at every round; we refer to Appendix C.1 for more details. 4.2 Optimal Budget Allocation In this section, we present an efficient greedy algorithm that solves the integer program (9). We start with the binary-choice case (M=2M=2) in Algorithm˜1, and extend it to the multi-choice case in Appendix C.3. For a binary-choice question qiq_i, the choice set contains only two choices =0,1 Y=\0,1\, and the difficulty vector reduces to a scalar parameter θ=P[Yi=1]∈[0,1]θ=P[Y_i=1]∈[0,1]. Under B i.i.d. samples and majority voting (with random tie-breaking when B is even), we obtain P[YiMaj(B)=1∣θ]=∑b=(B+1)/2B(Bb)θb(1−θ)B−b,B odd∑b=B/2+1B(Bb)θb(1−θ)B−b+12(B/2)θB/2(1−θ)B/2,B evenP[Y_i^Maj(B)=1 θ]= cases _b=(B+1)/2^B Bbθ^b(1-θ)^B-b,&$B$ odd\\[11.00008pt] _b=B/2+1^B Bbθ^b(1-θ)^B-b+ 12 BB/2θ^B/2(1-θ)^B/2,&$B$ even cases (10) and P[YiMaj(B)=0∣θ]=1−P[YiMaj(B)=1∣θ]P[Y_i^Maj(B)=0 θ]=1-P[Y_i^Maj(B)=1 θ]. Thus, the self-consistency rate is SC(θ;B)=maxP[YiMaj(B)=1∣θ],P[YiMaj(B)=0∣θ],SC(θ;B)= \P[Y_i^Maj(B)=1 θ],P[Y_i^Maj(B)=0 θ] \, (11) where SC(θ;0)=12SC(θ;0)= 12. We define the marginal gain R(θ,n)R(θ,n) at budget level n for a question with difficulty parameter θ as the increase in self-consistency rate resulting from allocating one additional unit of budget: R(θ,n):=SC(θ;n+1)−SC(θ;n).R(θ,n):=SC(θ;n+1)-SC(θ;n). We propose a greedy yet optimal algorithm (Algorithm 1) that repeatedly allocates budget to the grid with the largest current marginal improvement. Algorithm 1 Greedy Budget Allocation Algorithm 1: Grid (θj)j=1K(θ^j)_j=1^K, probabilities (pj)j=1K(p_j)_j=1^K, and average per-round budget B¯total B_total 2:Initialize current budget Bj←0B_j← 0 for all j∈[K]j∈[K]. 3:Initialize current marginal gain δj←R(θj,0) _j← R(θ^j,0) for all j∈[K]j∈[K]. 4:Initialize total used budget T←0T← 0. 5:while TB¯totalT B_total do 6: j⋆←argmaxjδj ← _j _j 7: if Bj⋆=0B_j =0 then 8: Bj⋆←1B_j ← 1, T←T+pj⋆T← T+p_j 9: else 10: Bj⋆←Bj⋆+2,T←T+2pj⋆B_j ← B_j +2,T← T+2p_j 11: end if 12: Update δj⋆←R(θj⋆,Bj⋆) _j ← R( _j ,B_j ) 13:end while Theorem 4.1. Algorithm 1 outputs an optimal solution to the discretized online allocation problem (9) in expectation, with a randomized rounding rule.444This is because the remaining budget may not suffice for another iteration. See Appendix C.1 for details. Figure 2: Budget allocation plan of the offline and online settings on 9 simulated binary choice questions, =1,2Y=\1,2\. Each question is associated with a θ=max(θ1,θ2)θ= ( _1, _2), and larger theta indicates easier questions. 4.2.1 Connection with the Offline Case Although the offline and online cases rely on different allocation procedures, their budget proportions become nearly identical as the budget grows. As shown in Figure 2, increasing the average per-question budget leads the two allocations to converge to similar proportions. Further discussion and theoretical support are provided in Appendix D. Table 2: PETS-Offline Results. We compare PETS against confidence-guided and uniform sample budget allocation. “(conf)” denotes the trace confidence-weighted variant. # traces reports the number of sampled traces required to reach full consistency (consistency =1=1); Con. and Acc. report each method’s achieved consistency and accuracy evaluated at the trace count where PETS-Off. attains consistency 1. Qwen3-4B Qwen3-30B Qwen-Long GPT-20B GPT-120B Dataset Method # traces ↓ Con. ↑ Acc. ↑ # traces Con. Acc. # traces Con. Acc. # traces Con. Acc. # traces Con. Acc. PETS-Off. 2780 1.00 69.7 2607 1.00 71.8 2513 1.00 76.3 3180 1.00 75.7 2580 1.00 82.5 PETS-Off. (conf) 3667 0.99 70.3 3687 0.99 72.1 2887 0.99 77.0 3693 0.99 76.2 3540 0.99 82.1 Conf. guided 10652 0.96 68.5 9702 0.96 71.2 8158 0.96 76.1 10058 0.96 75.4 8474 0.97 81.6 Uniform 11013 0.96 68.9 10367 0.96 71.5 9973 0.96 76.5 10853 0.96 75.1 10393 0.97 81.5 GPQA Uniform (conf) 11453 0.95 69.9 11607 0.95 72.2 11400 0.95 76.4 11193 0.96 75.6 10500 0.96 80.8 PETS-Off. 212 1.00 83.3 190 1.00 88.6 152 1.00 90.0 181 1.00 90.0 212 1.00 93.9 PETS-Off. (conf) 257 0.98 84.0 223 0.97 86.7 203 0.97 90.4 251 0.97 89.7 211 0.98 93.3 Conf. guided 402 0.95 81.3 312 0.95 87.5 234 1.00 90.0 408 0.97 89.2 732 0.95 91.3 Uniform 470 0.94 82.1 545 0.96 86.1 288 0.97 89.3 410 0.95 90.2 681 0.95 91.3 AIME25 Uniform (conf) 610 0.91 83.3 763 0.93 85.6 752 0.94 88.9 618 0.94 89.0 911 0.94 91.9 PETS-Off. 259 1.00 63.1 135 1.00 70.0 83 1.00 70.0 200 1.00 73.3 184 1.00 74.4 PETS-Off. (conf) 369 0.96 66.0 120 1.00 69.9 91 0.99 69.9 232 0.97 72.6 218 0.99 73.7 Conf. guided 648 0.95 62.9 138 0.99 70.0 84 1.00 70.0 546 0.98 72.5 378 0.96 73.3 Uniform 861 0.94 63.0 202 0.98 69.6 96 0.99 69.9 665 0.96 71.9 448 0.97 73.7 AIME24 Uniform (conf) 942 0.92 63.4 179 0.97 68.6 115 0.98 69.7 1206 0.94 70.8 535 0.95 71.9 PETS-Off. 464 1.00 51.6 381 1.00 64.7 363 1.00 71.7 329 1.00 83.3 329 1.00 83.3 PETS-Off. (conf) 579 0.96 52.0 361 0.97 65.2 371 0.97 73.2 324 0.99 83.1 324 0.99 83.1 Conf. guided 1206 0.92 48.3 894 0.95 58.1 984 0.91 64.6 732 0.94 80.5 882 0.93 81.1 Uniform 1133 0.90 50.0 1219 0.91 64.7 1227 0.91 68.8 916 0.94 83.6 916 0.94 83.6 HMMT Uniform (conf) 1383 0.87 50.6 1089 0.91 65.1 1165 0.90 71.7 902 0.93 82.6 902 0.93 82.6 PETS-Off. 280 1.00 75.4 148 1.00 86.7 149 1.00 86.7 253 1.00 92.1 253 1.00 92.1 PETS-Off. (conf) 292 0.98 77.3 162 0.98 86.1 150 0.98 87.8 217 0.98 92.4 217 0.98 92.4 Conf. guided 654 0.94 71.3 252 0.95 80.8 348 0.98 85.0 336 0.96 93.8 552 0.95 90.5 Uniform 826 0.94 73.2 237 0.96 83.7 320 0.97 87.3 776 0.94 90.1 776 0.94 90.1 BRUMO Uniform (conf) 589 0.94 75.7 310 0.95 83.6 421 0.97 87.2 574 0.95 90.7 574 0.95 90.7 Figure 3: Budget allocation curve in the offline setting. “(conf)” denotes the trace confidence-weighted variant. Consistency is computed within each matched-variant comparison group: PETS-Offline vs. Uniform, and PETS-Offline (conf) vs. Uniform (conf). Table 3: PETS-Online Results. We compare PETS against confidence-guided and uniform sample budget allocation. “(conf)” denotes the trace confidence-weighted variant. # traces reports the number of sampled traces required to reach full consistency (consistency =1=1); Con. and Acc. report each method’s achieved consistency and accuracy evaluated at the trace count where PETS-On. attains consistency 1. Qwen3-4B Qwen3-30B Qwen-Long GPT-20B GPT-120B Dataset Method # traces ↓ Con. ↑ Acc. ↑ # traces Con. Acc. # traces Con. Acc. # traces Con. Acc. # traces Con. Acc. PETS-On. 4662 1.00 68.8 3826 1.00 71.6 4852 1.00 76.3 6826 1.00 75.9 4172 1.00 82.4 PETS-On. (conf) 4888 1.00 69.6 4357 0.99 71.8 4146 1.00 76.9 7269 0.99 76.1 5094 0.99 81.6 Conf. guided 7623 0.97 68.2 7361 0.98 70.5 7782 0.98 75.4 9355 0.98 74.3 7162 0.97 80.5 Uniform 9520 0.97 68.1 8456 0.97 71.2 9195 0.97 76.0 9699 0.98 76.1 8109 0.98 81.8 GPQA Uniform (conf) 9856 0.97 69.4 9257 0.96 72.0 9526 0.97 76.4 9895 0.98 76.3 9593 0.97 81.4 PETS-On. 194 1.00 75.0 504 1.00 83.5 218 1.00 85.0 195 1.00 85.0 454 1.00 91.7 PETS-On. (conf) 287 0.95 76.3 535 0.97 82.5 681 0.96 85.7 330 0.96 84.8 493 0.98 92.3 Conf. guided 232 0.96 75.0 272 0.96 82.5 146 0.97 86.0 385 0.94 84.5 232 0.96 89.5 Uniform 290 0.95 74.8 415 0.95 81.0 229 0.95 84.7 221 0.96 86.0 416 0.95 89.2 AIME25 Uniform (conf) 452 0.92 76.3 486 0.94 81.2 495 0.93 83.5 349 0.93 85.2 459 0.94 89.8 PETS-On. 170 1.00 56.2 81 1.00 65.0 83 1.00 65.0 130 1.00 70.0 107 1.00 69.8 PETS-On. (conf) 185 0.96 60.0 81 1.00 64.8 86 0.99 64.8 104 0.99 68.8 92 1.00 69.5 Conf. guided 292 0.96 57.0 80 0.99 64.5 80 1.00 65.0 106 0.98 68.0 170 0.98 68.5 Uniform 393 0.94 56.8 83 1.00 64.7 82 1.00 65.0 237 0.98 67.7 205 0.97 67.0 AIME24 Uniform (conf) 405 0.94 58.8 83 1.00 64.7 101 0.99 64.8 171 0.98 68.0 144 0.98 67.7 PETS-On. 531 1.00 48.5 825 1.00 56.2 872 1.00 67.0 248 1.00 85.0 221 1.00 85.0 PETS-On. (conf) 615 0.93 46.8 761 0.95 56.8 1061 0.95 68.8 233 0.97 85.5 263 0.96 86.5 Conf. guided 727 0.91 43.0 623 0.94 52.5 666 0.99 64.5 436 0.91 81.5 382 0.93 80.0 Uniform 792 0.89 46.2 813 0.93 56.2 803 0.96 66.7 475 0.92 83.3 309 0.95 84.8 HMMT Uniform (conf) 931 0.89 45.7 786 0.92 56.7 959 0.95 67.8 409 0.92 83.2 458 0.91 85.0 PETS-On. 601 1.00 63.2 125 1.00 80.0 130 1.00 80.2 213 1.00 95.0 383 1.00 88.8 PETS-On. (conf) 494 0.97 64.7 121 0.99 79.5 138 0.99 81.5 162 0.99 94.7 241 0.99 89.7 Conf. guided 398 0.93 58.0 202 0.96 73.5 142 0.95 76.5 368 0.89 88.0 424 0.92 85.5 Uniform 613 0.94 61.5 172 0.96 77.7 167 0.97 80.7 245 0.95 91.7 521 0.92 86.3 BRUMO Uniform (conf) 519 0.93 65.5 159 0.96 77.7 189 0.98 81.3 184 0.95 91.7 353 0.94 87.2 Figure 4: Budget allocation curve in the online setting. “(conf)” denotes the trace confidence-weighted variant. Consistency is computed within each matched-variant comparison group: PETS-Online vs. Uniform, and PETS-Online (conf) vs. Uniform (conf). Oracle variant assumes access to the latent parameter θ, while in the online setting, θ is learnt from a training dataset. 5 Experiment In this section, we conduct evaluation of PETS on widely used knowledge and reasoning benchmarks, including GPQA-Diamond Rein et al. [2024], AIME 24 19, AIME 25 25, Brumo 25 26, and HMMT Feb 25 27. We consider popular reasoning LLMs: Qwen3-4B-Thinking and Qwen3-30B-A3B-Thinking Yang et al. [2025], gpt-oss-20b and gpt-oss-120b Agarwal et al. [2025], and QwenLong-L1.5-30B-A3B Shen et al. [2025]. Following our offline budget allocation (Section 3) and online budget allocation (Section 4), we evaluate PETS under the offline and online scenarios. For each dataset, we sample 128128 responses per question from each model. To define a maximum allocation budget of 6464 traces per question as the finite proxy for the infinite sampling limit, we uniformly subsample 6464 responses from the 128128. We repeat this subsampling process 3030 times and report the mean performance. We also include confidence weighted version in our experiment, where we follow Fu et al. [2025b] to compute tail trace confidence Ci=w(Ti)C_i=w(T_i) as the weight for weighted majority voting at aggregation time (In PETS-offline we also involve it at sampling time as shown in Section 3). We evaluate self-consistency rate as defined in Equation 1 and Equation 2. Our primary metric is the number of traces required to reach full self-consistency (=1)(=1), where the majority answer matches the population majority answer yi∞y_i^∞ (or yiW,∞y_i^W,∞ in the weighted version), approximated using 64 traces. We also report accuracy on the dataset. More details and full results are provided in Appendix E. In both offline and online settings, we compare against two baselines: uniform budget allocation across questions (Uniform) and the confidence-guided allocation (Conf. guided) method of DeepConf Fu et al. [2025a]. 5.1 PETS for Offline Budget Allocation We first evaluate PETS-Offline, where all questions are available to the budget-allocation optimizer. Following Section 2, we consider both unweighted and confidence-weighted settings, and only compare methods within the same setting. We report self-consistency and accuracy at the trace count where PETS-Offline first reaches full self-consistency (=1)(=1). Results are shown in Table 2 and Figure 3. Across models and datasets, ❶ PETS-Offline consistently reduces the number of traces required to reach full self-consistency by up to 75%75\% compared to uniform allocation, while achieving higher self-consistency at any budget (Figure 3). ❷ When the population majority aligns with the true answer, improved self-consistency directly translates into higher accuracy. ❸ Confidence-weighted majority voting further shifts the population majority towards the ground truth, thus resulting in improved accuracy. 5.2 PETS for Online Budget Allocation We next evaluate PETS in the online case, where questions arrive sequentially, and allocation decisions are irreversible. Besides Uniform, we also compare PETS-Online with PETS-Oracle, which can access the latent difficulty θ and thus serves as an estimation-free upper bound. As in the offline setting, we also consider both unweighted and confidence-weighted versions. PETS-Online allocates budget on the fly using only observed traces. Table 3 and Figure 4 show the results. Consistent with offline results, ❶ PETS-Online substantially reduces the traces required to reach full self-consistency, ❷ leading to improved accuracy. ❸ Confidence-weighted self-consistency further boosts accuracy by reshaping the population majority. ❹ PETS-Online closely matches PETS-Oracle in both self-consistency and accuracy, indicating that the estimation procedure in Appendix C.4 is effective. We further report Pass@1 and MV@128 accuracy as lower and upper reference bounds, respectively, for all methods. The results are shown in Figures 16 and 17. 5.3 Additional Results In this section, we provide two ablations for the online difficulty discretization. Tables 4 and 5 show that both the oracle allocation, which clusters ground-truth (a,b)(a,b) parameters, and the practical predictor, which uses only K0=4K_0=4 warm-up samples, are not highly sensitive to the number of difficulty bins. Accuracy varies only modestly across choices of k, and in several AIME 2024 settings remains unchanged, suggesting that coarse difficulty grouping is sufficient for the online allocation policy. We also report wall-clock allocation overhead in Table 6. The online predictor adds only a few seconds of preprocessing and budget assignment on the evaluated datasets, while the offline OKG allocator is substantially more expensive due to sequential Monte Carlo allocation. This supports the intended use of PETS-Online as a practical streaming policy: it preserves the adaptive allocation behavior of PETS while keeping the decision-time overhead small. Table 4: Effect of Oracle KMeans cluster number k on Oracle accuracy. The Oracle uses KMeans clustering on ground-truth (a,b)(a,b) parameters to partition questions into k difficulty bins. Predictor and Baseline results are unaffected by this parameter. Dataset Model k=2k=2 k=3k=3 k=5k=5 k=8k=8 GPQA Qwen3-4B 0.6905 0.6905 0.6964 0.6905 GPT-120B 0.8036 0.8036 0.8214 0.8274 AIME 2024 Qwen3-4B 0.9500 0.9000 0.9000 0.9000 GPT-120B 1.0000 1.0000 1.0000 1.0000 Table 5: Effect of Predictor difficulty bin number k on Predictor accuracy. The Predictor assigns each question to one of k bins based on the number of distinct answers among K0=4K_0=4 warm-up. Dataset Model k=2k=2 k=3k=3 k=4k=4 k=5k=5 GPQA Qwen3-4B 0.6845 0.6845 0.6845 0.6786 GPT-120B 0.8214 0.8095 0.8095 0.8095 AIME 2024 Qwen3-4B 0.9500 0.9000 0.9000 0.9000 GPT-120B 1.0000 1.0000 1.0000 1.0000 Table 6: Wall-clock runtime (seconds) of different budget allocation methods. Online Predictor trains bucket statistics on 30 questions and then assigns each test question a budget via K0=4K_0=4 warm-up samples. Online Uniform applies a fixed per-question budget with no training. Offline OKG performs sequential Monte Carlo allocation (B=16B=16 per question, nsamples=500n_samples=500). Dataset Model Online Predictor Online Uniform Offline OKG GPQA Qwen3-4B 4.734.73 <0.01<0.01 212.2212.2 GPT-120B 4.684.68 <0.01<0.01 204.1204.1 AIME 2024 Qwen3-4B 1.551.55 0.080.08 36.036.0 GPT-120B 1.191.19 0.030.03 39.039.0 6 Related Work Test-time scaling and efficient reasoning. Test-time scaling improves reasoning either by extending chain-of-thought trajectories or by sampling multiple trajectories in parallel [Snell et al., 2024; Welleck et al., 2024; Wei et al., 2022]. Self-consistency and Best-of-N aggregate such samples by voting or selection [Wang et al., 2022; Brown et al., 2024]. Because naive scaling is costly, efficient-reasoning methods shorten traces, impose token budgets, prune trajectories, or filter samples using confidence and difficulty estimates rather than directly optimizing allocation [Muennighoff et al., 2025; Chen et al., 2024a; Fu et al., 2025a; Wang et al., 2025a]. Crowdsourcing and adaptive allocation. Our formulation is also connected to crowdsourcing and budgeted labeling: Dawid–Skene models noisy workers and item difficulty [Dawid and Skene, 1979], while adaptive assignment and optimistic knowledge gradient methods allocate labels by expected value of information [Sheng et al., 2008; Chen et al., 2013]. Related work also studies aggregation, adaptive stopping, and compute allocation across queries, tokens, or rollouts [Komiyama et al., 2025; Chen et al., 2024b; Zuo and Zhu, 2025; Lin et al., 2025; Wang et al., 2025b]. Unlike reward- or judge-based selection, which can suffer from reward hacking or miscalibration [Huang et al., 2025a; Gao et al., 2024], PETS optimizes self-consistency against an infinite-compute voting oracle. 7 Conclusion We present PETS, a principled framework that improves the efficiency of parallel sampling with self-consistency without sacrificing performance. Across challenging benchmarks and state-of-the-art reasoning models, PETS consistently increases self-consistency and accuracy while substantially reducing the number of required reasoning trajectories. Our experiments reveal that while majority voting can approximate the population majority and improve accuracy when the population majority matches the true answer, but when the majority is systematically wrong, additional sampling provides little benefit, revealing a limitation of allocation-only approaches. Finally, while PETS-Online estimates the latent question difficulty θ via a short warm-up phase, an important next step is to train models to predict θ directly from the question prior to generation. Acknowledgement Z. Deng, Y. Han, and T. Chen are grateful for the kind support of Renaissance Philanthropy AI4Math fund. Impact Statement This paper presents work whose goal is to advance the field of LLM reasoning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here. References S. Agarwal, L. Ahmad, J. Ai, S. Altman, A. Applebaum, E. Arbus, R. K. Arora, Y. Bai, B. Baker, H. Bao, et al. (2025) Gpt-oss-120b & gpt-oss-20b model card. arXiv preprint arXiv:2508.10925. Cited by: Appendix A, §5. B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V. Le, C. Ré, and A. Mirhoseini (2024) Large language monkeys: scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787. Cited by: Appendix A, §6. X. Chen, Q. Lin, and D. Zhou (2013) Optimistic knowledge gradient policy for optimal budget allocation in crowdsourcing. In Proceedings of the 30th International Conference on Machine Learning, S. Dasgupta and D. McAllester (Eds.), Proceedings of Machine Learning Research, Vol. 28, Atlanta, Georgia, USA, p. 64–72. External Links: Link Cited by: Appendix A, §B.2, §B.2, §D.3, §3, §3, §3, §3, §6. X. Chen, J. Xu, T. Liang, Z. He, J. Pang, D. Yu, L. Song, Q. Liu, M. Zhou, Z. Zhang, et al. (2024a) Do not think that much for 2+ 3=? on the overthinking of o1-like llms. arXiv preprint arXiv:2412.21187. Cited by: Appendix A, §6. Y. Chen, X. Pan, Y. Li, B. Ding, and J. Zhou (2024b) Simple and provable scaling laws for the test-time compute of large language models. arXiv preprint arXiv:2411.19477. Cited by: Appendix A, §6. A. P. Dawid and A. M. Skene (1979) Maximum likelihood estimation of observer error-rates using the em algorithm. Applied Statistics 28 (1), p. 20–28. External Links: Link Cited by: Appendix A, §6. Z. Deng, T. P. Zollo, B. Eyre, A. Inamdar, D. Madras, and R. Zemel (2025) QuEst: enhancing estimates of quantile-based distributional measures using model predictions. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 13347–13368. External Links: Link Cited by: Appendix A. Z. Deng, T. P. Zollo, J. C. Snell, T. Pitassi, and R. S. Zemel (2023) Distribution-free statistical dispersion control for societal applications. In Advances in Neural Information Processing Systems, Vol. 36. External Links: Link Cited by: Appendix A. J. D. Esary, F. Proschan, and D. W. Walkup (1967) Association of random variables, with applications. The Annals of Mathematical Statistics 38 (5), p. 1466–1474. Cited by: §C.3. Y. Fu, J. Chen, S. Zhu, Z. Fu, Z. Dai, Y. Zhuang, Y. Ma, A. Qiao, T. Rosing, I. Stoica, et al. (2024) Efficiently scaling llm reasoning with certaindex. arXiv preprint arXiv:2412.20993. Cited by: Appendix A. Y. Fu, X. Wang, Y. Tian, and J. Zhao (2025a) Deep think with confidence. arXiv preprint arXiv:2508.15260. Cited by: Appendix A, §1, §2, §3, §5, §6. Y. Fu, X. Wang, Y. Tian, and J. Zhao (2025b) Deep think with confidence. External Links: 2508.15260, Link Cited by: §E.1, §5. Y. Gao, G. Xu, Z. Wang, and A. Cohan (2024) Bayesian calibration of win rate estimation with LLM evaluators. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing (EMNLP), p. 4757–4769. Cited by: Appendix A, §6. [14] Gemini 3 Pro. (en). External Links: Link Cited by: Appendix A. D. Guo, D. Yang, H. Zhang, J. Song, P. Wang, Q. Zhu, R. Xu, R. Zhang, S. Ma, X. Bi, et al. (2025) DeepSeek-r1 incentivizes reasoning in llms through reinforcement learning. Nature 645 (8081), p. 633–638. Cited by: Appendix A, §1. B. Hou, Y. Zhang, J. Ji, Y. Liu, K. Qian, J. Andreas, and S. Chang (2025) Thinkprune: pruning long chain-of-thought of llms via reinforcement learning. arXiv preprint arXiv:2504.01296. Cited by: Appendix A. A. Huang, A. Block, Q. Liu, N. Jiang, A. Krishnamurthy, and D. J. Foster (2025a) Is best-of-N the best of them? coverage, scaling, and optimality in inference-time alignment. In Proceedings of the 42nd International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, Vol. 267, p. 25075–25126. Cited by: Appendix A, §1, §6. C. Huang, L. Huang, J. Leng, J. Liu, and J. Huang (2025b) Efficient test-time scaling via self-calibration. arXiv preprint arXiv:2503.00031. Cited by: §1. [19] (2025-07) HuggingFaceH4/aime_2024 · Datasets at Hugging Face. External Links: Link Cited by: §5. A. Jaech, A. Kalai, A. Lerer, A. Richardson, A. El-Kishky, A. Low, A. Helyar, A. Madry, A. Beutel, A. Carney, et al. (2024) Openai o1 system card. arXiv preprint arXiv:2412.16720. Cited by: Appendix A. J. Komiyama, D. Oba, and M. Oyamada (2025) Best-of-∞ – asymptotic performance of test-time compute. arXiv preprint arXiv:2509.21091. Cited by: Appendix A, §6. Y. Li, P. Yuan, S. Feng, B. Pan, X. Wang, B. Sun, H. Wang, and K. Li (2024) Escape sky-high cost: early-stopping self-consistency for multi-step reasoning. arXiv preprint arXiv:2401.10480. Cited by: Appendix A. J. Lin, X. Zeng, J. Zhu, S. Wang, J. Shun, J. Wu, and D. Zhou (2025) Plan and budget: effective and efficient test-time scaling on large language model reasoning. arXiv preprint arXiv:2505.16122. Cited by: Appendix A, §6. H. Luo, L. Shen, H. He, Y. Wang, S. Liu, W. Li, N. Tan, X. Cao, and D. Tao (2025) O1-pruner: length-harmonizing fine-tuning for o1-like reasoning pruning. arXiv preprint arXiv:2501.12570. Cited by: Appendix A. [25] (2025-11) Mathai/aime25 · Datasets at Hugging Face. External Links: Link Cited by: §5. [26] (2026-01) MathArena/brumo_2025 · Datasets at Hugging Face. External Links: Link Cited by: §5. [27] (2026-01) MathArena/hmmt_feb_2025 · Datasets at Hugging Face. External Links: Link Cited by: §5. N. Muennighoff, Z. Yang, W. Shi, X. L. Li, L. Fei-Fei, H. Hajishirzi, L. Zettlemoyer, P. Liang, E. Candès, and T. B. Hashimoto (2025) S1: simple test-time scaling. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, p. 20286–20332. Cited by: Appendix A, §1, §6. M. Raič (2019) A multivariate berry–esseen theorem with explicit constants. Bernoulli 25 (4A), p. 2824–2853. Cited by: §C.3, Proposition C.2. D. Rein, B. L. Hou, A. C. Stickland, J. Petty, R. Y. Pang, J. Dirani, J. Michael, and S. R. Bowman (2024) Gpqa: a graduate-level google-proof q&a benchmark. In First Conference on Language Modeling, Cited by: §5. W. Shen, Z. Yang, C. Li, Z. Lu, M. Peng, H. Sun, Y. Shi, S. Liao, S. Lai, B. Zhang, et al. (2025) QwenLong-l1. 5: post-training recipe for long-context reasoning and memory management. arXiv preprint arXiv:2512.12967. Cited by: §5. V. S. Sheng, F. Provost, and P. G. Ipeirotis (2008) Get another label? improving data quality and data mining using multiple, noisy labelers. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, p. 614–622. Cited by: Appendix A, §6. C. Snell, J. Lee, K. Xu, and A. Kumar (2024) Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314. Cited by: Appendix A, §1, §6. K. Team, Y. Bai, Y. Bao, G. Chen, J. Chen, N. Chen, R. Chen, Y. Chen, Y. Chen, Y. Chen, et al. (2025) Kimi k2: open agentic intelligence. arXiv preprint arXiv:2507.20534. Cited by: Appendix A. [35] Thang Luong and Edward Lockhart Advanced version of Gemini with Deep Think officially achieves gold-medal standard at the International Mathematical Olympiad. Note: https://deepmind.google/blog/advanced-version-of-gemini-with-deep-think-officially-achieves-gold-medal-standard-at-the-international-mathematical-olympiad/ Cited by: §1. G. Wan, Y. Wu, J. Chen, and S. Li (2025) Reasoning aware self-consistency: leveraging reasoning paths for efficient llm sampling. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), p. 3613–3635. Cited by: Appendix A. X. Wang, S. Feng, Y. Li, P. Yuan, Y. Zhang, C. Tan, B. Pan, Y. Hu, and K. Li (2025a) Make every penny count: difficulty-adaptive self-consistency for cost-efficient reasoning. In Findings of the Association for Computational Linguistics: NAACL 2025, p. 6904–6917. Cited by: §1, §6. X. Wang, Y. Li, S. Feng, P. Yuan, Y. Zhang, J. Shi, C. Tan, B. Pan, Y. Hu, and K. Li (2025b) Every rollout counts: optimal resource allocation for efficient test-time scaling. arXiv preprint arXiv:2506.15707. Cited by: Appendix A, §6. X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, S. Narang, A. Chowdhery, and D. Zhou (2022) Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171. Cited by: Appendix A, §1, §6. J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al. (2022) Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems 35, p. 24824–24837. Cited by: Appendix A, §6. S. Welleck, A. Bertsch, M. Finlayson, H. Schoelkopf, A. Xie, G. Neubig, I. Kulikov, and Z. Harchaoui (2024) From decoding to meta-generation: inference-time algorithms for large language models. arXiv preprint arXiv:2406.16838. Cited by: Appendix A, §6. J. Xiong, Q. Chen, F. Ye, Z. Wan, C. Zheng, C. Zhao, H. Shen, H. Li, C. Tao, H. Tan, H. Bai, L. Shang, L. Kong, and N. Wong (2025) ATTS: asynchronous test-time scaling via conformal prediction. arXiv preprint arXiv:2509.15148. External Links: Link Cited by: Appendix A. A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. (2025) Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: Appendix A, §5. P. Yao, J. G. Mathew, S. Singh, D. Firmani, and D. Barbosa (2024) A bayesian approach towards crowdsourcing the truths from LLMs. In NeurIPS 2024 Workshop on Behavior Discovery and Understanding (BDU), External Links: Link Cited by: Appendix A. R. Zhang, R. M. S. Khan, Z. Tan, D. Li, S. Wang, and T. Chen (2025) The quest for efficient reasoning: a data-centric benchmark to cot distillation. arXiv preprint arXiv:2505.18759. Cited by: Appendix A. T. P. Zollo, Z. Deng, J. C. Snell, T. Pitassi, and R. Zemel (2024a) Improving predictor reliability with selective recalibration. Transactions on Machine Learning Research. External Links: Link Cited by: Appendix A. T. P. Zollo, T. Morrill, Z. Deng, J. C. Snell, T. Pitassi, and R. Zemel (2024b) Prompt risk control: a rigorous framework for responsible deployment of large language models. In International Conference on Learning Representations, Cited by: Appendix A. B. Zuo and Y. Zhu (2025) Strategic scaling of test-time compute: a bandit learning approach. arXiv preprint arXiv:2506.12721. Cited by: Appendix A, §1, §6. Appendix A Additional Related Work Test-Time Scaling. Since the emergence of long-reasoning models such as GPT-o1 Jaech et al. [2024] and DeepSeek-R1 Guo et al. [2025], test-time scaling Snell et al. [2024]; Welleck et al. [2024]; Xiong et al. [2025] has gained traction as a way to improve performance by allocating substantially more computation (e.g., reasoning tokens) at inference time. One line of work scales the length of chain-of-thought (CoT) trajectory by extending the reasoning process Wei et al. [2022]; representative examples include GPT-o1 Jaech et al. [2024], DeepSeek-R1 Guo et al. [2025], Kimi K2 Team et al. [2025], Qwen3 Yang et al. [2025], gpt-oss Agarwal et al. [2025], and Gemini 3 Pro 14. Another line of work scales via parallel sampling of multiple trajectories, leveraging self-consistency Wang et al. [2022] or Best-of-N selection Brown et al. [2024] and aggregating outputs (e.g., by majority vote). In this paper, PETS focuses on the intersection of these two lines and considers the efficient selection of multiple long reasoning trajectories. Efficient Reasoning. Although test-time scaling can improve performance, its increased inference cost has motivated works on efficient reasoning. Along the line of CoT extension, Muennighoff et al. [2025] proposes budget forcing to control test-time compute by terminating the model’s reasoning once a preset budget is reached. Other approaches aim to elicit shorter yet effective reasoning by fine-tuning with condensed CoT traces Chen et al. [2024a]; Luo et al. [2025]; Hou et al. [2025]; Zhang et al. [2025]. Along the parallel sampling direction, several methods introduce more efficient variants of self-consistency that reduce the number of trajectories while maintaining accuracy Li et al. [2024]; Wan et al. [2025]; Fu et al. [2024]. Most closely related to our work, DeepConf Fu et al. [2025a] leverages per-trajectory confidence to filter low-confidence traces and terminate generation when confidence falls below a threshold. Crowdsourcing. Crowdsourcing has been extensively studied as a budgeted labeling problem, with classical models such as Dawid–Skene capturing item difficulty and annotation noise [Dawid and Skene, 1979]. Building on these probabilistic foundations, a line of work has focused on adaptive task assignment and budget allocation, where items are sequentially selected for labeling based on expected benefit [Sheng et al., 2008]. In particular, Chen et al. [2013] formulate crowdsourcing as a Bayesian decision process and propose the optimistic knowledge gradient (OKG) policy, providing a principled approach to optimal budget allocation under majority-style aggregation. A central ingredient in these approaches is uncertainty quantification [Deng et al., 2025; Zollo et al., 2024a, b; Deng et al., 2023]: reliable estimates of uncertainty determine which items require additional labels, which workers or responses should be trusted, and when the current aggregate label is sufficiently confident. In this sense, crowdsourcing systems depend on uncertainty quantification to trade off exploration, such as collecting more annotations for ambiguous items, against exploitation, such as allocating budget to decisions with high expected utility. Conversely, crowdsourcing can be viewed as a mechanism for reducing epistemic uncertainty by strategically acquiring diverse and informative human judgments. However, these methods are primarily designed for human annotators, and few works have extended them to the setting of test-time consistency in large language models. Computational Resources Allocation. A common family of approaches generates multiple candidate answers and then selects or aggregates them. Komiyama et al. [2025] analyze majority-vote best-of-N in the asymptotic regime N→∞N→∞, and propose an adaptive generation/early-stopping rule based on answer agreement, including extensions to weighted multi-LLM ensembles. Complementarily, Chen et al. [2024b] provide simple two-stage aggregation schemes (knockout and league) with provable failure-probability decay as test-time compute grows, using the LLM itself as a black-box generator and pairwise comparator. When selection relies on an imperfect reward/judge model, scaling can backfire. Huang et al. [2025a] formalize inference-time alignment through Best-of-N sampling and show that large N can induce reward hacking; they propose a pessimistic alternative with scaling-monotonic guarantees. Beyond per-question scaling, allocating compute across queries is crucial under a global budget. Zuo and Zhu [2025] cast Test-time scaling allocation as a bandit learning problem that adapts compute online to query difficulty and solvability. Other work targets different compute axes: Lin et al. [2025] study budget tokens within a single reasoning process via planning and uncertainty-aware scheduling, while Wang et al. [2025b] study efficient test-time scaling for search by allocating rollouts at the direction level to avoid candidate-count bias. Finally, several Bayesian works address reliability and evaluation. Yao et al. [2024] treat multiple LLMs as annotators and extend Dawid–Skene for uncertainty-aware truth aggregation. Gao et al. [2024] calibrate win-rate estimates from LLM evaluators, mitigating bias in LLM-as-judge comparisons. In contrast to reward-based TTS, our work focuses on budget allocation to optimize self-consistency defined against an infinite-compute (weighted) voting oracle, enabling principled allocation without depending on a potentially misspecified reward model. Appendix B Appendix of Offline Case (Section 3) B.1 Bayesian MDP We place independent priors on i θ_i and i μ_i: i∼Dir(i0),i0∈R+M,andμi,m∼(βi,m0,vi,m0),vi,m0>0,m∈[M], θ_i ( α_i^0), α_i^0 _+^M, _i,m ( _i,m^0,v_i,m^0),\ \ v_i,m^0>0,\ \ m∈[M], with i⟂i θ_i μ_i a priori. The Dirichlet parameters αi,m0 _i,m^0 can be viewed as pseudo-counts for class m. The Gaussian parameters (βi,m0,vi,m0)( _i,m^0,v_i,m^0) specify the prior mean and variance of the class-conditional confidence mean μi,m _i,m. At stage t, let StS^t denote the global belief state, which collects posterior parameters for all questions as follows: St(iti=1N,iti=1N,iti=1N),it=(βi,1t,…,βi,Mt),it=(vi,1t,…,vi,Mt).S^t (\ α_i^t\_i=1^N,\ \ β_i^t\_i=1^N,\ \ v_i^t\_i=1^N ), β_i^t=( _i,1^t,…, _i,M^t),\ v_i^t=(v_i,1^t,…,v_i,M^t). In the fully observed offline setting, each observation reveals (Yi,Ci)(Y_i,C_i) for the sampled trace, so it α_i^t admits a Dirichlet-multinomial conjugate update and (it,it)( β_i^t, v_i^t) admit Gaussian conjugate updates conditioned on YiY_i . At each state StS^t, we would select a question iti_t and observe (Yt,Ct)=(yt,ct)(Y_t,C_t)=(y_t,c_t), the Dirichlet parameters update via the conjugate Categorical–Dirichlet rule it+1=it+yt,jt+1=jt∀ji, α_i^t+1= α_i^t+ δ_y_t, α_j^t+1= α_j^t\ \ ∀ j≠ i, where m∈RM δ_m ^M is the one-hot vector with a 11 at entry m. For the confidence model, only the component μi,yt _i,y_t is updated. Recall that under state StS^t, the maintained confidence model is μi,m∣St∼(βi,mt,vi,mt),m∈[M], _i,m S^t ( _i,m^t,v_i,m^t), m∈[M], and we assume the observation model Ct∣(Yt=m,μi,m)∼(μi,m,1)C_t (Y_t=m, _i,m) ( _i,m,1). The Normal–Normal conjugate update yields vi,ytt+1=(1vi,ytt+1)−1,βi,ytt+1=vi,ytt+1(βi,yttvi,ytt+ct),v_i,y_t^t+1= ( 1v_i,y_t^t+1 )^-1, _i,y_t^t+1=v_i,y_t^t+1 ( _i,y_t^tv_i,y_t^t+c_t ), while (βi,mt+1,vi,mt+1)=(βi,mt,vi,mt)( _i,m^t+1,v_i,m^t+1)=( _i,m^t,v_i,m^t) for all mytm≠ y_t, and (jt+1,jt+1)=(jt,jt)( β_j^t+1, v_j^t+1)=( β_j^t, v_j^t) for all jij≠ i. Given belief state StS^t and action it=i_t=i, the posterior distribution of the next label is Pr(Yt=m∣St,it=i)=E[θi,m∣it]=αi,mt∑k=1Mαi,kt. (Y_t=m S^t,i_t=i)=E[ _i,m α_i^t]= _i,m^t _k=1^M _i,k^t. Moreover, conditional on Yt=mY_t=m, the posterior predictive confidence is Gaussian: Ct∣(Yt=m,St,it=i)∼(βi,mt, 1+vi,mt),C_t (Y_t=m,S^t,i_t=i) \! ( _i,m^t,\ 1+v_i,m^t ), Together, the posterior predictive distribution and the conjugate update rules characterize the state transitions and transition probabilities of the resulting Bayesian MDP. B.2 Algorithm of PETS-Offline We introduce the PETS-Offline algorithm here. Before doing that, we will give further explanation on R+(Sit)R^+(S_i^t), an optimistic approximation of the expected one-step utility gain R(Sit)R(S_i^t). R(Sit) R(S_i^t) =EYt,Ct[U(Sit+1)−U(Sit)|St,it=i] =E_Y_t,C_t\! [U(S_i^t+1)-U(S_i^t)\ |\ S^t,\ i_t=i ] =∑m=1MP(Yt=m∣St,it=i)ECt[U(Sit+1)−U(Sit)|St,it=i,Yt=m] = _m=1^MP(Y_t=m S^t,i_t=i)\,E_C_t\! [U(S_i^t+1)-U(S_i^t)\ |\ S^t,\ i_t=i,\ Y_t=m ] Here the per-question terminal utility U(Sit)U(S_i^t) under belief Sit(it,it,it)S_i^t ( α_i^t, β_i^t, v_i^t) is defined as U(Sit)maxm∈[M]Pr(yiW,∞=m∣Sit),U(S_i^t) _m∈[M] \! (y_i^W,∞=m S_i^t ), In the optimistic version following Chen et al. [2013], we use R+(Sit)R^+(S_i^t) to approximate R(Sit)R(S_i^t) to avoid the complex computation of P(Yt=m∣St,it=i)P(Y_t=m S^t,i_t=i) and to achieve consistency of the algorithm as has been proven in Chen et al. [2013]. In our setting where we have an additional parameters governing the posterior distribution of CtC_t, to relieve the computational burden, we make further simplification: Ri+(St) R^+_i(S^t) maxm∈[M]E[U(Sit+1)−U(Sit)|St,it=i,Yt=m] _m∈[M]E\! [U(S_i^t+1)-U(S_i^t)\ |\ S^t,\ i_t=i,\ Y_t=m ] =maxm∈[M](ECt∣St,it=i,Yt=m[U(Upd(Sit;m,Ct))]−U(Sit)) = _m∈[M] (E_C_t S^t,i_t=i,Y_t=m [U(Upd(S_i^t;m,C_t)) ]-U(S_i^t) ) ≈maxm∈[M](U(Upd(Sit;m,βi,mt))−U(Sit)), ≈ _m∈[M] (U(Upd(S_i^t;m, _i,m^t))-U(S_i^t) ), Here Upd(Sit;m,c)Upd(S_i^t;m,c) denotes the posterior update obtained by hypothetically observing (Yt=m,Ct=c)(Y_t=m,C_t=c), and the approximation plugs in the predictive mean E[Ct∣St,it=i,Yt=m]=βi,mtE[C_t S^t,i_t=i,Y_t=m]= _i,m^t. This policy is myopic (and thus not globally optimal in general), but provides a principled and computationally efficient heuristic for adaptive budget allocation. Algorithm 2 Optimistic Knowledge Gradient (confidence-weighted Bayesian setting) 1:Priors (i0,i0,i0)i=1N\( α_i^0, β_i^0, v_i^0)\_i=1^N, total budget T, plug-in parameter κ0κ 0 2:for t=0,1,…,T−1t=0,1,…,T-1 do 3: Compute per-question optimistic utility gain for all i∈[N]i∈[N]: Ri+(St)≈maxm∈[M](U(Upd(Sit;m,βi,mt))−U(Sit))R_i^+(S^t)\ ≈\ _m∈[M] (U(Upd(S_i^t;m, _i,m^t))-U(S_i^t) ) 4: Select it=argmaxi∈[N]Ri+(St)i_t= _i∈[N]R_i^+(S^t). 5: Query the LLM on question iti_t and observe (yt,ct)(y_t,c_t) with yt∈[M]y_t∈[M], ct∈R+c_t _+. 6: Dirichlet update (label): itt+1=itt+yt α_i_t^t+1= α_i_t^t+ δ_y_t. 7: Normal update (confidence mean for class yty_t): vit,ytt+1=(1vit,ytt+1)−1,βit,ytt+1=vit,ytt+1(βit,yttvit,ytt+ct).v_i_t,y_t^t+1= ( 1v_i_t,y_t^t+1 )^-1, _i_t,y_t^t+1=v_i_t,y_t^t+1 ( _i_t,y_t^tv_i_t,y_t^t+c_t ). 8: Keep all other parameters unchanged: for jitj≠ i_t, set (jt+1,jt+1,jt+1)=(jt,jt,jt)( α_j^t+1, β_j^t+1, v_j^t+1)=( α_j^t, β_j^t, v_j^t), and for mytm≠ y_t, set (βit,mt+1,vit,mt+1)=(βit,mt,vit,mt)( _i_t,m^t+1,v_i_t,m^t+1)=( _i_t,m^t,v_i_t,m^t). 9:end for 10: return Terminal labels y^i∈argmaxm∈[M]Pr(yiW,∞=m∣SiT) y_i∈ _m∈[M] (y_i^W,∞=m S_i^T) for all i∈[N]i∈[N]. In the special case Ct≡1C_t≡ 1, the unweighted variant of our algorithm was proved to be consistent by Chen et al. [2013]. Note that a key component in this algorithm is to compute P(yiW,∞=m|Sit)P(y_i^W,∞=m|S_i^t), which can be achieved via Monte Carlo sampling. B.3 Proof of lemma 3.1 Proof of Lemma 3.1. In the offline trajectory allocation setting, after allocating a total of H traces, we output a terminal label y^i y_i for each question i∈[N]i∈[N]. Given the terminal posterior (belief) state SH=iHi=1NS^H=\ α_i^H\_i=1^N, our goal is to maximize the conditional expected self-consistency rate: y^ii=1N \ y_i\_i=1^N ∈argmaxy^ii=1N∑i=1NP(y^i=yiW,∞∣ℱH) ∈ _\ y_i\_i=1^N _i=1^NP\! ( y_i=y_i^W,∞ ^H ) =argmaxy^ii=1N∑i=1N∑m=1MI(y^i=m)P(yiW,∞=m∣SiH), = _\ y_i\_i=1^N _i=1^N _m=1^MI( y_i=m)\,P\! (y_i^W,∞=m S_i^H ), (12) where ℱtt=0H\F^t\_t=0^H denotes the filtration generated by the sample path (i0,yi0,ci0…,it−1,yit−1,cit−1)(i_0,y_i_0,c_i_0…,i_t-1,y_i_t-1,c_i_t-1), and the second equality follows because conditioning on ℱHF^H fixes the terminal posterior SiHS_i^H for each i. Now observe that the objective in (12) is separable across questions. Indeed, for each fixed i, the decision variable y^i y_i only appears in the i-th summand: ∑m=1MI(y^i=m)P(yi∞=m∣SiH). _m=1^MI( y_i=m)\,P\! (y_i^∞=m S_i^H ). Therefore, maximizing the total sum is equivalent to maximizing each term independently. For any question i, we have y^i y_i ∈argmaxy^∈[M]∑m=1MI(y^=m)P(yiW,∞=m∣SiH) ∈ _ y∈[M] _m=1^MI( y=m)\,P\! (y_i^W,∞=m S_i^H ) =argmaxm∈[M]P(yiW,∞=m∣SiH), = _m∈[M]P\! (y_i^W,∞=m S_i^H ), which proves the claim. ∎ Appendix C Appendix of Online Case (Section 4) C.1 Details of Algorithm 1 Streaming Policy. Recall that the discretized formulation (9) yields a static grid-level allocation vector (B1,…,BK)(B_1,…,B_K) under the average budget constraint ∑j=1Kp^jBjBtotal/N _j=1^K p_jB_j B_total/N. In the actual online streaming setting, however, the policy must remain feasible under a remaining-budget constraint that evolves with time. We therefore implement the online policy as a state-dependent dynamic re-planning rule. At time t, define the remaining total budget Rt∈Z0,R1:=Btotal,R_t _ 0, R_1:=B_total, and the remaining horizon Ht:=N−t+1.H_t:=N-t+1. Equivalently, the remaining per-question average budget is B¯t:=RtHt. B_t:= R_tH_t. Upon observing qtq_t, the policy computes a grid-level budget vector by solving (approximately) the discretized allocation problem under the current average budget B¯t B_t: (B1(t),…,BK(t))←GreedyAlloc(p^j,^jj=1K,B¯t),(B^(t)_1,…,B^(t)_K)\;←\; GreedyAlloc (\ p_j, θ^j\_j=1^K,\; B_t ), (13) where GreedyAlloc is Algorithm 1 (run with capacity B¯t B_t) and returns an integer vector satisfying ∑j=1Kp^jBj(t)B¯t. _j=1^K p_j\,B^(t)_j B_t. The actual budget spent on the current question is then bt:=Bjt(t)b_t:=B^(t)_j_t. After spending btb_t on question qtq_t, the remaining budget updates as Rt+1:=Rt−bt.R_t+1:=R_t-b_t. By construction, the policy always respects the global budget constraint ∑t=1NbtBtotal _t=1^Nb_t B_total: indeed, RtR_t is nonnegative and decreases by exactly the spent amount each step. The rule (13) makes the policy dynamic: even though (9) is written with a fixed average constraint, the online execution continuously recomputes the target grid budgets using the remaining budget-to-horizon ratio B¯t B_t. This re-planning step corrects for randomness and prevents early overspending, while retaining the same structure as in Algorithm 1. Random Rounding Method. Our greedy allocation procedure increases the grid-level budgets in discrete steps. In particular, for grid j one increment corresponds to adding two additional trials, which consumes expected budget 2p^j2 p_j (since a p^j p_j fraction of incoming questions fall into grid j). As a result, near the end of the budget, the remaining expected budget may be insufficient to execute the next full 22-trial increment for the current best grid. Let δ denote the remaining expected budget (per-question average budget under the gridized constraint) at the moment when the algorithm is about to take one more 22-trial increment for the currently selected grid i⋆i . Suppose that δ∈(0,2p^i⋆),δ∈(0,2 p_i ), so a full increment for grid i⋆i would violate feasibility. Let B=(B1,…,BK)B=(B_1,…,B_K) be the current integer allocation vector. Define B+B^+ as the neighboring allocation obtained by applying one additional greedy increment to grid i⋆i : Bi⋆+=Bi⋆+2,Bj+=Bj(ji⋆).B^+_i =B_i +2, B^+_j=B_j\ (j≠ i ). We then output a randomized allocation B~ B as follows: – With probability ρ:=δ/(2p^i⋆)\;ρ:=δ/(2 p_i ), set B~=B+ B=B^+. – With probability 1−ρ\;1-ρ, set B~=B B=B. By construction, E[∑j=1Kp^jB~j]=∑j=1Kp^jBj+ρ⋅2p^i⋆=∑j=1Kp^jBj+δ,E\! [ _j=1^K p_j\, B_j ]= _j=1^K p_j\,B_j\;+\;ρ· 2 p_i = _j=1^K p_j\,B_j\;+\;δ, so the randomized rounding consumes exactly the remaining expected budget and keeps the expected budget constraint tight (hence feasible). C.2 Proof of Optimality of Algorithm 1 (Theorem 4.1) We first establish a diminishing-returns property of SC(θ;B)SC(θ;B) when θ is a scalar, which directly motivates the optimality of our greedy allocation rule in Algorithm 1. Lemma C.1. For any θ∈[0,1]θ∈[0,1] and n∈N+n∈ N_+, the marginal gain R(θ,n)R(θ,n) is zero for odd n. Meanwhile, it is a nonincreasing function of n over even integers, and strictly decreasing when θ12θ≠ 12. Proof of Lemma C.1. We focus on the binary case where each call returns an answer in 0,1\0,1\ and the ground-truth label is 11, since the function SC(θ;n)SC(θ;n) enjoys a symmetry around θ=12θ= 12: SC(θ;n)=SC(1−θ;n),∀θ∈[0,1],B∈N.SC(θ;n)=SC(1-θ;n), ∀θ∈[0,1], 10000\ B . (14) Indeed, flipping the answer of 0 and 11 for each call transforms the binomial count X∼Bin(n,θ)X (n,θ) into B−X∼Bin(B,1−θ)B-X (B,1-θ), while the majority rule with random tie-breaking is invariant under this relabeling. Consequently, by (14), R(θ,n)=R(1−θ,n),∀θ∈[0,1],B∈N.R(θ,n)=R(1-θ,n), ∀θ∈[0,1], 10000\ B . Therefore, it suffices to analyze the case θ12θ 12 (replace θ by 1−θ1-θ if θ<12θ< 12). Finally, the boundary case θ=12θ= 12 is trivial: when θ=12θ= 12, we have X∼Bin(n,12)X (n, 12) which is symmetric around n/2n/2, hence SC(12;n)=P(X>n2)+12P(X=n2)=12,∀n,SC ( 12;n )=P (X> n2 )+ 12P (X= n2 )= 12, ∀ n, Therefore, for this boundary case, R(12,n)≡0.R ( 12,n )≡ 0. which means, any extra budgets on questions with θ=12θ= 12 bring no increment. In the remainder of the proof, we may assume θ>12θ> 12. If n is odd, set n=2m−1n=2m-1. Two cases can change the majority vote: – When there are m correct answers in 2m−12m-1 samples, the majority is correct. If the 2m2m-th answer is wrong, the total becomes m correct and m wrong, which is a tie. With random tie breaking, correctness drops from 1 to 0.5. The “drop amount” is 0.5. The probability of the borderline configuration is P[Choose which m of the first (2m−1)are correct]=(2m−1m)θm(1−θ)m−1.P[Choose which m of the first 10000\ (2m-1) 10000\ are correct]= 2m-1mθ^m(1-θ)^m-1. The next sample then satisfies P[the 2m-th sample is wrong]=1−θ.P[the 10000\ 2m 10000\ -th sample is wrong]=1-θ. while the 2m2m-th is wrong. Then the decreasing probability is 12(2m−1m)θm(1−θ)m−1⋅(1−θ). 12 2m-1mθ^m(1-θ)^m-1·(1-θ). – When there are m−1m-1 correct answers in 2m−12m-1 samples, and the 2m2m-th is correct. Then similarly, increasing probability is 12(2m−1m−1)θm−1(1−θ)m⋅θ. 12 2m-1m-1θ^m-1(1-θ)^m·θ. Thus R(θ,2m−1)=0R(θ,2m-1)=0 for odd n=2m−1n=2m-1. Similarly, for even n, there are also two cases which will increasing the correct probability, which is m correct answers in 2m2m samples and the 2m+12m+1-th is also correct or wrong, thus R(θ,2m)=12θ(2m)[θ(1−θ)]m−12(1−θ)(2m)[θ(1−θ)]m=(θ−12)(2m)[θ(1−θ)]m.R(θ,2m)= 12θ 2mm[θ(1-θ)]^m- 12(1-θ) 2mm[θ(1-θ)]^m= (θ- 12 ) 2mm[θ(1-θ)]^m. Furthermore, since R(θ,2m+2)R(θ,2m)=(2m+2m+1)(2m)⋅θ(1−θ)=(4−2m+1)θ(1−θ)<1. R(θ,2m+2)R(θ,2m)= 2m+2m+1 2mm·θ(1-θ)= (4- 2m+1 )θ(1-θ)<1. Then R(θ,2m)R(θ,2m) is strictly decreasing for any m when θ12θ≠ 12. ∎ Proof of Theorem 4.1. Recall the discretized (grided) optimization problem: maxBj∈Z0∑j=1Kp^jSC(θj;Bj)s.t.∑j=1Kp^jBjBtotal/N, _\B_j _ 0\ _j=1^K p_jSC( _j;B_j) .t. _j=1^K p_jB_j B_total/N, (15) where p^j p_j is the estimated probability mass of grid j (i.e., the fraction of problems whose difficulty falls into grid j). If we increase BjB_j by one (i.e. add one extra trial to grid j), then the objective in (15) increases by p^jR(θj,Bj), p_jR( _j,B_j), and the expected-budget constraint increases by pjp_j. Therefore, the marginal gain per unit expected cost equals p^jR(θj,Bj)p^j=R(θj,Bj). p_jR( _j,B_j) p_j=R( _j,B_j). This shows that the grid probability p^j p_j appears in both the objective and the expected-budget constraint, and cancels out when comparing actions by marginal gain per expected-cost unit. Hence, choosing the next increment by maximizing R(θj,Bj)R( _j,B_j) is exactly greedy with respect to the correct marginal reward per expected-cost unit. By Lemma C.1, for every θ>1/2θ>1/2 we have R(θ,2m−1)=0andR(θ,0)>R(θ,2)>⋯>R(θ,2m)>⋯,R(θ,2m-1)=0 R(θ,0)>R(θ,2)>·s>R(θ,2m)>·s, i.e., the nontrivial marginal gains occur only at even budgets and form a nonincreasing sequence. In particular, since R(θ,2m−1)=0R(θ,2m-1)=0, we have SC(θ;2m)=SC(θ;2m−1),SC(θ;2m)=SC(θ;2m-1), so allocating the 2m2m-th trial does not improve the objective compared with 2m−12m-1. Equivalently, for any m0m 0, SC(θ;2m+1)−SC(θ;2m−1)=(SC(θ;2m+1)−SC(θ;2m))=R(θ,2m).SC(θ;2m+1)-SC(θ;2m-1)= (SC(θ;2m+1)-SC(θ;2m) )=R(θ,2m). Thus, when we think in effective increments, adding two trials to a grid (from 2m−12m-1 to 2m+12m+1) yields exactly the marginal reward R(θ,2m)R(θ,2m), and these effective marginal rewards decrease with m. Consider the multiset of all effective marginal rewards ℋ:=R(θj,2m):j∈[K],m=0,1,2,….H:= \R( _j,2m):j∈[K],m=0,1,2,… \. Any feasible allocation Bj\B_j\ in (15) corresponds to choosing a prefix of the sequence R(θj,0),R(θj,2),R(θj,4),…R( _j,0),R( _j,2),R( _j,4),… because one cannot obtain the (m+1)(m+1)-th effective gain for grid i without also taking the first m effective gains. Moreover, by Lemma C.1, each such sequence is nonincreasing. Algorithm 1 maintains the active set S=(j,Bj)i=1KS=\(j,B_j)\_i=1^K and repeatedly selects the grid with the largest currently available effective marginal reward, i.e., it chooses j⋆∈argmaxjR(θj,Bj)j ∈ _jR( _j,B_j) and then increases Bj⋆B_j by 22. Because each grid’s effective marginal rewards form a nonincreasing sequence, this procedure is exactly the process which picks the globally largest remaining element from a collection of nonincreasing lists. Hence after t effective steps, the greedy algorithm has selected the t largest elements in ℋH that are feasible under the prefix constraints, which maximizes the accumulated improvement in the objective among all allocations spending the same expected budget. If the remaining budget is insufficient to complete the next 22-trial effective step for the current best grid, we can randomize the last step: suppose the remaining expected budget is δ∈(0,2pj⋆)δ∈(0,2p_j ). We perform the next 22 trials for grid j⋆j with probability δ/(2pj⋆)δ/(2p_j ) and do nothing otherwise. This keeps the expected budget exactly feasible and achieves the optimal convex combination of the two neighboring integer allocations. Therefore, Algorithm 1 attains the optimum of (15). ∎ C.3 22-parameter Approximation in Multi-Choice Case In the multi-choice setting, the difficulty parameter θ is high-dimensional, making direct optimization costly. We therefore use a Gaussian surrogate family (an+b)a>0\ (a n+b)\_a>0 to approximate the self-consistency rate SC(;n)SC( θ;n). This enables a direct extension of Algorithm 1: replace SC(;n)SC( θ;n) with (an+b) (a n+b) for a suitable pair (a,b)(a,b). Proposition C.2 (Gaussian-probit approximation with 1/n1/ n rate). Fix M2M 2 and ∈M−1 θ∈^M-1 with θ1>θ2⋯θM _1> _2 ·s _M. Let d:=M−1d:=M-1. Define the margin vector ∈R+d _+^d by :=jθ1−θj+1(j=1,…,d),_j:= _1- _j+1 (j=1,…,d), and define the covariance matrix ∈Rd×d ^d× d of V1V_1 as in (17) below. Define σmin:=min1jdjj,a:=min1jdjj. _ := _1 j d _j, a:= _1 j d _j _j. Then for all n1n 1, the majority-vote success probability satisfies |SC(;n)−(an)|C(,M)n, |SC( θ;n)- (a n) | C( θ,M) n, where one explicit admissible constant is given by C(,M):=CBEd1/4ρ()+d2πσmin+(d−1)ϕ(a)a,C( θ,M):=C_BEd^1/4ρ( θ)+ d 2π _ + (d-1)φ(a)a, with the auxiliary quantities ρ():=E∥(V1−)−1/2∥23,ϕ(x):=12πe−x2/2.ρ( θ):=E \|^-1/2(V_1- ) \|_2^3, φ(x):= 1 2πe^-x^2/2. Here CBEC_BE is the Berry-Esseen approximation constant[Raič, 2019]. Moreover, since ‖V1−‖22d\|V_1- \|_2 2 d a.s., we have the fully explicit bound ρ()8d3/2λmin()3/2,ρ( θ) 8d^3/2 _ ( )^3/2, which yields the explicit bound C(,M)8CBEd7/4λmin()3/2+d2πσmin+(d−1)ϕ(a)a.C( θ,M) 8C_BEd^7/4 _ ( )^3/2+ d 2π _ + (d-1)φ(a)a. Proof of Proposition C.2. Let A∈1,…,MA∈\1,…,M\ with P(A=i)=θiP(A=i)= _i. After n i.i.d. draws, let X=(X1,…,XM)∼Multinomial(n,),SC(;n)=pn:=P(argmaxiXi=1),X=(X_1,…,X_M) (n, θ), ( θ;n)=p_n:=P( _iX_i=1), with uniform random tie-breaking. Define the margin vector D:=(D2,…,DM)∈Zd,Dj:=X1−Xj(j=2,…,M).D:=(D_2,…,D_M)∈ Z^d, D_j:=X_1-X_j\ (j=2,…,M). Let ℰn:=argmaxiXi=1 E_n:=\ _iX_i=1\. Then deterministically D∈[1,∞)d⊆ℰn⊆D∈R+d.\D∈[1,∞)^d\ E_n \D _+^d\. This gives the sandwich bound P(D∈[1,∞)d)pnP(D∈R+d).P(D∈[1,∞)^d) p_n (D _+^d). (16) Let A1,…,AnA_1,…,A_n be the i.i.d. samples. Define for each round b the vector Vb=(Vb,2,…,Vb,M)∈−1,0,1d,Vb,j:=I(Ab=1)−I(Ab=j).V_b=(V_b,2,…,V_b,M)∈\-1,0,1\^d, V_b,j:= I(A_b=1)- I(A_b=j). This gives D=∑b=1nVb,E[Vb]=:=(θ1−θ2,…,θ1−θM)∈R+d.D= _b=1^nV_b, [V_b]= :=( _1- _2,…, _1- _M) _+^d. A direct computation gives the covariance matrix =Cov(V1)∈Rd×d =Cov(V_1) ^d× d: =jjθ1+θj+1−(θ1−θj+1)2,=jkθ1−(θ1−θj+1)(θ1−θk+1)(jk)._j= _1+ _j+1-( _1- _j+1)^2, _jk= _1-( _1- _j+1)( _1- _k+1) (j≠ k). (17) Note that θ1j1_j _1 1 implies θ1jk−θ12=θ1(1−θ1)0_jk _1- _1^2= _1(1- _1) 0, so has nonnegative off-diagonal entries. Since =Cov(V1) =Cov(V_1), it is always positive semidefinite. To prove ≻0 0, it suffices to show that for any u∈Rdu ^d, u⊤u=Var(u⊤V1)=0⟹u=0.u u=Var(u V_1)=0 u=0. Note that V1V_1 takes only the following values: V1=d,A=1,−ej,A=j+1,j=1,…,d,V_1= cases1_d,&A=1,\\ -e_j,&A=j+1, j=1,…,d, cases where d1_d is the all-ones vector in RdR^d and eje_j is the j-th standard basis vector. Thus the inner product is u⊤V1=∑i=1dui,A=1,−uj,A=j+1,j=1,…,d.u V_1= cases _i=1^du_i,&A=1,\\ -u_j,&A=j+1, j=1,…,d. cases If Var(u⊤V1)=0Var(u V_1)=0, then u⊤V1u V_1 must be almost surely constant. Since θ1>0 _1>0 and θj+1>0 _j+1>0 for all j, all events A=1\A=1\ and A=j+1\A=j+1\ occur with positive probability, so we must have ∑i=1dui=−uj,∀j=1,…,d. _i=1^du_i=-u_j, ∀ j=1,…,d. In particular, the right-hand side does not depend on j, implying u1=⋯=ud=:cu_1=·s=u_d=:c. Substituting into the above identities yields dc=−cdc=-c, i.e., (d+1)c=0(d+1)c=0, hence c=0c=0 and therefore u=0u=0. Thus Var(u⊤V1)=0Var(u V_1)=0 implies u=0u=0, which proves ≻0 0. Let G∼(n,n)G N(n ,n ). By Bentkus’ convex-set Berry–Esseen bound[Raič, 2019], for any convex set A⊂RdA ^d, |P(D∈A)−P(G∈A)|CBEd1/4nE∥(V1−)−1/2∥23. |P(D∈ A)-P(G∈ A) | C_BEd^1/4 n\,E \|^-1/2(V_1- ) \|_2^3. Both A0:=R+dA_0:=R_+^d and A1:=[1,∞)dA_1:=[1,∞)^d are convex, hence |P(D∈Ak)−P(G∈Ak)|CBEd1/4nρ(),k∈0,1. |P(D∈ A_k)-P(G∈ A_k) | C_BEd^1/4 n\,ρ( θ), k∈\0,1\. (18) Write G=n+nZG=n + n\,Z with Z∼(0,)Z N(0, ). This implies 0P(G∈A0)−P(G∈A1)∑j=1dP(0Gj1)=∑j=1dP(−nZjj1n−n)j.0 (G∈ A_0)-P(G∈ A_1) _j=1^dP(0 G_j 1)= _j=1^dP\! (- n\,_j Z_j 1 n- n\,_j ). Since Zj∼(0,)jjZ_j N(0,_j) has density bounded by 1/2πjj1/ 2π_j, P(−nZjj1n−n)j1n⋅12πjj1n⋅12πσmin.P\! (- n\,_j Z_j 1 n- n\,_j ) 1 n· 1 2π_j 1 n· 1 2π\, _ . Therefore, the boundary gap satisfies 0P(G∈A0)−P(G∈A1)dn⋅12πσmin.0 (G∈ A_0)-P(G∈ A_1) d n· 1 2π\, _ . (19) Let Z′=(Z1′,…,Zd′)Z =(Z _1,…,Z _d) be the coordinate-wise standardized version of Z: Zj′:=−Zjjj,cj:=jj>0,a:=min1jdcj.Z _j:=- Z_j _j, c_j:= _j _j>0, a:= _1 j dc_j. This gives P(G∈A0)=P(Z−n)=P(Z′nc)=:g(n).P(G∈ A_0)=P(Z - n\, )=P(Z n\,c)=:g( n). Let j⋆∈argminjcjj ∈ _jc_j so that cj⋆=ac_j =a. Since the event Z′nc\Z n\,c\ implies Zj⋆′anZ _j a n, we have the upper bound g(n)P(Zj⋆′an)=(an).g( n) (Z _j a n)= (a n). For the lower bound, by Gaussian association (nonnegative correlations) the decreasing events [Esary et al., 1967]. Zj′an\Z _j a n\ satisfy P(⋂j=1dZj′an)∏j=1dP(Zj′an)=(an)d.P ( _j=1^d\Z _j a n\ ) _j=1^dP(Z _j a n)= (a n)^d. Moreover ⋂jZj′an⊆Z′nc _j\Z _j a n\ \Z n\,c\, hence g(n)(an)d.g( n) (a n)^d. Therefore, the Gaussian approximation error satisfies 0(an)−g(n)(an)−(an)d.0 (a n)-g( n) (a n)- (a n)^d. (20) Now let p:=(an)∈(1/2,1)p:= (a n)∈(1/2,1) and note that for x∈[0,1]x∈[0,1], 1−xd−1(d−1)(1−x)1-x^d-1 (d-1)(1-x) (Bernoulli inequality). The Bernoulli inequality yields p−pd=p(1−pd−1)(d−1)p(1−p)(d−1)(1−p).p-p^d=p (1-p^d-1 ) (d-1)p(1-p) (d-1)(1-p). Using Mills’ ratio 1−(x)ϕ(x)/x1- (x) φ(x)/x for x>0x>0, we obtain 0(an)−g(n)(d−1)(1−(an))(d−1)ϕ(an)an(d−1)ϕ(a)an,0 (a n)-g( n) (d-1) (1- (a n) ) (d-1) φ(a n)a n (d-1)φ(a)a n, where the last step uses ϕ(an)ϕ(a)φ(a n) φ(a) for n1n 1. From (16), (18), and (19), |pn−P(G∈A0)|CBEd1/4nρ()+dn⋅12πσmin. |p_n-P(G∈ A_0) | C_BEd^1/4 nρ( θ)+ d n· 1 2π _ . Adding Step 5 yields |pn−(an)|CBEd1/4nρ()+dn⋅12πσmin+(d−1)ϕ(a)an. |p_n- (a n) | C_BEd^1/4 nρ( θ)+ d n· 1 2π _ + (d-1)φ(a)a n. This proves the claim with b=0b=0 and the stated explicit constant C(,M)C( θ,M). ∎ Remark C.3. Indeed, in practice we use the regression method to decide parameter a,ba,b for given θ, such approximation has very great precision, see Figure 5 as a reference. Recall the Gaussian surrogate family ga,b(k):=(ak+b),a>0,k0,g_a,b(k)\;:=\; \! (a k+b ), a>0,\ k 0, where is the standard normal CDF and ϕ:=′φ:= is the standard normal PDF. Concavity on the relevant budget range. In our allocation procedure, each question (or difficulty grid) receives at least a small warm-up budget before the greedy stage. Let kmin1k_ 1 denote the smallest budget value that can occur in the greedy stage (e.g., kmin=4k_ =4 if we warm up with 4 samples). The next lemma shows ga,bg_a,b is concave for all kkmink k_ as long as ak+ba k+b is nonnegative on that range. Lemma C.4 (Concavity of ga,bg_a,b for kkmink k_ ). Fix a>0a>0 and b∈Rb . If akmin+b 0,a k_ +b\; \;0, (21) then the function k↦ga,b(k)k g_a,b(k) is concave on [kmin,∞)[k_ ,∞) (in the usual continuous sense). In particular, ga,b′(k)g_a,b (k) is nonincreasing on [kmin,∞)[k_ ,∞). Proof. For k>0k>0, let t(k):=ak+bt(k):=a k+b. By the chain rule, ga,b′(k)=ϕ(t(k))⋅a2k.g_a,b (k)=φ(t(k))· a2 k. Differentiating again (using ϕ′(x)=−xϕ(x)φ (x)=-xφ(x)) yields ga,b′(k) g_a,b (k) =dk(ϕ(t(k))⋅a2k) = ddk (φ(t(k))· a2 k ) =ϕ′(t(k))⋅t′(k)⋅a2k+ϕ(t(k))⋅dk(a2k) =φ (t(k))· t (k)· a2 k\;+\;φ(t(k))· ddk ( a2 k ) =(−t(k)ϕ(t(k)))⋅a2k⋅a2k+ϕ(t(k))⋅(−a4k3/2) = (-t(k)φ(t(k)) )· a2 k· a2 k\;+\;φ(t(k))· (- a4k^3/2 ) =−ϕ(t(k))(a2t(k)4k+a4k3/2). =-\,φ(t(k)) ( a^2\,t(k)4k+ a4k^3/2 ). Now assume (21). Then for all kkmink k_ we have t(k)=ak+b0t(k)=a k+b 0. Since ϕ(t(k))>0φ(t(k))>0 and the bracketed term is nonnegative, we conclude ga,b′(k)0g_a,b (k) 0 for all kkmink k_ , i.e., ga,bg_a,b is concave on [kmin,∞)[k_ ,∞). ∎ In our multi-choice extension, we approximate SC(i;k)SC( θ_i;k) by SC(;k)≈=(aik+bi),SC( θ;k)≈= (a_i k+b_i), which has diminishing returns on the greedy range. Therefore, replacing SC(i;k)SC( θ_i;k) by this Gaussian family preserves the key structural property needed by Algorithm 1, and the same greedy allocation rule applies verbatim in the multi-choice case. Figure 5: Probability that multinomial majority voting selects the true best option as a function of budget. We plot P(YMaj(B)=argmaxy∈θy)P\! (Y^Maj(B)= _y _y ) versus Budget∈1,…,64 Budget∈\1,…,64\ for different ground-truth preference vectors =(θ1,…,θM) θ=( _1,…, _M). Gray curves (Exact) are computed from the true θ (exact for M=2,4M=2,4; Monte Carlo estimates for M=10M=10), while green dotted curves (Probit) are produced by fitting a two-parameter probit model and evaluating the fitted model across budgets. The fitted probit curves closely track the exact/MC curves in all regimes. Panels correspond to M∈2,4,10M∈\2,4,10\. For M=4M=4, we use: dominate [0.8,0.1,0.1,0][0.8,0.1,0.1,0], head-heavy [0.6,0.3,0.05,0.05][0.6,0.3,0.05,0.05], linear [0.4,0.3,0.2,0.1][0.4,0.3,0.2,0.1], flat [0.3,0.25,0.25,0.2][0.3,0.25,0.25,0.2], and uniform [0.25,0.25,0.25,0.25][0.25,0.25,0.25,0.25]. For M=10M=10, we use: dominate [0.8,0.15,0.05,0,…,0][0.8,0.15,0.05,0,…,0], head-heavy [0.25,0.15,0.10,0.0714,…,0.0714][0.25,0.15,0.10,0.0714,…,0.0714], linear [10,9,…,1]/55[10,9,…,1]/55, flat normalize([10,9,…,1]0.4)normalize([10,9,…,1]^0.4), and uniform [0.1,…,0.1][0.1,…,0.1]. C.4 Warm-up griding and Difficulty Estimation Details In practice, we use a short warm-up to map each question to a coarse difficulty grid, and then apply a precomputed one-shot budget for that grid. For each question q, we first draw 44 responses and let Cq(4)=(c1,c2,c3,c4)C_q^(4)=(c_1,c_2,c_3,c_4) be the sorted option counts. Up to label permutation, Cq(4)C_q^(4) takes one of five patterns, inducing five grids Tq∈1,…,5T_q∈\1,…,5\ via a deterministic rule Tq=g(Cq(4))T_q=g(C_q^(4)). Using training questions with large i.i.d. answer pools, we estimate the grid proportions p^jj=15\ p_j\_j=1^5 and fit a representative surrogate curve (a^j,b^j)( a_j, b_j) for each grid. At test time, we assign q to TqT_q using the 44 warm-up samples and then allocate BTqB_T_q additional samples in a single shot. We provide the estimation details delow. Given a question q, we draw 44 i.i.d. LLM responses and count how many times each answer option is selected. Let Cq(4)=(c1,c2,c3,c4)C_q^(4)=(c_1,c_2,c_3,c_4) denote the sorted (descending) counts of answer options among the first four responses, padding with zeros if fewer than four distinct options appear. Note that this definition is valid regardless of the total number of answer options: with only four samples, at most four options can appear, so the count pattern space is unchanged for multiple-choice with 4 4 options and also extends to other discrete-answer settings. By symmetry among answer labels, there are exactly five possible patterns: (4,0,0,0),(3,1,0,0),(2,2,0,0),(2,1,1,0),(1,1,1,1). \(4,0,0,0),\,(3,1,0,0),\,(2,2,0,0),\,(2,1,1,0),\,(1,1,1,1) \. We define a deterministic grid mapping Tq=g(Cq(4))∈1,…,5,T_q=g(C_q^(4))∈\1,…,5\, e.g., g can map the patterns above to grids in the listed order (any fixed one-to-one mapping works as long as it is used consistently). For each training question q, we assume access to a large pool of i.i.d. answers generated from yq∼Cat(q).y_q ( θ_q). To account for the randomness of using only four warm-up samples, we repeatedly subsample four answers (without replacement from the pool, or with replacement if the pool is large) and record the induced grid: Tq(r)=g(Cq,r(4)),r=1,…,R.T_q^(r)=g\! (C_q,r^(4) ), r=1,…,R. This yields an empirical, question-specific grid distribution p^q(j)=1R∑r=1RTq(r)=j,j∈1,…,5. p_q(j)= 1R _r=1^R1\T_q^(r)=j\, j∈\1,…,5\. Averaging over training questions produces the empirical grid proportions p^j=1|train|∑q∈trainp^q(j),j∈1,…,5. p_j= 1| Q_train| _q∈ Q_train p_q(j), j∈\1,…,5\. For each training question q, we fit its two-parameter difficulty curve (a^q,b^q)( a_q, b_q) using the procedure in Section C.3 based on the full answer pool (so that the fit is stable). To obtain a representative curve for each grid, we aggregate the per-question fits within that grid. To reduce sensitivity to borderline cases, we recommend using the soft grid weights p^q(j) p_q(j): (a^j,b^j)=argmin(a,b)∑q∈trainp^q(j)ℓq(a,b),( a_j, b_j)= _(a,b) _q∈ Q_train p_q(j)\, _q(a,b), where ℓq(a,b)=En|SC((q);n)−(an+b)| _q(a,b)=E_n |SC( θ(q);n)- (a n+b) | is the fitting loss in Section C.3. A simpler alternative is a weighted average in parameter space, a^j=∑qp^q(j)a^q∑qp^q(j),b^j=∑qp^q(j)b^q∑qp^q(j), a_j= _q p_q(j) a_q _q p_q(j), b_j= _q p_q(j) b_q _q p_q(j), which we found to work well when the per-question fits are already accurate. Appendix D An Asymptotic Perspective on Online vs. Offline PETS In this section, we prove that as the total budget B→∞B→∞, the budget allocated to each question type converges to a fixed proportion for both the offline (Section 3) and the online (Section 4) settings. Moreover, the limiting proportions in the offline and online cases are very close, which highlights the consistency between the two methods. D.1 Convergence of Budget Proportions for the Online Case We first show that as B→∞B→∞, every problem type will be sampled infinitely many times. Lemma D.1. For a binary-choice problem set P with difficulty labels θii∈[N]\ _i\_i∈[N] and corresponding probabilities pii∈[N]\p_i\_i∈[N] (where pi>0p_i>0), suppose we allocate budgets using Algorithm 1. Then, as the total budget B→∞B→∞, the sample count Bi(B)B_i(B) for every i diverges to infinity. Proof of Lemma D.1. Since difficulty labels θ and 1−θ1-θ lead to the same behavior in our algorithm, without loss of generality we assume θi∈(1/2,1) _i∈(1/2,1). For simplicity, assume each problem type has been sampled once initially. Then, following Algorithm 1, the marginal accuracy gain from allocating two additional budget units at level 2m−12m-1 is R(2m−1;θi)=pi(θi−12)(2m)[θi(1−θi)]m,m∈N,R(2m-1; _i)=p_i ( _i- 12 ) 2mm\,[ _i(1- _i)]^m, m∈ N, (22) where λi _i is the probability mass of the problem type with label θi _i. At round t, the algorithm selects the type satisfying it∈argmaxiR(2mi(t)−1;θi),mit(t+1)=mit(t)+1,mj(t+1)=mj(t)(jit),i_t∈ _iR(2m_i(t)-1; _i), m_i_t(t+1)=m_i_t(t)+1, m_j(t+1)=m_j(t)\ \ (j≠ i_t), with the initialization mi(0)=1m_i(0)=1. Define λi:=θi(1−θi)∈(0,1/4) _i:= _i(1- _i)∈(0,1/4). Then R(2m+1;θi)R(2m−1;θi)=(2m+2m+1)(2m)⋅λi=(4−2m+1)λi<4λi<1. R(2m+1; _i)R(2m-1; _i)= 2m+2m+1 2mm· _i= (4- 2m+1 ) _i<4 _i<1. Therefore, as m increases, the marginal gain for each arm strictly decreases. Now suppose there exists some type j that is sampled only finitely many times as B→∞B→∞. Then there exists a constant M such that mj(t)≡Mm_j(t)≡ M for all sufficiently large t, and thus R(mj(t);θj)≡R(M;θj)>0R(m_j(t); _j)≡ R(M; _j)>0 remains constant. On the other hand, at least one arm i must be selected infinitely often; for that arm, we have mi(t)→∞m_i(t)→∞ and hence R(mi(t);θi)→0R(m_i(t); _i)→ 0, which contradicts the greedy choice rule (since eventually R(M;θj)R(M; _j) would dominate). Therefore, every arm must be sampled infinitely often, i.e., mi(t)→∞m_i(t)→∞ for all i. ∎ Next, we derive the convergence of sampling proportions and identify the limiting ratios. Proposition D.2. Under the same conditions as Lemma D.1, the ratio mi(B)/Bm_i(B)/B converges to a constant for each i as B→∞B→∞. Moreover, the limiting allocation ratio satisfies mi(B)B∝1p(θi). m_i(B)B 1p( _i). where p(θ)=−log(4θ(1−θ))>0p(θ)=- (4θ(1-θ))>0. Proof of Proposition D.2. Define, for each difficulty label, (2m−1)i:=−logR(2m−1;θi)._i(2m-1):=- R(2m-1; _i). (23) For each update of arm i, the corresponding increment in i is (2m−1)i=(2m+1)i−(2m−1)i=−log((4−2m+1)pi)._i(2m-1)=_i(2m+1)-_i(2m-1)=- ( (4- 2m+1 )p_i ). Since for m1m 1 we have 4−2m+1∈[3,4)4- 2m+1∈[3,4), it follows that for each fixed i, 0<−log(4pi)(m)i−log(3pi)<∞.0<- (4p_i) _i(m) - (3p_i)<∞. Let :=maxmaxisupm1(m)i=maxi(−log(3pi))<∞_ := _i _m 1_i(m)= _i (- (3p_i) )<∞. Define the minimum and maximum potentials at time t as L(t):=mini(mi(t))i,U(t):=maxi(mi(t))i.L(t):= _i_i (m_i(t) ), U(t):= _i_i (m_i(t) ). At time t, the algorithm samples the arm attaining the minimum potential, say iti_t, and increases its potential from L(t)L(t) to at most L(t)+maxL(t)+_ , while leaving all other arms unchanged. Hence, U(t+1)maxU(t),L(t)+max.U(t+1) \U(t),\,L(t)+_ \. Consequently, the potential range satisfies U(t+1)−L(t+1)maxU(0)−L(0),max.U(t+1)-L(t+1) \U(0)-L(0),\,_ \. By induction, letting C:=maxU(0)−L(0),maxC:= \U(0)-L(0),\,_ \, we obtain |(mi(t))i−(mj(t))j|C,∀i,j. |_i (m_i(t) )-_j (m_j(t) ) | C, ∀ i,j. (24) Next, we derive a first-order approximation for (m)i_i(m). By Stirling’s formula, R(m;θi) R(m; _i) =λi(θi−12)(2m)pim = _i ( _i- 12 ) 2mmp_i^m (25) =λi(θi−12)4mπm(1+O(1m))pim. = _i ( _i- 12 ) 4^m π m (1+O ( 1m ) )p_i^m. (26) Therefore, the first-order potential expansion is (m)i=−logR(m;θi)=−mlog(4pi)+12logm+bi+o(1),_i(m)=- R(m; _i)=-m (4p_i)+ 12 m+b_i+o(1), (27) where bi:=−log(λi(θi−12)π)b_i:=- ( _i ( _i- 12 ) π ) is a constant, and o(1)→0o(1)→ 0 as m→∞m→∞. Combining (24) and (27), we obtain −mi(t)log(4pi)+12logmi(t)+bi=−mj(t)log(4pj)+12logmj(t)+bj+O(1).-m_i(t) (4p_i)+ 12 m_i(t)+b_i=-m_j(t) (4p_j)+ 12 m_j(t)+b_j+O(1). Moving the logarithmic terms to the right-hand side yields mi(t)log(4pi)=mj(t)log(4pj)+O(logt),m_i(t) (4p_i)=m_j(t) (4p_j)+O( t), since mj(t)tm_j(t) t and all arms are sampled infinitely often asymptotically. Fixing m1(t)m_1(t) gives mi(t)=log(4p1)log(4pi)m1(t)+o(t).m_i(t)= (4p_1) (4p_i)\,m_1(t)+o(t). Therefore, the total sample count satisfies t+N=∑imi(t)=m1(t)∑ilog(4p1)log(4pi)+o(t).t+N= _im_i(t)=m_1(t) _i (4p_1) (4p_i)+o(t). Finally, the limiting ratio is mi(t)mj(t)=log(4pj)log(4pi)+o(1)⟹limt→∞mi(t)mj(t)=log(4pj)log(4pi)=log(4θj(1−θj))log(4θi(1−θi)). m_i(t)m_j(t)= (4p_j) (4p_i)+o(1) _t→∞ m_i(t)m_j(t)= (4p_j) (4p_i)= \! (4 _j(1- _j) ) \! (4 _i(1- _i) ). (28) ∎ D.2 Convergence of Budget Proportions for Offline Case Let X∼Beta(a,b)X (a,b) with parameters a,b∈N+a,b∈ N_+. Its density is fa,b(x)=1B(a,b)xa−1(1−x)b−1,x∈(0,1),f_a,b(x)= 1B(a,b)x^a-1(1-x)^b-1, x∈(0,1), where the Beta function is B(a,b)=∫01ta−1(1−t)b−1t=(a)(b)(a+b)=(a−1)!(b−1)!(a+b−1)!.B(a,b)= _0^1t^a-1(1-t)^b-1\,dt= (a) (b) (a+b)= (a-1)!(b-1)!(a+b-1)!. We define the tail probability at 1/21/2: Pa,b:=P(X1/2).P_a,b:=P(X 1/2). We first obtain a closed form for P(Xx)P(X x) when a,ba,b are integers: Lemma D.3. For any integer a,b1a,b 1 and any x∈[0,1]x∈[0,1], P(Xx)=∑k=0a−1(a+b−1k)xk(1−x)a+b−1−k.P(X x)= _k=0^a-1 a+b-1kx^k(1-x)^a+b-1-k. Equivalently, the lower tail can be written as P(Xx)=∑k=a+b−1(a+b−1k)xk(1−x)a+b−1−k.P(X x)= _k=a^a+b-1 a+b-1kx^k(1-x)^a+b-1-k. Proof. Define the polynomial Q(x):=∑k=0a−1(a+b−1k)xk(1−x)a+b−1−k,x∈[0,1].Q(x):= _k=0^a-1 a+b-1kx^k(1-x)^a+b-1-k, x∈[0,1]. We will show that Q(x)=P(Xx)Q(x)=P(X x) by verifying that Q has the same derivative as the Beta tail probability and the same boundary value at x=1x=1. (i) Differentiate Q(x)Q(x). For each term xk(1−x)a+b−1−kx^k(1-x)^a+b-1-k we have dx[xk(1−x)a+b−1−k]=kxk−1(1−x)a+b−1−k−(a+b−1−k)xk(1−x)a+b−2−k. ddx [x^k(1-x)^a+b-1-k ]=kx^k-1(1-x)^a+b-1-k-(a+b-1-k)x^k(1-x)^a+b-2-k. Hence, differentiating termwise gives Q′(x) Q (x) =∑k=0a−1(a+b−1k)[kxk−1(1−x)a+b−1−k−(a+b−1−k)xk(1−x)a+b−2−k]. = _k=0^a-1 a+b-1k [kx^k-1(1-x)^a+b-1-k-(a+b-1-k)x^k(1-x)^a+b-2-k ]. The k=0k=0 term in the first part is zero, so re-index the first sum by j=k−1j=k-1: ∑k=1a−1(a+b−1k)kxk−1(1−x)a+b−1−k _k=1^a-1 a+b-1kk\,x^k-1(1-x)^a+b-1-k =∑j=0a−2(a+b−1j+1)(j+1)xj(1−x)a+b−2−j. = _j=0^a-2 a+b-1j+1(j+1)\,x^j(1-x)^a+b-2-j. Also rewrite the second part as ∑k=0a−1(a+b−1k)(a+b−1−k)xk(1−x)a+b−2−k. _k=0^a-1 a+b-1k(a+b-1-k)x^k(1-x)^a+b-2-k. Therefore, the derivative simplifies as Q′(x) Q (x) =∑j=0a−2(a+b−1j+1)(j+1)xj(1−x)a+b−2−j = _j=0^a-2 a+b-1j+1(j+1)x^j(1-x)^a+b-2-j −∑k=0a−1(a+b−1k)(a+b−1−k)xk(1−x)a+b−2−k - _k=0^a-1 a+b-1k(a+b-1-k)x^k(1-x)^a+b-2-k =(a+b−1)∑j=0a−2(a+b−2j)xj(1−x)a+b−2−j−(a+b−1)∑k=0a−1(a+b−2k)xk(1−x)a+b−2−k. =(a+b-1) _j=0^a-2 a+b-2jx^j(1-x)^a+b-2-j-(a+b-1) _k=0^a-1 a+b-2kx^k(1-x)^a+b-2-k. These two sums cancel term-by-term for k=0,1,…,a−2k=0,1,…,a-2, leaving only the k=a−1k=a-1 term from the second sum: Q′(x)=−(a+b−1)(a+b−2a−1)xa−1(1−x)b−1=−(a+b−1)!(a−1)!(b−1)!xa−1(1−x)b−1.Q (x)=-(a+b-1) a+b-2a-1x^a-1(1-x)^b-1=- (a+b-1)!(a-1)!(b-1)!\,x^a-1(1-x)^b-1. (i) Differentiate the Beta tail probability. Define T(x):=P(Xx)=∫x11B(a,b)ta−1(1−t)b−1t.T(x):=P(X x)= _x^1 1B(a,b)t^a-1(1-t)^b-1\,dt. By the fundamental theorem of calculus, T′(x)=−1B(a,b)xa−1(1−x)b−1=−(a+b−1)!(a−1)!(b−1)!xa−1(1−x)b−1,T (x)=- 1B(a,b)x^a-1(1-x)^b-1=- (a+b-1)!(a-1)!(b-1)!\,x^a-1(1-x)^b-1, which matches Q′(x)Q (x). At x=1x=1, T(1)=P(X1)=0.T(1)=P(X 1)=0. The polynomial has the same boundary value: Q(1)=∑k=0a−1(a+b−1k) 1k(1−1)a+b−1−k=0,Q(1)= _k=0^a-1 a+b-1k\,1^k\,(1-1)^a+b-1-k=0, Since Q′(x)=T′(x)Q (x)=T (x) on [0,1][0,1] and Q(1)=T(1)Q(1)=T(1), we conclude Q(x)=T(x)Q(x)=T(x) for all x∈[0,1]x∈[0,1], i.e. P(Xx)=Q(x)=∑k=0a−1(a+b−1k)xk(1−x)a+b−1−k.P(X x)=Q(x)= _k=0^a-1 a+b-1kx^k(1-x)^a+b-1-k. This proves the lemma. ∎ We can then derive the explicit increment of self-consistency of a problem from state (m,n)(m,n) to (m+1,n)(m+1,n) (that is, add one positive answer based on m positive and n negative answer) if the true answer is positive. Lemma D.4. We have :=m,nPm+1,n−Pm,n=12m+n(m+n−1n−1)._m,n:=P_m+1,n-P_m,n= 12^m+n m+n-1n-1. where the shorthand is Pm,n=P(X1/2),X∼Beta(m,n).P_m,n=P(X 1/2),X (m,n). Proof. Apply Lemma D.3 with x=12x= 12: Pa,b=∑k=0a−1(a+b−1k)(12)k(12)a+b−1−k=2−(a+b−1)∑k=0a−1(a+b−1k).P_a,b= _k=0^a-1 a+b-1k ( 12 )^k ( 12 )^a+b-1-k=2^-(a+b-1) _k=0^a-1 a+b-1k. Let m,n∈1,…,Nm,n∈\1,…,N\ :=m,nPm+1,n−Pm,n=P(Beta(m+1,n)1/2)−P(Beta(m,n)1/2)._m,n:=P_m+1,n-P_m,n=P(Beta(m+1,n) 1/2)-P(Beta(m,n) 1/2). We write Pm+1,n=2−(m+n)∑k=0m(m+nk),Pm,n=2−(m+n−1)∑k=0m−1(m+n−1k).P_m+1,n=2^-(m+n) _k=0^m m+nk, P_m,n=2^-(m+n-1) _k=0^m-1 m+n-1k. Let A:=m+nA:=m+n. Then Pm+1,n=2−A∑k=0m(Ak),Pm,n=2−(A−1)∑k=0m−1(A−1k).P_m+1,n=2^-A _k=0^m Ak, P_m,n=2^-(A-1) _k=0^m-1 A-1k. Hence, the increment can be written as =m,n2−A∑k=0m(Ak)−2−(A−1)∑k=0m−1(A−1k)._m,n=2^-A _k=0^m Ak-2^-(A-1) _k=0^m-1 A-1k. Now apply Pascal’s identity (Ak)=(A−1k)+(A−1k−1) Ak= A-1k+ A-1k-1: ∑k=0m(Ak) _k=0^m Ak =∑k=0m(A−1k)+∑k=0m(A−1k−1) = _k=0^m A-1k+ _k=0^m A-1k-1 =(A−1m)+2∑k=0m−1(A−1k). = A-1m+2 _k=0^m-1 A-1k. Therefore, Pascal’s identity yields m,n =2−A((A−1m)+2∑k=0m−1(A−1k))−2−(A−1)∑k=0m−1(A−1k) =2^-A ( A-1m+2 _k=0^m-1 A-1k )-2^-(A-1) _k=0^m-1 A-1k =2−A(A−1m)+(2−A⋅2−2−(A−1))∑k=0m−1(A−1k) =2^-A A-1m+ (2^-A· 2-2^-(A-1) ) _k=0^m-1 A-1k =2−A(A−1m), =2^-A A-1m, Finally, substituting back A=m+nA=m+n yields =m,n2−(m+n)(m+n−1m)=12m+n(m+n−1n−1)._m,n=2^-(m+n) m+n-1m= 12^m+n m+n-1n-1. This is strictly positive because the binomial coefficient is positive. ∎ Remark D.5 (A simple probabilistic interpretation). Lemma D.3 can be rewritten as a Binomial CDF identity: if Y∼Binomial(a+b−1, 1−x)Y (a+b-1,\,1-x), then P(Xx)=P(Yb).P(X x)=P(Y b). In particular, at x=1/2x=1/2, Pa,b=2−(a+b−1)∑k=0a−1(a+b−1k)=P(Binomial(a+b−1,1/2)a−1).P_a,b=2^-(a+b-1) _k=0^a-1 a+b-1k=P (Binomial(a+b-1,1/2) a-1 ). Next, we derive the convergence of sampling proportions and identify the limiting ratios. Proposition D.6. Consider the offline setting with all questions qii=1N\q_i\_i=1^N available upfront and difficulty labels θi _i. Under equal-weight Offline PETS with Beta(1,1)Beta(1,1), the ratio mi(B)/Bm_i(B)/B converges for each i as B→∞B→∞ and obeys mi(B)B∝1p(θi). m_i(B)B 1p( _i). Define the KL divergence to 12 12: KL(q∥12):=qln(2q)+(1−q)ln(2(1−q)),q∈(0,1),KL(q\| 12):=q (2q)+(1-q) (2(1-q) ), q∈(0,1), then p(θ)=KL(θ∥12)p(θ)=KL(θ\| 12). Proof. Let θ∈(0,1)θ∈(0,1) be the success probability. Draw i.i.d. Bernoulli random variables Y1,Y2,…∼i.i.d.Bernoulli(θ),P(Yi=1)=θ,P(Yi=0)=1−θ.Y_1,Y_2,… .i.d. Bernoulli(θ), (Y_i=1)=θ,\ P(Y_i=0)=1-θ. For each sample size T1T 1, define the success and failure counts mT:=∑i=1TYi,nT:=T−mT=∑i=1T(1−Yi).m_T:= _i=1^TY_i, n_T:=T-m_T= _i=1^T(1-Y_i). Clearly, mT+nT=Tm_T+n_T=T and (mT,nT)(m_T,n_T) is the empirical outcome of a binomial experiment with parameter θ, by Strong Law of Large Numbers, mTnT=mT/T1−mT/T⟶θ1−θalmost surely. m_Tn_T= m_T/T1-m_T/T\ \ θ1-θ surely. Then along the binomial sample path (mT,nT)(m_T,n_T), by Lemma D.4 =mT,nT12T(T−1mT)=12P(Binomial(T−1,12)=mT),_m_T,n_T= 12^T T-1m_T= 12P (Binomial(T-1, 12)=m_T ), and moreover, with qT:=mT/(T−1)q_T:=m_T/(T-1), follows from Stirling’s formula applied to the binomial pmf P(Binomial(T−1,12)=mT)P(Binomial(T-1, 12)=m_T) , yielding P(Binomial(T−1,12)=mT)≈12π(T−1)qT(1−qT)exp(−(T−1)KL(qT∥12)).P (Binomial(T-1, 12)=m_T )≈ 1 2π(T-1)q_T(1-q_T) \! (-(T-1)\,KL(q_T\| 12) ). Finally, since qT→θq_T→θ almost surely, the exponent satisfies 1Tlog⟶mT,nT−KL(θ∥12)a.s. 1T _m_T,n_T\ \ -KL(θ\| 12) .s. The remaining part is similar with online case in Section D.1. Which means, since the linear term of mT,nT_m_T,n_T (resp. logR(m;θ) R(m;θ)) converge to −KL(θ∥12)-KL(θ\| 12), then we have similar expression mi(t)KL(θi∥12)=mj(t)KL(θj∥12)+O(logt).m_i(t)KL( _i\| 12)=m_j(t)KL( _j\| 12)+O( t). The rest derivation is similar, hence mi(B)B∝1KL(θi∥12). m_i(B)B 1KL( _i\| 12). ∎ D.3 Discussion of the Asymptotic Behavior for Online vs. Offline Cases As shown in Sections D.2 and D.1, the asymptotic limits induced by the two allocation paradigms are not exactly identical. This discrepancy mainly stems from the different statistical viewpoints adopted in each setting. In the offline case, the difficulty parameters are inferred during the allocation process from progressively collected samples, and thus optimal decision-making requires a Bayesian perspective: one must update the posterior distribution via a Bayesian framework, otherwise (as discussed in [Chen et al., 2013]) the optimality of the resulting allocation cannot be properly assessed. In contrast, the online streaming case assumes the answer distribution parameters are known a priori (or at least can be estimated with sufficient confidence), and therefore employs a frequentist-style update based on empirical frequencies. As a consequence, the two settings lead to slightly different criteria for determining the majority-voting outcome. Nevertheless, we observe that the resulting limiting behaviors are remarkably close in practice; see Figure 2 for an illustration. Appendix E Appendix of Experiment E.1 Implementation Details in PETS-Offline. Confidence-weighted voting. In the confidence-weighted setting, each reasoning trajectory is associated with a scalar confidence score extracted from the model output following Fu et al. [2025b]. Specifically, we compute a tail trace confidence for each generated reasoning trace by averaging the token-level confidence scores over the last 20482048 tokens, and use this value as the weight in majority voting. To mitigate the influence of low-confidence traces, we further apply a confidence-based filtering strategy: only the top 70%70\% most confident traces are retained for voting, while the remaining 30%30\% are assigned zero weight. We refer to this scheme as top-70%70\% confidence-weighted majority voting. The resulting weighted voting rule is used consistently throughout the paper for defining both self-consistency and the population majority label yi∞y_i^∞. Note that we use confidence-weighted majority voting as a proxy for the Bayes-optimal terminal decision rule. Uniform allocation baseline. Under uniform allocation (standard test-time scaling), we fix an average per-question budget b=1,…,64b=1,…,64 and sample exactly b trajectories for every question. When comparing against PETS-Offline, we evaluate Uniform at the per-question budget b⋆b that matches the trace count where PETS-Offline first reaches full self-consistency. E.2 Implementation Details in PETS-Online. In the experiment, PETS-Online is evaluated against PETS-Oracle and Uniform allocation. We now introduce each method in detail. PETS-Online streaming allocation. The PETS-Online assumes not having access to q θ_q and implements a fully deployable online streaming policy. Instead of observing the true difficulty, we use a short warm-up procedure to obtain a coarse difficulty proxy. Specifically, for each question we first sample four responses and compute the sorted option-count vector Cq(4)C_q^(4). Up to permutation of answer labels, Cq(4)C_q^(4) falls into one of five predefined patterns, which deterministically map the question to one of five difficulty grids. Using training questions with large i.i.d. answer pools, we estimate (i) the empirical mass of each grid and (i) a representative two-parameter difficulty curve for each grid by fitting a Gaussian-based approximation to the self-consistency curve. Based on these grid-level statistics, we pre-compute the optimal per-grid budgets using the greedy allocation algorithm 1 as in the oracle setting. At test time, each incoming question undergoes the same four-sample warm-up to determine its grid, after which the corresponding precomputed budget is allocated in a single shot. This procedure respects the streaming and one-shot constraints, requires no access to future questions, and uses only minimal online sampling to approximate question difficulty θ. PETS-Oracle online streaming allocation. In the oracle online streaming experiment, we assume access to the true difficulty vector q θ_q of each arriving question q, i.e., the underlying answer distribution of the model under infinite sampling. This oracle setting is not deployable in practice and is used solely as an upper bound to assess the optimality of the proposed online allocation strategy. Using a held-out training set with large i.i.d. answer pools, we estimate the prior distribution over question difficulties by discretizing the continuous difficulty space into K grids, each represented by a prototype j θ_j with prior mass pjp_j. Based only on the prior statistics (pj,j)(p_j, θ_j), we solve the discretized optimization problem in Equation (9) using the greedy algorithm (Alg. 1) to obtain a fixed budget allocation Bjj=1K\B_j\_j=1^K for all grids. At test time, questions arrive sequentially in a streaming manner. For each incoming question, its true difficulty vector q θ_q is revealed, the corresponding grid index is identified, and the precomputed budget BiB_i is allocated in a single shot. Predictions are obtained by (weighted) majority voting, and we evaluate self-consistency and accuracy under the same protocol as in the offline setting. Uniform online streaming allocation. As a baseline for the online streaming setting, we consider a uniform allocation strategy that assigns the same fixed budget to every question, independent of its difficulty. Given an average per-question budget constraint B¯=Btotal/T B=B_total/T, uniform allocation assigns Bq≡⌊B¯⌋B_q≡ B samples to each arriving question. E.3 Full Experiment Results E.3.1 Full PETS-Offline Results Figure 6: GPQA offline Figure 7: AIME 25 offline Figure 8: AIME 24 offline Figure 9: HMMT offline Figure 10: BRUMO offline Table 7: PETS-Offline results. Results are formatted as mean (variance). Qwen3-4B Qwen3-30B Qwen-Long GPT-20B GPT-120B Dataset Method #tok@con=1↓ con@match↑ acc@match↑ #tok@con=1↓ con@match↑ acc@match↑ #tok@con=1↓ con@match↑ acc@match↑ #tok@con=1↓ con@match↑ acc@match↑ #tok@con=1↓ con@match↑ acc@match↑ GPQA PETS-Offline 2780 (515.55) 0.997 (0.00) 0.697 (0.01) 2607 (547.05) 0.999 (0.00) 0.718 (0.01) 2513 (529.63) 0.998 (0.00) 0.763 (0.01) 3180 (365.21) 0.998 (0.00) 0.757 (0.01) 2580 (493.68) 0.998 (0.00) 0.825 (0.01) PETS-Offline (conf) 3667 (758.10) 0.989 (0.01) 0.703 (0.01) 3687 (657.44) 0.988 (0.01) 0.721 (0.01) 2887 (459.94) 0.992 (0.01) 0.770 (0.01) 3693 (534.94) 0.992 (0.01) 0.762 (0.01) 3540 (788.10) 0.990 (0.01) 0.821 (0.01) Uniform 11013 (1679.85) 0.957 (0.02) 0.689 (0.01) 10367 (2031.53) 0.958 (0.01) 0.715 (0.01) 9973 (2531.31) 0.958 (0.01) 0.765 (0.01) 10853 (2021.22) 0.958 (0.01) 0.751 (0.01) 10393 (2148.61) 0.965 (0.01) 0.815 (0.01) Uniform (conf) 11453 (1382.58) 0.947 (0.01) 0.699 (0.01) 11607 (1154.88) 0.949 (0.01) 0.722 (0.01) 11400 (1353.41) 0.950 (0.02) 0.764 (0.01) 11193 (1460.74) 0.956 (0.01) 0.756 (0.01) 10500 (1988.76) 0.957 (0.02) 0.808 (0.01) AIME25 PETS-Offline 212 (47.23) 1.000 (0.00) 0.833 (0.00) 190 (56.99) 1.000 (0.00) 0.886 (0.02) 152 (60.48) 1.000 (0.00) 0.900 (0.00) 181 (47.59) 1.000 (0.00) 0.900 (0.00) 212 (62.50) 0.997 (0.01) 0.939 (0.01) PETS-Offline (conf) 257 (81.37) 0.979 (0.02) 0.840 (0.02) 223 (58.26) 0.966 (0.03) 0.867 (0.03) 203 (82.13) 0.970 (0.02) 0.904 (0.02) 251 (87.55) 0.970 (0.03) 0.897 (0.01) 211 (65.67) 0.976 (0.02) 0.933 (0.02) Uniform 470 (286.16) 0.937 (0.03) 0.821 (0.02) 545 (462.35) 0.957 (0.03) 0.861 (0.02) 288 (224.17) 0.969 (0.03) 0.893 (0.02) 410 (244.78) 0.953 (0.03) 0.902 (0.02) 681 (353.75) 0.947 (0.03) 0.913 (0.03) Uniform (conf) 610 (395.44) 0.913 (0.05) 0.833 (0.03) 763 (508.98) 0.928 (0.04) 0.856 (0.03) 752 (564.94) 0.942 (0.03) 0.889 (0.02) 618 (342.65) 0.937 (0.04) 0.890 (0.03) 911 (542.15) 0.943 (0.03) 0.919 (0.03) AIME24 PETS-Offline 259 (90.68) 1.000 (0.00) 0.631 (0.02) 135 (31.27) 1.000 (0.00) 0.700 (0.00) 83 (45.04) 1.000 (0.00) 0.700 (0.00) 200 (70.17) 1.000 (0.00) 0.733 (0.00) 184 (81.01) 1.000 (0.00) 0.744 (0.02) PETS-Offline (conf) 369 (122.85) 0.961 (0.03) 0.660 (0.03) 120 (35.23) 0.996 (0.01) 0.699 (0.01) 91 (53.13) 0.989 (0.02) 0.699 (0.01) 232 (72.18) 0.969 (0.02) 0.726 (0.01) 218 (93.86) 0.986 (0.02) 0.737 (0.02) Uniform 861 (531.96) 0.938 (0.03) 0.630 (0.03) 202 (129.44) 0.977 (0.02) 0.696 (0.01) 96 (62.23) 0.990 (0.02) 0.699 (0.01) 665 (554.41) 0.962 (0.02) 0.719 (0.02) 448 (483.41) 0.967 (0.03) 0.737 (0.03) Uniform (conf) 942 (516.00) 0.922 (0.04) 0.634 (0.03) 179 (115.38) 0.973 (0.03) 0.686 (0.02) 115 (78.82) 0.978 (0.03) 0.697 (0.01) 1206 (676.46) 0.941 (0.02) 0.708 (0.02) 535 (501.94) 0.948 (0.02) 0.719 (0.03) HMMT PETS-Offline 464 (136.40) 1.000 (0.00) 0.516 (0.02) 381 (79.24) 0.999 (0.01) 0.647 (0.02) 363 (97.88) 0.996 (0.01) 0.717 (0.02) 329 (129.81) 1.000 (0.00) 0.833 (0.00) 329 (129.81) 1.000 (0.00) 0.833 (0.00) PETS-Offline (conf) 579 (198.24) 0.963 (0.03) 0.520 (0.03) 361 (103.47) 0.973 (0.03) 0.652 (0.02) 371 (126.91) 0.971 (0.03) 0.732 (0.02) 324 (118.80) 0.989 (0.02) 0.831 (0.01) 324 (118.80) 0.989 (0.02) 0.831 (0.01) Uniform 1133 (489.01) 0.904 (0.04) 0.500 (0.03) 1219 (483.32) 0.913 (0.03) 0.647 (0.03) 1227 (463.11) 0.911 (0.04) 0.688 (0.03) 916 (483.33) 0.938 (0.03) 0.836 (0.02) 916 (483.33) 0.938 (0.03) 0.836 (0.02) Uniform (conf) 1383 (472.53) 0.872 (0.07) 0.506 (0.04) 1089 (473.89) 0.913 (0.05) 0.651 (0.03) 1165 (419.04) 0.901 (0.03) 0.717 (0.03) 902 (464.29) 0.930 (0.04) 0.826 (0.03) 902 (464.29) 0.930 (0.04) 0.826 (0.03) BRUMO PETS-Offline 280 (74.88) 1.000 (0.00) 0.754 (0.02) 148 (28.33) 1.000 (0.00) 0.867 (0.00) 149 (51.95) 1.000 (0.00) 0.867 (0.00) 253 (75.44) 1.000 (0.00) 0.921 (0.02) 253 (75.44) 1.000 (0.00) 0.921 (0.02) PETS-Offline (conf) 292 (109.71) 0.978 (0.03) 0.773 (0.03) 162 (53.20) 0.981 (0.03) 0.861 (0.02) 150 (77.59) 0.981 (0.02) 0.878 (0.02) 217 (77.06) 0.984 (0.02) 0.924 (0.02) 217 (77.06) 0.984 (0.02) 0.924 (0.02) Uniform 826 (481.21) 0.936 (0.03) 0.732 (0.03) 237 (87.14) 0.958 (0.03) 0.837 (0.03) 320 (310.71) 0.974 (0.01) 0.873 (0.02) 776 (494.32) 0.943 (0.02) 0.901 (0.03) 776 (494.32) 0.943 (0.02) 0.901 (0.03) Uniform (conf) 589 (309.52) 0.941 (0.04) 0.757 (0.03) 310 (256.06) 0.949 (0.03) 0.836 (0.03) 421 (463.32) 0.970 (0.02) 0.872 (0.02) 574 (430.99) 0.952 (0.03) 0.907 (0.03) 574 (430.99) 0.952 (0.03) 0.907 (0.03) E.3.2 Full PETS-Online Results Besides the full results, here we also presents the comparison with the oracle case of the online setting, which assumes access to the latent parameter θ; in the realistic online setting, θ is unavailable and must be learned from a training dataset. Figure 11: GPQA online Figure 12: AIME 25 online Figure 13: AIME 24 online Figure 14: HMMT online Figure 15: BRUMO online Table 8: PETS-Online results. Results are formatted as mean (variance). Oracle case of the online setting assumes access to the latent parameter θ; in the realistic online setting, θ is unavailable and must be learned from a training dataset. Qwen3-4B Qwen3-30B Qwen-Long GPT-20B GPT-120B Dataset Method #tok@con=1↓ con@match↑ acc@match↑ #tok@con=1↓ con@match↑ acc@match↑ #tok@con=1↓ con@match↑ acc@match↑ #tok@con=1↓ con@match↑ acc@match↑ #tok@con=1↓ con@match↑ acc@match↑ GPQA PETS-Online 4662 (1771.56) 1.000 (0.00) 0.688 (0.01) 3826 (1695.09) 1.000 (0.00) 0.716 (0.01) 4852 (2352.11) 1.000 (0.00) 0.763 (0.01) 6826 (1663.76) 1.000 (0.00) 0.759 (0.01) 4172 (1267.37) 1.000 (0.00) 0.824 (0.01) PETS-Online (conf) 4888 (2048.79) 0.995 (0.01) 0.696 (0.01) 4357 (2223.79) 0.993 (0.01) 0.718 (0.01) 4146 (1741.11) 0.995 (0.01) 0.769 (0.01) 7269 (1543.73) 0.991 (0.01) 0.761 (0.01) 5094 (1403.07) 0.990 (0.01) 0.816 (0.01) PETS-Oracle 3008 (299.30) 0.998 (0.00) 0.687 (0.01) 2878 (441.03) 0.998 (0.00) 0.715 (0.01) 3127 (394.72) 0.995 (0.01) 0.763 (0.01) 4458 (715.04) 0.999 (0.00) 0.759 (0.01) 2970 (526.74) 0.998 (0.00) 0.823 (0.01) PETS-Oracle (conf) 3174 (334.03) 0.995 (0.01) 0.697 (0.01) 3061 (548.13) 0.995 (0.01) 0.719 (0.01) 3187 (284.75) 0.995 (0.01) 0.769 (0.01) 5242 (673.92) 0.996 (0.01) 0.761 (0.01) 3289 (276.80) 0.995 (0.01) 0.815 (0.01) Uniform 9520 (1258.23) 0.969 (0.01) 0.681 (0.01) 8456 (2024.35) 0.974 (0.02) 0.712 (0.01) 9195 (1768.03) 0.973 (0.02) 0.760 (0.01) 9699 (1311.70) 0.983 (0.01) 0.761 (0.01) 8109 (2676.36) 0.976 (0.01) 0.818 (0.01) Uniform (conf) 9856 (1356.49) 0.967 (0.02) 0.694 (0.01) 9257 (1947.92) 0.964 (0.01) 0.720 (0.01) 9526 (1249.55) 0.971 (0.01) 0.764 (0.01) 9895 (1201.26) 0.978 (0.01) 0.763 (0.01) 9593 (1686.56) 0.968 (0.01) 0.814 (0.01) AIME25 PETS-Online 194 (111.95) 1.000 (0.00) 0.750 (0.00) 504 (493.65) 1.000 (0.00) 0.835 (0.02) 218 (246.36) 1.000 (0.00) 0.850 (0.00) 195 (221.00) 1.000 (0.00) 0.850 (0.00) 454 (464.19) 1.000 (0.00) 0.917 (0.02) PETS-Online (conf) 287 (219.04) 0.947 (0.04) 0.763 (0.03) 535 (450.59) 0.970 (0.04) 0.825 (0.03) 681 (492.92) 0.955 (0.03) 0.857 (0.03) 330 (296.69) 0.960 (0.04) 0.848 (0.02) 493 (490.02) 0.983 (0.02) 0.923 (0.03) PETS-Oracle 168 (89.50) 0.970 (0.03) 0.750 (0.01) 201 (101.39) 0.978 (0.04) 0.823 (0.04) 126 (39.82) 0.983 (0.03) 0.857 (0.02) 134 (65.99) 0.982 (0.02) 0.857 (0.02) 175 (80.60) 0.982 (0.03) 0.908 (0.03) PETS-Oracle (conf) 223 (102.49) 0.932 (0.05) 0.762 (0.03) 226 (89.60) 0.952 (0.05) 0.817 (0.03) 191 (65.17) 0.950 (0.04) 0.855 (0.03) 178 (67.21) 0.958 (0.03) 0.847 (0.02) 192 (86.07) 0.963 (0.04) 0.912 (0.04) Uniform 290 (262.13) 0.948 (0.03) 0.748 (0.02) 415 (319.94) 0.947 (0.06) 0.810 (0.04) 229 (151.20) 0.953 (0.04) 0.847 (0.03) 221 (190.98) 0.955 (0.04) 0.860 (0.02) 416 (338.82) 0.952 (0.05) 0.892 (0.04) Uniform (conf) 452 (311.86) 0.923 (0.05) 0.763 (0.03) 486 (262.88) 0.935 (0.06) 0.812 (0.03) 495 (301.53) 0.925 (0.04) 0.835 (0.03) 349 (222.46) 0.930 (0.03) 0.852 (0.03) 459 (332.33) 0.943 (0.04) 0.898 (0.04) AIME24 PETS-Online 170 (82.05) 1.000 (0.00) 0.562 (0.03) 81 (3.82) 1.000 (0.00) 0.650 (0.00) 83 (8.68) 1.000 (0.00) 0.650 (0.00) 130 (96.34) 1.000 (0.00) 0.700 (0.00) 107 (37.18) 1.000 (0.00) 0.698 (0.01) PETS-Online (conf) 185 (103.12) 0.957 (0.04) 0.600 (0.04) 81 (3.52) 0.998 (0.01) 0.648 (0.01) 86 (14.12) 0.988 (0.02) 0.648 (0.01) 104 (40.90) 0.988 (0.02) 0.688 (0.02) 92 (19.26) 0.997 (0.01) 0.695 (0.02) PETS-Oracle 160 (60.49) 0.992 (0.02) 0.562 (0.03) 82 (5.50) 1.000 (0.00) 0.650 (0.00) 82 (5.38) 1.000 (0.00) 0.650 (0.00) 103 (27.69) 1.000 (0.00) 0.700 (0.00) 103 (28.26) 0.998 (0.01) 0.697 (0.01) PETS-Oracle (conf) 176 (93.59) 0.953 (0.04) 0.603 (0.05) 82 (5.16) 0.998 (0.01) 0.648 (0.01) 87 (14.00) 0.990 (0.02) 0.648 (0.01) 94 (17.47) 0.992 (0.02) 0.692 (0.02) 95 (20.72) 0.995 (0.02) 0.693 (0.02) Uniform 393 (269.74) 0.935 (0.04) 0.568 (0.04) 83 (10.61) 0.997 (0.01) 0.647 (0.01) 82 (6.10) 1.000 (0.00) 0.650 (0.00) 237 (294.79) 0.977 (0.03) 0.677 (0.03) 205 (180.65) 0.972 (0.03) 0.670 (0.02) Uniform (conf) 405 (355.95) 0.942 (0.05) 0.588 (0.05) 83 (8.68) 0.997 (0.01) 0.647 (0.01) 101 (64.22) 0.988 (0.02) 0.648 (0.01) 171 (184.40) 0.980 (0.02) 0.680 (0.02) 144 (120.85) 0.978 (0.03) 0.677 (0.03) HMMT PETS-Online 531 (199.60) 1.000 (0.00) 0.485 (0.02) 825 (389.51) 1.000 (0.00) 0.562 (0.03) 872 (397.80) 1.000 (0.00) 0.670 (0.03) 248 (129.24) 1.000 (0.00) 0.850 (0.00) 221 (146.53) 1.000 (0.00) 0.850 (0.00) PETS-Online (conf) 615 (182.54) 0.933 (0.06) 0.468 (0.02) 761 (330.68) 0.952 (0.05) 0.568 (0.03) 1061 (362.50) 0.950 (0.06) 0.688 (0.04) 233 (96.81) 0.968 (0.05) 0.855 (0.04) 263 (134.09) 0.955 (0.05) 0.865 (0.03) PETS-Oracle 498 (169.60) 0.937 (0.03) 0.468 (0.02) 513 (198.68) 0.973 (0.05) 0.558 (0.03) 803 (331.95) 0.960 (0.06) 0.665 (0.04) 215 (101.26) 0.982 (0.03) 0.838 (0.03) 166 (71.99) 0.985 (0.03) 0.850 (0.02) PETS-Oracle (conf) 497 (190.79) 0.915 (0.06) 0.470 (0.03) 453 (176.85) 0.923 (0.06) 0.565 (0.03) 690 (364.53) 0.927 (0.06) 0.675 (0.04) 205 (78.56) 0.955 (0.05) 0.847 (0.03) 199 (72.56) 0.950 (0.04) 0.867 (0.03) Uniform 792 (323.71) 0.893 (0.05) 0.462 (0.03) 813 (345.51) 0.925 (0.08) 0.562 (0.04) 803 (331.81) 0.962 (0.06) 0.667 (0.04) 475 (311.66) 0.920 (0.04) 0.833 (0.06) 309 (181.08) 0.947 (0.04) 0.848 (0.03) Uniform (conf) 931 (315.65) 0.885 (0.07) 0.457 (0.04) 786 (278.13) 0.922 (0.11) 0.567 (0.04) 959 (304.29) 0.947 (0.07) 0.678 (0.04) 409 (219.94) 0.920 (0.06) 0.832 (0.05) 458 (280.36) 0.913 (0.06) 0.850 (0.04) BRUMO PETS-Online 601 (478.46) 1.000 (0.00) 0.632 (0.03) 125 (38.38) 1.000 (0.00) 0.800 (0.00) 130 (89.34) 1.000 (0.00) 0.802 (0.01) 213 (202.63) 1.000 (0.00) 0.950 (0.00) 383 (241.37) 1.000 (0.00) 0.888 (0.02) PETS-Online (conf) 494 (337.36) 0.968 (0.06) 0.647 (0.03) 121 (30.34) 0.985 (0.03) 0.795 (0.02) 138 (114.69) 0.985 (0.02) 0.815 (0.02) 162 (59.26) 0.993 (0.02) 0.947 (0.01) 241 (142.94) 0.988 (0.02) 0.897 (0.01) PETS-Oracle 345 (201.30) 0.975 (0.03) 0.628 (0.04) 118 (34.74) 0.980 (0.02) 0.792 (0.02) 112 (33.36) 0.993 (0.02) 0.805 (0.02) 141 (53.84) 0.977 (0.03) 0.935 (0.02) 277 (126.84) 0.948 (0.04) 0.868 (0.03) PETS-Oracle (conf) 312 (117.58) 0.948 (0.07) 0.645 (0.03) 115 (28.09) 0.972 (0.04) 0.787 (0.02) 109 (35.67) 0.982 (0.02) 0.812 (0.02) 128 (30.64) 0.965 (0.04) 0.932 (0.03) 208 (97.93) 0.963 (0.04) 0.880 (0.03) Uniform 613 (415.94) 0.940 (0.06) 0.615 (0.04) 172 (107.33) 0.963 (0.04) 0.777 (0.04) 167 (111.72) 0.970 (0.03) 0.807 (0.02) 245 (202.96) 0.948 (0.05) 0.917 (0.04) 521 (344.31) 0.915 (0.03) 0.863 (0.03) Uniform (conf) 519 (270.25) 0.925 (0.08) 0.655 (0.05) 159 (85.26) 0.955 (0.04) 0.777 (0.03) 189 (131.80) 0.975 (0.03) 0.813 (0.02) 184 (98.60) 0.948 (0.04) 0.917 (0.04) 353 (260.85) 0.942 (0.04) 0.872 (0.03) Figure 16: Summarization of the detailed offline comparison across datasets and models. Pass@1 denotes single-pass prediction accuracy (a lower-bound reference), while MV@128 denotes majority voting over 128 samples, used as a finite proxy of infinite-budget performance (an upper-bound reference). Figure 17: Summarization of the detailed online comparison across datasets and models. Pass@1 denotes single-pass prediction accuracy (a lower-bound reference), while MV@128 denotes majority voting over 128 samples, used as a finite proxy of infinite-budget performance (an upper-bound reference).