Technical Summary: Self-Consistency via Marginal Sharpening

Problem Statement

Modern language models increasingly solve complex tasks by generating intermediate reasoning traces (e.g., derivations, code sketches, proof outlines) before emitting a final answer. While standard inference methods like Chain-of-Thought prompting elicit this behavior, they often rely on sampling a single trajectory or using post-hoc majority voting (self-consistency) to select the final answer.

The authors identify a fundamental limitation in existing inference-time sharpening methods, specifically power sampling. Power sampling sharpens the distribution over complete generated sequences (the joint distribution of reasoning trace $z$ and answer $a$). The paper argues this is the wrong level of abstraction for reasoning:

1. Latent Variable Entanglement: A reasoning trace is a latent computation. Many distinct traces can lead to the same correct answer.
2. Competing vs. Supporting: Sequence-level sharpening treats alternative derivations or implementations of the same solution as competitors, concentrating probability on specific complete transcripts rather than on the answer itself.
3. Brittleness of Voting: Standard self-consistency (majority voting) requires exact string matching. In structured domains like code or proofs, the same underlying solution can manifest in many surface forms (different variable names, control flows, or lemma orders), causing voting to fragment support across valid variations.

The core problem is how to leverage multiple reasoning traces to amplify the probability of the correct answer without requiring exact string agreement or incurring the computational cost of searching over full trajectories.

Methodology: Marginal Sharpening

The authors propose Marginal Sharpening, an inference-time objective that shifts the target from the joint distribution $\pi(z, a | x)$ to the sharpened answer marginal $p_{\alpha}^{marg}(a | x)$.

Theoretical Framework

1. Decomposition: The model completion $y$ is parsed into a reasoning trace $z$ and a final answer segment $a$. The model induces a natural answer marginal $m(a | x) = \sum_z \pi(z, a | x)$.
2. Target Distribution: Instead of sharpening the joint distribution, the method defines a power distribution over the answer marginal:
   $$p_{\alpha}^{marg}(a | x) = \frac{m(a | x)^\alpha}{\sum_{a'} m(a' | x)^\alpha}$$
   where $\alpha > 1$ is the sharpening strength. As $\alpha \to \infty$, this converges to the answer with the maximum marginal support (the ideal self-consistency target).
3. Integer-Power Representation: For integer sharpening strength $K$, the authors derive an exact decomposition using $K$ independent reasoning traces. The target distribution can be expressed as an expectation over $K$ independently sampled traces $z_{1:K}$:
   $$p_{K}^{marg}(a | x) \propto \mathbb{E}_{z_{1:K}} \left[ \prod_{i=1}^K \pi(a | x, z_i) \right]$$
   This formulation connects self-consistency to sampling from an answer-level target distribution.

Algorithm: Parallel Autoregressive Decoding

Directly sampling from the derived distribution is intractable because it requires summing over all possible future continuations (the "continuation normalizer"). The authors propose a lightweight parallel autoregressive decoding algorithm (Algorithm 1) that approximates this target:

1. Trace Generation: Generate $M = K \times S$ reasoning traces, grouped into $S$ sets of $K$ traces each.
2. Token-Level Approximation: Instead of computing the full sequence probability, the algorithm decodes the answer token-by-token. At each step $t$, it computes a weighted distribution over the vocabulary:
   $$q_t^{(S)}(v | x, a_{<t}) \propto \sum_{s=1}^S w_s(a_{<t}) \exp\left( \sum_{i=1}^K \log \pi(v | x, z_i^{(s)}, a_{<t}) \right)$$
   • Prefix Weights ($w_s$): These weights track the likelihood of the already generated answer prefix under each group of $K$ traces. They are updated online as tokens are sampled.
   • Local Approximation: The algorithm ignores the intractable "continuation normalizer" (the probability of future tokens), treating it as a common factor that cancels out during local normalization.
3. Sampling: The algorithm samples the next token from this distribution, updates the prefix weights, and repeats until the answer terminates.

This approach allows the model to generate a single answer that is "supported" by multiple reasoning paths, effectively performing soft self-consistency during generation rather than as a post-hoc voting step.

Key Contributions

1. Formulation of Marginal Sharpening: The paper defines an inference-time objective that treats reasoning traces as latent variables and sharpens the induced answer distribution, rather than the joint distribution of traces and answers.
2. Multi-Trace Decomposition: The authors demonstrate that for integer sharpening strengths, the sharpened answer marginal admits a decomposition into an expectation over $K$ independent reasoning traces, theoretically linking self-consistency to answer-level sampling.
3. Efficient Decoding Algorithm: They propose a parallel autoregressive algorithm that approximately samples from this sharpened distribution. It is purely autoregressive, requires no external canonicalizers, and avoids the quadratic token generation cost of sequence-level power sampling.
4. Empirical Validation: The method is evaluated on mathematical reasoning (MATH-500) and code generation (HumanEval+, LiveCodeBench) benchmarks.

Results

The experiments utilize Qwen family models (1.7B, 4B, 8B) across three benchmarks.

• Performance vs. Power Sampling: Marginal sharpening significantly outperforms standard power sampling on code generation benchmarks (HumanEval+ and LiveCodeBench). On MATH-500, it performs comparably to or slightly below majority voting (which is a strong baseline for math due to small answer spaces and symbolic verification).
• Efficiency: The method is orders of magnitude faster than power sampling for long generations. For $L=8192$, marginal sharpening was 38× faster than power sampling on the HumanEval+ benchmark while achieving higher accuracy. Power sampling requires $O(L^2)$ token generation due to resampling, whereas marginal sharpening requires $O(L)$.
• Hyperparameters:
  • Sharpening Strength ($K$): Increasing $K$ generally improves performance by concentrating probability on answers supported by multiple traces, though it increases computation.
  • Sample Count ($S$): Increasing $S$ (the number of trace groups) improves the quality of the token-level approximation, yielding consistent gains, particularly at lower generation budgets.
  • Budget Allocation: Under a fixed total compute budget ($K \times S = \text{const}$), different allocations between sharpening strength and sample count yield comparable results, suggesting a trade-off where aggressive sharpening and better approximation quality largely compensate for each other.

Significance and Claims

The paper claims that self-consistency should be understood as an answer-level inference principle rather than a post-hoc voting heuristic.

• Shift in Focus: By targeting the answer marginal, the method correctly aggregates support across diverse reasoning paths (e.g., different code implementations or proof strategies) that sequence-level methods treat as distinct, competing outputs.
• Scalability: The proposed algorithm enables the benefits of self-consistency in domains with large, structured output spaces (like code) where exact string matching fails, without the prohibitive computational cost of full trajectory search or resampling.
• Practicality: The method is a "soft" version of self-consistency that can be implemented with standard autoregressive models and parallel decoding, making it a practical alternative to temperature sampling and power sampling for reasoning tasks.

The authors conclude that test-time compute is more effectively spent on refining the answer belief induced by latent reasoning than on selecting the single most likely complete transcript.