PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-Augmented Reasoning: Evolving Step-by-Step Knowledge Graph Retrieval for LLM Reasoning

Wenjie Wu, Yongcheng Jing, Yingjie Wang, Wenbin Hu, Dacheng Tao

arXiv:2503.01642v1cs.AI

TL;DR

Small LLMs face limited domain knowledge, hallucinations, and constrained reasoning depth, while step-wise KG retrieval for o1-like reasoning has received little attention. KG-RAR combines step-wise retrieval, process-oriented graph construction, and training-free PRP-RM; experiments report gains across Math500 and GSM8K, including a 20.73% relative improvement for Llama-3B on Math500.

  • Problem

    Small LLMs struggle with complex reasoning, and traditional RAG does not address intermediate-step hallucinations or the structured relationships needed for multi-step reasoning.

    Source: §1 · p. 1

  • Method

    KG-RAR combines hierarchical step-wise KG retrieval, process-oriented math graph construction, and training-free PRP-RM to refine retrievals and evaluate step correctness.

    Source: §1 · p. 2

  • Results

    20.73% relative improvement over CoT prompting for Llama-3B on Math500, with experiments across six smaller models on Math500 and GSM8K.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework integrates external knowledge into frozen LLM reasoning without additional training.

    Source: §1 · p. 2

    KG-RAR can incur higher computational overhead and may introduce unnecessary noise or fail to improve reasoning in some cases.

    Source: §6 · p. 7

Abstract

from arXiv · show

Recent large language model (LLM) reasoning, despite its success, suffers from limited domain knowledge, susceptibility to hallucinations, and constrained reasoning depth, particularly in small-scale models deployed in resource-constrained environments. This paper presents the first investigation into integrating step-wise knowledge graph retrieval with step-wise reasoning to address these challenges, introducing a novel paradigm termed as graph-augmented reasoning. Our goal is to enable frozen, small-scale LLMs to retrieve and process relevant mathematical knowledge in a step-wise manner, enhancing their problem-solving abilities without additional training. To this end, we propose KG-RAR, a framework centered on process-oriented knowledge graph construction, a hierarchical retrieval strategy, and a universal post-retrieval processing and reward model (PRP-RM) that refines retrieved information and evaluates each reasoning step. Experiments on the Math500 and GSM8K benchmarks across six models demonstrate that KG-RAR yields encouraging results, achieving a 20.73\% relative improvement with Llama-3B on Math500.

1 INTRODUCTION

Small LLMs face domain-knowledge, hallucination, and reasoning-depth challenges, while conventional RAG does not address intermediate-step hallucinations or provide the structured relationships complex reasoning needs. KG-RAR integrates step-wise graph retrieval into multi-step reasoning and combines it with process-oriented graphs and training-free scoring.

1 INTRODUCTION

  • Small LLMs struggle with complex mathematical and scientific reasoning amid insufficient domain knowledge, hallucination susceptibility, and constrained reasoning depth.The paper notes that few studies address these challenges in o1-like reasoning.Source: §1 · p. 1
  • Traditional RAG retrieves only for the initial prompt, leaving intermediate-step hallucinations unaddressed and potentially missing structured relationships needed for complex reasoning.The paper frames these as two challenges for applying RAG to o1-like multi-step reasoning.Source: §1 · p. 1
  • KG-RAR combines hierarchical retrieval, a process-oriented math knowledge graph, and training-free PRP-RM to refine retrieved knowledge and score step correctness.Questions and intermediate reasoning steps are progressively matched to relevant subgraphs.Source: §1 · p. 2
  • 20.73% relative improvement over CoT prompting for Llama-3B on Math500; results also report gains for Llama-8B on Math500 and GSM8K.The reported relative gains are 15.22% for Llama-8B on Math500 and 8.68% for Llama-8B on GSM8K.Source: §1 · p. 2

2 RELATED WORK

Prior work uses test-time compute and reward models to refine LLM reasoning, while KG integration has mainly addressed static knowledge tasks. The paper positions step-wise KG reasoning and training-free scoring as gaps for complex multi-step tasks.

2.1 LLM Reasoning

  • o1-like methods allocate inference-time computation to refine reasoning paths, but remain computationally expensive and challenging for small models.The related work discusses approaches including Best-of-N, Beam Search, and Monte Carlo Tree Search.Source: §2.1 · p. 2

2.2 Knowledge Graphs Enhanced LLM Reasoning

  • KG-enhanced LLM work has focused on question answering, fact-checking, and entity-centric reasoning, mostly retrieving static knowledge rather than iterative logical computations.The paper contrasts that focus with mathematics, where problem solving demands dynamic, step-by-step inference.Source: §2.2 · p. 2

2.3 Reward Models

  • Fine-tuned ORMs and PRMs can improve validation accuracy but incur high training costs and often generalize poorly across tasks.Generative reward models integrate chain-of-thought reasoning into reward assessment, while fine-tuning still limits adaptability.Source: §2.3 · pp. 2–3

3 PRE-ANALYSIS

The paper frames graph-augmented reasoning as a way to support frozen LLMs with external knowledge without additional fine-tuning. It identifies integration, graph construction, and universal scoring as challenges for implementing that approach.

3.1 Motivation and Problem Definition

  • Graph-augmented reasoning aims to improve frozen LLMs’ step-by-step reasoning by integrating external KGs without additional fine-tuning.The proposed advantages include support for small models in resource-constrained environments, scaling test-time compute, and transfer across reasoning tasks using domain-specific KGs.Source: §3.1 · p. 3

3.2 Challenge Analysis

  • The paper identifies three implementation challenges: integrating KGs with frozen LLMs, constructing graphs that encode procedural reasoning, and scoring reasoning paths without task-specific fine-tuning.Existing KGs largely encode static rather than procedural knowledge, and current fine-tuned reward models are costly and lack adaptability.Source: §3.2 · pp. 3–4
  • KG-RAR and PRP-RM are proposed to address these challenges with a step-by-step KG retrieval-augmented reasoning framework and dedicated post-retrieval processing and reward model.Source: §3.2 · p. 4

4 PROPOSED APPROACH

KG-RAR integrates knowledge-graph retrieval into frozen LLM reasoning through a retrieve-refine-reason cycle. It combines a process-oriented math graph, hierarchical retrieval, and post-retrieval refinement and step evaluation.

4.1 Overview

  • KG-RAR organizes frozen, small-scale LLM reasoning into three phases: retrieving graph knowledge, refining it, and reasoning iteratively.The framework is intended to operate without additional training.Source: §4.1 · p. 4

4.2 Process-Oriented Math Knowledge Graph

  • The math knowledge graph represents process-supervision samples through problems, procedures, errors, and related mathematical knowledge.Samples are decomposed into branch, subfield, problem type, problem, procedures, errors, and related knowledge; about 10,000 PRM800K samples yield a graph of approximately 80,000 nodes and 200,000 edges.Source: §4.2 · p. 4

4.3 Step-by-Step Knowledge Graph Retrieval

  • Problem retrieval hierarchically filters by type, subfield, and branch, then uses semantic similarity and graph traversal to retrieve relevant context.For each reasoning step, retrieval is narrowed to subgraphs of similar problems, and breadth-first search extracts potential next steps, related knowledge, and error patterns.Source: §4.3 · pp. 4–5

4.4 Post-Retrieval Processing and Reward Model

  • PRP-RM iteratively refines retrieved context for each reasoning step, evaluates step correctness and completion, and continues until completion exceeds a threshold or inference depth is reached.Its role-based prompts assign guidance and correctness evaluation to the Responsible Teacher, heuristic questioning to the Socratic Teacher, and error diagnosis to the Critical Teacher.Source: §4.4 · pp. 5–6, Figure 4 · p. 5

5 EXPERIMENTS

The experiments evaluate Step-by-Step KG-RAR and PRP-RM against CoT prompting and fine-tuned reward models, then examine component choices. KG-RAR improves accuracy on Math500 and GSM8K, while ablations assess retrieval processing, graph structure, padding, roles, scaling, solution counts, and voting.

5.1 Experimental Setup

  • The setup uses Best-of-N with n = 8 for Math500 and n = 4 for GSM8K, holding the Reasoner LLM and PRP-RM constant for fair comparisons.Accuracy (%) is the primary metric; the setup uses step depth 8 and padding 4 for KG-RAR.Source: §5.1 · p. 6, §5 · p. 6

5.2 Comparative Experimental Results

  • Step-by-Step KG-RAR consistently outperforms CoT across Math500 difficulty levels, with larger gains in Llama3 than Qwen2.5.The authors attribute Qwen2.5's smaller gains likely to its higher baseline accuracy; smaller models decline on harder problems amid reasoning inconsistencies.Source: §5.2 · p. 6
  • 8.95% average relative accuracy gain on Math500 under Maj@8; Llama-3.2-8B improves 8.68% on GSM8K under Maj@4.The GSM8K evaluation results are reported in Table 2.Source: §5.2 · p. 6, Table 2 · p. 6

5.3 Ablation Studies

  • PRP-RM refinement improves performance over raw KG retrieval, and KG-RAR outperforms no-RAG and unstructured-RAG baselines.The retrieval comparisons use Llama-3B on Math500 Level 3 and Qwen-0.5B Reasoner with Qwen-3B PRP-RM on Math500, respectively.Source: §5.3 · p. 6, Figure 6 · p. 7, Figure 7 · p. 7
  • Padding trades off consistency against refinement: small padding causes inconsistencies, while large padding hinders refinement; Critical Teacher performs best among the three roles.These comparisons use Llama-1B on Math500 Level 3 for padding and Llama-3B on Math500 for PRP-RM roles.Source: Figure 9 · p. 7, Figure 8 · p. 7
  • Accuracy improves incrementally with more generated solutions, while Majority Vote and Last Vote outperform extreme-based voting methods.The paper reports that extreme-based methods are prone to PRP-RM overconfidence in incorrect solutions; scaling both the Reasoner LLM and PRP-RM independently also improves performance.Source: Figure 9 · p. 7

6 CONCLUSIONS AND LIMITATIONS

The conclusion presents KG-RAR as an iterative retrieve-refine-reason framework for frozen LLMs, with PRP-RM refining retrievals and scoring reasoning steps. It reports average gains over CoT on Math500 and notes computational overhead and cases where the approach may add noise or fail to help.

6 CONCLUSIONS AND LIMITATIONS

  • KG-RAR iteratively retrieves, refines, and reasons over external knowledge graphs, while PRP-RM refines raw retrievals and assigns step-wise scores.The framework is presented as aiming to enhance o1-like multi-step reasoning in frozen LLMs.Source: §6 · p. 7
  • 8.95% relative improvement on average over CoT prompting on Math500, with PRP-RM competitive with fine-tuned reward models without heavy training or fine-tuning costs.The conclusion reports these experimental results as evidence for the proposed approach.Source: §6 · p. 7
  • The approach has higher computational overhead and may introduce unnecessary noise or fail to enhance reasoning.The authors identify these as limitations and describe efficiency improvements and broader applications as future work.Source: §6 · p. 7

Related papers

Loading 2503.01642v1…