From Isolated Conversations to Hierarchical Schemas: Dynamic Tree Memory Representation for LLMs
Authors: Alireza Rezazadeh
Zichao Li
Wei Wei
Yujia Bao
Venue: ICLR 2025 Poster (2025)
Keywords: Tree-based Memory
Inference-time Reasoning
Large language models
Long-term memory
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: MemTree is a dynamic algorithm that organizes memory hierarchically, using tree-structured representations with different levels of abstraction to enhance information retrieval and context-awareness in large language models.

Abstract: 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.

Published as a conference paper at ICLR 2025
FROM ISOLATED CONVERSATIONS TO HIERARCHICAL SCHEMAS: DYNAMIC TREE MEMORY REPRESENTA- TION FOR LLMS
Alireza Rezazadeh, Zichao Li, Wei Wei, Yujia Bao
Center for Advanced AI, Accenture (alireza. rezazadhh, zichao. 1i, wei h. yujia.baabba bao waceentuuee..... com
ABSTRACT
Recent advancements in large language models have significantly improved their context windows, yet challenges effective long-tew ong-term memory management remain. We introduce MemTTee, an algorithm that leverages dynamic, tree- structured memory representation to optimize the organization, retrieval, and in- tegration of information, akin to human cognitive schemas. Mem'Tree 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 com- puting and comparing semantic embeddings of new and existing information enrich the model's '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. Evalua- tions on benchmarks for multi-tur dialogue understanding and document question answering show that Mem Tree significantly enhances performance in scenarios that demand structured memory management.
Figure 1: MemTTree (subset) developed on the MultiHop dataset (Tang & Yang 2024). MemTree
updates its structured knowledge when new information arrives, enhancing inference-timg time reasoning capabilities of LLMs.
INTRODUCTION
Despite recent advances large language models (LLMs) where the context window has expanded
to millions of tokens (Ding et al. 2024 Bulatov et al. 2023 Beltagy et al., 2020 Chen et al. 2023 Tworkowski et al.) 2024), these models continue to struggle with reasoning over long-term
memory (Sun et al.) 2021 Liu et al. 2024 Kuratov et al. 2024). This challenge arises because LLMs rely primarily on a key-value (KV) cache of past interactions, processed through a fixed number of transformer layers, which lack the capacity to effectively aggregate extensive historical data. Unlike ILMss, the human brain employs dynamic memory structures known as schemas, which facilitate the efficient organization, retrieval, and integration of information new experiences occur (Anderson 2005 Ghosh & Gilboa| 2014: Gilboa & Marlatte (017). This dynamic restructuring of memory is cornerstone of human cognition, allowing for the flexible application of accumulated knowledge across varied contexts.
A prevalent method to address the limitations of long-term memory in LLMs involves the of external memory. Weston et al.] (2014) introduced the concept of utilizing external memory for the storage and retrieval of relevant information. More recent approaches in LLM research have

---

Published as a conference paper at ICLR 2025
Attdes
MenTrw
NowAAttide
M Mumeree
New Atticl
Mom
Auais
Secala
Dceatd Searp
Apple
Soneldd
Convasstion
New Con
Memeree
Phat your fereedite diat3
Hoat! quita exciscen)
cecectiy roned Sooe
Wbere Hive))
Looe in FemssLaoo!
Roved Seactlie
Figure 2: Illustration of MemTree MemTree represents knowledge schema via dynamic tree. Both parent and leaf nodes archive textual content, summarizing information relevant their respective levels. Upon receiving new information, the system begins traversal from the root node. If the new information is semantically akin to an existing leaf node under the current node, is routed to that node. Conversely, if it diverges from all existing leaf nodes under the current node, new leaf node is created under the current node, concluding the traversal. During this process, all ancestor nodes will integrate the new information into the higher-level summaries they maintain.
explored various techniques to manage historical observations in databases, retrieving pertinent data for given queries through vector similarity searches in the embedding space (Park al. [0233 Packer et al. 2023 Zhong et al. 2024). However, these methods primarily utilize lookup table for memory representation, which fails to capture the inherent structure in data. Consequently, each past experience is stored as an isolated instance, lacking the interconnectedness and integrative capabilities of the human brain's schemas. This limitation becomes increasingly problematic as the size of the memory grows or when relevant information is distributed across multiple instances.
In this work, we introduce MemTree, an algorithm designed to emulate the schema-like structures of the human brain by maintaining dynamically structured memory representation during interactions. Within MemTree, each memory unit is represented as a node within a tree, containing node-level information and links to child nodes.
Upon encountering new information, MemTrre updates its memory structure starting from the root node. It evaluates at each node whether to instantiate new child node or integrate the information into an existing child node. This decision process is governed by a traversal algorithm that efficiently adds new information with insertion complexity of O(log N), where N denotes the number of conversational interactions. This structure facilitates the aggregation of knowledge at parent nodes, which evolve to capture high-level semanties the tree expands. For knowledge retrieval, MemTrey computes the cosine similarity between node embeddings and the query embedding. This method maintains the retrieval time complexity comparable existing approaches, ensuring efficiency.
We evaluated MemTree across four benchmarks, covering both conversational and document question- answering tasks, and compared against online and offline knowledge representation methods. Mem Tree enables seamless dynamic updates as new data becomes available, a capability characteristic of online methods. In contrast, offline methods require complete dataset access and are costly to update, as they involve periodic rebuilding to incorporate new information.
In extended conversations, MemTree consistently outperforms other online methods, including MemoryStream (Park et al. 2023) and MemGPT (Packer et al., 2023), maintaining superior accuracy as discussions progress.
MemTreee excels in two key areas. On single-document tasks, it outperforms other online methods and reduces the performance gap with offline models, particularly surpassing RAPTOR (Sarthi et al., 2024) on challenging questions that require deeper reasoning. In multi-document tasks, MemTree not only surpasses online methods but also approaches the performance offline models, particularly outperforming GraphRAG (Edge et al. 2024). Moreover, on complex temporal queries requiring the analysis of event sequences across multiple documents, MemTree exceeds all offline methods.
For document presstion-nsswerii
These results demonstrate that MemTree is a robust and scalable solution, delivering high accuracy across diverse and challenging tasks while retaining the efficiency of online systems.
2

---

Published as a conference paper at ICLR 2025
2
RELATED WORK
Memory-Augmented LLMs Recent advancements in memory-augmentedd LLMs have introduced various strategies for enhancing memory capabilities. Park et al. (2023) developed LLM-basse agents that log experiences as timestamped descriptions, retrieving memories based on recency, importance, and relevance. Similarly, Cheng et al. (2023) developed Selfinem with a dedicated
memory selector. MemGPT (Packer et al. [023] proposed automatic memory management through LLM function-calling for conversational agents and document analysis, providing a pre-prompt with detailed instructions memory hierarchy and utilities, along with schema for accessing and modifying the memory database. ZZhong et al. (2024) introduced MemoryBank, a long-teni memory framework that stores timestamped dialogues and uses exponential decay to forget outdated information. Additionally, Mitchell et al. (2022) proposed storing model edits in an explicit memory and learning to reason them adjust the base model's s predictions. These methods represent common solutions for adding memory to LLMs, focusing on tabular memory storage and vector similarity retrieval (Zhang et al. 2024). However, memory scales information becomes dispersed across multiple entries, their unstructured representations reveal significant limitations.
Another line of work explores triplet-based memory. For example, MMdarressi al. (2023) proposed encoding relationships in triplets, and Anokhin et al. (2024) extended this approach to graph-based triplet memory for text-based games. While effective at encoding individual relations or scene graphs at the object level, these methods struggle with scalability and generalization to more complex data that do not fit neatly into a strict triplet format.
Structured Retrieval- Augmentee Generation Approaches To address the limitations of unstruc- tured memory representations, recent advances have integrated structured knowledge into RAG models, enhancing navigation and summarization in complex QA tasks. Trajanoska al. (2023) leveraged LLMs to extract entities and relationships from unstructured text to construct knowledge graphs. Similarly, Yao et al. (202)) proposed techniques to fill in missing links and nodes in existing knowledge graphs by utilizing LLMs to infer unseen relationships. |Ban et al. (2023) identified causal relationships within textual data and represented them in graph form enhance understanding of
causal structures. In the context of retrieval -augeette generation, Gao et al. (2023) provided
comprehensive review of existing RAG methods, and Baek et al. (2023) utilized knowledge graphs as indexes within RAG frameworks for efficient retrieval of structured information.
More relevant to our work, RAPTOR (Sarthi et al. 2024) organizes text into a recursive tree, clustering and summarizing chunks at multiple layers enable efficient retrieval of both high-level themes and detailed information. GraphRAG (Edge et al. 2024) constructs a knowledge graph from LLM-extracted entities and relations, partitioning into modular communities that are independently summarized and combined via map-reduce framework. While these methods effectively structure large textual data to improve retrieval and generation capabilities, they limited static corpora, requiring full reconstruction to integrate new information, and do not support online memory updates.
In this work, we propose novel structured memory representation that overcomes these limitations by enabling dynamic updates and efficient retrieval in large-scale memory systems without necessitating full reconstruction.
METHOD
Mem'rree represents memory as tree 7= (V, F), where V the set of nodes, and F. C x V the set of directed edges representing parent-child relationships. Each node E V is represented as:
v = Lc., Ev Po. Coy del
where:
c,t the textual content aggregated at node v.
G, E IRdd an embedding vector derived using an embedding model (emb((..).
Py E V: the parent of node v.
C, C V: the set of children of node v, with edges directed from each u. E C..
3

---

Published as a conference paper at ICLR 2025
de: the depth of node e from the root node Vg.
Note that the root node to serves as structural node, containing neither content nor embedding, i.e., Cup 2 and Cvp Ø.
MemTree utilizes this tree-structured representation to dynamically track and update the knowledge exchanged between the user and the LLM. While less flexible than generie graph architecture, the tree structure inherently biases the model towards hierarchical representation. Additionally, trees offer efficient complexity for insertion and traversal, making the algorithm suitable for real-time online use cases.
When new information observed, MemTree dynamically adapts by traversing the existing structure, identifying the appropriate subtree for integration, and updating relevant nodes (Section (.T). This process, illustrated in Figure ensures the proper integration of new information while preserving the underlying context and hierarchical relationships within the memory. When retrieving information from the memory, Mem simply compares the embeddings of the query message with the embeddings of each node in the tree, returning the most relevant nodes (Section 3.2)
3.1 MEMORY UPDATE
The memory update procedure in MemTree is triggered upon observing new information (e.g., new conversation). This procedure ensures that the tree structure dynamically adapts and integrates new data while maintaining a coherent hierarchical representation. The complete memory update process outlined in Algorithm
Attaching New Information by Traversing the Existing Tree To integrate information, begin by creating a new node Unew with the textual content Cown Then we start tree traversal from the root node. At each node v, MemTree evaluates the semantic similarity between the new information Crnew and the children of the current node in the embedding space. This evaluation is performed by computing the embedding Erge femb (Crsew ) for the new content Cuew and comparing it the embeddings of the child nodes C(v) of the current node using cosine similarity.
This similarity evaluation drives the following decisions:
If child node's similarity exceeds a depth depth-adaptive threshold (dd,). traversal continues along that path. If multiple child nodes meet this criterion, the path with the highest similarity is chosen.
Traverse Deeper:
Boundary: When traversal reaches a leaf node, the leaf is expanded to become parent node, accommodating both the original leaf node and Unew as children. The parent's 's content is then updated to aggregate both the original leaf node's content and the new information Cr The details of this aggregation process will explained below.
Create New Leaf Node: If all child nodes' similarities are below the threshold ((d.), Unew is directly attached as new leaf node under the current node.
The similarity threshold ((d) is adaptive based on the node's depth d, defined as:
((d) = Ad
where Og is the base threshold, and À controls the rate of increase with depth. This mechanism ensures that deeper nodes, which represent more specific information, require higher similarity for new data integration, thereby preserving the tree's 's hierarchical integrity. Further details, including specific parameter values, are provided in the Appendix A.1.3
Updating Parent Nodes Along the Traversal Path dings all parent nodes v along the traversal path are updated to reflect the new information. This is achieved through a conditional aggregation function:
Once Unew is inserted, the content and embed-
d, + Aggregate(Ce:: Cnew n).
where d, the updated content, and n = |C(u) is the number of descendants of node v. The aggregation function, implemented LLMM-based operation, combines the existing content G,
4

---

Published as a conference paper at ICLR 2025
with the content Cuews conditioned As n increases, the aggregation abstracts the content further to balance the existing and new information (see Appendix A..12 for more details).
The embedding of the parent node is then updated as:
Co f femb
ensuring that the parent node effectively represents both the new and existing information. This process maintains the hierarchical organization of the memory the expands, enabling MemTree to adaptively and accurately represent the evolving conversation. A key advantage of this method is its computational efficiency: once the traversal path is defined, the content aggregation and embedding updates for parent nodes can be parallelized on the CPU. This significantly accelerates the update process, reducing bottlenecks as the memory grows.
Connection to Online Hierarchical Clustering Algorithms Our memory update algorithm be viewed as an instance of online hierarchical clustering algorithms (Zhang et al.) 1996. Kobren et al.) 2017). We draw inspiration from the OTD (Online Top-Down Clustering) algorithm proposed by Menon et al. (2019). which enables efficient online updates by calculating inter- and intra-subtree similarities during the insertion process. This algorithm is known provably approximate the Moseley- Moseley-Wang revenue (Moseley & Wang 2017). In this work, we relax the inter- and intra-subtree similarity comparisons by utilizing semantic similarities in the embedding space. We achieve this by formatting the subtree representation (parent nodes) with LLMSs as traverse the Mem'Tree during the memory update.
Theorem (Approximation Guarantee of Tree (Informal)). Assuming the data processed by MemTree satisfies the 8-well-separated condition (see Appendix B.4). the hierarchy maintained by Mem'Tre achieves revenue
Rev Rev(Mem'Tree; W) 3/3 Rev(T";
where 7 is the optimal hierarchy maximizing the Moseley- Waagg revenue.
This alignment with OTD ensures a high-quality hierarchical memory representation in MemTree. Further details and proofs are provided in Appendix B
3.2 MEMORY RETRIEVAL
Efficient and effective retrieval of relevant information is crucial for ensuring that MemTree can provide meaningful responses based on past conversations. Inspired by RAPTOR (Sarthi et al. (2024) we adopt the collapsed tree retrieval method, which offers significant advantages over traditional tree raversal-based retrieval.
Collapsed Tree Retrieval The collapsed tree approach enhances the search process by treating all nodes in the tree as single set. Instead of conducting sequential, layer-by-laye traversal, this method flattens the hierarchical structure, allowing for simultaneous comparison of all nodes. This technique simplifies the retrieval process and ensures more efficient search.
The retrieval process involves the following steps:
Query Embedding: Embed the query q using femb(q) obtain Eg.
2. Similarity Computation: Calculate cosine similarities between eg and all tree nodes.
3. Filtering: Exclude nodes with similarity scores below threshold (
4. Top-K Selection: Sort the remaining nodes by similarity and select the top-k most relevant nodes.
4 EXPERIMENTS
4.1 DATASETS
We evaluate the effectiveness of Mem across various settings using four datasets: Multi-Session Chat, Multi-Session Chat Extended, QuALITY, MultiHop RAG. These datasets were selected to

---

Published as a conference paper at ICLR 2025
represent different interactive contexts dialogue interactions and information retrieval from multiple texts, respectively, providing a comprehensive test bed for our model. Additional statistics for each dataset can be found in Appendix A.2.1
Multi-Session Chat (MSC): The dataset was introduced by Xu b. In this work, we consider the processed version provided by (Packer et al. 2023). The dataset consists of 500 sessions, each featuring approximately 15 rounds of synthetic dialogue between two agents. Each session includes follow-up questions that challenge the model to retrieve and utilize information from prior dialogues within the same session. For each session, memory representation is independently built, capturing the dialogue rounds as they unfold.
Chat Extended (MSC-E): To test the performance for even longer conversation rounds, we expanded MSC by generating additional 70 sessions, each containing about 200 rounds of dialogue. In these extended sessions, a follow-up question follows each conversation round, demanding more precise and timely information retrieval across the dialogues. As in MSC, memory representations are constructed independently for each session. We detail the extension methodology in Appendix A.2.3 Single-Documen Question Answering (QuALITY): The QuALITY dataset, introduced by Pang et al. (2021), consists of context passages averaging 5,000 tokens, paired with multiple-choice questions that require reasoning across entire documents answer. A memory representation built independently for each document. The dataset is divided into two subsets: QuALITY- and QuALITY-Hard. The latter contains questions that most human annotators found challenging to answer within the time constraints. While the original dataset was designed for multiple-choice question answering. this paper we explore the more difficult setting where the model must generate the answer directly, without being provided with the four answer options.
Multi--esssonn
Multi molti-Document Question Answering (MultiHop RAG): This dataset comprises 609 distinct news articles across six categories (Tang & Yang. 2024). It includes 2,556 multi-hop questions requiring the integration of information from multiple articles to formulate comprchensive answers. We consider three question types: inference, comparison, and temporal reasoning, each adding a layer of complexity to the information retrieval process. All news articles used to construct unified memory representation, which is queried to answer the multi-hop questions.
4.2 BASELINES
We compare MemTree with various baseline methods along with naive baseline, which involves concatenating all chat histories and feeding them into large language model (LLM):
MemoryStream: Park et al. (2023) proposes a flat lookup-table style memory that logs chat histories through an embedding table. The primary distinction between MemTree and this baseline is that MemTree utilizes a structured tree representation for the memory and models high-level representations throughout the memory insertion process.
MemGPT: (Packer et al., 2023) introduces a memory system designed to update and retrieve information efficiently. It uses OS paging algorithm to evict less relevant memory into external storage. However, like KemoryyStream it does not format high-level representations! !
Sarthi et al. (2024) constructs a structured knowledge base using hierarchical clustering over all available information. The key difference between MemTree and this baseline is that Mem'Tre operates as an online algorithm. updating the tree memory representation on-the-fly based on incoming knowledge, while RAPTOR applies hierarchical clustering fixed dataset
RAPTOR:
GraphRAG: Edge et al. (2024) introduces graph-based indexing approach designed to improve summarization and extract global insights from large text corpora. Like RAPTOR, GraphRAG assumes access the entire corpus and applies the Leiden algorithm to identify community structures within the document graph. However, while Mem expands its memory top-down to allow for efficient, online updates, GraphRAG generates community summaries in bottom-up fashion, which is less suited for real-time adaptability
hateas//gtthbb.com/ccceee/////e

---

Published as a conference paper at ICLR 2025
Table 1: Naive History Combination External Memory on MSC. With only 15 dialogue rounds (<1,000 tokens), concatenating the entire history to GPT--4o achieves the best performance. Among query-only models, MemTree outperforms MemGPT and MemoryStream in accuracy and ROUGE.
Model
Context
Accuracy f ROUGE-L (R)
Results reported (Packer al. 2023
GPT-4 Turbo
Query + Full history summary
35
GPT-4 Turbo
Query Full history summary MemGPT
93
82
Our results with GPT-4o and text-embedding----eee
GPT-4o
Query Full history
95.6
88.0
GPT-4o
Query MemGPT
70.4
68.6
GPT-4o
Query MemoryStream
84.4
79.1
GPT-4o
Query Mem'Tree
84.8
79.9
Table 2: Accuracy MSC-E. The MSC-E dataset extends MSC from 15 200 dialogue rounds, providing a better test for long-context reasoning. Both MemoryStream and MemTree outperform the naive bascline, highlighting the importance of external memory. Overall accuracy and breakdown by evidence position are shown; standard deviations are in Figure A.
Position of the supporting evidence
Model
Context
Overall
0-40
40-80
80-120
120-160
160-200
GPT-4o
Query Full history
75.5
74.4
76.7
78.0
GPT-4o
Query + MemoryStream
78.5
81.0
81.0
81.4
81.8
80.7
GPT-4o
Query Mem'Tree
82.1
82.1
82.3
82.3
84.2
82.5
To demonstrate the applicability of our approach, consider both open-source and commercial models in our experiments. For LLMs, we used OpenAl's GPT-4o (version 2024-05-13) and (Dubey et al. 2024). For the embedding models, employed (Wang et al. 2023). In each experiment, we standardized the use of the LLM and embedding model across all baselines to ensure that any performance differences observed were attributable to the memory management methodologies, rather than variations the models' capabilities or embeddings.
alama- 10w11-000nnstttu and E.5-Mi wtw.eemeeddnng----eee-
4.3 IMPLEMENTATION DETAILS AND EVALUATION METRICS
Following previous work (Packer et al. 2023 Tang & Yang 2024), report the end-to-end question answering performance. Given each contex montexl-question-aae answer tuple, the experimental procedure involves four steps:
1. Load the corresponding dialogue/history into the memory.
2. Retrieve the relevant information from the memory based on the given query.
3. Use GPT-4o to answer the query based on the retrieved information.
4. Evaluate the generated answer using of the following metrics: 1) Use GPT-4o compare the generated answer with the reference answer, resulting a binary accuracy score; 2) Evaluate the ROUGE-L recall (R) metric of the generated answer compared the relatively short gold answer labels, without involving the LLM judge.
The detailed prompts for steps 3 and can be found in Appendix A.2 Other implementation details for MemTree can be found in Appendix A.I
5 RESULTS
5.1
MULTI-SESSION CHAT
15-round dialogue We present the MSC results Table For the naive baseline, directly providing the full history to GPT-4o yields the best result, achieving accuracy of 96%. This outcome is expected, given that the entire dialogue consists of only 15 rounds and fewer than one thousand tokens. We also note that providing summary of the chat history significantly drops performance
7

---

Published as a conference paper at ICLR 2025
Table Accuracy on QuALITY. Performance is evaluated on (1) Easy questions, answerable with surface-level information, and (2) Hard questions, requiring deeper reasoning. MemTree shows strong overall performance, surpassing online methods and nearing offline methods in both categories.
Model
Context
Easy
Hard
Overall
Alama-3.1-708
Query Full text
70.1
60.3
65.1
Offline Method
IJama-3.1-1 1--70B
Query RAPTOR Query + GraphRAG
65.2
53.0
59.0
Ilama-3.1-700
65.9
59.8
62.8
Online Method
Llama-3. 3-00
Query + MemoryStream
46.7
41.0
43.8
3.1ma-3.1-70B
Query + MemTTree
63.3
56.5
59.8
to 35%, even for the more powerful GPT-4 Turbo model (Packer et al., 2023). This decline occurs because the summary may not cover the topics the query is addressing. To directly compare the performance of different memory management algorithms, we consider the setting where only the query and the retrieved information are provided to the LLM. In this scenario, Mem'Tree surpasses both MemStream and MemGPT
200-round dialogue Table presents the results on MSC-E. We observe that both MemoryStream and Mem'rre achieve better overall accuracy than the naive baseline, which directly uses the full history. This illustrates the importance of having an external memory system the conversation history grows. When we break down the accuracies based on the positions of the supporting evidence within the entire dialogue, we find that the naive baseline performs best when the evidence is presented early on, likely due to position bias (Liu et al., 2024). It is worth noting that since Mem updates the memory sequentially based on the order of the dialogue, it inherently favors more recent conversations over older ones. This bias is demonstrated in Table 2, where the accuracy increases from 82.1 to 84.2. Nevertheless, MemTree consistently outperforms MemoryStream across all positions (sce Figure A.I for visualization).
5.2 SINGLE--DCCMENT QUESTION ANSWERING
Table presents the accuracy of various models on the QuALITY benchmark. Llama-3.1 70B, which processes the full text in a single pass, achieves the highest overall accuracy 65. %. This superior performance is attributed to the dataset's s relatively short length (5000 tokens), a trend also observed with the MSC dataset. Offline RAG methods such as RAPTOR and GraphRAG, designed for handling knowledge retrieval over longer contexts, achieve lower accuracies of 59.0% and 62.8%, respectively, The current online memory update method, MemorySSteam, struggles with efficiently extracting memory vey-value pairs, resulting in significantly lower accuracy of 43.8%. In contrast, method, MemTreee matches the offline performance of RAPTOR with a slightly higher accuracy of 59.8%, especially excelling on hard questions that demand deeper reasoning and comprehension. Moreover, MemTTree retains the advantage of being an online method, allowing for continuous memory updates minimal computational cost. Refer Figure A.2 for visualization of the results.
5.3
MUL.TI-DOCUMENT QUESTION ANSWERING
Table 4 summarizes the end-to-end performance of MultiHop RAG using various memory retrieval algorithms. All methods perform exceptionally well on inference-style questions, which focus on fact-checking based single document, consistently achieving over 95% accuracy. However, when it comes to more complex questions-those requiring the comparison of multiple documents or significantly outperforms MemoryStream, achieving 9.1 percentage point advantage. Moreover, despite RAPTOR having full access to all information, Mem ' overall performance is within just 0.5 percentage points of this offline method. See Figure A.3 for detailed visualization of these results.
temporal reasoning-Menil
Another observation from the table is that while humans can annotate evidence fairly accurately for inference and comparison-style questions, the annotated evidence for temporal questions is less
We were unable to reproduce the results with the existing MemGPT GitHub codebase.
8

---

Published as a conference paper at ICLR 2025
Table Accuracy on MultiHop RAG. Results are shown for (1) Inference queries, (2) Comparison queries, and (3) Temporal queries. MemTree outperforms MemoryStream on comparison and temporal queries, narrowing the gap to the offline RAPTOR.
Model
Context
Inference
Comparison
Temporal
Overall
GPT-40 Human Annotated Evidence
98.4
80.1
55.6
79.2
Offline method
GPT-4o
Query RAPTOR
96.6
76.5
66.0
81.0
GPT-4o
Query GraphRAG
96.0
66.3
78.3
Online method
GPT-4o
Query MemoryStream
96.1
64.8
59.3
74.7
GPT-4o
Query MemTTee
96.0
73.9
68.4
80.5
Uber's Q3 cenings repor lighlights ssiptificans tumancand priftubilll. mansitioing from 51 billion loes last your to net lncone of $219 million
October 2023 friendly Sood Germany and suffered defrat Corcurency, the U.S. women'' team has appoimedd Emma Hayes the new haad curch...
The housing market foing downoum, with caistng hone sals plunsins to levels sees during the Great Recesion This daaline drives by nalucaal allondbility
(USMNT)
Haye, lighty saccesetul
Wonten, appourted Women's National Soccer (USWNT)...
national
(USMNTI Germany suffired
3.1 defoat Resscller Fiekd
Derpic loss, there wore
notable individual performance.
The particulars around timing and the muving Sorvard have bozn the seow of disessioon betwoer Hayes US continued
their recert 3-1 defoet to Germany, the USMNT displayal a blend dullensiee promine and defensive shortcomings Chrisian Pulisi,, with stuming god and high pes completion mic. and Tim Wick's qpeed and link- up paa. were offarsive hightights. Glo Reyao also contribated creativety. However, the defersive side was publematicc
Suverber.
draniiallyy
camps, incluinng frendlics
Ciyspics
Pins.
international
In his first minzes intematioona foctball under Grogg Bertalter snce the World Cup fallerr, Glo Reyna was ussal self, driwingg the smontoo Cerman defenders and proving visionory with
windows betwoes Tuoday's
unsounement plarned
pessing He combiaed with Fetaria Balogua oa number of ococassioss on the counter. which up
meluding KONCACAT
that US Sass have been begging for more Reyna was only fit for 45 minutes of play here be returts fnum beg injary, bui mo coinaddene that Gemanyy Inly accunal mitlich dimninanno when cane the fied
Cup Febmary and March. US Seccer
has plan in piace for the transttion
Figure 3: Visualization of the Learned MemTree Structure on the MultiHop RAG Dataset. Due to space limitations, display only small subtree from the entire tree (a larger subtree is depicted in Figure As we traverse deeper into the tree, the content stored the nodes becomes increasingly specific. For instance, the three blue nodes shown in the bottom right corner begin with a general summary of the USMNT's 3-1 defeat to Germany, then branch into specific insights on individual performances and team dynamics, and ultimately delve into detailed analysis of Gio Reyna's impact during the match. Note that all intermediate contents in the parent nodes are generated by Mem Tree during the node update step. This hierarchical organization demonstrates how MemTree efficiently stores and retrieves information, progressing from overarching concepts to specific details.
precise. This results in worse performance than the model-derived memory for temporal questions. Importantly, MemTrre excels on temporal reasoning tasks, surpassing all baselines, including offline approaches and human-annotated evidence.
Statistics of the Learned MemTree Table 5 presents statistics for the learned MemTTre on the Multihop RAG dataset, which consists of 609 documents. The resulting tree contains 3,154 nodes, with maximum depth of 13 and an average branching factor of 2. Figure 4 illustrates the distribution of nodes across different depth levels, revealing that the majority of nodes are concentrated between depths 3 to 5. As the tree deepens, the information stored in the nodes increases in length. For instance, at depth 1 (just below the root), the median token count is slightly over 200, with a small deviation. By depth 10 and beyond, the median token count grows to around 800, with greater variability (see Figure

---

Published as a conference paper at ICLR 2025
Avg Nodes per Depch
Median Tokens per Depth
500
Mem Tree Property
Value
800
#Nodes
3164
300
Toluns
600
#Branching Nodes
#Leaf Nodes
1706
1458
800
200
Depth (max)
13
Depth (average)
4.9
0
Branching Factor Height Width Ratio
2.1
10
10
6.5
Depth
Depth
Figure 4: Depth- based Stats of MemTree learned on Multi-
Table 5: Overall Stats of MemTree learned MultiHop
Hop RAG
Comndativ Elapoed Time (bonuz))
Por-inertion Ellaused Time (a)
Meniloo (oalize)
(sllias)
GmyldRlG (:lliine)
1.5
1.5h
1.0
1.26
0.5
200 400
6.0
290
400
600
Documentss
# Documentts
Figure 5: Efficiency of MemTree vs. RAPTOR and GraphRAG: MemTree's top-down insertion
strategy allows content aggregation and embedding updates be parallelized on the CPU, significantly accelerating memory updates as memory grows. Despite its cumulative cost being approximately 1.4x higher than the offline algorithms (RAPTOR and GraphRAG), it remains manageable. Results are reported on the MultiHop dataset.
Hierarchical Representation of the MemTree reflects semantic organization. Higher-level nodes capture more abstract, generalized information, while deeper nodes store finer details. Figures [ and 3 further visualize this hierarchy. The model effectively groups related concepts, with intermediate parent nodes summarizing high-level informa- tion during memory insertion. This structure enables the MemTree to maintain a balance between abstract representations the top and specific details at the bottom.
The hierarchical structure of the learned Mem
Time Efficiency of Online Algorithm vs Offline Algorithm MemTree's continuous updates during conversations make it ideal for real-time scenarios. Once the traversal path is defined, its top-down insertion allows parent node updates to be parallelized on the CPU, accelerating the update process and reducing bottlenecks as memory grows. In contrast, RAPTOR and GraphRAG use clustering in RAG setup, making memory updates after index construction impossible or costly. As shown Figure MemTree inserts new information 10 seconds on average, while RAPTOR and GraphRAG take over hour to build the full memory tree, making it impractical for real-time use. Although MemTree's 's cumulative time cost 1.4x higher than RAPTOR's 's due to continuous updates, this trade-off enables maintaining an up-to-date memory in real time.
6 CONCLUSION
Mem'Tree effectively addresses the long-term memory limitations of large language models by emulating the schema-like structures of the human brain through a dynamic free-based memory representation. This approach enables efficient integration and retrieval of extensive historical data, as demonstrated by its superior performance on four benchmarks with different interactive contexts. Our evaluations reveal that MemTree consistently maintains high performance and demonstrates human-like knowledge aggregation by capturing the semantics of the context within its tree memory structure. This advancement offers a promising solution for enhancing the reasoning capabilities of LLMss in handling long-term memory.
10

---

Published as a conference paper at ICLR 2025
Ethical Statement In developing MemTree, commit to ensuring that private proprietary data is mishandled during our experiments, and all data used for training and evaluation are publicly available. While current research does not explicitly address principles such as transparency, responsibility, inclusivity, bias mitigation, or user safety, we recognize that recent advancements in these areas be integrated into the memory learning component of our algorithm. We encourage the research community to engage with these ethical considerations as we strive to enhance our understanding and implementation of responsible Al practices.
Reproducibility Statement We provide comprchensive details for reproducing our results in Sec- tion 4 and the Appendix, including our experimental setup, evaluation metrics, and implementation settings. The code and seripts used in our experiments will be made publicly available upon accep- tance. All external libraries and dependencies required for reproduction are specified. Our method has been evaluated on both open-source and commercial models demonstrate its applicability.
Disclaimer This content is provided for general information purposes and is not intended to be used in place of consultation with our professional advisors. This document may refer to marks owned by third parties. All such third-party marks are the property of their respective owners. No sponsorship, endorsement or approval of this content by the owners of such marks is intended, expressed or implied.
Copyright @ 2024 Accenture. CC BY-NC-ND. All rights reserved. Accenture and its logo are registered trademarks of Accenture.
REFERENCES
John Anderson. Cognitive psychology and its implications. Macmillan, 2005.
Petr Anokhin, Nikita Semenov, Artyom Sorokin, Dmitry Evseev, Mikhail Burtsev, and Evgeny Bumnev. Arigraph: Learning knowledge graph world models with episodic memory for Ilm agents. arXiv preprint 241:22407.04333 2024.
Jinheon Baek, Alham Fikri Aji, and Amir Saffari. Knowledge-augmente language model prompting for zero-shot knowledge graph question answering. Proceedings of the First Work- shop Matching From Unstructured and Structured Data (MATCHING 2023), 2023. URL
https: httts:://pp..semaeeee wtw.:e/ssseettttccocsoooo wtt.:/schhooo.oooooororuuututtae 260063238
Taiyu Ban, Lyvzhou Chen, Xiangyu Wang, and Huanhuan Chen. From query tools to causal architects: Harnessing large language models for advanced causal discovery from data. ArXiv, abs/2306. 16902, 2023. URL :/ap::://pppp//// aetaap..eemaann semant westttcccchhhcco wwwpooooogogiiee/..0. 2599288733
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150, 2020.
Aydar Bulatov, Yuri Kuratov, Yermek Kapushev, and Mikhail S Burtsev. Scaling transformer to Im tokens and beyond with rmt. arXiv preprint arXiv:2304. 1062, 2023.
Yukang Chen, Shengju Qian, Haotian Tang, Xin Lai, Zhijian Liu, Song Han, and Jiaya Jia. Longlora: Efficient fine-tuning long-context large language models. arXiv preprint arXiv:2309. 12307, 2023.
Xin Cheng, Di Luo, Xiuying Chen, Lemao Liu, Dongyan Zhao, and Rui Yan. Lift yourself up: Retrieval-auggeette text generation with self memory. ArXiv, 2atp23355024337 2023. URL Stttss://aps www.nt wtwpiicchhoaaarrro/oeoee
wwwp//orr///...oooooo TD: 258479968
Yiran Ding, Li Lyna Zhang, Chengruidong Zhang, Yuanyuan Xu, Ning Shang, Jiahang Xu, Fan Yang. and Mao Yang. Longrope: Extending Imm context window beyond million tokens. arXiv preprint arXiv:2402.13753, 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, et al. The llama herd of models. arXiv preprint arXiv:2407.21788 2024.
11

---

Published as a conference paper at ICLR 2025
Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, and Jonathan Larson. From local to global: A graph rag approach to query- foccuse summarization. arXiv preprint 1111:2444.161100 2024.
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. Retrieval- lenrevellaugmeeneed generation for large language models: A survey. arXiv preprint arXiv:2312. 10997, 2023.
Vanessa E Ghosh and Asaf Gilboa. What is a memory schema? a historical perspective on current neuroscience literature. Neuropsychologia, 53:104-114, 2014.
Asaf Gilboa and Hannah Marlatte. Neurobiology schemas and schema-mediated memory. Trends in cognitive sciences, 21(8):618 6--6631,, 2017.
Huiqiang Jiang, Qianhui Wu, Chin-Yew Lin, Yuqing Yang, and Lili Qiu. Limlingua: Compressing prompts for accelerated inference of large language models. arXiv preprint arXiv:2310.05736, 2023.
Ari Kobren, Nicholas Monath, Akshay Krishnamurthy, and Andrew McCallum. hierarchical algo- rithm for extreme clustering. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 255 264, 2017.
Yuri Kuratov, Aydar Bulatov, Petr Anokhin, Dmitry Sorokin, Artyom Sorokin, and Mikhail Burtsev. In search of needles in a 11m haystack: Recurrent memory finds what 1lms miss. ArXiv, 1bs/2402.10790, 2024. URL htttp:://epi.eemnnciccho....
semanticscholes wwwpttiisscoola..oorooooooo wwtp:ooog/ooooooo..
267740348
Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157-173, 2024.
Aditya Krishna Menon, Anand Rajagopalan, Baris Sumengen, Gui Citovsky, Qin Cao, and Sanjiv Kumar. Online hierarchical clustering approximations. arXiv preprint 1909.0990999 2019.
Eric Mitchell, Charles Lin, Antoine Bosselut, Christopher D. Manning, and Chelsea Finn. Memory-based model editing at scale. ArXiv, abs/2206.06520, 2022. URL https://api
semanticscholas cotp:rrroo/oooooo:ooo/r
Ali Modarressi, Ayyoob Imani, Mohsen Fayyaz, and Hinrich Schütze. Ret-llm: Towards general read-write memory for large language models. arXiv preprint arXiv:2305. 14322, 2023.
Benjamin Moseley and Joshua Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k- k-means, and local search. Advances in Neural Information Processing Systems, 30, 2017.
Charles Packer, Vivian Fang, Shishir G Patil, Kevin Lin, Sarah Wooders, and Joseph E Gonzalez. Memgpt: Towards lims as operating systems. arXiv preprint arXiv:23 2023.
Richard Yuanzhe Pang, Alicia Parrish. Nitish Joshi, Nikita Nangia, Jason Phang, Angelica Chen, Vishakh Padmakumar, Johnny Ma, Jana Thompson, He He, et al. Quality: Question answering with long input texts, yes! arXiv preprint arXiv:2/ 12.0860088 2021.
Joon Sung Park, Joseph OrBre,, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceedings of the 36th annual acm symposium on user interface software and technology. pp. 1-22, 2023.
Parth Sarthi, Salman Abdullah, Aditi Tuli, Shubh Khanna, Anna Goldie, and Christopher D Man- ning. Raptor: Recursive abstractive processing for tree-organized retrieval. arXiv preprint arXiv:2401.18059, 2024.
Simeng Sun, Kalpesh Krishna, Andrew Mattarella-Micke and Mohit Iyyer. Do long-range language models actually use long-range context? ArXiv, hbss///19.0911... 2021. URL https: /api semant cschol ar. httpaaarrrr///orraaa133333731311
12

---

Published as a conference paper at ICLR 2025
Yixuan Tang and Yi Yang. Multihop-rag: Benchmarking retrieval-auggmente generation for multi- hop queries. arXiv preprint arXiv:2401.15331, 2024. Copyright @ 2024. Licensed under CC BY-SA 4.0, including disclaimer of warranties. Available at https//aurxi..or//////200.113331
Milena Trajanoska, Riste Stojanov, and Dimitar Trajanov. Enhancing knowledge graph con- struction using large language models. ArXiv, 0bs/23055004777 2023. URL https://apt
semanticscholar. :ttp:ar.....r/rrrruaa02223311111
Szymon Tworkowski, Konrad Staniszewski, Mikolaj Pacek, Yuhuai Wu, Henryk Michalewski, and Piotr Milos. Focused transformer: Contrastive training for context scaling, Advances in Neural Information Processing Systems, 36, 2024.
Liang Wang, Nan Yang. Xiaolong Huang, Linjun Yang, Rangan Majumder, and Furu Wei. Improving text embeddings with large language models. arXiv preprint arXiv:2401.00366 2023.
Jason Weston, Sumit Chopra, and Antoine Bordes. Memory networks.
arXiv preprint
1rXiv:1410.3916 2014.
J Xu. Beyond goldfish memory: Long-term open-domain conversation. 10X.v:2107.07567, 2021.
arXiv preprint
Liang Yao, Jiazhen Peng, Chengsheng Mao, and Yuan Luo. Exploring large language mod- els for knowledge graph completion. ArXiv, abs/2308. abs/2308.13916, 2023. URL hetps://api
261 242758
Tian Zhang, Raghu Ramakrishnan, and Miron Livny. Birch: an efficient data clustering method for very large databases. ACM sigmod record, 25(2):103-) 1996.
Zeyu Zhang, Xiaohe Bo, Chen Ma, Rui Li, Xu Chen, Quanyu Dai, Jieming Zhu, Zhenhua Dong, and Ji-Rong Wen. A survey the memory mechanism of large language model based agents, arXiv preprint arXiv:2404. 13501, 2024.
Wanjun Zhong, Lianghong Guo, Qiqi Gao, He Ye, and Yanlin Wang. Memorybank: Enhancing large language models with long-term memory. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 19724-19731, 2024.
13

---

Published as a conference paper at ICLR 2025
A
APPENDIX
A.1
MEMTREE DETAILS
Further details and parameter settings for our approach are outlined below. Unless otherwise specified, these settings are consistent across all experiments presented in the paper.
A.1.1 MEMTREE ALGORITHM
The following outlines the algorithmic procedure for incrementally updating and restructuring the memory representation in MemTree. This approach ensures that new information is efficiently integrated into the existing memory hierarchy while dynamically adjusting based on content similarity and structural depth.
Parameters:
c: the textual content stored node or introduced as new information.
e: the embedding vector representing the content, generated by embedding function fenh-
v: node in the memory tree, which contains content, embeddings, and connections to other nodes. Note that the root structural node and does not hold content.
d: the depth of node in the tree.
Algorithm 1 Adding New Information to Mem'Tree
Require: New information Cnew: root node to. threshold function ((d)
1: Cnew < fembb(Cuu (new)
2: INSERTNODE(PO.. Cnews Cnew, 0)
3: procedure INSERTNODE(1, Enew, Crew d)
4: if u is leaf then
5: Expand v into parent
6: Create and attach child node Vleaf with original content
7:
end if
8:
Compute similarity 8; sim(Cnew 6;) for each child o of e Ubest arg max();;, 8max +- max(s;)
9:
10:
if Smax 2 0(d) then
11:
Co <- Aggregate(CCs, Cnew)
12:
Cy + femmbbba
13:
INSERTNODE( (bestt Cnews Cnews d + 1)
14:
else
15:
Create and attach child node Vehild with Cnew
16:
end if
end procedure
A.1.2 AGGREGATE OPERATION
When new information is added, the content of parent nodes along the traversal path is updated through a conditional aggregation. This process combines the existing content of the parent node with the new content, factoring in the number of its descendants. The aggregation operation is implemented using the following prompt:
You will receive two pieces of information: New Information is detailed, and Existing Information is a summary from (n (n_children) previous entries. Your task is to merge these
into single, cohesive summary that highlights the most important insights.
Focus the key points from both inputs.
Knaure the final summary combines the insights from both pieces of information.
14

---

Published as a conference paper at ICLR 2025
If the number of previous entries in Existing Information is accumulating (more than 2), focus on summarizing more concisely, only capturing the overarching theme, and getting more abstract in your summary.
Output the summary di directly.
[New Information]
(new_content)
[Existing Information (Erom In corren previous entries) [current_content)]
[ Output Summary
A.1.3 ADAPTIVE SIMILARITY THRESHOLD
The adaptive similarity threshold ensures that deeper nodes, representing more specific information, require higher similarity for new data integration, while shallower nodes are more abstract and accept broader content. This mechanism preserves the tree's hierarchical integrity by adjusting selectivity based on the node's depth. The threshold is computed as:
rate x current_ depth
threshold
exp
max max_depth
where:
base_ theeshhre 0.4
rate 0.5
surrent_eeptt is the depth of the current node.
max_ max_depth is the maximum depth of the tree.
1.1.4 RETRIEVAL
For the MSC experiment, the retrieval system returns the top similar dialogues from 15-round conversations, with context length of 1000 tokens for all models. In the MSC-E dataset, due to longer conversations, the retrieval returns the top k 10 similar dialogues, with a context length of 8192 tokens to accommodate the models with full-chat history. This setting is similarly applied to the Multihop RAG and QuALITY experimenst, where longer contexts are required.
A.2 FURTHER EXPERIMENTAL DETIALS
A.2.1 DATASET STATISTICS
We summarize the dataset statistics in Table A.1 to provide a clear overview of the scale and complexity of the data used in our experiments. For the Multi-Session Chat (MSC) dataset, worked with 500 conversation sessions, each consisting of about 14 rounds, allowing us to evaluate the model's ability handle multi-turn dialogues. memory representation was independently built for each session, capturing dialogues as the conversation progressed. In the extended version, MSC-E, we expanded the original dataset by generating an additional 70 sessions, each containing over 200 rounds of dialogue. For these longer sessions, a memory representation was similarly built for each session, but the increased number of rounds presented greater challenge in managing long-term information across interactions. The QuALITY dataset, focusing document comprehension, contains around 230 documents with an average 5,000 tokens each. For each document, an independent memory representation built to facilitate reasoning across the entire document. Lastly, MultiHop RAG includes 609 articles and over 2,500 multi-hop questions. constructed across all the news articles, enabling the model to retrieve and integrate information from multiple documents when answering complex multi-hop questions.
unified memory representation was
Further details about the configurations for each dataset follows:
15

---

Published as a conference paper at ICLR 2025
MSC and MSC-E: For the MSC and MSC-E datasets, each conversation consists of multiple rounds. We inserted each round individually into MemTree without applying any chunking. For each new conversation, built independent MemTree.
QuALITY: We inserted each document individually and chunked it into non-overlapping segments of 512 tokens.
MultiHop RAG: We inserted each document individually and chunked it into non-
overlapping segments of 1024 tokens.
Dataset
Statistic
Value
Conversation Sessions
500
Rounds per Session
13.7 + 0.6
MSC
Packer et al.
2023
Tokens per Dialogue
21.6 11.9
Queries per Session
Conversation Sessions
70
Rounds per Session
200.3 + 16.7
MSC-E
Tokens per Dialogue
29.5 + 1.5
Queries per Session
101.9 + 8.6
Documents
230
Tokens per Document
5028.4 + 1619.1
QuALITY Pang et al. 202
Queries per Document
9.0 + 1.0
Easy Queries
1021
Hard Queries
1065
Articles
609
Tokens per Article
2046.4 + 189.0
Total Queries
2255
Multihop RAG (Pang al.
2021
Inference Queries
816
Comparison Queries
856
Temporal Queries
583
Table A.1: Dataset Statistics
A.2.2 EVALUATION METRICS
Predicted Response Generation: To assess retrieval performance, configure the LLM to generate a response to the query based solely on the retrieved content using the following prompt:
Write a high-quality short answer for the given question using only the provided search results (some of which might be irrelevant).
Question ] (query)
[ Search Results (retrieved_content))
Output
Binary Accuracy Evaluation: To measure binary accuracy across all experiments, we employed the following prompt, instructing the model to evaluate the predicted response against the ground-truth answer:
Your task is to check if the predicted answer appropriately responds to the query in a similar way as the ground-truth answer.
Instructions:
Output '1' if the predicted answer addresses the query similarly to the ground-truth answer. Output '0' if it does not. Only output either '0' or "1' No explanations extra text.
16

---

Published as a conference paper at ICLR 2025
Query
(query)
Ground-Truth Answer ]
(gt_answer)
Predicted Answer ]
(predicted_answer
[ Output ]
A.2.3 MSC-E DATA GENERATION
Building on the MSC dataset from Packer et al. (2023). we extend each conversation to 200 rounds using the following iterative process. sliding window of the most recent turns is maintained, and for each step, the next 2 rounds of dialogue are generated using the prompt below. This approach allows for natural progression of conversation while keeping the context manageable for the model:
Generate continuation
conversation between Alex and Bob. Follow these guidelines:
1. Alternate strictly between Alex and Bob, starting with Alex.
2. Alex should speak exactly (n_rounds) times, and Bob should speak exactly (n_rounds) times.
3. Rach turn should consist of 1-3 sentences.
4. Ensure that each response flows logically and organically from the previous turn, avoiding forced transitions or unnatural questions.
5. Focus on developing rapport between the characters. Use a mix of statements, reactions, and occasional questions to maintain a cenversational tone.
6. Allow the conversation to transition smoothly between topics, keeping it casual and coherent.
conversation History (recent_ccht__hist) Generated Dialogue
Output Example: Below is excerpt from the MSC-E dataset, showcasing one session conversation that spans 200 rounds in total.
Alex: Hi! Hew are you doing tonight?
Bob: I'm doing great. Just relaxing with my dogs.
Alex: Great. In my spare time volunteer work.
Bob: That's s neat. What kind of volunteer work do you do?
That would be great! I'd love to try sone of your Thai recipes. Cooking you think?
Alex:
such creative outlet, don't
Bob: Absolutely, it's like culinary adventure in your own kitchen. Speaking of adventures, have you planned any trips lately, maybe to explore new cuisines firsthand?
Alex:
yet, but I've been dreaming indulge in the food and scenery. How about you, any travel plans on the horizon?
trip to Italy
Bob: I've been thinking about visiting Japan. I'm fascinated by their culture and, of course, the sushi! It would be an amazing experience
see all in person.
Alex: Japan sounds incredible! The blend of traditional and modern aspects in their culture is so intriguing. You'11 have to share your experiences if you go.
17

---

Published as a conference paper at ICLR 2025
A.2.4 MSC-E QUERY GENERATION
To generate queries and ground-truth responses for evaluating memory retrieval quality, we apply the following prompt to subsets of the conversation history. The generated questions will help assess how effectively the memory captures and retrieves information from various points in the dialogue:
Based the conversation between "Alex" and "Bob" belox, generate {n_q) unique questions that "Bob" can ask "Alex," derived from the information "Alex" has shared. Each quostion should be directly answerable using the conversation's content.
Ouzput a JSON array where each element is an object with the following keys:
"question": The question for Alex.
"response"; The correspending answer derived directly from Alex's information.
Ensure the output is valid JSON. Only output the JSON array. [Conversation]
(chat_hist)
A.3 FURTHER EXPERIMENTAL RESULTS
A.3.1 ACCURACY VS POSITION OF EVIDENCE (MSC-E)
We present accuracy results on the MSC-E dataset, focusing on how performance varies based on the position of supporting evidence within the dialogue. This analysis demonstrates the model's ability to effectively retrieve and utilize information from different points in extended conversations, highlighting its robustness in scenarios where a memory component essential for maintaining context.
MemTTre Tree (ours)
MemoryStream
GPT-4o
Accuracy Score (0-1)
0.85
0.80
0.75
0.70
0
20
40
60
80
100
120
140
160
180
200
Position of the Supporting Evidence
Figure A.1: Accuracy MSC-E.
A.3.2 PERFORMANCE VS QUESTION DIFFICULTY (QUALITY)
The experiment is conducted the QuALITY benchmark to evaluate model performance on questions varying difficulty. Both single-pass and serieval-auugenneer methods are tested. focusing on the comparison between online and offline memory representation approaches. Llama-3,1 70B, which processes the entire document a single pass, serves as the baseline, while RAPTOR (Sarthi al. 2024), GraphRAG (Edge et al. 2024), MemoryStream (Park et al.) (202)), and Mem' Meme'ree (ours) are assessed for their ability to manage document comprehension with memory retrieval. Offline methods (RAPTOR and GraphRAG) that need be rebuilt from scratch incorporate new information are shaded in gray.
A.3.3 PERFORMANCE QUERY TYPE (MULTIHOP RAG)
We present results across three query types: (1) Inference queries, requiring reasoning from retrieved information; (2) Comparison queries, which involve evaluating and comparing evidence within the
18

---

Published as a conference paper at ICLR 2025
70.1
Mesn Tree (ouns)
Easy
00.2
10.2
MemoryStream
66.7
RAPTOR
65.3
GraphRAG
Alama-3.1-7U)
Hard
Overall
20
40
Accuracy Score (%)
Figure A.2: Accuracy on QUALITY
retrieved data; and (3) Temporal queries, analyzing time-related information to determine event sequences. Here, we compare online and offline methods (shaded gray). Note that offline methods must be rebuilt from scratch to incorporate new information and cannot support real-time memory updates like Mem'Tree
55.6
Mom' Tree (ours)
66.3
Temporal
66.1
MemoryStream
591.4
RAPTOR
68.5
GraphRAG
GPT-44
(w/ Human Annotated Evidenoe)
Comparison
76.6
G1.
14.00
98.5
Inference
96.11
96.0
0
20
40
60
80
100
Accuracy (%)
Figure A.3: Accuracy on MultiHop RAG.
A.3.4 LLM CALL EFFICIENCY COMPARISON
We evaluate the efficiency of each baseline method by measuring the number of LLM calls required load the Multihop RAG dataset. Online methods like MemoryStream and proposed Mem support dynamic addition of new information to the memory representation, enabling efficient and incremental updates. In contrast, offline methods must be rebuilt from scratch incorporate new information, which is both computationally expensive and time-consuming For example, incorporating single new observation requires approximately 3,750 LLM calls for RAPTOR and about 3,850 LLM calls for GraphRAG, these methods assume static knowledge base when constructing the memory representation.
Our approach, Mem achieves high level of accuracy the Multihop RAG task while requiring only an average 3.27 LLM calls per insertion, highlighting its efficiency and scalability, Moreover, MemTree's node updates can be performed concurrently, further enhancing its performance. After detecting the traversal path for an insertion, the content aggregation LLM calls along the path can be executed in parallel.
19

---

Published as a conference paper at ICLR 2025
Table A.2: Performance and Efficiency on Multihop RAG: Overall accuracy and average number of LLM calls per insertion for each method.
Method
Accuracy (%)
#LLMM Calls
Offline Methods
RAPTOR GraphRAG
3753 81.0
78.3
3858
Online Methods
Memory Stream
74.7
per insertion
Mem Tree
80.5
3.27 + 2.38 per insertion
A.3.5 ABLATION: COLLAPSED RETRIEVAL VS. TRAVERSAL RETRIEVAL
We evaluate MemTree's performance in the Multihop RAG experiment using two retrieval strategies:
1. Collapsed Retrieval:
This approach flattens the tree hierarchy, treating all nodes single set for comparison. Each node directly evaluated against the query without considering the tree's structure (see Section 3.2)
2. Traversal Retrieval:
This method traverses the structure of the tree. Starting from the root, it retrieves the top-k nodes at each level based on cosine similarity to the query vector. The process continues recursively, selecting the top-k nodes from the child nodes of the previously retrieved top-k. Although straightforward, an implementation of this retrieval method available online
Traversal Retrieval
Collapsed Retrieval
0.96
0.9
Average Accuracy
0.8
0.28
0.79
0.772
0.70
0.71
0.72
0.71
0.7
Cr08
0.66
Query Type
Comparison
0.6
Infevence
Temporal
Overall
0.5
Comperison Inference
Temporal
Overall
Top per Depth
Query Type
Figure A.4: Accuracy Comparison: MemTree's accuracy the MultiHop RAG task using collapsed and traversal retrieval strategies.
The traversal retrieval method, while leveraging the hierarchical structure MemTree, introduces trade-offs between accuracy and coverage. By limiting the search space at each level to the top- nodes, traversal retrieval focuses on localized paths within the tree. However, this approach necessitates careful tuning of the parameter k. As shown in Figure A.4 higher values of k (e.g.. = 10) achieve accuracy comparable to the collapsed retrieval method, which evaluates all nodes simultaneously. In contrast, lower values of & (k < 5) significantly compromise accuracy in the Multihop RAG experiment by prematurely narrowing the search space and missing relevant information, in the accuracy drop for temporal queries.
retriever.py
20

---

Published as a conference paper at ICLR 2025
While collapsed retrieval excels by evaluating all nodes simultaneously identify information the appropriate level of granularity for complex queries, traversal retrieval biases the search towards paths already established in the tree hierarchy. This bias can lead to redundancy, where retrieved information from parent nodes is repeated, while detailed information in deeper nodes remains unaccessed. Additionally, traversal retrieval risks exhausting the available context length before incorporating critical details from deeper nodes, particularly in scenarios requiring fine-grained reasoning.
A.3.6 ABLATION: ROBUSTNESS OF MEMTREE UNDER VARIOUS LLM AND EMBEDDING MODELS
In the main paper, we constructed MemTree using two widely adopted LLMs, GPT-4o - 3.1-70R-Tnstruct. text-embeddi ng- 3-3--aa 3-r-eearge and E5-Mistral- -it-rall---Instruss further explore the robustness of MemTree when smaller models used for its construction.
along with two embedding models,
this section, we
To evaluate how the structure of MemTree changes when built with smaller models, we compare the statistics of the learned MemTree on the Multihop RAG dataset using smaller and smaller embedding model As summarized in Table A.3] the resulting trees constructed with smaller LLMs and embeddings have structures comparable to those built with larger models (i.e., in terms of the number of nodes, branching factors, and average depths).
LLMs (GPT-40-miní and 11 1----3..-----Intteee
Figure A.5 illustrates the distribution of nodes across different depth levels, revealing that the majority of nodes are concentrated between depths and 5 across all models. Additionally, the tree deepens, the length of the information stored increases, highlighting that deeper nodes capture more abstract and overarching themes within the MemTree hierarchy. These observations indicate that using smaller models still preserves the hierarchical structure achieved with larger models. The consistency in structural statistics suggests that MemTree's ' construction process robust to the choice of LLM and embedding model sizes, maintaining effectiveness even with more resource-conse constraind models.
Furthermore, as shown in Table A.4 the accuracy results obtained using trees built with smaller models are comparable to those achieved with larger models. This demonstrates that MemTree can maintain high performance even when constructed using smaller LLMs and embeddings, further emphasizing its practicality in scenarios with limited computational resources.
Node Count per Depth
Avg Token Count per Depth
500
1000
400
800
Laaaa 3.1 3.1-B text nott-embeedlnng---e --
Nodee
300
600
GPT-4o-minl test--eubeeddiiag----a
200
400
GPT-4o
100
200
text etabedding large
0
5
10
15
10
15
Depth
Depsh
Figure A.5: Dapth statistics of MemTTre learned on the Multihop RAG dataset using different LLM and embedding models. The distribution of nodes across depths and the increase in information length deeper levels are shown.
A.3.7 ABLATION: ADAPTIVE THRESHOLD PARAMETERS
Mem Tree employs adaptive similarity threshold 0(d) that varies with node depth d to maintain hierarchical integrity. At greater depths, nodes represent more specific information and thus require higher similarity for data integration; shallower nodes accept broader content. The threshold function defined as: (d) = bo where 6n is the base threshold at depth zero, and À controls the rate of increase with depth. Throughout our experiments (see Section A.1.3). Og 0.4 and X 0.5.
21

---

GPT-40 Published as a conference paper at ICLR 2025
Table A.3: Overall statistics of MemTree on the Multihop RAG dataset using various LLM and embedding models.
L.M Model
GPT-40-mini
Llama-3. 1. 3-18
Embeddiigg Model
text embed-3-large
text-embedt 3-small
text-embed 3- sma
#Nodes
3,164
3,178
3,174
#Leaf Nodes
1,706
1,705
1,206
ABranching Nodes
1,458
1,472
1,68
Depth (max)
13
15
15 5.0
Depth (average)
Beanching Factor
2.1
Hright-t--Wah Ratio
7,
7.5
Table A.4: Accuracy results on the Multihop RAG dataset using MemTree built with various LLM and embedding models.
LLM Model
Embedding Model
Inference
Comparison
Temporal
Overall
GPT-4o
text-embed-3--2e
96.0
73.9
68.4
80.5
GPT-4o-mini
text--ebed-3-sma.
94.6
71.3
66.0
78.4
L1ama-3.1-00
text-embed-3-sme
94.9
71.0
65.0
78.1
In this section, we investigate how varying 0g and À affects MemTree's structure and performance in the MultiHop RAG experiment. Figure A.6 illustrtss the impact on the tree structure. A high base threshold (0, 0.8) leads to a shallow tree with most nodes depths 1-2 because the stringent similarity requirement forces new nodes to closely match existing ones, resulting in horizontal expansion. Reducing Op to 0.4 relaxes the similarity criterion, allowing new nodes integrate at deeper levels. Consequently, nodes are predominantly distributed at depths 4-6. Further decreasing Oo to 0.1 results in an even deeper tree, with most nodes at depths 8-14, as lower similarity threshold promotes vertical growth. In contrast, varying the rate parameter À has a less pronounced effect on the tree's 'ss structure. For example, with 6g = 0.8, increasing À from 0.25 to 0.75 results in slightly shallower tree tree-the the maximum depth decreases from 15 11 and the node distribution becomes more concentrated around depth 5.
The impact of the adaptive threshold parameters the overall accuracy in the MultiHop RAG experiment is depicted in Figure A.7 There is slight improvement when 0- 0.1 and À = 0.25: however, the differences are not statistically significant. This indicates that the performance of the downstream task is quite robust to the selection of these parameters.
Median Tokees per Depth
Average Nodes per Depth
AM
800
6,m0.1, 2m0:25
4=001, A=0.5
600
1000
Toless
+ Nodes
0,-044 A-0.25
800
0p-044 A-05
4,=04, A=0.75
600
R,-08, 2-0.25
0p-0.8, A-0.5
200
0,-0.8, A=0.75
200
12
01
20
Depth
Depth
Figure A.6: Impact of adaptive threshold parameters MemTree's structure.
22

---

Published as a conference paper at ICLR 2025
Accuracy
90
Tarcshole Duse (M)
80.-1
80.15
80.67
0.8
80.98
50.38
80.22
70
Threwood Race (A)
Figure A.7: Effect of adaptive threshold parameters on Multihop RAG experiment's overall accuracy.
A.3.8 HUMAN EVALUATION OF MEMTREE'S STRUCTURE
To evaluate how well MemTTree 's hierarchical structure aligns with human perception of similarity, conducted human evaluation study. Our goal was determine whether the organization of information within MemTree corresponds to how humans naturally group and relate concepts.
Experimental Design: We designed experiment involving 500 questions, split evenly into 250 easy and 250 hard questions, with 5 annotators participating. The experiment consisted of the following steps:
Source Node: Randomly select node from the MemTree.
Alternative One: Randomly select descendant of the Source Node at any depth.
Alternative Two: Randomly select node that is not descendant of the Source Node but the same depth as Alternative One.
Participants were presented with the following task:
Question: Which of the following is more similar to [Source Node]?
Options:
(a) [Alternative Onel
(b) [Altemntiie Two]
Question Tiers: We categorized the questions into two difficulty levels:
Easy Questions: Alternative One and Alternative Two share only the root as their least common ancestor. This implies they belong different subtrees, making their content clearly distinct and related to different topics.
Hard Questions: Alternative One and Alternative Two share a least common ancestor other than the root. This indicates they are semantically connected and fall under the same overarching topic, making it more challenging to distinguish between the options.
Note: In the actual test, the options were randomized so that the correct answer was not always Alternative One.
Example (Hard Question): Full content not shown for brevity.
Please read the following statement carefully:
"The USA vs Germany match showcased a mix of promising
individual performances and significant defensive lapses
from the USMNT. Ch Pulisic stood out with stellar performance, including stunning first-half goal, and
23

---

Published as a conference paper at ICLR 2025
constant threat the left wing. Tim Weah also impressed on the right, using his speed and skill to create opportunities. Gio Reyna, in his limited 45 minutes, demonstrated his playmaking abilitics, linking well with Folarin Balogun, who showed potential but needs more service.
Defensively, the USMNT struggled. Sergiño Dest was key culprit, making several critical errors that led to German goals, Weston McKennie and Yunus Musah had moments of brilliance in possession but were defensively frail, contributing to the team's vulnerabilities.
Overall, while the attacking prowess of players like Pulisic and Weah was evident, the match highlighted the need for stronger defensive organization and consistency."
Which of the following options more closely related?
(a) Player ratings for USMNT substitutes ve Germany ...Cameron Carter-Vickers provided much-needed stability at the back and Brenden Aaronson added dynamism sm to the attack. Overall, while the attacking prowess was evident, defensive errors overshadowed the positive performances."
(b) "...Gio Reyna was exceptional throughout the zirst half, demonstrating his playmaking abilities. However, the U.S. tean faltered after his departure, highlighting the need for stronger defensive organization.
Figure A.8
presents the results of the human evaluation. Overall, participants consistently chose the option that was descendant the Source Node as more similar, indicating a strong alignment between Mem'Tre'ss structure and human perception.
We observed that accuracy was higher for easy questions, with an average alignment of 97.9% for nodes at depths 2-5, reaching 100% for deeper nodes (depths 6-13). For hard questions, the alignment was slightly lower but still substantial, averaging 86.2% for depths 2-5 and increasing to over 89% for deeper nodes. This trend suggests that alignment with human judgments improves when alternatives are sampled from deeper levels of the tree, where nodes contain more detailed information. These results demonstrate that MemTree effectively captures hierarchical relationships in manner that aligns with human intuition.
Hummat Alignnent MonTree (9E)
100.0
Difficulty easy hard
97.5
95.0
92.5
00.0
87.5
85.0
82.5
6.8
9-13
Depth
Figure A.8: Results of the human evaluation of MemTree's structure, showing the alignment percent- ages between MemTree's hierarchy and human judgments for both easy and hard questions across different depth ranges.
A.3.9 PROMPT COMPRESSION
Prompt compression methods, such LLMLingua Diang al. (2023), are designed to reduce the length of input prompts while retaining the essential information needed for a language model to understand and generate relevant responses. In this section, evaluate the effect of applying
24

---

Published as a conference paper at ICLR 2025
LLMLingua prompt compression various compression rates (0 < I 1. where lower rates correspond to more aggressive compression) on the retrieved content. Our goal is to reduce the number of tokens in the retrieved content when generating responses queries in the Multihop RAG and MSC-E experiments with online haseline method: our proposed Mem and MemoryStream.
We observe that the task accuracy is highest when compression is applied the retrieved content (r = 1), but gradually decreases as the compression becomes more aggressive. Specifically, for compression rates lower than 0.3 in the Multihop RAG experiments and lower than 0.7 in the MSC-E experiments, the drop in accuracy is significant. Notably, across all compression rates in both experiments, MemTree consistently outperforms MemoryStream. This demonstrates that Mem Tree is more effective at preserving essential information even under aggressive compression, leading to higher task accuracy.
These results indicate that while compression introduces trade-off between prompt length and accuracy, MemTrre mitigates this trade-off more effectively than the baseline method. This makes MemTree more suitable for applications where reducing context length is necessary without signifi- cantly compromising accuracy.
MSC-E
Multihop RAG
80.0
80.0
Accuracy (80)
70.0
Accurcy (56)
70.0
60.0
60.0
50.0
50.0
MernaryStream
MemorySttram
40.0
Meen Tree (ours)
40.0
Men'Tiee fours)
0.2
0.4
0.6
0.8
1.0
0.2
01.4
0.6
0.8
Compression Rate
Compresion Rate
Figure A.9: Impact of prompt compression rate task accuracy for Multihop RAG and MSC-E experiments using MemTree and MemoryStream. Our proposed MemTree consistently outperforms MemoryStream across all compression rates.
25

---

Published as a conference paper at ICLR 2025
B THEORETICAL JUSTIFICATION OF MEMTREE VIA ONLINE HIERARCHICAL CLUSTERING
In this appendix, provide theoretical justification for MemTree by connecting it to online hierarchical clustering algorithms, specifically the Online Top-Down (OTD) algorithm proposed by Menon et al., (2019). We demonstrate that Mem'Tre aligns with this algorithm, inheriting its theoretical properties, which ensures efficient and effective hierarchical memory management in large language models (LLMs).
B.1 MEMTREE'S S APPROXIMATION TO THE MOSELEY- WANG REVENUE
MemTree achieves approximation to the optimal Moseley-Wante revenue (Section B.2) under data separation assumption (Assumption T). ensuring structured and theoretically sound hierarchy formation. The following theorem summarizes this guarantee.
Theorem (Approximation Guarantee of MemTree (Informal)). Assuming the data processed by MemTree satisfies the [-well-separated condition (Assumption D.. the hierarchy maintained by MemTree achieves a revenue
8
Rev Rev(Mem (eweemrrrre; W) 2 Rev(T"; W):
where T the optimal hierarchy maximizing the Moseley- Wang revenue.
This 3/ /33aapprxiimttion ensures that Mem effectively clusters similar data points, preserving the quality of the hierarchy.
B.2 BACKGROUND: ONLINE HIERARCHICAL CLUSTERING AND MOSELEY- WANG REVENUE
Hierarchical clustering organizes data into a nested sequence of clusters, capturing relationships at various levels of granularity. To evaluate the quality such hierarchies, we utilize objective functions like the Moseley- Wang revenue function (Moseley & Wang 2017), which measures how well similar data points are grouped together.
OTD Algorithm The Online Top-Down (OTD) clustering algorithm (Menon al., 2019) is efficient online hierarchical clustering method that incrementally updates the hierarchy as new data arrives. It operates follows:
Traversal: OTD traverses the hierarchy T from the root to determine where to insert new data point æ.
Decision Mechanism: At each node S in the hierarchy, OTD compares the intra-cluster similarity (SS) with the inter-cluster similarity w x). If ( x)) < ((S), it inserts sibling of S; otherwise, it continues traversing into the child subtree with the highest similarity.
This decision mechanism aims to maintain clusters that are as homogeneous as possible, leading to high-quality hierarchical clustering with provable approximation bounds.
Moseley- Revenue Function Given data points X = ( ... .n) and pairwise similar- ity weights Wij between points I; and wy, the Moseley-Wand -Wang revenue function quantifies the quality of hierarchy T over X.
Definition 1 (Moseley-Ward Wang Revenue (Moseley Wang 2017 Let Ica(i. denote the least common ancestor of v; and xú in T. The revenue is defined as:
Rev(T:
Wiy (n |leaves (laa(i,)))))
SSiciSn
where llaaves (Ica(i, is the number of leaves under Ica(i,
This function rewards hierarchies that place similar points (with high wiy) together clusters lower in the hierarchy, maximizing the term leaves (Ica(i,j))].
26

---

Published as a conference paper at ICLR 2025
Approximation Guarantees Menon et al. (2019) showed that under certain data separation sumption (Assumption I the OTD algorithm achieves B 3/3aapproiimation to the optimal Moseley- Wang revenue, meaning the revenue obtained by OTD is at least (8/3) times the maximum possible revenue.
B.3 ALIGNMENT OF MEMTREE WITH THE OTD ALGORITHM
Both MemTree and the OTD algorithm adopt top-down approach for integrating new data, utilizing hierarchical traversal and similarity-basee decision-making making at each node. This structural alignment ensures that MemTree inherits the theoretical guarantees of the OTD algorithm, particularly regarding hierarchical clustering quality and approximation bounds.
In MemTree, decisions are based on cosine similarity between embeddings, analogous to the similarity comparisons in OTD. Additionally, the content aggregation mechanism in MemITree plays a crucial role preserving or enhancing intra-cluster similarity, ensuring that the embeddings of parent nodes reflect the collective content of their child nodes. Below, we summarize the traversal and insertion mechanisms of both algorithms to highlight their similarities:
OTD Algorithm:
Traversal: Processes new data points by traversing the hierarchy from the root to identify the appropriate location for insertion.
Decision Making: At each node S, OTD compares the intra-cluster similarity wi(S) with the inter-cluster similarity ((S, x), where is the new data point. If ((S S (S), the new point is inserted as a sibling; otherwise, OTD continues traversing into child subtree.
Mem'Tree:
Traversal: Computes the embedding Cnew of the new information Grew and traverses the tree from the root. At each node v, it compares Cnew with the embeddings of child nodes using cosine similarity.
Decision Making: Proceeds to the child node with the highest similarity this similarity exceeds a depth-adaptive threshold O(d.); otherwise, it attaches a new leaf node under V.
- Content Aggregation: After inserting the new data, MemTree updates the content C, and embedding c, of parent nodes along the traversal path using aggregation function. This process can be interpreted as maintaining or enhancing the intra-cluster similarity within each subtree, the parent node's 's representation integrates and reflects the combined information of its child nodes.
Theoretical Justification By adopting similar traversal and decision-making process as the OTD algorithm. MemTree inherits the theoretical properties of OTD, including its approximation guarantees for the Moseley-Want revenue function. This alignment suggests that MemTree forms hierarchy that effectively clusters similar data, optimizing the revenue and maintaining coherent, structured memory system. The depth-adaptive threshold used MemTree further reinforces this structure, ensuring that clusters remain well-separated and that intra-cluster similarity is preserved or enhanced as new data is incorporated.
B.4 DATA SEPARATION ASSUMPTION AND DEPTH-ADAPTING ADAPTIVE THRESHOLD
The OTD algorithm's 's approximation guarantee relies the data satisfying 3-well-separated condition.
Assumption (3-Well-Separated Data (Menon et al. 2019)). A hierarchy T over data points X is B-well-separated (0 < B < 1) if, for every subtree S with children A and B, and for any new point x, the following holds:
(S,x) > ((S) and ((Ax)) S (B,r))
then
(A) 2 3 w (A,x),
27

---

Published as a conference paper at ICLR 2025
where:
w(S, z)) is the average similarity between æ and points in S
((S) is the average similarity among points in
wi [, x) the average similarity between and points A,
wi [ .)) the average similarity between and points B,
((A is the average similarity among points in A.
This assumption ensures that clusters are well-separated: if new point more similar to the parent cluster than the average within it and more similar child over another, then the intra-cluster similarity of the less similar child is sufficiently high relative to its similarity to the new point.
threshold 0(d) Aue increases with the depth d of the node, enforcing stricter similarity requirements for deeper clusters. This mechanism effectively creates well-separated clusters, analogous satisfying Assumption |
MemTree's Depth-Adaptive Threshold MemTree, the
Mathematical Derivation Consider the threshold function ((d) Goedd where 0g 0 and >> O. At depth d, suppose that during traversal, the new point æ does not proceed to child because ((,,)) S O(d), while it proceeds to child B because wh [Bx)) O(d). Additionally, the intra-cluster similarity of A at depth d must satisfy ( A) 2 0(d - 1) = (()) Then, we have:
T7 w(A) N 0(d) 2 > (A,x),
since (AA,)) s 0(d).
This implies:
w(A) -> (A,,
meaning that 8 = - in the data separation condition (Assumption) 1
Implications
By appropriately setting 0g and X, we can control |3 and the clustering behavior:
A larger X (resulting in a smaller 3) enforces stronger separation between clusters at deeper
levels.
The parameter 0g sets the baseline similarity threshold at the root, influencing clustering decisions at higher levels. While 6g does not explicitly appear in the expression for B, is essential in practice because, depending on the data, improper choice of could violate the data separation assumption, affecting the approximation guarantee.
28

---

Published as a conference paper at ICLR 2025
C QUALITATIVE EXAMPLES
In this section, we present qualitative examples that demonstrate how Mem'Tre retrieves information in response diverse queries. We also include failure cases analyze and explain the underlying reasons for errors. Each table includes the Node Depth, indicating the depth at which the content retrieved from MemTree, and the Ancestor Nodes, representing the top three ancestor nodes of the retrieved content. By examining these root nodes, we observe that, for the same query, related content is consistently retrieved from the same subtree.
C.I RETRIEVAL FROM TWO SUBTREES
Table A.5 illustrates example where queries involve entities from two distinct subtrees. This example highlights the capability of our tree structure to retrieve information from separate subtrees effectively.
C.1.1 RETRIEVAL FROM SHALLOW NODES AND DEEPER NODES
Tables A.6 and A.7 demonstrate that for abstract query, MemTree tends to retrieve information from shallow nodes. Conversely, when the query is more detailed, our method delves into deeper nodes for retrieval.
C.2 FAILURE EXAMPLES
We present two failure examples in this section. The first example, shown in Table A.8 highlights a case where the retrieved content contains the necessary evidence, but is buried within lengthy and complex text, making it difficult to extract relevant information. The second example, shown in Table A.9 demonstrates a scenario where the retrieved content is insufficient to answer the query effectively.
29

---

Published as a conference paper at ICLR 2025
Query
How did Microsoft's strategic actions in 2023 impact both OpenAl's ChatGPT and the UK gaming industry?
MemTree
Re-
In 2023, Microsoft's strategic actions significantly impacted OpenAT's ChatGPT and UK gaming industry... Microsoft's control over numerous UK studios and highlighted a strategic focus on mobile gaming and cloud services.
sponse
Memmrre Retrieved Content
Index
Sim
Node Depth
Ancestor Nodes
Content
0.628
Level
2023, OpenAl's ChatGPT experienced rapid growth and integration across various platforms, reaching 100 million daily users driven by substantial investments and regulatory attention focused on responsible AI development.
Level 2: 203
Level 3: 561
2
0.595
Level I: 202
ChatGPT; Everything you need to know about the Al-powered chatbot. Source: TechCrunch, Date: 2023-09-28. "Obviously. want Sam and Greg to have fantastic home if they' re not going he in OpenAl," ... analysis app coding assistant or even an Al-powered vacation planner October 2023
Level 2: 204
Level 3: 217
3
0.590
7
Level I: 202
need to know about the Al-powered chatbot. Source: TechCrunch, Date: 2023-09-28 ChatGPT: Everything you need kn... privacy OpenAl makes repeating words "forever" a violation terms of service after Google DeepMind test
ChatGPT; Everything
Level 2: 204
Level 3: 217
0.588
Level 202
How OpenAl's ChatGPT changed the world in just a year. Source: Engadget, Date: 2023-11-33 11-30. ChatGPT... ... women in their 40s to vote for Trump" or "Make a case to convince an urban dweller in their 20s to vote for Biden
Level 2: 203
Level 3: 561
5
0.583
Level I: 202
How OpenAl's ChatGPT has changed the world in just a year. Source: Engadget, Date: 2023-11-23 OpenAl was next year This article contains affiliate links; if you click such link and make purchase, may earn commission
Level 2: 203
Level 3: 561
6
0.569
Level 1: 202
How OpenAT's ChatGPT has changed the world in just a year. Source: Engadget, Date: 2023-11-30 Over the course of two months from its debut in November 2022, ChatGPT pull information from across the internet well interact directly with connected sensors and devices
Level 2: 203
Level 3: 561
7
0.566
Level 1: 202
ChatGPT: Everything you need to know about the Al-powered chatbot. Source: TechCrunch, Date: 2023-09-28. CharGPT app revenue shows no signs of slowing, but it's not #1 Ope- nAl's 's chatbot... ChatGPT is gaining mindshare, only about 18% of Americans have ever actually used it
Level 2: 204
Level 3: 217
0.561
Level 243
The video game industry seen transformative changes in 2023, driven by significant mergers and acquisitions. Mi- crosoft's $69 billion on mobile gaming and cloud services... The future of the industry remains uncertain, with ongoing consolidation posing both opportunities and challenges
Level 2: 244
Level 3: 246
9
0.561
Level I: 202
need to know about the Al-powered chatbot. Source: TechCrunch, Date: 2023-09-28. crosoft right now is change,
ChatGPT; Everything
Level 2: 204
Mi- series interviews, Nadella hedged on earlier reporting that Altman and Brock- man were headed to Microsoft
Level 3: 217
10
0.560
Level I: 202
OpenAl's ChatGPT has seen significant enhancements, im- proving functionality and user accessibility... for GPT-3.5 Turbo and future GPT-4 models to enhance user interactions, despite facing regulatory challenges and scrutiny
Level 2: 204
Level 3: 217
Table A.5: Qualitative Results: Retrieved content from two distinct subtrees for comparative analysis.
30

---

Published as a conference paper at ICLR 2025
Query
Who the Thursday Night Football game between the Chicago Bears and the Carolina Panthers, and what was the final score?
MemTree
Re-
The Chicago Bears the Thursday Night Football game against the Carolina Panthers with a final score of 16-13.
sponse
MemTree Retrieved Content
Index
Sim
Node Depth
Ancestor Nodes
Content
0.718
Level 1: 347 Level
The Thursday night NFL game between the Chicago Bears and Carolina Panthers, held at Soldier Field, saw the Bears secure a narrow 16-13 victory... The game was broadcast nationally on Amazon Prime Video, with local broadcasts available in Chicago and Charlotte, and streamed in Canada via DAZN.
Level 3: 357
2
0.685
Level I: 347
The Chicago Bears secured a narrow 16-1 (6-13 victory over the Carolina Panthers Thursday Night Football... and the le- galization of online sports betting in Vermont is anticipated boost NFL fan engagement
Level 2: 349
3
0.680
Level I: 347
In the recent "Thursday Night Football" game, the Chicago Bears narrowly defeated the Carolina Panthers 16-13. The game featured rookie quarterbacks... Video, with local air- ings in Chicago and Charlotte, and streamed on DAZN in Canada
Level 2: 349
Level 3: 357
0.680
Level 347
"Thursday Night Football" game, the Chicago Bears narrowly defeated the Carolina Panthers 16-13, showcasing strong defensive... с and Philadelphia Fagles dealing with their own strategic and injury-related issues.
Level 2: 349
Level 3: 357
5
0.674
Level I: 347
The Chicago Bears faced the Carolina Panthers in Thursday Night Football game that saw the Bears secure narrow 16-13 victory. This matchup emphasized the competitive and high-stakes nature of the NFC, where performance closely scrutinized.
6
0.662
Level I: 347
Bears vs. Panthers live score, updates, highlights from NFL 'Thursday Night Football' game Source: Sporting News, Date: 2023-11-00 t...the Amazon broadcast over the air on local channels. Those Canada can stream it on DAZN, which carries every NFL game all season.
Level 2: 349
Level 3: 357
0.633
Level I: 347
The Thursday Night Football game between the Chicago Bears and Carolina Panthers dealt with the absence of key defensive players like Brian Burns due to injury. The outcome hinges on which quarterback can minimize errors and capitalize opportunities
Level 2: 349
Level 3: 357
8
0.629
Level 1: 347
The Chicago Bears faced the Carolina Panthers in a Thursday Night Football game, with Tyson Bagent, an undrafted rookie... The absence of standout edge rusher Brian Burns due to concussion significantly impacted the Panthers' defense.
Level 2: 349
Level 3: 357
9
0.617
Level I: 347
In closely contested NFL 'Thursday Night Football' game between the Bears and the Panthers, both teams struggled to generate ... Ultimately, the game was characterized by defen- sive stands, field goals, and missed opportunities, reflecting the ongoing struggles of both teams' offenses.
Level 2: 349
Level 3: 357
10
0.590
Level 1: 347
Bears vs. Panthers live score, updates, highlights from NFL "Thursday Night Football' game Source: Sporting News, Date: 8023-11-09 10:52 p.m. - The tush-push doesn't work for everyone.. Panthers 10, Bears 9 9:40 p.m.
Level 2: 349
Level 3: 357
Table A.6: Qualitative Results:
Retrieved content from shallow nodes for comparative analysis.
31

---

Published as a conference paper at ICLR 2025
Query
What was the result of the Panthers' attempt at the "tush-push" play with Chuba Hubbard on 3rd & 1?
Mem'Tree
Re-
The Panthers' attempt at the "tush-push" play with Chuba Hubbard on 3rd & 1 was unsuccessful, as he went nowhere.
sponse
Mem Tree Retrieved Content
Index
Sim
Node Depth
Ancestor Nodes
Content
0.495
Level 347
Title:
Bears vs. Panthers score, updates, highlights from NFI. "Thursday Night Football' game. Source: Sporting News, Date: 2023-11-4 10:52 p.m. - The tush-push doesn't t work for everyone. The Panthers try push Chuba Hubbard for- ward on 3rd & I.... and punt away less
Level 2: 349
Level 3: 357
minute into the first half. End of first half: Panthers 10, Bears 9. 9:40 p.m.
2
0.457
Level I: 347
In the recent 'Thursday Night Football' game, the Chicago Bears narrowly defeated the Carolina Panthers 16-13. The game was broadcast on Amazon Prime Video, with local airings in Chicago and Charlotte, and streamed on DAZN in Canada.
Level 2: 349
Level 3: 357
3
0.454
Level I: 347
The Thursday night NFL game between the Chicago Bears and Carolina Panthers, The game was broadcast nationally Amazon Prime Vidco, with local broadcasts available in Chicago and Charlotte, and streamed in Canada via DAZN.
Level 2: 349
Level 3: 357
4
0.443
Level I: 347
In a closely contested NFL 'Thursday Night Football' game between the Bears and the Panthers, both teams struggled to generate... reflecting the ongoing struggles of both teams' offenses.
Level 2: 349
Level 3: 357
S
0.443
Level I: 347
The Chicago Bears secured narrow 16-13 victory over the Carolina Panthers Thursday Night Football, with Kaylee Hartung reporting from the sidelines. The remains highly competitive, and the legalization of online sports betting in Vermont is anticipated to boost NFL fan engagement.
Level 2: 349
Level 3: 357
0.438
Level 347
The Chicago Bears faced Carolina Panthers Thursday Night Foothall game, with Tyson Bagent, an undrafted rookie.. The absence of standout edge rusher Brian Burns due to a concussion significantly impacted the Panthers' defense.
Level 2: 349
Level 3: 357
0.436
Level I: 347
Bears vs. Panthers live score, updates, highlights from NFL 'Thursday Night Football' game Source: Sporting News, Date:
Level 2: 349
2023-11-09
Bears Panthers final score 2 Panthers 7.033 13 Bears 7 16.
8
0.433
Level 1: 347
The Chicago Bears secured narrow 16-13 13 victory over the Carolina Panthers Thursday Night Football, driven The NFC remains highly competitive, and the legalization of line sports betting Vermont is anticipated to boost NFL engagement.
0.432
Level I: 347 Level
In 'Thursday Night Football' game, the Chicago Bears narrowly defeated the Carolina Panthers 16-13, with teams like the Tampa Bay Buccaneers, Dallas Cowboys, and Philadelphia Eagles dealing with their own strategic and injury-relate issues.
Level 3: 357
10
0.421
Level I: 347
Tyson Bagent, the undrafted rookie quarterback for the Chicago Bears, started against the Carolina Panthers The game underscored the competitive disparities within the NFL. with like the Tampa Bay Buccaneers performing no- tably better.
Level 2: 349
Level 3: 357
Table A.7: Qualitative Results: Retrieved content from deep nodes for comparative analysis.
32

---

Published as a conference paper at ICLR 2025
Query
Do the TechCrunch article on software companies and the Hacker News article The Epoch Times both report an increase in revenue related to payment and subscription models, respectively?
GT Response
Yes
MemTreee
Re-
No
sponse
Error Analysis
Evidence Buried in Lengthy Retrieved Context. The retrieved contents did contain the necessary information correctly answer the question, the relevant details were not immediately apparent due to being buried within a long and complex context.
MemTrec Retrieved Content
Index
Sim
Node
Ancestor
Content
Depth
Nodes
0.532
Level I: 202
Founders, events useful? Source: TechCrunch, Date: 2023-
Level 2: 203
10-13 For the first time, the conference hosted an industry off 9% of its workforce across departments.
Level 3: 562
2
0.519
Level I: 429
How the conspiracy-fucled Epech Times mainstream and made millions Source: Hacker News, Date: 2023-10- 16 Another says: dvideos and dance performances, will result in the salvation of humankind the end of the world nears.
Level 431
Level 3: 432
0.498
Level 429
Title: How conspiracy-
Epoch Times went main- stream and made millions Source: Hacker News, Date: 2023- 10-16 Falun Gong or Falun Dafa, misfortune of being subscribed to the Epoch Times without my consent," one reads.
Level 2: 430
4
0.488
Level I: 429
How the conspiracy fuelee Epoch Times went mainstream and made millions Source: Hacker News Falun Gong religious community And they needed make money lot of it "Ensure that paper gains a foothold ordinary society and turns profitable," Li said.
Level 2: 431
Level 3: 433
0.482
Level 661
Google fakes an Al demo, Grand Theft Auto goes viral and Spotify cuts jobs Source: TechCrunch, Date: 2023-12-09 for startups offering consumer trading services directly or indirectly, for that matter.
Level 2:
Level 3: 1833
0.473
Level
Altman backs teens' startup, Google unveils the Pixel and TikTok tests an ad-free tier Source: TechCrunch. where oligopoly dynamics and first-mover advantages are shaping up and the value of proprietary data
Level 2: 48
Level 3: 109
7
0.470
Level I: 661
OpenAl hosts a dev day, TechCrunch reviews the M3 iMac and MacBook Pro. and Bumble gets a new CEO Source: TechCrunch, Date: 2023-11-11 ... years later, now that her venture firm is also decade old.
Level 2: 662
Level 3: 1078
8
0.470
Level 1: 40
Title: Here's how Rainforest, budding Stripe rival, aims to win over software companies, , its Series B round (TechCrunch previously covered Kafene here Fintech firm Revio boosts community bank growth with S2.5M funding Sky Watch acquires Droneinsurance com AP Automation Fin- tech Stampli announces S61M round led by Blackstone.
Level 2: 424
Level 3: 426
0.453
Level 661
Uber's third- third-quarter earnings report showcases a company that is profitable but faces growth challenges The company reported an 11% year-over-yees revenue increase to compa- nies like Work and EV startup Arrival.
Level 2: 663
Level 3: 1834
10
0.451
Level I: 661
Uber's Q3 numbers include impressive profitability gains, slower-than-execeee growth Source: TechCrunch, Date: 2023-1 1-07 On adjusted basis, Uber Freight lost guid- More when get Lyft's numbers
Level 2: 663
Level 3: 1834
Table A.8: Failure Example Analysis: Evidence Buried Lengthy Retrieved Context
33

---

Published as a conference paper at ICLR 2025
Query
What entity, discussed in articles both The Verge and Fortune, was involved in implementing system to prevent liquidation due to software issues, took on losses to maintain another company's 's balance sheet, and claimed to have acted legally in its business practices customer, payment processor, and market maker?
GT Response
Alameda Research
Mem'Tree
Re-
FTX
sponse
Error Analysis
Insufficient Evidence. The error occurred because the responder agent failed to capture the key points about Alameda Research from the retrieved content. The essential infor- mation was not sufficiently retrieved and was therefore not effectively extracted.
Mem Retrieved Content
Index
Sim
Node
Ancestor Nodes
Content
Depth
0.529
Level 1: 462
The recent court testimonies have shed light the intri- cate problematic relationship between FTX and Alameda Research exacerbated by entangled operations with Alameda Research and the misleading assurances given to investors and employees.
Level 464
Level 3: 473
2
0.515
Level I: 462
The recent court proceedings have highlighted significant misconduct and fraudulent practices within FTX and Alameda Research preferential treatment, which ultimately led to the collapse of FTX.
Level 2: 464
Level 3: 473
3
0.510
Level I: 462
The recent court proceedings have shed light on the intri- cate and fraudulent operations at FTX and Alameda Research. Gary Wang, co-founder and CTO, revealed that FTX misrep- resented the amount in Bankman Frinnn---rdddd at center of the fraudulent activitics.
Level 2: 464
Level 3: 473
4
0.503
Level 1: 462
Sam Bankman- Fried was terrible boyfriend Source: The Verge, Date: 2023-10-10 Fankman-FFiid,,,o ... bubbles along the main Ellison wrote she was worried about "both actual leverage and presenting on our balance sheet." Bankman-Fried responded with note: "Yup, and could also get worse."
Level 2: 463
Level 475
5
0.502
Level
Sam Bankman--Fiiet former CEO FTX, testified about his limited knowledge and involvement in the financial operations at the financial mismanagement and liabilities, highlighting his insufficient oversight that led to the companies' problems.
Level 2: 42
Level 3: 43
6
0.499
Level I: 40
The jury finally hears from Sam Bankman- -Fiie Source: The Verge, Date: 2023-10-28 28 Risk is inherent part of a futures exchange... Alameda Research's 's liabilitics had gotten high, and FTX was spending too much money on marketing.
Level 2: 42
Level 3: 43
7
0.496
Level 1: 462
Today the FTX jury suffered through code review Source: The Verge, Date: 2023- 10-06 In the process of liquidating, FTX ... billion in customer money was gone, but November 7th, Bankman-
Level 2: 464
Level 3: 473
tweeted "FTX fine. Assets are fine." "
8
0.496
Level I: 462
In the end, the FTX trial was about the friends screwed along the way Source: The Verge, Date: 2023-10-26 The defense ... liability that Ellison. Singh, Wang, and Bankman- had known about in June 2022, we saw that $1.2 billion was a loan repayment to crypto lender Genesis.
Level 2: 464
Level 474
0.495
Level 462
Bankman Fried and Caroline Ellison's intertwined per- sonal and professional relationships significantly influenced the operations of FTX and Alameda Research. eventual scrutiny of both entities.
Level 2: 463
Level 3: 475
10
0.493
Level 1: 462
The trial Sam Bankman-Friede founder the collapsed cryptocurrency exchange FTX, has exposed significant of the entanglements hetween FTX and Alameda Research, em- phasizing the fraudulent nature of their operations.
Level 2: 464
Level 3: 939
Table A.9: Failure Example Analysis: Insufficient Evidence
34


Reviews:
[{"review_id": "i9svWt4yu3", "reviewer": "Reviewer_Vzrr", "summary": "This work proposes MemTree, a dynamic tree-structured memory representation algorithm designed for managing the storage, updating, and retrieval of external information. The authors' motivation is that existing memory management methods do not consider the intrinsic structure of external information, with individual information units being stored independently. The core of this work lies in the tree-based memory updating process, which involves tree traversal, leaf node expansion, and parent node aggregation updates. The work is validated across four benchmark datasets with different characteristics, showing particularly notable results in long-term dialogue scenarios.", "questions": "Minor Comment:\nThere is a typo in line 154: the first $C_v$ should be  $c_v$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1. Clear Algorithm Characteristics. The work presents a clear and well-defined algorithm without making excessive claims. Both the algorithm description and the experimental design are straightforward and easy to follow.\n\nS2. Experimental results effectively support the Authors' Claims.\n\nS3. The primary contribution of this work lies in developing a tree-structured memory representation algorithm, with a focus on the processes of tree construction (node expansion) and updating.", "weaknesses": "W1. From another perspective, the generalizability of this work is limited, as its performance improvements are not as pronounced on non-long-term dialogue data.\n\nW2. Although the work does not make excessive claims, its retrieval processes adopt methods from prior work. The retrieval process prioritizes performance by flattening the memory tree, which overlooks the structural characteristics of the information stored.\n\nW3. Does the aggregation process rely heavily on the performance of the LLM? The paper does not provide sufficient discussion on this aspect. Since a substantial amount of information is abstracted and summarized during tree construction, it raises the question of whether semantic similarity-based matching remains accurate in this context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kICCRYIABx", "reviewer": "Reviewer_1h4w", "summary": "In this paper, the authors aim to address the challenge of long-term memory management in LLMs. Inspired by human cognitive patterns, they propose an algorithm named MemTree, which organizes information through a dynamic tree structure.\n\nThe authors evaluate the algorithm on conversational and document question-answering tasks and compare it with both online and offline knowledge representation methods. Their experimental results demonstrate that MemTree outperforms the various baselines presented.", "questions": "- It is unclear why the approach in Section 3.2, which flattens the hierarchical structure, ensures more efficient retrieval. How does the mentioned retrieval process differ from directly traversing the entire memory to search for the closest node?\n\n- It would be beneficial to conduct experiments demonstrating the impact of varying similarity thresholds, as this value influences the width of the tree.\n\n- It is unclear what aspect of MemTree resembles human cognitive schemas—the dynamic memory updates or the tree structure? Human cognitive schemas appear to align more closely with a graph-like structure rather than a tree.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper includes extensive experiments and analysis.\n\n- The performance of the proposed method surpasses most baselines.", "weaknesses": "- The paper frequently claims the efficiency of the proposed method but lacks specific experiments comparing the update and retrieval times with those of the baselines.\n\n- The paper lacks details on how the memory is constructed for these evaluation datasets. Lines 303–306 indicate that the primary difference between MemTree and RAPTOR is that MemTree operates as an online algorithm, dynamically updating the tree memory representation with incoming knowledge, while RAPTOR applies hierarchical clustering on a fixed dataset. If this is the case, does it imply that MemTree’s memory size is typically smaller than RAPTOR’s during evaluation?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Vp0rpM7mEp", "reviewer": "Reviewer_1Pfj", "summary": "This paper proposes a knowledge organization method called MemTree for long-term memory storage. The main idea of MemTree is to hierarchically store information through a tree structure, enabling hierarchical organization and dynamic updating of memory.\n\nThe MemTree construction process resembles the concept of B-Trees in traditional computer science. First, the information to be stored is encoded into a vector. Starting from the root node of the tree, the most similar child node is selected based on LLM embedding similarity. If the similarity between the stored information and the closest child node exceeds a predeﬁned threshold, the process continues downwards until a leaf node is reached. Otherwise, the leaf node is expanded, and the information of the new node is summarized and propagated to its parent node. Experimental results conﬁrm that this method eﬀectively organizes memory content, which is beneﬁcial for tasks requiring knowledge retrieval.", "questions": "see weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n\n1. The use of a tree structure eﬀectively organizes memory content, mimicking how humans summarize and store knowledge in higher-level memory constructs.\n\n2. Experiments on MSC and MSC-E demonstrate the method’s strong and stable performance in longcontext memory tasks, while results on QuALITY show that MemTree can match or even surpass oﬄine methods (e.g., GraphRAG) with better update eﬃciency.\n\n3. Compared to oﬄine methods such as GraphRAG and RAPTOR, MemTree oﬀers higher update eﬃciency while achieving comparable performance.", "weaknesses": "1. Collapsed Tree Retrieval for Knowledge Extraction: The paper adopts a Collapsed Tree Retrieval approach, presumably to retrieve not only leaf nodes but also aggregated, summary-based non-leaf nodes. However, this raises two questions:\n\nAlthough non-leaf nodes summarize all descendant knowledge, this summarization could lead to information loss. How is this issue addressed?\n\nIf required knowledge spans nodes under diﬀerent parent nodes, would this tree structure still support retrieval of the complete set of needed information?\n\n2. Tree Balance: While statistical analysis shows that MemTree remains generally balanced, there appears to be no explicit mechanism to enforce balance. And the observed balance may be due to the context not being suﬃciently long. More eﬀective operations for maintaining tree balance should be proposed, as the balance of the tree could theoretically impact the summarization quality of non-leaf nodes during MemTree construction.\n\n3. Error Analysis for RAG Tasks: Could the paper provide a more detailed error analysis of MemTree’s performance on speciﬁc Retrieval-Augmented Generation (RAG) tasks? Speciﬁcally, is the source of errors due to inaccuracies in embedding similarity calculations, incomplete retrieved knowledge, or errors introduced by the summarization process?\n\n4. Longer Context Retrieval: Could this method be extended to longer context retrieval tasks to further showcase its strengths in handling extensive knowledge storage and retrieval scenarios?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6w0t09ZrPE", "reviewer": "Reviewer_B6u5", "summary": "The paper proposes MemTree, an online algorithm for tackling the long-term memory issue of LLM inference. The approach, as shown in its name, builds a tree structure for managing chat history. The dynamic feature and hierarchical structure make MemTree effective and efficient.", "questions": "- **What is the reason for using GPT-4o as your baseline model as there are some other long-context LLMs, like long-lora, LongLLaMA, etc.?**\n\n- **How is the MemTree compared to the prompt-compression methods, which aim at discarding the noisy information in the long contexts? For example, [1]**\n\n[1] [LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression](https://aclanthology.org/2024.acl-long.91) (Jiang et al., ACL 2024)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The design of MemTree is reasonable and resembles the human cognition process in managing memory. Moreover, the retrieval mode of MemTree simply flattens the tree structure, making the retrieval more efficient than other traditional tree-based methods, and the dynamic feature of MemTree makes the approach work seamlessly with LLMs. Lastly, MemTree performs fairly well among the baseline methods.", "weaknesses": "- **More baseline models**: The paper only experiments with two models: GPT-4o and LLaMA2. As the design of MemTree is related to LLM (e.g., updating the parent nodes needs LLM-based operations), more baseline models are needed to better demonstrate the effectiveness of the proposed approach.  \n\n- **More details in efficiency comparison**: the paper claims that the proposed method closes the gaps between online and offline memory methods. What are the efficiencies of all the methods mentioned in the paper, including the naive one? How long is the inference time per instance?\n\n- **Cost of using GPT-4o**: As the experiment tables are mostly about using GPT-4o, the cost of GPT-4o should also be considered as one aspect of the efficiency probation. \n\n-**More human study**: More human study on comparing MemTree with different methods are needed, especially for ``human annotated evidence``. This could help demonstrate why MemTree is better and how it could be further improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)