Can We Trust LLM’s Logic Quantifying Uncertainty Coherence and Robustness via a Graph Based Framework

Jul 16, 2026

Large Language Models can produce plausible yet unfaithful reasoning, while common decoding like Self-Consistency checks only final answer agreement and overlooks the logical validity of intermediate steps. The work addresses how to quantify uncertainty in reasoning, whether semantic/structural/causal awareness can filter unfaithful “lucky guesses” beyond majority voting, and how reasoning topology behaves under adversarial perturbations. It introduces GRAPHEVAL, a graph based framework with the Graph Reasoning Coherence Score and a medoid based Graph Self-Consistency decoding strategy, plus adversarial ablations to test robustness.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages42

Reading Time1 h 46 min

Introduction

Background on hallucinations and trust limitations

Chain-of-Thought and Self-Consistency decoding

Motivation for graph-based reasoning evaluation

Proposed Framework

GRAPHEVAL: graph-based reasoning fidelity

Graph Reasoning Coherence Score (GRCS)

Graph Self-Consistency (GSC)

Evaluation Focus

Uncertainty quantification and faithfulness correlation

Filtering unfaithful “lucky guesses”

Adversarial topology ablation and robustness

arXiv :2607 .080 17v 1 [ cs .CL] 9 Jul 2026 Can We Trust LLM’s Logic? Quantifying Uncertainty, Coherence, and Robustness via a Graph-Based Framework Riccardo Revalor¶ , Jalees Rehman‡, Debjit Pal¶ ¶ Department of Electrical and Computer Engineering ‡Department of Biochemistry and Molecular Genetics University of Illinois Chicago Chicago, IL 60607, USA {rreva, jalees, [dpal2}@uic.edu](dpal2}@uic.edu) Abstract Large-Language Models (LLMs) can be prone to flawed and unfaithful reasoning that decoding strategies like Self-Consistency (SC) fail to detect as they evaluate only 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 naïve majority voting? and How robust is reasoning topology under adversarial conditions? To address these questions, we introduce GRAPHEVAL, a graph-based reasoning framework that re-frames uncertainty quantification (UQ) as a holistic reasoning fidelity problem. We propose a novel UQ metric, Graph Reasoning Coherence Score (GRCS), that 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 targeted cases, causes drops in accuracy. 1 Introduction In recent years, Large-Language Models (LLMs) have achieved remarkable success across different domains through a single model, often generalizing to new tasks in zero-shot and few-shot settings (Brown et al., 2020; Zhao et al., 2023) . Nevertheless, their trustworthiness is limited by their tendency to produce plausible but fabricated reasoning, colloquially known as hallucinations, often doing so with high statistical confidence (Ji et al., 2023) . Such a lack of trustworthiness have severely restricted their deployment in mission-critical environments (Huang et al., 2020) . To increase LLMs performance, Chain-of-Thought (CoT) prompting was introduced (Wei et al., 2022), with the goal of enabling them to decompose complex problems into intermediate steps, and articulate reasoning in a humanlike additive way (Kahneman, 2011; Ziabari et al., 2025; de Varda et al., 2025) . Decoding strategies that mimic human-like reasoning, e.g., Self Consistency (SC) (Wang et al., 2023b), have been widely used to sample LLM answers. SC samples multiple reasoning pathsand selects the most frequent final answer, assuming that reasoning agreement ultimately leads to correctness. However, SC applies majority voting to the final output, marginalizing the different CoTs, making it highly vulnerable to unfaithful reasoning. In certain cases, hallucinations actively contribute to the “lucky guess”, in which a LLM may follow flawed, illogical, or even contradictory reasoning processes, yet yield the correct answer. While the answer may be correct, the unreliability of this process fundamentally threatens the model’s trustworthiness and robustness. In mission critical settings where errors can lead to catastrophic physical (Shen et al., 2023), financial (Chen & Hu, 2025), or legal (Linna & Linna, 2026) consequences, empirical performance alone is insufficient (Morey et al., 2025) . We hypothesize that quantifying reasoning coherence and uncertainty in

FAQs

What does Graph Self-Consistency (GSC) do under decoding?

GSC uses a medoid-based decoding strategy that trades nominal accuracy for improved reasoning fidelity. Adversarial medoid ablation shows the selected reasoning path can act as a “load-bearing path,” and forcing away from it degrades faithfulness and can reduce accuracy in targeted cases.

Jul 16, 2026

Upload by Genevieve