Graph-Based Memory: When Knowledge Graphs Beat Vector Stores

"Who else worked on the service Marc rewrote?" No chunk in your store contains that answer. One memory says Marc rewrote the ingestion service. A different memory, written three months earlier by a different conversation, says Priya and Dan own ingestion. The answer is the intersection, and it exists in neither document.

Raising k does not fix this. Set k to 50 and you get 50 chunks ranked by similarity to a query whose salient terms are "Marc" and "rewrote," which means you retrieve everything about Marc and nothing about ingestion ownership, because the ownership memory never mentions Marc. Top-k similarity is a single-hop operator. The question is two hops. That is a structural mismatch, not a tuning problem, and it is the clearest case where a graph earns its complexity.

The schema is smaller than you expect

CREATE TABLE memory_edges (
  id               bigserial PRIMARY KEY,
  subject          text        NOT NULL,
  predicate        text        NOT NULL,
  object           text        NOT NULL,
  valid_from       timestamptz NOT NULL DEFAULT now(),
  valid_to         timestamptz,               -- NULL = currently true
  source_memory_id uuid        NOT NULL REFERENCES memories(id),
  confidence       real        NOT NULL DEFAULT 1.0
);

CREATE INDEX ON memory_edges (subject, predicate) WHERE valid_to IS NULL;
CREATE INDEX ON memory_edges (object,  predicate) WHERE valid_to IS NULL;

Two columns carry most of the weight. source_memory_id means every edge is traceable to the text it came from, so you can show provenance and delete edges when their source memory is deleted. Without it you have a graph of assertions nobody can audit. valid_tomakes the graph bitemporal: an edge is not deleted when it stops being true, it is closed. "Marc owns ingestion" from January and "Priya owns ingestion" from June are both correct facts about different intervals, and a store that overwrites the first loses the ability to answer anything about the past.

The two-hop query is ordinary SQL:

WITH rewrote AS (
  SELECT object AS service
  FROM memory_edges
  WHERE subject = 'Marc' AND predicate = 'rewrote' AND valid_to IS NULL
)
SELECT e.subject AS person, e.object AS service
FROM memory_edges e
JOIN rewrote r ON e.object = r.service
WHERE e.predicate IN ('owns', 'works_on', 'maintains')
  AND e.valid_to IS NULL
  AND e.subject <> 'Marc';

For unbounded depth you need recursion, and you need a visited set or it will not terminate:

WITH RECURSIVE reach(node, depth, path) AS (
  SELECT 'Marc', 0, ARRAY['Marc']
  UNION ALL
  SELECT e.object, r.depth + 1, r.path || e.object
  FROM reach r
  JOIN memory_edges e ON e.subject = r.node
  WHERE r.depth < 3
    AND e.valid_to IS NULL
    AND NOT e.object = ANY(r.path)      -- cycle guard, non-negotiable
)
SELECT DISTINCT node, depth FROM reach WHERE depth > 0;

Cap the depth. In a densely connected personal knowledge graph, hop 4 typically reaches everything, and "everything" is not a retrieval result, it is the table.

Where graph memory actually breaks

It is not the traversal. Recursive CTEs are boring and fast at the scale a personal memory store operates at. It is entity resolution, and I want to be specific about why, because this is the part that gets waved away in every graph-RAG demo.

The same entity arrives under different names."Marc," "Marc T," "marc@company.com," "the new backend lead," and "he" all refer to one person across five conversations with three different LLMs. If those become five nodes, the two-hop query above returns nothing, because the edges are split across nodes that never join. A graph with unresolved entities is not a partially useful graph. It is a pile of disconnected pairs that answers strictly less than vector search would have, while costing more to build.

LLM extraction produces near-duplicate predicates. Ask a model to extract triples from a hundred memories and you will get works_on, worked_on, is_working_on, contributes_to, member_of_team, and assigned_to, all meaning the same relation. Your query filters on predicate IN (...) and misses two thirds of the edges. The fix is a closed predicate vocabulary supplied in the extraction prompt with an explicit instruction to emit other rather than invent a label, plus a periodic pass that maps stragglers onto the canonical set. An open vocabulary sounds flexible and is actually just an unqueryable schema.

Extraction costs a model call per memory. Every write becomes an LLM invocation producing a few hundred output tokens, and it must be re-run when the extraction prompt or the predicate vocabulary changes, which is a full backfill over the entire store. This is roughly an order of magnitude more expensive per write than embedding, where an embedding call is cents per million tokens and returns in tens of milliseconds. Budget for it as an async background job, never on the write path.

Edges go stale invisibly. A vector that is out of date still returns text with a timestamp on it, and a downstream model can notice the date and hedge. A closed-world graph query returns Priya owns ingestion as a bare fact with no hedge, and the model states it with full confidence. Graph answers feel more authoritative than they are, and that is a real hazard. Carry valid_from into the rendered context so the model can see how old the assertion is.

Microsoft's GraphRAG paper is worth reading precisely because it is honest about the indexing cost. Its win is on global sensemaking queries ("what are the main themes across this corpus") where no top-k retrieval can help by construction, and it pays for that with an expensive extraction and community-summarization pipeline over the whole corpus up front.

The decision rule

Graph when the query is relational: multi-hop, aggregate-over-neighborhood ("everyone who touched this service"), negative ("which services have no owner"), or temporal ("who owned this in March"). These all require structure that similarity cannot express, and no k is large enough.

Vectors when the query is associative: find me something like this, what did we discuss about the deployment problem, remind me of the thing about caching. Fuzzy, tolerant of paraphrase, and you want the original text back rather than a distilled assertion. Extraction into triples actively destroys information here, because the nuance of the sentence was the useful part.

In practice you run both and route. Detect whether the question names two or more entities with a relation between them; if so, try the graph and fall back to vector search when traversal returns empty. Feed both result sets into the context with clear labels so the model knows which claims are structured assertions and which are recalled text. Do not try to make one substitute for the other.

Unimatrix stores relations alongside the vector index rather than instead of it, and the Palace-to-Location hierarchy already gives traversal a natural scope so a two-hop query does not wander into an unrelated project. The retrieval tools that expose this are described in the MCP reference.