PaperlayerView exact revision on arXiv

Source-linked AI summary

From Isolated Conversations to Hierarchical Schemas: Dynamic Tree Memory Representation for LLMs

Alireza Rezazadeh, Zichao Li, Wei Wei, Yujia Bao

arXiv:2410.14052v3cs.CLcs.AIcs.LG

TL;DR

LLMs still struggle with long-term memory, and flat lookup memories can leave related information disconnected. MemTree organizes memory in a dynamically updated tree, and evaluations report gains across extended conversations and document question-answering tasks.

  • Problem

    LLMs continue to struggle with long-term memory, while flat lookup memories leave experiences isolated and are limited when relevant information is spread across instances.

    Source: §1 · pp. 1–2

  • Method

    MemTree stores memory in a dynamically updated tree, routing information by semantic similarity and aggregating knowledge at parent nodes for retrieval.

    Source: §1 · p. 2

  • Results

    MemTree outperforms online methods in extended conversations, approaches offline systems on multi-document QA, and exceeds them on complex temporal queries.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Across four benchmarks, MemTree maintains high performance and captures context semantics through hierarchical memory aggregation.

    Source: §6 · p. 10

    The authors were unable to reproduce results using the existing MemGPT GitHub codebase.

    Source: §5.3 · p. 8

Abstract

from arXiv · show

Recent advancements in large language models have significantly improved their context windows, yet challenges in effective long-term memory management remain. We introduce MemTree, an algorithm that leverages a dynamic, tree-structured memory representation to optimize the organization, retrieval, and integration of information, akin to human cognitive schemas. MemTree organizes memory hierarchically, with each node encapsulating aggregated textual content, corresponding semantic embeddings, and varying abstraction levels across the tree's depths. Our algorithm dynamically adapts this memory structure by computing and comparing semantic embeddings of new and existing information to enrich the model's context-awareness. This approach allows MemTree to handle complex reasoning and extended interactions more effectively than traditional memory augmentation methods, which often rely on flat lookup tables. Evaluations on benchmarks for multi-turn dialogue understanding and document question answering show that MemTree significantly enhances performance in scenarios that demand structured memory management.

1 INTRODUCTION

MemTree addresses the limits of flat memory representations with a dynamically updated tree that aggregates information hierarchically. Across dialogue and document QA, it outperforms online methods and approaches or exceeds offline methods on several document tasks.

1 INTRODUCTION

  • LLMs continue to struggle with long-term memory despite expanded context windows, while flat lookup memories leave experiences isolated and struggle when relevant information spans multiple instances.The paper attributes the LLM challenge to reliance on KV caches processed through a fixed number of transformer layers.Source: §1 · pp. 1–2
  • MemTree updates its tree from the root, routing new information by semantic similarity, aggregating knowledge at parent nodes, and retrieving through cosine similarity over node embeddings.The stated insertion complexity is O(log N), with retrieval time comparable to existing approaches.Source: §1 · p. 2
  • The evaluation covers four benchmarks across conversational and document question-answering tasks, comparing MemTree with online and offline knowledge representation methods.Online methods can update as data arrives, whereas offline methods require complete dataset access and periodic rebuilding.Source: §1 · p. 2
  • Across extended conversations and document QA, MemTree outperforms online methods, approaches offline performance on multi-document tasks, and exceeds offline methods on complex temporal queries.The paper also reports high accuracy across diverse tasks while retaining the efficiency of online systems.Source: §1 · p. 2

2 RELATED WORK

Prior work includes flat memory stores, triplet or graph structures, and static tree-based retrieval systems. MemTree is presented as a structured memory approach designed for dynamic updates without full reconstruction.

2 RELATED WORK

  • Memory-augmented LLMs commonly use tabular storage and vector-similarity retrieval, but unstructured entries become limiting as memories grow or information is dispersed.Examples include timestamped experience logs, memory selectors, function-calling memory management, and timestamped dialogue stores.Source: §2 · p. 3
  • Triplet and graph-based triplet memories encode relations but can struggle to scale or generalize beyond data that fits strict triplet formats.The passage describes them as effective for individual relations or object-level scene graphs.Source: §2 · p. 3
  • RAPTOR and GraphRAG structure text for retrieval, but their static-corpus designs require full reconstruction to integrate new information and do not support online updates.RAPTOR uses recursive clustering and summaries; GraphRAG builds and summarizes graph communities.Source: §2 · p. 3
  • MemTree is proposed to enable dynamic updates and efficient retrieval in large-scale memory systems without full reconstruction.Source: §2 · p. 3

3 METHOD

MemTree represents memory as a tree whose nodes hold content and embeddings, with parent-child links organizing information hierarchically. Its update procedure routes new information by depth-adaptive semantic similarity and updates ancestor summaries; retrieval compares a query with all nodes.

3 METHOD

  • The memory tree uses nodes with aggregated text, embeddings, parent and child links, and depth; the root is a structural node without content or an embedding.The tree biases representation toward hierarchy and supports efficient insertion and traversal for online use, though it is less flexible than a generic graph.Source: §3 · pp. 3–4

3.1 MEMORY UPDATE

  • New information is embedded and compared by cosine similarity with the current node’s children, then follows the most similar qualifying child or becomes a new leaf.If traversal reaches a leaf, that leaf is expanded to parent the original content and new information.Source: §3.1 · p. 4
  • The similarity threshold increases with depth, requiring stronger matches at more specific nodes to preserve the tree’s hierarchical organization.The base threshold and the rate of increase are controlled by θ0 and λ.Source: §3.1 · p. 4
  • After insertion, ancestor nodes along the traversal path update their content and embeddings to reflect the new information.The LLM-based aggregation abstracts content further as descendant count increases, and parent updates can be parallelized on the CPU once the traversal path is set.Source: §3.1 · pp. 4–5
  • MemTree’s update procedure is framed as online hierarchical clustering using semantic similarities between subtree representations, with its stated approximation guarantee conditional on β-well-separated data.Source: §3.1 · p. 5

3.2 MEMORY RETRIEVAL

  • Collapsed-tree retrieval embeds the query, compares it with every node, filters below-threshold matches, and selects the top-k remaining nodes.Treating all nodes as one set avoids sequential, layer-by-layer traversal.Source: §3.2 · p. 5

4 EXPERIMENTS

The experiments test MemTree on dialogue and document question-answering tasks using four datasets, with baselines spanning online and offline memory methods. The evaluation standardizes language and embedding models across methods and scores generated answers with GPT-4o accuracy or ROUGE-L recall.

4.1 DATASETS

  • Four datasets cover short and extended dialogue, single-document QA, and multi-document questions requiring inference, comparison, or temporal reasoning.MSC uses 500 sessions of about 15 rounds; MSC-E adds 70 sessions of about 200 rounds, QuALITY passages average 5,000 tokens, and MultiHop RAG contains 609 articles and 2,556 questions.Source: §4.1 · pp. 5–6

4.2 BASELINES

  • Baselines include naive full-history prompting, online MemoryStream and MemGPT, and offline RAPTOR and GraphRAG.MemoryStream and MemGPT use flat memory representations, whereas RAPTOR and GraphRAG build structured indexes from a fixed corpus.Source: §4.2 · p. 6

4.3 IMPLEMENTATION DETAILS AND EVALUATION METRICS

  • All baselines use the same language and embedding models, and generated answers are evaluated with GPT-4o binary accuracy or ROUGE-L recall.The end-to-end procedure loads dialogue or history into memory, retrieves information for a query, and uses GPT-4o to answer.Source: §4.2 · p. 7, §4.3 · p. 7

5 RESULTS

Across extended dialogue and document question answering, MemTree outperforms online comparators, approaches offline methods, and excels on temporal reasoning. The results also describe its learned hierarchy and the update-time trade-off of maintaining memory online.

5.1 MULTI-SESSION CHAT

  • On 200-round MSC-E, MemTree consistently outperforms MemoryStream across evidence positions, while both memory systems beat the full-history baseline.The authors note a recency bias in MemTree; accuracy increases from 82.1 to 84.2 across the reported evidence positions.Source: §5.1 · p. 8

5.2 SINGLE-DOCUMENT QUESTION ANSWERING

  • On QuALITY, MemTree reaches 59.8% accuracy, matching RAPTOR’s 59.0% closely and outperforming online methods, especially on hard questions.Llama-3.1 70B using the full text achieves the highest overall accuracy at 65.1%.Source: §5.2 · p. 8, Table 3 · p. 8

5 RESULTS

  • Across extended dialogue and document QA, MemTree beats online comparators, approaches offline systems, and leads on temporal reasoning.On MultiHop RAG, it also outperforms all baselines on temporal reasoning, including offline approaches and human-annotated evidence.Source: §5.3 · pp. 8–9, §5.1 · p. 8, §5.2 · p. 8

5.3 MULTI-DOCUMENT QUESTION ANSWERING

  • On complex MultiHop RAG questions, MemTree leads MemoryStream by 9.1 percentage points and finishes within 0.5 points of offline RAPTOR overall.Inference-style questions exceed 95% accuracy for all methods; MemTree surpasses baselines, including human-annotated evidence, on temporal reasoning.Source: §5.3 · pp. 8–9, Table 4 · p. 9
  • The learned tree for 609 MultiHop documents has 3,154 nodes, reaches depth 13, and has an average branching factor of 2.1.Most nodes lie at depths 3–5; median node length grows from slightly over 200 tokens at depth 1 to around 800 at depth 10 and beyond.Source: §5.3 · p. 9, Figure 4 · p. 10, Table 5 · p. 10
  • Higher-level nodes hold abstract summaries, while deeper nodes store increasingly specific details, with parent summaries generated during insertion.The illustrated branch moves from a general summary of the USMNT’s defeat to team and player details, ending with Gio Reyna’s impact.Source: Figure 3 · p. 9, §5.3 · p. 10
  • MemTree inserts new information in 10 seconds on average, while RAPTOR and GraphRAG take over an hour to build the full memory tree.Continuous updates make MemTree suitable for real-time use, though its cumulative time cost is 1.4x RAPTOR’s.Source: §5.3 · p. 10, Figure 5 · p. 10

6 CONCLUSION

MemTree uses a dynamic tree-based memory representation to integrate and retrieve historical information, and the paper reports strong performance across four benchmarks. The appendix details how it inserts and aggregates information, adjusts similarity thresholds by depth, and configures retrieval.

6 CONCLUSION

  • MemTree achieves superior performance on four benchmarks with different interactive contexts, while capturing context semantics in its tree memory.The conclusion describes this as a way to address LLM long-term memory limitations.Source: §6 · p. 10

A.1.1 MEMTREE ALGORITHM

  • New information is embedded and inserted from the root; child similarity and a depth-dependent threshold determine whether to aggregate along a branch or create a new child.The algorithm expands a leaf into a parent before attaching children when needed.Source: §A.1.1 · p. 14

A.1.2 AGGREGATE OPERATION

  • Along the insertion path, parent content is conditionally updated by merging existing content with new information, with the number of descendants factored in.The aggregation prompt makes summaries more abstract as previous entries accumulate beyond two.Source: §A.1.2 · pp. 14–15

A.1.3 ADAPTIVE SIMILARITY THRESHOLD

  • The adaptive threshold requires higher similarity at deeper, more specific nodes while allowing broader content at shallower nodes.The stated purpose is to preserve the tree’s hierarchical integrity as selectivity varies with depth.Source: §A.1.3 · p. 15

A.1.4 RETRIEVAL

  • For MSC retrieval, the system returns top k = 3 dialogues with 1,000-token context; MSC-E uses top k = 10 and 8,192-token context, as do MultiHop RAG and QuALITY.Source: §A.1.4 · p. 15

A.2.1 DATASET STATISTICS

The appendix describes experiments spanning multi-turn dialogue, document comprehension, and multi-document question answering. Dataset setup varies by task, including the unit inserted into memory and whether documents are chunked.

A.2.1 DATASET STATISTICS

  • The experiments cover 500 MSC sessions of about 14 rounds, 70 extended MSC-E sessions exceeding 200 rounds, around 230 QuALITY documents, and 609 MultiHop RAG articles with over 2,500 questions.Table A.1 is identified as the summary of dataset statistics.Source: §A.2.1 · p. 15, Table A.1 · p. 16
  • MSC and MSC-E insert each dialogue round without chunking and build an independent MemTree for each conversation.Source: §A.2.1 · p. 16
  • QuALITY documents are inserted individually in non-overlapping 512-token segments, while MultiHop RAG documents use non-overlapping 1,024-token segments.Source: §A.2.1 · p. 16

A.2.2 EVALUATION METRICS

The appendix describes binary-accuracy evaluation across dialogue and document question-answering settings, including generated long conversations and questions. It also reports MemTree’s insertion-call efficiency and outlines comparisons across evidence positions, question difficulty, and query types.

A.2.2 EVALUATION METRICS

  • The evaluation generates an answer from retrieved content, then uses binary accuracy: a model judges whether it addresses the query similarly to the ground truth and outputs 1 or 0.Source: §A.2.2 · p. 16

A.2.3 MSC-E DATA GENERATION

  • MSC-E conversations are extended to 200 rounds using a sliding window of the most recent eight turns to generate the next two dialogue rounds.The generation prompt requires alternating Alex and Bob turns and aims for logical, organic continuity.Source: §A.2.3 · p. 17

A.2.4 MSC-E QUERY GENERATION

  • MSC-E query generation asks for unique questions answerable from Alex’s shared information, paired with responses grounded in the conversation.Source: §A.2.4 · p. 18

A.3.1 ACCURACY VS POSITION OF EVIDENCE (MSC-E)

  • The MSC-E analysis examines accuracy by the position of supporting evidence in extended dialogue.The passage characterizes this as testing retrieval and use of information from different points in conversations.Source: §A.3.1 · p. 18

A.3.2 PERFORMANCE VS QUESTION DIFFICULTY (QUALITY)

  • On QuALITY, the comparison tests single-pass Llama-3.1 70B against retrieval methods across question difficulty, including online and offline memory approaches.RAPTOR and GraphRAG are identified as offline methods that must be rebuilt to incorporate new information.Source: §A.3.2 · p. 18

A.3.3 PERFORMANCE VS QUERY TYPE (MULTIHOP RAG)

  • MultiHop RAG results are organized by inference, comparison, and temporal query types, with online and offline methods compared.Offline methods require rebuilding from scratch to incorporate new information and do not support real-time memory updates like MemTree.Source: §A.3.3 · pp. 18–19

A.3.4 LLM CALL EFFICIENCY COMPARISON

  • Adding one observation requires about 3,750 LLM calls for RAPTOR and 3,850 for GraphRAG, while online methods support incremental updates.The passage characterizes rebuilding static offline representations as computationally expensive and time-consuming.Source: §A.3.4 · p. 19
  • MemTree averages 3.27 LLM calls per insertion on MultiHop RAG, and its node updates can run concurrently after the insertion path is detected.Table A.2 covers overall accuracy and average LLM calls per insertion.Source: §A.3.4 · p. 19, Table A.2 · p. 20

A.3.5 ABLATION: COLLAPSED RETRIEVAL VS. TRAVERSAL RETRIEVAL

The ablation compares collapsed retrieval, which evaluates all nodes, with traversal retrieval, which searches recursively through selected top-k nodes. Traversal retrieval’s accuracy depends on k and trades search coverage against path-focused retrieval.

A.3.5 ABLATION: COLLAPSED RETRIEVAL VS. TRAVERSAL RETRIEVAL

  • Collapsed retrieval compares the query against all nodes, whereas traversal recursively selects top-k nodes at each level by cosine similarity.Source: §A.3.5 · p. 20
  • At k = 10, traversal retrieval achieves accuracy comparable to collapsed retrieval, while k ≤ 5 significantly compromises MultiHop RAG accuracy, especially for temporal queries.Figure A.4 presents the accuracy comparison between the two strategies.Source: §A.3.5 · p. 20, Figure A.4 · p. 20
  • Traversal can repeat parent information and exhaust context before reaching deeper details, making fine-grained reasoning vulnerable to missed information.Source: §A.3.5 · p. 21

A.3.6 ABLATION: ROBUSTNESS OF MEMTREE UNDER VARIOUS LLM AND EMBEDDING MODELS

MemTree retains comparable tree structure and accuracy when constructed with smaller language and embedding models. Its nodes remain concentrated at intermediate depths, with deeper nodes storing more abstract information.

A.3.6 ABLATION: ROBUSTNESS OF MEMTREE UNDER VARIOUS LLM AND EMBEDDING MODELS

  • Smaller LLMs and embeddings produce trees with node counts, branching factors, and average depths comparable to larger-model trees.The reported comparison uses GPT-4o-mini, Llama-3.1-8B-Instruct, and text-embedding-3-small.Source: §A.3.6 · p. 21
  • Across models, most nodes fall at depths 3–5, while deeper nodes store longer content representing more abstract themes.Figure A.5 illustrates the depth distribution and increase in information length.Source: §A.3.6 · p. 21, Figure A.5 · p. 21
  • Accuracy with trees built using smaller LLMs and embeddings is comparable to that achieved with larger models.The comparison is on the Multihop RAG dataset.Source: §A.3.6 · p. 21

A.3.7 ABLATION: ADAPTIVE THRESHOLD PARAMETERS

MemTree raises its similarity threshold with tree depth, imposing stricter integration criteria deeper in the hierarchy. Changing the base threshold substantially alters tree depth, while tested parameter choices leave MultiHop RAG accuracy statistically similar.

A.3.7 ABLATION: ADAPTIVE THRESHOLD PARAMETERS

  • The threshold θ(d) = θ0e^λd increases with depth, requiring higher similarity to integrate information into more specific, deeper nodes.Experiments use θ0 = 0.4 and λ = 0.5.Source: §A.3.7 · p. 21
  • Lowering θ0 shifts most nodes deeper: from depths 1–2 at θ0 = 0.8, to 4–6 at 0.4, and 8–14 at 0.1.Varying λ has a less pronounced structural effect; at θ0 = 0.8, increasing λ from 0.25 to 0.75 reduces maximum depth from 15 to 11.Source: §A.3.7 · p. 22, Figure A.6 · p. 22
  • MultiHop RAG accuracy differences across tested adaptive-threshold settings are not statistically significant.A slight improvement appears at θ0 = 0.1 and λ = 0.25.Source: §A.3.7 · p. 22, Figure A.7 · p. 23

A.3.8 HUMAN EVALUATION OF MEMTREE’S STRUCTURE

The appendix examines human alignment, prompt compression, and MemTree’s theoretical connection to online hierarchical clustering. It reports alignment between the tree and human judgments, a compression trade-off, and an approximation guarantee under a data-separation assumption.

A.3.8 HUMAN EVALUATION OF MEMTREE’S STRUCTURE

  • Human judgments align with MemTree’s hierarchy: easy-question alignment averages 97.9% at depths 2–5 and reaches 100% at depths 6–13; hard-question alignment is 86.2% and over 89%, respectively.The reported alignment increases for alternatives sampled from deeper tree levels.Source: §A.3.8 · p. 24, Figure A.8 · p. 24

A.3.9 PROMPT COMPRESSION

  • Across compression rates, MemTree outperforms MemoryStream on Multihop RAG and MSC-E, although accuracy declines as compression becomes more aggressive.Accuracy drops significantly below compression rates of 0.3 for Multihop RAG and 0.7 for MSC-E; Figure A.9 compares the methods.Source: §A.3.9 · p. 25, Figure A.9 · p. 25

B THEORETICAL JUSTIFICATION OF MEMTREE VIA ONLINE HIERARCHICAL CLUSTERING

  • The appendix motivates MemTree’s theoretical justification by connecting its online hierarchical memory organization to the Online Top-Down clustering algorithm.The authors state that this connection is intended to transfer OTD’s theoretical properties to MemTree.Source: B THEORETICAL JUSTIFICATION OF MEMTREE… · p. 26

B.1 MEMTREE’S APPROXIMATION TO THE MOSELEY-WANG REVENUE

  • Under the β-well-separated data assumption, MemTree’s hierarchy achieves a β/3-approximation to optimal Moseley-Wang revenue.The guarantee is presented as an informal theorem.Source: §B.1 · p. 26, §3 · p. 26

B.2 BACKGROUND: ONLINE HIERARCHICAL CLUSTERING AND MOSELEY-WANG REVENUE

  • The Moseley-Wang revenue evaluates hierarchy quality by rewarding similar points grouped lower in the tree, and OTD incrementally updates hierarchies using similarity comparisons.The cited OTD guarantee also requires a data-separation assumption.Source: §B.2 · pp. 26–27

B.3 ALIGNMENT OF MEMTREE WITH THE OTD ALGORITHM

  • MemTree parallels OTD’s top-down traversal and similarity-based insertion decisions, while aggregating content and embeddings along the insertion path.The paper interprets parent aggregation as maintaining or enhancing intra-cluster similarity, and uses this alignment to motivate inherited theoretical guarantees.Source: §B.3 · p. 27

B.4 DATA SEPARATION ASSUMPTION AND DEPTH-ADAPTIVE THRESHOLD

The appendix relates MemTree’s depth-adaptive threshold to a data-separation condition and illustrates how hierarchical retrieval varies with query specificity. It also identifies failure cases involving buried or insufficient evidence.

B.4 DATA SEPARATION ASSUMPTION AND DEPTH-ADAPTIVE THRESHOLD

  • The β-well-separated assumption constrains similarities between a new point, a parent cluster, and its child clusters; the authors use it to justify MemTree’s clustering guarantee.The threshold θ(d) = θ0e^λd increases with depth to enforce stricter similarity requirements in deeper clusters.Source: §B.4 · pp. 27–28
  • Increasing λ yields a smaller β and stronger separation at deeper levels, while an unsuitable θ0 may violate the separation assumption and affect the approximation guarantee.θ0 sets the root-level similarity threshold.Source: §B.4 · p. 28

C.1 RETRIEVAL FROM TWO SUBTREES

  • For the same query, related retrieved content is consistently associated with the same subtree, and the examples include queries spanning distinct subtrees.The appendix describes retrieved content using its node depth and top three ancestor nodes.Source: C QUALITATIVE EXAMPLES · p. 29, §C.1 · p. 29

C.1.1 RETRIEVAL FROM SHALLOW NODES AND DEEPER NODES

C.2 FAILURE EXAMPLES

  • The failure examples show two limits: necessary evidence may be buried in lengthy, complex retrieved text, or the retrieved content may be insufficient to answer.These are presented as qualitative failure cases.Source: §C.2 · p. 29, Table A.8 · p. 33, Table A.9 · p. 34

Related papers

Loading 2410.14052v3…