acceptodds
Under review as a conference paper at ICLR 2027

SANE: Selector-Agnostic Nonparametric Early Stopping for Efficient Repeated Sampling

Abstract

Repeated sampling improves the accuracy of large language models by generating multiple outputs from the model and selecting one of them as the final answer. Using a fixed sampling budget wastes computation on the easier tasks that require fewer samples. Early-stopping algorithms address this issue by stopping the sampling process once they detect additional samples are unlikely to improve the final answer. Existing algorithms are limited to the single selection mechanism they are designed for, such as self-consistency (SC) or best-of- (BoN), and some require modeling the underlying distribution of rewards or answers, which may be challenging. We introduce SANE, a practical early-stopping algorithm for repeated sampling that is nonparametric and compatible with any black-box selector that satisfies a union-consistency property: if the selector's choice is the same for two disjoint sets of samples, its choice remains the same over their union. This is satisfied by the commonly used SC, BoN, and weighted BoN algorithms. After sampling outputs, we lower bound the probability that the selector's choice remains the same with additional samples. SANE bounds this probability by partitioning the samples into disjoint blocks and estimating the selector's choice for each of them through subsampling. We empirically show that SANE provides a superior cost-accuracy trade-off across a variety of tasks, models, reward models, and selector algorithms and can match the accuracy of fixed-budget sampling with 42%-73% fewer samples.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM Test-time Scaling, Repeated Sampling, Efficiency

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_WDN2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes SANE, an early-stopping rule for repeated sampling that applies to any selector satisfying union consistency: if the selector picks the same answer on two disjoint sample sets, it picks that answer on their union. After n samples, SANE lower-bounds the probability that the selection survives M more samples, by partitioning samples into blocks and estimating through subsampling how often each block alone yields the current answer. Experiments on five benchmarks with self-consistency (SC), best-of-N (BoN) and weighted BoN report 42–73% fewer samples at the accuracy of a fixed budget of 16.

Critical strengths
  1. A simple, general mechanism. One stopping rule covers SC, BoN and weighted BoN using only black-box selector calls and subsampling, with no model of answer or reward distributions. This matters because existing rules are each tied to one selector.
  2. A robust default. A single configuration (N=32, ρ=0.5, M=8, α=0.5) lies above the fixed-budget curve on all five benchmarks and all three selectors (Figures 4, 9–12). This evidence is the least affected by the tuning concerns below, and it is why I do not recommend clear rejection.
Critical weaknesses

The evaluation does not support the headline savings. Figure 3 is tuned and reported on the whole data (Appendix A), with 5,520 settings per setup for SANE against 161–1,311 for the baselines (Table 2) and no confidence intervals. On SC the gap is roughly half a point. Table 1 reports cost at “equal accuracy” but not the test accuracy reached, and the 0.1 margin is far below what 250 held-out questions can resolve. All savings of about 70% or more come from CSQA and GSM8K, where the fixed-budget curve moves only about 0.5 to 2.5 points between 4 and 16 samples. The BoN and weighted-BoN baselines are weak. The SC baselines keep a stopping rule that ignores rewards. BEACON and Pandora Box need more samples than the fixed budget on nine of ten rows, which the paper attributes to these methods being tested on alignment tasks. The BEACON paper, however, reports large savings on math reasoning with a Skywork reward model, under a looser matching criterion.

The claims of generality and guarantees are not substantiated. Only the three selectors known to satisfy union consistency are evaluated. None of the selectors that motivate the paper (regularised BoN, ranking-based, learned aggregators) is shown to satisfy it. The abstract and introduction promise guarantees, but there is no theorem or proof, only an informal sentence in Section 6. For the thresholds used (ρ from 0.4 to 0.9), the implied bound on accuracy gain is between 0.1 and 0.6. It is unclear that the bound drives the gains. At the default configuration the prefix in Section 5.1 is always empty, and for n from 4 to 8 the blocks have size 2, where SC depends on an unspecified tie-breaking rule. Figure 2 (left) shows the bound is far below the true stability probability for a large share of trials.

Questions for authors

What test accuracies do the Table 1 configurations reach, with confidence intervals? Does the 0.1 margin mean above or within the fixed-budget accuracy? What tie-breaking rule is used for SC and BoN, and does union consistency hold under it? Are the cost grids for BEACON and Pandora Box scaled to each reward model’s range, and can your implementation reproduce a result from the BEACON paper? How does SANE relate to the bootstrapped BoN distribution of Rakhsha et al. (2025)?

Additional evidence that would change my assessment (within the scope of the current experiments, not future work): Figure 3 with parameters tuned on held-out questions and comparable grid sizes. Results for one selector other than SC, BoN and weighted BoN, or a statement of which motivating selectors satisfy union consistency. An ablation of the two partitioning schemes against a simple threshold on the subsample agreement rate.

3 comments
AuthorsOpenReview ↗

Rebuttal - Part 1

We thank the reviewer for their review. Their feedback has helped us improve the manuscript and in the following we would like to address their concerns.

Additional evidence that would change my assessment (within the scope of the current experiments, not future work): Figure 3 with parameters tuned on held-out questions and comparable grid sizes. Results for one selector other than SC, BoN and weighted BoN, or a statement of which motivating selectors satisfy union consistency. An ablation of the two partitioning schemes against a simple threshold on the subsample agreement rate.

We are happy to provide these results.

Request 1) Pareto curve figure with held-out tuning and comparable grid size on MMLU-Pro-Math: The figure is in the top row of Figure 9 in the revision.

For each algorithm, we first find the parameter configs that are on the pareto curve based on the validation set. These parameter choices are then plotted according to their test budget and accuracy. We have increased the grid size of parameter sweep for some of the baselines and added a variant of SANE with a much smaller grid. The grid size of SANE's limited variant is now smaller than that of all other baselines (Table 5). After these modifications, our original results still qualitatively hold.

Request 2) Results for another selector, or review of union-consistency of the motivating selectors: The review of selectors is given in Appendix A and summarized in Table 2. We also provide the results for Length-regularize BoN in Table 7.

We have added a full discussion on the 14 selectors mentioned in the introduction, as well as a new family of selectors raised by reviewer aTiA. Beyond BoN, SC, and WBoN that are the most popular selectors and are the focus of the paper, KL-regularized BoN and Length-regularized BoN are also UC. Wasserstein-regularized BoN approximates a UC selector: replacing the empirical output distribution of the pool in its definition with the true output distribution pp makes it UC. We also show filtering outputs using any pool-independent, prompt-dependent, binary verifier (e.g., safety, formatting, length constraints, or reward/confidence thresholds) followed by any UC selector remains UC.

One of our motivating examples was length-regularized BoN (RBoN_L). In the evaluations of five regularized BoN varients by Ichihara et. al. (2025, Table 2), RBoN_L performed the best in 8 out of 15 setups. With RBoN_L selector, SANE with limited grid beats all the baselines in 4 of 5 benchmarks. On average over setups, uses 5% fewer samples than bootstrapping and 40% fewer than the rest. Table 7 in revision reports the numbers.

Request 3) An ablation of the two partitioning schemes against a simple threshold on the subsample agreement rate: The ablation result is provided below. We have also added an in-depth analysis of the two partitioning schemes in terms of their recall and precision to detect stability (Section C.1).

For the ablation of two partitioning schemes, we fix N=512,M=8,α=0.5N = 512, M = 8, \alpha = 0.5 to ensure non-empty prefix and PP partitioning happens. We compare original SANE against only using future-sample (FS) partitioning and prefix-pool (PP) partitioning variants, as well a simple subsampling baseline. This baseline uses the same mn=nαm_n=n^\alpha as SANE. We tune threshold ρ\rho for all four algorithms over the same 14 values from 0.1 to 0.99 to meet the accuracy of Base@N minus 0.5 pp margin on the validation set. The following table reports the mean budget and test accuracy of each algorithm with the tuned ρ\rho. SANE uses 48% fewer samples compared to only using future-sample (FS) partitioning and 78% fewer samples than simple subsampling. PP-only fails to meet the validation accuracy constraint for SC and WBoN.

Test mean samples/question (test accuracy %). N/A: no rho reached the floor.

SelectorSANEOnly FSOnly PPSubNo stopping (N=512)
SC30.45 (61.1)70.24 (61.2)N/A107.83 (61.3)512 (61.7)
BoN6.38 (61.2)6.38 (61.2)34.94 (65.1)21.75 (61.3)512 (62.1)
WBoN8.16 (61.1)9.61 (61.0)N/A76.14 (62.2)512 (63.2)
Average budget15.0028.74N/A68.57512

In the revision, we include a comparison of the two partitioning schemes in Section C.1 with Figure 5,6 that shows choosing FS in small nn gives us high precision. In large n, PP has a better recall and both have acceptable precision. We explain this by the estimation error and true bound's gap for two schemes.

AuthorsOpenReview ↗

Rebuttal - Part 2

In the following we address the detailed concerns of the reviewer:

Figure 3 is tuned and reported on the whole data (Appendix A), with 5,520 settings per setup for SANE against 161–1,311 for the baselines (Table 2)

Please refer to our response to Request 1 above, these concerns are addressed in Figure 7 of the revision. We have added the limited-grid variant of SANE in Table 1 as well, where it still beats all baselines on average over setups.

no confidence intervals. On SC the gap is roughly half a point. Table 1 reports cost at “equal accuracy” but not the test accuracy reached, and the 0.1 margin is far below what 250 held-out questions can resolve.

[Question:] Does the 0.1 margin mean above or within the fixed-budget accuracy?

Q: What test accuracies do the Table 1 configurations reach, with confidence intervals?

The 0.1 margin is part of the selection rule: a setting qualifies if its validation accuracy is at least the no-stopping validation accuracy plus 0.1 points (above, not within). It defines the accuracy target used for tuning, applied identically to every method. It is not a claim that accuracy is resolved to 0.1 points on test.

The test accuracies of the Table 1 configurations are now reported in Table 5 of the revision. Across all methods and setups, they are within −0.9 to +0.6 points of no stopping. Each question's accuracy is estimated from 36 outcomes for BoN and WBoN (3 LLMs × 3 reward models × at least 4 trials) and 12 for SC, which reduces the noise from sampling. Treating questions as the independent units, the standard error of each test accuracy is 2.1–2.9 points. For the purpose of comparisons, the 95% intervals of the paired difference between the methods' accuracy and the base accuracy have median half-width of 0.4.

All savings of about 70% or more come from CSQA and GSM8K, where the fixed-budget curve moves only about 0.5 to 2.5 points between 4 and 16 samples.

This is beyond our control and the behavior of repeated sampling on these datasets.

The BoN and weighted-BoN baselines are weak. The SC baselines keep a stopping rule that ignores rewards. BEACON and Pandora Box need more samples than the fixed budget on nine of ten rows, which the paper attributes to these methods being tested on alignment tasks. The BEACON paper, however, reports large savings on math reasoning with a Skywork reward model, under a looser matching criterion.

The limitations of the baselines further strengthen the motivation of our work. Our comment on BEACON and PBox mostly refers to their considered framework. In their framework, the goal of BoN is to find outputs with the highest possible rewards. In contrast, our goal is to find a correct output, regardless of its reward score. This difference impacts the stopping decision as well.

Only the three selectors known to satisfy union consistency are evaluated. None of the selectors that motivate the paper (regularised BoN, ranking-based, learned aggregators) is shown to satisfy it.

Please see our response to Requirement 2 above.

The abstract and introduction promise guarantees, but there is no theorem or proof, only an informal sentence in Section 6.

The proof of the claim simply follows from L∗L^* being a high probability lower bound for the stability problem and the union bound over all the iterations. We further clarified this claim and proof in the revision.

For the thresholds used (ρ from 0.4 to 0.9), the implied bound on accuracy gain is between 0.1 and 0.6. It is unclear that the bound drives the gains.

These values give the worst-case accuracy gain of continuing sampling. The real drop in accuracy is expectedly much lower. Low thresholds still adjust the sensitivity of the stopping rule, even if their guaranteed bound on the accuracy gain is too high.

At the default configuration the prefix in Section 5.1 is always empty

Please see our response to Requirement 3 for results on non-empty prefixes.

AuthorsOpenReview ↗

Rebuttal - Part 3

What tie-breaking rule is used for SC and BoN, and does union consistency hold under it?

for n from 4 to 8 the blocks have size 2, where SC depends on an unspecified tie-breaking rule.

We use pseudo-random hash of the outputs to break ties in all three selectors. We clarified this in the revision. Yes, the selectors remain union consistent with any fixed tie-breaking rule. The hashes of future samples in our estimation procedures are randomly generated.

Figure 2 (left) shows the bound is far below the true stability probability for a large share of trials.

This is harmless considering our conservative stopping approach, since it only means we may fail to detect stability and continue sampling.

Are the cost grids for BEACON and Pandora Box scaled to each reward model’s range, and can your implementation reproduce a result from the BEACON paper?

For BEACON, yes. We z-score each reward model's rewards over each benchmark-LLM dataset, so c is in units of that model's standard deviation. For PBox, the cost is priced in utility, which lies in [0, 1] for every reward model, so it needs no rescaling. As in the original paper, the rewards are used raw, since the method reads their differences as log-odds. Reproducing BEACON results required high computational cost of generating LLM outputs on their benchmarks, which was not feasible for us. We tried our best to correctly implement the algorithms.

How does SANE relate to the bootstrapped BoN distribution of Rakhsha et al. (2025)?

Our estimation of q^\hat q with subsampling is closely related to their m-out-of-n bootstrapping. Subsampling draws samples without replacement but bootstrapping draws with replacement. Asymptotically and with some additional mild assumptions, bootstrapping estimates the same quantity (See "Resampling Fewer Than n Observations: Gains, Losses, and Remedies for Losses" by Bickel et. al.).

Reviewer_CeNDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes SANE, an early-stopping method for repeated sampling with union-consistent selectors, including self-consistency, best-of-N, and weighted best-of-N. It uses subsampling to estimate a lower bound on the probability that the selected answer remains unchanged after M additional samples. A confidence-corrected version provides a theoretical guarantee, while the experiments use an uncorrected version. Evaluation uses precomputed generations across five benchmarks, three LLMs, and three reward models. The authors report 42–74% fewer samples relative to a fixed budget of 16.

Critical strengths
  1. Union consistency provides a useful common formulation for stopping across different selectors. The partitioning argument explains how observed samples can be reused to estimate stability without fitting a separate reward distribution.

  2. The evaluation covers several selectors, models, and benchmarks, and includes simple persistence and agreement heuristics. This breadth is useful for assessing whether a common stopping rule offers practical advantages.

Critical weaknesses
  1. The practical statistic can be confidently wrong. Consider BoN with 10% higher-reward correct samples and 90% identical wrong answers. Four wrong samples yield estimated stability 1, while true stability for M=8 is only 0.9^8≈0.43. This event occurs 66% of the time. The practical method drops the confidence correction, and Figure 2’s fixed-n histogram does not establish reliability at actual stopping times.

  2. The equal-accuracy savings are not established on held-out data. Accuracy matching is imposed on validation questions, but Table 1 reports only test budget savings, without test accuracy differences. The Pareto curves are tuned and evaluated on the same questions with 5,520 configurations for SANE. I cannot tell whether the reported savings preserve accuracy after parameter selection.

Questions for authors

For the practical algorithm, how often does the true stability probability fall below ρ at the actual stopping time, measured using independent future samples?

2 comments
AuthorsOpenReview ↗

Rebuttal - Part 1

We thank the reviewer for their review and feedback. We address each point below.

The practical statistic can be confidently wrong. Consider BoN with 10% higher-reward correct samples and 90% identical wrong answers. Four wrong samples yield estimated stability 1, while true stability for M=8 is only 0.9^8≈0.43. This event occurs 66% of the time.

The reviewer's example is correct. However, the mentioned failure is not specific to SANE, and any early-stopping rule faces a challenge on this prompt. We highlight that this is a fundamental challenge of the early-stopping problem. A stopping rule has to either accept a significant chance of premature stopping in such prompts, or act very conservatively and continue sampling even after observing many agreeing outputs, which reduces budget saving on other prompts.

For any stability threshold ρ\rho and δ>0\delta > 0, any stopping rule falls into one of two categories:

  1. For some prompt similar to the example, it stops prematurely (when the final answer is not yet stable) with probability greater than δ\delta.
  2. It does not stop sampling even when all the first n<Mlog⁡(1/δ)/log⁡(1/ρ)n < M \log(1/\delta) / \log(1/\rho) outputs give the same final answer.

To see this, modify the reviewer's example such that the more probable sample has probability δ1/n<ε<ρ1/M\delta^{1/n} < \varepsilon < \rho^{1/M} instead of 90%. Then, the first nn outputs all pick the more probable answer with probability greater than δ\delta, but the answer is still not stable. As an example, set δ=0.05,ρ=0.9,M=8\delta=0.05, \rho=0.9, M=8 which gives ε\varepsilon = 98.69%. If a rule wants to have less than 5% chance of premature stopping for this prompt, it should not stop even if the first 227 samples pick the same final answer. This is the same conservativeness the theoretical variant of SANE exhibits.

Now consider a second prompt similar to the first, but the more probable answer (probability ε\varepsilon=98.69%) has the higher reward instead of lower. With probability of about 95%, the first four outputs all pick the more probable answer, and in this case, the answer is actually stable. Assuming N=32N=32, the conservative rule does not save the cost of 28 future samples it could save by stopping.

As we see, avoiding premature stopping on the first prompt, prevents us from saving significant sampling costs on the second prompt. A method that aims for strictly high precision on all prompts, including difficult ones such as this one, misses the gains it could have on easier prompts. Since our objective is the aggregate performance on the whole dataset, our decision depends on which type of prompts is more frequent. Intuitively speaking, we expect the second type of prompt, where the preferred answer of the generative model and reward model agree, to be more frequent as this is the case on the "easy" prompts. In our response to the reviewer's next concern we provide the concrete evidence that abandoning the theoretical guarantee on all prompts becomes problematic only in rare occasions.

The practical method drops the confidence correction, and Figure 2’s fixed-n histogram does not establish reliability at actual stopping times.

For the practical algorithm, how often does the true stability probability fall below ρ at the actual stopping time, measured using independent future samples?

In Table 4 of our revision, we have added the false-positive rate at SANE's stopping times in each setup with the default parameter choices. Averaged over the five benchmarks, the false-positive rate is 0.67% for SC, 4.64% for BoN, and 1.56% for WBoN.

The equal-accuracy savings are not established on held-out data. Accuracy matching is imposed on validation questions, but Table 1 reports only test budget savings, without test accuracy differences. [...] I cannot tell whether the reported savings preserve accuracy after parameter selection.

This was a mistake in our initial submission. The test accuracy of the stopping rules with the parameter selected for Table 1 is now provided in Table 5 of revision. The table shows that in all setups, the test accuracies of all methods are within 0.9pp of each other.

AuthorsOpenReview ↗

Rebuttal - Part 2

The Pareto curves are tuned and evaluated on the same questions with 5,520 configurations for SANE.

We make two adjustments to address the reviewer's concern. First, we introduce a restricted parameter grid for SANE with only 414 configurations and expand the grid of all baselines to have at least 414 configurations. This makes the limited variant of SANE have the smallest grid size. Second, we add a new version of Pareto curve plot that tunes the methods on held-out data. We pick the Pareto-optimal parameter configurations on the validation set. These are then plotted according to their test accuracy and mean budget. The new results are given in Figure 9 and remain qualitatively similar.

We also highlight that in the matched accuracy experiment of Table 1, the limited variant of SANE becomes the second-best method, only worse than the full-grid SANE, according to average budget over all setups.

Reviewer_SDd9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Thip paper addresses wasted inference compute in repeated sampling and single selection mechanism of the existing early-stopping methods. This paper proposes SANE that is nonparametric and compatible with any black-box selector such as self-consistency, Best-of-N, and weighted Best-of-N that satisfies a union-consistency property. It stops when a lower bound on the probability that the current selected answer remains unchanged after M additional samples exceeds a threshold. SANE achieves 42.4%–73.9% budget savings at accuracy comparable to a fixed 16-sample baseline on five benchmarks.

Critical strengths

The motivation is clear. Fixed-budget repeated sampling wastes inference compute on easy tasks; adaptive stopping directly targets this inefficiency. The proposed SANE is nonparametric and compatible with any black-box selector such as self-consistency, Best-of-N, and weighted Best-of-N that satisfies a union-consistency property.

Critical weaknesses

The theoretical version uses a Hoeffding-style high-probability bound and δ/N allocation. The authors acknowledge that it is extremely conservative, while experiments use n_min=4, 2,000 random subsets per step, and approximate bounds instead. Thus the empirically strongest algorithm does not retain the highlighted high-probability stopping guarantee. The paper should separate the theoretical and practical variants, report their cost–accuracy gap. Compute accounting is incomplete. At every step SANE repeatedly evaluates the selector on many random subsets (2,000 per step), potentially with repeated reward scoring. The selector will introduce additional compute budgets. Lack of experiments on other-scale models and new open-source models.

Questions for authors

Information about large models should be presented in the main submission. This article is in the appendix, which is not mentioned in the main submission. Does union consistency hold strictly for SC/BoN/WBoN with ties?

2 comments
AuthorsOpenReview ↗

Rebuttal - Part 1

We thank the reviewer for their review and feedback. We address each point below.

The theoretical version uses a Hoeffding-style high-probability bound and δ/N allocation. The authors acknowledge that it is extremely conservative, while experiments use n_min=4, 2,000 random subsets per step, and approximate bounds instead. Thus, the empirically strongest algorithm does not retain the highlighted high-probability stopping guarantee.

Our empirical algorithm keeps the theoretically guaranteed lower bound for the stability probability, which itself bounds the conditional accuracy gain. Even though using the certified lower bounds for it instead of a point estimate is needed for a provable guarantee, relying on the point estimate after empirically examining its effectiveness is common in practical algorithms. We have provided this examination in Figure 2 to justify the deviation from theory in our practical implementation. On MMLU-Pro-Math and with the default parameters, only 3.7% of SANE's stops are false positives (Table 4). Since we are concerned with the aggregate performance of the algorithm over many trials, the rare violations of the bounds are not a sever issue.

The use of 1000 random subsets (the original submission misspecified it as 2000) only adds a standard error of 0.016 to the estimation, and nmin>1n_{min} > 1 only makes the rule more conservative. Both are insignificant compared the lower bound's estimation error.

The paper should separate the theoretical and practical variants, report their cost–accuracy gap.

We appreciate the reviewer's feedback on the paper's clarity. In our revision, we have made the distinction by naming the theoretical variant "SANE-Cert" and attributing the theoretical guarantee to it in the introduction. We have also adjusted the algorithm section to reflect this naming separation.

Empirically evaluating SANE-Cert on choices of δ\delta and ρ\rho that provide a meaningful guarantee requires more samples than it is available to us. With ∣Z∣=10|Z| = 10, δ=0.05\delta = 0.05, in all but fewer than 1% of the parameter settings explored in our experiments, SANE-Cert never stops before NN, even when every subsample agrees with the current final answer. Thus, SANE's cost–accuracy gap with SANE-Cert is the same as what it is with the no-stopping rule. The conservativeness of the SANE-Cert is a consequence of our minimal assumptions on the selector and the underlying distributions, and not the algorithm design.

Compute accounting is incomplete. At every step SANE repeatedly evaluates the selector on many random subsets (2,000 per step), potentially with repeated reward scoring. The selector will introduce additional compute budgets.

In all commonly used selection methods, the cost of selecting the final answer is negligible compared to LLM inference. With default parameters and SC, BoN, or WBoN selectors, each SANE decision takes less than 2 milliseconds on a laptop CPU. This is miniscule compared to the cost of generating output with the LLM that is used as the cost measure in our paper. The score of each output only need to be calculated once and stored for each output and needs to be done even without SANE's early stopping. With these cached scores, almost all selection algorithms are a lightweight operation on CPU.

Prior work (Zhao et. al. 2025) has explored using a trained model to select the final answer from the pool of outputs. Even in this case, if the decision is a forward pass of a neural network, the evaluation of sampled subsets can be done in a batch and incur a negligible cost compared to LLM inference. In the extreme cases of costly selection models, one can replace our U-statistic estimator (eq. 7) with a Monte Carlo estimation that only evaluates the selector on ⌊T/t⌋\lfloor T/t\rfloor disjoint subsets of size tt from the pool. This estiamtor has more variance than the U-statistic but is computationally cheaper. This variant recovers most of the benefits of SANE. The following are the budget used on MMLU-Pro-Math to match Base@16 accuracy with the same setup as Table 1. Disjoint MC matches U-statistic in BoN but falls behind on SC and WBoN. Averaged over the three selectors, SANE with disjoint MC estimate only uses 8.2% more samples.

Budget used: test mean samples/question (test accuracy %).

SelectorSANE (U-statistic)SANE (disjoint MC)Base@16
SC6.24 (58.3)7.51 (59.2)16 (59.2)
BoN5.83 (61.1)5.82 (60.8)16 (61.4)
WBoN5.79 (60.8)5.97 (61.0)16 (61.3)
Average5.956.4416
AuthorsOpenReview ↗

Rebuttal - Part 2

Lack of experiments on other-scale models and new open-source models.

We agree that more experiments can strengthen the empirical evaluations. Unfortunately, repeated sampling is notoriously computationally expensive, and a meaningful study with newer models was not feasible. Due to its cost, repeated sampling is mostly considered with smaller LLMs, which is the scale our experiments focus on.

Does union consistency hold strictly for SC/BoN/WBoN with ties?

With a fixed tie-break rule, yes. For example, one can pick the winner among tied outputs based on their pseudo-random hash. We clarified the tie-breaking when defining these selectors in our revision.

Information about large models should be presented in the main submission. This article is in the appendix, which is not mentioned in the main submission.

We will try our best to fit this information in the main text in the versions of the paper.

Reviewer_aTiAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SANE, a nonparametric early stopping algorithm for repeated sampling in LLMs. Instead of modeling the distribution of final answers or rewards for a specific selector, SANE frames early stopping around fixed lookahead stability: it stops sampling when the stability probability, defined as the probability that the selector's choice remains the same after MM additional samples, exceeds a threshold. Assuming the selector satisfies union consistency, SANE lower bounds this probability by partitioning the observed and future samples into disjoint blocks and estimating the selector's choice on each block through subsampling. Depending on the sample size nn, it either partitions the MM future samples into blocks or splits the observed samples into a prefix and a subsampling pool. Evaluated across five benchmarks, three base LLMs, three reward models, and three selectors (SC, BoN, and WBoN), SANE matches the accuracy of fixed budget sampling while using 42% to 73% fewer samples.

Critical strengths

The paper provides a training-free approach with large and consistent sample savings. Existing early-stopping methods first model the underlying distribution of final answers or rewards and then derive how the selector's choice will change. In contrast, SANE directly uses subsampling to estimate whether the selector will change its final answer with more samples. It therefore requires no training and no distributional modeling. Only black-box access to evaluate the selector on arbitrary subsets of samples. This allows the early-stopping rule to be designed independently of the selector and yields substantial, consistent budget savings across setups.

Critical weaknesses
  • The experimental analysis lacks ablations, making it unclear whether the gains come from the core components of the method. The paper neither compares against a naive bootstrap baseline nor ablates its two partitioning schemes; in fact, under the default parameters, the prefix in the prefix-and-pool partitioning is never non-empty. Consequently, one cannot tell whether the empirical gains come from the union-consistency decomposition itself, or from subsampling estimation, agreement stopping at small nn, or a much larger hyperparameter tuning grid.
  • The claim of being "selector-agnostic" is not well supported. The method only applies to selectors that satisfy union consistency. This family likely consists mainly of selectors that score each sample individually and take a sum or maximum, yet the paper does not characterize this scope. Moreover, the experiments only test SC, BoN, and WBoN, which are precisely the types of selectors that existing methods already handle. Common selectors that first filter samples by reward and then take a majority vote do not satisfy union consistency; for them, SANE's lower bound no longer holds and is expected to overestimate stability and stop prematurely, which the paper neither discusses nor tests.
Questions for authors

please refer to weakness

3 comments
AuthorsOpenReview ↗

Rebuttal - Part 1

We thank the reviewer for their review. Their feedback has helped us improve the manuscript and in the following we would like to address their concerns.

The paper neither compares against a naive bootstrap baseline nor ablates its two partitioning schemes; in fact, under the default parameters, the prefix in the prefix-and-pool partitioning is never non-empty.

We are happy to provide both the ablations of SANE partitioning schemes and the comparison against the naive Bootstrapping. For a choice of N,M,αN,M,\alpha that leads to non-empty prefix in SANE and tuning ρ\rho, to reach a fixed validation accuracy, SANE uses 48% fewer samples compared to only using future-sample (FS) partitioning and 73% fewer samples than naive bootstrap. PP-only fails to meet the validation accuracy constraint for SC and WBoN. In the same setup as Table 1, SANE uses 19% fewer samples than naive bootstrap. In Appendix C.1 of our revision, we provide an in-depth comparison of the two partitioning schemes in terms of their precision and recall to detect stability, explained by their estimation error and the true bound's gap. Here are more details:

The reviewer is right that under the default parameters, SANE's prefix is always empty. This is because PP partitioning is only used for large nn and the default parameters are suitable for small budgets. However, around 34% of parameter choices in our grid included non-empty prefix states. To measure the impact of the partitioning choice, we fix N=512,M=8,α=0.5N = 512, M = 8, \alpha = 0.5 to make sure the prefix is not empty and tune ρ\rho . For MMLU-Pro Math, we tune ρ\rho over 14 values from 0.1 to 0.99 to reach base@512 accuracy minus a 0.5 margin on validation set with the lowest budget. Here are the budget and accuracy on the test set. The 48% and 73% claims above are based on the last row.

Test mean samples/question (test accuracy %). N/A: no rho reached the floor.

SelectorSANEOnly FSOnly PPBootNo stopping (N=512)
SC30.45 (61.1)70.24 (61.2)N/A80.81 (61.6)512 (61.7)
BoN6.38 (61.2)6.38 (61.2)34.94 (65.1)9.72 (61.9)512 (62.1)
WBoN8.16 (61.1)9.61 (61.0)N/A78.67 (62.8)512 (63.2)
Average budget15.0028.74N/A56.40512

With N=512, the number of trials are more limited than the paper and the test accuracy has more variations when validation accuracy is matched. Here, Boot draws nn outputs with replacement from the pool and measures the fraction of times that the current final answer is selected from them. It stops if this fraction is over the threshold ρ\rho. Note that Boot is rather a heuristic and does not measure any relevant probabilities. For example in BoN, the agreement rate is at least 1−e−1=0.631-e^{-1}=0.63 regardless of the underlying distributions, due to failure of bootstrapping in extrema statistics. In comparison, SANE tracks an estimate of stability probability and its threshold ρ=1−λM\rho = 1- \lambda M is set by the cost of each sample. We also added Boot to Table 1 in our revision. In two of the 15 setups it wins over SANE with less than 0.6pp margin. On average, SANE uses 19% fewer samples (last row of revised Table 1).

Lastly, we have added an in depth discussion of the choice of partitioning scheme in Section 7 with Figure 3 that shows choosing FS in small nn crucially gives us high precision. In large n, PP has a better recall and both have acceptable precision.

AuthorsOpenReview ↗

Rebuttal - Part 2

The experimental analysis lacks ablations, making it unclear whether the gains come from the core components of the method. [...] Consequently, one cannot tell whether the empirical gains come from the union-consistency decomposition itself, or from subsampling estimation, agreement stopping at small n, or a much larger hyperparameter tuning grid.

In short:

  • (Union Consistency) Union consistency is the structural assumption that enables SANE’s stability decomposition, rather than an optional implementation component.
  • (Subsampling) SANE with subsampling uses 7.6% fewer samples than if disjoint Monte Carlo estimation was used.
  • (Early Agreement) SANE uses 42%, 42%, 48% fewer samples than ESC, Pers, and TSA baselines that use early agreement.
  • (Tuning grid) After expanding the baseline grids, SANE with a grid smaller than the rest still uses at least 15% fewer samples than other baselines, averaged across setups.

We address each point in detail below.

1) Role of union-consistency decomposition. Without union-consistency decomposition, one needs to directly estimate the stability probability P(S(Y1:n+M)=S(Y1:n)∣Y1:n)P(S(Y_{1:n+M}) = S(Y_{1:n}) | Y_{1:n}). With the standard plug-in bootstrapping, this means replacing M fresh outputs Yn+1:n+MY_{n+1:n+M} with MM randomly drawn outputs from Y1:nY_{1:n} with replacement. This is not a valid approach. For example with BoN, the bootstrap samples can never beat the highest scoring output in the pool and the resulting answer will always be the same as S(Y1:n)S(Y_{1:n}). This leads to a stability probability estimation of 1.

2) Role of subsampling estimation. One alternative to subsampling estimation through the U-statistic (eq. 6) is using disjoint subsets of the sample pool to form ⌊T/t⌋\lfloor T/t \rfloor independent observation for a Monte Carlo estimate. Subsampling is the more accurate estimator but disjoint Monte Carlo requires less compute. The following are the budgets used on MMLU-Pro-Math to match Base@16 accuracy with the same setup as Table 1. Disjoint MC matches U-statistic in BoN but falls behind on SC and WBoN. Averaged over the three selectors, SANE uses 7.6% fewer samples.

Budget used: test mean samples/question (test accuracy %).

SelectorSANE (U-statistic)SANE (disjoint MC)Base@16
SC6.24 (58.3)7.51 (59.2)16 (59.2)
BoN5.83 (61.1)5.82 (60.8)16 (61.4)
WBoN5.79 (60.8)5.97 (61.0)16 (61.3)
Average5.956.4416

3) Role of agreement stopping at small nn. We already have three baselines that only work based on agreement stopping. ESC stops once a fixed number of consecutive sampled outputs, tuned from 2 to 16, agree with each other. Pers and TSA look at the selector's choice instead of the outputs themselves and stop once the selector's choices across different nn values agree with each other. On average over Table 1, SANE uses 42% fewer samples than ESC, 42% less than Pers, and 48% less than TSA. These comparisons show that the agreement-based baselines do not recover SANE’s sampling efficiency.

4) Role of parameter-grid size. SANE has three tunable parameters, more than most baselines, resulting in a larger natural tuning grid and greater flexibility in the cost–accuracy trade-off. This does not significantly affect the test accuracies. Test accuracies are reported in Table 5 and are within 0.9pp of the base.

To assess how much SANE’s gains depend on its larger grid, we expanded the baseline grids and added a limited-grid variant of SANE whose grid is smaller than that of every baseline. As reported in Table 1, this variant still uses at least 15% fewer samples than each baseline, averaged across setups, and achieves the lowest sampling budget in 11 of 15 setups. Where a baseline performs better, the gap is at most 2.5pp in budget savings.

AuthorsOpenReview ↗

Rebuttal - Part 3

The claim of being "selector-agnostic" is not well-supported. The method only applies to selectors that satisfy union consistency.

We clarify that the term "selector-agnostic" appears solely in the algorithm's name to signify that SANE requires only black-box access to the selector rather than knowledge of its internal mechanics. The union-consistency assumption is clearly stated when explaining our contribution in the abstract, introduction, and conclusion. We are happy to adjust any specific wording in the next versions.

This family likely consists mainly of selectors that score each sample individually and take a sum or maximum, yet the paper does not characterize this scope. Moreover, the experiments only test SC, BoN, and WBoN, which are precisely the types of selectors that existing methods already handle.

Scope of Union-consistent Selectors. We appreciate the reviewer's feedback to provide more discussions on the scope of union-consistent selectors. Our revision adds a thorough review of 14 selection mechanisms in the literature and whether they satisfy the union-consistency (UC) condition in Appendix A, summarized in Table 2. Beyond BoN, SC, and WBoN that are the most popular selectors and are the focus of the paper, KL-regularized BoN and Length-regularized BoN are also UC. Wasserstein-regularized BoN approximates a UC selector: replacing the empirical output distribution of the pool in its definition with the true output distribution pp makes it UC.

Furthermore, Proposition 1 (Appendix A) proves that filtering outputs using any pool-independent, prompt-dependent, binary verifier (e.g., safety, formatting, length constraints, or reward/confidence thresholds) followed by any UC selector remains UC. While we are unaware of a closed-form characterization of the entire UC class, Proposition 1 demonstrates that it extends well beyond simple sums and maxima.

Necessity of some structural assumptions. We want to highlight that making some structural assumption on the selector is inevitable to reason about the future stability in our black-box setting. Consider the selector that uses SC if the number of outputs is below 100 and switches to BoN afterward. A selector with only black-box access cannot reliably and efficiently work both for this selector and SC. Our method improves upon the previous work by expanding the supported selector from a single algorithm to a large family. The UC condition is natural and, as mentioned after its definition, is used as an axiom in social choice theory.

SANE lifts distribution assumption even on previously studied selectors. Lastly, we want to emphasize that our contribution goes beyond relaxing the prior work's assumption on the selector. It also lifts the parametric distribution assumptions needed for selectors other than SC. In the limited sample regime, modeling quantities such as rewards requires using parametric distributions. BEACON fits a normal distribution and PBox fits an exponential right-tail. Even when we use BoN, which satisfies the stopping rule's assumption on the selector, these distribution assumptions may fail. For example, with LLM-as-a-judge the rewards are one of 10 discrete values or the model's log probabilities may not follow any of these distributions. Regularized variants of BoN introduce KL, length, or Wasserstein penalties, further complicating parametric modeling. SANE is completely distribution-free, outperforming parametric baselines on BoN in our experiments while also providing the first principled stopping rule for WBoN, to the best of our knowledge.

Common selectors that first filter samples by reward and then take a majority vote do not satisfy union consistency; for them, SANE's lower bound no longer holds and is expected to overestimate stability and stop prematurely, which the paper neither discusses nor tests.

We thank the reviewer for highlighting this important distinction. As shown in Proposition 1, filtering by a fixed, prompt-dependent reward threshold before majority voting preserves UC. The closest example we found for the method the reviewer is mentioning is "Deep Think with Confidence" where the outputs with the top α\alpha-quantile rewards are kept, and WBoN is used for selecting among them. In Appendix A we show that this method is approximating a UC selector. Specifically, if instead of the empirical α\alpha-quantile of the reward that is estimated from the pool, the true quantile from pp is used as the threshold, the selector becomes UC. The reviewer is right that due to the possible noise and mismatch between the empirical and true quantiles, UC can be violated. In such cases, SANE can still be applied as an approximate/heuristic stopping rule, though, to the best of our knowledge, no theoretically grounded (non-heuristic) stopping rule currently exists for non-UC selectors.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal Revision

We thank all the reviewers for their review and feedback. We have revised the paper to address their concerns. The major modifications are highlighted in blue. Here is the summary of changes:

Discussions:

  • Review of selection algorithms and scope of union-consistency: In Appendix A, we reviewed 14 selection algorithms in the literature in terms of satisfying union-consistency (UC). We also prove filtering outputs and then applying a UC selector is also UC.

  • Choice of partitioning schemes. In Appendix C.1 (Figure 5,6) we show precision, recall, estimation error and bound gap for each lower bound. This motivates SANE's partitioning choice as having better precision in early iterations and better recall in later ones.

Experiments:

  • Changes to parameter sweep grid: We increased the grid size of the baselines and introduced a new variant of SANE with a smaller grid than all the baselines. Table 1 is updated and SANE - Limited is added to frontier curves in Figure 8.
  • Bootstrap Baseline: In response to reviewer aTiA, we added bootstrapping as a baseline. The results are in Table 1.
  • Ablation of partitioning schemes: We provide the comparison of SANE with only using one of the partitioning schemes in Table 3 (tuned ρ\rho) and Figure 7 (all ρ\rho).
  • False positive rate at stopping time: In response to reviewer CeND, we provide the false-positive rate of SANE at stopping time in Table 3.
  • Test accuracies of Table 1: Table 5 reports the test accuracies of methods with the tuned configuration used in Table 1.
  • Pareto curves with held-out tuning: In Figure 9, we use validation set to pick Pareto-optimal points and plot their test accuracy and budget.
  • Results on Length-regularized BoN: Table 7 reports the resutls for this selector in the same setup as Table 1.

Clarifications and minor changes:

  • We named the theoretical variant of the algorithm SANE-Cert
  • Ties are broken by hash of outputs
  • Bibliography clean-up

We again thank all the reviewers and the AC for their time and effort during this process.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.