💬 NLP

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

This paper introduces Path-of-Thoughts (PoT), a novel framework that enhances large language models' relational reasoning capabilities by decomposing tasks into graph extraction, path identification, and reasoning stages, achieving significant performance gains over state-of-the-art baselines without fine-tuning while maintaining resilience against extraction errors.

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

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: LLMs are Great Storytellers, But Bad Navigators

Imagine a Large Language Model (LLM) as a brilliant librarian who has read every book in the world. If you ask, "What is the capital of France?" or "Write a poem about rain," this librarian answers instantly and perfectly.

However, if you ask a complex logic puzzle like, "Alice is Bob's sister. Bob is sitting to the left of Charlie. Charlie is behind Dave. Where is Alice relative to Dave?" the librarian often gets confused. They might try to guess the answer based on how the words sound rather than actually mapping out the relationships. They tend to "hallucinate" (make things up) or get lost in the middle of the story.

This paper introduces a new framework called Path-of-Thoughts (PoT) to fix this. Instead of asking the librarian to guess the answer immediately, PoT gives them a three-step map-making process.

The Solution: The "Path-of-Thoughts" (PoT) Framework

Think of the PoT framework as a Detective's Workflow. Instead of the detective (the AI) trying to solve the crime in one giant leap of intuition, they break the job down into three specific stages.

Stage 1: Graph Extraction (Drawing the Map)

The Analogy: Imagine the story is a messy room full of furniture, people, and scattered notes. The first step is to ignore the messy room and draw a clean schematic map on a whiteboard.

What happens: The AI reads the story and extracts only the important facts: "Who is who?" and "How are they connected?"
The Result: It turns the messy text into a clean Graph (a network of dots and lines).
- Dots = People or objects (e.g., Alice, the Box, the Green Thing).
- Lines = Relationships (e.g., "sister of," "behind," "covers").
Why it helps: Even if the AI makes a small mistake here, it's better than trying to reason through the whole messy story at once.

Stage 2: Path Identification (Finding the Route)

The Analogy: Now that you have the map, you have a destination. You don't need to look at the entire map to get from Point A to Point B; you just need the specific route.

What happens: The system looks at the question (e.g., "Where is the Green Thing relative to the Orange Thing?") and finds the specific line of connections on the map that links them.
The Magic Trick: Sometimes, there are multiple ways to connect two points, or the map might have some "noise" (wrong lines drawn by mistake). PoT finds all possible paths.
Why it helps: If the AI drew a wrong line on the map (e.g., saying "A is behind B" when it's actually "A is in front of B"), having multiple paths allows the system to cross-check. If one path leads to a dead end or a contradiction, the system can ignore it and follow the correct path. It's like having a GPS that shows you three different routes; if one is blocked by traffic, you just take the other one.

Stage 3: Reasoning (Solving the Puzzle)

The Analogy: Now that you have the specific route isolated, you hand it to a Logic Solver (either a super-smart AI or a strict mathematical computer program).

What happens: The solver looks only at the specific chain of facts you found in Stage 2. It doesn't care about the rest of the story. It applies strict rules (like "If A is left of B, and B is left of C, then A is left of C").
The Result: A precise answer.

Why is this better than the old way?

The Old Way (Chain-of-Thought):
Asking the AI to "think step-by-step" is like asking a human to solve a maze while blindfolded, just by describing the walls in their head. They might get lost after 5 steps.

The PoT Way:

Stop and Draw: First, draw the maze on paper (Graph Extraction).
Trace the Line: Find the specific line from start to finish (Path Identification).
Walk the Line: Walk that specific line to the end (Reasoning).

The "Superpower" of PoT: Resilience

The paper highlights a crucial advantage: Robustness.

Imagine the AI makes a mistake in Stage 1 and draws a "fake" connection on the map (e.g., it accidentally says "The Red Box is under the Blue Box" when it's actually above).

Without PoT: The AI tries to reason through the whole story including that fake fact and gets the wrong answer.
With PoT: The system finds multiple paths. One path might use the fake fact and lead to a weird result. Another path might use the correct facts. The system can see that the "fake" path doesn't make sense or conflicts with other paths, and it ignores it. It's like having a team of detectives where if one gets confused, the others correct them.

The Results

The researchers tested this on four different "puzzle" datasets involving:

Kinship: Figuring out family trees (e.g., "Who is the uncle of...?").
Spatial Reasoning: Figuring out where objects are relative to each other (e.g., "Is the cup to the left of the plate?").

The Outcome:
PoT beat the current best methods by a huge margin (up to 21.3% better). It did this without needing to retrain the AI models (which is expensive and slow). It simply gave the AI a better way to organize its thoughts.

Summary

Path-of-Thoughts is like giving a confused librarian a whiteboard and a highlighter.

Whiteboard: Draw the relationships clearly (Graph).
Highlighter: Circle only the path that matters (Path Identification).
Solve: Answer the question based only on what's highlighted.

This stops the AI from getting distracted by irrelevant details or tripping over its own mistakes, making it a much more reliable "reasoner."

1. Problem Definition

The paper addresses the limitations of Large Language Models (LLMs) in multi-hop relational reasoning. While LLMs possess vast semantic knowledge, they often struggle with tasks requiring the composition of multiple relational facts, such as:

Kinship Reasoning: Inferring relationships like "grandfather" or "uncle" based on a chain of family descriptions.
Spatial Reasoning: Determining relative positions (e.g., "north-west") based on a series of spatial constraints.

Existing approaches suffer from specific shortcomings:

Prompt-based methods (e.g., Chain-of-Thought): Often suffer from "shallow reasoning," getting distracted by irrelevant context, or failing to maintain logical consistency over long reasoning chains.
Neuro-symbolic methods: While robust, they often require task-specific symbolic translation, are brittle to LLM extraction errors (hallucinations), and may fail when the input contains contradictions or ambiguities.
Generalizability: Many prior works assume the queried entities are pre-defined, whereas real-world scenarios require extracting both the entities and the relations from natural language queries.

2. Methodology: Path-of-Thoughts (PoT)

The authors propose PoT, a framework that decomposes relational reasoning into three distinct stages: Graph Extraction, Path Identification, and Reasoning. This approach leverages the compositional nature of graphs to mitigate errors and improve robustness.

A. Graph Extraction

Goal: Convert the unstructured textual story into a structured reasoning graph $G = (N, E)$ .
Process: A single LLM call extracts all entities (nodes), relations (edges), and attributes.
Innovation: The authors design a specialized prompting strategy to ensure high extraction accuracy. Key features include:
- Sectional Markup: Using special characters (e.g., #) to logically segment the prompt.
- Syntactic Delimiters: Enforcing strict output formats (e.g., triplets like (A, relation, B)).
- Task Decomposition: Separating the extraction of triplets from the identification of the query entities to reduce cognitive load on the LLM.
Output: A graph where nodes represent entities (with attributes like gender or size) and edges represent relations.

B. Path Identification

Goal: Isolate the specific reasoning paths relevant to the query from the potentially noisy or complex graph.
Process: The system identifies all paths connecting the source entity ( $n_{src}$ ) and target entity ( $n_{tar}$ ) defined in the query.
Algorithm: Depth-First Search (DFS) is used to enumerate all possible paths.
Robustness Mechanism: Unlike methods that rely on a single "best" path, PoT identifies multiple independent paths. If the LLM makes an extraction error (e.g., flipping a relation) or if the story contains ambiguity, different paths may yield different potential answers. This allows the system to handle conflicting information rather than failing catastrophically.

C. Reasoning

Goal: Infer the final relation based on the identified paths.
Dual Reasoner Support:
1. LLM Reasoner: The extracted path (expressed in natural language) is fed to an LLM to infer the answer. This reduces the context window size, preventing distraction from irrelevant parts of the story.
2. Symbolic Reasoner: The path is translated into a formal logic language (e.g., Answer Set Programming - ASP) and solved by a symbolic solver (e.g., CLINGO). This is used when domain-specific rules are available and high precision is required.
Aggregation: The system can output multiple possible answers if different paths suggest different relations, reflecting the uncertainty in the input.

3. Key Contributions

Novel Framework: PoT is the first work to explicitly identify query-relevant subgraphs before reasoning, effectively decoupling extraction from the reasoning process.
Efficient Extraction: A prompting-based approach that extracts the entire graph and query in a single LLM call, avoiding the high latency and token costs of iterative extraction.
Robustness to Errors: By leveraging the compositional nature of graphs and exploring multiple paths, PoT demonstrates superior resilience against LLM extraction errors (e.g., wrong relations) and input ambiguities compared to single-path methods.
Generalizability: The framework does not assume pre-defined entities; it extracts both the story structure and the query entities, making it applicable to a wider range of datasets.

4. Experimental Results

The authors evaluated PoT on four datasets: StepGame (spatial), CLUTRR (kinship), SPARTUN (spatial), and a custom Chinese Kinship dataset.

Performance Gains:
- PoT significantly outperformed state-of-the-art baselines (including Zero-shot, Few-shot, Chain-of-Thought, and CoT-SC).
- Accuracy Improvement: Achieved up to a 21.3% improvement over baselines.
- Neuro-symbolic Comparison: PoT-Symbolic (using a symbolic solver) outperformed the LLM-ASP baseline, particularly on complex reasoning hops (e.g., $k=10$ in StepGame).
Robustness Analysis:
- Ablation Studies: Removing the "Path Identification" module caused a significant drop in performance (e.g., from 73.4% to 69.2% on StepGame), proving that isolating relevant paths is crucial.
- Noise Resistance: In synthetic experiments where noise (irrelevant edges, flipped relations, conflicting info) was injected into the graph, PoT with Path Identification maintained high accuracy, whereas methods without it (or without path isolation) degraded significantly.
Efficiency: Despite requiring two LLM calls (extraction + reasoning), the total computational cost and latency were comparable to standard Chain-of-Thought prompting because the reasoning module processes only the small, relevant path rather than the entire story.

5. Significance

Bridging the Gap: PoT effectively bridges the gap between the flexibility of LLMs and the rigor of symbolic reasoning without requiring extensive fine-tuning.
Error Mitigation: It offers a practical solution to the "hallucination" problem in LLM reasoning by structuring the problem space into a graph, allowing the system to "see" contradictions or alternative paths rather than blindly following a linear chain of thought.
Scalability: The framework is adaptable to various domains (spatial, kinship, etc.) and can utilize either LLMs or symbolic solvers depending on the availability of domain rules, making it a versatile tool for complex reasoning tasks.

In conclusion, Path-of-Thoughts represents a significant step forward in making LLMs more reliable for complex, multi-hop reasoning tasks by structuring the reasoning process through graph-based decomposition and path isolation.