PaperlayerView exact revision on arXiv

Source-linked AI summary

TAGGRAPH: Tag-Augmented Graphs for Graph Retrieval of Agent Persistent Histories

Yu-Shu Chen, Yu-Jung Liang, Pengtao Xie

arXiv:2609.38353v2cs.IRcs.AI

TL;DR

LLM agents need persistent memory, but retrieval comparisons are difficult when systems vary in representation, indexing, retrieval, and evaluation. This paper evaluates retrieval configurations over shared 5W-style memories, finding that rankings vary across memory settings and that no method leads across all evaluated settings.

  • Problem

    Memory systems vary in representation, indexing, retrieval, and evaluation, making their retrieval behavior difficult to compare.

    Source: §1 · p. 1

  • Method

    The paper compares localized graph traversal, AdaptiveGraph diffusion, and lexical ranking over shared 5W-style memories, with OpenClaw as a raw-input external reference.

    Source: §1 · p. 2, §3.3.4 · p. 4

  • Results

    Retrieval rankings vary across settings: AdaptiveGraph reaches 0.844 MRR on LongMemEval-S, while localized traversal leads on ATANT Core and BM25 leads its stress rounds.

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

  • Takeaways & Limitations

    No method performs best across all evaluated settings, supporting evaluation of retrieval strategies jointly with the memory setting and lexical baselines.

    Source: §1 · p. 2

    The framework tests only the 5W schema, leaves the ATANT crossover unexplained, and does not fully test store-size effects.

    Source: §6.3 · p. 9

Abstract

from arXiv · show

Long-term memory lets LLM agents recall past interactions and remain consistent across sessions, but memory systems are hard to compare because they often vary in representation, indexing, retrieval, and evaluation. We present a controlled evaluation framework based on shared 5W-style conversational memories. Localized graph configurations traverse a common base graph; AdaptiveGraph adds chronological edges and Personalized PageRank diffusion. We also evaluate BM25 over the same extracted notes and OpenClaw as a raw-input external reference. Retrieval rankings vary across memory settings. On LongMemEval-S, AdaptiveGraph is the strongest graph configuration at 0.844 MRR, but BM25 reaches 0.867 and OpenClaw 0.880. On ATANT Core, localized graph traversal outperforms diffusion and BM25, whereas BM25 leads the stress rounds. Reducing LongMemEval-S within the tested range does not reproduce the ATANT diffusion penalty, but the smallest tested store remains larger than ATANT Core, so store size cannot be ruled out. The penalty also persists under a permissive content-match criterion. Vocabulary normalization and extraction quality substantially affect graph retrieval, and missing extraction tags are common among top-five misses. Retrieval strategies should therefore be evaluated jointly with the memory setting and against strong lexical baselines.

1 Introduction

Persistent agent memory must retrieve relevant past interactions from a bounded, costly context, but retrieval depends jointly on how memories are represented, indexed, and ranked. The paper controls these choices over shared 5W-style memories and finds that retrieval rankings vary across evaluated memory settings.

1 Introduction

  • Retrieval quality depends jointly on memory representation, indexing, and search, while many published systems vary these components together.This makes it difficult to identify which choice produces a gain or whether graph retrieval improves on a strong lexical baseline.Source: §1 · p. 1
  • The framework compares graph configurations over a shared 5W-style representation, with localized traversal and AdaptiveGraph diffusion as distinct approaches.AdaptiveGraph adds chronological edges and Personalized PageRank; OpenClaw indexes raw text as an external reference, not a controlled ablation.Source: §1 · pp. 1–2
  • Retrieval rankings vary by setting: AdaptiveGraph leads graph configurations on LongMemEval-S, while localized traversal leads on ATANT Core and BM25 leads its stress rounds.OpenClaw and BM25 score higher than AdaptiveGraph on LongMemEval-S; the ATANT diffusion penalty's cause remains unidentified, and extraction quality affects graph results.Source: §1 · p. 2
  • The paper contributes a controlled comparison interface, an interpretable 5W-style base representation, and evidence that graph and lexical methods trade places across memory settings.Extraction quality constrains all graph configurations.Source: §1 · p. 2

2 Related work

Prior agent-memory work spans free-text, embedding-based, and graph-structured approaches, while benchmarks differ in their memory regimes. This paper narrows the comparison to retrieval behavior over a shared conversational representation.

2 Related work

  • Agent-memory surveys map design choices across storage, consolidation, indexing, and recall, while this paper focuses specifically on retrieval under shared representations.The cited surveys are Hu et al. (2025) and Bei et al. (2025).Source: §2 · p. 2
  • Free-text reflections and embedding retrieval underpin systems such as MemGPT, MemoryBank, and Generative Agents; 5W tags provide a complementary set of explicit graph retrieval keys.The original interaction remains the retrieved unit.Source: §2 · p. 2
  • Embedding-centric systems retrieve by semantic similarity, while the paper compares graph retrieval with a controlled BM25 baseline over the same extracted notes.OpenClaw is an external production reference that ranks raw text using embedding similarity and BM25.Source: §2 · p. 2
  • Graph-memory systems often vary representation and retrieval together, so the paper compares traversal and PageRank diffusion over one shared 5W representation.Examples discussed include GraphRAG, HippoRAG, Zep, MAGMA, and A-MEM.Source: §2 · p. 2
  • LongMemEval tests typed questions over long multi-session histories, whereas ATANT tests continuity in shorter narratives to examine whether rankings transfer across regimes.The controlled configurations share ingestion, representation, and base graph construction; OpenClaw remains outside this comparison.Source: §2 · pp. 2–3

3 Methodology

The methodology standardizes memory ingestion, storage, retrieval, and evaluation so retrieval configurations can be compared over shared conversational memories. It combines extracted 5W representations and graph-based methods with lexical and external reference baselines.

3 Methodology

  • Each backend implements remember() and query(); graph configurations share extracted notes, a 5W ontology, and a base tag-topic-file graph.Localized configurations traverse the graph, while AdaptiveGraph adds chronological file edges and Personalized PageRank.Source: §3 · p. 3

3.1 Memory ingestion and extraction

  • Each interaction is stored as a Markdown document preserving the original dialogue, while extraction creates structured Who, What, When, Where, Why, Extra, and Summary fields.Extraction favors precision, avoids unsupported inferences, and treats user statements as the primary memory source.Source: §3.1 · p. 3

3.2 Graph construction

  • Hierarchical ontology tags represent extracted concepts as separate paths, while the full Markdown interaction remains the retrieved unit.Ontology prompting encourages reuse but does not enforce it or eliminate near-duplicate labels.Source: §3.1 · p. 3, §3.2 · p. 3
  • The graph links tags, topics, files, and ontology nodes through concept, memory, similarity, and parent-child edges.Similarity edges connect topics sharing at least three attributes across extracted 5W categories; AdaptiveGraph also links consecutive files chronologically.Source: §3.2 · pp. 3–4

3.3.1 OpenClaw

  • OpenClaw retrieves from raw conversation text with a dense-plus-BM25 pipeline and serves as an external production reference, not a controlled ablation.Its dense cosine similarity and BM25 weights are 0.7 and 0.3, respectively.Source: §3.3.1 · p. 4

3.3.2 BM25

  • The controlled BM25 baseline ranks the full text of the same extracted notes without using ontology or graph edges.Holding the memory store fixed tests whether graph structure improves on lexical ranking of identical retrieval units.Source: §3.3.2 · p. 4

3.3.3 TagGraph

  • TagGraph uses bounded breadth-first traversal over parent and child concepts, then scores candidate files by graph distance.Stopwords removes query tokens found in more than 15% of a case’s files, while TF-IDF weights rarer content terms; traversal and base graph remain unchanged.Source: §3.3.3 · p. 4

3.3.4 AdaptiveGraph

  • AdaptiveGraph adds chronological file edges and uses Personalized PageRank to propagate relevance through ontology, topic-file, similarity, and temporal connections.Matched ontology tags and TF-IDF file-overlap scores initialize the teleportation vector; final file rankings use PageRank probabilities, with direct file seeding preserving a lexical route.Source: §3.3.4 · pp. 4–5

4 Experimental setup

The evaluation uses LongMemEval-S and ATANT Core and Stress rounds, comparing retrieval methods over shared extracted memories alongside an external raw-input reference. It varies extraction models and evaluates ranking primarily with MRR.

4.1 Datasets

  • LongMemEval-S contains 500 questions over multi-session histories with roughly 40–50 past sessions per question, while ATANT covers persistent narratives across six life domains and separate stress rounds.LongMemEval also includes an oracle variant that supplies only gold sessions as a distractor-free upper-bound check.Source: §4.1 · p. 5

4.2 Compared retrieval methods

  • Six methods are compared, including four graph configurations sharing the same ingestion pipeline and base graph, BM25 over the same notes, and raw-input OpenClaw.OpenClaw lacks the shared 5W pipeline and graph, so it is treated as an external production reference rather than a controlled ablation.Source: §4.2 · p. 5

4.3 Memory extraction models

  • Graph-based retrieval is tested with Gemma, GPT-OSS, and Qwen3-Small extraction models while holding the prompt fixed.This design attributes graph-retrieval differences primarily to extraction model and retrieval configuration rather than prompt variation.Source: §4.3 · p. 5

4.4 Evaluation metrics

  • MRR is the primary retrieval metric; LongMemEval matches retrieved notes to gold sessions, while ATANT relevance requires all expected answer substrings.LongMemEval notes are mapped to source sessions and deduplicated through depth 40; ATANT uses case-insensitive substring matching because it lacks gold session labels.Source: §4.4 · p. 5

5 Results

Retrieval rankings differ across LongMemEval-S and ATANT: AdaptiveGraph leads graph configurations on LongMemEval-S, while localized traversal leads on ATANT Core. Vocabulary normalization and extraction quality also materially affect graph retrieval, and many top-five misses lack helpful tags.

5 Results

  • On LongMemEval-S, AdaptiveGraph reaches 0.844 MRR, below BM25’s 0.867 and OpenClaw’s 0.880; on ATANT Core, TagGraph-Stopwords leads while BM25 leads R2–R5.Within the shared extracted-note comparison, graph methods and BM25 use the same notes; OpenClaw indexes raw conversations.Source: §5 · p. 6

5.1 Effect of graph diffusion

  • Removing file seeding costs 0.119 MRR on LongMemEval-S, versus 0.020 for diffusion and 0.001 for chronological edges; removing diffusion raises ATANT Core MRR by 0.158.These leave-one-out effects are marginal and non-additive.Source: §5.1 · p. 6

5.2 Effect of vocabulary normalization

  • Stopword filtering improves LongMemEval-S MRR by 36.5–59.3% across extractors, and TF-IDF further raises MRR from 0.404–0.706 to 0.428–0.718.Common query terms can open broad ontology regions and introduce unrelated files.Source: §5.2 · p. 7

5.3 Performance across extraction models

  • With TagGraph-TFIDF on LongMemEval-S, Gemma reaches 0.718 MRR versus 0.428 for GPT-OSS, a 0.290 difference.The entire Basic-to-TFIDF progression under GPT-OSS adds 0.132; tag-vocabulary convergence is only a possible explanation, not an established cause.Source: §5.3 · p. 7
  • GPT-OSS is weakest on assistant-side questions, while Qwen3-Small is weakest on knowledge updates; assistant-side performance also reflects a restrictive ingestion rule.The shared prompt asks models not to extract facts found only in assistant responses.Source: §5.3 · p. 7

5.4 From ranking to answer accuracy

  • Containment accuracy rises from 14.6% for TagGraph-Stopwords to 18.7% for TagGraph-TFIDF and 25.3% for AdaptiveGraph, following the retrieval ordering.The check uses the same Qwen3-Small generator on 487 LongMemEval-S cases and a slightly different retrieval-scoring implementation.Source: §5.4 · p. 7

5.5 Failure case diagnostics

  • Among 658 gold notes missed by at least one graph configuration, 651 lack a helpful tag under at least one extractor, while seven have helpful tags under all extractors but configuration-dependent outcomes.This is a gold-note reachability audit, not a causal decomposition of all retrieval errors.Source: §5.5 · p. 7

6 Discussion

Retrieval rankings depend on the memory setting: AdaptiveGraph leads the graph methods on LongMemEval-S, while localized traversal leads on ATANT Core. The discussion qualifies these results with unresolved causes, extraction constraints, and limitations of the shared 5W representation.

6.1 When diffusion helps and when it hurts

  • No graph configuration wins across settings: AdaptiveGraph leads on LongMemEval-S, while localized traversal leads on ATANT Core.On LongMemEval-S, diffusion contributes 0.000 MRR without distractors and about +0.02 at higher densities; the benefit is non-negative but non-monotonic across the tested range.Source: §6.1 · p. 8
  • On ATANT Core, removing diffusion raises MRR by 0.158, while direct file seeding is the largest marginal contributor when both components are present.The proposed topic-dilution mechanism remains unmeasured; reducing LongMemEval-S to 24.3 notes per case does not reproduce the penalty, but does not reach ATANT Core’s 7.7 notes per story. The penalty persists under permissive any-substring matching, and its cause remains unidentified.Source: §6.1 · p. 8

6.2 Extraction constrains graph retrieval

  • Missing helpful tags remove localized graph paths, while AdaptiveGraph can still seed file nodes from TF-IDF overlap.The miss-set diagnostic cannot estimate extraction failure’s causal contribution; the extraction prompt prioritizes user statements, which can omit assistant-side evidence such as a needed restaurant recommendation. Suggested improvements include validation, selective preservation of assistant facts, and more consistent synonym and subtopic handling.Source: §6.2 · p. 8

6.3 Limitations and future work

  • The evaluation does not compare free-text summaries or relation triples, so the observed rankings may be specific to the shared 5W schema.The implementation also rebuilds each case graph rather than updating incrementally, and flat Markdown storage is not designed for deployment scale.Source: §6.3 · p. 9

A Example 5W Memory Note

  • Each conversation turn is stored as a Markdown note with an extracted-tag line and the raw exchange preserved verbatim for content scoring and auditability.The tag line links the note into the tag→topic→file graph used for retrieval.Source: A Example 5W Memory Note · pp. 11–12

B Extraction Prompt

  • All three extraction models receive the same prompt at temperature 0, enabling comparisons that trace performance differences to the extraction models rather than prompt engineering.The prompt prioritizes precision: extract only supported information, use user statements as the primary source, and omit uncertain tags.Source: B Extraction Prompt · p. 12

C Ontology Excerpt

  • The ontology is a growing indented Markdown hierarchy whose indentation encodes parent-child edges, and the prompt’s preference for existing tags is not enforced after generation.Source: C Ontology Excerpt · pp. 14–15

D Tag Vocabulary Convergence by Extraction Model

  • 376.5 distinct concepts per case for Gemma compares with 918.5 for GPT-OSS and 1,140.5 for Qwen3-Small; Gemma reuses each concept about twice as often.The one-corpus observation supports, but does not isolate, vocabulary convergence as the cause of retrieval differences.Source: Table 2 · p. 15, D Tag Vocabulary Convergence by… · p. 15

E Implementation Details

The implementation uses shared storage, ontology, graph construction, and evaluation code for the graph methods, alongside an external OpenClaw configuration. Retrieval depth is fixed at 40, with a limited sensitivity check on one LongMemEval-S configuration.

E Implementation Details

  • BM25 uses default rank-bm25 parameters over full note text, while OpenClaw combines dense and lexical rankings over raw stored chunks.OpenClaw’s combined score is 0.7 sdense + 0.3 sBM25; maximal marginal relevance and temporal decay are disabled in the benchmark configuration.Source: E Implementation Details · pp. 15–16
  • All graph methods share memory storage, ontology construction, graph construction, and evaluation code; AdaptiveGraph uses Personalized PageRank with α = 0.85 for 20 iterations.Source: E Implementation Details · p. 16
  • Retrieval depth is fixed at 40; on TagGraph-TFIDF over LongMemEval-S, MRR changes by less than 0.004 across depths 20, 40, and 80, with unchanged recall@5.The sensitivity sweep was not repeated for other methods or ATANT.Source: E Implementation Details · p. 16

F Component Ablation and Downstream Answer Accuracy

The appendix tests the ATANT diffusion penalty under a permissive match criterion, checks downstream answer accuracy, and documents controls for component and per-question-type comparisons.

F Component Ablation and Downstream Answer Accuracy

  • AdaptiveGraph without diffusion scores 0.705 on ATANT Core, while TagGraph-Stopwords scores 0.703, though their ranking algorithms remain distinct.The ablation holds the graph and initial query scores fixed; setting iterations to zero removes diffusion alone. Shared ATANT Core configurations agree within 0.007 MRR across implementations.Source: F Component Ablation and Downstream… · p. 16, Table 3 · p. 16

F.1 Strict and Permissive Content Match on ATANT

  • The ATANT Core diffusion penalty stays above +0.13 under permissive content match for all three extraction models, so strict matching does not account for it.The penalty shrinks by about a tenth under the permissive criterion.Source: §F.1 · p. 16, Table 4 · p. 16

F.2 Downstream Answer Accuracy

  • AdaptiveGraph reaches 0.773 MRR, versus 0.463 for TagGraph-TFIDF and 0.409 for TagGraph-Stopwords, in the downstream run.Token F1 and containment give the same ordering, but the scoring implementation differs from Table 1, so the result is treated as a directional check rather than an exact replication.Source: §F.2 · p. 17, Table 5 · p. 17

G Per-Question-Type Recall@1/3/5

  • The per-question-type recall breakdown includes OpenClaw retrieving over the same extracted notes, distinct from the native raw-input OpenClaw reference.The OC-notes comparison uses the same memory representation across columns.Source: G Per-Question-Type Recall@1/3/5 · p. 17

H ATANT Core Results by Category

On ATANT Core, AdaptiveGraph trails every localized variant across all six life domains, while the localized variants’ relative order varies by category.

H ATANT Core Results by Category

  • AdaptiveGraph trails every localized variant in all six ATANT Core domains; its largest gaps are Career (0.608 vs 0.844 for Stopwords) and Learning (0.540 vs 0.753 for Basic).The results use GPT-OSS extraction.Source: H ATANT Core Results by Category · p. 18
  • Localized variants’ internal order varies by category: Stopwords leads on Career and Health, while TF-IDF leads on Daily Life.The category-specific ordering matches the small overall spreads reported in Table 1.Source: H ATANT Core Results by Category · p. 18
  • The diffusion penalty is not driven by a single domain, because AdaptiveGraph trails localized methods in every category.Source: H ATANT Core Results by Category · p. 18

I ATANT Stress-Round MRR

The ATANT split comparison shows a Core disadvantage for AdaptiveGraph that closes by R5; the accompanying table reports store size and diffusion-penalty statistics by split.

I ATANT Stress-Round MRR

J Failure Category Examples

The failure diagnostics distinguish missing helpful tags from retrieval misses and illustrate several categories in the pooled failure subset.

J Failure Category Examples

Related papers

Loading 2609.38353v2…