Keep Your Receipts: Trustworthy Cleanup of Agent-Built Knowledge Graphs

Vishisht Choudhary

cs.AIOct 13, 2026

Keep Your Receipts: Trustworthy Cleanup of Agent-Built Knowledge Graphs

Authors: Vishisht Choudhary

Organizations: Technical University of Munich

Abstract

Agents build knowledge graphs as memory, and building them has become easy. Maintaining them has not. When a source is retracted, overruled, or erased, everything built on top of it (entity merges, entailed edges, community summaries) must be re-examined, and the maintainer must choose between deleting too much and too little. Deployed pipelines delete only the directly extracted facts: on our corpus that reduces contaminated queries from 32.2% to 28.0% under a real retraction and changes nothing under predicate revocation. Rebuilding is no repair for a constructor that samples: two builds of the same 300-document corpus differ in 29,475 artifacts, five times the 6,248 that removing the 61 retracted documents changes. PolyGraph instead asks the constructor for receipts: for every artifact, alternative bundles of source evidence, each claimed sufficient on its own, emitted in the call that creates it. Cleanup is then set arithmetic over the receipts, with no model calls. Because receipts are the model's own self-report, a re-derivation audit checks them by deleting the cited evidence and testing whether the constructor still produces the artifact. The audit finds that a receipt is trustworthy when it is shaped like the claim it backs. Merge receipts, each backing one narrow claim, agree with re-derivation 68% and 85% of the time. Summary receipts, elicited per sentence but stored as one flat list for the whole text, are wrong about two thirds of the time, almost always by keeping dead content. One receipt per sentence instead is 100% and 88% faithful and lets cleanup keep 33 of 35 touched summaries. The result holds under a second oracle model, a claim-blind prompt, ten further deletions, a second domain and a second constructor. Distrusting the summary layer cuts contaminated queries to 0.4% and 0.8% at 99.8 to 100% of the recall a perfect maintainer would return.

Figures & tables

Panel of Figure 1 — Figure 1: Two real chains from the corpus. Deployed deletion removes only the extracted claims (dashed). The entity merge keeps one evidence source from a paper that still stands, so it is correctly retained (green); five of five re-derivations agree. The entailed edge and the summary rest only on retracted evidence, mention no retracted paper, and keep reaching the retriever (red). Support labels delete the edge with one disjointness test. The summary’s label wrongly claims it still stands, the failure Section 6 measures; the layered policy of Section 6.4 removes it.

Panel of Figure 2 — Figure 2: The audit as a classroom exercise, and its protocol translation (italics). A report claims wolves live in Duisburg on the strength of two books, each sufficient alone. When book A is retracted, the audit does not argue with that receipt: it removes book A and has the passage rewritten five times from book B only. Whether the wolves come back decides whether the sentence stays; the receipt does not.

layer	resampling floor	effect of the deletion	ratio
all artifacts	29,475	6,248	0.21
claims	3,294	506	0.15
merges	236	54	0.23
entailed edges	25,826	5,647	0.22
summaries	119	41	0.34

Table 1: Symmetric difference in artifacts. The floor is

|G_{1}\triangle G_{2}|

for two independent builds of the same unchanged corpus; the effect is

|G_{1}\triangle G_{3}|

, where

G_{3}

omits the 61 retracted documents.

operation	layer	$n$	agreement	leaky	over-deleted	undecided
retract-source	merges	21	68.4%	21.1%	10.5%	2
retract-source	summaries	7	33.3%	66.7%	0.0%	1
revoke-relation	merges	29	84.6%	11.5%	3.8%	3
revoke-relation	summaries	25	36.4%	63.6%	0.0%	3

Table 2: Self-reported labels graded against re-derivation (

R=5

\tau=0.2

). Every model-authored artifact touched by the deletion was adjudicated, so rows are populations;

n

counts touched artifacts and undecided ones are listed separately. Leaky : label says alive, re-derivation says dead. Entailed edges are re-derived symbolically, agree by construction, and are excluded. Summary rows use the pipeline’s original summary prompt, which asks for support per sentence but stores one flat label for the whole summary; Table 3 varies that format.

operation	receipt format	$n$	agreement	leaky	over-deleted	undecided
retract-source	flat	7	33.3%	66.7%	0.0%	1
retract-source	whole summary	7	100.0%	0.0%	0.0%	0
revoke-relation	flat	25	36.4%	63.6%	0.0%	3
revoke-relation	whole summary	26	90.5%	0.0%	9.5%	5
retract-source	sentence-level	62	100.0%	0.0%	0.0%	1
revoke-relation	sentence-level	124	87.6%	4.1%	8.3%	3

Table 3: Summary receipts under three elicitation formats, on the same 59 communities, deletions, re-derivation prompt,

R

and

\tau

. Flat is the original prompt of Table 2 : support asked per sentence, one flat list of alternatives stored for the whole summary. Whole summary asks only for sets that each support the entire summary; under it 10 of 59 summaries list more than one support set, against 46 of 59. Sentence-level elicits one list of alternatives per sentence, and the last two rows audit each touched sentence as its own artifact, so

n

counts sentences.

	retract-source		revoke-relation
policy	tainted@10	recall@10	tainted@10	recall@10
no verification, no cascade (deployed)	28.0%	89.3%	36.8%	86.8%
trust all labels	0.8%	99.9%	2.1%	99.8%
distrust the failing layer	0.4%	99.9%	0.8%	99.8%

Table 4: Retrieval-level consequence of the verification verdict. BM25,

k{=}10

, 300 MeSH-descriptor queries; truth is the re-derivation oracle. “Deployed” deletes only claims whose every asserting source is withdrawn, which is what current pipelines do. “Distrust the failing layer” applies the Table 2 verdict: summary labels are ignored and touched summaries are removed outright.

Explore similar work

Aug 17, 2026

Quipu: A Governed Bitemporal Knowledge Graph Store

Agents now write knowledge graphs, but knowledge-graph stores still carry defaults set when humans curated them: accept writes now and clean later, keep one time axis or none, treat every writer's facts as equally trustworthy, and leave governance to dashboards and middleware. These four defaults are individually convenient and jointly untenable under agent workloads. We present Quipu, an embeddable store that inverts all four: no fact enters except through a gate whose predicates evaluate the pending post-state; data, trust labels, verdicts, and the rules themselves are bitemporal; named graphs are the unit of authority and trust, composed under a lattice whose one invariant is that composition never widens; and the governance specification

Σ

, the trace, and signed verdicts are facts in the store they govern, making the audit

T \models Σ

a query. We evaluate with Census, a deterministic multi-writer lifecycle whose single seeded run scores every research question against planted ground truth: the gated store ends with 0 of 6 planted defects versus 6 of 6 ungated; all 7 composition probes uphold the lattice contract; 50 of 50 satisfied verdicts re-derive faithfully as of their instant while all 50 would be misreported under a latest-only rule set; and the SARC reference checker agrees with the in-store audit verdict-for-verdict, differing only on coverage semantics. A recorded trace from a governed writer surfaces a live enforcement gap the audit names with its remediation. On DEMM-Bench, an external decision-evidence sufficiency benchmark, a content-only reading of the exported records answers all 512 property-level governance questions correctly with zero overclaim under all eight degradation conditions, while container-presence baselines overclaim on up to 87.5% of them -- and the run surfaced, and led us to close, a gap in what a denial's verdict attests.

Steve Brown

Knowledge Graphs Temporal KGs AI Agent Governance Data Provenance

Ask PDF

May 14, 2026

Why Neighborhoods Matter: Traversal Context and Provenance in Agentic GraphRAG

Retrieval-Augmented Generation can improve factuality by grounding answers in external evidence, but Agentic GraphRAG complicates what it means for citations to be faithful. In these systems, an agent explores a knowledge graph before producing an answer and a small set of citations. We frame citation faithfulness as a trajectory-level problem: final citations should not only support the answer, but also account for the graph traversal, structure, and visited-but-uncited entities that may influence it. Through controlled ablation experiments, we compare the effects of isolating, removing, and masking cited and uncited graph entities. Our results show that cited evidence is often necessary, as removing it substantially changes answers and reduces accuracy. However, citations are not sufficient, because accurate answers can also depend on uncited traversal context and surrounding graph structure. These findings suggest that citation evaluation in Agentic GraphRAG should move beyond source support toward provenance over the broader retrieval trajectory.

Riccardo Terrenzi, Maximilian von Zastrow, Serkan Ayvaz

Centre for Industrial Software, University of Southern Denmark, Alsion 2, 6400 Sønderborg, Denmark

Data Provenance Graph Retrieval-Augmented Generation Citation Verification RAG Evaluation

Ask PDF

Aug 13, 2026

Reconcile Once, Write Anytime: A Trust-Tiered Librarian and a Multi-Agent Writer for Drift-Free, Point-in-Time Research

Long-form research reports generated by large language models drift, contradict themselves, and lose provenance: the same metric appears with different values, and rumor is quoted as confidently as an audited filing. We present a two-tier agentic system that separates a maintained, point-in-time knowledge library from report writing. A deterministic "librarian" ingests timestamped sources into a trust-tiered ontology, layering evidence cards, an authoritative metric ledger, and a claim graph into an always-current source of truth, not per-query RAG over raw chunks. A portable multi-agent "writer" runtime then composes a contradiction-free, evidence-grounded report at any knowledge cutoff T, reading only evidence with as_of <= T (no look-ahead); red-team verdicts flow back into the librarian. We evaluate on a self-collected, public corpus of 6,130 sources yielding 555,926 evidence cards (SEC EDGAR filings across 295 issuers and 11 sectors, U.S. Bureau of Labor Statistics releases, and Wikipedia). From the one library we compose four point-in-time reports on distinct theses and run eight reproducible experiments, whose headline metrics come from a deterministic quality-control gate, itself validated by defect-injection meta-evaluation at recall 1.0 and precision 1.0. A shared metric ledger removes 6,845 cross-section contradictions to zero. Tier-first selection is correct on 22/22 gold cases where a popularity-first baseline scores only 9/22; trust tiering leaks zero media-sourced numbers, and no government statistic displaces a company's own filing. A red-team refutation propagates back and self-corrects a later run with zero manual edits. Replay exhibits zero look-ahead violations across seven cutoffs while the library grows from 235,373 to 555,312 cards. Difficulty-tiered model routing exceeds the all-Opus quality ceiling while running 3.7x faster than serial.

Xing Zhang, Yanwei Cui, Guanghui Wang +1

AWS Generative AI Innovation Center

Long-Form Document Generation Data Provenance Language Modeling Evidence-Grounded Generation LLM Agent Reliability

Ask PDF