Temporal Order Matters for Agentic Memory: Segment Trees for Long-Horizon Agents
2026-06-03 • Computation and Language
Computation and LanguageArtificial Intelligence
AI summaryⓘ
The authors created a new way for chatbots to remember past conversations by keeping track of the order in which things happen, not just the topics discussed. This method, called Segment Tree Memory (SegTreeMem), organizes conversation pieces in a tree that respects time order and groups related parts hierarchically. When the chatbot needs to find information, SegTreeMem combines how relevant something is with its place in the timeline. Tests showed that keeping the time order helped the chatbot answer questions better compared to other memory systems. This suggests that remembering when things happened is important for good, long-term chatbot memory.
conversational agentsmemory architecturetemporal orderSegment Tree Memoryhierarchical memorysemantic matchinglong-horizon memoryonline update ruleretrievallarge language models (LLM)
Authors
Yifan Simon Liu, Liam Gallagher, Faeze Moradi Kalarde, Jiazhou Liang, Armin Toroghi, Scott Sanner
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.