Scalable Best-of-N Selection for Large Language Models via Self-Certainty

Thank you for your thoughtful feedback. We appreciate the opportunity to clarify and strengthen our work. Below we address your concerns and outline our modifications:

1. Limited Improvement and Novelty (Weakness1 & 2)

   Our paper introduces self-certainty metrics and Borda voting, both of which are novel contributions not covered in existing literature. Additionally, we conduct a systematic comparison between two major paradigms of confidence estimation:

   • Probability-based measures (e.g., perplexity, which only considers the probability of the sampled token)
   • Distribution-based measures (e.g., self-certainty, which leverages the entire token distribution)

   This comparison highlights the advantages of using distributional information for calibrating confidence and selecting superior responses.

   Significance of Improvements: The performance gains of Borda voting are substantial and consistent. For example:

   • On LiveBench-MATH, Borda voting improves accuracy by +1.2% (N=8).
   • On MATH, it outperforms self-consistency by +0.7% (N=64).

   These improvements are especially meaningful given the strong baseline of self-consistency and the difficulty of these benchmarks.

   Key Advantages of Self-Certainty:

   • Fine-grained Confidence: Provides token-level estimates rather than coarse sequence-level metrics.
   • Generalizability: Applicable to diverse tasks, including open-ended scenarios where final answers are not directly comparable.
   • Efficiency and Scalability: Uses logits already computed during inference, adding negligible overhead.
   • Robustness vs. Perplexity: Self-certainty better distinguishes correct from incorrect outputs (Figure 1), avoids length bias (Figure 5), and achieves superior stability (Figure 4, Table 1).

   While increasing N may improve self-consistency, it incurs significant computational cost. In contrast, self-certainty-based methods leverage existing logits with virtually no extra cost under a proper implementation.

2. Comparison with Normalized Weighted Sum (Weakness2 & Problem2)

   We considered straightforward score‐summing but found two critical shortcomings:

   1. Instability under imbalanced samples. Borda voting mitigates the collapse of sum-based methods self-consistency in imbalanced cases (e.g., 0.5 + 0.5 > 0.9 or 0.5×10 > 0.9×5), where it revert to vanilla majority voting and ignore confidence.

   2. Tunable trade-off via exponent p. The exponent p lets us smoothly interpolate between pure voting‐based (p→0) and confidence-based (p→∞) schemes.

   We deliberately use self-consistency rather than a normalized weighted-sum baseline because prior work shows that normalized weighted-sum actually underperforms vanilla self-consistency (see Table 1 of the Self-Consistency paper [1]). Moreover, normalized weighted-sum relies solely on token probabilities and ignores the full distribution over unsampled tokens—a limitation that our self-certainty metrics overcome, as evidenced in Figure 1, Figure 4, and Table 1. Finally, when we replace probabilities with self-certainty scores in a “sum voting” variant (Table 2), Borda voting still outperforms simple summation, confirming the advantages of our rank-based approach.

3. Experiments with Additional Reasoning Models (Weakness3 & Question3)

   We agree that broader evaluation strengthens the work. We have now added experiments on Qwen3-4B (Thinking Mode) with the MATH-level 5 test set. The same performance ordering holds: FirstAns < Self-Certainty < Self-Consistency < Borda.

   Method	N=4	N=8	N=16
   FirstAns	87.24	87.61	88.37
   Self-Consistency	87.84	88.37	89.43
   Self-Certainty	87.54	88.14	88.97
   Borda (p=0.3)	87.92	88.44	89.65
   Borda (p=0.7)	87.99	88.52	89.73
   Borda (p=1.2)	87.92	88.60	89.88
   Borda (p=2.0)	87.54	88.44	89.95

4. Clarification on Greedy Decoding (Question 1) Yes—greedy decoding uses a single pass. It is fully deterministic (aside from floating-point nondeterminism), so additional sampling yield little variations.

We believe these clarifications and additional results address your concerns and demonstrate the novelty, significance, and robustness of our contributions. Thank you for your valuable feedback.

[1]Self-Consistency Improves Chain of Thought Reasoning in Language Models

Thank you for your thoughtful feedback. We address each point below and will incorporate these clarifications in the revised manuscript.

1. Clarity of Narrative (Weakness1 & Problem2,3)

   The overall flow of our paper is as follows: Our experiments are exploratory in nature rather than aimed at proving a specific theoretical result. We observed that most existing confidence measures rely solely on the probability of sampled tokens—such as perplexity—while discarding the distribution of unsampled tokens. This led us to ask an important question: Does the discarded distribution encode useful information about the model’s confidence?

   To answer this, we introduce four candidate confidence measures that incorporate distributional information. Among these, KL-divergence performs best. We term this approach self-certainty (SCe) and adopt it as our primary metric.

   To further enhance the performance of existing metrics, we propose Borda voting and evaluate both its effectiveness and the generalizability of self-certainty. We acknowledge that the switch between the term KL and self-certainty may reduce readability. To address this, we will revise the manuscript to consistently denote it as KL (SCe)* Additionally, we will clearly separate our main proposed method from baseline methods in the revised version for improved clarity.

   Your suggestion to separate probability-based methods and voting-based methods to better highlight the strengths of our approach is greatly appreciated. We will reorganize the presentation accordingly and include the metric used (mean accuracy) in the tables for transparency.

2. Significance of Results (Weakness2 & Problem3)

   We agree that emphasizing the statistical significance of results strengthens the paper. In the revised manuscript, we will include a one-sided paired t-test with the hypothesis that the proposed voting methods outperform self-consistency at fixed $N$ and $p$ across runs and datasets.

   The p-values are shown below:

   Variant	p (N = 8)	p (N = 64†)
   Borda (p = 0.3)	0.00	0.09
   Borda (p = 0.7)	0.01	0.02
   Borda (p = 1.2)	0.02	0.00
   Borda (p = 2.0)	**	0.00

† LiveBench-Math is excluded as the result is unavailable. ** Underperforms self-consistency.

As shown, Borda voting with most values of $p$ significantly outperforms self-consistency.

3. Choosing $p$ (Weakness2 & Question1)

We have discussed $p$-selection in the end of Section 6.2. Two practical strategies can be used when exhaustive search is undesirable:

• Rule of Thumb: Use $p = 0.3$ for $N \leq 16$; $p = 1.2$ for larger $N$.
• Data‑Driven Tuning: Tune $p$ on a held‑out validation set or a small subset of the test set.

While these heuristics may not yield the global optimum, they still deliver performance that significantly exceeds self-consistency, as shown by the significance tests above.

4. Practicality of Using $N > 16$ (Question 4)

   It is standard practice in the literature for best-of-$N$ methods to evaluate with $N > 16$. For example:

   • Self-consistency [1] uses $N = 40$.
   • Scaling test-time compute considers $N = 512$ [2].
   • PRM evaluates up to $N = 1000$ [3].

   To contextualize $N = 64$: if a reasoning model requires 8× the tokens of a standard model, sampling 64 responses for a standard model is equivalent to ~8 samples for a reasoning model—a reasonable computational budget.

   Furthermore, strong performance at larger $N$ demonstrates the stability of self-certainty, an important property for confidence metrics. This indicates robustness when handling more tokens with fewer errors, which is highly desirable.

[1]Self-Consistency Improves Chain of Thought Reasoning in Language Models

[2]Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters

[3]Let’s Verify Step by Step

Thank you for your valuable feedback. Below, we address each of your concerns individually:

1. Normalization of Self-Certainty (Weakness1)

   The method of normalizing self-certainty depends heavily on the specific use case and is typically straightforward. For example, if self-certainty is used in reinforcement learning, z-score normalization ($\frac{\text{sce} - \text{mean(sce)}}{\text{std(sce)}}$) can be an effective choice. Alternatively, if one intends to interpret self-certainty as a probability or scale it to the $[0, 1]$ range, min-max normalization ($\frac{\text{sce} - \min(\text{sce})}{\max(\text{sce}) - \min(\text{sce})}$) is applicable.

   It is worth noting that even well-established metrics like probabilities often require transformation prior to application. For instance, in the self-calibration metric [1] you mentioned, a transformation of the form $\mathrm{SSC}(y)= \frac{\sum_{i : y_i = y} c_i}{\sum_{i=1}^{N} c_i}$ is employed. In this context, $c_i$ could seamlessly be replaced with self-certainty scores $sce_i$ for normalization purposes.

   Furthermore, many widely used metrics in NLP, such as perplexity or average log-probability, are not normalized but are nonetheless informative and accepted by the community.

2. Intuition Behind Borda Voting (Weakness1 & 2)

   Borda voting is a deliberate design choice, not a workaround for unnormalized scores. It balances the influence of self-certainty and self-consistency while remaining stable as $N$ changes. Table2 shows that simple sum voting performs between pure self-consistency and Borda voting. In small or highly imbalanced samples (e.g., $0.5+0.5>0.9$ or $0.5\times10>0.9\times5$), sum voting collapses to vanilla self-consistency, discarding confidence information. Borda voting mitigates this by ranking the scores and by letting us modulate the relative weight of confidence via the exponent $p$. Designing a scheme that keeps absolute scale, preserves stability across $N$, and offers the same control remains a promising avenue for future work.

3. Clarification of Lines 219–221

   Thank you for pointing this out. The statement:

   “Notably, perplexity assigns higher confidence to no-answer responses—often resulting from self-repetition or early stopping—while self-certainty reliably assigns these responses lower confidence scores.”

   was intended to reference Figure1, where we distinguish between correct, incorrect, and no-response cases, not Figure 4. We will revise the manuscript wording to eliminate this ambiguity.

4. Clarification Regarding Figure 4

   We appreciate your close reading and catching the typo in Equation (2) and the formulas afterwards; it should be $p(\cdot|x, y_{\leq i})$ instead of $p(\cdot|x, y_{< i})$.Correspondingly, our token‑wise self‑certainty for the first token should measure the KL divergence after sampling token 1, which better reflects the model’s change in belief after deciding on one token. While this shift has minimal effect on the sentence‑wise self‑certainty (since it averages over many tokens), it yields more interpretable token-level values.

   The values reported in Figure 4 are empirical, not made up. We examined multiple completions and selected representative examples based on their confidence trajectories. By “initial error” we meant the first reasoning step (step 1), not the first token. Our goal was to illustrate the model’s early preference between two reasoning patterns; we agree that aggregate metrics are more informative overall, and we will both correct the typo and clarify our intent when discussing Figure 4.

5. Additional Questions

   • Handling Ties: In the rare event of a tie, we select the first sampled candidate. However, due to the use of the power function in weighting, ties are extremely uncommon in practice.

   • Upper Bound: The upper bound of performance is provided in Appendix A.1, Figure 9, under the label Oracle, which significantly outperforms all mentioned metrics.

   • Model Precision: The model uses bfloat16 for weights during inference and float32 for subsequent logit processing.

We appreciate your insightful comments and believe the revised manuscript will reflect these improvements more clearly.

[1] Efficient Test-Time Scaling via Self-Calibration.

Thank you for this explanation.

Now I fully understand what this example wants to convey. In your revised version, please either explain it clearly or use another straightforward case.

I am generally satisfied with this paper so far, and I have one last concern about the generalizing ability of self-certainty. In Table 1, self-certainty improves over self-consistency by using a better confidence measurement. On the other hand, the Soft Self-Consistency (SSC) [1] method we discussed earlier improves over self-consistency using a more delicate answer aggregation method. So, it comes to me that whether combining self-certainty and the SSC method yields even better improvement.

[1] Efficient Test-Time Scaling via Self-Calibration.

Thank you for your thoughtful review! We’re grateful for the opportunity to clarify and strengthen our manuscript.

1. Comparison with Soft Self‑Consistency (Weakness1) Thank you for pointing out the Soft Self‑Consistency paper—it’s highly relevant. We have now directly compared our self‑certainty measure against soft self‑consistency (using mean‑aggregation over the entire response as the action space) on the MATH‑Level 4 dataset with $N=16$. Results:

   Method	First Answer	Self‑Certainty	Soft Self‑Consistency
   Accuracy	57.21	64.37	58.53

   These results indicate that self-certainty significantly outperforms soft self-consistency under equivalent settings. While the original soft self-consistency also introduces the idea of averaging over the answer space alone (instead of the full response), this innovation is equally applicable to self-certainty.

   Moreover, in scenarios with sparse answer spaces—such as those discussed in the SSC paper—self-certainty can be especially advantageous over self-consistency. This is because each response is more likely to produce a unique answer group, reducing the effectiveness of self-consistency. We will cite and discuss the Soft Self-Consistency paper in the next version of the manuscript.

2. Usefulness of Self‑Certainty (Weakness2 & 3) Although self‑certainty alone underperforms full self‑consistency methods, it offers several unique advantages:

   • Fine‑Grained Confidence Self‑certainty provides token‑level confidence scores, enabling potential of “local” or process‑based scoring.

   • Generalizability Unlike self-consistency, which relies on comparable final answers, self-certainty is applicable to a wider range of tasks, including open-ended or generative tasks such as free-form dialogue. It is particularly useful in cases where the answer space is vast or difficult to isolate from the overall response. In addition, self-certainty can be integrated with GRPO to support reinforcement learning without external feedback.

   • Model Calibration Self-certainty is effective at capturing model calibration. As shown in Figure 1, it better separates correct from incorrect and null responses compared to perplexity. In Appendix A2, Figure 10, we show that self-certainty correlates well with question difficulty, indicating its potential as a proxy for model performance or task complexity in the absence of ground-truth answers.

   • Standalone Metric In contrast to composite methods that require multiple scoring mechanisms, self-certainty is a standalone metric. It can replace or complement traditional token probability–based confidence signals. For example, self-certainty can substitute the token-probability weights in soft self-consistency, potentially improving its performance.

   • Potential for Black-Box Models Although current APIs may not expose self-certainty, the metric does not require revealing the full predictive distribution, making it compatible with plausible future API designs (e.g., exposing token-level confidence summaries). Moreover, for black-box systems, one could approximate self-certainty using a white-box surrogate’s logits, which can be a promising future work.

3. Voting Methods with Different Confidence Measures (Weakness3 & Question) We agree that a head-to-head comparison is helpful. On MATH-Level-5 with Llama-3.1-8B-Instruct (N=16), we evaluated voting using several confidence measures and Borda exponents p.

   Method	Perplexity	(D) Entropy	(D) Perplexity	(D) Gini	Self‑certainty
   Self‑consistency (p=0)	37.99	37.99	37.99	37.99	37.99
   Borda (p = 1)	38.60	39.12	38.14	39.35	38.90
   Borda (p = 2)	38.60	38.40	38.14	38.75	39.43

   When $N$ and the exponent $p$ is large, self‑certainty–based Borda voting outperforms other metrics, which demonstrates its robustness. We will include this table and analysis in the revision.

4. Choosing the Optimal Exponent $p$ in Voting (Weakness4) We appreciate the concern about selecting $p$. As discussed at the end of section6.2, the optimal $p$ increases with the number of samples N. Except exhuastive search, below are two possible way of determine $p$ to use

   • Rule of Thumb: use $p=0.3$ for $N\le16$; $p=1.2$ for larger $N$.
   • Data‑Driven Tuning: one can also tune $p$ on a held‑out validation set or a small fraction of the test set.

   We will expand this discussion and provide more guidance in the revised manuscript.

Thank you again for your valuable feedback. We look forward to incorporating these revisions and believe they will significantly strengthen our work.

We sincerely appreciate your thoughtful feedback. Below, we address your specific concerns and suggestions:

1. Justification of Choosing Reverse KL with Uniform Distribution as Main Metrics (Weakness)

   We chose reverse KL divergence to a uniform distribution as our primary confidence metric based on extensive exploratory experiments. Our motivation was to ask: “Does the probability mass beyond the sampled token help us assess model confidence for best‑of‑N selection?” We compared several candidates (e.g., forward KL, entropy, perplexity) and found that reverse KL is the most robust, particularly as N increases: it does not suffer from the same scaling “pitfalls” as other metrics.

   Regarding the uniform reference, we also tried using the empirical distribution over the N samples (Appendix A.4) and observed no significant difference. We retain the constant term in the uniform‐KL for easier interpretation; users may omit it if desired.

   To further elucidate the behavior of “self‑certainty,” we will include two formal properties (and their proofs) in the next revision:

   1. SFT increases self‑certainty on the training completions.
   2. Self-certainty is less prone to repetition trap. When the repetition‑branch distribution features a flatter tail, the self‑certainty–preferred collapse set is a subset of the distributional entropy or perplexity sets.

2. Incorporating a Voting Scheme over Multiple Metrics (Question1)

   We agree that combining confidence metrics can be beneficial. We have implemented a simple Borda‐count voting scheme on MATH‑level 5 (N = 64) and report preliminary results below:

   Method	Perplexity	(D) Entropy	(D) Perplexity	(D) Gini	Self‑certainty
   Self‑consistency (p=0)	37.99	37.99	37.99	37.99	37.99
   Borda (p = 1)	38.60	39.12	38.14	39.35	38.90
   Borda (p = 2)	38.60	38.40	38.14	38.75	39.43

   These results show that, for large N, self‑certainty dominates when the Borda exponent p is tuned appropriately—demonstrating its robustness relative to other metrics. We will include this table in the revised manuscript.

3. Why the “FirstAns” Baseline Stops Improving for N ≥ 16 (Question2)

   The “FirstAns” baseline simply selects the first valid answer encountered among the N samples. In our experiments, all questions already yield a valid answer within the first 8 samples, so increasing N beyond 8 offers no benefit. Other metrics degrade for large N because they can be misled by over‑confident incorrect responses.

4. Self‑certainty as a Measure of Model Calibration (Question3)

   Indeed, self‑certainty serves as an effective proxy for calibration. In Figure 1, self‑certainty cleanly separates correct responses from no-response and incorrect ones, whereas perplexity exhibits weaker separation. Furthermore, Appendix A.2 (Figure 10) shows that average self‑certainty declines significantly as problem difficulty increases, matching the drop in accuracy. We will make these calibration connections explicit in the revised draft.

5. Clarification on Figure 2 Normalization (Question4)

   In Figure 2, we compare each metric against itself across two sample sets—not the two metrics against each other—so no additional normalization is needed. Both self‑certainty and perplexity are already length‑normalized by definition, allowing direct comparison across samples of varying lengths.

6. Runtime Complexity and Memory Overhead (Question6)

   Computing self‑certainty incurs approximately no extra cost: the logits required are already produced during sampling, so best‑of‑N strategies mentioned in our manuscript (regardless of confidence metric) share the same time and memory complexity, which is dominated by the sampling process itself. While one could leverage self‑certainty for dynamic sampling given the roboustness demonstrated in our article, that extension is beyond this paper’s scope.

7. Self-certainty on Short Questions (Question5) Since self-certainty is a logit-based method, we infer that for short questions there are too few logits to average over, and the task relies more on memorization than on reasoning, self‑certainty’s effectiveness can decline. Here is an experiment on a Commonsense QA using Llama 3.1‑8B‑Instruct with N = 8, we obtain:

   Method	Accuracy (%)
   FirstAns.	51.02
   Self‑consistency	59.05
   Self‑certainty	53.64
   Borda voting (p = 0.7)	60.11

   Here, Borda voting still able to outperform self-consistency under the preliminary setting. We will include the result of the multiple choice QA dataset for completeness in the future revision.

We trust these clarifications and the additional results will address your concerns. Thank you again for the valuable feedback!