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

Large Language Models (LLMs) often produce correct final answers through flawed or unfaithful reasoning, a phenomenon known as a "lucky guess." Existing methods like Self-Consistency (SC) rely on majority voting of final answers, which fails to detect these logical inconsistencies. This paper asks: How can we reliably quantify uncertainty in LLM reasoning, filter out unfaithful "lucky guesses," and assess the robustness of reasoning topologies?

The authors propose GRAPHEVAL, a framework that treats LLM reasoning as a graph-based structure. First, they use a Decomposer LLM to convert raw text reasoning into a Directed Acyclic Graph (DAG) of atomic facts and causal dependencies. They then introduce the Graph Reasoning Coherence Score (GRCS), a metric based on Semantic-Structural Graph Edit Distance (SS-GED) that measures the consensus within a model's reasoning manifold. Finally, they introduce Graph Self-Consistency (GSC), a decoding strategy that selects the "medoid" reasoning path—the most central and supported path in the graph—rather than simply picking the most frequent final answer.

• GRCS Reliability: GRCS consistently shows a negative correlation with reasoning faithfulness across various model sizes (from 8B to 70B parameters), outperforming baseline uncertainty metrics like simple dispersion or entropy.
• GSC vs. SC: GSC effectively filters out unfaithful "lucky guesses" that often inflate the accuracy scores of smaller models under standard majority voting.
• Load-Bearing Paths: Through adversarial ablation, the authors demonstrate that the GSC-selected medoid path acts as a "load-bearing" structure; forcing the model to deviate from this path significantly degrades reasoning faithfulness and, in many cases, reduces task accuracy.

This work shifts the evaluation of LLM trustworthiness from final-answer accuracy to holistic reasoning fidelity. By providing a way to quantify when a model is "guessing" versus "reasoning," GRAPHEVAL offers a path toward more reliable deployment of LLMs in mission-critical environments where the logical process is as important as the final result.