Paper 2510.15444
A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning
- Published
- Oct 2025
- Research lab
- Independent
- Citations
- 11
- GitHub
- 14 stars
01 In brief
Summary
This paper introduces a theoretical framework for sampling-based test-time scaling in LLM reasoning, decomposing reasoning error into estimation error and model error.
It analyzes self-consistency (SC) and perplexity (PPL), finding SC has linear estimation error convergence while PPL has exponential but suffers from high model error and degradation when probabilities are low.
To address these, the authors propose RPC (Reasoning-pruning Perplexity Consistency), combining Perplexity Consistency (PC) and Reasoning Pruning (RP).
PC integrates internal LLM probabilities into self-consistency to achieve exponential convergence with low model error, while RP prunes low-probability reasoning paths to prevent degradation.
Theoretical analysis shows RPC achieves fast convergence and low error.
Experiments on seven benchmarks (MATH, MathOdyssey, OlympiadBench, AIME, HumanEval, MBPP, APPS) show RPC reduces sampling budget by at least 50% while matching or exceeding SC performance, improves accuracy by 1.29% on average, and enhances confidence reliability (lower ECE).
RPC also generalizes to code generation and additional reasoning tasks, and is compatible with advanced methods like ESC and reward models.
The work provides the first theoretical foundation for sampling-based test-time scaling, offering insights for future method development.
02 From the paper
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.