Thinking with Knowledge Graphs: Enhancing LLM Reasoning Through Structured Data

1 INTRODUCTION

• LLMs can produce nonfactual, nonsensical, or incoherent text, with hallucinations particularly prevalent in tasks requiring intricate reasoning.Prompting, retrieval-augmented generation, and fine-tuning are among approaches that use external information sources.Source: §1 · p. 1
• GNN-based KG embeddings can guide LLM generation, but graph-specific integration may require substantial re-engineering across tasks or graph types.The representations must also align GNN and LLM processing.Source: §1 · p. 1
• SPARQL-based retrieval leaves the KG and LLM as separate components, while natural-language encoding can make graph structure difficult to preserve without ambiguity.The paper instead proposes representing KGs with programming-language code, which is structured and familiar from LLM pretraining.Source: §1 · p. 1
• Programming-language representations of KGs outperform natural-language and JSON representations on complex reasoning tasks, with more accurate and reliable outputs.The authors emphasize Python representations of entity relationships.Source: §1 · p. 1
• The approach tightly integrates KGs into LLMs to improve complex-task reasoning accuracy and ground reasoning, reducing the chance of hallucinations.The paper identifies relation examples for generalization, in addition to trustworthy information, as a motivation.Source: §1 · pp. 1–2

2 RELATED WORK

• Graph reasoning work includes graph-to-text methods that can create large contexts, graph structure and prefix-tuning systems, and instruction fine-tuning for graph tasks.Wang et al. [28], Guo et al. [15], and Ye et al. [37] use Graph2Text; Chai et al. [9] introduced GraphLLM.Source: §2 · p. 2
• KG-focused approaches combine LLM and GNN representations, plan and retrieve over KG paths, encode graph neighborhoods, or build community summaries for retrieval.These include Choudhary et al., Yasunaga et al. [36], Luo & Pan [22], Dernbach et al. [12], and Edge et al. [13].Source: §2 · p. 2
• Related work studies code in LLM training and Python functions for knowledge-base querying, while fine-tuned chain-of-thought methods use natural-language reasoning steps.Nie et al. [24] use seven Python meta-functions for database operations; creating fine-tuning datasets for chain-of-thought is labor intensive [19], [39].Source: §2 · p. 2
• Prior studies report latent multi-hop reasoning but difficulty with later hops; this work instead represents entity relationships in Python to answer questions directly.Yang et al. [33] report difficulty with later hops, and Biran et al. [3] propose back-patching; unlike Nie et al. [24], this work encodes relationships rather than atomic query operations.Source: §2 · p. 2

3.1 Knowledge Graph Definition

• A KG is defined as entities, relationships, and directed triplets; two-hop and three-hop reasoning chains share bridge entities between adjacent triplets.Source: §3.1 · p. 2

3.2 Knowledge Graph Representation for LLM Reasoning

• Natural-language encoding expresses KG triplets as prose, including a two-hop chain of relationships.Source: §3.2 · p. 3
• JSON stores triplets as entity keys with relationship/entity values, but its data-only format makes multi-hop inference difficult to represent.A comment or description field could be added for the reasoning, though the passage says this is not generally recommended.Source: §3.2 · p. 3
• Python representations use static dictionaries for retrieval or a dynamic KnowledgeBase whose infer function accepts arbitrary relationships and can generalize to KG subgraphs.Source: §3.2 · p. 3, Figure 3 · p. 3, Figure 4 · p. 3

4 EXPERIMENTS

• The experiments compare how different KG entity-relation representations affect LLM reasoning across two datasets.Source: §4 · p. 4

4.1.1 Dataset 1.

• Dataset 1 uses Wikidata two-hop relations split into eight bridge-entity partitions, with partition 2 for training and partition 4 for testing.The split has no bridge entities shared between train and test, while relationship-pair overlap is about 99%.Source: §4.1.1 · p. 4

4.1.2 Dataset 2.

• Dataset 2 trains on compositional relations capped at 500 instances per relation pair and uses its compositional development set for testing.The relation types are kept consistent with Dataset 1 for easier comparison; entity and relation overlap was not further restricted.Source: §4.1.2 · p. 4

4.1.3 Dataset 3.

• Dataset 3 extends Dataset 1’s two-hop chains with a third hop to test whether two-hop fine-tuning generalizes to three-hop reasoning.Its training data includes prompts and responses based on both one-hop and two-hop information.Source: §4.1.3 · p. 4

4.2 Large Language Models

• Llama-3.1-8B-Instruct is fine-tuned with different multi-hop entity-relation representations, while Llama-3.1-70B-Instruct is not fine-tuned because of resource constraints.The experiments use LoRA and greedy decoding.Source: §4.2 · pp. 4–5, §4.3 · p. 5

4.3 Experiment Environment

• Experiments use Hugging Face checkpoints, one Nvidia A100 with 40GB RAM per GPU, and one training epoch.Source: §4.3 · p. 5

4.4 Experiment Design

• The experiment design tests how KG representations affect reasoning and compares model performance under three conditions.Source: §4.4 · p. 5, §4.4.1 · p. 5

4.4.1 LLM Reasoning without Context.

• Without context, the baseline prompts the model to predict e3 from (e1,r1,r2), alongside one-shot reasoning examples and zero-shot prompts to fine-tuned models.The one-shot and fine-tuned conditions each test three KG representation formats; the context experiments target potential RAG applications.Source: §4.4.1 · p. 5, §4.4.2 · p. 5

4.4.2 LLM Reasoning with Context.

• With context, fine-tuned models trained on one-hop and two-hop triplets are tested for reasoning over longer paths.Source: §4.4.3 · p. 5

• Table 4 presents the prompts used across the experiments.Source: §4.5 · p. 5
• The examples shown in the paper are for two-hop reasoning prompts.Source: §4.5 · p. 5
• Three-hop prompts follow the same logic and format, while one-shot natural-language, JSON, and Python examples are placed in Appendix A.The appendix placement is attributed to paper-length limits.Source: §4.5 · p. 5

• The main metric is multi-hop reasoning accuracy conditioned on the correctness of each individual hop, denoted r = p(h|h1,h2,...,hn).Source: §4.6 · p. 5
• The metric is used instead of overall accuracy because final outputs also depend on entity knowledge and whether each hop is inferred correctly.The authors describe it as measuring latent multi-hop reasoning performance.Source: §4.6 · p. 5
• Overall accuracy is also provided as a reference for potential applications.Source: §4.6 · p. 5

4.7 Experimental Results

• Dynamic Python one-shot prompting is approximately 78% higher than zero-shot on Dataset 1; static Python is about 60% higher on Dataset 2.Source: §4.7.1 · p. 5
• One-shot Python prompts outperform natural-language and JSON prompts, while one-shot JSON performs worse than zero-shot prompting.Source: §4.7.1 · p. 5
• Fine-tuned Llama-3.1-8B-Instruct models with any entity-relationship representation outperform zero-shot Llama-3.1-70B-Instruct on latent multi-hop reasoning, with Python representations best.Source: §4.7.1 · pp. 5–6

4.7.2 RQ2: Can fine-tuned LLMs generalize their reasoning ability

• On three-hop reasoning, every fine-tuned representation beats the unfine-tuned baseline, with Python best; the evaluated relation pair substantially overlaps training.Source: §4.7.2 · p. 6

4.7.3 RQ3: How much can LLM in-context learning help or benefit

• With input context, fine-tuned models outperform the unfine-tuned baseline, and dynamic Python fine-tuning surpasses the much larger Llama-3.1-70B-Instruct baseline.Source: §4.7.3 · p. 6

4.8 Discussion

• Python representations combine structured data with the inference process, offering a more controlled and unambiguous way to guide reasoning than the discussed alternatives.The discussion contrasts them with natural language, which is straightforward and common in pretraining, and JSON, which suits structured storage but can be difficult for LLMs to integrate directly.Source: §4.8 · p. 6
• Some fine-tuned small LLMs outperform much larger LLMs, although larger models can also help connect multiple hops and infer answers.Source: §4.8 · p. 7
• Fine-tuning emphasizes multi-hop relationships rather than individual entity facts, and the authors report generalization to different entities and to more hops than seen in training.The authors also report improved in-context learning results.Source: §4.8 · p. 8
• Experiments cover only two- and three-hop compositional reasoning; more sophisticated real-world reasoning remains outside the evaluated scope.The authors identify more complex relationship representations as future work.Source: §4.8 · p. 8

5 CONCLUDING REMARKS

• Programming-language representations of entity relationships help improve LLM multi-hop reasoning and reduce hallucination.Source: §5 · p. 8
• Native programming-language data structures and iterative inference functions provide a controlled, unambiguous way to model relationships and guide multi-hop reasoning.Source: §5 · p. 8
• The conclusion identifies more sophisticated relationships and reasoning beyond two- and three-hop compositional cases as future work.It also proposes studying impacts at both pre-training and fine-tuning stages.Source: §5 · p. 8

A.1 Explanation for Natural Language Prompt; A.2 JSON structure Prompt

• A.1 states the composer and spouse facts in prose, while A.2 encodes the same entity-relation pairs as JSON mappings.Source: §A.1 · p. 9, §A.2 · p. 9

A.3 Python Code Snippet for Prompt V1

• A.3 defines explicit relationship types and maps the example entities to David Shire and Didi Conn.Source: §A.3 · p. 9
• A.3 retrieves the entity associated with a starting entity and relation using relationships[r1][e1].Source: §A.3 · p. 9
• A.3 formats the result as a natural-language statement describing the spouse of the composer of the starting entity.Source: §A.3 · p. 9

A.4 Python Code Snippet for Prompt V2

• A.4 represents facts in a knowledge-base dictionary, with each (entity1, relation) key mapped to entity2.Source: §A.4 · p. 10
• A.4’s add_fact method takes a starting entity, relation, and related entity as its inputs.Source: §A.4 · p. 10
• A.4’s infer method traverses a relation chain from a starting entity and returns None if the path does not exist.Source: §A.4 · p. 10
• A.4 adds the composer and spouse facts, then traverses both relations to reach Didi Conn from It Goes Like It Goes.Source: §A.4 · p. 10