From Entity-Centric to Goal-Oriented Graphs: Enhancing LLM Knowledge Retrieval in Minecraft

This paper introduces a Goal-Oriented Graph (GoG) framework that enhances Large Language Models' procedural reasoning in complex environments like Minecraft by structuring knowledge as goal-dependent chains, thereby significantly outperforming existing retrieval-augmented methods such as GraphRAG.

The Gist

Imagine you are teaching a very smart, but slightly scattered, robot how to play Minecraft. Your goal is to tell it, "Build a diamond axe."

The problem is that Minecraft is a game of logic and steps. You can't just build a diamond axe; you first need wood, then planks, then sticks, then a crafting table, then a wooden pickaxe, then stone, then iron, and so on. It's a long, complex chain of events.

This paper introduces a new way to help the robot understand these chains. Let's break it down using some everyday analogies.

The Problem: The "Shredded Paper" Approach

The researchers looked at how other AI systems (like GraphRAG) try to learn. They found these systems act like someone who took a detailed instruction manual, shredded it into millions of tiny pieces, and then tried to rebuild the book by looking at the scraps.

• The Old Way (Entity-Centric): The AI looks at the manual and sees facts like: "Stone is hard," "Pickaxes are made of wood," "Iron is shiny." It connects these facts loosely.
• The Result: When you ask the robot to "Make a diamond axe," it gets confused. It knows what a diamond is and what an axe is, but it doesn't know the order of operations. It might try to smelt a diamond (which is impossible) or forget that it needs a furnace first. It's like trying to bake a cake by just knowing that "flour exists" and "eggs exist," without knowing the recipe.

The Solution: The "Goal-Oriented Graph" (GoG)

The authors propose a new framework called Goal-Oriented Graphs (GoG). Instead of shredding the manual, they reorganize it into a flowchart or a family tree of tasks.

• The New Way (Goal-Centric): Instead of just listing facts, the AI builds a map where every node is a Goal.
  • Top Node: "Make Diamond Axe."
  • Branch 1: "To do this, you must first make an Iron Pickaxe."
  • Branch 2: "To make an Iron Pickaxe, you must first smelt Iron Ingots."
  • Branch 3: "To smelt Iron, you need a Furnace and Coal."

This structure is like a recipe book rather than a dictionary. It explicitly tells the robot: "You cannot do Step B until Step A is finished."

How It Works in Practice

1. Building the Map: The AI reads the Minecraft Wiki and recipe files. Instead of just memorizing facts, it uses a large language model to ask, "What do I need to do this?" and "What do I need to do that?" It builds a giant, organized tree of dependencies.
2. Retrieving the Path: When you give the robot a task ("Craft a Diamond Axe"), it doesn't guess. It looks at its map, finds the "Diamond Axe" goal, and traces the path backward to the very first step (chopping a tree).
3. The Plan: It hands the robot a clear, step-by-step list: "Chop tree -> Make planks -> Make sticks -> Make table..."

Why It's Better (The Results)

The researchers tested this in Minecraft against other methods. Here is what happened:

• Simple Tasks: For easy things like making a wooden sword, all methods worked okay.
• Hard Tasks: For complex things like making a diamond axe or armor, the old methods (GraphRAG) often failed completely. They got lost in the noise of disconnected facts.
• The GoG Winner: The new method succeeded 3 times more often on gold tasks and 58% more often on armor tasks compared to the next best method.

The Analogy:
Imagine you are lost in a giant library.

• GraphRAG gives you a list of every book title in the library. You have to guess which book has the map you need. You might pick a book about "History of Rome" when you needed "How to fix a car."
• GoG gives you a treasure map. It doesn't just list books; it draws a line from "You are here" to "The Treasure," showing you exactly which doors to open and in what order.

The "Hallucination" Fix

One of the coolest findings was how GoG stopped the AI from making silly mistakes.

• The Mistake: Other AIs tried to "smelt a diamond." In the game, you smelt ore to get diamonds. You can't smelt the diamond itself. The old AI didn't know the difference because it was just matching words.
• The Fix: Because GoG is built on procedures (recipes), it knows that "Smelting" is a specific step that only happens before you have the final item. It prevents the robot from trying to cook the finished meal.

Summary

This paper is about teaching AI to stop thinking in isolated facts and start thinking in logical stories. By organizing knowledge into a hierarchy of goals (like a family tree of tasks), the AI can solve complex, multi-step problems that used to stump it. It turns a chaotic pile of information into a clear, step-by-step instruction manual that even a robot can follow.

Technical Summary

1. Problem Statement

Large Language Models (LLMs) excel at general reasoning but struggle with step-by-step procedural reasoning in complex, interactive environments like Minecraft. While Retrieval-Augmented Generation (RAG) methods, specifically GraphRAG, attempt to bridge this gap by organizing knowledge into entity-relation graphs, they suffer from a fundamental limitation:

• Fragmentation: GraphRAG relies on an entity-centric paradigm, extracting low-granularity triples (e.g., "stone is used for pickaxe"). This fragments causal knowledge, making it difficult for LLMs to reconstruct coherent, multi-step plans.
• Noise: The retrieval process often returns excessive, irrelevant connected nodes (e.g., all entities related to "stone"), creating noisy contexts that degrade planning performance.
• Lack of Hierarchy: Existing methods fail to explicitly model the hierarchical decomposition of high-level goals into actionable subgoals and prerequisites.

2. Methodology: Goal-Oriented Graphs (GoG)

The authors propose Goal-Oriented Graphs (GoG), a framework that shifts the paradigm from entity relations to logical goal dependencies.

A. Graph Structure

• Nodes: Represent goals (e.g., "craft a wooden pickaxe") rather than entities. Each node contains structured attributes:
  • Name, Description, Aliases
  • Preconditions: Required tools and materials.
  • Postconditions: Expected outcomes.
• Edges: Represent subgoal relationships (prerequisite dependencies). An edge exists from Goal A to Goal B if Goal B is a prerequisite for Goal A.
• Construction:
  1. Extraction: An LLM extracts goals and attributes from unstructured text sources (Minecraft Wiki, recipe files).
  2. Merging: New goals are merged with existing ones using embedding similarity (cosine similarity of names and condition lists) to handle aliases and duplicates.
  3. Derivation: Subgoal edges are derived by matching the preconditions of a new goal with the postconditions of existing goals.
  4. Result: A directed acyclic graph (DAG) representing the task hierarchy.

B. Inference and Planning Pipeline

1. Goal Selection: Given a task query (e.g., "craft diamond axe"), the system retrieves the top-$k$ matching goals based on embedding similarity. An LLM selects the best match.
2. Recursive Retrieval: A Depth-First Search (DFS) traverses the graph from the selected goal to retrieve all subgoals, forming a coherent reasoning chain. Cycles are pruned to ensure feasibility.
3. Plan Generation: The retrieved goal tree and the aggregated list of required materials/tools are fed to an LLM to generate a step-by-step execution plan.
4. Replanning: If execution fails (e.g., missing item), the system uses the goal tree to calculate the specific missing prerequisites and replans.

3. Key Contributions

1. Novel Framework (GoG): Introduced a goal-centric knowledge graph structure that explicitly models procedural dependencies (goals, preconditions, postconditions), contrasting with traditional entity-centric graphs.
2. Goal-Driven Retrieval Algorithm: Developed a recursive retrieval mechanism that constructs explicit reasoning chains by traversing goal hierarchies, overcoming the fragmentation issues of GraphRAG.
3. Comprehensive Evaluation: Validated the framework in Minecraft, a demanding benchmark for long-horizon planning, demonstrating significant improvements over state-of-the-art baselines.
4. Ablation and Robustness: Analyzed the impact of different knowledge components (goal trees vs. material lists) and demonstrated that GoG degrades gracefully even when constructed from noisy, unstructured text.

4. Experimental Results

Experiments were conducted on 66 Minecraft tasks (ranging from wood to diamond/armor) using three LLMs (Llama 3.2-Vision, Gemma 3, Qwen 2.5-VL).

• Performance on Complex Tasks:
  • Success Rate: GoG significantly outperformed baselines on difficult tasks. For example, on Gold tasks, GoG achieved a 72.3% success rate compared to 5.6% for the Hierarchical Knowledge Graph (HKG) baseline and 0% for GraphRAG.
  • Long-Horizon Planning: On Diamond tasks, GraphRAG and Vanilla baselines failed completely (0% success), while GoG achieved 66.1% success.
  • Efficiency: GoG required significantly fewer in-game steps to complete tasks compared to baselines, indicating more efficient planning.
• Comparison with Baselines:
  • GraphRAG: Often performed worse than the Vanilla baseline due to retrieval noise (irrelevant entities).
  • HKG (Optimus-1 inspired): Performed better than GraphRAG but lacked the ability to handle complex procedural logic not found in simple recipe files (e.g., tool requirements for mining).
• Ablation Studies:
  • Providing both the Goal Tree and Material List yielded the highest plan quality (Goal Satisfaction, Soundness, Completeness, Efficiency).
  • GoG remained robust even when constructed from "noisy" free-form text, though performance dipped slightly in efficiency.

5. Significance and Future Directions

• Paradigm Shift: The paper argues that for procedural tasks, goal hierarchies are superior to entity networks. It solves the "shredded paper" problem of GraphRAG by keeping causal chains intact.
• Generalizability: While tested in Minecraft, the GoG framework is applicable to any domain with structured procedural knowledge (e.g., manufacturing, cooking, medical troubleshooting) where tasks can be decomposed into goals and preconditions.
• Future Work: The authors plan to explore dynamic graph construction for creative tasks, multi-path optimization (finding the most efficient route among multiple valid decompositions), and online incremental replanning.

Conclusion:
The GoG framework successfully enhances LLM reasoning in complex environments by structuring knowledge around logical dependencies rather than semantic entities. This approach enables agents to construct coherent, multi-step plans, significantly outperforming current retrieval-augmented methods in long-horizon procedural tasks.