Technical Summary: Reliable Chain-of-Thought via Prefix Consistency

Problem Statement

Large Language Models (LLMs) often improve reasoning accuracy by generating multiple Chain-of-Thought (CoT) traces and aggregating them via Majority Voting (MV), a technique known as self-consistency. However, Standard MV treats all generated traces equally, failing when the correct answer is in the minority. To address this, Weighted Majority Voting (WMV) methods assign reliability scores to traces based on confidence signals derived from token log-probabilities (e.g., DeepConf, Self-certainty) or verbalized self-assessments (e.g., P(True)).

A critical limitation of existing WMV methods is that their reliability signals often fail to distinguish between correct and incorrect traces on difficult problems. As demonstrated in the paper, on challenging benchmarks where Pass@1 is low (e.g., <50%), baseline confidence signals frequently place correct and wrong traces in overlapping ranges, rendering them ineffective for reweighting precisely when it is most needed. Furthermore, many existing methods require access to token-level log-probabilities, which may not be available in all deployment scenarios.

Methodology: Prefix Consistency

The authors propose Prefix Consistency, a novel reliability signal that does not require access to token log-probabilities. The core observation motivating this method is that correct reasoning traces tend to be more reproducible under regeneration than incorrect ones.

The Mechanism

1. Truncation: For each generated CoT trace $y_i$ with answer $a_i$, the method truncates the trace at a fixed fraction $\tau$ (e.g., 75% of the tokens), retaining the prefix.
2. Regeneration: The model is prompted to regenerate the continuation from this truncated prefix $K$ times, yielding a set of new answers $\{ \tilde{a}_{i,1}, \dots, \tilde{a}_{i,K} \}$.
3. Scoring: A prefix consistency score $c_i(a)$ is calculated for every candidate answer $a$ within the group (initial answer + regenerations). The score represents the frequency with which $a$ appears in the group:
   $$c_i(a) = \frac{|\{a' \in A_i^{(\tau, K)} : a' = a\}|}{K+1}$$
   If the initial answer $a_i$ is correct, the regeneration process tends to reproduce $a_i$ (high $c_i(a_i)$). If $a_i$ is incorrect, the regeneration often diverges to different incorrect answers, resulting in a lower consistency score for the initial wrong answer.

Prefix-Consistency-Weighted Majority Voting (PC-WMV)

The method integrates this signal into a Weighted Majority Voting framework. Instead of weighting the initial sample once, PC-WMV weights every distinct candidate answer $a$ in the regeneration group based on its reproducibility score $c_i(a)$. The final prediction is the answer with the highest total weighted vote:
$$\hat{a}_{PC} = \arg \max_{a \in \mathcal{A}} \sum_{i=1}^N w(c_i(a))$$
where $w: [0, 1] \to \mathbb{R}_{\ge 0}$ is a weighting function (e.g., linear, quadratic, or cubic).

Theoretical Guarantee: The paper provides an asymptotic analysis (Theorem 1) showing that if the discrimination gap $D(\tau) = r_C(\tau) - r_W(\tau)$ is positive (where $r_C$ is the reproduction rate of correct answers and $r_W$ is that of wrong answers), PC-WMV can recover the correct answer even when the initial Pass@1 is below 50% and Standard MV would fail. Specifically, PC-WMV converges to the correct answer whenever $\pi(a^*) > \frac{r_W}{r_C + r_W}$, a threshold strictly lower than the 0.5 required by Standard MV.

Key Contributions

1. Novel Reliability Signal: The introduction of prefix consistency, a signal based on the reproducibility of answers under regeneration that requires no log-probability access.
2. Superior Correctness Prediction: Empirical evidence across five models and four benchmarks (FrontierScience-Olympiad, HMMT Feb 2026, AIME 2025, Brumo 2025) showing that prefix consistency outperforms existing WMV baselines (DeepConf, P(True), Self-certainty) as a correctness predictor. It achieves the highest macro-averaged AUROC in 15 out of 20 (model, benchmark) settings.
3. Cost Efficiency: PC-WMV reaches the accuracy plateau of Standard MV using significantly fewer tokens. In cost-equivalent comparisons, PC-WMV achieves the same accuracy as Standard MV with a median of 4.6× fewer tokens, with savings reaching up to 21× on difficult benchmarks.
4. Robustness to Difficulty: Unlike baseline signals that degrade on hard problems, prefix consistency maintains a positive discrimination gap ($r_C > r_W$) even when Pass@1 is below 50%, allowing it to effectively reweight votes in regimes where Standard MV fails.

Results

• Discrimination Gap: Table 1 confirms that $r_C > r_W$ holds across all models and benchmarks. The discrimination gap $D$ is substantial (e.g., 43.7% on FrontierScience-Olympiad for GPT-OSS-120B), indicating a strong behavioral regularity where correct traces are more stable under regeneration.
• Accuracy vs. Cost: On the FrontierScience-Olympiad benchmark with GPT-OSS-120B, PC-cubic (cubic weighting) reaches Standard MV's plateau accuracy using only 0.05× of the tokens required by Standard MV (a 21× saving). Similar efficiency gains are observed on Ministral3-14B for AIME 2025.
• Comparison to Adaptive Stopping: PC-WMV is competitive with or superior to adaptive stopping baselines (Adaptive Consistency, Early-Stopping Self-Consistency) in terms of token efficiency, particularly on difficult tasks where adaptive methods often fail to reach high accuracy targets within the budget.
• Hyperparameter Sensitivity: The method is robust to the choice of truncation fraction $\tau$ and regeneration count $K$. The default setting ($\tau=0.75, K=1$) performs well across diverse benchmarks without extensive tuning.

Significance and Claims

The paper claims that regeneration stability is a practically useful test-time signal for aggregating votes, distinct from and often superior to confidence-based signals derived from log-probabilities or self-rating.

• Practical Utility: The method offers a cost-effective way to improve reasoning accuracy, particularly for difficult problems where standard self-consistency fails to find the correct answer.
• Theoretical Insight: The work highlights the "discrimination gap" $D$ as the key quantity governing the method's effectiveness. It demonstrates that the asymmetry in reproducibility between correct and incorrect traces is a fundamental property of reasoning models that can be exploited for aggregation.
• Limitations: The authors note that the method assumes access to an explicit CoT trace that can be truncated and continued, which may not apply to closed models with hidden reasoning. Additionally, the effectiveness depends on the existence of a meaningful gap between Pass@1 and the Standard MV plateau; if Pass@1 is already near the plateau, the gains from reweighting are limited.

In summary, the paper establishes that checking for the reproducibility of answers under prefix regeneration provides a reliable, log-probability-free signal that significantly improves the efficiency and accuracy of Chain-of-Thought aggregation.