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

arXiv: https://arxiv.org/abs/2606.04555 · HTML: https://mlsanity.com/paper/2606.04555/

## Key facts

- Cited by 3 papers in the map (data through 14 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.

## Placed in

- LLM agents and tool use / [Agent memory systems](https://mlsanity.com/agents/agent-memory-systems/)

## Builds on (most cited first, 29 of 29)

- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [G-Eval: NLG Evaluation using GPT-4 with Better Human Alignment](https://mlsanity.com/paper/2303.16634/) (2023)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [MemGPT: Towards LLMs as Operating Systems](https://mlsanity.com/paper/2310.08560/) (2023)
- [A-MEM: Agentic Memory for LLM Agents](https://mlsanity.com/paper/2502.12110/) (2025)
- [Evaluating Very Long-Term Conversational Memory of LLM Agents](https://mlsanity.com/paper/2402.17753/) (2024)
- [Mem0: Building Production-Ready AI Agents with Scalable Long-Term Memory](https://mlsanity.com/paper/2504.19413/) (2025)
- [LongMemEval: Benchmarking Chat Assistants on Long-Term Interactive Memory](https://mlsanity.com/paper/2410.10813/) (2024)
- [MemoryBank: Enhancing Large Language Models with Long-Term Memory](https://mlsanity.com/paper/2305.10250/) (2023)
- [RAPTOR: Recursive Abstractive Processing for Tree-Organized Retrieval](https://mlsanity.com/paper/2401.18059/) (2024)
- [Is ChatGPT Good at Search? Investigating Large Language Models as Re-Ranking Agents](https://mlsanity.com/paper/2304.09542/) (2023)
- [HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models](https://mlsanity.com/paper/2405.14831/) (2024)
- [MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queries](https://mlsanity.com/paper/2401.15391/) (2024)
- [Evaluating Memory in LLM Agents via Incremental Multi-Turn Interactions](https://mlsanity.com/paper/2507.05257/) (2025)
- [Walking Down the Memory Maze: Beyond Context Limit through Interactive Reading](https://mlsanity.com/paper/2310.05029/) (2023)
- [Zero-Shot Listwise Document Reranking with a Large Language Model](https://mlsanity.com/paper/2305.02156/) (2023)
- [From Isolated Conversations to Hierarchical Schemas: Dynamic Tree Memory Representation for LLMs](https://mlsanity.com/paper/2410.14052/) (2024)
- [RealMem: Benchmarking LLMs in Real-World Memory-Driven Interaction](https://mlsanity.com/paper/2601.06966/) (2026)
- [Rank-without-GPT: Building GPT-Independent Listwise Rerankers on Open-Source Large Language Models](https://mlsanity.com/paper/2312.02969/) (2023)
- [Elaborative Subtopic Query Reformulation for Broad and Indirect Queries in Travel Destination Recommendation](https://mlsanity.com/paper/2410.01598/) (2024)
- [MA-DPR: Manifold-aware Distance Metrics for Dense Passage Retrieval](https://mlsanity.com/paper/2509.13562/) (2025)
- [Multimodal Item Scoring for Natural Language Recommendation via Gaussian Process Regression with LLM Relevance Judgments](https://mlsanity.com/paper/2510.22023/) (2025)
- [Topic Segmentation and Labeling in Asynchronous Conversations](https://mlsanity.com/paper/1402.0586/) (2014)
- [A Simple but Effective Elaborative Query Reformulation Approach for Natural Language Recommendation](https://mlsanity.com/paper/2510.02656/) (2025)
- [Semantic XPath: Structured Agentic Memory Access for Conversational AI](https://mlsanity.com/paper/2603.01160/) (2026)
- [Bayesian Active Learning with Gaussian Processes Guided by LLM Relevance Scoring for Dense Passage Retrieval](https://mlsanity.com/paper/2604.17906/) (2026)
- [Evaluating Scene-based In-Situ Item Labeling for Immersive Conversational Recommendation](https://mlsanity.com/paper/2604.09698/) (2026)
- [Goal-Oriented Reasoning for RAG-based Memory in Conversational Agentic LLM Systems](https://mlsanity.com/paper/2605.12213/) (2026)

## Built on by (most cited first, 3 of 3)

- [MicroVerse: An Instrument for Measuring Self-Authored Identity Drift in Long-Horizon Multi-Agent Language-Model Simulations](https://mlsanity.com/paper/2608.15844/) (2026)
- [RoutePrism: Tracing Construction Order Effects in Agent Memory](https://mlsanity.com/paper/2609.34160/) (2026)
- [Have I Scene This Before? Spatially Grounded Conversational Memory for Complex Queries in Egocentric Assistants](https://mlsanity.com/paper/2610.05526/) (2026)

## 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.