Toward a Theory of Hierarchical Memory for Language Agents

Yashar Talebirad, Ali Parsaee, Csongor Y. Szepesvari, Amirhossein Nadiri, Osmar Zaiane · 2026

Read Toward a Theory of Hierarchical Memory for Language Agents by Yashar Talebirad, Ali Parsaee, Csongor Y. Szepesvari, Amirhossein Nadiri, Osmar Zaiane (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21564.txt.

Introduction

Talebirad and co-authors propose a shared theory for hierarchical memory in language agents. Many systems already split memory into extracted units, grouped summaries, and budget-aware retrieval, but designs are hard to compare. The theory uses three operators: extraction, coarsening, and traversal. Coarsening groups units and assigns each group a representative, whose self-sufficiency can vary along a spectrum. They show this choice constrains which retrieval strategies can work. They then map eleven existing systems, from document hierarchies to agent traces, onto the same three operators.

Catalog record

CREATORYashar Talebirad, Ali Parsaee, Csongor Y. Szepesvari, Amirhossein Nadiri, Osmar Zaiane
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30322
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.21564

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Toward a Theory of Hierarchical Memory for Language Agents Yashar Talebirad, Ali Parsaee, Csongor Y. Szepesvari, Amirhossein Nadiri, Osmar Zaiane Abstract Many recent long-context and agentic systems address context-length limitations by adding hierarchical memory : they extract atomic units from raw data, build multi-level representatives by grouping and compression, and traverse this structure to retrieve content under a token budget. Despite recurring implementations, there is no shared formalism for comparing design choices. We propose a unifying theory in terms of three operators. Extraction ( α \alpha ) maps raw data to atomic information units; coarsening ( C = ( π , ρ ) C=(\pi,\rho) ) partitions units and assigns a representative to each group; and traversal ( τ \tau ) selects which units to include in context given a query and budget. We identify a self-sufficiency spectrum for the representative function ρ \rho and show how it constrains viable retrieval strategies (a coarsening-traversal coupling ). Finally, we instantiate the decomposition on eleven existing systems spanning document hierarchies, conversational memory, and agent execution traces, showcasing its generality. 1 Introduction Language agents increasingly rely on large external corpora and long interaction histories, but larger context windows do not reliably improve information use. Models underweight mid-context evidence ( 7 ) , struggle with single-fact retrieval in long documents ( 4 ) , and often degrade as context grows (“context dilution”/“context rot”). This reveals a gap between capacity (more tokens) and control (what to surface, and when). Hierarchical memory is a recurring response: RAPTOR ( 10 ) , GraphRAG ( 3 ) , xMemory ( 5 ) , H-MEM ( 12 ) , and SimpleMem ( 6 ) build multi-level representations by grouping, compressing, and selectively expanding under a budget; analogous ideas appear in agent execution-trace memory, including reasoning-focused traces (MemoBrain ( 8 ) , StackPlanner ( 19 ) ) and action/state traces (InfiAgent ( 15 ) ). Yet these systems are usually presented as isolated design points, making it hard to compare assumptions. We show that, every hierarchical memory system, whether it operates on stored knowledge or live agent execution traces, instantiates a single three-operator pipeline (Figure 1 ). Extraction ( \alpha ) maps raw data to a graph of atomic information units. Coarsening ( C=(\pi,\rho) ) partitions units into groups and produces a representative for each group, yielding a smaller graph, and iterating this produces the hierarchy. Traversal ( \tau ) takes the hierarchy, a query, and token budget, and returns a subset of atomic units to include in context. The central theoretical observation is that the representative function \rho varies along a self-sufficiency spectrum: a detailed summary preserves most of the group’s information, while a category label preserves almost none. This property constrains which retrieval strategy works. Self-sufficient representatives support collapsed search over all levels (RAPTOR), while referential representatives require top-down refinement (H-MEM, xMemory). We call this constraint the coarsening-traversal (C–T) coupling. Prior efforts classify memory systems but do not formalize hierarchy construction. CoALA ( 11 ) organizes memory by cognitive type (working, episodic, semantic, procedural), and MemEngine ( 20 ) implements multiple systems from shared primitives. We provide a mathematical unification, extended to agent execution traces: a formal (\alpha,C,\tau) decomposition with information monotonicity, a self-sufficiency spectrum with C–T coupling, and an instantiation of this decomposition across eleven data and trace systems. Figure 1: The (\alpha,C,\tau) pipeline: D is extracted ( \alpha ) into atoms G_{0} ; coarsening C_{1},C_{2},C_{3} yields layers G_{1},G_{2},G_{3} ; traversal \tau takes a query and budget and returns a subset S of atoms. 2 The Framework 2.1 Core Definitions Natural language exhibits multiscale structure (themes, topics, individual facts), and queries may target any scale. We define three operators that build multiresolution representations of this structure. Information units. Let \mathcal{F}=\mathcal{F}_{1}\times\cdots\times\mathcal{F}_{p} be a product of feature spaces with one distinguished factor \mathcal{F}_{c}=\Sigma^{*} (text). A unit u\in\mathcal{F} has projections \phi_{i}(u) ; \phi_{c}(u) is the content. Typical attributes include embeddings \phi_{\mathrm{emb}} , timestamps \phi_{\mathrm{time}} , entities \phi_{\mathrm{ent}} , and structural paths \phi_{\mathrm{path}} . Unit graph. G=(U,E) with U a finite set of units and E\subseteq U\times U . The edge set may be empty (a flat bag of units, as in SimpleMem), may encode entity-entity relationships (a knowledge graph, as in GraphRAG), or may encode sequential adjacency (a conversation stream, as in xMemory). Extraction. The first operator maps raw data into structured units. \alpha:\mathcal{D}\to\mathcal{G} maps raw data D to a unit graph G_{0}=(U_{0},E_{0}) . All preprocessing (chunking, named entity recognition, path assignment) happens inside \alpha , and thus, each unit is self-contained in the resulting graph G_{0} . Coarsening. A coarsening operator on G=(U,E) is C=(\pi,\rho) : (i) \pi:U\twoheadrightarrow[m] is a surjective grouping that induces the partition \{G_{j}=\pi^{-1}(j)\} ; (ii) \rho:2^{U}\to\mathcal{F} is a representative function such that \rho(G_{j})\in\mathcal{F} . We assume |U^{\prime}|=m<|U| , where U^{\prime}=\{\rho(G_{j}):j\in[m]\} . 1 1 1 Some systems (RAPTOR’s GMM soft clustering, overlapping community detection) allow a unit to belong to multiple groups, replacing \pi:U\to[m] with \pi:U\to 2^{[m]}\setminus\emptyset ; the hierarchy then becomes a DAG. Hierarchy. Iterating C_{i} produces a hierarchy \mathcal{H}=(G_{0},C_{1},\ldots,C_{L}) with G_{\ell}=C_{\ell}(G_{\ell-1}) . 2 2 2 \mathcal{H} lists the initial graph G_{0} and the coarsening operators ; the graphs G_{1},\ldots,G_{L} are the results of applying them, not separate entries in the tuple. The “layers” in the multi-level view are these derived graphs. Denote the node set of G_{\ell} as V_{\ell} . Level 0 is thus the atom set V_{0} ; each application of C_{\ell} builds the next layer V_{\ell} from V_{\ell-1} by grouping nodes (via \pi_{\ell} ) and assigning one representative per group (via \rho_{\ell} ), with edges from each representative to its children. The hierarchy can thus be viewed as a multi-layer graph: the bottom layer holds fine-grained units, and each higher layer is a coarsened graph whose nodes summarize the subgraph below (Figure 1 ). Each C_{\ell} may use a different grouping and representative strategy (e.g., xMemory uses temporal grouping at level 1, semantic grouping at level 2, and thematic grouping at level 3). 2.2 Multi-Resolution Representation Assume the input data D is drawn from a distribution over \mathcal{D} . Since V_{0}=\alpha(D) and each V_{\ell}=C_{\ell}(V_{\ell-1}) , every level inherits randomness from D , and the entropies below are well defined. Let \mathcal{H}=(G_{0},C_{1},\ldots,C_{L}) , and assume each C_{\ell} is deterministic and information-losing with positive probability under D (equivalently, not almost surely invertible). Then: (i) H(V_{0})>H(V_{1})>\cdots>H(V_{L}) , since determinism gives H(V_{\ell})\leq H(V_{\ell-1}) and strict information loss on a nonzero-probability set makes the inequality strict; (ii) for any query variable Q with query-agnostic coarsening (i.e., V_{\ell} depends only on V_{\ell-1} and not on Q ), I(Q;V_{0})\geq I(Q;V_{1})\geq\cdots\geq I(Q;V_{L}) , since learning V_{\ell} provides no additional information about Q once V_{\ell-1} is known; equivalently, Q – V_{\ell-1} – V_{\ell} forms a Markov chain (and the Data Processing Inequality applies). This formalizes that every coarsening step loses information. 3 3 3 This also aligns with the Information Bottleneck principle ( 14 ) : as compression becomes more aggressive at each level of \mathcal{H} , representations move along a trade-off curve between retained detail and compactness, suggesting a multi-resolution structure. The atoms V_{0} set the information ceiling; finer extraction increases H(V_{0}) and raises the ceiling on downstream retrieval quality. 4 4 4 Appendix B relates data size, context window, and

Read the complete text