Source-linked AI summary
AriGraph: Learning Knowledge Graph World Models with Episodic Memory for LLM Agents
Petr Anokhin, Nikita Semenov, Artyom Sorokin, Dmitry Evseev, Andrey Kravchenko, Mikhail Burtsev, Evgeny Burnaev
TL;DR
LLM agents need memory that supports learning from past experience, but full-history and unstructured retrieval approaches have limitations for continuous interaction and complex reasoning. AriGraph integrates semantic and episodic memory in a graph that Ariadne uses with planning and decision-making; the paper reports strong interactive-game results and competitive multi-hop question answering.
Problem
Full-history and unstructured retrieval approaches have limitations for continuous interaction and handling complex logic, while effective ways to equip LLM agents with long-term memory remain an open question.
Source: §1 · p. 1Method
AriGraph builds and updates a graph integrating semantic knowledge and episodic experiences, and Ariadne combines it with planning and decision-making.
Source: §1 · pp. 1–2Results
Takeaways & Limitations
The authors report that structured knowledge representation supports efficient retrieval and reasoning and that AriGraph maintains high performance as task complexity increases.
Source: §7 · p. 7The approach may be further enhanced with multimodal observations, procedural memories, and more sophisticated graph search methods.
Source: §7 · p. 7
Abstract
from arXiv · showhide
Advancements in the capabilities of Large Language Models (LLMs) have created a promising foundation for developing autonomous agents. With the right tools, these agents could learn to solve tasks in new environments by accumulating and updating their knowledge. Current LLM-based agents process past experiences using a full history of observations, summarization, retrieval augmentation. However, these unstructured memory representations do not facilitate the reasoning and planning essential for complex decision-making. In our study, we introduce AriGraph, a novel method wherein the agent constructs and updates a memory graph that integrates semantic and episodic memories while exploring the environment. We demonstrate that our Ariadne LLM agent, consisting of the proposed memory architecture augmented with planning and decision-making, effectively handles complex tasks within interactive text game environments difficult even for human players. Results show that our approach markedly outperforms other established memory methods and strong RL baselines in a range of problems of varying complexity. Additionally, AriGraph demonstrates competitive performance compared to dedicated knowledge graph-based methods in static multi-hop question-answering.
1 Introduction
LLM agents need long-term memory to accumulate knowledge, but full-history and unstructured retrieval approaches have limitations for continuous interaction and complex reasoning. AriGraph combines semantic and episodic memory in a graph, and Ariadne is reported to outperform other memory approaches and RL baselines in interactive games while performing competitively on multi-hop question answering.
1 Introduction
- Full-history memory is costly for continuous interaction and can struggle with complex logic; unstructured retrieval may miss related information scattered across memory.The introduction also notes that alternative long-term memory frameworks remain in their infancy.Source: §1 · p. 1
- AriGraph integrates semantic knowledge and episodic experiences in a graph that the agent updates while interacting with its environment.Ariadne combines this memory with retrieval, planning, and decision-making.Source: §1 · pp. 1–2
- Ariadne significantly outperforms other LLM memory approaches and RL baselines in interactive games, while AriGraph performs competitively on multi-hop question answering.The paper also reports NetHack scores comparable to an agent with ground-truth knowledge.Source: §1 · p. 2
2 AriGraph World Model
AriGraph represents semantic knowledge and episodic observations in one graph, updating that world model from each new observation. Retrieval combines semantic graph search with episodic search over observations linked to relevant triplets.
2 AriGraph World Model
- The world model separates semantic vertices and edges from episodic vertices and edges, with episodic edges connecting triplets from an observation to that observation’s vertex.These episodic links represent a temporal relationship: the connected knowledge happened at the same time.Source: §2 · p. 2
- For each observation, AriGraph extracts semantic triplets, removes outdated incident edges, adds updated semantic knowledge, and records the observation in episodic memory.Episodic memory adds an observation vertex and an edge connecting it with the triplets extracted at that step.Source: §2 · p. 3
- Retrieval first selects relevant semantic triplets by similarity, then expands through graph structure using configurable search depth and breadth.Episodic search uses those triplets to find linked past observations.Source: §2 · p. 3
- Episodic search ranks observations by their linked input triplets, weighting against low-information observations and returning the top k vertices.Observations with exactly one triplet receive zero weight; more extracted triplets receive greater weight through log2 scaling.Source: §2 · p. 3
3 Ariadne cognitive architecture
Ariadne combines AriGraph long-term memory with working memory, planning, and decision-making while interacting with an unknown environment. It updates its plan based on action feedback and selects actions aligned with the current plan.
3 Ariadne cognitive architecture
- Ariadne learns a world model, plans, and executes actions at each time step, keeping AriGraph as long-term memory and current task information in working memory.Working memory includes the goal, current observation, and recent observation-action history.Source: §3 · p. 3
- The planning module creates or updates task-relevant subgoals and adjusts the plan using feedback on prior actions.The revised plan is then made available to the decision-making module.Source: §3 · p. 3
- The decision module selects a valid action consistent with the plan and can use graph-stored spatial relations to route to a target location.It follows the ReAct framework and articulates a rationale before acting.Source: §3 · p. 3
4 Experimental Setup
The evaluation spans partially observable TextWorld games, NetHack dungeon exploration, and static multi-hop question answering, with comparisons tailored to each setting.
4.1 TextWorld interactive environments
- TextWorld evaluation includes spatial-navigation, object-collection, and tool-manipulation games, plus a four-level Cooking task for RL comparisons.Human performance was collected through a graphical interface for basic Treasure Hunt, Cleaning, and Cooking versions; incomplete sessions were excluded.Source: §4.1 · pp. 3–4
- For baseline comparisons, Ariadne’s planning and decision-making module used alternative memories instead of AriGraph: full history of observations and actions, iterative summarization, RAG, RAG with Reflexion, and Simulacra.The LLM backbone for AriGraph and other LLM-based baselines was gpt-4-0125-preview.Source: §4.1 · p. 4
4.2 NetHack environment
- NetHack compares restricted-room Ariadne with restricted-room NetPlay and NetPlay given explored-level observations.Ariadne receives only the current room or corridor, testing whether AriGraph can retain relevant information about the explored level.Source: §4.2 · pp. 4–5
4.3 Multi-hop Q&A
- Multi-hop QA evaluation uses 200 random Musique and HotpotQA samples and compares AriGraph with GraphReader, ReadAgent, HOLMES, GraphRAG, and RAG baselines.The setup replaces Contriever with BGE-M3 and adjusts prompts for the QA tasks.Source: §4.3 · p. 5
5 Results
Ariadne performs strongly across interactive text-game tasks, including comparisons with reinforcement-learning agents and human players. It also performs comparably to a memory-oracle baseline in NetHack and competitively on multi-hop question answering.
5.1 TextWorld
- Ariadne completes Treasure Hunt Hardest despite more than twice Hard’s rooms, additional keys, and distractors; baselines fail to solve Treasure Hunt.Ariadne completes Treasure Hunt in about fifty steps and maintains robust performance in Treasure Hunt Hard.Source: §5.1 · p. 5
- In Cleaning, filtering outdated object locations matters more than retaining all information; Ariadne notably outperforms alternatives, including Reflexion.Reflexion improves over RAG on its second try, then degrades on later tries.Source: §5.1 · p. 5
- Ariadne outperforms reinforcement-learning agents at all four Cooking difficulty levels and the average human player on every task.It scores similarly to the best human plays in Cooking and Treasure Hunt, but underperforms in Cleaning.Source: §5.1 · p. 6, Figure 4 · p. 6
- AriGraph grows during exploration and flattens as the agent becomes familiar with the environment; its growth rate also decreases with stronger LLM backbones.The graph grows moderately when Treasure Hunt and Cooking add rooms and objects in their hard versions.Source: §5.1 · p. 6
- Ariadne shows a clear advantage over LLM-based and reinforcement-learning baselines across TextWorld tasks.The reported roles of semantic memory include building and updating knowledge of the current environment; episodic memory helps retrieve detailed information not captured semantically.Source: §5.1 · p. 6
5.2 NetHack
- Ariadne performs comparably to NetPlay with full-level information while receiving only room observations.NetPlay with memory-oracle access achieved the highest scores, while NetPlay with only current-room observations performed worst.Source: §5.2 · p. 6, Table 1 · p. 6
5.3 Multi-hop Q&A
- AriGraph with GPT-4 and GPT-4o-mini outperforms several document-Q&A baselines; GPT-4o-mini is weaker than GraphRAG on Musique but stronger on HotpotQA.The approach is reported as more than 10x cheaper than GraphRAG.Source: §5.3 · p. 6
- With GPT-4, HOLMES achieves the best performance, while AriGraph produces comparable results.The cited comparison notes that the Q&A baselines were purpose-built, with task-specific prompt tuning and architectural enhancements.Source: §5.3 · p. 6
6 Related work
Prior LLM-agent memory systems and text-based-game agents often lack structured knowledge representations, while knowledge-graph Q&A work generally does not address updates from interactive experience. AriGraph is compared with work in both areas, including its performance on static multi-hop Q&A.
Related LLM agents
- Earlier open-ended Minecraft agents use skill libraries, summaries, or episodic plans, but lack semantic knowledge structure and may rely on extensive LLM knowledge or the Minecraft wiki.Reflexion and CLIN store insights from trajectories without structural knowledge representation; LARP separates semantic and episodic memories and also lacks that structure.Source: §6 · pp. 6–7
Graph scaling and Q&A comparison
- AriGraph’s graph grows during exploration and learning, then quickly saturates; hard versions of Treasure Hunt and Cooking produce moderate growth as rooms and objects increase.The section also presents AriGraph memory as competitive with strong Q&A baselines on multi-hop datasets.Source: Figure 5 · p. 7, Table 2 · p. 7
Knowledge-graph Q&A
- Knowledge-graph Q&A methods build graphs from documents, but the cited work does not address interactive environments or graph updates prompted by new experiences.The related methods named include GraphReader, HOLMES, HippoRAG, and GraphRAG.Source: §6 · p. 7
Text-based environments
- Text-based environments were developed for reinforcement-learning evaluation, and raw LLMs perform poorly there without agent architecture and memory.The cited literature also includes multiple experiments applying LLMs to these scenarios.Source: §6 · p. 7
7 Conclusions
AriGraph is a knowledge-graph world model for LLM agents that integrates semantic and episodic memories; Ariadne combines it with planning and decision-making. The paper reports advantages over other memory systems in interactive tasks and competitive performance in multi-hop question answering.
7 Conclusions
- AriGraph integrates semantic and episodic memories from textual observations into a structured, dynamic knowledge-graph world model for LLM agents.Ariadne combines this memory architecture with planning and decision-making.Source: §7 · p. 7
- Ariadne with AriGraph significantly outperforms other memory systems on long-term-memory tasks, including decision-making, planning, and exploration in partially observable environments.The paper also reports competitive performance on multi-hop Q&A benchmarks.Source: §7 · p. 7
- The authors identify multimodal observations, procedural memories, and more sophisticated graph search as possible enhancements.Source: §7 · p. 7
Memory Graph Search Details
The section describes semantic graph search and an exploration mechanism that uses the current plan and graph-derived exit information. Semantic search is BFS-like and uses embedding retrieval to find relevant triplets.
Memory Graph Search Details
- SemanticSearch is close to breadth-first search, but uses Contriever to retrieve the top w edges most similar to each query by embedding dot product.For a semantic-vertex query, retrieval often returns incident edges and can also find edges attached to semantically close vertices.Source: Memory Graph Search Details · p. 10
B Exploration
- An auxiliary agent activates or deactivates exploration mode based on whether the established plan calls for exploration.The graph agent finds probable unexplored exits from location and exit triplets, using expert knowledge about which graph elements represent locations and exits.Source: B Exploration · p. 10
C Graph statistics
The section tracks graph growth and updates rather than measuring graph accuracy, which is difficult to assess because equivalent constructions can vary. Growth is most active during exploration and slows in familiar areas, and decreases as the LLM used to build the graph improves.
C Graph statistics
- The authors measure graph growth and update rates instead of correspondence to a true graph, which is hard to assess given construction variability and potentially useful extra information.The separate random-action experiment used Cleaning, which offers many interactive objects and cannot be failed.Source: C Graph statistics · p. 10
- Graph growth is most active during exploration, slows in familiar areas, and decreases as the quality of the graph-building LLM increases.Source: C Graph statistics · pp. 10–11
- Figure 6 reports graph-construction and updating statistics during a random walk.Source: Figure 6 · p. 11
D Token usage
The section identifies Table 3 as a token-usage analysis for text games and QA tasks, then gives prompts used in the system. The prompts specify triplet extraction and updating, exploration assessment, planning, action selection, and situation summaries.
D Token usage
- Table 3 covers token usage analysis for text games and QA tasks.Source: Table 3 · p. 11
E LLM Prompts
- Extraction prompts represent observations as subject–relation–object triplets and ask for connections across distinct parts of an observation.They also direct the system to include related facts about entities and use a structured triplet format.Source: E LLM Prompts · p. 12
- The outdated-triplet prompt replaces existing facts only when new triplets duplicate or conflict with the same aspect, favoring retention when uncertain.Source: E LLM Prompts · p. 12
- An exploration prompt asks whether planned subgoals require exploring, while action-selection instructions prioritize the main goal, actionable subgoals, and unexplored areas when relevant.Source: E LLM Prompts · pp. 12–13
- The guide prompt asks for a concise situation summary focused on essential details, prior action outcomes, and information useful for decision-making.Source: E LLM Prompts · p. 13
F Text-based Games
This section describes three interactive TextWorld tasks and a separate, simpler cooking benchmark for comparison with RL agents. The benchmark setup uses randomly generated environments and task-specific instructions.
F Text-based Games
- Treasure Hunt requires following a chain of clues to unlock a golden locker, with variants ranging from 12 rooms and 4 keys to 36 rooms, 7 keys, and extra items as noise.The hard variant has 16 rooms and 5 keys, with the second key significantly harder to find.Source: F Text-based Games · p. 14
- Cleaning asks agents to return 11 misplaced items across nine rooms, rewarding correct moves and penalizing manipulation of correctly placed items.The task emphasizes exploration and memory of where items belong, unlike the one- or two-location focus of TextWorld Commonsense.Source: F Text-based Games · p. 14
- Cooking requires finding a recipe, selecting ingredients, and applying the specified preparation methods and tools; an incorrect action or tool loses the game.The medium task has 9 locations and 3 ingredients, while the hard task has 12 locations and 4 ingredients; initial instructions explain appliance use.Source: F Text-based Games · p. 14
- The RL comparison uses a simpler four-level Cooking variation, ranging from one ingredient in one room to three ingredients in six rooms.The levels vary cutting and cooking requirements, and are described as significantly simpler than the main tasks.Source: F Text-based Games · p. 14
- LLMs received cooking-tool instructions in their first observation, and the LLM and RL comparisons used environments that were not fully identical.The agents were tested on three randomly generated environments per difficulty; without the instructions, the game was described as unbeatable for LLM agents and humans.Source: F Text-based Games · p. 14
G Additional graphics and tables
The supplemental results report normalized scores across TextWorld tasks and show performance dynamics in test games. The reported comparisons favor AriGraph across tasks and include differences between task difficulty levels.
G Additional graphics and tables
- The cited section says Table 4 summarizes results of all experiments across Treasure Hunt (Medium, Hard, Hardest), Cooking (Medium, Hard, Hardest), and Cleaning.Figure 14 presents step-by-step performance dynamics for different agents and human players.Source: G Additional graphics and tables · p. 14
- AriGraph significantly outperforms all baselines and scales well to larger, more complex environments in the reported TextWorld tasks.The table reports normalized scores across the Treasure Hunt, Cooking, and Cleaning tasks.Source: G Additional graphics and tables · p. 14, Table 4 · p. 15
- In Figure 14, Ariadne performs comparably to top players in Treasure Hunt, slightly behind in Cleaning, and faster than top human players in Cooking.The hard task variants show no decrease in Ariadne’s performance quality as difficulty increases and highlight the importance of episodic memory.Source: Figure 14 · p. 21