Technical Summary: Can We Trust LLM's Logic? Quantifying Uncertainty, Coherence, and Robustness via a Graph-Based Framework

1. Problem Statement

Large Language Models (LLMs) frequently produce plausible but unfaithful reasoning, often termed "hallucinations," which can be confidently incorrect. Current decoding strategies, particularly Self-Consistency (SC), rely on majority voting over final answers to improve accuracy. However, SC evaluates only the agreement of the final output, ignoring the logical validity of intermediate steps. This allows "lucky guesses"—where flawed, illogical, or contradictory reasoning paths coincidentally converge on the correct answer—to artificially inflate accuracy metrics. In mission-critical domains (e.g., medicine, law, finance), this lack of reasoning fidelity poses significant risks.

The paper identifies three core challenges:

1. Uncertainty Quantification (UQ): How to reliably quantify uncertainty in LLM reasoning processes that captures structural collapse and confident hallucinations, rather than just token-level probability.
2. Faithful Decoding: Whether semantic and structural awareness can filter out unfaithful "lucky guesses" that naïve majority voting misses.
3. Robustness: How robust the reasoning topology is under adversarial conditions, specifically when dominant reasoning paths are removed.

2. Methodology: GRAPHEVAL

The authors propose GRAPHEVAL, a graph-based reasoning framework that transforms raw text generations into analyzable topological structures to evaluate reasoning fidelity holistically. The pipeline consists of five stages:

A. Causal Fact Decomposition and DAG Construction

• Generation: A Generator LLM ($G_{LLM}$) produces $N$ Chain-of-Thought (CoT) traces at high temperature to capture reasoning diversity.
• Annotation: Each step is annotated with direct causal dependencies (e.g., [depends_on: 0, 1]).
• Decomposition: A distinct Decomposer LLM ($D_{LLM}$), operating at deterministic temperature, breaks coarse steps into granular Subject-Verb-Object atomic facts while preserving the original causal dependencies.
• Graph Representation: The output is mapped to a Directed Acyclic Graph (DAG) $G = (V, E)$, where nodes are atomic facts and edges represent causal dependencies.

B. Semantic-Structural Distance Computation (SS-GED)

To measure consistency across the reasoning manifold, the framework computes pairwise distances between all DAGs using an extended Graph Edit Distance (GED).

• Optimization: Instead of NP-hard A* search, the authors use the Hungarian algorithm ($O(m^3)$) for efficient bipartite matching.
• Cost Function: Substitution costs are based on cosine distance between node/edge embeddings.
• Improvements:
  • Fair Normalization: Scales edit costs by the average graph size to handle varying lengths.
  • Semantic-Structural Blending: Combines structural similarity with the semantic similarity of terminal nodes (conclusions). The final similarity score $S(G_i, G_j)$ is a weighted blend of terminal-node cosine similarity and a Radial Basis Function (RBF) transform of the normalized edit distance.

C. Graph Reasoning Coherence Score (GRCS)

GRCS is a novel UQ metric defined as the inverse of the mean pairwise distance across the reasoning manifold:
$$\text{GRCS} = \frac{1}{1 + \mu(D(q))}$$
where $D(q)$ is the set of pairwise distances. GRCS quantifies semantic-structural consensus. It is designed to detect mode collapse (repetitive, flawed shortcuts) and confident hallucinations (fabricated facts leading to disconnected conclusions), which increase the average pairwise distance.

D. Graph Self-Consistency (GSC)

GSC is a decoding strategy that selects the medoid CoT—the path most central and supported within the semantic-structural graph manifold—rather than the most frequent final answer.

• Selection Criteria: The medoid $z^*$ maximizes a score combining Structural Centrality (total similarity to other graphs) and Graph-level Consensus (fraction of other graphs containing semantically similar nodes, weighted heavily for terminal nodes).
• Goal: To trade nominal accuracy for reasoning fidelity, filtering out unfaithful paths that happen to yield the correct answer.

E. Adversarial Medoid Ablation

To test robustness, the framework employs a prompt-poisoning attack that explicitly forbids the model from reusing the GSC-selected medoid path. This forces the model to generate alternative reasoning paths, allowing the authors to measure if accuracy drops or if "lucky guesses" emerge when the primary "load-bearing" path is removed.

3. Key Contributions

1. GRCS Metric: A distributional uncertainty metric based on SS-GED that consistently shows a negative correlation with reasoning faithfulness across model scales, effectively capturing hidden uncertainty in flawed reasoning paths where traditional metrics (dispersion, entropy, Topo-UQ) fail.
2. GSC Decoding Strategy: A structural decoding method that isolates "lucky guesses." Empirical results show it significantly reduces unfaithful reasoning in smaller models (e.g., Llama 3.1 8B) while preserving or improving accuracy in more capable models (e.g., DeepSeek R1).
3. Adversarial Robustness Findings: The study demonstrates that the GSC-selected medoid acts as a "load-bearing path." Forcing models away from this path often degrades reasoning faithfulness, even if accuracy is temporarily maintained via flawed shortcuts.

4. Experimental Results

The framework was evaluated across five datasets (GSM8K, BoolQ, StrategyQA, MedQA, GPQA) and three models (Llama 3.1 8B, Phi-4, DeepSeek R1).

• Uncertainty Quantification: GRCS was the only metric to remain negatively correlated with faithfulness in 93% (14/15) of configurations. Baselines like dispersion and entropy often showed positive or weak correlations, mistaking repetitive flawed reasoning for confidence.
• Decoding Performance:
  • Small Models (Llama 3.1 8B): GSC caused significant accuracy drops (e.g., -7.6% on GSM8K, -9.0% on MedQA) compared to SC. This indicates that SC's high accuracy was inflated by unfaithful "lucky guesses" which GSC successfully filtered out.
  • Capable Models (DeepSeek R1): GSC maintained or slightly improved accuracy across all datasets, suggesting that for larger models, the structurally central path aligns more closely with the correct answer.
• Audit of Disagreements: In cases where SC and GSC disagreed, GSC-selected answers were significantly more likely to be faithful (79.5% vs. 57.6% for SC).
• Adversarial Ablation: When the medoid path was ablated, smaller models exhibited a strong negative correlation between accuracy gains and faithfulness drops, empirically confirming the "lucky guess" phenomenon. Larger models showed less correlation but still exhibited faithfulness degradation when accuracy was preserved.

5. Significance and Claims

The paper argues that LLM trustworthiness cannot be judged by answer agreement alone. By modeling sampled CoTs as DAGs, the authors demonstrate that reasoning structure reveals critical signals of uncertainty and robustness that final-answer consensus obscures.

• Shift in Paradigm: The work motivates a shift from evaluating final-output frequency to reasoning-level analysis, particularly for mission-critical settings where errors have catastrophic consequences.
• Role of Medoids: The GSC-selected medoid is identified not just as a statistical average, but as a "load-bearing" structure essential for reliable deduction.
• Limitations: The authors acknowledge that GRAPHEVAL has higher time complexity ($O(N^2 \cdot m^3)$) than SC and that its statistical strength diminishes on very large, capable models (like DeepSeek R1) which exhibit broader, high-entropy reasoning topologies. The framework is currently optimized for short-horizon benchmarks (3–6 steps), and scalability to long-context, highly compositional tasks remains an open question.

In summary, GRAPHEVAL provides a rigorous, graph-based mechanism to quantify reasoning fidelity, offering a more reliable alternative to standard decoding strategies for ensuring trustworthy LLM deployment.