AriGraph

Full title: AriGraph: Learning Knowledge Graph World Models with Episodic Memory for LLM Agents Authors: Petr Anokhin, Nikita Semenov, Artyom Sorokin, Dmitry Evseev, Andrey Kravchenko, Mikhail Burtsev, Evgeny Burnaev (AIRI; Skoltech; London Institute for Mathematical Sciences; University of Oxford) Venue/year: arXiv preprint, 2024 (v3: May 2025) — arXiv:2407.04363 Links: arXiv · local PDF: research-papers/2407.04363-arigraph.pdf

Why this paper matters

AriGraph is the cleanest demonstration that an LLM agent can learn a structured world model from scratch — not retrieve over one. Where MemGPT pages flat text and Generative Agents score a flat stream, AriGraph has the agent build a knowledge graph of semantic triplets, interleaved with episodic vertices holding raw observations, updating it online as it explores — including replacing outdated edges when the world changes (the player takes the key: key, is in, locker → key, is in, inventory) (§2). Retrieval becomes graph traversal: embedding search finds entry-point triplets, BFS expands along the structure, and episodic search hops from triplets back to the full observations that produced them (Algorithm 1). The payoff is dramatic on interactive tasks: the Ariadne agent hits normalized score 1.0 on TextWorld games where full-history, RAG, Reflexion, and Generative-Agents-style memory baselines score 0.05–0.93 (Table 4) — and it transfers competitively to static multi-hop QA at roughly 10x less token cost than GraphRAG (§5.3). It is the bridge between agent memory and world models, and the direct intellectual sibling of Zep and HippoRAG.

The problem

Two research questions frame the paper (§1): RQ1 — can an LLM agent learn a useful structured world model from scratch through environment interaction? RQ2 — does structured knowledge improve retrieval and enable effective exploration? The motivating diagnosis: full-history contexts are costly and drown "complex logic hidden in vast amounts of information"; recurrent/state-space alternatives (RMT, Mamba) are "still in their infancy"; and vanilla RAG "suffers from unstructured nature, greatly reducing the ability to retrieve related information, which may be scattered throughout the agent's memory" (§1). Knowledge graphs fix the scatter problem but existing KG-QA systems (GraphRAG, HOLMES, HippoRAG) build graphs from static documents — "these studies do not address the context of functioning within an interactive environment, nor do they take into account the updates to knowledge graphs prompted by new experiences" (§6). Interactive worlds are partially observable and mutable: facts go stale the moment you act. The missing piece is a memory that is structured (for multi-hop recall), episodic (for detail the triplets drop), and self-updating (for a world that changes underneath you).

The mechanism

The memory graph (§2, Figure 2A)

The world model is a graph G = (Vs, Es, Ve, Ee):

• Semantic vertices Vs — objects/concepts extracted from observations.
• Semantic edges Es — triplets (object1, relation, object2) stored as (v, rel, u); this is the semantic memory ("Kitchen, is west of, Living Room", "Recipe, requires, Red Pepper").
• Episodic vertices Ve — one per step: v_e^t = o_t, the full raw textual observation.
• Episodic edges Ee — e_e^t = (v_e^t, E_s^t): each step's episodic vertex is linked to all triplets extracted from that observation, encoding "happened at the same time" (footnote 1 concedes these are really hyperedges).

So every fact knows which moments produced it, and every moment knows which facts it contributed — a two-way index between compressed knowledge and raw experience.

Graph construction and outdated-edge replacement (§2, "Constructing AriGraph")

On each new observation o_t: (1) an LLM extracts new triplets (V_s^t, E_s^t) (extraction prompt in Appendix E — atomic subjects/objects, ≤7-word triplets, inventory conventions like item, is in, inventory); (2) the system gathers E_s^rel, all existing semantic edges incident to the mentioned vertices; (3) the LLM compares E_s^rel against the new triplets and flags outdated edges, which are removed — with prompt-level guardrails against over-deletion ("triplets should not be replaced if they provide distinct or complementary information... If there is uncertainty about whether a triplet should be replaced, prioritize retaining the existing triplet"); (4) new triplets are merged in; (5) episodic vertex v_e^t and its episodic edge are appended. Deletion-by-replacement is the paper's key departure from append-only memories: the semantic layer stays current while episodic history remains complete.

Two-step retrieval (§2, Algorithms 1–2)

Semantic search SemanticSearch(q, Vs, Es, d, w) is BFS over the graph seeded by embedding similarity: a pretrained Contriever model scores query against edge texts and returns the top-w closest triplets; the vertices incident to those triplets become new queries at depth+1; expansion stops at depth d. Width w controls beam size per hop, depth d controls how many hops of associative structure are pulled in — so (d, w) directly trades recall of scattered-but-linked facts against noise.

Episodic search then takes the retrieved triplets as input and scores every episodic vertex by

rel(v_e^i) = (n_i / max(N_i, 1)) · log(max(N_i, 1))

where n_i = how many of the retrieved triplets are incident to episode i's edge, and N_i = the episode's total triplet count (Eq. 1). The ratio rewards episodes dense in currently-relevant facts; the log factor (log2) up-weights information-rich observations and prevents trivial ones from scoring high — single-triplet observations get zero weight outright. The top-k episodes return as full raw text, recovering detail the triplets abstracted away.

The Ariadne agent (§3, Figure 2B)

AriGraph is the long-term memory of a full cognitive architecture: working memory holds the goal, current observation, recent action history, and the retrieved semantic + episodic knowledge; a planning module maintains a plan as task-relevant sub-goals (each with a reason), re-evaluating after every action's feedback; a decision module follows ReAct — rationale, then one action from the valid list. The graph also extends the action space: "go to location" commands are executed by computing routes over the spatial triplets, and an exploration sub-agent detects unexplored exits from the graph (triplets like "kitchen, has an unexplored exit, south"; Algorithm 3, Appendices A–B). That is RQ2's second half: structure isn't just for recall, it drives navigation and exploration.

The algorithm

Reconstructed from §2, Algorithm 1 (memory graph search) and Algorithm 2 (semantic search):

# ---------- LEARNING (every step t) ----------
def update_graph(o_t):
    V_new, E_new = LLM_extract_triplets(o_t)          # (obj1, rel, obj2) list
    E_rel  = edges_incident_to(V_new)                  # existing facts about same objects
    stale  = LLM_detect_outdated(E_rel, E_new)         # e.g. key,is in,locker -> inventory
    Es.remove(stale)                                   # semantic layer stays CURRENT
    Vs.add(V_new); Es.add(E_new)
    Ve.add(v_e = o_t)                                  # episodic layer stays COMPLETE
    Ee.add((v_e, E_new))                               # "happened at the same time"

# ---------- RETRIEVAL (Algorithm 1) ----------
def memory_search(queries Q, k, d, w):
    E_out = {}
    for q in Q:                                        # queries: obs, plan, goal...
        E_out |= SemanticSearch(q, Vs, Es, d, w)
    V_out = EpisodicSearch(E_out, Ve, Ee, k)
    return E_out, V_out                                # triplets + raw observations

def SemanticSearch(q, Vs, Es, d, w):                   # Algorithm 2: embedding-seeded BFS
    L = queue([q]); D[q] = 0; E_found = {}
    while L not empty:
        q' = L.dequeue()
        if D[q'] >= d: continue                        # depth cutoff
        E' = EmbedAndRetrieve(Es, q', w)               # Contriever: top-w closest edges
        for edge in E':
            for v in incident_vertices(edge):
                if v not in L: L.enqueue(v); D[v] = D[q'] + 1
        E_found |= E'
    return E_found

def EpisodicSearch(E_in, Ve, Ee, k):                   # Eq. 1
    for episode i:
        n_i = |E_in ∩ triplets_of(i)|                  # relevant facts in this episode
        N_i = |triplets_of(i)|                         # its total information content
        rel_i = (n_i / max(N_i,1)) * log2(max(N_i,1))  # zero if N_i == 1
    return top_k_by(rel_i)

# ---------- THE AGENT LOOP (§3) ----------
loop:
    o_t = observe(); update_graph(o_t)
    sem, epi = memory_search({o_t, plan, goal}, k, d, w)
    working_memory = {goal, o_t, recent_actions, sem, epi, unexplored_exits}
    plan   = LLM_plan(working_memory)                  # sub-goals + reasons, revised
    action = LLM_react(working_memory, plan, valid_actions)   # rationale -> action
    execute(action)                                    # incl. graph-routed "go to X"

Walkthrough:

• update_graph is where the "world model" earns its name: the semantic layer is a belief state, mutated to stay true, while episodic vertices are an immutable log. Compare MemGPT (log + summary, no beliefs) and Generative Agents (log + reflections, never deletes).
• LLM_detect_outdated is the risky step — deleting a still-true fact is worse than keeping a stale one, hence the conservative prompt bias toward retention (Appendix E).
• SemanticSearch starts unstructured (embeddings find entry points even with vocabulary mismatch — searching "grill" can reach "bbq, used for, grilling") and continues structured (BFS follows edges embeddings would never rank). Depth d = multi-hop reach; width w = per-hop beam.
• EpisodicSearch is retrieval through structure: episodes are never embedded and matched directly — they are scored by overlap between their triplets and the semantically retrieved ones. The n_i/N_i · log N_i shape is precision times information content.
• The loop's queries include the current plan, so retrieval is goal-conditioned, not just observation-conditioned — memory serves the plan, and the plan is revised against memory each step.

Results that matter

Setup notes: five attempts per game, score averaged over the three best runs; LLM backbone gpt-4-0125-preview for AriGraph and all LLM baselines (§4.1), so differences isolate the memory module — decision-making is identical across conditions (Figure 1 caption).

Limitations & how to defend the findings

• "Text games are toy worlds — triplet extraction is easy there." Partly true and partly answered: NetHack (§5.2) is a substantially messier environment, and Ariadne with crippled room-only observations nearly matches NetPlay running with a handcrafted full-level "memory oracle." Still, all environments are text-native; the paper itself lists multi-modal observations as future work (§7).
• "Graph quality is never measured — how do we know the graph is right?" Conceded explicitly: "direct measurement of its correspondence to the true graph is extremely challenging" due to synonyms and equivalent restructurings, so the paper measures growth/update rates instead (Appendix C) — the graph grows during exploration and plateaus once the environment is familiar (Figure 5), and growth is cleaner with stronger LLMs (LLaMA-3-8B builds a far noisier graph than GPT-4, Figure 6). The performance numbers are the indirect quality measure.
• "The ablations cut both ways." Yes — and honestly reported. Removing episodic memory helps on Cleaning (0.92 vs 0.79, Table 4) because that game punishes stale detail more than it rewards recall: "it is more important to properly filter outdated information... than not to lose any information" (§5.1). Episodic memory pays off precisely where dense detail matters (recipes in Cooking: 1.0 vs 0.64). Memory design is task-dependent; AriGraph gives you both dials.
• "On static QA it doesn't even win." Correct on MuSiQue: HOLMES beats AriGraph(GPT-4) 48.0 vs 45.0 EM. The paper's defense: all QA baselines are purpose-built for QA with task-specific prompt tuning; AriGraph is a general agent memory competitive out of domain, it takes best-in-table HotpotQA EM (68.0), and it costs ~10x less than GraphRAG (§5.3, Table 3). Also fair to note: it swapped Contriever for BGE-M3 for QA (§4.3) — retrieval quality matters and was tuned once.
• "Outdated-edge detection could silently corrupt memory." The paper does not quantify wrong-deletion rates; the guardrails are prompt-level (Appendix E) and replacements are empirically rare after exploration settles (Figure 5, "Replacements" track). This is the component to instrument first in any reimplementation.
• "Expert knowledge is baked in." The exploration machinery "uses expert knowledge about what elements of the semantic graph can represent locations and exits" (Appendix B), and Cooking observations were augmented with tool-use instructions for both LLM and human players (Appendix F). Real, disclosed scaffolding — the world-model learning is from scratch; the interface to it is not fully.

Connections

• CoALA, instantiated literally: semantic edges = semantic memory, episodic vertices = episodic memory, working memory as prompt-composition hub, ReAct decision cycle — Ariadne is close to a reference implementation of CoALA's diagram with a graph as the long-term store.
• Zep/Graphiti and HippoRAG are the production siblings: Zep's temporal knowledge graph invalidates outdated edges (via validity intervals rather than deletion) exactly where AriGraph replaces them; HippoRAG's Personalized-PageRank-over-KG is the static-corpus analogue of AriGraph's BFS-with-depth/width. AriGraph's distinction: the graph is built online from interaction, not offline from documents (§6).
• vs Generative Agents (the "Simulacra" baseline here): recency/importance/relevance scoring over a flat stream loses to structure on every hard task (Table 4) — evidence that associative topology, not scoring finesse, is what multi-hop interactive recall needs. AriGraph even uses GA's memory as a named baseline, a rare direct architecture-vs-architecture comparison.
• vs MemGPT: orthogonal answers to context limits — MemGPT manages placement of flat text across tiers; AriGraph changes the representation. A MemGPT-style archival store could hold an AriGraph; nothing in either design excludes the other.
• World-model reading: the semantic layer is a belief state over a POMDP updated by an LLM "sensor model" (triplet extraction) and "update rule" (outdated-edge replacement) — the same role the latent state plays in model-based RL world models, but symbolic, inspectable, and editable. The RL comparison (beating GATA/EXPLORER, which learn belief graphs by training) makes this framing explicit.
• Reflexion's limits, shown empirically: cross-episode verbal reflection improves try 2 then degrades on later tries in Cleaning (§5.1) — episodic learning without a current-state store accumulates advice, not knowledge.

Reading guide

• Read first: §2 in full (memory structure → construction/outdated-edge replacement → two-step retrieval, with Algorithm 1) — it is compact and the entire contribution. Then §3 for how the graph plugs into planning/ReAct.
• The one figure to study: Figure 2 — panel A shows the two-layer graph (episodic vertices O1–O3 fanning into shared semantic triplets); panel B shows the full Ariadne loop with the three LLM modules. Together they are the paper.
• Then the evidence: Figure 3 (main results + ablations + human comparison — note where "w/o episodic" wins), Table 4 in Appendix G (the complete score matrix), Table 2 (QA) with Table 3 (the 10x token-cost claim).
• Appendices worth mining: E (the actual extraction/replacement prompts — the deletion guardrails are directly reusable), A (Algorithm 2's BFS details and the "grill"→"bbq" example), C (graph-growth-vs-LLM-quality study).
• Skimmable: §4's game descriptions (Appendix F has the fuller versions), §6 related work unless you need the GraphRAG/HOLMES positioning, Figures 7–13 (environment screenshots).