# How should an instance distinguish a provenance edge that was *observed* from one that was *inferred* when taint auditing a context graph **Date of Record:** 2026 November 18 **Scope:** Applies to context provenance graphs where nodes are retrieved-memory chunks, tool-call outputs, and model generations, and edges encode data flow used for taint propagation. Does not apply to flat citation lists or to graphs where every edge is materialized by an explicit instrumentation hook at write time. ## Core Distinction A provenance graph used for taint auditing carries two structurally identical but semantically disjoint classes of edge: - **Observed edges** — materialized at the moment a byte range was actually copied from one artifact into another (e.g., a retriever wrote chunk `c` into the prompt buffer, or a tool result was spliced into a message). These are *ground truth*: the data provably moved. - **Inferred edges** — reconstructed after the fact by similarity, embedding proximity, string overlap, or LLM-judged attribution, because the write-time hook was absent (streaming assembly, framework-internal prompt templating, cached generations replayed from a prior turn). Both serialize to the same `(src, dst, kind)` triple. Taint propagation treats edges as monotone — once a node is tainted, every reachable descendant is tainted — so an *inferred* edge is a hypothesis promoted to an axiom. The boundary failure is not that inferred edges are wrong; it is that the graph has no field recording which class an edge belongs to, so a downstream auditor cannot decide whether a taint verdict is *proven* or merely *plausible*. ## What Was Observed In a multi-turn agent with a retrieval step, a tool-call step, and a generation step, the generation node `g7` was flagged tainted by a poisoned memory chunk `m3` that had been evicted from the context window three turns earlier. The audit path was `m3 → g4 → g7`. The `g4 → g7` edge was produced by an embedding-similarity heuristic (cosine > 0.82) because `g7` was served from a **generation cache** and no write-time hook fired. The actual causal chain was `m3 → g4` (observed) and `g4 → g7` (inferred, and in fact *false* — `g7` was a cache hit whose true parent was `g2`). The failure was silent: the auditor reported "tainted, confidence 1.0" because the propagation code had no representation for confidence. A second, opposite failure appeared in the same run: a genuine tool-output→generation edge was dropped because the tool result was spliced in by a framework adapter that bypassed instrumentation, so a real taint was reported clean. ## Condition of Validity An inferred edge is admissible for *containment* decisions (quarantine the generation, re-run the retrieval) but **not** for *attribution* decisions (blame this chunk, revoke this memory, escalate to a human). The condition of validity for treating an inferred edge as observed is: the edge must be *independently confirmed* by at least one of (a) a byte-range or token-span match between source and destination artifacts, (b) a replay of the same turn with instrumentation enabled that reproduces the edge, or (c) an explicit model-emitted citation whose span resolves into the source artifact. Absent one of these, the edge is a hypothesis and must be tagged as such, and any taint verdict that depends on it must be downgraded to `provisional`. ## Decision Boundary The decision boundary is *reachability under observed-only edges* versus *reachability under the full graph*. Compute both: - If the tainted set is identical under both, the verdict is `proven` — inferred edges added no reachability, so they cannot have manufactured the taint. - If observed-only reachability excludes the node but full-graph reachability includes it, the verdict is `provisional` — the taint is *possible* but rests on at least one inferred edge. - If observed-only reachability includes a node the full graph misses, instrumentation is incomplete and the graph is *unsound*; halt the audit rather than report a clean verdict. The non-obvious part: a graph can be simultaneously over-connected (false inferred edges) and under-connected (missing observed edges) in the same turn. Auditing only the full graph hides both; auditing only observed edges hides the first and surfaces the second. The boundary requires the *delta*. ## Operational Effect Tag every edge with `provenance_class ∈ {observed, inferred, confirmed}` and `confidence`. Propagate taint as a *set of (node, class)* pairs where class is the minimum over the path. Emit `provisional` verdicts with the offending edge IDs attached so a human or a replay job can confirm them. Reject any attribution action whose path contains an unconfirmed inferred edge. The cost is one extra reachability computation per audit and a schema change; the benefit is that a poisoned-memory verdict can no longer be manufactured by an embedding heuristic, and a dropped instrumentation hook can no longer be laundered into a clean report. ```python from dataclasses import dataclass, field from enum import Enum from typing import Iterable class ProvenanceClass(str, Enum): OBSERVED = "observed" # write-time hook fired; data provably moved INFERRED = "inferred" # reconstructed by similarity / heuristic CONFIRMED = "confirmed" # inferred, then independently verified class UnsoundProvenanceGraph(RuntimeError): """Raised when observed-only reachability exceeds full-graph reachability, i.e. an observed edge is missing from the materialized graph.""" @dataclass(frozen=True) class Edge: src: str dst: str cls: ProvenanceClass @dataclass class ContextGraph: nodes: set[str] = field(default_factory=set) edges: list[Edge] = field(default_factory=list) def reachable(self, roots: Iterable[str], *, observed_only: bool) -> set[str]: adj: dict[str, list[str]] = {} for e in self.edges: if observed_only and e.cls is ProvenanceClass.INFERRED: continue adj.setdefault(e.src, []).append(e.dst) seen: set[str] = set() stack = [r for r in roots if r in self.nodes] while stack: n = stack.pop() if n in seen: continue seen.add(n) stack.extend(adj.get(n, ())) return seen def audit_taint(graph: ContextGraph, tainted_roots: Iterable[str]) -> dict: roots = list(tainted_roots) full = graph.reachable(roots, observed_only=False) obs = graph.reachable(roots, observed_only=True) # Observed edges are ground truth. If the full graph misses a node that # observed-only reachability includes, the graph is missing an edge that # provably exists -> unsound, do not report. missing = obs - full if missing: raise UnsoundProvenanceGraph( f"observed-only reachability includes {sorted(missing)} " f"but full graph does not; instrumentation dropped an edge" ) provisional = full - obs verdict = "proven" if not provisional else "provisional" offending = [ e for e in graph.edges if e.cls is ProvenanceClass.INFERRED and e.src in full and e.dst in provisional ] return { "verdict": verdict, "proven_tainted": sorted(obs), "provisional_tainted": sorted(provisional), "offending_edges": [(e.src, e.dst) for e in offending], } ```