🤖 AI

SodaMem: Evidence-Grounded Temporal Graph Memory for LLM Agents

SodaMem is an evidence-grounded temporal graph memory system for LLM agents that improves long-term conversation accuracy by tracking fact validity and provenance through time-aware graph edges, achieving state-of-the-art performance on LongMemEval-S at a low cost per query.

Original authors: Fengrong Wan, Chengcan Wu, Ningtao Lyu

Published 2026-08-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fengrong Wan, Chengcan Wu, Ningtao Lyu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are talking to a very smart, very chatty robot friend who has been hanging out with you for weeks. You've shared thousands of messages, from your favorite spicy food to the time you decided to quit eating it. Now, you ask, "What should I cook tonight?" A simple robot might just scan your chat history and find the first thing it sees: "I love spicy food!" It misses the fact that you changed your mind three days ago. This is the problem of Long-Horizon Memory in Artificial Intelligence. It's not just about finding a needle in a haystack; it's about knowing which needle is the current one, when it was picked up, and whether it's still sharp. Scientists are trying to build AI agents that don't just remember what was said, but maintain a living, breathing model of what is true right now, updating their knowledge as time passes and new information arrives.

Enter SodaMem, a new system designed to be the ultimate "memory manager" for these AI friends. Think of SodaMem not as a giant, messy notebook where every conversation is scribbled down in order, but as a high-tech, living time-traveling detective's board.

Most current AI memory systems are like flat diaries. If you write "I hate broccoli" on Monday and "I love broccoli" on Tuesday, a simple diary just has two lines. When you ask the AI later, it might get confused about which one is true, or it might grab the wrong one because it looks similar to your question. SodaMem fixes this by turning every fact into a FactEvent—a special, typed card that doesn't just say what happened, but when it was mentioned, when it actually happened, and how long it stays true.

Here is how the magic works:

The Detective's Board (The Graph)
Instead of a list, SodaMem builds a web of connections. Every time the AI learns something new, it creates a card. If you say, "I'm cutting down on spice," SodaMem draws a red line from that new card to your old "I love spicy food" card and labels it "SUPERSEDES" (meaning "this new one replaces the old one"). If you contradict yourself, it draws a "CONTRADICTS" line. This way, the AI doesn't just guess which fact is newer; it has a clear, visual map of the timeline. It knows exactly which fact is the "current" one and which ones are outdated history.

The Three-Legged Stool (The Retrieval)
When you ask a question, SodaMem doesn't just look for keywords. It uses a "multi-tunnel" search, like a detective using three different tools at once:

The Graph Tunnel: It follows the red and blue lines on the detective board to find related facts and check if they are still valid.
The Word Tunnel: It scans for exact words and phrases (like a classic search engine).
The Vibe Tunnel: It looks for ideas that "feel" similar to your question, even if the words are different.
It then combines all these clues. If the Graph Tunnel says "this fact is outdated" but the Word Tunnel finds it, the system weighs the evidence. It prioritizes facts that are supported by multiple paths and are still "valid" according to the timeline.

The Planner and The Reader
Once the evidence is gathered, SodaMem uses a two-step team to answer you. First, a Planner (like a project manager) checks the evidence, decides if it needs to dig deeper, and gathers the best facts. Then, a Reader (like a journalist) writes the final answer. Crucially, the Reader must cite its sources. It can't just make things up; it has to point to the specific "FactEvent" cards that prove its answer is correct.

The Results
The researchers tested this system on a tough challenge called LongMemEval-S, which has 500 questions about long conversations. SodaMem got 92.8% of the answers right (464 out of 500). Even more impressively, it did this while spending very little money on computer power—about $0.00161 per question on average (with a median of $0.00111).

In the world of AI memory, many other systems that get high scores cost ten to forty times more to run because they use much more expensive "brain" models. SodaMem sits near the top of the accuracy chart while staying in the "budget-friendly" zone. It proves that you don't need to spend a fortune to get a smart, up-to-date memory; you just need a better way to organize the facts.

However, the authors are careful to note that this is a specific configuration tested on one dataset. While the results are promising, they suggest that the system still has room to grow, especially in handling tricky time-related questions where humans might misremember dates. But for now, SodaMem offers a clear, evidence-based way for AI agents to stop living in the past and start living in the present.

Technical Summary: SodaMem

Problem Statement

Long-horizon LLM agents assisting users over weeks face four critical failure modes that flat RAG diaries, Markdown logs, and simple vector stores fail to resolve:

Currency/Conflict: Append-only logs struggle to determine the current state when preferences reverse (e.g., "I love spicy food" vs. "I am cutting down on spice"), often leaving the LLM to guess which chunk is freshest.
Temporal Structure: Systems fail at relative-date queries ("most recently," "two months ago") when lacking a comparable timeline or when relative phrases lack a clear anchor.
Provenance: Trust is undermined by lossy summaries and opaque vector hits that lack citations to specific source turns.
Association: Multi-hop synthesis often collapses due to context confusion, retrieving memories that are semantically similar but episodic mismatches, rather than establishing true entity/claim links.

The field has shifted from asking "can the model find a needle?" to "can the agent maintain a coherent, updatable model of the user and use it under the right conditions?"

Methodology: SodaMem

SodaMem is an evidence-grounded temporal graph memory infrastructure designed to maintain a citable, updatable user state. It operates via an Ingest–Store–Planner–Reader pipeline.

1. Core Data Structure: FactEvents

Memory is structured as FactEvents, defined as tuples $f = (\kappa, \pi, m, \tau, \rho, S, \sigma)$ :

Kind ( $\kappa$ ) & Predicate ( $\pi$ ): Typed facts.
Modality ( $m$ ) & Temporal Fields ( $\tau$ ): Includes mention time, occurrence time, and validity intervals.
Entity Roles ( $\rho$ ): Structured roles for entities.
Source Spans ( $S$ ): Mandatory provenance links to specific "MessagePieces" in the raw dialogue.
Status ( $\sigma$ ): Active, superseded, or invalid.

2. Ingest & Maintenance

Extraction: An LLM extracts candidates from dialogue sessions, enforcing a hard constraint that all claims must map to literal source spans.
Temporal Resolution: Optional post-processing resolves relative dates (e.g., "two days ago") into comparable timestamps based on the session time.
Supersession Logic: When a new fact updates a competing subject-predicate slot, the system creates SUPERSEDES, CONTRADICTS, or UPDATES edges. The old fact's validity interval is closed, and its status is marked as superseded.

3. Storage & Indexing

Persistence: Facts are stored in SQLite with hybrid indexing:
- Lexical: BM25 over fact text, spans, and raw turns.
- Dense: Vector embeddings (e.g., MiniLM/GTE) for semantic similarity.
- Graph: Edges connecting facts via semantic neighbors and typed relations.
Graph Relations: Includes DERIVED FROM links to spans and temporal edges (SUPERSEDES, etc.).

4. Retrieval: Multi-Tunnel & Connection-Density Fusion

Retrieval avoids relying on a single signal (e.g., cosine similarity alone) by using a three-tunnel approach:

Graph/Entity Tunnel (Strong): Hits entities or facts as search heads and expands via 1-hop or limited multi-hop semantic/relation edges.
BM25 Tunnel (Strong): Lexical hits on facts, spans, or raw turns, expanding to temporally adjacent turns for context.
Embedding Tunnel (Weak): Dense neighbors with expansion patterns similar to BM25 but lower base weights to avoid retrieving related-but-irrelevant episodes.

Fusion & Ranking:

Validity Gates: Hard filters exclude facts marked invalid/superseded or outside a stated validity window.
Connection Density: Evidence is ranked by the accumulation of "mass" from multiple hits (direct and derived) across tunnels.
Soft Temporal Scoring: Instead of hard time filters, a "time bonus" is added to the ranking confidence if the fact falls within the user's query window. This allows the system to recover from user misdating (e.g., "two months ago" for a 3-month-old fact).

5. Answering: Planner–Reader Loop

Planner: An LLM agent can iteratively call tools (search, inspect, session expand) to grow the evidence pool if initial density ranking is insufficient.
Reader: A separate LLM composes the final response using the selected evidence IDs, enforcing mandatory citations to the source records. This separation ensures citation discipline is distinct from tool policy.

Key Contributions

Problem Framing: The paper synthesizes agent-memory research to isolate currency, temporal structure, provenance, and association as the specific failure modes left unresolved by flat RAG and Markdown logs.
System Architecture: SodaMem introduces a pipeline featuring a typed FactEvent schema, hybrid retrieval (graph + lexical + dense), supersession semantics for conflict resolution, and a planner–reader loop for evidence-grounded answering.
Cost–Accuracy Evaluation: The authors compile public systems with estimable API costs into a unified cost–accuracy map, analyzing the "dominated" region (higher cost, lower accuracy) relative to their own system.

Results

Evaluated on LongMemEval-S (500 questions, ~115k-token histories):

Accuracy: SodaMem achieved 92.8% accuracy (464/500) in a store-of-record configuration (best of N=3).
Cost Efficiency:
- Mean Cost: $0.00161 per question (~18.3k tokens) using deepseek-v4-flash.
- Median Cost: $0.00111 per question (~14.6k tokens).
Comparison:
- SodaMem sits near the accuracy frontier while operating at "Flash-tier" spend.
- It strictly dominates several published systems (e.g., Cersei Embed/Hybrid, AgentOS, MemoryBank) that offer lower accuracy at significantly higher costs (often using GPT-4o or Opus-class models).
- While top-tier systems like agentmemory V4 (96.2%) and Mem0 (94.4%) achieve higher scores, they do so at an estimated order of magnitude higher cost (using Opus/GPT-4o).

Significance and Claims

The paper claims that SodaMem demonstrates that high-accuracy, evidence-grounded personal memory does not require expensive, massive-context models or unstructured logs. By treating memory as a temporal knowledge graph with explicit supersession logic and a planner–reader loop, the system achieves:

Maintainable State: A coherent, updatable model of the user that handles preference reversals deterministically.
Auditability: Every claim is backed by a source span, addressing the provenance gap in current RAG systems.
Cost-Effectiveness: It achieves near-frontier accuracy (92.8%) at a fraction of the cost of systems relying on high-end models, effectively "undercutting" Opus/GPT-4o high-spend systems by ~10–40x in estimated cost per question.

The authors note limitations, including reliance on self-grading (using the same Flash model as judge) and the fact that cost comparisons are compiled estimates rather than a single-harness bake-off. However, the results suggest that structured, evidence-grounded temporal graphs are a viable path for long-horizon agents.