Temporal Order Matters for Agentic Memory: Segment Trees for Long-Horizon Agents
For developers of long-horizon conversational agents, this work demonstrates that explicitly preserving temporal order in memory structures yields measurable performance gains over existing methods that rely primarily on topical similarity.
The paper introduces Segment Tree Memory (SegTreeMem), a memory architecture that organizes conversation history as a temporally ordered segment tree, improving answer quality over flat retrieval, graph-structured memory, and tree-structured memory baselines across three long-horizon benchmarks and two LLM backbones.
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.