← logs/

Graph-grounded verification: checking agent outputs against structured knowledge

Most factuality checking today is an LLM judging an LLM. The grader and the author come from the same model family, and both can hallucinate in the same places. A different line of work grounds the check in structure: a knowledge graph is a fixed, inspectable store of facts, and verdicts come from graph topology and relations instead of another generation pass. The distinction is sharper than it looks, and it has been earning real evaluation mileage since 2024.

Two directions, easy to confuse

  • GraphRAG runs upstream of generation: the graph is context, and the LLM is still both author and judge.
  • Graph-grounded verification runs downstream: the graph is the ground truth, and the verdict is structural.

The second direction needs a reference graph, a way to turn prose into checkable claims, and a decision rule that does not end in "ask the LLM again". Benchmarks like FactKG made the task measurable; systems like the hybrid KG-plus-search pipeline made it practical.

GraphRAG: the graph upstream

GraphRAG (Edge et al., Microsoft Research, arXiv 2404.16130) is the paper that put graphs back on the RAG agenda. It uses an LLM to build a graph index in two stages: first an entity knowledge graph from the source documents, then pregenerated community summaries for groups of closely related entities. A question is answered by generating a partial response from each community summary and summarizing the partials.

Its target is global sensemaking questions: "What are the main themes in this dataset?" over corpora in the million-token range, where no single passage contains the answer. For those, GraphRAG beats a conventional RAG baseline substantially on both the comprehensiveness and diversity of answers.

The boundary matters for this note: GraphRAG makes the model generate better, but the answer is still judged by the same model that wrote it. The graph improved the author; it did not replace the judge.

Hybrid fact-checking: KG precision with a search fallback

Kolli et al., Hybrid Fact-Checking (arXiv 2511.03217) builds the verification direction as a three-step pipeline. Step one, KG retrieval, does rapid one-hop lookups in DBpedia. Step two, an LM-based classifier guided by a task-specific labeling prompt with internal rule-based logic. Step three, a web search agent invoked only when KG coverage is insufficient.

The results are the point: F1 of 0.93 on the FEVER Supported/Refuted split without task-specific fine-tuning, plus a reannotation study showing the pipeline frequently uncovers valid evidence for claims originally labeled "not enough information". The architecture lesson: the KG provides precision and interpretability, and the search agent is a coverage fallback, not the primary signal.

The benchmarks that made this measurable

FactKG (Kim et al., ACL 2023) turned KG-based verification into a benchmark: 108k natural-language claims over DBpedia with five reasoning types, one-hop, conjunction, existence, multi-hop, and negation. It made the task precise enough to grade systems on rather than argue about.

MultiHal (Lavrinovics et al., arXiv 2505.14101) extends the paradigm: a multilingual, multihop benchmark for hallucination evaluation built from 25.9k curated KG-paths mined from open-domain knowledge graphs. The baseline results show KG-grounded evaluation is not just principled but measurably stronger: KG-RAG improves hallucination detection by 0.29 to 0.42 over vanilla QA across models and languages.

The verifier gate

The shape I keep coming back to is a verifier gate downstream of generation:

prose -> claim extraction (LLM parses, does not judge)
      -> entity resolution -> anchor to reference graph
      -> verdicts from structure:
           SUPPORTED: path exists in the reference graph
           CONTRADICTED: conflicts with a functional, single-valued relation
           UNGROUNDED: no anchor in the reference graph

The crucial move is removing the LLM from the verdict step. An LLM is used to parse prose into structured claims, never to decide truth. If the graph pins a birth year and a claim says another year, that is a deterministic contradiction check, not a judgment call.

Absence is the second move, and it is where RAG breaks. Retrieve a fabricated entity and you get nothing back; a RAG pipeline treats "nothing" as a null, and the model falls back to its parametric prior and guesses. A graph lets you read the shape of the miss: a connected component of claims with zero anchors in the trusted graph is a fabricated cluster. The topology of absence is evidence.

Determinism is the payoff. The same input yields the same verdict, the graph path is the computation, and the decision costs no tokens per claim. That makes it a gate: agent output passes through it before the user sees it, and evals run against it as a fixed ground truth.

Honest limits: graph coverage is the binding constraint, since every gap becomes an UNGROUNDED verdict; entity resolution is where the real engineering effort goes; the pipeline inherits the claim extractor's failure rate, because that parsing step is still probabilistic even though the verdict is not; and temporal facts need versioned graphs or they will contradict the present.

GraphJudge: what I actually built

At HackwithBay 3.0 I built exactly this shape as a hackathon project. GraphJudge (github.com/xesws/HackWithBay_repo), live demo at graphjudge.butterbase.dev, is a graph-grounded factuality judge for LLM output. Paste generated text, and it extracts atomic claims, anchors them to a trusted Neo4j reference graph, and returns a verdict per claim with graph evidence.

The verdicts: SUPPORTED, backed by the reference graph; CONTRADICTED, conflicting with a functional reference fact; UNGROUNDED, not supported by the reference graph. A fourth signal came out of the graph structure itself: an UNGROUNDED fabricated cluster, a group of claims that only point to each other and do not connect to the trusted core, found with WCC-style component analysis via the Neo4j Graph Data Science library.

The core design claim, from the repo's README: the verdict is made by the graph, not by an LLM. The judgment path runs on Cypher, GDS, and arithmetic, so the decision is deterministic, auditable, and costs no tokens. An LLM is used only to parse prose into structured claims. The hackathon scoreboard against an LLM judge (gemini-3.5-flash, one call per doc): on a 63-claim benchmark, equal on planted-false detection at 100% (17/17 each), ahead on exact three-way labeling at 100% versus 98.4%. The single disagreement is a useful receipt: claim CF002, a fabricated entity the gold labels UNGROUNDED, which the graph called UNGROUNDED and the LLM called CONTRADICTED. Scope honesty: it is a hackathon demo on a small reference graph, credit-gated per verification; the point is the architecture, not the scale.

Graph RAG uses the graph to help an LLM generate. GraphJudge uses the graph to judge what an LLM generated, and the judgment is made by graph topology, not by a model. The named next step is versioned graphs for temporal facts: a fact that was true last year and is false today currently forces a choice between contradicting the present and contradicting the past, and the honest answer is a graph that records when each edge held.

Sources linked in this post were fetched and verified.