Time-Travel Retrieval for Agent Memory: Temporal Knowledge Graphs in Practice

Agent memory has quietly become the bottleneck in long-running assistants. A model that can plan and tool-call for hours is useless if it cannot answer "what did we decide last Tuesday?" without dragging the entire transcript back into context. Flat retrieval over chat logs degrades into needle-in-a-haystack search, and overwriting facts loses the history needed for auditing. Temporal knowledge graphs (TKGs) are the emerging answer: store facts with validity intervals, keep history append-only, and retrieve the state of the world at a chosen point in time.

Why flat memory fails on time

Most memory systems today fall into one of three traps:

• Context stuffing — append every turn to the prompt until the window fills. Works for short sessions, collapses on multi-week ones.
• Vector diaries — embed chunks and retrieve by cosine similarity. Good for "find the needle", blind to "is this still true?".
• Overwriting state — keep one current value per entity. Loses provenance and auditability; cannot answer retrospective questions.

The common failure mode is currency: the agent retrieves something semantically close but temporally wrong. A user changes jobs, a server is migrated, a policy is superseded — and the agent confidently quotes last month's fact. Temporal graphs attack this by making time a first-class dimension of storage and retrieval, not metadata bolted onto a vector.

The bitemporal property graph

The cleanest formulation is a bitemporal graph: each fact is stored as an immutable identity node linked to versioned content nodes carrying two closed-open intervals:

• Valid time — when the fact was true in the world.
• Transaction time — when the database recorded it.

Because nothing is overwritten, point-in-time retrieval becomes a filter rather than a reconstruction. A Neo4j-flavoured sketch:

MERGE (e:Entity {id: $entityId})
CREATE (v:FactVersion {
  value: $value,
  validFrom: datetime($validFrom),
  validTo: datetime($validTo),
  txFrom: datetime(),
  txTo: null
})
CREATE (e)-[:HAS_VERSION]->(v)

Retrieving "what did we know on 14 October?" is then a predicate on both intervals, not a search through overwritten rows. The cost is storage growth and query complexity; the benefit is auditability and the ability to answer "what did we believe then?" — essential for regulated or multi-agent settings.

Three retrieval strategies compared

Recent systems cluster into three approaches, with very different trade-offs:

Approach	Mechanism	Strength	Weakness
Graphiti / Zep	Temporally-aware KG with validity periods; non-lossy updates	Production-ready ingestion of chat + structured data	Heavy extraction cost; LLM per episode
Bitemporal store	Immutable versions with valid/transaction time	Exact point-in-time correctness; auditable	Post-filter dilution on temporal reasoning
Geometric (ROMEM)	Continuous phase rotation in complex space	Append-only, resolves conflicts at query time	Requires training; less interpretable

Graphiti (Zep's engine) dynamically synthesises unstructured conversation and structured business data while maintaining a timeline of facts and their validity periods — the closest thing to a production memory layer today. The bitemporal store is the right tool when correctness and auditability dominate. ROMEM takes a radical tack: time is a continuous phase shift, obsolete facts rotate out of phase, and conflicts resolve geometrically rather than through database operations.

What the benchmarks actually say

The 2026 benchmark of choice is LongMemEval (500 questions across six types, including knowledge updates and temporal reasoning). Three results are worth quoting:

• A bitemporal Neo4j store achieves 80% R@10 on knowledge-update questions via the time-travel path — but drops temporal-reasoning recall from 50% to 37.5%. The culprit is post-filter dilution: filtering after retrieval shrinks the candidate pool unevenly. The fix is to push temporal constraints into the traversal itself.
• Chronos (selective temporal event extraction plus dynamic prompting) reaches 95.60% accuracy on LongMemEval-S, with the events calendar alone contributing a 58.9% gain. The lesson: extract only temporally-grounded state transitions, keep raw turns for semantic context.
• TSHMem adds temporal transition reweighting to graph traversal and hits 66.3% accuracy with fewer evidence tokens — robustness comes from integrating time into graph topology, not treating it as decay metadata.

The pattern: treating time as metadata or a decay score is the recurring mistake. Integrating it into traversal, topology, or geometry is what moves the numbers.

Design choices that bite

A few practical traps, in order of severity:

1. Post-filter dilution. Never filter by validity after retrieval if you can avoid it. Push intervals into the Cypher WHERE clause or the traversal predicate.
2. Temporal-entity noise. Raw dialogue is full of ambiguous dates. Multi-resolution normalisation to ISO ranges (Chronos) beats single-point estimates.
3. Sparse long-tail evidence. Rare entities and isolated events fail naive traversal. Hybrid lexical–dense indexing (SodaMem) plus hierarchical summaries (TSHMem) covers the gaps.
4. Provenance. Store source spans. Without them, "why did the agent say that?" becomes unanswerable — and un-auditable.
5. Cost. Graphiti extracts per episode with an LLM. For high-volume agents, budget extraction before committing to the architecture.

A pragmatic starting point

For most teams, the sensible path is incremental:

1. Keep a raw turn calendar (cheap, high recall).
2. Add a selective event calendar with resolved datetime ranges.
3. Store facts as superseding versions with SUPERSEDES/UPDATES edges.
4. Retrieve with time-aware traversal, not post-filtering.
5. Measure on LongMemEval or LoCoMo before and after each change.

Time-travel retrieval is not a feature you bolt on; it is a property of how facts are modelled. The systems winning in 2026 are the ones that made that choice early and measured honestly — including the cases where time-travel made recall worse.

References

• Graphiti / Zep: temporal knowledge graph architecture for agent memory.
• Chronos: temporal-aware conversational agents with structured event retrieval.
• TSHMem: temporal-semantic hierarchical memory graph.
• SodaMem: evidence-grounded temporal graph memory.
• ROMEM: continuous phase rotation for temporal knowledge graphs.
• MAGMA: multi-graph agentic memory architecture.
• LongMemEval and LoCoMo benchmarks for long-term memory evaluation.