Bounding Path-Level Error in LLM-Built Knowledge Graphs

Large language models now build knowledge graphs directly from text. A knowledge graph here is a network of facts stored as (subject, relation, object) triples. A model reads a document, writes out the triples, and a second model acting as a judge, the "LLM-as-a-judge" pattern, throws away the triples it thinks the text does not support. The trouble is that nobody can say how wrong the surviving graph is. Filtering judges give a yes/no per triple with no stated error rate. Even a guarantee per triple would describe the wrong object, because people use these graphs by following chains of edges, and a chain is wrong if any one of its edges or any of its node-merging decisions is wrong. A single false merge of two different people named "J. Smith" can corrupt hundreds of paths while touching zero individually checked triples.

We propose to calibrate the judge so that the error rate of the paths a downstream user will actually traverse stays below a target $\alpha$, with a finite-sample statistical guarantee. The calibration treats whole documents, not triples, as the unit of exchangeability, because errors within a document are correlated. It also judges entity merges alongside edges. The two-sentence version: today's graph filters certify nothing, and certifying triples is not enough, because hallucinated facts show up and spread at the level of paths and merged nodes. We set judge thresholds on held-out documents so that the share of corrupted short paths is provably below a chosen limit, and we measure how much true content that costs.

Core Claim

Two things should hold. First, a graph filtered so that at most $\alpha$ of its triples are unsupported will have a path-level error rate well above $\alpha$, and above what a naive independence calculation predicts. The reason is that judge mistakes concentrate on high-degree entities and on entity resolution, so they spread through many paths. Second, calibrating directly on a path-level loss, over thresholds for both edges and merges, keeps realized path error at or below $\alpha$ across random calibration splits. It should also keep more supported edges than the conservative fix of tightening the per-triple threshold to $\alpha/k$ for $k$-hop paths.

If the first prediction fails, so that triple-level control already bounds path error in practice, the proposal reduces to an application of existing calibration. We would report that as the main finding.

Relation to Prior Work

The proposal reuses a method from one line of work and applies it to a weakness in another.

Can LLMs be Good Graph Judge for Knowledge Graph Construction? (GraphJudge) has GPT-4o-mini extract triples from denoised text. A LLaMA-2-7B judge, fine-tuned on entity-swapped negatives, then keeps or drops each triple. It reports the best F1 on REBEL-Sub, GenWiki, SCIERC and Re-DocRED. GraphJudge supplies our extractor and our strongest judge. It operates per triple with a fixed decision rule and no error bound, and its authors name richer knowledge units as future work. We keep its judge and change what is controlled and how.

Knowledge-Centric Hallucination Detection (REFCHECKER) supplies two things. One is evidence that triple-sized units are the right checking granularity: an average gain of 10 Macro-F1 over sentence-level checks. The other is the KNOWHALBENCH annotations. It also constrains us. It documents an internal-knowledge bias, in which checkers accept claims that are true in the world but not stated in the reference. That bias threatens any calibration whose calibration and test documents differ in how much they overlap with the judge's memorized knowledge.

GraphEval, FactAlign and HalluGraph all build graphs from model outputs in order to detect hallucinations. GraphEval runs natural-language-inference models on each triple. FactAlign uses embedding alignment plus an inference-based intrinsic/extrinsic classifier. HalluGraph uses entity-grounding and relation-preservation ratios and reaches AUC 0.94 on legal contract QA. These papers motivate the proposal: entity and role swaps are the errors graph structure catches best. None of them builds a reusable knowledge graph, and none attaches an error guarantee to its decisions. HalluGraph and GraphEval also report that graph methods add little on short texts. This is why we target document-level extraction (Re-DocRED) rather than short answers.

Judge, Retrieve, or Abstain supplies the calibration machinery: thresholds on judge uncertainty chosen on a held-out set with Clopper-Pearson bounds, so that the false discovery rate stays below $\alpha$. With Qwen3-8B it raises coverage on NQ-Open from 7% to 82% at $\alpha=0.20$. It treats each claim as an independent binary verdict on open-domain QA. We change the loss from per-claim to per-path, change the exchangeable unit from claim to document, and add a second threshold for merges.

AgentEval motivates the path view by analogy. It finds that 63% of step failures in agent traces propagate from upstream errors, and that judging steps on a dependency graph lifts failure recall from 0.41 to 0.89. Its graph is an execution trace, not a fact graph, so it is evidence that composition matters, not a method we reuse.

Research Program

The pipeline has four stages. The first is GraphJudge's extractor, which produces candidate triples. Entity resolution then proposes merges of mentions into nodes, and each merge is kept as a separate candidate decision rather than applied silently. Next, a judge assigns a support score $s_e$ to every candidate edge and $s_m$ to every candidate merge, each conditioned on the source text. Finally, the graph keeps edges with $s_e \ge \lambda_e$ and merges with $s_m \ge \lambda_m$.

We use two judges. The fine-tuned GraphJudge model is open, so its token probabilities give scores directly. A black-box GPT-4o-mini judge gets a score from agreement across several resampled, paraphrased verdict prompts. This addresses the concern from Judge, Retrieve, or Abstain that logit-based calibration excludes commercial APIs.

For a document $d$ and thresholds $\lambda=(\lambda_e,\lambda_m)$, let $P_k(d,\lambda)$ be the set of simple paths of length at most $k$ in the accepted graph. Let $B_k(d,\lambda)$ be the subset that contains at least one unsupported edge or one incorrect merge. The per-document loss is $L(d,\lambda)=|B_k|/\max(1,|P_k|)$. The quantity we control is

$$R(\lambda)=\mathbb{E}_{d}\left[L(d,\lambda)\right].$$

We calibrate on held-out documents in the style of Judge, Retrieve, or Abstain. Over a grid of $(\lambda_e,\lambda_m)$ we compute a Clopper-Pearson-style upper confidence bound on $R$, test the grid in a fixed order from strict to permissive, and select the most permissive pair whose bound stays below $\alpha$. If documents are exchangeable, the guarantee is $\Pr[R(\hat\lambda)\le\alpha]\ge 1-\delta$, where $\delta$ is the chosen failure probability. Because $L$ lies in $[0,1]$, a bounded-loss version of the bound applies.

Treating the document as the unit is the deliberate choice here. Triples from the same document share denoising and extraction failures, so they are not exchangeable with one another. Pretending they are would produce intervals that are too tight.

Building the calibration labels is the main cost. Gold triples in Re-DocRED, SCIERC, REBEL-Sub and GenWiki undercount true support, because extractors produce valid triples the annotators skipped. We will therefore have annotators label a stratified sample of non-gold extracted triples and every proposed merge in the calibration documents. This also lets us estimate how much label noise in the remaining gold-only portion inflates or deflates measured risk.

The analysis also tests the hub hypothesis behind the core claim. For each graph we will regress path corruption on the degree of the entities attached to wrong edges and wrong merges.

Baselines

The do-nothing reference keeps every triple the GraphJudge extractor emits, with resolution merges applied silently. This shows how much path error raw LLM extraction produces. It anchors every coverage–risk curve.

The strongest existing method is GraphJudge's own pipeline, with its fine-tuned judge and default keep/drop rule. The file reports that it achieves top F1 on REBEL-Sub, GenWiki, SCIERC and Re-DocRED, and that its 7B judge outperforms GPT-4o and 70B+ models. However, no reported result found on Lacuna for GraphJudge's exact F1 values. We will therefore rerun it ourselves on the same documents with the same extractor outputs. It is the strongest competitor because it is the only published system that filters hallucinated triples during graph construction. To beat it, our method must match its retained supported-edge count while keeping path error below $\alpha$ in at least $1-\delta$ of random splits, where GraphJudge's fixed rule offers no such property. We will also report where GraphJudge's realized path error sits.

The ablation that isolates the key ingredient keeps the same judge, scores, Clopper-Pearson calibration and document units, but controls triple-level false discovery at $\alpha$. A second variant controls it at $\alpha/k$, the union-bound correction for $k$-hop paths. Both variants also drop merge judging. A further ablation keeps the path loss but removes the merge threshold, showing how much of the path error comes from entity resolution rather than from edges.

We also include an empirical threshold on GraphJudge's score, tuned on the same calibration documents to hit $\alpha$ path error with no confidence correction. We also include a prompted GPT-4o judge with a rubric. For reference, the file reports GPT-4o at 83% on ME-FEVER versus 91% for the fine-tuned Halu-J, and ChatGPT at 58.53% on HaluEval summarization detection (HaluEval). Every method gets identical documents, extractor outputs and calibration/test splits. Any method with tunable parameters gets the same tuning budget on the calibration documents only.

Why not just…?

Why not just tune a threshold on a validation set? This is the most serious threat. In expectation, a threshold tuned on held-out documents hits the target about as often as the calibrated one. Calibration adds two things: a guaranteed bound on how often the target is missed, and correct handling of correlated errors within a document. If the empirical threshold misses the path-level target in only about $\delta$ of 200 random splits on Re-DocRED and under the SCIERC shift, then the confidence correction is not worth its coverage cost. We would then report that the path-level loss and merge judging, not the bound, carry the contribution.

Why not just control triple-level error at $\alpha/k$? This is simple, and if errors were independent and evenly spread it would be roughly right but wasteful. Our hypothesis says it fails in both directions. It throws away many good edges at low-degree nodes. It still misses corruption from wrong merges, because merges are never judged. The ablation measures both effects directly. If $\alpha/k$ matches our coverage and keeps the bound, the path-level machinery is unnecessary.

Why not just use a stronger judge or a better extractor? A better judge moves the whole coverage–risk curve outward, and we welcome that. But it does not by itself tell a user what error rate the resulting graph has. The evidence that scale fixes judging is also weak: GraphJudge's 7B specialist beats larger general models, and REFCHECKER documents internal-knowledge bias even in strong checkers. We run the calibration on top of both an open fine-tuned judge and a black-box frontier judge, so judge strength and guarantee are separated.

Why not just check each triple with an off-the-shelf inference model, as GraphEval does? That is a choice of score, not an alternative to calibration. We include an inference-model score as a third judge in the same procedure. If it yields comparable coverage at equal risk, it is the cheaper recommendation.

Proposed Experiments

The primary testbed is Re-DocRED, because its multi-sentence documents produce graphs with real paths. SCIERC serves as a domain-shift test, with calibration on general documents and testing on scientific abstracts. REBEL-Sub and GenWiki are secondary. KNOWHALBENCH's 11,000 human-labeled triplets give a sanity check that each judge's edge scores rank support correctly before any calibration. We use $k\in\{1,2,3\}$, $\alpha\in\{0.05,0.10,0.20\}$ and $\delta=0.1$.

The metrics are four:

  • realized path-level risk on test documents;
  • the fraction of 200 random calibration/test splits in which that risk exceeds $\alpha$;
  • coverage, the share of human-verified supported edges retained;
  • a downstream check: on HotpotQA, questions are answered by retrieving paths from graphs built over the supporting paragraphs, and we count answers that rest on an unsupported path.

There are three decisive checks.

  1. Do graphs calibrated at triple level show path error substantially above $\alpha$, concentrated at high-degree nodes and wrong merges? If not, the core claim is false.
  2. Does path-level calibration keep the violation frequency at or below $\delta$, while beating the $\alpha/k$ ablation on coverage? This decides whether the method is worth using.
  3. A counterfactual stress test. We calibrate on ordinary Re-DocRED documents, then test on copies whose stated facts were edited to contradict common knowledge. This probes whether REFCHECKER's internal-knowledge bias breaks exchangeability and voids the guarantee. If it does, the bound holds only within the source distribution, and we will state that limit plainly.