# Beyond Semantic Equivalence: Logical Graphs for LLM Uncertainty Quantification

arXiv: https://arxiv.org/abs/2607.16868 · HTML: https://mlsanity.com/paper/2607.16868/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 47 references that are in the map.
- First posted on arXiv 18 Jul 2026.

## Builds on (most cited first, 30 of 30)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [A Survey of Large Language Models](https://mlsanity.com/paper/2303.18223/) (2023)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Know What You Don't Know: Unanswerable Questions for SQuAD](https://mlsanity.com/paper/1806.03822/) (2018)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [Teaching Models to Express Their Uncertainty in Words](https://mlsanity.com/paper/2205.14334/) (2022)
- [The Falcon Series of Open Language Models](https://mlsanity.com/paper/2311.16867/) (2023)
- [Unsupervised Quality Estimation for Neural Machine Translation](https://mlsanity.com/paper/2005.10608/) (2020)
- [On Hallucination and Predictive Uncertainty in Conditional Language Generation](https://mlsanity.com/paper/2103.15025/) (2021)
- [Fact-Checking the Output of Large Language Models via Token-Level Uncertainty Quantification](https://mlsanity.com/paper/2403.04696/) (2024)
- [SelfCheck: Using LLMs to Zero-Shot Check Their Own Step-by-Step Reasoning](https://mlsanity.com/paper/2308.00436/) (2023)
- [Kernel Language Entropy: Fine-grained Uncertainty Quantification for LLMs from Semantic Similarities](https://mlsanity.com/paper/2405.20003/) (2024)
- [LLM4Drive: A Survey of Large Language Models for Autonomous Driving](https://mlsanity.com/paper/2311.01043/) (2023)
- [A Survey on Code Generation with LLM-based Agents](https://mlsanity.com/paper/2508.00083/) (2025)
- [LUQ: Long-text Uncertainty Quantification for LLMs](https://mlsanity.com/paper/2403.20279/) (2024)
- [Factuality of Large Language Models: A Survey](https://mlsanity.com/paper/2402.02420/) (2024)
- [A Survey of Uncertainty Estimation Methods on Large Language Models](https://mlsanity.com/paper/2503.00172/) (2025)
- [A Survey of Uncertainty Estimation in LLMs: Theory Meets Practice](https://mlsanity.com/paper/2410.15326/) (2024)
- [Are Large Language Models More Honest in Their Probabilistic or Verbalized Confidence?](https://mlsanity.com/paper/2408.09773/) (2024)
- [A Head to Predict and a Head to Question: Pre-trained Uncertainty Quantification Heads for Hallucination Detection in LLM Outputs](https://mlsanity.com/paper/2505.08200/) (2025)
- [LoGU: Long-form Generation with Uncertainty Expressions](https://mlsanity.com/paper/2410.14309/) (2024)
- [Semantic Energy: Detecting LLM Hallucination Beyond Entropy](https://mlsanity.com/paper/2508.14496/) (2025)
- [Prompt-Reverse Inconsistency: LLM Self-Inconsistency Beyond Generative Randomness and Prompt Paraphrasing](https://mlsanity.com/paper/2504.01282/) (2025)
- [SeSE: Black-Box Uncertainty Quantification for Large Language Models Based on Structural Information Theory](https://mlsanity.com/paper/2511.16275/) (2025)
- [Survey of GenAI for Automotive Software Development: From Requirements to Executable Code](https://mlsanity.com/paper/2507.15025/) (2025)
- [Shapley Uncertainty in Natural Language Generation](https://mlsanity.com/paper/2507.21406/) (2025)

## Abstract (arXiv)

Large Language Models often produce confidently stated yet unreliable outputs, posing critical challenges for deployment in safety-sensitive applications. Existing uncertainty metrics such as semantic entropy capture agreement at the level of semantic equivalence, but largely ignore the logical relationships between distinct answers. As a result, they tend to overestimate uncertainty and falsely flag hallucinations in settings where generated responses are diverse in form yet logically compatible (e.g., differing only in granularity or specificity). We propose Logical Graph Uncertainty (LGU), a framework that explicitly models implication and incompatibility among answers. LGU aggregates probability mass along entailment chains onto the most specific hypotheses the answers support, measures the entropy of the resulting distribution, and penalizes mutual incompatibility among those hypotheses. Across multiple question-answering benchmarks and model families, LGU ranks first on average among existing uncertainty measures, with its largest gains---up to +7.1% AUROC and +3.5% AUARC over semantic entropy---on questions whose sampled answers are logically structured.