🤖 AI

Quantifying Consistency in LLM Logical Reasoning via Structural Uncertainty

This paper introduces "structural uncertainty," a framework that quantifies logical reasoning consistency in large language models by analyzing the stability of self-preference rankings among sampled solutions, revealing that this metric complements traditional answer dispersion to better identify unreliable reasoning in deductive tasks while distinguishing regimes where such consistency evaluation is informative.

Original authors: Baishali Chaudhury, Mengdie Flora Wang, Hyunji Hayley Park, Rahul Ghosh, Sungmin Hong, Jae Oh Woo

Published 2026-06-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Baishali Chaudhury, Mengdie Flora Wang, Hyunji Hayley Park, Rahul Ghosh, Sungmin Hong, Jae Oh Woo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are asking a very smart, but sometimes overconfident, student to solve a difficult math problem. You ask them to try solving it five different times.

The Old Way: Counting Answers
Traditionally, to see if the student is reliable, we just look at their five answers.

If they say "10" five times, we think, "Great! They are consistent."
If they say "10, 12, 9, 10, 11," we think, "Uh oh, they are confused."

But there's a problem. What if the student gets the answer wrong every single time, but for five different reasons?

Answer 1: "10" (because they forgot a minus sign).
Answer 2: "10" (because they added instead of subtracted).
Answer 3: "10" (because they misread the numbers).

To the old method, the student looks perfectly consistent because the final answer is always "10." But the thinking behind each answer was a mess. The old method misses this internal chaos.

The New Way: The "Self-Judge" Tournament
This paper introduces a new way to check the student, called Structural Uncertainty. Instead of just looking at the final answers, we ask the student to act as their own referee.

Here is the process:

Generate: The student writes down five different solutions (some might be right, some wrong).
Tournament: We ask the student to compare these solutions against each other in pairs. "Is Solution A better than Solution B?"
Ranking: We take all these comparisons and build a ranking. Who is the "best" solution? Who is the "worst"?
The Twist: We do this tournament multiple times, but we change the order of who fights whom (like drawing a random map of connections).

The Two Signals
By watching how the student ranks their own work, the authors found two distinct signals that tell us if the reasoning is stable:

The "Flip-Flop" Signal (Across-Trial Instability):
- Imagine: In one tournament, the student says Solution A is the best. In the next tournament (with a different set of matchups), they suddenly say Solution C is the best.
- Meaning: The student doesn't actually know what a "good" solution looks like. Their internal compass is spinning. This is a huge red flag, even if all five answers were the same number.
- Analogy: It's like a judge who picks the "best" movie in a lineup today, but picks a completely different one tomorrow, even though the movies haven't changed. The judge is unreliable.
The "Tie-Breaker" Signal (Within-Trial Ambiguity):
- Imagine: In a single tournament, the student looks at all five solutions and says, "They are all pretty good, I can't really pick a winner." The ranking is a flat line.
- Meaning: This is actually a good sign for complex math problems! It means there are multiple valid ways to solve the problem, and the student recognizes that. It shows they understand the nuance.
- Analogy: It's like a food critic saying, "These five pizzas are all excellent; I can't pick just one." That's a sign of a sophisticated palate, not confusion.

The "Library" vs. The "Math Class"
The paper discovered that this new method works differently depending on the type of task:

In Math/Logic (The "Math Class"): The method shines. If the student is confused, their rankings flip-flop wildly. If they are smart, they can distinguish between good and bad paths.
In Fact-Checking (The "Library"): The method hits a wall. Imagine asking the student to find a specific fact in a library of books. If the books don't have the answer, the student will say "I don't know" every time.
- Because the answer is "I don't know," the student's internal ranking becomes a perfect flat line (everyone is tied for last place).
- The paper calls this a "Collapse." The signal disappears. The method realizes, "Oh, this isn't a reasoning problem; it's a retrieval problem." In these cases, the old method (just checking if answers differ) is actually better.

The Bottom Line
This paper doesn't just ask, "Did the AI get the right answer?" or "Did it give the same answer five times?"

Instead, it asks, "Does the AI have a stable, consistent way of judging its own work?"

If the AI's internal rankings are shaky and flip-flopping, it's likely reasoning poorly, even if the final answer looks right.
If the AI's rankings are stable, it's likely reasoning well.
If the AI's rankings collapse into a flat tie, it might be a task where reasoning doesn't matter (like looking up a fact that isn't there).

This helps us spot "smart-sounding" failures where the AI is confidently wrong but internally inconsistent, a problem that older methods completely missed.

Technical Summary: Quantifying Consistency in LLM Logical Reasoning via Structural Uncertainty

Problem Statement

Large Language Models (LLMs) frequently exhibit a failure mode in multi-step deductive reasoning where they arrive at the same incorrect conclusion through different, internally flawed reasoning paths. Existing post-hoc evaluation methods primarily assess reliability through output dispersion (measuring the semantic variation or entropy of sampled answers). While useful, this approach discards a critical complementary signal: the structural consistency of the model's internal preferences among competing reasoning candidates.

Current dispersion-based methods fail to detect "systematic but internally unstable" reasoning. For instance, if a model generates five candidates that all agree on a wrong answer, dispersion-based metrics report low uncertainty (zero entropy), masking the fact that the model's internal ranking of these candidates may be highly unstable. This paper addresses the need for an evaluation framework that measures not just what answers differ, but how consistently the model ranks competing reasoning solutions for the same query.

Methodology: Structural Uncertainty Framework

The authors propose Structural Uncertainty, a consistency-aware evaluation framework that quantifies the stability of self-preference-induced rankings over sampled candidate solutions. The framework operates in a fully black-box setting without requiring access to model internals (logits or hidden states).

1. Pipeline Overview

Given a query $x$ :

Candidate Generation: The model generates $N$ diverse candidate reasoning solutions ( $N=5$ ) using stochastic decoding and distinct prompt templates (e.g., step-by-step, think-aloud, Socratic, decomposition, analogical).
Self-Preference Elicitation: The same model acts as a judge to determine pairwise preferences among its own outputs. To reduce computational cost from $O(N^2)$ to $O(N)$ , the authors sample a uniform random spanning tree over the $N$ candidates for each trial, querying only the $N-1$ edges.
Preference Aggregation:
- Bradley-Terry Modeling: Pairwise judgments are modeled using the Bradley-Terry (BT) framework with $L_2$ regularization to infer latent utilities $\theta_i$ for each candidate.
- PageRank Normalization: The inferred pairwise win probabilities are converted into a transition matrix, and the stationary distribution (PageRank score $\pi$ ) is computed to produce a global ranking distribution for that trial.
- Robustness Check: A TrueSkill variant (Bayesian skill rating with confidence-weighted updates) is also implemented, yielding highly similar results.
Uncertainty Decomposition: The process is repeated for $M$ $M$ independent trials (spanning tree samples). The resulting ensemble of ranking distributions $\{\pi^{(m)}\}_{m=1}^M$ ${π^{(m)}}_{m = 1}^{M}$ is decomposed into two entropy-based components:
- Within-Trial Candidate Ambiguity ( $StructU_{within}$ ): The average entropy of the ranking distribution within a single trial. High values indicate the model cannot confidently distinguish between candidates even within a single comparison set.
- Across-Trial Ranking Instability ( $StructU_{across}$ ): The difference between the total entropy of the mean ranking and the average within-trial entropy. High values indicate that the model's preferred ranking fluctuates significantly depending on the specific set of comparisons (spanning tree) sampled.

2. Integration with Self-Consistency

The framework combines structural uncertainty with standard Self-Consistency Uncertainty (entropy of the answer distribution). The authors propose a fixed empirical fusion rule:

$StructU_{across}$ correlates negatively with accuracy (instability $\to$ failure), so it is added to Self-Consistency entropy.
$StructU_{within}$ correlates positively with accuracy on reasoning tasks (ambiguity among plausible paths), so it is subtracted from Self-Consistency entropy.

Key Contributions

A Post-Hoc Consistency Framework: A model-agnostic method to quantify reasoning consistency via the stability of self-preference rankings, providing a signal complementary to output dispersion.
Structural Decomposition: The decomposition of uncertainty into across-trial instability (signaling unreliable reasoning) and within-trial ambiguity (signaling competitive plausible paths), derived via Bradley-Terry/TrueSkill and PageRank.
Regime Analysis: A characterization of when structural signals are informative versus when they collapse. The paper identifies a "regime boundary" where reasoning-level consistency evaluation becomes uninformative.

Experimental Results

The framework was evaluated across five LLMs (including Claude 4.5 Sonnet, DeepSeek R1, GPT-OSS 20B, Amazon Nova Premier, Qwen 3 32B) and eight benchmarks (Math-Synth, MATH-500, AMC-23, AIME-24/25, MMLU-Pro, TruthfulQA, HotpotQA).

1. Complementarity on Reasoning Tasks

On mathematical and logical reasoning benchmarks (e.g., Math-Synth, MATH-500, AMC-23), combining structural uncertainty with self-consistency significantly improves the identification of unreliable reasoning instances (measured by Selective Prediction AUC and AUROC).

Performance Gains: The hybrid estimator ($StructU + SelfConsU$) achieved the highest or second-highest performance on most reasoning tasks, with gains up to +13.4% for weaker models on hard contest problems.
Correlation with Accuracy:
- Across-trial instability showed a strong negative correlation with correctness (instability signals failure).
- Within-trial ambiguity showed a positive correlation with correctness on math tasks, consistent with scenarios where multiple valid solution paths exist.

2. Collapse on Retrieval Tasks

On factual retrieval tasks (specifically HotpotQA), the structural signal collapsed.

Observation: Both correct and incorrect questions exhibited near-zero across-trial uncertainty and near-maximum within-trial uncertainty (uniform PageRank distributions).
Mechanism: Factual retrieval over fixed documents elicits structurally homogeneous reasoning chains regardless of the prompt template. The model's self-preference judgments become indistinguishable (coin-flip), rendering the structural signal uninformative.
Implication: In this regime, dispersion-based methods (like Self-Consistency or Semantic Dispersion) outperform the structural approach. The collapse itself serves as a diagnostic signature indicating the absence of reasoning-level structural diversity.

3. Ablation and Validation

Randomization: Replacing real self-preferences with random comparisons caused AUROC to drop to near-chance levels, confirming the signal relies on genuine model preferences, not pipeline artifacts.
Backend Robustness: Both Bradley-Terry and TrueSkill backends produced consistent rankings ( $\rho > 0.95$ ), validating the decomposition as a property of the ranking distribution rather than a specific model choice.

Significance and Claims

The paper claims that Structural Uncertainty is best understood not as a universal confidence estimator, but as a regime-sensitive evaluator of logical reasoning consistency.

Reframing Evaluation: It shifts the question from "How much do responses differ?" (dispersion) to "How consistently does the model rank competing reasoning solutions?" (structure).
Diagnostic Utility: The framework provides a practical diagnostic for practitioners. The "HotpotQA signature" (near-zero across-trial uncertainty + high within-trial entropy) indicates a task regime where reasoning-level consistency evaluation is futile, suggesting a switch to dispersion-based methods.
Limitations: The authors modestly note that the method increases inference cost ( $N \times M$ comparisons) and that self-preferences inherit model-specific biases. The decomposition is empirical and observable under a fixed protocol, not a fundamental identification of underlying data uncertainty. The method is most effective when responses differ in reasoning quality; it fails when variation is purely stylistic or when the task structure (e.g., deterministic retrieval) suppresses reasoning diversity.

In conclusion, the paper demonstrates that measuring the stability of a model's internal preference ordering over its own outputs provides a critical, complementary view of reasoning reliability, particularly for detecting systematic errors that answer-level agreement alone cannot reveal.