💬 NLP

When Correct Edges Cannot Be Verified: A Provenance Gap in Incomplete KGQA and a Provenance-Favoring Completion Policy

This paper reveals that textual verifiability is a poor proxy for edge correctness in Incomplete Knowledge Graph Question Answering due to a widespread lack of supporting text for valid facts, leading to the proposal of TGComplete, a provenance-favoring policy that prioritizes admitting only verifiable edges to ensure auditability over maximizing recall.

Original authors: Yongqi Kang, Yu Fu, Yong Zhao

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yongqi Kang, Yu Fu, Yong Zhao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a complex mystery using a giant, digital encyclopedia (a Knowledge Graph) and a very smart, but sometimes hallucinating, detective (a Large Language Model).

Usually, the detective walks through the encyclopedia, following a trail of facts to find the answer. But sometimes, the encyclopedia is missing pages. The trail breaks, and the detective gets stuck.

To fix this, the detective can try to "guess" the missing fact from its own memory, or it can go to a library of books (text) to find evidence. The big question this paper asks is: If the detective finds a book that mentions the missing fact, does that mean the fact is actually true?

The authors say: No, not necessarily. And here is why, explained simply.

1. The "Missing Page" Problem

In the real world, knowledge graphs are incomplete. Imagine a map of a city where some streets are erased. If your GPS (the reasoning model) tries to drive from Point A to Point B, it hits a dead end.

The Old Way (GoG): The detective just guesses the missing street name based on what it "remembers." It might be right, or it might be a complete hallucination.
The New Idea: Before accepting the guess, check the library (text) to see if anyone wrote about that street. If the library has a book mentioning it, we assume the guess is safe.

2. The Big Surprise: The "Provenance Gap"

The authors tested this by taking a perfect map, secretly deleting 20% to 40% of the streets, and seeing what happened. They knew exactly which streets were the "real" missing ones because they deleted them themselves.

The Counter-Intuitive Finding:
They found that 76% to 96% of the correct missing streets could not be found in the library books, even if they searched every single book exhaustively.

The Analogy:
Imagine you are looking for a specific, obscure fact: "Who was the mayor of a tiny village in 1994?"

The Fact: It is 100% true.
The Library: You search every newspaper, biography, and history book.
The Result: The library doesn't mention the mayor's name in the same sentence as the village name. The fact is true, but it is textually invisible.

The paper calls this the Provenance Gap.

Verifiability: Can I find a book that says this?
Correctness: Is this actually true?
The Gap: Just because you can't find a book doesn't mean it's false. And just because you can find a book doesn't guarantee it's the whole truth. Most facts in these databases are like that obscure mayor—they exist, but they don't show up as "Head + Tail" in a single sentence in a book.

3. The Solution: TGComplete (The "Cautious Detective")

Since we can't rely on finding a book to prove a fact is true, the authors built a new system called TGComplete.

Instead of trying to be perfect, TGComplete changes the goal. It asks: "Should I admit this fact into my reasoning, or should I admit I don't have proof?"

How it works:

Stop: When the trail breaks, it stops.
Search: It looks for evidence in the library.
Verify: It checks if the evidence strongly supports the guess.
Decide:
- If there is strong proof? Admit the fact and keep going.
- If there is no proof? Abstain (stop and say "I don't know"). It does not guess.

4. The Trade-Off: Precision vs. Recall

This is where the "Risk Management" part comes in.

The Cost: Because TGComplete refuses to guess without proof, it misses some correct answers. It rejects about 24% to 50% of the correct missing facts because they had no book evidence.
The Gain: However, the facts it does accept are much more trustworthy. It filters out the "fake" guesses.
The Magic: Surprisingly, even though it rejects many correct facts, the final answer accuracy (getting the right answer to the question) stays the same as the guessing method.

Why?
The authors discovered that most of the missing facts (even the correct ones) are causally redundant.

Analogy: Imagine solving a maze. You need to turn left, then right, then left. The "missing fact" is the second "left."
The authors found that in 95–97% of cases, the maze could still be solved even if you ignored that specific missing turn, because the detective's internal knowledge or other paths were enough to get to the exit.
So, rejecting the missing fact didn't hurt the final score, but it did prevent the detective from confidently stating a fake fact.

5. The Bottom Line

The paper concludes that we need to change how we think about "checking" facts in AI.

Old Belief: "If I can't find it in the text, it's probably wrong."
New Reality: "If I can't find it in the text, it might still be true, but I can't prove it."

TGComplete is a tool for Auditability. It doesn't promise to find every single correct answer. Instead, it promises that every answer it gives is backed by a paper trail. It trades "finding everything" for "only saying things I can prove."

In a world where we need to trust AI, this paper suggests it's better to have a system that says "I don't know" than one that confidently lies, even if that means it misses a few correct guesses along the way.

Technical Summary: "When Correct Edges Cannot Be Verified: A Provenance Gap in Incomplete KGQA and a Provenance-Favoring Completion Policy"

1. Problem Formulation

The paper addresses Incomplete Knowledge Graph Question Answering (IKGQA), a setting where critical triples required for reasoning are missing from the Knowledge Graph (KG). Standard methods like Think-on-Graph (ToG) fail when reasoning paths break due to missing edges. Recent approaches, such as Generate-on-Graph (GoG), attempt to resolve this by having Large Language Models (LLMs) generate missing triples from parametric knowledge. To mitigate hallucination risks, a common strategy is to verify these generated edges against retrieved text before admitting them into the reasoning chain.

The authors challenge a fundamental, untested premise of this "verify-before-admit" strategy: Does textual verifiability actually track correctness? Specifically, they investigate whether an edge supported by text is more likely to be correct, and conversely, whether edges lacking textual support are likely incorrect.

2. Key Findings: The Provenance Gap

Through a systematic measurement study using the gold deleted triples from the standard random-deletion protocol (on CWQ and WebQSP datasets), the authors identify a counterintuitive phenomenon they term the Provenance Gap:

Correctness vs. Verifiability Divergence: Among edges that are gold-correct (matching the deleted ground truth), 76–96% have no supporting passage in the corpus, even under exhaustive retrieval conditions.
Structural Cause: This gap is not an artifact of poor retrieval but a structural property of Freebase-style facts. Most facts (e.g., involving CVT mediator nodes, database identifiers, cross-sentence facts, or long-tail entities) do not appear as head–tail co-mentions in a single text passage.
Metric Implication: Textual faithfulness metrics (e.g., "text-grounded ratio") measure provenance (can the edge be verified?), not correctness (is the edge true?). The two concepts are separated by a paradigm-level gap that in-corpus retrieval cannot close.
Causal Redundancy: A secondary finding reveals that 95–97% of correct answers do not depend on any unsupported completed edge. Most completed edges are causally redundant for the final answer, shifting the problem from "ensuring correctness" to "risk management" (admitting or abstaining under uncertainty).

3. Methodology: TGComplete

Based on these findings, the authors propose TGComplete, a training-free, index-free provenance-favoring admission policy. Unlike GoG, which generates-to-complete, TGComplete retrieves-to-complete.

Pipeline:

Breakpoint Trigger: When reasoning encounters a missing edge $(h, r, ?)$ , the system triggers text retrieval from an external corpus (Wikipedia).
Candidate Extraction: A candidate tail entity $t$ is extracted from the retrieved passages.
Three-Factor Verification Loop: A candidate edge is admitted only if it passes:
- Multi-source Agreement: Counting independent sources supporting the candidate.
- LLM Entailment Judgment: A lightweight loop where the backbone LLM judges if the source passages strictly entail the candidate (mapping to scores: Entailed, Uncertain, Not Entailed).
- KG Conflict Detection: Checking for conflicts with existing functional constraints in the KG.
Admission/Abstention: If the combined confidence score exceeds a fixed threshold ( $\tau=0.5$ ) and no conflicts exist, the edge is admitted. Otherwise, the system abstains (rejects the edge) and backtracks with a more targeted query. Crucially, the threshold is never lowered to accommodate low-quality candidates.

4. Experimental Results

Evaluated against the GoG baseline and other RAG/Graph-RAG methods on IKG-20% and IKG-40% subsets of CWQ and WebQSP:

Accuracy (EM): TGComplete achieves no statistically detectable loss in Exact Match (EM) compared to GoG (McNemar $p > 0.05$ across all subsets). This confirms that rejecting unverifiable edges does not significantly harm final answer accuracy, consistent with the causal redundancy finding.
Edge Precision: TGComplete significantly improves edge precision against gold triples (15–21% vs. 3–14% for GoG). By filtering out unverifiable candidates, the admitted edges are more likely to be correct.
Strict Faithfulness (Provenance): The admitted edges in TGComplete exhibit 3.1–7.4× higher strict faithfulness (verified by an independent judge) compared to GoG.
Recall Cost: The method accepts a lower recall of edges, rejecting 24–50% of gold-correct edges that lack textual support. However, because these rejected edges are mostly causally redundant, this does not translate to a drop in final answer accuracy.
Robustness: The "no accuracy loss, higher provenance" pattern holds even in the IKGWQ dataset (real-world knowledge updates), though absolute faithfulness scores remain low due to the difficulty of grounding up-to-date facts.

5. Significance and Claims

The paper positions TGComplete not as a universally superior method, but as a principled point on a precision/provenance–recall trade-off.

Reframing Completion: The authors argue that edge completion in IKGQA should be viewed as a risk-management decision rather than a correctness contest. Since most correct edges are unverifiable, the goal shifts to "admit or abstain under provenance uncertainty."
Auditability: TGComplete is designed for settings where auditability matters. It guarantees that admitted edges are verifiable, even if it means discarding some correct-but-unverifiable facts.
Limitations of Text Verification: The study concludes that no text-verification method can guarantee correctness because of the inherent provenance gap. Text grounding serves as a signal for provenance, not a certificate of truth.
Future Directions: The paper suggests that closing the gap may require richer evidence composition (multi-passage aggregation), structured evidence (tables/infoboxes), or KB-text alignment resources, rather than simply improving retrieval or LLM generation.

The authors release code, prompts, and evaluation scripts to support replication, emphasizing that their contribution is a measurement study revealing a fundamental limitation in current IKGQA verification strategies and a policy to navigate it.