Research map / Large language models / Reasoning and chain of thought
Scalable Best-of-N Selection for Large Language Models via Self-Certainty
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes self-certainty, a reward-free confidence metric (KL divergence of next-token distributions from uniform, averaged over tokens), and Borda voting that combines it with self-consistency for best-of-N selection on reasoning and open-ended code tasks.
Problem
Best-of-N selection for LLM reasoning typically relies on costly reward models, while reward-free methods like self-consistency and USC fail on open-ended tasks or scale poorly.
Approach
Score each response by the average KL divergence between its per-token predicted distribution and a uniform distribution (self-certainty), and combine ranks by this score with answer-level voting via a Borda-style weighting (N-rank+1)^p, requiring no external reward model.
Key results
- On LiveBench-Math with N=32, Borda voting (p=1.2) reaches 26.69% vs 26.25% for self-consistency; on GSM8K with N=64 Borda (p=0.7) reaches 91.04% vs 90.99% for self-consistency and PRM reaches 95.15%.
- On MATH with N=64 using Llama-3.1-8B-Instruct, Borda (p=1.2) achieves 64.10% vs 63.40% for self-consistency.
- On DeepSeek-R1-Distill-Llama-8B (MATH Level 3, N=64), Borda (p=1.2) gives 88.06% vs 87.62% for self-consistency and greedy 77.54%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use self-certainty-ranked Borda voting instead of self-certainty-only selection | Llama-3.1-8B-Instruct · LiveBench-Math, N=8 | accuracy: 20.87 -> 23.69 | Helped |
| Use self-certainty-ranked Borda voting instead of self-certainty-only selection | Llama-3.1-8B-Instruct · GSM8K, N=64 | accuracy: 88.90 -> 91.07 | Helped |
| Use self-certainty-ranked Borda voting instead of self-certainty-only selection | Llama-3.1-8B-Instruct · MATH, N=64 | accuracy: 56.70 -> 64.10 | Helped |
| Use self-certainty-ranked Borda voting instead of self-certainty-only selection | Llama-3.1-8B-Instruct · CRUXEval-O, N=64 | accuracy: 45.83 -> 51.23 | Helped |
| Replace uniform reference distribution with an empirical token distribution (ablation) | Self-certainty · MATH test | accuracy: 54.60 -> 54.70; 56.46 -> 56.78 | No clear effect |
| Replace uniform reference distribution with an empirical token distribution (ablation) | Self-certainty · GSM8K test | accuracy: 87.19 -> 85.97; 88.55 -> 86.35 | Hurt |
| Use a larger Borda exponent, p=1.2 rather than p=0.5 (ablation) | Self-certainty Borda voting · MATH test, N=64 | accuracy: 63.71 -> 64.10 | Helped |
| Increase Borda exponent from p=1.2 to p=2.0 (ablation) | Self-certainty Borda voting · MATH test, N=64 | accuracy: 64.10 -> 60.02 | Hurt |
| Use self-certainty-based Borda voting rather than majority voting | Llama-3.1-8B-Instruct · MATH test, N=64 | accuracy: 63.40 -> 64.10 | Helped |
| Use Borda voting with self-certainty rather than normalized weighted-sum self-consistency | Llama-3.1-8B-Instruct · MATH-Level5 test, N=64 | accuracy: 38.75 -> 39.43 | Helped |
Surprising findings
- Perplexity assigns higher confidence to no-answer responses, while self-certainty assigns them lower scores.
- Plain self-certainty alone underperforms self-consistency on definitive-answer math datasets at equal N, and USC underperforms greedy decoding on LiveCodeBench with Llama-3.1-8B-Instruct.
Limitations
- Self-certainty alone is vulnerable to samples with artificially high confidence and underperforms self-consistency on convergent-answer math tasks.
- Optimal Borda exponent p is model- and task-dependent and requires tuning on validation data.
- Several experiments use a single trial, and differences from self-consistency are often small.
Experimental setup
Datasets: LiveBench-Math GSM8K MATH CRUXEval LiveCodeBench
Benchmarks: LiveBench-Math GSM8K MATH CRUXEval-O LiveCodeBench
Metrics: accuracy
Baselines: self-consistency universal self-consistency perplexity FirstAns greedy decoding GRM-Llama3.2-3B-RewardModel-FT Qwen2.5-Math-PRM-7B
Builds on: self-consistency universal self-consistency Borda count
Closest papers by meaning
- A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning (NeurIPS 2025 · similarity 0.91)
- Incentivizing LLMs to Self-Verify Their Answers (NeurIPS 2025 · similarity 0.90)
- Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs (ICLR 2026 · similarity 0.90)
- Optimal Self-Consistency for Efficient Reasoning with Large Language Models (ICML 2026 · similarity 0.90)
- Majority of the Bests: Improving Best-of-N via Bootstrapping (NeurIPS 2025 · similarity 0.89)
- Latent Self-Consistency for Reliable Majority-Set Selection in Short- and Long-Answer Reasoning (AAAI 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.