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

1 Introduction

• The framework decomposes reasoning error into estimation and model error: self-consistency has linear estimation-error convergence, while perplexity has exponential convergence but high model error and slower convergence at low probabilities.These limitations motivate methods that converge rapidly while maintaining low model error.Source: §1 · p. 2
• On four mathematical reasoning datasets, RPC reduces the required sampling budget by at least 50% while matching self-consistency performance; at equal budget, it improves over existing methods by an average of 1.29%.The paper also reports results across seven benchmark datasets and confidence estimates more closely aligned with ground truth than existing methods.Source: §1 · p. 2
• Perplexity Consistency adds internal LLM probabilities to self-consistency, changing estimation-error convergence from linear to exponential while maintaining low model error.Reasoning Pruning automatically models the probability distribution and removes low-probability paths to prevent degradation of convergence when probabilities are low.Source: §1 · p. 2
• RPC’s confidence estimates align more closely with ground truth than existing methods, and its empirical evaluation spans seven benchmark datasets.The paper presents RPC as a hybrid method combining Perplexity Consistency and Reasoning Pruning.Source: §1 · p. 2

2.1 Problem Formulation

• Reasoning paths receive confidence from their generation probability, answers are extracted from paths, and finite samples estimate confidence because exhaustive access is computationally infeasible.The analysis distinguishes confidence in a path from confidence in its extracted answer.Source: §2.1 · p. 3

2.2.1 Reasoning Error Decomposition

• Reasoning error separates into estimation error, determined by sample size and confidence-estimation strategy, and model error, fixed by the LLM’s reasoning capability.Apart from the fixed model error, total reasoning error is bounded by estimation error; improvement can target either component.Source: §2.2.1 · p. 3

2.2.2 Analysis of Self-Consistency

• Self-consistency’s unbiased confidence estimates have variance-only estimation error that decreases linearly with sample size, leaving substantial error when sampling is limited.The analysis assumes LLM sampling follows a Bernoulli distribution to derive method-specific estimation error.Source: §2.2.2 · p. 4, §2.2.1 · p. 4

2.2.3 Analysis of Perplexity

• Perplexity’s estimation error decreases exponentially for paths with non-negligible confidence, but this advantage degrades for very low-confidence paths, and its model error is typically larger than self-consistency’s.Because the path space is nearly infinite, perplexity estimates path probabilities using the unique set of sampled paths.Source: §2.2.3 · pp. 4–5

3 Methodology

• The method addresses three identified limitations: SC’s slow estimation-error convergence, PPL’s large model error, and PPL’s convergence advantage degrading in some cases.The paper frames these as efficiency, effectiveness, and degradation challenges, respectively.Source: §3 · p. 5

3.1 Perplexity Consistency

• PC matches SC’s model-error level while achieving PPL-like exponential estimation-error convergence in most scenarios.When p(ŷ | x) approaches zero and n p(ŷ | x) is much less than 1, the convergence can instead degenerate to a linear rate.Source: §3.1 · p. 6

3.2 Reasoning Pruning

• With the optimal threshold τ = p(y | x), RP achieves optimal error reduction for a given problem with at least the probability specified by Theorem 7.The authors state that this reduction improves estimation-error efficiency and reduces model error; RP sets an answer’s estimated probability to zero when its paths’ cumulative probability is below τ.Source: §3.2 · p. 6
• RP automatically sets its pruning threshold by modeling sampled-path probabilities as a mixture of two Weibull distributions for high- and low-probability regions.For stability with limited samples, the method also uses a truncated mean, retaining outputs above the overall mean to avoid excessive pruning when mixture estimates may be inaccurate.Source: §3.2 · p. 6

3.3 RPC Method

• RPC first prunes low-probability reasoning paths, then computes confidence with PC.This combines the two proposed components into the RPC confidence-estimation method.Source: §3 · p. 5, §3.3 · p. 6

4.1 Experimental Setting

• Experiments compare PPL, SC, and verbalized confidence on four math and three code benchmarks using specified LLMs, consistency functions, and sample sizes.The math models are InternLM2-Math-Plus 1.8B and 7B and DeepSeekMath-RL 7B; code uses Deepseek-Coder 33B. Experiments are repeated 10 times with different random seeds.Source: §4.1 · p. 7

4.2 Empirical Results

• RPC outperforms PPL and SC across math sample budgets, with Table 2 reporting better results in most cases.Figure 2 reports RPC’s best performance across all four math datasets; the detailed accuracy results in Table 2 support the comparison.Source: Figure 2 · p. 8, Table 2 · p. 8, §4.2 · p. 8
• RPC requires fewer samples than SC to reach comparable performance, while Reasoning Pruning addresses the degeneration seen with PC.PC converges faster than SC in several cases and at similar rates in others; RPC’s pruning module is reported to prevent PC’s degeneration.Source: §4.2 · p. 8
• RPC achieves lower ECE and higher accuracy than PPL and SC, indicating more reliable confidence estimates.Figure 3’s MathOdyssey reliability diagrams show reduced calibration error for RPC relative to SC.Source: §4.2 · p. 8, Figure 3 · p. 9

4.3 Further Discussion

• RPC achieves the highest accuracy across all three code-generation benchmarks and outperforms existing methods on GPQA and LogiQA.The code-generation evaluation uses Deepseek-Coder 33B; the GPQA and LogiQA evaluation uses DeepSeek-R1-Distill-Qwen-7B with 16 samples.Source: §4.3 · p. 9, Figure 4 · p. 9
• RPC’s gains persist across InternLM2-Math-Plus 1.8B and DeepSeek-Math 7B, and when used with advanced reasoning models, ESC, or reward-model BoN.The reported scale and architecture results are consistent with Table 2; RPC combined with ESC or BoN outperforms SC and the methods’ original versions.Source: §4.3 · p. 9
• At high sampling temperatures, RPC further improves reasoning performance, whereas SC may deteriorate as estimation errors increase.The reported benefit is attributed to RPC’s ability to use more diverse reasoning paths.Source: §4.3 · p. 9
• RPC adds negligible computational overhead in practice and reduces required LLM inferences; its pruning module needs no manually set threshold.The paper characterizes this as a computational trade-off: minimal overhead in exchange for time savings from fewer inferences, with automatic pruning making RPC hyperparameter-free.Source: §4.3 · p. 9

LLM Reasoning Boosting

• Prior reasoning-boosting work spans prompting, decomposition, few-shot examples, MCTS, reward models, fine-tuning, and efficiency methods; RPC can build on these methods through multiple sampling strategies.The paper distinguishes its theoretical analysis of these methods from prior work focused mainly on empirical effectiveness.Source: §5 · pp. 9–10
• Table 3 reports that RPC outperforms existing methods in major cases.The caption says accuracy is reported as mean and standard deviation, but supplies no specific values.Source: Table 3 · p. 10

LLM Confidence Estimation

• Confidence estimation is grouped into perplexity, verbalized, and self-consistency approaches, with recent work using confidence to enhance reasoning.The paper presents its theoretical explanations as support for findings from DeepConf, CISC, and TTSC.Source: §5 · p. 10

• RPC achieves superior error convergence, reasoning performance, and confidence reliability, according to the paper’s theoretical analysis and empirical results.Source: §6 · p. 10
• RPC combines internal LLM probabilities with self-consistency for faster estimation-error convergence while maintaining low model error and pruning low-probability paths to address degeneration.Source: §6 · p. 10
• The framework decomposes reasoning error into estimation and model error, revealing self-consistency efficiency issues and perplexity effectiveness and degeneration issues.Source: §6 · p. 10
• The paper presents a preliminary step toward advanced reasoning approaches and suggests its framework can guide future research.Detailed limitations and future work are discussed in Appendix E.Source: §6 · p. 10

Broader Impacts

• The framework may benefit LLM reasoning researchers by clarifying existing methods’ limitations and informing future approaches; the paper identifies no negative societal impacts to discuss.The authors frame this as a potential benefit of the work’s theoretical foundation.Source: Broader Impacts · p. 10

Main claims

• The authors state that their contributions are explicitly claimed at the end of the introduction.Source: NeurIPS Paper Checklist · p. 16

Limitations

• The authors say they discuss the work’s limitations at the end of the conclusion and in Appendix E.Source: NeurIPS Paper Checklist · p. 16

Theory assumptions and proofs

• The authors state that theoretical results include their full assumptions and that complete proofs are provided in Appendix A.Source: NeurIPS Paper Checklist · p. 17

Experimental result reproducibility; Open access to data and code

• The authors say the information needed to reproduce the experiments appears in Section 4.1 and Appendix C, with code in the supplementary material and resources on the project homepage.The homepage is https://wnjxyk.github.io/RPC.Source: NeurIPS Paper Checklist · pp. 17–18

Experimental setting/details; Experiments compute resources; Experiment statistical significance

• The authors report that experimental details are in Section 4.1 and Appendix C, compute-resource details are in Appendix C, and standard deviations are reported in the main paper.Source: NeurIPS Paper Checklist · pp. 18–19

NeurIPS Code of Ethics

• The authors state that they reviewed the NeurIPS Code of Ethics and that the paper conforms to it.Source: NeurIPS Paper Checklist · p. 19

10. Broader impacts

• The authors state that positive and negative societal impacts are discussed in Section 6.Source: §10 · p. 19
• The authors report that they released no models or datasets considered high-risk for misuse.Source: §10 · p. 20
• The paper says existing assets are credited in its references and that it introduces no new assets.Source: §10 · pp. 20–21
• The authors state that the paper involves neither crowdsourcing nor research with human subjects.Source: §10 · p. 21
• The authors declare LLM use because the core algorithm estimates confidence from sampled LLM reasoning paths.Source: §10 · p. 22

A.1 Proof of Proposition 1, Proposition 2 and Proposition 3

• The general proof decomposes squared confidence error into model error and estimation error, with the cross term zero for an unbiased confidence function.The proof takes expectations over combinations of n sampled reasoning paths.Source: §A.1 · p. 23
• Self-consistency estimates an answer’s probability by its frequency among n sampled reasoning paths, and its error includes a sampling-variance term and squared model error.The proof applies the general decomposition to the empirical answer-frequency confidence function.Source: §A.1 · p. 23
• Perplexity’s proof uses sampled-path confidence to form a sampling distribution and assumes sampled reasoning paths are distinct, an assumption said to slightly affect n if violated.It then expresses squared error using path probability and whether the path’s answer is correct.Source: §A.1 · pp. 23–24

A.2 Model Error Comparison in Ideal Case

• The paper states that perplexity has larger model error in practice because it does not use the consistency function to analyze problem-specific structure.Source: §A.2 · p. 24
• With infinite sampling and unique answers for incorrect paths, self-consistency’s model error is no greater than perplexity’s, and is strictly lower when consistency identifies equivalent correct paths.The comparison assumes each incorrect reasoning path leads to a distinct answer.Source: §A.2 · pp. 24–25

A.3 Proof of Theorem 4

• For Theorem 4, the proof assumes sampled reasoning paths are distinct and defines k as the number of paths answering a given candidate answer that can be covered under the sampling budget.The proof notes that distinct sampled paths are a reasonable practical assumption and that relaxing it slightly affects n.Source: §A.3 · p. 25

A.4 Proof of Theroem 7

• For Theorem 7, the proof sets the pruning threshold to p(y | x) and estimates a candidate answer’s probability from sampled paths that produce that answer.The excerpt frames the resulting reasoning error in terms of estimation error and model error.Source: §A.4 · p. 26

B Pseudo Code of RPC Method

• RPC’s pseudocode returns the reasoning paths with the highest confidence, using the extraction function to parse paths into answers.Source: B Pseudo Code of RPC Method · p. 27
• The algorithm first retains paths whose high-probability estimate exceeds 0.5 or whose internal probability meets the sample mean, then scores paths by consistency-weighted probabilities of retained paths.The pseudocode identifies these as reasoning-pruning and perplexity-consistency phases, respectively.Source: B Pseudo Code of RPC Method · p. 27

C.1 Datasets

• Mathematical evaluation uses MATH (5,000 test examples), MathOdyssey (387 problems), OlympiadBench (1,284 selected English problems without images), and AIME (993 test problems).The source describes MATH as challenging competition math, MathOdyssey as spanning advanced high-school through Olympiad levels, OlympiadBench as Olympiad-level math and physics, and AIME as problems collected from 1983 to 2024.Source: §C.1 · p. 27
• Code-generation evaluation uses HumanEval (164 Python problems), sanitized MBPP (427 entry-level problems), and 1,000 introductory APPS problems.Source: §C.1 · p. 27

C.2 Detailes of Mathematical Reasoning Task

• Main-paper experiments use temperature 1.0 and top-p 0.95, with prompts following each LLM’s recommended template.Source: §C.2 · p. 27
• InternLM2-MATH-Plus uses chat-role prompts, whereas DeepSeek-Math uses a non-chat prompt; both request step-by-step reasoning.The corresponding prompt passages show “Let’s think step by step” for InternLM2-MATH-Plus and request the final answer in boxed format for DeepSeek-Math.Source: §C.2 · pp. 27–28
• Because tuned math models are difficult to prompt for confidence, the verbalized method estimates probability from the likelihoods of the first generated “True” and “False” tokens.The method follows [52].Source: §C.2 · p. 28

C.3 Detailes of Code Generation Task

• Code snippets are evaluated for functional correctness on dataset test cases, with top-p 0.95, maximum generation length 1,024, code extraction and stop-sequence truncation, and token log-probabilities recorded.For verbalization, confidence is also extracted from the generated text; the listed truncation sequences begin with newline followed by class, def, #, if, or print.Source: §C.3 · p. 28
• Code self-consistency follows [7]: 100 test cases are sampled per problem, and two solutions are consistent when they produce the same results on those cases.The consistency function is an indicator equal to 1 if and only if the two codes execute the same result on the sampled tests.Source: §C.3 · p. 28
• Code-generation prompts provide a function header, signature, and docstring; test-generation prompts replace the function body with “pass” and request test cases, while verbalized prompts request a confidence score and enforce an extractable output format.Source: §C.3 · pp. 28–29

D.1 Results under High Sampling Temperature.

• At T = 1.1 and T = 1.3, RPC consistently surpasses baseline methods, with a significant performance gap over SC.Across sample sizes, RPC improves reasoning performance by leveraging increased sampling diversity, while SC deteriorates from increased estimation error.Source: Table 4 · p. 30, §D.1 · p. 30, Figure 5 · p. 30

D.2 Performance with Different Models Scales

• For InternLM-2-MATH-Plus 1.8B, RPC consistently outperforms SC, while PPL leads on MathOdyssey, attributed to its relatively low model error there.The reported results are for four mathematical reasoning datasets across sample sizes.Source: Figure 7 · p. 31, §D.2 · p. 31

D.3 Performance with R1 LLMs

• On DeepSeek-R1-Distill-Qwen-7B, RPC consistently outperforms PPL and SC across all datasets, with improvements persisting for the stronger base LLM.The experiments use 16 samples and compute internal probability only from the response after the “</think>” token.Source: Table 5 · p. 31, §D.3 · p. 31

D.4 Performance Comparison with Advanced Methods

• RPC using ESC beats SC and ESC across all datasets, while RPC using RM performs better than or comparable to SC and BoN using RM.These results support compatibility with advanced methods; the experiments use DeepSeek-R1-Distill-Qwen-7B with 16 samples.Source: §D.4 · p. 31, Table 6 · p. 32, Table 7 · p. 32

D.5 Performance on Additional Reasoning Tasks

• On GPQA and LogiQA, RPC consistently outperforms PPL and SC, supporting generalization to these additional reasoning tasks.Experiments use DeepSeek-R1-Distill-Qwen-7B with 16 samples; GPQA covers biology, physics, and chemistry, while LogiQA tests logical reasoning.Source: Table 8 · p. 32, §D.5 · p. 32

D.6 Explanation on Hyper-parameters

• RPC’s Reasoning Pruning automatically determines which paths to prune without manual thresholds, and it maintains robust performance across tested initializations and parameter bounds.Tests used 10 random seeds; Fixed Init with bounds [0.2, 0.8] is the default, and these configurations do not require practical tuning.Source: §D.6 · p. 32, Table 9 · p. 33

D.7 Explanation on Computational Overhead

• RPC’s theoretical complexity simplifies to O(25k + nk + n_p^2) ≤ O(25k + nk + n^2), adding minimal overhead compared with SC.On MathOdyssey with 128 samplings, SC takes 0.006s per question and RPC 0.036s; the overhead is negligible against LLM inference time and is exchanged for fewer LLM inferences while maintaining performance.Source: §D.7 · p. 33

Limitations and future work

• The general framework is applied only to two typical sampling-based methods and RPC, and future work could extend it to advanced variants and other test-time scaling strategies.The authors state that the framework can evaluate methods derived from the two analyzed types and may adapt to varied strategies.Source: E Limitations and Future Work · p. 33

Limitations

• RPC is a straightforward post-hoc method using sampled paths, but its gains are moderate versus training-based approaches, and how to use its insights to improve LLM training remains open.It requires no changes to model architecture or training.Source: E Limitations and Future Work · p. 33

Limitations and future work

• The current method is relatively simple; future work could add reward-model scores to perplexity consistency and use more advanced reasoning-pruning techniques.The authors identify both components as having room for improvement.Source: E Limitations and Future Work · p. 33

Future work

• Effective sampling for better convergence requires sufficiently diverse reasoning paths, but sampling strategies to achieve this were not deeply investigated.The authors suggest designing improved strategies based on their theoretical framework.Source: E Limitations and Future Work · p. 34
• RPC works on math, code, and logical reasoning without task-specific properties, while future methods could exploit task-specific properties such as those of g(·).The authors propose developing task-specific approaches based on their framework.Source: E Limitations and Future Work · p. 34