PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhewei Kang, Xuandong Zhao, Dawn Song

arXiv:2502.18581v3cs.CLcs.AIcs.LG

TL;DR

Existing Best-of-N selection methods face computational costs or limitations on open-ended tasks and candidate ranking. The paper proposes self-certainty, a logit-based confidence metric and voting method, and reports scalable performance improvements across reasoning and code-generation settings. The authors conclude that it is a lightweight, broadly applicable approach, while noting that it can underperform self-consistency on problems with definitive answers.

  • Problem

    Reward models are computationally expensive and vulnerable to distribution shifts, while self-consistency and USC have limited open-ended applicability, scalability, or direct response-quality scoring.

  • Method

    Self-certainty estimates response quality from divergence of token probability distributions from uniformity and supports rank-weighted Borda voting across sampled responses.

  • Results

    Self-certainty-based selection scales with N, complements chain-of-thought, and outperforms self-consistency or USC across reasoning and open-ended code-generation settings.

  • Takeaways & Limitations

    Self-certainty provides a scalable, lightweight metric for evaluating and selecting LLM outputs across complex reasoning and open-ended tasks.

  • Takeaways & Limitations

    Self-certainty can underperform self-consistency on mathematical problems with definitive answers, although combining it with answer-level voting can bridge the gap.

Abstract

from arXiv · show

Best-of-N selection is a key technique for improving the reasoning performance of Large Language Models (LLMs) through increased test-time computation. Current state-of-the-art methods often employ computationally intensive reward models for response evaluation and selection. Reward-free alternatives, like self-consistency and universal self-consistency, are limited in their ability to handle open-ended generation tasks or scale effectively. To address these limitations, we propose self-certainty, a novel and efficient metric that leverages the inherent probability distribution of LLM outputs to estimate response quality without requiring external reward models. We hypothesize that higher distributional self-certainty, aggregated across multiple samples, correlates with improved response accuracy, as it reflects greater confidence in the generated output. Through extensive experiments on various reasoning tasks, we demonstrate that self-certainty (1) scales effectively with increasing sample size N, akin to reward models but without the computational overhead; (2) complements chain-of-thought, improving reasoning performance beyond greedy decoding; and (3) generalizes to open-ended tasks where traditional self-consistency methods fall short. Our findings establish self-certainty as a practical and efficient way for improving LLM reasoning capabilities. The code is available at https://github.com/backprop07/Self-Certainty

1 Introduction

Best-of-N improves LLM reasoning by selecting among multiple responses, but reward models and reward-free consistency methods face substantial computational or task-scope limitations. The paper introduces self-certainty, which uses output probability distributions for efficient quality assessment and selection.

  • Motivation: Reward models improve response selection but are expensive, vulnerable to distribution shifts, and susceptible to reward hacking.Ensembles can mitigate some issues while increasing computational overhead.
  • Motivation: Self-consistency is restricted to tasks with directly comparable answers, limiting its use for differing reasoning paths and open-ended generation.Universal self-consistency extends applicability but can be constrained by context length, model ability, and sample size.
  • Self-certainty: Self-certainty measures divergence of predicted token distributions from uniformity, treating more peaked distributions as more certain.The token distribution is produced during inference, so the metric incurs almost no additional computational overhead.
  • Results: Self-certainty-based voting consistently outperforms self-consistency across mathematical reasoning, code reasoning, and code generation benchmarks.The evaluation covers LiveBench-Math, GSM8K, MATH, CRUXEval, and LiveCodeBench across varying sample sizes and question difficulties.
  • Key advantages: Self-certainty scales with sample size, complements chain-of-thought through weighted voting, and generalizes to open-ended responses where self-consistency is inapplicable.The contribution summary reports improvements beyond greedy decoding and USC for open-ended tasks.

2 Related Works

Prior response-selection methods use external reward models or consistency-based aggregation, while confidence-estimation approaches often require additional evaluations. Self-certainty instead uses the LLM’s own logits to assess response quality without additional training.

  • Reward Models: External verifiers and reward models can improve reasoning selection but are often task-specific, base-model-sensitive, and expensive to train.Some require parameter counts similar to the evaluated LLM.
  • Self-certainty: Self-certainty avoids additional training by using the LLM’s own logits for efficient quality assessment.This distinguishes it from external reward models used for response reranking and selection.
  • Consistency-Based Selection: Self-consistency selects the most common response but is limited to tasks with convergent final answers and is difficult to generalize to open-ended generation.Universal self-consistency broadens task coverage but faces scalability issues and lacks a certainty measure.
  • Confidence Estimation: Several confidence-estimation methods require multiple evaluations, hindering scalability for Best-of-N selection.Self-certainty instead leverages output token distributions generated during inference.

3 Measuring Confidence of LLMs

The paper compares token-level and distributional confidence measures for selecting LLM outputs. It proposes self-certainty, which uses the model’s full token distributions to estimate confidence and better distinguish correct reasoning.

  • LLMs produce a probability distribution over the vocabulary at each autoregressive generation step, representing their belief about the next token.
  • Average log-probability and perplexity quantify confidence from probabilities assigned to sampled tokens, but negative perplexity can struggle with long contexts.Perplexity equals exp(−AvgLogP), so the two measures are equivalent for response selection.
  • Distributional confidence evaluates the entire vocabulary distribution at each step and aggregates token-level scores into sentence-level confidence.The aggregation function averages scores across output positions.
  • Self-certainty measures how far predicted token distributions diverge from a uniform distribution, treating more peaked distributions as more certain.The paper explores KL divergence, Gini impurity, entropy, and distributional perplexity as distributional measures.
  • Self-certainty more effectively distinguishes correct from incorrect samples and achieves superior accuracy at higher N values.Figure 2 compares confidence assigned to alternative quadratic-equation reasoning paths, while Figure 3 presents Borda Voting as a separate aggregation method.
  • Self-certainty averages confidence across reasoning steps, allowing early errors to reduce confidence in subsequent steps more effectively than negative perplexity.The method contrasts with reward models that typically use the minimum reward across reasoning steps.

4 Self-Certainty with Voting Method

The voting method combines self-certainty with answer frequency to improve selection among multiple outputs. It uses rank-weighted voting, while acknowledging vulnerability to artificially high confidence scores.

  • Self-certainty-driven selection can be distorted by samples with artificially high confidence scores.With identical N values, it underperforms self-consistency in accuracy on mathematical datasets with definitive answers.
  • The proposed method integrates decoding-layer self-certainty with response-layer information from self-consistency.The paper presents this combination as a way to extract more reliable responses from multiple outputs with explicit answers.
  • Borda Voting addresses score-scaling and frequency weaknesses by ranking outputs by confidence before assigning rank-based votes.Traditional score summation is sensitive to score scaling, while average confidence may underrepresent frequently sampled answers.
  • Each valid response contributes p-weighted votes according to rank, and the answer with the highest total becomes the consensus selection.When p = 0, the method becomes majority voting; as p approaches infinity, the highest-ranked output dominates.
  • Borda Voting can identify the correct answer by integrating confidence ranking and answer frequency when confidence-only selection and self-consistency fail.The parameter p controls the influence of ranking and is tunable.

5 Experiment Setup

The experiments compare self-certainty and related confidence or voting strategies across mathematical reasoning, code reasoning, and open-ended code generation, using varied sample sizes and models.

  • Confidence Measures: Experiments compare confidence measures for selecting responses from identical Best-of-N samples generated by Llama-3.1-8B-Instruct.LiveBench-Math uses N = 4, 8, 16, 32, 64 subsets from 64 sampled responses, averaged across five repetitions.
  • Compared Strategies: The evaluation contrasts self-certainty and Borda Voting with self-consistency, USC, greedy decoding, FirstAns, and selected outcome and process reward models.The comparisons distinguish internal selection from external reward-model selection.
  • Evaluation Protocol: USC is evaluated with its original template, with assistance selecting the first valid response when it fails to choose an extractable answer.This adjustment is described as a fairness measure for comparison.
  • Additional Analyses: The study also examines response-length bias through a 64-sample LiveBench-Math scatter plot and evaluates self-certainty on DeepSeek-R1-Distill-Llama-8B.The reasoning-model experiment uses MATH Level 3 and a single trial because of increased reasoning time.
  • Datasets: Benchmarks cover mathematical reasoning, code reasoning, and open-ended code generation, where self-consistency cannot be applied.Datasets include LiveBench-Math, GSM8K, MATH, CRUXEval-O, and LiveCodeBench.

6 Results and Analysis

Across datasets and selection settings, self-certainty scales with sample size, supports voting, and extends response selection to open-ended generation. Its strongest reported advantages concern distributional confidence, response-length robustness, and Borda voting, alongside a stated vulnerability to artificially high-confidence samples.

  • 6.1 Self-Certainty: Distributional confidence outperforms perplexity for N ≥16, while KL divergence continues improving through N = 32 and 64.Self-certainty is defined as KL divergence from a uniform distribution and generalizes better than alternative empirical distributions.
  • 6.1 Self-Certainty: Self-certainty remains largely invariant to reasoning length, unlike measures that correlate positively with response length.The analysis frames this as avoiding confidence inflation from extended but potentially meaningless reasoning.
  • 6.1 Self-Certainty: Self-certainty better separates correct and incorrect responses, while perplexity can assign higher confidence to no-answer responses.On MATH Level 4, self-certainty distributions for correct and incorrect responses are centered around distinct means.
  • 6.2 Self-Certainty and Voting: Borda voting with self-certainty outperforms majority voting, average self-certainty, and sum self-certainty on MATH.Across four datasets, self-certainty-based Borda voting also consistently outperforms self-consistency across p and N settings.
  • 6.2 Self-Certainty and Voting: The optimal Borda parameter p increases from 0.5 to 1.2 as N increases from 8 to 64.The authors recommend grid search for practical parameter selection.
  • 6.3 Generalization: On LiveCodeBench, self-certainty outperforms greedy decoding across both tested models and surpasses USC on Qwen-2.5-Coder-32B-Ins, with performance improving as N increases.USC underperforms greedy decoding on Llama-3.1-8B-Instruct but exceeds it on the larger Qwen model.
  • 6.3 Generalization: On DeepSeek-R1-Distill-Llama-8B, self-certainty outperforms greedy decoding and sampling, with performance scaling with N.The supplied passage also reports that self-certainty-based Borda voting surpasses self-consistency.

7 Discussion and Future Research

The discussion presents self-certainty as a lightweight approach that scales across settings while identifying limitations and future refinements. It also highlights applications in test-time optimization and learning pipelines.

  • Self-certainty outperforms Greedy and FirstAns, while appropriately tuned Borda Voting surpasses self-consistency on MATH Level 3.
  • Self-certainty can underperform self-consistency on problems with definitive, convergent answers, but combining it with Borda voting bridges this gap.The combined approach achieves results that rival or exceed self-consistency.
  • The current implementation uses simple averaging for token-level confidence and a basic power function for Borda vote distribution.Future work should investigate more sophisticated or data-driven aggregation and vote-weighting functions.
  • Self-certainty’s computational efficiency supports test-time optimization, data filtering, auto-labeling, and reinforcement-learning pipelines.The paper identifies confidence estimation as relevant to reward shaping and intrinsic signals.

8 Conclusion

The conclusion presents self-certainty and self-certainty-based Borda voting as approaches for evaluating and improving LLM responses. It reports scalability, improved chain-of-thought reasoning, and advantages over USC in code generation.

  • Self-certainty and self-certainty-based Borda voting evaluate and enhance model response performance.
  • Self-certainty offers superior Best-of-N scalability compared with average log probability and perplexity.
  • Self-certainty’s ranking information improves chain-of-thought reasoning and outperforms universal self-consistency in code generation tasks.
  • The method’s stability, flexibility, and generalizability support applications across a wide range of domains.

A Theoretical Analysis

The paper defines self-certainty from token-distribution divergence and analyzes when likelihood ascent increases it. Experiments examine scaling, difficulty, distribution choices, and empirical alternatives across reasoning benchmarks.

  • A log-likelihood ascent step increases token-position self-certainty to first order if and only if p_y* > ∥p∥2.
  • For the argmax token, self-certainty increases under the theorem’s conditions whenever the distribution is not one-hot.
  • Borda voting and self-certainty show continued improvement as N increases, while Oracle selection remains significantly better.The Oracle method assumes perfect knowledge of the correct answer.
  • Self-certainty generally decreases as MATH question difficulty increases for both correct and incorrect responses.The authors describe this pattern as a potential parameter-free signal for assessing question difficulty.
  • Performance differences among evaluation methods become more pronounced at higher MATH difficulty levels as N increases from 8 to 64 generations.
  • Self-certainty is defined as the KL divergence between a generated token distribution and a uniform distribution.The divergence measures deviation from random sampling.
  • Replacing the uniform distribution with an empirical distribution has minimal MATH accuracy impact but noticeably reduces GSM8K performance.The paper recommends retaining the uniform distribution because of sensitivity to distributional shifts.

B.5 Comparison of Voting Methods with Different Confidence Metrics

The paper compares self-certainty-based voting with alternative confidence and self-consistency methods. Results favor self-certainty at large N when Borda voting is properly tuned, including against normalized weighted sum.

  • Empirical self-certainty is comparable to uniform self-certainty on MATH but is significantly outperformed by it on GSM8K.The difference is attributed to likely distributional shift.
  • For large N, self-certainty consistently outperforms alternative confidence metrics when the Borda exponent p is properly tuned.
  • Normalized weighted sum combines voting with sentence-level average log probabilities, but incorporating token probabilities generally does not improve standard self-consistency.
  • Borda voting with an appropriate exponent p outperforms normalized weighted sum on MATH-Level5 with N = 64 samples.

C.1 Self-Certainty

The examples illustrate how self-certainty and universal self-consistency evaluate generated responses across mathematical reasoning and code-generation tasks. Self-certainty assigns a higher confidence score to the correct mathematical response, while the examples also show differences in how reasoning is produced across task types.

  • Examples: Self-certainty assigns the correct glasses solution a higher confidence score than an incorrect geometric-series solution.The correct response receives a self-certainty score of 17.81, compared with 17.13 for the incorrect response.
  • Examples: The correct glasses solution calculates 8 full-price and 8 discounted glasses for a total of $64.It charges $5 for each full-price glass and $3 for each discounted glass.
  • Examples: The incorrect glasses solution treats each subsequent glass as 60% of the previous one and reports $12.50.It models the prices as a geometric sequence beginning 5, 3, 1.80, 1.08, ... .
  • Examples: The paper observes that reasoning behavior differs between definite-answer mathematics and open-ended code generation.The model evaluates mathematical answers step by step but jumps directly to a conclusion in the code-generation example.
  • Universal Self-Consistency: Universal self-consistency selects Response 0 as the most consistent answer in the alphabet-writing example.The evaluation states that Responses 0 and 1 share answer 130 and have similar reasoning.
  • Code Generation: For the digit-array product task, the example includes code that increments the minimum digit and computes the product in O(n) time.The implementation iterates over the array and then multiplies the digits.
Loading 2502.18581v3…