Part IV · Graphs and AI

Trustworthy AI, One Graph at a Time

Created by Felipe Casadei

AI systems state false facts with confidence, hide their reasoning, and act without a paper trail. Nearly every working fix for these trust failures is built on the mathematics of this course: after this chapter you will be able to read current research on AI reliability and recognize the graphs doing the work.

The trust problem, drawn as a picture

A large language model (LLM), the kind of system behind chatbots such as ChatGPT and Claude, has a trust problem with several distinct faces. It states false facts fluently and confidently, a failure the field calls hallucination. Its reasoning happens inside billions of numerical weights, where no one can watch it. When it cites sources, the citations often fail to support the claims they are attached to. It learns which things go together, not which things cause which, so its decisions can break the moment circumstances change. And when it acts as an autonomous agent, browsing the web, writing files, and running code on your behalf, it is hard to establish afterwards what it did and whether it was allowed to do it.

Over the last three years, a pattern has emerged in the research aimed at each of these failures. The leading fixes are built on graphs. Not graphs in the everyday sense of bar charts, but graphs in exactly the sense of this course: vertices and edges, paths and trees, directed acyclic graphs, cuts and separators, even lattices. Facts become labeled edges that can be checked one at a time. Reasoning becomes a directed graph whose vertices can be re-verified. An agent's actions become a graph in which "could the secret have leaked?" is a question about directed paths. The inside of the model itself is now being extracted as a weighted graph of cause and effect.

One honest warning before we start, and we will return to it at the end. A graph is scaffolding for verification, not a magic fix. Turning an answer into a graph does not make the answer true; it makes the answer checkable, which is a different and more modest thing. Every system in this chapter still depends on the quality of the graph it builds and on someone actually doing the checking.

This chapter visits six research fronts: grounding answers in knowledge graphs, fact-checking output edge by edge, structuring the model's reasoning as a graph, recording provenance, reasoning about causes with directed acyclic graphs, and reading the model's internal circuitry as an attribution graph. Along the way we pick up the auditing of AI agents and a fifty-year-old lattice model of security that has found a second life. Chapter 13 introduced graphs as the substrate of modern AI; Chapter 14 covered retrieval over knowledge graphs in depth. This chapter is about trust.

New notation in this chapter

Everything here runs on directed graphs, so most of the new notation is directed vocabulary, plus two imports from neighbouring fields: probability's independence symbol and order theory's lattice operations.

We freely reuse earlier notation with a one-clause reminder at first use: \(V(G)\) and \(E(G)\) for vertex and edge sets, \(N(v)\) for the neighbourhood of \(v\), and the structural vocabulary of paths, cycles, trees, bipartite graphs, cuts, and separators from Chapter 1 through Chapter 3.

Grounding: facts as labeled edges

Why do language models hallucinate about facts at all? Because of where their facts live. A model's knowledge is smeared across billions of numerical parameters. There is no address where "the capital of Australia" is stored, no way to update that one fact cleanly, and no mechanism that stops the model from producing a plausible-sounding invention in the same fluent voice it uses for the truth.

The triple (Canberra, capital_of, Australia) is an edge from the vertex Canberra to the vertex Australia, labeled capital_of. A compound fact is a walk. "The capital of the country where the Sydney Opera House stands" is a walk of length two: follow the located_in edge from the Opera House to Australia, then the capital edge from Australia to Canberra. Large public knowledge graphs such as Wikidata and DBpedia store facts about the world in exactly this form^[1].

An influential roadmap paper by Pan and colleagues frames the two technologies as complements^[1]. Language models are general and fluent but opaque and unreliable about facts. Knowledge graphs are explicit, structured, and auditable but rigid and incomplete. The paper maps three ways to combine them: feed the graph into the model, use the model to build and query the graph, or wire the two together so each checks the other. A survey by Agrawal and colleagues, focused specifically on hallucination, organizes graph-based defenses by where the graph enters the pipeline: during training, during answering (retrieval), or after generation (verification)^[2].

Figure 15.1 shows the core idea. An ungrounded model maps a prompt straight to an answer, and the answer hangs in the air: there is no object you can point at to ask "supported by what?". A grounded model consults a knowledge graph, and its answer arrives attached to a path. Every hop of the path is an edge someone can check.

Two concrete systems show the flavor. Microsoft's GraphRAG, the subject of Chapter 14, extracts an entity graph from a document collection, detects communities in it (vertex sets with many internal edges and few edges leaving, the intuition behind the cuts of Chapter 3 and Chapter 6), and answers broad questions from per-community summaries^[3]. Think-on-Graph goes further: it makes the model an agent that walks the knowledge graph itself, running a beam search over the graph's edges, keeping the most promising reasoning paths alive at each step, and returning its final answer together with the path that justifies it. Its authors call the property "knowledge traceability": a human expert can look at the returned path and check every hop^[4].

Catching a hallucination edge by edge

Grounding tries to prevent hallucination before it happens. Verification catches it afterwards. The move is the same in both directions: translate prose into edges, because edges can be tested one at a time while a paragraph can only be eyeballed as a whole.

FactKG is a benchmark built for the direction "check a claim against a big trusted graph": 108,000 natural-language claims, each to be verified against a knowledge graph^[6]. Its designers deliberately spread the claims across five reasoning types, and every one of them is a graph query you can already name. One-hop: does this single edge exist? Conjunction: do all of these edges exist? Existence: does any edge with this label leave this vertex? Multi-hop: is there a path with these labels? Negation: is this edge absent?

GraphEval flips the direction^[5]. Instead of checking against a public graph, it converts the model's own output into a small knowledge graph, then tests each triple of that graph against the context the model was given: is this edge entailed by the source text or not? Because the verdict attaches to individual edges, the system can point at which edge is hallucinated rather than flagging the whole paragraph. The same paper adds GraphCorrect, which repairs the flagged edges and reports that most hallucinations it finds can be fixed in place^[5].

In course terms, claim verification is subgraph matching: does the claim graph embed in the trusted graph? One-hop verification is edge membership. Multi-hop verification is the existence of a path with prescribed labels, a constrained cousin of the connectivity questions of Chapter 3. And there is a covering condition hiding here, in the sense of Chapter 2: put the generated claims on one side of a bipartite graph and the retrieved evidence passages on the other, with an edge when a passage supports a claim. "The answer is fully supported" says the support edges cover the claim side.

Chains, trees, and graphs of thought

So far the graph has lived outside the model, as a store of facts. The next idea moves it into the model's reasoning process itself, and the progression reads like the opening of Chapter 1: first a path, then a tree, then a directed acyclic graph.

Ask a model to "think step by step" and you get chain-of-thought prompting, introduced by Wei and colleagues: the model writes intermediate reasoning steps before its final answer, and this measurably improves performance on arithmetic, commonsense, and symbolic reasoning tasks^[7]. Structurally, a chain of thought is a path. Each thought has one predecessor and one successor. There is no way to consider an alternative and no way to back up from a mistake: one bad step early poisons everything after it.

Tree of Thoughts, by Yao and colleagues, fixes the no-backing-up problem^[8]. The model proposes several candidate next thoughts (branching), scores how promising each one looks, and explores the resulting tree with lookahead and backtracking, exactly like a search tree in classical algorithms. On tasks that genuinely require search the gains are dramatic. On the Game of 24 puzzle, where four numbers must be combined with arithmetic to reach 24, GPT-4 with chain-of-thought prompting solved 4% of instances; the tree-based search solved 74%^[8].

Graph of Thoughts, by Besta and colleagues, takes the final step: thoughts are vertices, dependencies between thoughts are edges, and the structure is an arbitrary directed graph^[9]. The new power is merging. Two lines of reasoning developed independently can be combined into a single thought, which is a vertex with in-degree \(d^-(v)\ge 2\), and a thought can be refined through feedback loops. On a sorting task the authors report 62% higher output quality than tree-of-thoughts alongside a cost reduction of more than 31%^[9]: extra edges buy reuse of intermediate work.

Why does this matter for trust, and not just for benchmark scores? Because an explicit reasoning graph is inspectable. You can see exactly which intermediate results fed the final answer, re-verify any single vertex, and after fixing one, re-run only \(\mathrm{Desc}(v)\), the part of the computation downstream of the fix. Deciding what to compute first is a topological ordering of the dependency graph, the directed acyclic graph (DAG for short: a directed graph with no directed cycle) whose existence of a valid order is guaranteed exactly by acyclicity. A hidden chain of activations offers none of this. A drawn graph of thoughts offers all of it.

Provenance: the graph behind a citation

A trustworthy answer is not just correct. It is checkably correct, which requires a record of support: this claim rests on that passage, which came from that document, which was retrieved by that query. Such a record is naturally a directed graph.

How badly is this record needed? Gao and colleagues built ALCE, the first benchmark that requires models to generate answers with inline citations and then automatically scores whether the cited passages actually support the cited claims^[10]. The sobering headline: even the best model they tested lacked complete citation support roughly half the time on some datasets. In graph terms, the claim-to-source edges that models emit are frequently wrong or missing, so the bipartite claim-source graph (claims on one side, passages on the other, in the sense of Chapter 2) cannot be taken at face value; it has to be measured and repaired.

For full AI agents the stakes rise, because the run involves actions, not just sentences. A 2026 survey by Wang and colleagues argues that "final-answer accuracy alone cannot explain how an output was produced," and reviews execution provenance: recording an agent's entire run, its retrievals, tool calls, memory reads and writes, and intermediate claims, as one typed directed graph^[11]. Once the run is a graph, auditing becomes graph analysis, and each audit question is one you can already state precisely. Which evidence is the answer derived from? That is \(\mathrm{Anc}(a)\), the set of vertices with a directed path to the answer vertex \(a\). Did any untrusted input influence a critical action? That asks whether a directed path exists from a tainted vertex to the action vertex. Where did a failure originate? Walk the ancestors of the bad output.

The certification direction deserves its own sentence, because it is Menger's theorem wearing work clothes. To prove an answer cannot be tainted, show there is no directed path from any untrusted vertex to the answer; equivalently, exhibit a separator, a set of checked vertices meeting every such path. That every-path-meets-the-cut logic is exactly the connectivity duality you learned in Chapter 3^[20].

Causal graphs: surviving change

The trust failures so far were about facts and records. A deeper one is about the difference between correlation and cause. A model trained purely on observed data learns which things go together. Ice-cream sales and drowning deaths rise together every summer; a correlational model happily learns the association, and a decision system built on it might conclude that banning ice cream would save swimmers. What is missing is a way to represent "Season causes both" and to reason about what changes when you intervene. Judea Pearl's framework does exactly this, and its central object is a graph.

The graph-theoretic engine of the framework is d-separation, a purely structural rule that reads independence off the picture. A path between two variables transmits association unless it is blocked. An ordinary vertex on the path blocks it once you condition on that vertex, that is, hold it fixed. A collider, a vertex where both path edges point inward, does the opposite: it blocks the path by default and opens it when conditioned on. Working out which variables to hold fixed, so that all spurious paths between a treatment and an outcome are blocked while the genuine causal paths stay open, is pure path analysis on a DAG. In our example, the path IceCream \(\leftarrow\) Season \(\rightarrow\) Drownings is open, which is why the two correlate; conditioning on Season blocks it, giving IceCream \(\perp\) Drownings \(\mid\) Season ("ice cream is independent of drownings once season is held fixed").

Two verified research threads connect this machinery to AI trust. Kaddour and colleagues survey causal machine learning: using a causal graph plus equations (a structural causal model) to make models robust to distribution shift, to make generative models controllable by intervention, to make explanations counterfactual ("what would the decision have been had the applicant's income differed?"), and to make fairness claims formally analyzable^[13]. And Kıcıman and colleagues tested whether language models can do causal reasoning themselves: GPT-4 reached 97% accuracy on pairwise causal-discovery questions and 92% on counterfactual reasoning benchmarks, far above earlier methods, yet the same paper documents unpredictable failure modes and notes that the models "ignore actual data"^[12]. Their proposed synthesis is a division of labor: let the fluent-but-fallible model help human experts draft the causal DAG from domain knowledge, then let the sound-but-narrow graph machinery do the rigorous inference. The graph is the interface between the two kinds of system.

Neurosymbolic welds

That division of labor has a name. Neurosymbolic AI combines neural networks, which are good at perception and language but offer no guarantees, with symbolic reasoning, meaning logic, rules, constraint solving, and graph algorithms, which offer guarantees but cannot read raw text or pixels. The trust argument is direct: if the final answer is produced or checked by a symbolic component, you can verify it and prove properties about it, whatever the neural part did internally. The knowledge-graph systems earlier in this chapter are neurosymbolic in spirit: Think-on-Graph is a neural model steering a symbolic search over an explicit graph^[4], and the "synergized" category of the Pan roadmap describes designs where neural and graph components check each other^[1].

How much of the field aims at trust? A systematic review by Colelough and Regli analyzed 167 peer-reviewed neurosymbolic papers from 2020 to 2024 and sorted them by focus (papers can count in more than one category): 63% work on learning and inference and 44% on knowledge representation, while explainability and trustworthiness sit at only 28%, and meta-cognition, systems that know what they know, at 5%^[14]. The authors flag the gap as the field's opportunity: the machinery for verifiable hybrid reasoning exists, but few groups aim it at trust.

For you, the striking fact is how regularly symbolic problems compile to graph problems you have studied. Constraint satisfaction relates to the colouring of Chapter 5: assigning values to variables so that constrained pairs differ is graph colouring, which is why compilers colour interference graphs to allocate registers. Logical entailment over a rule base is reachability in an implication graph. Aligning the entities of a generated answer with the entities of a knowledge graph is a matching problem in a bipartite graph, the territory of Chapter 2. And the lesson of Chapter 12 applies with full force: many hard symbolic problems become tractable when their constraint graphs are tree-like, which is why solvers care intensely about tree-width.

Watching the agent: action graphs and permission lattices

An AI agent is a model wired to tools: it can browse, write files, run code, send messages. This changes the question from "is the answer right?" to "were the actions safe and authorized?" Three graph structures organize the current answers.

The first we have met: record the whole run as an execution-provenance DAG^[11]. Dependency edges answer operational questions directly. What would re-running this step invalidate? \(\mathrm{Desc}(v)\), its descendants. What influenced this dangerous command? \(\mathrm{Anc}(v)\). Is there a valid order to execute pending tasks? Yes exactly when the dependency digraph is acyclic, in which case a topological order exists; a directed cycle among tasks is a deadlock, and cycle detection finds it.

The second is runtime rule enforcement. AgentSpec, by Wang, Poskitt, and Sun, to appear at the International Conference on Software Engineering (ICSE) 2026, is a small language for rules of the form trigger, predicate, enforcement, which sit between the agent and the world^[15]. Rules watch the stream of proposed actions and block, modify, or demand user confirmation for unsafe ones ("on file-delete outside the workspace: require confirmation"). In effect the rules define which paths through the agent's action space are permitted: a reachability constraint imposed on the action graph before the actions happen, where provenance audits it after.

The third structure is the oldest idea in this chapter. In 1976, Dorothy Denning published a lattice model of secure information flow^[16], and fifty years later it fits AI agents as if made for them.

Denning's rule is one sentence: give every security class a place in a lattice, and let information flow only upward. She showed that this single structural condition unifies the security mechanisms of real systems and supports automatic certification of programs^[16]. For an AI agent: give the agent a class, give every resource a class, and permit an action exactly when the lattice order allows the flow. The Hasse diagram is a concrete DAG you can draw, audit, and prove things about.

Certification is once more a cut argument. To certify that an agent with Secret access can never leak to a Public channel, show the information-flow graph contains no directed path from any Secret-classified vertex to any Public-classified sink; equivalently, exhibit a separating set that every such potential path must cross. It is the same Menger-flavored move as the provenance audit^[16][20], which is no coincidence: leak-freedom and taint-freedom are both non-reachability claims.

Opening the model: attribution graphs

Everything so far treats the model as a black box and builds graphs around it. The most direct attack on opacity opens the box: extract the model's own computation, for a specific prompt, as a graph.

This is the method of Anthropic's circuit-tracing work^[17]. The raw graph for a single prompt has millions of edges, so the pipeline prunes it to the small high-impact subgraph a human can actually read, then validates the resulting story by perturbation: artificially suppress a feature and check that the downstream effects the graph predicts actually occur. Pruning has a Chapter 6 flavor: think of influence as a flow from the input vertices to the output sink, and keep the edges whose removal would drop that flow most. And the reason pruning is mandatory rather than cosmetic is a Chapter 4 fact of life: a drawing of a million-edge graph is an unreadable mat of crossings, so interpretability at scale is also a graph-summarization problem.

The companion paper, "On the Biology of a Large Language Model," applies the method to Claude 3.5 Haiku and reads real mechanisms off the graphs^[18]. Three findings are worth carrying with you. First, multi-hop reasoning: asked for the capital of the state containing Dallas, the model's graph shows an intermediate Texas feature between the Dallas input and the Austin output, evidence of genuine two-step computation rather than a memorized shortcut. Second, planning: at the start of a line of poetry, features for candidate rhyming words at the line's end are already active, and they shape the words chosen in between. Third, hallucination mechanics: the model carries a default "can't answer" circuit that is suppressed by "known entity" features, and hallucinations occur when that suppression misfires. Notice what the third finding is: a mechanism-level diagnosis of the failure this chapter opened with, and one you could only state with the graph in hand.

Dwell on the shape of that experiment. The claim "the model computes Dallas \(\to\) Texas \(\to\) Austin" is the claim that the computation contains a directed path of length 2 through an intermediate vertex. The validation deletes the middle vertex and watches the output change: a one-vertex separator argument, in the exact sense of Chapter 3, carried out on the internals of a running model. The interpretability frontier speaks the language of this course with almost no translation.

What graphs do not fix

This chapter has been enthusiastic, so its last section owes you the other side of the ledger. Graphs make AI checkable. They do not make it correct, and the gap between those two words is where engineering judgment lives.

First, a graph is only as good as its construction, and the graph is often built by the same kind of fallible model it is meant to police. GraphRAG's entity graph is extracted by a language model^[3]; GraphEval's triples are extracted by one too^[5]. An extraction error becomes a wrong edge, and every downstream verification inherits it. Second, grounding shifts trust rather than eliminating it: an answer traced to a knowledge-graph path is only as trustworthy as the graph's curators, and knowledge graphs are incomplete, sometimes stale, and occasionally wrong. Third, formal guarantees cover only what is modeled. A permission lattice certifies flows in the graph you drew; a side channel you did not draw is invisible to it. AgentSpec blocks the unsafe actions its rules describe, and the authors report over 90% prevention, not 100%^[15]. Fourth, causal conclusions are conditional on the DAG being right, and the DAG usually encodes human assumptions; the Kıcıman results show models can help draft it but cannot yet be trusted to certify it^[12]. Fifth, attribution graphs explain one prompt at a time, after aggressive pruning; the pruned residue and the error vertices are honest admissions that part of the story is missing^[17].

What you should carry out of this chapter is a translation table. Hallucination control is edge verification. Reasoning structure is the path-tree-DAG hierarchy. Citation quality is a bipartite covering condition. Audit is reachability; safety certification is a cut; scheduling is topological order; intervention is edge deletion; a mechanism claim is a directed path, tested by removing a separator. You built all of these tools in Chapters 1 through 12 on small graphs you could draw by hand. The systems in this chapter apply them, unchanged, to the question of whether machines that talk can be made to answer for what they say. That question is open. The vocabulary it will be settled in is the one you now speak.