A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning

AI summary

Overview

• Research area: Machine learning / large language model reasoning, specifically the theory of sampling-based test-time scaling and confidence estimation.
• Technical level: Advanced. The paper is built on propositions and theorems (error decompositions, convergence rates, probabilistic guarantees) with proofs deferred to appendices, though the empirical story is told through standard accuracy and calibration tables.
• Scope in one sentence: The paper builds a theoretical framework that splits LLM reasoning error into estimation error and model error, uses it to diagnose self-consistency and perplexity, and proposes a hybrid method called Rpc that is claimed to combine fast convergence with low model error.

What This Paper Is About

Sampling-based test-time scaling improves LLM reasoning by generating multiple reasoning paths for one question and then picking an answer with a confidence estimator, most commonly self-consistency or perplexity. The paper's problem is that the reasons these methods work, fail, or waste computation have not been given a rigorous foundation. The goal is to build a first theoretical framework for these methods, expose the specific weaknesses of each paradigm, and design a method whose error behavior is provably better.

Key Contributions

1. A theoretical framework for sampling-based test-time scaling. Reasoning error (measured as squared error between the estimated confidence and the indicator of correctness) is decomposed into an estimation error term, which depends on sampling size and the confidence estimator, and a model error term, which is fixed by the LLM's reasoning capability.
2. A formal analysis of two dominant paradigms. Self-consistency (Sc) is shown to have estimation error that decays only linearly in sample size n, while perplexity (Ppl) has exponentially decaying estimation error whose rate depends on the magnitude of the ground-truth path probability, and which can degrade when that probability is low; Ppl is also argued to carry larger model error than Sc.
3. A new method, Rpc (Reasoning-pruning Perplexity Consistency). It contains Perplexity Consistency, which sums the LLM's internal probabilities over sampled paths that map to a given answer inside the self-consistency framework, and Reasoning Pruning, which automatically removes low-probability reasoning paths using a fitted two-component Weibull mixture.
4. Empirical validation across seven benchmarks. Results on four math reasoning datasets and three code generation benchmarks report reduced sampling budgets, higher accuracy, and better-calibrated confidence than the compared methods.

Main Findings

• Self-consistency is variance-limited. Its estimation error is exactly (1/n) p(ŷ|x)(1 − p(ŷ|x)), so it shrinks only linearly with sample size and remains large under limited sampling budgets.
• Perplexity converges fast but carries larger model error. Its estimation error is (1 − p(t̂|x))^n p(t̂|x)(2·I[ŷ_i = y] − p(t̂|x)), an exponential rate, but the rate depends on p(t̂|x) and degrades for low-probability paths; the model error term is stated to be typically larger than Sc's in practice and is formally demonstrated in an ideal case in Appendix 4.
• Perplexity Consistency inherits both strengths. With k = |{t̃ : g(t̃) = ŷ}| and α := 1 − (1/k) p(ŷ|x), the estimation error becomes α^n p(ŷ|x)(2·I[ŷ = y] − (1 + α^n)p(ŷ|x)), i.e. exponential in n, while the model error matches that of Sc.
• Perplexity Consistency can still degrade. When p(ŷ|x) → 0 and n·p(ŷ|x) ≪ 1, α^n tends to 1/(1 + n·p(ŷ|x)), so the rate unexpectedly degenerates to linear; this motivates Reasoning Pruning.
• Reasoning Pruning improves both error terms at high probability. With the optimal threshold τ = p(y|x) and k̂ = |{t̃_i : g(t̃_i) = ŷ, i = 1, …, n}|, pruning achieves the optimal error reduction with probability at least 1 − exp(−2k̂k²(1 − τ/(1 − α))²).
• Sampling budget is roughly halved. On MATH, Rpc reaches 51.16 accuracy with 32 samples versus Sc's best of 50.57 with 64 samples (−50.0%); on MathOdyssey, 29.31 with 32 samples versus 28.32 with 112 samples (−71.4%); on OlympiadBench, 11.07 with 64 samples versus 11.07 with 128 samples (−50.0%); on AIME, 9.50 with 48 samples versus 9.40 with 128 samples (−62.5%).
• The isolated Perplexity Consistency module shows the predicted degradation. Pc needs 32 samples on MATH (50.63 vs 50.57, −50.0%) and 64 on AIME (9.00 vs 9.40, −50.0%), but shows no reduction on MathOdyssey (28.51 with 112 samples) or OlympiadBench (11.07 with 128 samples), consistent with the degeneration analysis.
• Accuracy improves with the same budget. Using InternLM-2-MATH-Plus 7B, Rpc averages 26.11 accuracy versus 24.82 for Sc, 21.90 for Ppl, and 10.76 for verbalized confidence; the paper states an average improvement of 1.29% over existing methods when using the same sampling budget.
• Confidence is better calibrated. Average ECE is 12.37 for Rpc versus 13.37 for Sc, 73.14 for Ppl, and 72.09 for Verb. Per-dataset on MathOdyssey, Rpc reaches 31.62 accuracy with ECE 9.87 versus Sc's 28.25 accuracy with ECE 12.23.
• Gains hold across model scales and architectures. With InternLM2-Math-Plus 1.8B, Rpc scores 37.88 / 16.35 / 6.52 / 3.26 on MATH / MathOdyssey / OlympiadBench / AIME versus Sc's 36.48 / 14.52 / 5.99 / 2.66; with DeepSeekMath-RL 7B, Rpc scores 53.37 / 37.25 / 11.30 / 9.52 versus Sc's 53.33 / 36.68 / 11.29 / 9.42.
• Code generation results are also favorable. On HumanEval, MBPP, and introductory-level APPS using Deepseek-Coder 33B, Rpc achieves the highest accuracy across all three benchmarks.
• Rpc is described as hyperparameter-free. Reasoning Pruning determines the threshold automatically from the sampled probability distribution, so no manual threshold needs setting, and the paper states the added computational overhead is negligible relative to LLM inference time.

Methodology in Plain English

The authors start from the observation that when an LLM answers a question, its confidence in an answer is estimated by sampling a finite number of reasoning paths and then scoring them. They measure how wrong that estimated confidence is compared with the ideal outcome — 1 if the answer is correct, 0 if not — using squared error averaged over all possible sets of sampled paths. Splitting that expression algebraically yields two pieces: one that reflects sampling noise (estimation error) and one that reflects how well the model's own probabilities match reality (model error). Applying this split to self-consistency reveals a slow, linearly shrinking noise term; applying it to perplexity reveals a fast exponential term that weakens for low-probability paths, plus a larger model-error term.

Their proposed fix borrows from both sides. Perplexity Consistency keeps self-consistency's habit of grouping sampled paths by the answer they produce, but instead of counting paths it adds up the LLM's internal probabilities for those paths, so the answer score is a probability mass rather than a vote count. Reasoning Pruning then deletes candidate answers whose cumulative probability is too small. Because a hand-tuned cutoff is fragile, the authors fit a mixture of two Weibull distributions to the observed path probabilities, treat one component as the high-probability region and the other as the low-probability region, and discard paths whose posterior probability of belonging to the high-probability component is below 0.5. A truncated-mean safeguard keeps paths above the overall mean so that small samples do not trigger over-aggressive pruning.

Empirically, they benchmark Rpc against perplexity confidence, self-consistency confidence, and verbalized confidence. Math experiments use InternLM2-Math-Plus at 1.8B and 7B, plus DeepSeekMath-RL 7B; code experiments use Deepseek-Coder 33B. Default sample sizes are n = 128 for MathOdyssey, OlympiadBench, and AIME, and n = 64 for MATH, with each experiment repeated 10 times under different random seeds on A800 and H800 GPUs.

Why This Matters

• Impact on research: The paper offers a reusable decomposition, so new confidence estimators can be compared by which error term they attack rather than by benchmark score alone. It also provides a theoretical account of why a widely used technique (self-consistency) has a hard efficiency ceiling, and it connects LLM internal probability to the consistency framework in a provably structured way.
• Question answering and tutoring systems (applications): Best-of-N selection with better-calibrated confidence lets a system decide when an answer is trustworthy and when to escalate or ask for clarification.
• Mathematical and scientific problem solving (applications): The MATH, MathOdyssey, OlympiadBench, and AIME results concern exactly the competition-style workloads where compute-constrained deployment matters most.
• Code generation and program repair (applications): The HumanEval, MBPP, and APPS experiments suggest the selection mechanism transfers to tasks where correctness is checked by tests rather than by string matching.
• Domain question answering with smaller models (applications): Because the method was also tested on DeepSeek-R1-Distill-Qwen-7B with 16 samples on GPQA and LogiQA, the approach is relevant where only small models or small sampling budgets are affordable.
• Industry relevance: Halving the number of sampled generations directly cuts inference cost, which is the dominant cost in test-time scaling. Because the paper reports the added overhead of Rpc as negligible next to LLM inference time, it is a plausible drop-in around existing serving stacks, and the authors report compatibility with ESC and Best-of-N using a reward model.

Future Directions

• Pruning under tiny p(ŷ|x). The degeneration analysis and Remark 6 leave the low-probability regime only partially resolved; how reliably the fitted Weibull mixture identifies the right threshold when very few samples are drawn remains an open question.
• Extending the theory beyond the current assumptions. The analysis relies on a Bernoulli sampling assumption and a specific ideal case for comparing model errors; relaxing these would test how far the propositions generalize.
• Broadening the empirical base. The paper already extends to GPQA and LogiQA, code generation, high sampling temperatures, and advanced base methods (ESC, Best-of-N with a reward model); further tasks and estimator families would show whether Rpc is a general wrapper or a math-specific improvement.
• Probability-based methods that use external models. The paper's categorization includes methods that score reasoning paths with external models rather than the LLM's internal probability, but the analysis and method target internal probability only; a framework covering external scorers is a natural next step.

Target Audience

Researchers and graduate students working on LLM inference-time methods, confidence estimation, or calibration, plus practitioners who deploy Best-of-N style sampling and need to justify a sampling budget. Readers need comfort with expectation, variance, and convergence-rate arguments, since the core arguments are propositions and theorems rather than experiments alone.

Authors’ abstract

Test-time scaling seeks to improve the reasoning performance of large language models (LLMs) by adding computational resources. A prevalent approach within the field is sampling-based test-time scaling methods, which enhance reasoning by generating multiple reasoning paths for a given input during inference. However, despite its practical success, the theoretical foundations remain underexplored. In this paper, we provide the first theoretical framework for analyzing sampling-based test-time scaling methods, grounded in the perspective of confidence estimation. Based on the framework, we analyze two dominant paradigms: self-consistency and perplexity, and reveal key limitations: self-consistency suffers from high estimation error while perplexity exhibits substantial modeling error and possible degradation of the estimation error convergence. To address these limitations, we introduce RPC, a hybrid method that leverages our theoretical insights through two key components: Perplexity Consistency and Reasoning Pruning. Perplexity Consistency combines the strengths of self-consistency and perplexity, boosting the convergence rate of estimation error from linear to exponential while preserving model error. Reasoning Pruning prevents degradation by eliminating low-probability reasoning paths. Both theoretical analysis and empirical results across seven benchmark datasets demonstrate that RPC has a strong potential for reducing reasoning error. Notably, RPC achieves reasoning performance comparable to self-consistency while not only enhancing confidence reliability but also reducing sampling costs by 50%. The code and resources are available at https://wnjxyk.github.io/RPC.