- 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
- 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.
- 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
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 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.
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 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.).
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.
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 p 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.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α as SANE. We tune threshold ρ 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 ρ. 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.
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 n 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.