Structural Uncertainty: LLM logical reasoning consistency

Baishali Chaudhury and five coauthors published a paper titled "Quantifying Consistency in LLM Logical Reasoning via Structural Uncertainty," submitted on 15 Jun 2026, that defines a new consistency-aware signal for large language models called structural uncertainty. The paper, accepted as best paper at the ICLR 2026 Workshop on Logical Reasoning of Large Language Models, proposes ranking the model's own sampled reasoning solutions to assess whether its multi-step deductions are stable or contradictory.

What is structural uncertainty and how is it computed?

Structural uncertainty is a consistency-aware framework derived from the stability of self-preference-induced rankings over sampled reasoning solutions. The authors generate multiple candidate solutions for a query, ask the model to judge pairwise preferences among its own outputs, and aggregate those self-preferences into ranking distributions via Bradley-Terry modeling with PageRank. The framework decomposes the resulting signal into two entropy-based components: across-trial ranking instability and within-trial candidate ambiguity. Those two components separate whether the model flips the relative order of candidates across sampling trials or whether multiple candidates remain competitively plausible within a single trial.

How did the authors test structural uncertainty and what did they find?

The paper evaluates structural signals across five LLMs and eight benchmarks and compares them to traditional answer-dispersion measures. On logical and mathematical reasoning tasks the authors report that combining structural signals with answer dispersion improves identification of unreliable instances. By contrast, on factual retrieval tasks the structural signal "collapses toward uniformity," which the authors use to diagnose a regime boundary where reasoning-level consistency evaluation is uninformative. The two entropy components also relate differently to accuracy: within-trial ambiguity correlates positively with correctness, while across-trial instability correlates negatively with correctness.

Why it matters

Structural uncertainty reframes reliability from output variance to the model's ability to rank and prefer its own reasoning paths. The paper shows that a ranking-based, self-judgment signal adds complementary information to output dispersion on multi-step deductive tasks, identifying instances where the model's reasoning is internally unstable even if answers repeat. The contrasting correlations of the two components mean a single confidence scalar will miss important distinctions: within-trial ambiguity can indicate multiple plausible solution paths, while across-trial instability flags unreliable reasoning.

What to watch

Watch whether structural uncertainty generalizes beyond the five LLMs and eight benchmarks in the paper, and whether practitioners adopt pairwise self-preference rankings in reliability pipelines for complex reasoning. Another concrete signal will be whether the structural signal remains informative on task classes that the authors identified as collapsing toward uniformity, notably factual retrieval, which would confirm the paper's suggested regime boundary.

References and concrete facts from the paper: the work is indexed as arXiv:2606.17312, submitted on 15 Jun 2026, and was published at the ICLR 2026 Workshop on Logical Reasoning of Large Language Models where it was accepted as best paper. The evaluation used five LLMs and eight benchmarks and decomposed structural signals into across-trial ranking instability and within-trial candidate ambiguity, aggregated via Bradley-Terry modeling with PageRank.