Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning

Oct 2, 2023•Linhao Luo, Yuan-Fang Li, Gholamreza Haffari +1•View PDF

TL;DR Highlight

How LLMs use Knowledge Graph relation paths via a Plan-Retrieve-Reason pipeline to give accurate answers without hallucination.

Who Should Read

Backend/AI developers solving hallucination and knowledge staleness problems in LLM-based QA systems. Especially teams building reliable reasoning pipelines with Knowledge Graph access.

Core Mechanics

Proposes a 3-step pipeline (Planning → Retrieval → Reasoning) where LLM first generates a 'relation path' plan from the KG, retrieves actual facts via that path, then reasons
Unlike existing RAG approaches that ignore KG structure and just fetch triples, using relation paths as a 'reasoning plan' is robust even for multi-hop questions
After instruction fine-tuning LLaMA2-Chat-7B as backbone, RoG's Planning module can be plugged into any LLM (ChatGPT, Alpaca, etc.) without retraining
Instead of just putting KG facts in context, including the reasoning path itself in output provides step-by-step explanation for why that answer was given (interpretability)
Transfer from Freebase-trained model to Wiki-Movies KG: retraining time reduced from 38h to 2h — easily portable to other KGs
Ablation confirms that without the planning module (random paths), performance drops significantly — 'planning which paths to explore' is itself the key

Evidence

WebQSP: Hits@1 85.7% — 4.4%p improvement over previous SOTA DECAF (82.1%)
CWQ (complex multi-hop questions): Hits@1 62.6%, F1 56.2% vs previous SOTA UniKGQA (Hits@1 51.2%, F1 49.1%) — improvements of 22.3%p and 14.4%p respectively
With RoG Planning module: ChatGPT Hits@1 66.8% → 81.5%, Flan-T5-xl 31.0% → 67.9% (~119% improvement for Flan-T5)
Ablation: removing Planning drops WebQSP F1 70.8 → 49.7; using random paths drops to 35.2

How to Apply

If you have an in-house Knowledge Graph (Neo4j, Freebase, etc.), when receiving a question, have the LLM first generate 'what relation order should I traverse to solve this?' as a relation path, BFS-traverse the KG with that path, retrieve actual paths, and provide as LLM context — greatly reduces hallucination
Replacing simple triple retrieval with relation path-based retrieval in existing RAG pipelines improves multi-hop question performance (e.g., 'What is the population of A's father's birthplace?'); the paper's Planning Prompt Template and Reasoning Prompt Template can be used directly as prompts
Hybrid structure: fine-tune LLaMA2-Chat-7B only for Planning, delegate reasoning to existing GPT-4 or Claude (plug-and-play supported)

Code Example

snippet

# RoG Planning + Reasoning Prompt Example

# Step 1: Planning - Generate KG relation paths
planning_prompt = """
Please generate a valid relation path that can be helpful for answering the following question:
{question}
"""
# Example format returned by LLM:
# <PATH> location.administrative_division.first_level_division_of <SEP> government.form_of_government.countries </PATH>

# Step 2: Retrieval - BFS traversal of actual paths from KG
def retrieve_reasoning_paths(question_entities, relation_path, kg):
    from collections import deque
    results = []
    queue = deque([(e, []) for e in question_entities])
    while queue:
        node, path = queue.popleft()
        if len(path) == len(relation_path):
            results.append(path)
            continue
        next_relation = relation_path[len(path)]
        for (s, r, t) in kg.get_triples(node):
            if r == next_relation:
                queue.append((t, path + [(s, r, t)]))
    return results

# Step 3: Reasoning - Generate final answer based on retrieved paths
reasoning_prompt = """
Based on the reasoning paths, please answer the given question.
Please keep the answer as simple as possible and return all the possible answers as a list.

Reasoning Paths:
{reasoning_paths}

Question:
{question}
"""

Terminology

Knowledge Graph (KG)A structured knowledge base storing entities (people, places, concepts) and their relations in graph form. Composed of (subject, relation, object) triples like (Justin Bieber, child_of, Jeremy Bieber).

Relation PathThe sequence of relations connecting entities in a KG. Like 'child_of → has_son' — the path plan showing which relations to follow to reach the answer.

HallucinationWhen an LLM plausibly generates content that's not factual. Like confidently giving a wrong answer.

KGQAKnowledge Graph Question Answering. The task of answering natural language questions using information stored in a Knowledge Graph.

Multi-hopReasoning that requires crossing multiple KG edges to reach an answer. Single-hop means one edge is enough; multi-hop needs several.

Related Resources

Original Abstract (Expand)

Large language models (LLMs) have demonstrated impressive reasoning abilities in complex tasks. However, they lack up-to-date knowledge and experience hallucinations during reasoning, which can lead to incorrect reasoning processes and diminish their performance and trustworthiness. Knowledge graphs (KGs), which capture vast amounts of facts in a structured format, offer a reliable source of knowledge for reasoning. Nevertheless, existing KG-based LLM reasoning methods only treat KGs as factual knowledge bases and overlook the importance of their structural information for reasoning. In this paper, we propose a novel method called reasoning on graphs (RoG) that synergizes LLMs with KGs to enable faithful and interpretable reasoning. Specifically, we present a planning-retrieval-reasoning framework, where RoG first generates relation paths grounded by KGs as faithful plans. These plans are then used to retrieve valid reasoning paths from the KGs for LLMs to conduct faithful reasoning. Furthermore, RoG not only distills knowledge from KGs to improve the reasoning ability of LLMs through training but also allows seamless integration with any arbitrary LLMs during inference. Extensive experiments on two benchmark KGQA datasets demonstrate that RoG achieves state-of-the-art performance on KG reasoning tasks and generates faithful and interpretable reasoning results.