# Benchmarking graph construction by large language models for coherence-driven inference

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 105 references that are in the map.
- First posted on arXiv 19 Feb 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Phi-4 Technical Report](https://mlsanity.com/paper/2412.08905/) (2024)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought](https://mlsanity.com/paper/2210.01240/) (2022)
- [FOLIO: Natural Language Reasoning with First-Order Logic](https://mlsanity.com/paper/2209.00840/) (2022)
- [LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers](https://mlsanity.com/paper/2310.15164/) (2023)
- [Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens](https://mlsanity.com/paper/2401.17377/) (2024)
- [SatLM: Satisfiability-Aided Language Models Using Declarative Prompting](https://mlsanity.com/paper/2305.09656/) (2023)
- [LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench](https://mlsanity.com/paper/2409.13373/) (2024)
- [On the Existence of Simpler Machine Learning Models](https://mlsanity.com/paper/1908.01755/) (2019)
- [From Statistical Relational to Neurosymbolic Artificial Intelligence: a Survey](https://mlsanity.com/paper/2108.11451/) (2021)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [AR-LSAT: Investigating Analytical Reasoning of Text](https://mlsanity.com/paper/2104.06598/) (2021)
- [Transformers on Markov Data: Constant Depth Suffices](https://mlsanity.com/paper/2407.17686/) (2024)
- [A Closer Look at Classification Evaluation Metrics and a Critical Reflection of Common Evaluation Practice](https://mlsanity.com/paper/2404.16958/) (2024)
- [On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning](https://mlsanity.com/paper/2406.14197/) (2024)
- [Learning Latent Block Structure in Weighted Networks](https://mlsanity.com/paper/1404.0431/) (2014)
- [Machine learning and information theory concepts towards an AI Mathematician](https://mlsanity.com/paper/2403.04571/) (2024)
- [Getting from Generative AI to Trustworthy AI: What LLMs might learn from Cyc](https://mlsanity.com/paper/2308.04445/) (2023)
- [Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/1807.04974/) (2018)
- [Prospects for inconsistency detection using large language models and sheaves](https://mlsanity.com/paper/2401.16713/) (2024)
- [NLP-based Regulatory Compliance -- Using GPT 4.0 to Decode Regulatory Documents](https://mlsanity.com/paper/2412.20602/) (2024)
- [Goodness of fit testing based on graph functionals for homogenous Erd"os Renyi graphs](https://mlsanity.com/paper/2305.10380/) (2023)
- [A Neurosymbolic Fast and Slow Architecture for Graph Coloring](https://mlsanity.com/paper/2412.01752/) (2024)

## Built on by (most cited first, 2 of 2)

- [Coherence-driven inference for cybersecurity](https://mlsanity.com/paper/2509.18520/) (2025)
- [Automatic coherence-driven inference on arguments](https://mlsanity.com/paper/2509.18523/) (2025)

## Abstract (arXiv)

We devise an algorithm to generate propositions that objectively instantiate graphs supporting coherence-driven inference. We also benchmark the ability of large language models (LLMs) to reconstruct coherence graphs from (a simple transformation of) propositions expressed in natural language, with promising results from a single prompt to reasoning-optimized LLMs. For example, o1/3/4-mini achieve perfect reconstruction half of the time on sparse graphs. Coherence-driven inference on consistency evaluations by LLMs may advance machine cognition capabilities.