Temporal Order Matters for Agentic Memory: Segment Trees for Long-Horizon Agents

• URL: http://arxiv.org/abs/2606.04555v1
• Date: Wed, 03 Jun 2026 07:42:15 GMT
• Title: Temporal Order Matters for Agentic Memory: Segment Trees for Long-Horizon Agents
• Abstract summary: SegTreeMem represents conversation history as a temporally ordered Segment Tree over utterances.<n>For retrieval, SegTreeMem propagates relevance scores through the tree to combine local semantic matching with hierarchical temporal context.<n>Additional temporal-order permutation analysis shows that the performance gain depends on preserving temporal order during memory construction.
• Score: 20.461904943047468
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Long-horizon conversational agents need to interact with users through evolving events, tasks, and goals. Such histories are naturally temporal, yet many existing memory systems organize information primarily by topical similarity and may ignore the order in which events occur. We introduce Segment Tree Memory, or SegTreeMem, a memory architecture that represents conversation history as a temporally ordered Segment Tree over utterances. SegTreeMem incrementally inserts new utterances through an online rightmost-frontier update rule, preserving chronological order while forming hierarchical memory segments. For retrieval, SegTreeMem propagates relevance scores through the tree to combine local semantic matching with hierarchical temporal context. Across three long-horizon memory benchmarks and two LLM backbones, SegTreeMem improves answer quality over flat retrieval, graph-structured memory, and tree-structured memory baselines. Additional temporal-order permutation analysis shows that the performance gain depends on preserving temporal order during memory construction, supporting the claim that temporal order is a key structure for agentic memory.

Related papers

• MRMS: A Multi-Resolution Memory Substrate for Long-Lived AI Agents [2.808851478009314]
  Long-lived AI agents require continuity across interactions.<n> Continuity cannot be obtained by simply extending the prompt window.<n>We propose an architectural memory substrate organized along two axes.
  arXiv  Detail & Related papers  (2026-07-06T02:54:37Z)
• Memory is Reconstructed, Not Retrieved: Graph Memory for LLM Agents [51.30250860677378]
  We propose MRAgent, a framework that combines an associative memory graph with an active reconstruction mechanism.<n>Running on a Cue-Tag-Content graph, our active reconstruction mechanism integrates reasoning directly into memory access.<n>Experiments on the LoCoMo benchmark and LongMemEval benchmark demonstrate significant improvements over strong baselines.
  arXiv  Detail & Related papers  (2026-06-04T11:29:46Z)
• StructMem: Structured Memory for Long-Horizon Behavior in LLMs [32.74072149174656]
  StructMem is a structure-enriched hierarchical memory framework that preserves event-level bindings and induces cross-event connections.<n>By temporally anchoring dual perspectives and performing periodic semantic consolidation, StructMem improves temporal reasoning and multi-hop performance on textttLoCoMo, while substantially reducing token usage, API calls, and runtime.
  arXiv  Detail & Related papers  (2026-04-23T14:57:23Z)
• MemSearch-o1: Empowering Large Language Models with Reasoning-Aligned Memory Growth in Agentic Search [59.98962867649009]
  We propose MemSearch-o1, an agentic search framework built on reasoning-aligned memory growth and retracing.<n>MemSearch-o1 grows fine-grained memory fragments from memory seed tokens from queries, then retraces and deeply refines the memory via a contribution function, and finally reorganizes a globally connected memory path.
  arXiv  Detail & Related papers  (2026-04-19T05:35:06Z)
• AdaMem: Adaptive User-Centric Memory for Long-Horizon Dialogue Agents [49.63422082885992]
  We propose AdaMem, an adaptive user-centric memory framework for long-horizon dialogue agents.<n>AdaMem organizes dialogue history into working, episodic, persona, and graph memories.<n>We evaluate AdaMem on the LoCoMo and PERSONAMEM benchmarks for long-horizon reasoning and user modeling.
  arXiv  Detail & Related papers  (2026-03-17T13:22:54Z)
• SwiftMem: Fast Agentic Memory via Query-aware Indexing [45.27116353623848]
  We propose SwiftMem, a query-aware agentic memory system that achieves sub-linear retrieval through specialized indexing over temporal and semantic dimensions.<n>Our temporal index enables logarithmic-time range queries for time-sensitive retrieval, while the semantic DAG-Tag index maps queries to relevant topics through hierarchical tag structures.<n> Experiments on LoCoMo and LongMemEval benchmarks demonstrate that SwiftMem achieves 47$times$ faster search compared to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-01-13T02:51:04Z)
• Memory Matters More: Event-Centric Memory as a Logic Map for Agent Searching and Reasoning [55.251697395358285]
  Large language models (LLMs) are increasingly deployed as intelligent agents that reason, plan, and interact with their environments.<n>To effectively scale to long-horizon scenarios, a key capability for such agents is a memory mechanism that can retain, organize, and retrieve past experiences.<n>We propose CompassMem, an event-centric memory framework inspired by Event Theory.
  arXiv  Detail & Related papers  (2026-01-08T08:44:07Z)
• AdmTree: Compressing Lengthy Context with Adaptive Semantic Trees [66.39371821756649]
  We propose AdmTree, a novel framework for adaptive, hierarchical context compression.<n>AdmTree segments input based on information density, utilizing gist tokens to summarize variable-length segments as the leaves of a semantic binary tree.<n>By preserving fine-grained details alongside global semantic coherence, mitigating positional bias, and dynamically adapting to content, AdmTree robustly retains the semantic information of long contexts.
  arXiv  Detail & Related papers  (2025-12-04T08:04:19Z)
• On Memory Construction and Retrieval for Personalized Conversational Agents [69.46887405020186]
  We propose SeCom, a method that constructs the memory bank at segment level by introducing a conversation segmentation model.<n> Experimental results show that SeCom exhibits a significant performance advantage over baselines on long-term conversation benchmarks LOCOMO and Long-MT-Bench+.
  arXiv  Detail & Related papers  (2025-02-08T14:28:36Z)
• From Isolated Conversations to Hierarchical Schemas: Dynamic Tree Memory Representation for LLMs [9.822315423251395]
  We introduce MemTree, an algorithm that leverages a dynamic, tree-structured memory representation to optimize the organization, retrieval, and integration of information.<n>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.
  arXiv  Detail & Related papers  (2024-10-17T21:47:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.