Citation Needed: Provenance for LLM-Built Knowledge Graphs — Daniel Chalef, Zep AI

So LLMs are really great at pulling together data from many sources, but they do so non-deterministically. They interpret and synthesize data, generating a summary, an extracted fact, a structured record, and this output artifact may not appear verbatim in the source inputs.

Synthesis often destroys the paper trail of how these outputs were originated. And I'm going to be talking today about provenance, which is tracing how an artifact was built and why. Legal compliance often demands provenance, but it's also useful for debugging, deciding which sources you trust and which artifacts to delete.

And solving this at scale presents a real engineering challenge.

If I can get my next slide going here. So my team and I built Graphiti, the open-source temporal graph framework, and Zep, our enterprise agent memory infrastructure, is built on Graphiti. Our customers derive context or agent memory from many user touchpoints.

Those could be chat, but not only chat. Often it's voice transcripts, email, business data. And our customers have struggled with provenance. Where did this fact come from? What is the veracity of this fact? And over the next few slides, I'll share how we engineered solutions to this problem.

So here's a stylized failure mode. An agent retrieves context about a patient. So this is a healthcare scenario. And what comes back is a clean, confident fact: patient has a penicillin allergy. And the context was synthesized from three sources: a lengthy EHR record, electronic health record, a PDF lab report, and something a patient typed into an AI intake chat.

If the agent presents the fact to a doctor in a treatment scenario without clearly indicating the source was from the patient themselves, it may mislead the doctor. When an agent retrieves context, can we point to the exact source and its veracity?

For complex agent applications, the answer is often no.

So I can imagine you're probably thinking, but can we just store a source ID on the fact? This can work well in structured data warehouses or data lakes. A pipeline outputs one value copied or mutated deterministically, and the sources are known and easily marked.

But with context pipelines run by LLMs, this breaks in several ways. You prompt an LLM with several sources. Many facts are each synthesized from one or more of the sources. Somebody like Jay Smith and John Smith are merged into a single entity, one identity, and John's facts are derived from many different places.

So new data might invalidate old facts. The store keeps changing underneath your pointer. And an append-only log, which often might come to mind here, gets very hard to manage at scale as there's so many changes occurring. So lineage needs to be an evolving set and survive mutation.

So sets of links between facts and their sources can be modeled on a graph as relationships. So provenance in a context store containing facts is a knowledge graph. In this example, we have three source data. In Graphiti, they're termed episodes.

We have two entities extracted from the episodes, patient and penicillin, and an edge between them. This graph triple the two entities and the edge can be hydrated as a fact: patient has a penicillin allergy. Tracing a fact to its source is just a graph walk.

So it's pretty simple and easy to map source to fact on the firstright.

But keeping it correct while the graph changes can be really hard. So

for example, when two entities merge, the merged entity needs to keep all source links from both. Otherwise, we silently drop a source and we lose lineage. And when new data contradicts existing data, mutating it, we need to capture this lineage too.

In therightmost card, a fact is rendered invalid by new data. And in Graphiti, an invalid-at date is added to the mutated edge. And the source episodes that resulted in the edge mutating are noted against the fact.

So again, in Graphiti, the relationship between source data and derived artifacts, such as facts, is easily modeled on the graph.

With metadata projection, we can also model classifications that span many different episodes and facts derived from them. And so I'll give you an example here.

In the prior healthcare scenario, episodes may originate from an EHR record and have an EHR tag associated with them, but not all records are. And so on ingestion, we tag the episodes with the EHR tag. All subsequent entities and facts derived from the episode inherit the tag.

And so if the agent wants to retrieve only facts from verified clinical sources, it's very simple to filter for the appropriate tag as we walk the graph. So one tagging action at ingestion supports evaluating the veracity of a fact.

But what if the fact has three parents or more? Here we have a verified flag as our metadata. And in this case, one parent is not verified. So is the fact verified? For the allergy flag, which could be a life and death situation, the agent missing that particular flag could be a deadly mistake.

So not retrieving the fact. And any source of the three should block that prescription being issued. But for something like a consent on file for procedure fact, the mistake is operating on an unverified consent. So the patient hasn't actually given their consent.

And every parent needs to be verified. So every single episode should have that tag. So the facts have very similar shapes. They have three parent episodes, but opposite policies. And here, Graphiti, or the underlying store, exposes that choice.

It exposes which of the episodes have the particular tag. But your agent needs to execute or apply your business rules. So that's not necessarily something that we bake into the graph. It's situational. Another situation where lineage is really important.

We may have to delete source data due to retention policies orright-to-be-forgotten requests, so privacy compliance. And this is really tricky because if we have context derived from multiple sources, how do we do so? Mapping lineage here is really useful.

We know which facts are derived from the source data we intend on deleting. But what if only some of the source data needs to be deleted, but not all? So in this example, we need to delete the intake chart data, so what the patient filled in, which is only one of three source data.

In Graphiti's model, the allergy fact survives the deletion. And that's because there are two parent episodes still supporting the fact. However, the contact preference fact is deleted as it was derived solely from the deleted source data. So the rule is pretty simple here, and it's easier to apply because the link exists.

A fact is only deleted if no remaining episodes support it.

So to sum it all up, deriving context is lossy and generative. Lineage needs to be built into the data structure, engineered into the data structure, which is a graph, not logged afterwards.

And in Graphiti, we keep the sources verbatim, and we link everything derived from those sources back to the source. And provenance offers many benefits to users of Graphiti. You have compliance built in, which makes your chief compliance officer very happy.

You can verify a fact based on its sources. So you understand veracity. Should I trust this fact? It's easy to debug where something came from. So why do I have this fact? How was it generated? And also, determining what to delete.

And most of what I've covered today is in the Graphiti framework. So you can go to

the Graphiti repo on GitHub, and I have a little QR code later that you can zap and try it out. So by the way, as an aside, lineage and provenance is expensive. Graph construction is really expensive in the way that Graphiti does it.

And so we've put significant effort into reducing cost and latency of generating graph artifacts. I'd be happy to speak to how we've done that in the Q&A. So thanks for attending. If you'd like to learn a little bit more about Zep or Graphiti, you can zap the QR codes.

Zep is on the left and Graphiti on theright. And I don't know if we're doing Q&A here or outside.

We could do some.

OK, happy to do Q&A.

Just repeat the question.

Yeah.

We have time.

Anybody have a question? Yeah, oneright from the front.

How do we mutate the graph

at the edge? Oh, to account for weight changes in relevancy?

That is a structure that we've actually built into Zep, not into Graphiti. And

what we do is we do have for that

some tracing that we do, which is kind of X of the graph. So not all of the

provenance is in the graph. Sorry, you?

If you have 50 edges.

If you have 50 edges.

In my editor, 50 edges.

Sorry, was that a question? If you have 50? Oh, there you go.

I said I use 50.

You use 50?

Yeah.

50 edges.

Yeah, edges.

So

Zep is able to look at provenance across those, but using a separate data structure from the graph.

OK, thank you.

For that particular problem.

So does the agent also create the edge types and the entities itself, or how does it resolve those edge types?

Yeah. So in Graphiti, you can search across the entire graph. It has vector similarity search against various textual artifacts, full-text search, as well as graph relational operations, things like BFS. It depends on the underlying graph database that's used.

And so your agent can walk the graph. It can search semantically, et cetera. And obviously, from anywhere you hit in the graph, you're then able to understand the provenance of a particular artifact that you've hit.

I find it very fascinating, this temporal supportright out of the Graphiti database. Can you tell just a little more under the hood, are those really the episodes that are nodes in the graph, just like the other nodes? And how do you extract?

So I saw the API that, let's say, I give some

add episode. How do we extract information from the add episode call under the hood, like large language models and edges?

Yeah, yeah. So yes, episodes are an entity on the graph or a node on the graph. It makes sense to model them that way.

In Zep and Graphiti, we have various derived artifacts that are

nodes on the graph as well because they too need to have lineage, and we need to understand how they were derived. And in terms of how the add episode method works, there's a pretty complicated pipeline that gets run on

episode ingestion. And I'll just give it a very high-level outline for you. So there's a structured extraction, extracting entities and the relationships between them, and candidate facts. And those are the materialized or hydrated fact triples. So two entities and a fact.

And a fact is structured as

subject, verb, object. And after that, there is a deconfliction process that runs, a deduplication and deconfliction process. We deduplicate entities, and we deconflict facts because there might be existing facts in the graph that are going to be mutated by a new learned fact.

So Daniel loves Adidas shoes. Three months later, Daniel's shoes fell apart. He sends the shoes back to the return application, and he sends an osteogram along with it. But now Daniel returned shoes as a fact, and Daniel was unhappy about Adidas.

We need to invalidate the Daniel loves Adidas shoes fact. And so that is part of that pipeline as well. A lot of what we do

uses LLMs, but we try very hard not to use LLMs in this process as well. So where we're able to deploy more traditional information retrieval techniques, more traditional NLP techniques, looking at things like entropy and a bunch of other using sym-hash and a bunch of other approaches to dedupe, we do so.

Far cheaper, far faster, far more deterministic. Hopefully, that answers your question.

Yep. Thank you for the great talk. Just wanted to ask a question. So it seems like a common theme these days in memory systems is more file-based memory and wikis and knowledge bases. And I'm just wondering, is Zep working on something like that?

And also, could some of the ideas here be represented in that paradigm?

Yeah.

Markdown suffers from provenance.

File-based memory starts to break down with provenance. It's very difficult when you mutate lines in a file to understand the lineage or the provenance of why those changes occurred. Not only that, but in multi-agent, multi-user, and multi-source scenarios, it can be very challenging to manage markdown files at scale.

I think they work really well for desktop usage. They sometimes work well in agentic use cases that are server-based, not necessarily desktop or single-user, single-agent scenarios.

But what we found is that

they just break down with the types of enterprise problems that we solve, in particular, provenance as an example. Does that answer your question?

Oh, more. I don't know how much time we have left, but maybe one more.

Just one.

Yeah.

Daniel, thank you. Question on the write-back. How do you do that, explicitly or implicitly? How do you create the facts? Do you ask the LLM to summarize the conversation, or at every turn you do that? And which component does it, Zep, or?

Yeah, so we do. Actually, as part of the extraction, we've managed to get a single-shot extraction working that extracts entities and the relationships between them and facts. And we're able to do so really cheaply as a consequence. And so yes, we're using an LLM for that.

We do have a reflection step or some reflection built in to ensure that the things that we've retrieved are actually accurate, as well as to do some other stuff around

more richness to the lineage. So why did something change? Not just this was related, but also why did it change?

That's partly in Graphiti, partly in Zep.

Yeah. Allright, well, thank you, everybody.