[2603.21564] Toward a Theory of Hierarchical Memory for Language Agents

Computer Science > Information Retrieval arXiv:2603.21564 (cs) [Submitted on 23 Mar 2026] Title:Toward a Theory of Hierarchical Memory for Language Agents Authors:Yashar Talebirad, Ali Parsaee, Csongor Y. Szepesvari, Amirhossein Nadiri, Osmar Zaiane View a PDF of the paper titled Toward a Theory of Hierarchical Memory for Language Agents, by Yashar Talebirad and 4 other authors View PDF HTML (experimental) 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 = (\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. Subjects: Information Retrieval (cs.IR); Artif...