When an AI agent tells a doctor that a patient has a penicillin allergy, the doctor needs to know: did that fact come from a verified electronic health record, a PDF lab report, or something the patient typed into a chat intake form? If the agent can't answer that question, the fact is dangerous. Knowledge graph provenance is the practice of structuring your agent's memory so every derived fact carries a link back to the raw data that produced it — and it is the single biggest unsolved engineering problem in production AI agent memory today.
Provenance — tracing how an artifact was built and why — is not a feature you bolt on after the fact. It has to be engineered into the data structure itself, and that structure is a graph. In a knowledge graph, facts live as relationships (edges) between entities (nodes), and the raw source data becomes a node too. Tracing a fact to its source becomes a graph walk instead of a database forensics exercise.
In this article: why provenance breaks in LLM pipelines (and why a source ID isn't enough), the graph-based provenance architecture that actually works in production, the four real-world problems it solves (trust, debugging, deletion, compliance), the open-source stack you can build on, and a practical implementation pattern.
Why does provenance break in LLM pipelines?
Standard data-warehouse lineage works because transformations are deterministic — one value in, one value out, and the pipeline documents each step. LLM context pipelines are nothing like that. When you prompt an LLM with several sources, it synthesizes facts that never existed verbatim in any single source. It merges "J. Smith" and "John Smith" into one entity. It derives new facts from multiple inputs at once. The output artifact — a fact, a summary, a structured record — often looks nothing like the inputs, and the paper trail of how it got there disappears during synthesis.
This is why the naive approach — "just store a source ID on each fact" — breaks in at least three ways:
- One fact, multiple sources. An LLM might synthesize a single fact from three source documents. Which source ID do you store? All three? In what relation? A single foreign key cannot express the nuance.
- Entity mutation. When "J. Smith" and "John Smith" are merged into one entity, the merged entity inherits facts from both. Every source link from both original entities must carry through to the merged entity, or lineage is silently dropped.
- Temporal contradiction. A fact that was true yesterday ("Daniel loves Adidas shoes") is contradicted by new data today ("Daniel returned the shoes and complained"). The old fact must be invalidated, not deleted — because you need to know it was once true and understand who told you otherwise. A flat source ID has no notion of temporal validity or mutation history.
So if you cannot solve provenance with source IDs, how do you solve it? You model the relationships between facts and their sources as links in a graph.
What is knowledge graph provenance?
Knowledge graph provenance is the practice of storing every source datum as a graph node, every derived fact as a graph edge between entity nodes, and every link from a fact back to its source as a graph relationship. Tracing a fact to its source becomes a graph walk — navigate from the edge (the fact) to the source nodes it links to.
The core data structure is a triple: subject (entity) → predicate (fact) → object (entity). In a healthcare example, that means:
Patient → has_allergy → Penicillin
The two entities (Patient, Penicillin) and the edge between them (has_allergy) together form a hydratable fact: "Patient has a penicillin allergy." The source data for this fact is the raw text from an EHR record, a PDF lab report, and an AI intake chat transcript — each stored as a separate node in the graph, linked to the fact edge it supports.
This is not an append-only log. It is an evolving graph that survives mutation: when entities merge, when facts are contradicted, when sources are deleted, the relationships update and the graph stays consistent.
Key graph components for provenance
| Component | What it is | Role in provenance |
|---|---|---|
| Entities (nodes) | People, products, concepts | The subjects and objects of facts; updated over time with evolving summaries |
| Facts / relationships (edges) | Typed triplets connecting entities | Each edge carries temporal validity (valid_at, invalid_at) |
| Episodes (source nodes) | Raw data as ingested — conversations, documents, records | Ground truth stream; every derived fact links back to its episodes |
| Lineage links | Edges from a fact edge to its source episode(s) | The actual "paper trail" — how you trace a fact to its origin |
How does temporal validity solve fact mutation?
A traditional knowledge graph treats facts as permanently true. That assumption is fatal in agent memory, where the world changes faster than the graph does.
A temporal knowledge graph (sometimes called a "context graph") attaches explicit validity windows to every fact:
valid_at: when the fact became true (timestamped from the source episode)invalid_at: when the fact was superseded or contradicted by new data
This lets you answer questions that a flat fact store cannot:
- "What did we know about this patient at time T?" — only return facts with
valid_at ≤ Tand noinvalid_atorinvalid_at > T - "When did this relationship change?" — look for the
invalid_attimestamp and the episode that caused it - "What facts are currently active?" — filter out anything with an
invalid_atin the past relative to the query time
The Adidas shoes example
This is not theoretical. Consider a user whose preferences change over time:
- March 2026: user sends a chat message mentioning they love their new Adidas shoes. The graph creates an edge:
User → loves → Adidas_shoes, withvalid_at: 2026-03-15. - June 2026: user returns the shoes through a return application and submits a complaint. The graph edges now are:
User → returned → Adidas_shoesandUser → unhappy_with → Adidas_shoes. - The original "loves Adidas shoes" edge is not deleted — it gets
invalid_at: 2026-06-10. Two episodes produced the change: the return transcript and the complaint.
Now when an agent retrieves context about this user's shoe preferences, it gets the current state (unhappy, returned shoes) and the historical state (loved them in March). Both are available for reasoning, and the agent can trace why the fact changed — the return and the complaint episodes.
This temporal model is what separates a knowledge graph for agent memory from a static knowledge graph or a document store. Without temporal validity, stale facts pollute agent context. Without provenance links, you cannot explain why a fact was invalidated.
What are the four problems provenance solves in production?
Provenance is not just a nice-to-have for compliance officers. It is the architectural answer to four real engineering problems that show up the moment your AI agent moves from a demo into production.
1. Verification and trust: "Should I trust this fact?"
When an agent retrieves context, you need to evaluate the veracity of each fact. A fact synthesized from a verified clinical record is more trustworthy than one pulled from what a patient typed into an intake chat.
In a provenance-enabled graph, you can tag source episodes at ingestion time — for example, with a "verified_clinical" tag. All entities and facts derived from those episodes inherit the tag through their lineage links. When the agent wants to retrieve only facts from trusted sources, it filters on the tag as it walks the graph.
But what about facts with multiple sources of differing quality? This is where policy matters. A fact with three source episodes — one verified, two not — might need different handling depending on what it is:
- For a life-or-death fact (drug allergy), missing one unverified source flag could be fatal. The rule might be: "retrieve the fact but flag that not all sources are verified."
- For a consent on file fact, generating clinical consent from an unverified source could lead to operating without actual consent. The rule might be: "every parent episode must be verified, or pull the fact entirely."
The graph store exposes which episodes carry which tags — your business rules decide what to do with it. The provenance layer gives you the raw material to enforce those rules. Without it, all facts look equally trustworthy, and that is how every agent-incurred liability case starts.
2. Debugging: "Why does the agent think this?"
When an agent produces a wrong or surprising result, the first debugging question is always "where did that come from?" Without provenance, you are reverse-engineering an LLM pipeline's entire history to find where a fact entered context — which is infeasible at scale.
With knowledge graph provenance, "why does the agent think X is true?" is a graph walk: X is an edge → find its source episodes → inspect their content. The answer is deterministic and fast regardless of graph size. You can trace the chain of reasoning from raw input to final fact to invalidation/contradiction in minutes, not days of log analysis.
3. Deletion under retention policies (GDPR, right to be forgotten)
This is the hardest problem provenance solves, and it is a legal requirement in the EU and California.
GDPR Article 17 gives individuals the right to request erasure of their personal data. In practice, when a user asks you to delete their data, you must remove it from your agent's memory too — and that memory includes facts derived from their conversations, which may be tangled with data from other sources.
The provenance graph makes this tractable because you can trace all facts that have lineage links to the deleted source's episode:
- Partial deletion with fact survival: A fact with three source episodes — one of which is the deleted one — survives deletion because the other two episodes still support it. You remove the lineage link to the deleted episode, but the edge stays.
- Cascading deletion of fully derived facts: A fact that was derived solely from the deleted source has no remaining supporting episodes — it is deleted entirely because nothing else backs it up.
The rule is clean: a fact is only deleted if no remaining source episodes support it. This is only computable if you have the lineage links. Without provenance, you are either deleting too much (destroying facts still supported by other sources) or too little (leaving facts from a deleted user's data in agent context, which is a GDPR violation) — and you likely cannot tell which.
4. Compliance auditing
Privacy regulators increasingly expect technical auditability — not just a policy document. If you cannot show, on demand, exactly where a fact came from, when it was derived, which source produced it, and whether any contradicting facts superseded it, you cannot demonstrate compliance. A provenance graph gives you the full chain as queryable graph structure that you can export for an audit on demand.
Association-level compliance also becomes structured: classifying which facts derived from which source episodes lets you produce data-flow maps ("all facts that originated from EHR feeds") that a compliance officer would normally spend weeks reconciling by hand.
Which open-source tools implement knowledge graph provenance?
The most mature open-source implementation of temporal knowledge graph provenance for AI agents is Graphiti, an Apache-2.0-licensed framework from Zep AI (github.com/getzep/graphiti).
Graphiti is built specifically to power agent memory at scale. Its core design matches the architecture above almost exactly:
- Episodes: source nodes — raw conversations, documents, or records — stored verbatim in the graph so every derived fact traces back to its source
- Entities and relationships: nodes and edges extracted from episodes by an LLM, with typed structure (subject → predicate → object)
- Temporal validity: every edge has
valid_atandinvalid_attimestamps, so the graph tracks what is true now and what was true before - Provenance by graph walk: tracing a fact to its source means starting at the edge and navigating to its source episodes through the lineage links in the graph
Graphiti powers Zep (getzep.com), Zep AI's managed agent-memory platform, which extends the open-source engine with low-latency retrieval, a hosted graph API, and production governance at scale. The Zep/Graphiti architecture is documented in an arXiv paper, "Zep: A Temporal Knowledge Graph Architecture for Agent Memory", which benchmarks Zep against MemGPT and shows strong retrieval performance on both the Deep Memory Retrieval benchmark and real-world enterprise evaluations.
A notable feature: Graphiti also includes an MCP server (mcp_server/README) — so AI coding assistants like Claude and Cursor can query a context graph directly. The MCP endpoints include add_triplet for inserting facts, search_memory_facts for temporal-aware fact retrieval, and get_episode_entities for tracing provenance from an episode to its derived entities. This means you can integrate provenance-aware retrieval into an AI assistant pipeline today, not in a research fork.
For more general data lineage needs (where the source is enterprise pipelines rather than LLM agents), Neo4j's graph-database documentation describes how knowledge graphs model data lineage across systems — the same edge-based provenance structure, applied to ETL rather than LLM context (Neo4j: What is data lineage?).
| Tool | License | Type | Provenance model | Best for |
|---|---|---|---|---|
| Graphiti | Apache-2.0 | Temporal knowledge graph framework | Edges link to Episodes (source nodes); valid_at/invalid_at timestamps |
AI agent memory with fact mutation and source traceability |
| Zep | Commercial | Managed agent memory platform (built on Graphiti) | Same provenance model, plus API/governance at scale | Production agent deployment without managing graph infra |
| Neo4j | GPL/Commercial | General graph database | Edges + nodes with lineage metadata | General-purpose data lineage, enterprise data governance |
| ProvTracer | Open source | Provenance-trace KG (research artifact) | Multi-modal LLM + knowledge graph serialization | Research and direct artifact provenance capture |
How do you implement knowledge graph provenance? A practical pattern
If you are building an AI agent with context that evolves over time, the provenance architecture has a clear pattern whether you adopt Graphiti, build on a graph database like Neo4j, or roll your own.
Step 1: Store episodes verbatim — every conversation turn, every document, every record the agent ingests goes in as a node. Do not summarize or transform yet; that happens later. This is the ground truth the provenance links point back to.
Step 2: Extract entities and relationships with an LLM — run an LLM extraction pass on each episode to pull out named entities and the relationships between them. The output is a set of triples: subject → predicate → object. Graphiti handles this in its extract_edges pipeline using structured LLM prompts with reference-time anchors for temporal reasoning (graphiti_core/utils/maintenance/edge_operations.py).
Step 3: Deduplicate and deconflict — when two entities turn out to be the same (e.g. "J. Smith" and "John Smith"), merge them. The merged entity inherits all source links from both originals. When a new fact contradicts an existing one, do not delete the old fact — mark it with an invalid_at timestamp and record which episode caused the contradiction. This is the step that keeps provenance stable as the graph mutates.
Step 4: Tag source episodes at ingestion — add metadata to each episode at the moment it enters the graph: source type (EHR, chat, email), trust level (verified, self-reported), retention rule. Every entity and fact derived from that episode inherits the tag through the lineage graph. Later, filtering "only verified_clinical facts" is a single graph traversal with a predicate filter.
Step 5: Link every derived fact back to its source episodes — for each edge in the graph, create a lineage link to the episode(s) it was extracted from. This is the provenance edge itself — the red arrow from the fact to the source. It is what makes the entire pattern queryable.
Step 6: At query time, retrieve facts with both their values and their provenance — when an agent retrieves context, return not just the fact, but its source lineage, trust tags, and temporal validity. The agent surface (or a wrapper around it) can then display provenance to the end user or apply business rules to what to surface.
Step 7: Deletion is a lineage walk — when a source must be deleted (e.g. a right-to-be-forgotten request), find every fact with a lineage link to that source episode. If the fact has other supporting episodes, remove the link to the deleted episode and keep the fact. If it does not, delete the fact. This is the entire rule: a fact is only deleted if no remaining episodes support it.
The reason this pattern is worth committing to memory is that bolting provenance onto a flat fact store after deployment costs roughly 5x what it does to build it at week 2 of architecture — every fact stored in the existing system needs retroactive source attribution, and the longer you wait, the harder the migration gets.
What this means for you
If you are a developer building AI agents with memory, the advice is direct: design your context store as a graph with provenance from day one. Adding temporal validity and source-lineage links later is a migration problem, not a new-feature problem. Graphiti gives you the open-source starting point; Zep gives you the managed version if you do not want to run a graph database yourself.
If you are building agents for regulated industries (healthcare, finance, legal), provenance is not optional. GDPR Article 17 forces a specific technical shape on your context store: you must be able to trace and delete derived data to honor right-to-be-forgotten requests. Auditors are starting to ask for evidence that the chain is intact. Graph provenance is the only known architecture that solves this without rebuilding your agent's memory.
If you are a small business deploying AI agents, you may not need a full knowledge graph today — simple chat history is enough when conversations are shallow. But if your agent accumulates state over time (customer preferences, order history, ticket state), consider storing context in a provenance-modeled structure from the start, even if the bot is modest today. The cost of adding it later increases exponentially with the volume of accumulated context. For more on how AI agents can add up structurally, see our guide on running a small business on AI agents: the delegation framework and stack.
If you are architecting agent memory layers, the key decision is whether you are building a context graph (temporal + provenance) or just a richer RAG pipeline. The latter is easier in the short term but will not answer the trust, debugging, deletion, and compliance questions that are coming for any agent that runs in production with real users. For a deeper look at open-source memory stacks that pair with knowledge-graph approaches, see our coverage of the Nemotron 3 + Qwen 3.8 open memory stack. And for the broader security implications of running autonomous agents — including sandbox escape patterns and the controls that provenance layers help enforce — see our anatomy of the OpenAI-Hugging Face kill chain.
FAQ
Q: What is knowledge graph provenance? A: Knowledge graph provenance is the practice of storing every source datum as a graph node, every derived fact as an edge between entities, and the link from a fact to its source as a relationship. Tracing a fact to its origin becomes a graph walk.
Q: Why can't I just store a source ID on each fact? A: A single source ID breaks when one fact is synthesized from multiple sources, when entities merge and inherit lineage from both originals, or when a fact is contradicted and invalidated by new data. These situations require a graph of lineage links, not a flat foreign key.
Q: How does knowledge graph provenance help with GDPR? A: When a right-to-be-forgotten request requires deleting a source, the lineage graph tells you exactly which facts were derived from that source. Facts with other supporting episodes survive (you just remove the link to the deleted source); facts with no other supporting episodes are deleted entirely. Without provenance, you either delete too much or not enough, and you cannot prove which.
Q: What is the difference between data lineage and provenance? A: Provenance tracks where data originated and how it was created ("where did this come from?"). Lineage tracks the full lifecycle of data through a system ("where did it move, how was it modified, where is it used next?"). Provenance is a subset of lineage; the two terms are often used together because they answer related provenance questions and operate on the same underlying graph structure.
Q: What is Graphiti and how does it implement provenance?
A: Graphiti is an open-source temporal knowledge graph framework from Zep AI (Apache-2.0, at github.com/getzep/graphiti). It models source data as "episodes" — graph nodes stored verbatim. Every entity and fact extracted from an episode links back to that episode, so tracing a fact to its source is a graph walk. Each fact edge also carries valid_at and invalid_at timestamps for temporal validity.
Q: Does knowledge graph provenance work with existing RAG pipelines? A: Yes — provenance models dataset episodes (the retrieved RAG chunks) as source nodes, entities extracted from them as graph nodes, and derived facts as edges with lineage links to the source chunks. Standard RAG pipelines do not retain these links by default, which is why attention migrates to Graphiti-style context graphs rather than plain vector retrieval.
Discussion
0 comments