AI Graph Database Evaluation Checklist for Agent Memory

Your agent nails today’s conversation and forgets it by tomorrow. Or worse, it remembers a fact that expired last week and states it with total confidence. The memory layer is failing, and the fix is not a bigger prompt. It is the database underneath, and picking the wrong one shows up as an agent nobody can trust.

Agent memory is a database problem before it is a prompt problem. Once you accept that, the question becomes which store to trust, and an ai graph database keeps surfacing as the answer for entities, relationships, and time. This post gives you a 7-point checklist to run before you commit.

The checklist is testable. Each of the seven dimensions is its own section with something you can measure, not a vibe. Two of them ship with runnable harnesses you can point at any candidate. By the end you will score your top engines on your real memory traffic, not a vendor slide.

TL;DR

• Agent memory is a database problem first: entities, relationships, and time, which flat vector stores cannot represent.
• Score any ai graph database on seven dimensions: latency, temporal correctness, precision and recall, schema flexibility, scale and cost, ecosystem, and ops with licensing.
• Two dimensions ship with runnable harnesses in this post: a temporal-correctness check and a precision@k check you can point at any candidate.
• Shortlist by published benchmarks like Zep’s, then replay your own memory traffic; a vendor number is a reason to test, never a reason to skip the test.
• Weight the dimensions for your agent, verify the current license and maintenance status of each engine, and re-score as your workload shifts.

Why Does Agent Memory Push You Toward a Graph Database?

Vector stores are excellent at one job: find text that looks like this query. Agent memory needs more than resemblance. It needs to know that a user changed jobs, that the new role supersedes the old one, and how two facts connect. A flat list of embeddings cannot hold those relationships cleanly.

Three gaps show up fast in production. Vector-only memory has no first-class relationships, so multi-hop recall degrades into guesswork. It has no clean temporal validity, so expired facts resurface. And similarity search over a growing memory returns near-duplicates that crowd out the one memory that mattered. Structure is the fix for all three.

This is the case for graph structure in memory: nodes for entities, typed edges for relationships, and timestamps for validity. If you are weighing the two designs head to head, our breakdown of vector store vs knowledge graph shows how each behaves under load before you pick one for memory.

None of this means a graph store is automatically right. It means the memory workload has shape that graphs represent well, and that shape is exactly what you will test. Our guide on how to evaluate agent memory frames the failure modes; the checklist below turns them into pass-or-fail measurements you can run.

One scope note, because “graph database” covers two different buying decisions. This post is only about the agent memory workload: facts about users and sessions that accumulate, expire, and get contradicted, where validity windows and recall quality decide whether the agent is trustworthy. It is not about picking a graph store to back a GraphRAG pipeline over a static document corpus, which turns on data model, native vector indexing, and framework adapters instead. If your graph holds documents rather than a user’s history, you want that decision framework, not this checklist.

The Checklist at a Glance

Seven dimensions decide whether an ai graph database can carry agent memory. Three are performance and cost gates, two are correctness gates, and two are operational gates. No single engine wins all seven, so the point is not a ranking. It is a weighted score against the workload you actually run.

Weight the dimensions before you score. A support agent with fast-changing facts leans on temporal correctness and latency; a research agent leans on precision, recall, and scale. Assign each dimension a weight that sums to one, then score every candidate the same way so the comparison stays honest across engines.

1. Query Latency and Write Throughput

Memory reads sit on the agent’s critical path. Every step that recalls context waits on the store, so p50 and p95 read latency shape how responsive the agent feels. Measure both under a realistic memory size, because a store that is fast at ten thousand nodes can stall at ten million.

Writes are the quieter risk. Agent memory arrives in bursts, a whole session flushed at once, then long idle gaps. Sustained write throughput under those bursts matters more than a headline average, because a store that buffers well on paper can drop or delay writes when a conversation ends and everything commits together.

Framework choices move these numbers. In Zep: A Temporal Knowledge Graph Architecture for Agent Memory, Rasmussen et al. report accuracy improvements of up to 18.5% on LongMemEval while cutting response latency 90% against a full-context baseline, plus 94.8% on the Deep Memory Retrieval benchmark against MemGPT’s 93.4%.

Read those numbers with the byline in mind: the paper is written by the Zep team about Zep, on benchmarks they selected. Treat them as a reason to shortlist graph-shaped memory, not as a result your setup will reproduce. Structure buys real headroom on latency and recall; the size of the win is yours to measure.

The takeaway is to benchmark on your own trace. Replay a real session’s reads and writes against each candidate, at the memory size you expect in six months, and record p50, p95, and sustained write rate. Published wins are a reason to shortlist an engine, never a reason to skip the test.

2. Temporal and Bitemporal Correctness

This is the dimension most stores get wrong, and the one that erodes trust fastest. A fact is rarely true forever. A user’s job title, their current project, a price, a policy: each has a window when it holds. Memory that returns a fact outside its window is not just stale, it is confidently wrong.

Bitemporal modeling separates two clocks: when a fact was true in the world (event time) and when your system learned it (ingestion time). You need both to answer questions like what did we know last Tuesday. An ai graph database that stores validity intervals on edges can answer point-in-time queries a plain store cannot.

Test it directly rather than trusting the datasheet. The harness below scores temporal correctness: it feeds cases where a fact should or should not be returned given the query time, and checks that the store honored the validity window. A perfect score means the engine never leaks an expired fact into agent context.

def temporal_correctness(cases):
    """Each case: (query_time, valid_from, valid_to, was_returned).
    Correct when a fact is returned only if the query time falls inside
    the fact's validity window."""
    correct = 0
    for q_time, valid_from, valid_to, returned in cases:
        should_return = valid_from <= q_time <= valid_to
        if should_return == returned:
            correct += 1
    return correct / len(cases)

if __name__ == "__main__":
    cases = [
        (5, 0, 10, True),    # in-window, returned  -> correct
        (15, 0, 10, False),  # expired, not returned -> correct
        (15, 0, 10, True),   # expired but returned  -> wrong
    ]
    score = temporal_correctness(cases)
    assert abs(score - 2/3) < 1e-9
    print(f"temporal correctness: {score:.2f}")

Run this against each candidate with your own validity windows and it becomes a regression gate. The diagram below shows the rule in one picture: a query inside the window gets the fact, a query after expiry gets nothing. Wire the same check into CI so a memory upgrade cannot silently reintroduce stale recall.

3. Retrieval Precision and Recall for Memory

Latency tells you how fast memory answers; precision and recall tell you whether the answer is any good. Precision@k is the fraction of the top-k recalled memories that are actually relevant. Recall@k is the fraction of all relevant memories that made it into the top-k. Agent memory needs both to stay high.

The two fail differently. Low recall means the agent misses a memory it needed and acts on a gap. Low precision means the agent’s context fills with near-duplicate or irrelevant memories that dilute the prompt and push the useful one out of the window. Both degrade answers without throwing any error.

You measure this with a labeled set: a handful of queries, each tagged with the memory IDs that truly answer it. The function below computes precision@k over that set. The same pattern extends to recall, and our guide on how to measure retrieval precision in CI shows how to gate it.

If you have no labels yet, LongMemEval is the closest public stand-in: 500 curated questions over long chat histories, scored across information extraction, multi-session reasoning, temporal reasoning, knowledge updates, and abstention. Use it as a floor, then label your own traffic, because your users ask nothing like a benchmark.

def precision_at_k(retrieved_ids, relevant_ids, k):
    """Fraction of the top-k retrieved memories that are relevant."""
    top = retrieved_ids[:k]
    if not top:
        return 0.0
    relevant = set(relevant_ids)
    hits = sum(1 for _id in top if _id in relevant)
    return hits / len(top)

if __name__ == "__main__":
    retrieved = ["m3", "m1", "m9", "m2"]
    relevant = {"m1", "m2", "m3"}
    assert precision_at_k(retrieved, relevant, k=2) == 1.0   # m3, m1 hit
    assert precision_at_k(retrieved, relevant, k=4) == 0.75  # m9 misses
    print("precision@k ok")

Set a threshold that matches your risk. A medical or legal agent may demand precision above 0.9 so it never acts on a wrong memory; a brainstorming assistant can tolerate lower precision for higher recall. Pick the numbers per use case, then hold every candidate ai graph database to the same bar.

4. Schema Flexibility and Ontology Evolution

Agents learn new entity types as they run. A support agent that started with users and tickets may need devices, contracts, and incidents next quarter. If adding an entity type means a schema migration and downtime, the memory layer fights the agent’s growth. Flexible schema is not a nicety here, it is a requirement.

For memory specifically, the data-model choice reduces to one question: how often does the shape change? Property graphs let you attach new labels and properties to nodes with no central schema, which is what fast-evolving memory wants. RDF and its ontologies give you strict semantics and reasoning in exchange for upfront modeling, which pays off when the schema is stable and shared across teams. Agent memory usually is not.

Test it with a simple drill: add a brand-new entity type and a relationship to your running store, then query across it, and time how long the whole change takes. An engine where that is a five-minute code change beats one where it is a migration ticket, at least for memory that keeps evolving.

5. Scale, Sharding, and Cost

Agent memory only grows. Every session adds nodes and edges, and nothing prunes itself by default. So the honest question is not how the store performs today but how it behaves at ten or a hundred times the current graph. Ask for node and edge ceilings, and whether traversal stays fast as both climb.

Sharding is where graph stores differ most. Partitioning a graph without cutting important edges is hard, and some engines scale vertically far better than they scale out. Know the story before you commit: a single-node ceiling you will hit in a year is a migration you are scheduling today without realizing it.

Cost tracks scale directly, so price the memory at its future size, not its launch size. Compare hosted per-node or per-hour pricing against self-hosted infrastructure and the people to run it. And watch memory growth in production, because an unbounded graph is a bill that climbs on its own.

6. Ecosystem and Framework Integrations

A graph store rarely plugs into an agent raw. Between the database and your agent sits a memory framework, and that layer often decides the experience more than the engine underneath. Score the integration path to your stack, not just the database’s benchmarks, because a great engine with no clean adapter is slow to adopt.

Three memory layers dominate right now. Zep, through its open Graphiti engine, builds a temporal knowledge graph tuned for agent memory. Mem0 offers a simpler key-fact memory API with native graph memory. Cognee builds an ontology-driven memory graph from raw data. Each sits on top of, or ships with, a graph store.

So evaluate the pair, not the part. A mid-tier engine with a first-class adapter to your agent framework and one of these memory layers will ship faster and break less than a benchmark leader you have to integrate by hand. Check driver maturity, client libraries in your language, and whether the framework you use is supported.

7. Operational Maturity and Licensing

The last dimension is the one that stops a launch. Can you back the memory up and restore it? Is there real high-availability, or a single node whose failure loses every agent’s history? Is there observability into slow queries? Memory that cannot be operated safely is a liability no benchmark score offsets.

Licensing decides whether you can ship at all. Open-source, source-available, and commercial licenses carry very different obligations, and a source-available license like BSL or SSPL can block the exact hosted setup you planned. Read the terms for your deployment before you fall for an engine, because relicensing surprises are expensive to unwind later.

The table below scans five common engines across model, strength, and license, as a starting shortlist rather than a verdict. Confirm the current license and maintenance status at evaluation time, since both shift. Then score your final two candidates on all seven dimensions with your own memory traffic before you sign anything.

Two rows deserve a caveat. Kùzu is genuinely good embedded technology, but kuzudb/kuzu is archived: existing releases keep working and the maintainers moved docs to GitHub Pages, yet nobody is shipping fixes, so treat it as frozen rather than maintained. And every head-to-head latency benchmark you will find comparing these engines was published by one of the vendors in it. Those numbers are a reason to shortlist, never a substitute for replaying your own memory traffic.

Scoring Memory Retrieval Quality with Future AGI

Dimensions two and three, temporal correctness and retrieval quality, are not one-time checks. They drift as memory grows and as the agent meets new data, so they need a scorer you can run continuously, not a spreadsheet you fill in once. This is where Future AGI fits into the checklist, as the measurement layer.

Start by turning your memory-correctness rule into a custom eval that encodes exactly what a right memory looks like for your agent. Because you define the criteria, the score reflects your validity windows and relevance bar, not a generic notion of correctness that ignores how your ai graph database is used.

Built-in evals cover dimension 3 directly. Precision@K and Recall@K are the same metrics the harness above computes, run against a labeled set of relevant memory IDs, so the numbers in this post become a scored dataset instead of a one-off script.

Context relevance adds the judged view of the same question: were the returned memories relevant and sufficient to answer the query at all.

Trajectory match goes one level up from retrieval and compares the agent’s action sequence against an expected trajectory, in strict, unordered, subset, or superset mode. It catches a run that fetched the right memory and then used it in the wrong order.

Log every memory call through Observe so retrieval quality, latency, and the path each query took sit in one trace. A regression then shows up as a visible event instead of a vague complaint that memory feels worse.

If you want the temporal-correctness gate running in CI without a network call, Future AGI’s Agent Learning Kit is Apache-2.0 and ships 72 local metrics behind a single evaluate() call after pip install ai-evaluation. That is the piece that makes a memory regression test cheap enough to run on every pull request.

The wider Future AGI platform is open source on GitHub. Sign up and run it managed, or self-host the whole stack on your own infrastructure with Docker Compose, whichever suits how your memory data is allowed to travel.

Running the AI Graph Database Checklist Before You Commit

Do not pick a memory store from a landing page. Take your two favorite engines, and score them on all seven dimensions with your own memory traffic: real sessions, real validity windows, real query mix. The checklist turns a brand preference into a number you can defend in a design review.

Weight the dimensions by how your agent actually works. A fast-changing support agent scores temporal correctness and latency heavily; a research agent weights precision, recall, and scale. Run the two harnesses from this post, fill the operational and licensing rows from the vendor’s terms, and let the weighted total do the deciding.

Then re-run it. Memory workloads move as your agent takes on new tasks, so the ai graph database that wins today may not win next year. Keep the checklist and its harnesses in your repo, re-score when your traffic shifts, and let evidence, not the loudest brand, keep picking your agent’s memory.