Temporal Order Matters for Agentic Memory: Segment Trees for Long-Horizon Agents
On the map: LLM agents and tool use → Agent memory systems
Abstract (arXiv)
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Placed in Agent memory systems, one of 16 directions in LLM agents and tool use. Builds on 29 of its 42 references that are in the map. First posted on arXiv 3 Jun 2026.
Builds on
29 of 42 references.
Closest ancestors · 6
Same direction, newest first
- 2026Goal-Oriented Reasoning for RAG-based Memory in Conversational Agentic LLM Systems12 May
- 2026Semantic XPath: Structured Agentic Memory Access for Conversational AI1 Mar
- 2025Evaluating Memory in LLM Agents via Incremental Multi-Turn Interactions7 Jul
- 2025Mem0: Building Production-Ready AI Agents with Scalable Long-Term Memory28 Apr
- 2025A-MEM: Agentic Memory for LLM Agents17 Feb
- 2024Evaluating Very Long-Term Conversational Memory of LLM Agents27 Feb
Other references · 23
- 2020Dense Passage Retrieval for Open-Domain Question Answeringcited by 3,779
- 2023Generative Agents: Interactive Simulacra of Human Behaviorcited by 3,500
- 2023G-Eval: NLG Evaluation using GPT-4 with Better Human Alignmentcited by 2,205
- 2023LongBench: A Bilingual, Multitask Benchmark for Long Context Understandingcited by 1,378
- 2023MemGPT: Towards LLMs as Operating Systemscited by 1,295
- 2024LongMemEval: Benchmarking Chat Assistants on Long-Term Interactive Memorycited by 656
- 2023MemoryBank: Enhancing Large Language Models with Long-Term Memorycited by 539
- 2024RAPTOR: Recursive Abstractive Processing for Tree-Organized Retrievalcited by 519
- 2023Is ChatGPT Good at Search? Investigating Large Language Models as Re-Ranking Agentscited by 356
- 2024HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Modelscited by 273
- 2024MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queriescited by 253
- 2023Walking Down the Memory Maze: Beyond Context Limit through Interactive Readingcited by 129
11 more
- 2023Zero-Shot Listwise Document Reranking with a Large Language Modelcited by 81
- 2024From Isolated Conversations to Hierarchical Schemas: Dynamic Tree Memory Representation for LLMscited by 77
- 2026RealMem: Benchmarking LLMs in Real-World Memory-Driven Interactioncited by 20
- 2023Rank-without-GPT: Building GPT-Independent Listwise Rerankers on Open-Source Large Language Modelscited by 14
- 2024Elaborative Subtopic Query Reformulation for Broad and Indirect Queries in Travel Destination Recommendationcited by 11
- 2014Topic Segmentation and Labeling in Asynchronous Conversationscited by 8
- 2025MA-DPR: Manifold-aware Distance Metrics for Dense Passage Retrievalcited by 8
- 2025A Simple but Effective Elaborative Query Reformulation Approach for Natural Language Recommendationcited by 8
- 2025Multimodal Item Scoring for Natural Language Recommendation via Gaussian Process Regression with LLM Relevance Judgmentscited by 8
- 2026Bayesian Active Learning with Gaussian Processes Guided by LLM Relevance Scoring for Dense Passage Retrievalcited by 5
- 2026Evaluating Scene-based In-Situ Item Labeling for Immersive Conversational Recommendationcited by 4
Built on by
Citing papers per year: 2026: 1.
1 paper.
Similar, not cited
Close in wording, no citation either way
- 2026APEX-MEM: Agentic Semi-Structured Memory with Temporal Reasoning for Long-Term Conversational AI
- 2026Beyond Dialogue Time: Temporal Semantic Memory for Personalized LLM Agents
- 2026AgentMemBench: A Systematic Benchmark for Evaluating Long-Term Memory Management Strategies in Conversational AI Agents
- 2026Membox: Weaving Topic Continuity into Long-Range Memory for LLM Agents
- 2026TiMem: Temporal-Hierarchical Memory Consolidation for Long-Horizon Conversational Agents
- 2026MemOps: Benchmarking Lifecycle Memory Operations in Long-Horizon Conversations
- 2026Beyond Memory Construction: Rethinking Memory Access for LLM-based Conversational Agents
- 2025A Simple Yet Strong Baseline for Long-Term Conversational Memory of LLM Agents