Large Language Models (LLMs) can exhibit flawed and unreliable reasoning, which decoding strategies like Self-Consistency (SC) fail to detect, as they only evaluate final-answer agreement while ignoring the logical validity of intermediate steps. This raises three fundamental questions: How can we reliably quantify uncertainty in LLM reasoning? Can semantic, structural, and causal awareness select more faithful reasoning compared to naive majority voting? And how robust is reasoning topology under adversarial conditions? To address these questions, we introduce GRAPHEVAL, a graph-based reasoning framework that reframes uncertainty quantification (UQ) as a holistic reasoning fidelity problem.
We propose a novel UQ metric, Graph Reasoning Coherence Score (GRCS), which quantifies semantic-structural consensus of the reasoning space and captures pathological mode collapse and confident hallucinations. We find that GRCS is the only metric that is consistently negatively correlated with reasoning faithfulness across both more capable and smaller models. Additionally, we introduce Graph Self-Consistency (GSC), a medoid-based decoding strategy that trades nominal accuracy for reasoning fidelity, exposing the degree to which SC is inflated by unfaithful lucky guesses in smaller models while preserving or improving accuracy in more capable ones. Finally, through adversarial medoid ablation, we demonstrate that the GSC-selected path acts as a 'load-bearing path,' and forcing models away from it degrades reasoning faithfulness and, in some cases, causes drops in accuracy.
Blogger's Review: This paper introduces an innovative graph-based framework to quantify uncertainty and robustness in LLM reasoning, emphasizing structural and semantic coherence in the reasoning process. This approach not only enhances our understanding of LLM reasoning but also provides new directions for future research. The introduction of the GRCS metric is significant for assessing model fidelity and warrants further exploration.