PaperlayerView exact revision on arXiv

Source-linked AI summary

Extracting and Following Paths for Robust Relational Reasoning with Large Language Models

Ge Zhang, Mohammad Ali Alomrani, Hongjian Gu, Jiaming Zhou, Yaochen Hu, Bin Wang, Qun Liu, Mark Coates, Yingxue Zhang, Jianye Hao

arXiv:2412.17963v2cs.CL

TL;DR

LLMs struggle with multi-hop relational reasoning, while neuro-symbolic approaches can be task-specific, brittle to extraction errors, or require many LLM calls. PoT extracts a graph, identifies query-relevant paths, and reasons over them; across four benchmark datasets it outperforms baselines, with reported accuracy improvement up to 21.3%.

  • Problem

    LLMs struggle with multi-hop relational reasoning, while prior neuro-symbolic approaches can be task-specific, brittle to LLM errors, or require many LLM calls.

    Source: §1 · p. 2

  • Method

    PoT uses one LLM call to extract an entity-relation graph, identifies paths between query entities, and uses the paths to infer possible answers.

    Source: §1 · p. 2, §4.1 · p. 5

  • Results

    Across four benchmark datasets, PoT outperforms baselines, with reported accuracy improvement reaching 21.3%.

    Source: §1 · p. 2, §7 · p. 13

  • Takeaways & Limitations

    PoT exhibits resilience to noisy relations through graph composition without fine-tuning or extensive LLM calls.

    Source: §7 · p. 13

    Constructing symbolic rules for PoT-Symbolic requires domain expertise and significant manual effort.

    Source: §6 · p. 13

Abstract

from arXiv · show

Large language models (LLMs) possess vast semantic knowledge but often struggle with complex reasoning tasks, particularly in relational reasoning problems such as kinship or spatial reasoning. In this paper, we present Path-of-Thoughts (PoT), a novel framework for solving relation reasoning that decomposes the task into three key stages: graph extraction, path identification, and reasoning. Unlike previous approaches, PoT efficiently extracts a reasoning graph that identifies crucial entities, relations, and attributes within the context. Subsequently, PoT identifies query-relevant reasoning paths within the graph, facilitating downstream reasoning of potential answers. Experimental evaluations across four datasets of relational reasoning demonstrate that PoT surpasses state-of-the-art baselines by a significant margin (up to 21.3%) without requiring fine-tuning or extensive LLM calls. Furthermore, unlike prior neuro-symbolic methods, PoT exhibits improved resilience against LLM extraction errors and input ambiguity by leveraging the compositional nature of graphs.

1 Introduction

LLMs can struggle with multi-hop relational reasoning, while prior neuro-symbolic approaches may be task-specific, brittle to LLM errors, or require many LLM calls. PoT extracts a graph, identifies query-relevant paths, and reasons over them; evaluations report improved accuracy and resilience to extraction errors and ambiguous descriptions.

1 Introduction

  • LLMs struggle with multi-hop relational reasoning, and neuro-symbolic approaches can require specialized modules, be brittle to LLM errors, or require many LLM calls.The paper contrasts these approaches with prompt-based baselines such as Chain-of-Thought (CoT) (Wei et al., 2022b).Source: §1 · p. 2
  • PoT decomposes relational reasoning into graph extraction, query-relevant path identification, and reasoning over the identified paths.The framework reports a maximum accuracy improvement of 21.3% and greater robustness to extraction errors and potentially controversial descriptions.Source: §1 · p. 2
  • A single LLM call extracts the graph and queries, while path identification finds independent reasoning paths to infer all possible answers.This approach is benchmarked on kinship and spatial reasoning datasets against baselines.Source: §1 · p. 2
  • Figure 1 illustrates a flipped-relation extraction error and shows PoT reasoning over relevant paths independently to alleviate cascading errors.The framework infers all possible answers from the paths.Source: Figure 1 · p. 3

2 Problem Definition

The task is to infer a target relation between two entities from a natural-language story whose context does not directly state that relation. The setting also permits multiple answers when stories are ambiguous or erroneous, and assumes relation compositions are common-sense or supplied as domain-specific rules.

2 Problem Definition

  • A sample pairs a textual story and target relation; its context describes entity relations, while its question asks about an unstated relation between two entities.The target entities must be extracted from the question in the paper’s more general setting.Source: §2 · p. 3
  • Unlike prior settings that omit the question or provide queried entities separately, this setting requires extracting both query entities from the question.The question asks for a relation between two entities whose relation is not directly given in the context.Source: §2 · p. 3
  • Ambiguous or erroneous stories may support multiple answers, and relation composition is assumed to rely on common sense or provided domain-specific rules.The rules may be specified as logical rules or as examples.Source: §2 · p. 3

3 Related Work

Prior work addresses relational reasoning with neural, prompting-based, and neuro-symbolic methods. PoT uses a graph representation and multiple paths to address limitations associated with task-specific symbolic translations and conflicting extracted information.

3 Related Work

  • Neural approaches include specialized spatial-reasoning networks, relational recurrent networks, and fine-tuned language models; benchmarks include StepGame, SPARTUN, and CLUTRR.The cited work reports a performance gap between language models reasoning directly from text and graph neural networks working from the underlying symbolic graph.Source: §3 · pp. 3–4
  • Prompting methods range from Chain-of-Thought (Wei et al., 2022b) and self-consistency (Wang et al., 2023b) to search-based approaches, but tailored strategies can limit adaptability.Chain-of-Symbol still relies on LLMs to construct reasoning paths implicitly, leaving it vulnerable to interfering or disordered relations.Source: §3 · p. 4
  • Neuro-symbolic systems combine language understanding with symbolic reasoning, but prior methods can require fine-tuning or be limited to tractable parsing settings.PoT instead extracts a versatile graph for different reasoners and uses multiple paths to mitigate the impact of conflicting information from extraction errors or input ambiguity.Source: §3 · pp. 4–5

4 Methodology

PoT converts a story into a graph, identifies paths between queried entities, and applies a reasoner to each path. Its extraction prompts structure the task, while the reasoning stage can use either an LLM or a symbolic solver.

4 Methodology

  • PoT has three modules: graph extraction, path identification, and reasoning over each identified path.The reasoner infers an answer from each path independently.Source: §4 · p. 5

4.1 Graph Extraction

  • Graph extraction represents entities and attributes as nodes and relations as triplet edges; prompts structure outputs and separate relation-triplet extraction from query identification.The queried entities are extracted from the question and represented as source and target nodes.Source: §4.1 · pp. 5–6

4.2 Path Identification

  • Path identification finds edge sequences connecting queried entities, traversing edges forward or backward; distinct paths can yield different answers when extraction errors or ambiguity occur.The module uses depth-first search to find paths.Source: §4.2 · p. 6

4.3 Reasoning

  • Each path is sent to an LLM or symbolic solver; LLM reasoning assumes common-sense knowledge, while ASP reasoning requires a problem-specific rule module.The reasoner choice depends on rule availability and user considerations such as speed, robustness, or optimality.Source: §4.3 · p. 6

5 Experiments

The experiments evaluate PoT across four relational-reasoning datasets, multiple LLM backbones, and prompting-based and neuro-symbolic baselines. PoT generally improves over these baselines, while extraction, path-identification, robustness, and cost analyses probe how the framework performs.

5.1 Experimental Setup

  • Evaluation spans StepGame, CLUTRR, SPARTUN, and Chinese Kinship, comparing prompting and neuro-symbolic baselines across general-purpose and reasoning-focused LLMs.Neuro-symbolic methods are not evaluated on SPARTUN or Chinese Kinship because their relation sets make symbolic knowledge modules difficult to write.Source: §5.1 · p. 7

5.2 Experimental Results

  • PoT-LLM outperforms prompting baselines in most scenarios, with exceptions on CLUTRR for GPT-3.5-turbo and SPARTUN for GPT-4-turbo and Llama3-70B; PoT-Symbolic improves over LLM-ASP except on StepGame with GPT-3.5-turbo.The full-pipeline results are single-trial comparisons.Source: §5.2 · p. 8, Table 1 · p. 9
  • For GPT-o1-mini and Claude-3.7-sonnet, PoT outperforms baselines on StepGame and CLUTRR; GPT-5 results are on par at medium effort and improve at minimal effort with fewer tokens.The authors report that accuracy is preserved with reduced reasoning effort.Source: §5.2 · pp. 8–9, Table 2 · p. 10
  • Despite requiring two LLM calls, PoT-LLM has computational cost and latency comparable to IO and CoT, with path-focused reasoning reducing overhead versus processing the whole story.The paper reports module-level time and token statistics for GPT-4o on StepGame k=3.Source: §5.2 · pp. 10–11, Table 3 · p. 11, Table 4 · p. 11
  • On 1,000 synthetic 20-sentence Stepgame stories, GPT-4-turbo with the tailored extraction prompt outperforms zero-shot and CoT prompting.The stories were assembled from a manually labeled pool of 100 StepGame sentences.Source: §5.2 · p. 11, Table 5 · p. 12
  • Without P.I., PoT-LLM accuracy falls on Stepgame (73.4 to 69.2, k=3; 68.0 to 61.7, k=4; 48.7 to 38.8, k=10) and CLUTRR (61.9 to 50.7).PoT-Symbolic changes by less than 0.5% on Stepgame and CLUTRR when P.I. is removed.Source: §5.2 · p. 11, Table 6 · p. 12
  • With P.I., the symbolic reasoner remains robust as noise increases, while the version without P.I. declines significantly; with P.I. it also beats or ties the ablated version across noise types.The synthetic evaluation simulates graph-extraction errors and story ambiguities.Source: §5.2 · pp. 11–12, Figure 2 · p. 12

6 Limitations

PoT’s limitations concern its evaluated task scope, dataset quality, and the manual or computational costs of its variants. The authors recommend choosing between PoT-Symbolic and PoT-LLM according to domain size and desired scalability.

6 Limitations

  • PoT has been tested only on relational problems where each relationship can be expressed as a composition or chain of other relationships.Its generality on non-relational reasoning remains unevaluated systematically.Source: §6 · p. 13
  • Incorrect or incomplete ground-truth labels found in case studies could confound evaluation, and addressing data-quality issues may improve conclusion reliability.Source: §6 · p. 13
  • PoT-Symbolic requires domain expertise and significant manual effort to construct symbolic rules, while LLM-assisted rule generation is left for future exploration.Source: §6 · p. 13
  • PoT-LLM removes manual rules but incurs higher inference latency and a small accuracy drop due to its reliance on LLM-based reasoning.Source: §6 · p. 13
  • The authors recommend PoT-Symbolic for small, well-defined domains and PoT-LLM when scalability and generality matter despite higher computational cost.Source: §6 · p. 13

7 Conclusion

The conclusion presents Path-of-Thoughts as a three-stage framework for relational reasoning. Experiments report baseline gains across four benchmarks, while analyses examine noise resilience and the importance of key relations and path order.

7 Conclusion

  • PoT outperforms baselines across four benchmark datasets without fine-tuning or extensive LLM calls.Source: §7 · p. 13
  • PoT decomposes relational reasoning into graph extraction, path identification, and reasoning.Source: §7 · p. 13
  • The framework shows resilience to noise relations, and analysis experiments highlight the importance of key relations and reasoning-path order.Source: §7 · p. 13

A.1 Noise Types

The noise analysis distinguishes a primary source-to-target reasoning chain from graph material outside that chain. Its seven perturbations leave the main chain uncorrupted to preserve ground-truth answers.

A.1 Noise Types

  • The main chain is the primary path from source to target, while the irrelevant part comprises all nodes and edges outside it.Source: §A.1 · p. 17
  • Noise types A–C flip an irrelevant edge, add a node and edge, or add a node connected by two potentially conflicting-attribute edges.Source: §A.1 · p. 17
  • Types D–G add an irrelevant edge, add an edge between main-chain nodes, modify an irrelevant-edge relation, or add a disconnected node pair.Source: §A.1 · p. 17

A.2 Path Counts Analysis

On CLUTRR with GPT-4o, accuracy varies with the number of extracted paths, and restricting the solver to only the shortest path reduces accuracy. The analysis compares path counts and their average accuracy.

A.2 Path Counts Analysis

  • 84.6% average accuracy is reached with three paths, while single-path stories average 68.9% on CLUTRR with GPT-4o.Most stories—697 of 1,048—produce a single path; accuracy gradually declines as path counts rise beyond three.Source: §A.2 · p. 17
  • The path-count analysis uses the PoT-Symbolic experiment on CLUTRR with GPT-4o and reports counts alongside corresponding average accuracy.Source: §A.2 · p. 17
  • 14.3% drops in average accuracy occur for samples with five or more paths when only the shortest path is passed to the symbolic solver.The experiment reports a notable average-accuracy drop across multiple path counts under this restriction.Source: §A.2 · p. 17

A.3 Implementation Details

Implementation used the OpenAI API on an Intel Xeon Gold 6140 CPU; neuro-symbolic baselines used Clingo and LLM-ASP knowledge modules. The appendix also describes a noise illustration and a CLUTRR chain-count table.

A.3 Implementation Details

  • The experiments used the OpenAI API on an Intel(R) Xeon(R) Gold 6140 CPU @ 2.30GHz.Source: §A.3 · p. 17
  • Figure 3 illustrates seven synthetic noise types on a five-node, four-edge toy graph, using color to mark relevant, irrelevant, and noisy elements.Relevant and irrelevant nodes and edges are red and green, respectively; noisy nodes and edges are purple.Source: Figure 3 · p. 18
  • Table 7 reports sample counts and average accuracy by number of chains extracted for PoT-Symbolic on CLUTRR with GPT-4o.Source: Table 7 · p. 18
  • Neuro-symbolic methods used the Clingo ASP solver and LLM-ASP knowledge modules written by human domain experts.Source: §A.3 · p. 18

A.4 Prompts for Baselines

This appendix points to baseline prompt templates and notes that they are shared across backbone LLMs. It lists templates for input-output, few-shot, chain-of-thought, and LLM-ASP baselines across the named datasets.

A.4 Prompts for Baselines

  • Baseline prompt templates are identical across backbone LLMs.The section directs readers to Table 1 for the templates.Source: §A.4 · p. 18

A.4.1 Prompt Templates for IO

  • Input-output prompt templates are listed for StepGame, CLUTRR, SPARTUN, and Chinese kinship in Tables 8–11.The StepGame and CLUTRR templates specify answer choices and bracketed output.Source: §A.4.1 · p. 18, Table 8 · p. 19, Table 9 · p. 19

A.4.2 Prompt templates for Few-Shot

  • Few-shot prompt templates for StepGame, CLUTRR, SPARTUN, and Chinese kinship are listed in Tables 12–15.Source: §A.4.2 · p. 18
  • Table 12’s StepGame few-shot prompt maps clock positions and cardinal directions to spatial relations and requests a bracketed answer.Source: Table 8 · p. 19

A.4.3 Prompt Templates for CoT and CoT-SC

  • CoT and CoT-SC prompt templates for the four datasets are listed in Tables 16–21.Source: §A.4.3 · p. 19

A.4.4 Prompt Templates for LLM-ASP

  • LLM-ASP extraction prompts for StepGame and CLUTRR are listed in Tables 22–24, covering relation and gender extraction.Source: §A.4.4 · p. 19

A.5 Prompt Templates for Graph extraction

The appendix documents graph-extraction and reasoning prompts, synthetic-noise construction, and CLUTRR ambiguities. It also describes Chinese kinship complexity and the resulting exclusion of ASP from those experiments.

A.5 Prompt Templates for Graph extraction

  • Graph-extraction prompts use in-context templates for StepGame, CLUTRR, and Chinese kinship, while observed GPT-4 extraction errors include wrong genders, missing relations, and wrong entities.Source: §A.5 · p. 19

A.6 Prompt Templates for LLM Reasoner

  • For StepGame and CLUTRR, the LLM reasoner receives extracted instance paths instead of the original stories; SPARTUN and Chinese kinship retain the story alongside the path.Source: §A.6 · p. 19

A.7 Noise Datasets

  • Synthetic noise samples are made by adding randomly located noise to clean CLUTRR stories; the study generates 100 samples per noise type and 100 per noise-count category.Noise can introduce conflicting relations, and multiple noise types are sampled with replacement.Source: §A.7 · pp. 19–20

A.8 CLUTRR Dataset Ambiguities

  • Some CLUTRR stories have more than one possible answer, as identified by manual checking.Table 36 provides examples.Source: §A.8 · p. 20

A.9 Baselines

  • For CLUTRR and StepGame, the LLM-ASP prompt was modified to extract all triplets and queries in one LLM call.The original setup assumes a given query for CLUTRR and extracts StepGame facts one sentence at a time.Source: §A.9 · p. 20
  • CoT-SC uses the CoT prompt, makes five LLM calls, and returns the top result from a majority vote.Source: §A.9 · p. 20

A.11 Chinese Kinship Complexity

  • Chinese kinship has over 500 possible titles versus CLUTRR’s 24, distinguishes maternal from paternal relatives, and was not tested with ASP because complete rule coverage was nearly infeasible.For example, English uses “uncle” for both parents’ brothers, while Chinese uses different titles.Source: §A.11 · pp. 20–21
  • The Chinese kinship prompt format labels each character’s gender and represents the question as a relation-query triplet.The examples represent relations as triplets between characters.Source: §A.11 · p. 34
Loading 2412.17963v2…