GRAPHEVAL: New Graph Framework Finds Self-Consistency Hides Errors in LLM Reasoning

Researchers published a paper on arXiv in July 2026 presenting GRAPHEVAL, a framework for assessing the validity of language model reasoning. The main finding: the standard Self-Consistency method systematically overlooks logical errors because it compares only final answers and ignores the intermediate reasoning steps entirely.

Why Self-Consistency misses reasoning errors

Self-Consistency (SC) is one of the most popular ways to make language models more reliable. The principle is simple: the model generates several solutions to the same problem, then majority voting picks the most frequent final answer. This filters out random slips well, but it leaves a blind spot.

Several reasoning chains can easily reach the same answer through entirely different logical paths, including flawed ones. The model looks confident and a consensus is reached, yet the structure of the reasoning remains incoherent. The authors call this phenomenon "confident hallucinations": the model expresses no uncertainty, but its intermediate steps fail a check for logical coherence.

What GRAPHEVAL proposes

The framework recasts uncertainty quantification as a measurement of the logical validity of the entire reasoning space, not just the final answers. The authors introduce two new tools:

• GRCS (Graph Reasoning Coherence Score) is a metric that captures semantic and structural consensus in a graph representation of the reasoning. It detects both pathological mode collapse and confident hallucinations.
• GSC (Graph Self-Consistency) is a medoid-based decoding strategy. Instead of voting on the final answer, it selects the reasoning chain that is structurally closest to all the others.

GRCS turned out to be the only metric that correlates negatively and consistently with faulty reasoning, in both large and small models.

What the experiments showed

The authors tested the framework on models of different scales and recorded several key patterns:

• In small models, GSC clearly shows how much SC inflates accuracy through "lucky guesses": models often reach the right answer via a flawed path, and SC does not notice.
• In more powerful models, GSC maintains or improves accuracy while also increasing the logical validity of the reasoning.
• Adversarial medoid ablation confirmed that the path GSC selects is "load-bearing": forcing a deviation from it lowers reasoning validity and, in some cases, worsens answer accuracy.

What this means

Standard accuracy metrics and Self-Consistency mask a fundamental problem: language models can guess the right answer without being able to reason correctly. GRAPHEVAL provides tooling that separates "the ability to guess" from "the ability to think," and this changes the frame for comparing and evaluating language models in academic and applied contexts.

Frequently asked questions

How does GSC differ from standard Self-Consistency?

Standard SC takes the majority answer among all generated solutions. GSC selects the reasoning chain that is structurally closest to all the others (the medoid). This makes it possible to evaluate the logical path to an answer, not just the final result.

Does GRAPHEVAL apply to models of any size?

The authors tested the framework on models of different scales. GRCS showed a stable negative correlation with faulty reasoning across all tested models. The effect of GSC varies: in small models it exposes SC's inflated accuracy, while in more powerful ones it improves both metrics at once.