Research map / Large language models / Retrieval and knowledge
Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GCR, which constrains LLM decoding with a KG-Trie of KG reasoning paths so a fine-tuned small KG-specialized LLM generates faithful paths and answers, then a general LLM aggregates them for zero-hallucination KGQA.
Problem
LLM reasoning over knowledge graphs is unfaithful (hallucinated paths and facts) and existing retrieval-based and agent-based KG-enhanced methods are inaccurate and costly at scale.
Approach
Build a trie over tokenized KG paths (within L hops of question entities) and use it as a logit constraint during beam-search decoding, so the LLM can only emit paths that exist in the KG; a general LLM then performs inductive reasoning over the top-K paths and hypothesis answers.
Key results
- GCR (Llama-3.1-8B + GPT-4o-mini) reaches 92.2 Hit and 74.1 F1 on WebQSP and 75.8 Hit and 61.7 F1 on CWQ, the best reported in its table.
- GCR achieves a 100% faithful reasoning ratio on both WebQSP and CWQ with KG constraints, versus lower ratios without them (48.1% on CWQ).
- Zero-shot transfer with the Freebase-trained model improves over the base general LLM by 8.2% on FreebaseQA and 7.6% on CSQA accuracy, with a smaller gain on MedQA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use GCR with Llama-3.1-8B and GPT-4o-mini instead of the strongest baseline | KGQA · WebQSP | Hit: 90.7 -> 92.2 | Helped |
| use GCR with Llama-3.1-8B and GPT-4o-mini instead of the strongest baseline | KGQA · CWQ | Hit: 68.7 -> 75.8 | Helped |
| add the KG-specialized LLM to GCR (ablation) | GCR · WebQSP | F1: 52.9 -> 73.2 | Helped |
| add the KG-specialized LLM to GCR (ablation) | GCR · CWQ | F1: 37.5 -> 60.9 | Helped |
| add the General LLM to GCR (ablation) | GCR · WebQSP | F1: 57.0 -> 73.2 | Helped |
| add the General LLM to GCR (ablation) | GCR · CWQ | F1: 39.4 -> 60.9 | Helped |
| remove KG constraints during graph-constrained decoding (ablation) | GCR · WebQSP and CWQ | faithful reasoning ratio: 100% to 48.1% on CWQ | Hurt |
| increase beam size from 10 to 20 (ablation) | GCR · WebQSP | F1 | Hurt |
| increase beam size (ablation) | GCR · WebQSP | Hit and recall | Helped |
| fine-tune a 0.5B KG-specialized LLM instead of using it without fine-tuning (ablation) | KG-specialized LLM · WebQSP | Hit: 87.48 | Helped |
| use GCR instead of the base model | zero-shot KGQA · FreebaseQA, CSQA, and MedQA | accuracy | Helped |
Surprising findings
- A fine-tuned 0.5B Qwen2 KG-specialized LLM outperforms the 70B Llama-3.1 after fine-tuning in the paper's ablation.
- Without KG constraints, the reasoning on CWQ remains largely unfaithful (48.1% faithful ratio) even when the answers are correct.
Limitations
- Relies on the KG subgraph within a fixed hop limit (2 hops) and on entity linking, so paths beyond the trie cannot be generated.
- Zero-shot gains are smaller on the specialized medical KG (MedQA), suggesting limited transfer to domain-specific KGs.
- Still depends on a closed-source general LLM (ChatGPT or GPT-4o-mini) for final inductive reasoning.
Experimental setup
Datasets: WebQSP CWQ FreebaseQA CSQA MedQA Freebase ConceptNet UMLS-based medical KG
Benchmarks: WebQSP CWQ FreebaseQA CSQA MedQA
Metrics: Hit F1 accuracy precision recall faithful reasoning ratio runtime LLM calls LLM tokens
Baselines: RoG GNN-RAG GNN-RAG+RA ToG EffiQA ReaRev UniKGQA ChatGPT+Self-Consistency
Builds on: chain-of-thought RoG FiD ToG
Closest papers by meaning
- Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.94)
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph (ICLR 2024 · similarity 0.92)
- Debate on Graph: A Flexible and Reliable Reasoning Framework for Large Language Models (AAAI 2025 · similarity 0.91)
- LightPROF: A Lightweight Reasoning Framework for Large Language Model on Knowledge Graph (AAAI 2025 · similarity 0.91)
- Towards Graph Foundation Models: Training on Knowledge Graphs Enables Transferability to General Graphs (NeurIPS 2025 · similarity 0.91)
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.