Fingerprint in the Crack: GraphRAGProv Brings How-Provenance to GraphRAG

*This post is a Chinese forum author's in-depth commentary on the demo paper "GraphRAGProv: GraphRAG Meets How-Provenance" (arXiv:2610.37237, INRIA Rennes). Below is a structured English rendering of the argument, translated and condensed.*

Key points

• The problem: In GraphRAG systems, the retrieved evidence subgraph only proves what the LLM *saw*—nothing reveals how the returned answer was *computed* from that evidence. The generation step (attention inside hundreds of Transformer layers) is the least auditable link in the chain.
• In high-stakes settings (medical diagnosis, computational law), the answer itself must be verifiable and the computation leading to it must be auditable—like a forensic evidence chain, where one broken link voids the whole thing.
• The fix—don't let the LLM write answers: GraphRAGProv reverses the usual roles. The knowledge graph acts as the *calculator*; the LLM only *translates* the natural-language question into a SPARQL query (and text into triples). The query's execution result is the answer itself. Auditing shifts from an uninspectable neural generation process to a replayable symbolic computation.

Three layers of traceable evidence

1. Graph construction layer: The LLM extracts RDF triples from text (e.g., "Borhane Alaouié is a Lebanese film director" → (Borhane Alaouié, nationality, Lebanese)) and must provide text citations for each of subject, predicate, and object. A deterministic locator resolves citations to exact character spans in the source; unmatched citations are rejected for correction. Design principle: deterministic components verify, statistical components only translate. 2. Symbolic block layer: Each *source-grounded statement occurrence* is registered as a symbolic block with a unique ID, linking an RDF triple to its source paragraph and evidence spans (stored via RDF-star reification). The same triple extracted from two paragraphs yields two independent occurrences with separate evidence. 3. How-provenance layer: The LLM-generated SPARQL query runs on GraphDB; the NPCS engine (Asma et al., 2024) rewrites the query to also compute the answer's how-provenance—a polynomial where ⊗ (multiplication) means statements jointly required and ⊕ (addition) means alternative derivation paths.

The full chain: q → Q → μ → P_μ → id_i → (u_i, E_i^s, E_i^p, E_i^o) — question, query, answer binding, provenance polynomial, statement occurrence IDs, and per-component character spans.

Evaluation: 400 cases

• Benchmarks: 200 compositional questions from 2WikiMultiHopQA and 200 answerable questions from MuSiQue. Graph construction and SPARQL generation used DeepSeek-V4-Flash.
• Full traceability available: 193/200 (2Wiki), 118/200 (MuSiQue); all 311 successfully decoded traces passed occurrence and source-span checks. The lower MuSiQue rate points to upstream construction, not the trace mechanism, as the bottleneck.

Four failure cases — a complete fault map

• Case 1 (Meesaya Murukku): Answer "India" was correct and every cited character existed at the right offset—but "Indian" described the *film*, not the *director*. Character-level precision does not guarantee semantic correctness of interpretation.
• Case 2 (Labyrinth): The query returned the correct year 1986 from two individually well-grounded assertions, yet the computation never established "Acornsoft published this game." The paper's verdict: *"An executable query answers what it asks of a graph, not necessarily what the user asked of the original text."*
• Case 3 (Aldobrandino): Entity resolution issued two IRIs for the same person, so a join silently returned an empty result. Crucially, empty results leave no provenance trace—the method's most honest blind spot.
• Case 4 (Caledon River): The trace showed both required relations came from a single paragraph while the benchmark assumed two—not a system failure, but a demonstration of using traces to audit the benchmark's own annotation assumptions.

Provenance is an audit trail, not a certificate

The paper never claims better accuracy; it claims inspectability—every step behind an answer can be checked, and responsibility boundaries are clear. In an era where answers are getting cheap, "how it was derived" is what becomes valuable. The author also situates this in a series: the earlier FoG work (arXiv:2610.37405) forced KG agents to retrieve evidence before answering; GraphRAGProv makes every evidence label withstand inspection—a third failure mode (stale evidence) is teased for a future post on LiveSearch.

References

• Wadie El Amrani, Luis Galárraga. "GraphRAGProv: GraphRAG Meets How-Provenance." arXiv:2610.37237 [cs.AI], 2026. (INRIA, Rennes; demo paper; builds on NPCS provenance engine, GraphDB, RDF-star)
• Zongyuan Sun et al. "Clearing the FoG: Training KG Agents to Retrieve the Evidence Behind Their Answers." arXiv:2610.37405 [cs.AI], 2026.