Skip to main content
Back

University of Toronto's SegTreeMem Beats Every Memory Baseline by 20%

SegTreeMem organizes conversation history as a chronologically ordered tree, beating flat retrieval and graph memory by up to 20% on long-horizon QA benchmarks.

Paper, Full Access
  • SegTreeMem is a new memory architecture for long-horizon conversational agents that organizes conversation history as a temporally ordered segment tree, guaranteeing every internal node covers a contiguous span of utterances.
  • It beats flat retrieval, graph memory (HippoRAG, A-MEM, Mem0), and tree memory (RAPTOR, MemTree) baselines by up to 20% LLM-judge accuracy across three benchmarks and two LLM backbones.
  • A temporal permutation ablation confirms the gains are specifically due to preserving order: randomly swapping 30% of utterance pairs drops SegTreeMem by 10-14 points, versus only 2-5 points for non-temporal baselines.
  • Retrieval uses score propagation through the tree (top-down or bottom-up), acting as a granularity dial: top-down favors specific factual recall, bottom-up favors broader contextual state.
  • Cosine-based construction is 10x cheaper in tokens and 5x faster than the LLM-based variant while remaining competitive in accuracy, making it the practical default for latency-sensitive deployments.
  • Known limitations include difficulty connecting long-range topical recurrences and potential loss of exact details (dates, names) in internal node summaries; code is available.

Most memory systems for conversational AI agents work like a topic-indexed filing cabinet: they group past exchanges by what they're about, not when they happened. That design choice turns out to be a significant limitation. A new paper from the University of Toronto and the Vector Institute argues that temporal order is a first-class structure for agent memory, and backs that claim with a new architecture called Segment Tree Memory (SegTreeMem) that beats every major memory baseline by up to 20% on long-horizon conversational QA.

The problem with topic-first memory

Long-horizon agents accumulate hundreds or thousands of utterances over time. The standard approach is to embed each utterance and retrieve the most semantically similar ones at query time. More sophisticated systems like RAPTOR, MemTree, A-MEM, and HippoRAG build hierarchical or graph-based structures on top of those embeddings. But nearly all of them organize memory by topical similarity, which means utterances from completely different moments in a conversation can end up grouped together under the same internal node.

The problem is subtle but real. Existing tree-based memory systems mostly focus on topically structured hierarchies and often ignore temporal sequencing, leaving two key design questions for temporally ordered memory underexplored: how to update a temporally ordered tree online as new utterances arrive, and how to exploit the resulting temporal hierarchy along with topical structure during retrieval. When a user asks "what did we decide last Tuesday about the project budget?", the answer depends on when something was said, not just what topic it touched.

Comparison of SegTreeMem temporal tree vs. other methods that lose temporal order in internal nodes

The segment tree as a memory index

A segment tree is a classical computer science data structure for range queries over intervals. SegTreeMem adapts it to conversation history: every node in the tree covers a contiguous, chronologically ordered span of utterances. Leaf nodes hold individual utterances; internal nodes hold LLM-generated summaries of the spans covered by their children. The root summarizes the entire conversation history.

This is the key structural guarantee that separates SegTreeMem from prior work. SegTreeMem represents conversation history as a Segment Tree over utterances while preserving temporal order, and incrementally incorporates new utterances into the Segment Tree while maintaining temporally contiguous interaction segments. No two children of the same parent can cover non-adjacent utterances. That invariant is enforced at every insertion.