Testing Whether an LLM's Domain Knowledge Is Connected

When a language model answers a multi-step question in a specialist field such as Alzheimer's biology, contract law, or agronomy, it has to chain facts: drug A inhibits protein B, B regulates pathway C. A recent theory paper argues that what decides whether retrieval can rescue such reasoning is the shape of the model's missing knowledge, not how much of it is missing. Prior Knowledge Makes It Possible treats the model's knowledge as a partial copy of a true knowledge graph, meaning a network of entities joined by factual relations. It then proves a phase transition. If the known part forms one large connected cluster (a "giant component"), a few lookups suffice to answer a connectivity question. If the known part is fragmented, the number of lookups grows like the square root of the graph size or worse. That result has only been checked on synthetic random graphs. Nobody has measured where a real model sits relative to this transition in a real domain.

We propose to measure it cheaply. We treat the model as a graph that can be queried one fact at a time: "is X related to Y by r?" We then borrow sublinear graph testing, a family of algorithms that estimate global properties of a huge graph from a small number of local queries. With it we estimate how fragmented the model's domain knowledge is, using a number of model calls that does not grow with the size of the domain. The claim to test is that this structural reading predicts which questions retrieval will fix, and how many retrieval rounds they need. It should do so better than the obvious scalar alternative, which is the model's average per-fact accuracy.

Core Claim

Let $G^*$ be a reference domain knowledge graph, built automatically from domain literature or taken from a curated source. Let $G$ be the subgraph of $G^*$ whose edges the model affirms consistently across paraphrased probes, plus any spurious edges it volunteers. The scalar that existing hallucination benchmarks report is roughly the fraction of $G^*$'s edges that land in $G$. KGHaluBench reports exactly such per-triple "depth" error rates and finds that they fall far more slowly with scale than entity-recognition errors.

If the missing edges were scattered at random, that scalar would almost determine whether $G$ has a giant component, because in random graphs connectivity depends essentially on average degree. Our hypothesis is that missing domain knowledge is correlated: whole subtopics, tail entities, and bridging mechanisms are absent together. That is the situation the theory paper's "double star with a missing bridge" construction captures. Under correlated missingness, two models with equal per-fact accuracy can sit on opposite sides of the phase transition.

Measuring structure is only worth doing if it is cheap. Probing every edge of $G^*$ costs one or more model calls per triple, which is prohibitive for domain graphs with millions of edges. We therefore estimate the giant-component fraction from a sample of start vertices. The estimate is

$$\hat{\phi}_T = \frac{1}{s}\sum_{i=1}^{s} \mathbf{1}\big[\,|C_G(v_i)| \ge T\,\big],$$

where $v_1,\dots,v_s$ are vertices sampled uniformly from the domain entity set, $C_G(v_i)$ is the connected component of $v_i$ in $G$, explored by a breadth-first search truncated at $T$ vertices, and the indicator records whether exploration reached $T$. A Hoeffding bound gives $s = O(\epsilon^{-2})$ samples for additive error $\epsilon$. Each search costs at most $T$ times a degree cap in model calls, so the total budget is independent of the number of entities $n$. Exploration never needs the model to enumerate neighbors. It walks $G^*$, which is free to traverse, and asks the model to verify each candidate edge, so the only expensive resource is model calls.

Research Program

The work has three parts.

The probing oracle. For each candidate edge we pose a yes/no verification prompt in several paraphrases, including the reversed-role form. An edge enters $G$ only if the answers agree. This uses the observation of Agrawal et al. that fabricated knowledge becomes unstable under indirect cross-examination. The reversed-role probe targets the entity-swapping failure that Milecki documents in clinical summaries. Without this filter, confidently hallucinated edges would knit false fragments together and inflate apparent connectivity. That is the noisy-prior case the theory paper handles with $K$-connected robustness, and one of our ablations removes the filter to measure the inflation directly.

Hub control. We cap explored degree by sampling a bounded number of reference neighbors per vertex, the usual device in bounded-degree testing. This keeps hub entities from consuming the budget. We also estimate a second quantity at the level of individual questions: for a question's endpoint entities, the number of verification calls a bidirectional search needs to connect them in $G$. That number is the empirical counterpart of the theory's constant-versus-$\sqrt{n}$ regimes.

Reference graphs. We use two kinds of $G^*$ so that conclusions do not rest on one noisy reference.

The first is automatically constructed. We use the AD-KG that DALK built from 9,764 PubMed papers with generative relation extraction. We also use graphs we extract from UltraDomain corpora with the same LLM-extraction pipeline that Graph-RAG systems use. Because extraction itself hallucinates, we filter these graphs with a GraphJudge-style triple verifier (Can LLMs be Good Graph Judge for Knowledge Graph Construction?) and report results both with and without that filter.

The second is curated: Wikidata-derived domain slices of the kind KGHaluBench samples from, where reference errors are rarer.

Prediction test. We then ask whether $\hat{\phi}_T$ and the per-question connection cost predict two outcomes: how much retrieval improves accuracy, and how many retrieval rounds are needed. These predictions are checked against real retrieval systems running over the same reference graphs.

Baselines

The do-nothing reference is retrieving a fixed number of graph hops for every question, ignoring any diagnosis of the model. Every predictor below is judged against this uniform allocation under an identical total retrieval budget.

The strongest competing predictor is the scalar per-fact accuracy, the KGHaluBench-style depth hallucination rate. We compute it on the same reference graph with the same consistency-filtered probes and the same number of model calls as our estimator, then regress outcomes on it. It is the natural competitor because, under random missingness, it should carry nearly all the information our structural estimate does. Beating it means our estimate explains significant additional variance in per-domain and per-question retrieval gain after the scalar is included. For context, KGHaluBench reports that entity-recognition hallucination falls from as high as 54.75% in 8B–32B models to about 11.91% in the largest proprietary models, while depth hallucination fell by only about 24%. Its automated verifier reaches up to 87.74% agreement with humans, and we use that figure to bound how much probe noise we should expect.

The second competitor is per-question model confidence measured by self-consistency, the standard signal for deciding when to retrieve. It gets the same call budget.

The third competitor is entity popularity or degree in $G^*$, which costs no model calls at all. KGHaluBench's difficulty weighting is built on page views and relation rarity, so this is a serious baseline.

The cost reference is exhaustive probing of every edge in a domain small enough to afford it. It gives ground-truth $\phi$ and lets us report estimation error against the fraction of calls saved.

We run three ablations. The first removes the paraphrase-consistency filter. The second keeps per-vertex accuracy fixed but randomly reassigns which edges the model knows. This destroys correlation while preserving the scalar, and if the structural estimate predicts no better on real models than on this shuffled control, the hypothesis fails. The third varies the truncation size $T$.

The strongest end-to-end systems that supply the retrieval outcomes are the following. QAFD-RAG reports 73.42 F1 on HotpotQA, against 58.67 for HippoRAG and 33.40 for GraphRAG (Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees). DALK reports 72.6% average accuracy on ADQA. For UltraDomain the file lists no absolute scores, and for 2WikiMultihopQA and MuSiQue there is no reported result found on Lacuna, so we will rerun these systems ourselves. We are not trying to beat them at question answering. They serve as the outcome measures our diagnostic must predict, and as the systems whose retrieval budget a diagnostic-driven allocation should make cheaper at equal accuracy.

Why not just…?

Why not just sample random triples and report per-fact accuracy? That is already sublinear and statistically clean, and if missing knowledge is close to random it is all one needs. It is the real threat to this proposal. The shuffled-missingness ablation and the incremental-variance test against the scalar are designed to settle it. If structure adds nothing, we will report that per-fact accuracy suffices, which is itself a useful constraint on the theory paper's relevance to practice.

Why not just use the model's confidence to decide when to retrieve? Confidence is measured per question and says nothing about whether the gap can be bridged in a few hops or needs many. The theory distinguishes exactly those cases. A model can also be confidently wrong on swapped roles, which is the failure HalluGraph targets with graph alignment, reaching 0.94 AUC on legal contract QA where BERTScore reaches 0.60. The budget-allocation experiment compares the two signals directly at equal calls.

Why not just verify every triple, as GraphJudge and GraphEval do? GraphEval and GraphJudge check the extracted graph against text, one triple at a time. We probe the model's knowledge, and exhaustive probing scales with the number of edges. We use it as ground truth on small domains and report how quickly the sampled estimate converges to it.

Why not just put the domain rules in the prompt? TheoremQA found that injecting theorem statements gave no significant gain. This suggests the deficit lies in linking facts together, which is what a connectivity measurement targets.

Proposed Experiments

We will probe open models of several sizes, along with any proprietary models we can afford, on several domains. The Alzheimer's domain uses AD-KG with ADQA questions. The general multi-hop setting uses Wikidata slices behind HotpotQA, 2WikiMultihopQA, and MuSiQue. The specialist domains are UltraDomain's agriculture and legal subsets, using graphs we extract ourselves.

The first decisive check is estimator fidelity. On domains small enough for exhaustive probing, $\hat{\phi}_T$ should land within $\epsilon$ of the exhaustive value using a small fraction of the calls.

The second check is correlation. Across model–domain pairs, the measured gap between $\phi$ and the value implied by the scalar under random missingness should be clearly nonzero. If it is near zero everywhere, the structural hypothesis is dead.

The third check is prediction. Per-question connection cost in $G$ should predict the number of retrieval rounds QAFD-RAG or a bidirectional search needs, and the retrieval gain on ADQA and MuSiQue. It should do so beyond the scalar, popularity, and confidence baselines, measured by rank correlation and incremental $R^2$.

The fourth check is practical. Allocating a fixed retrieval budget across questions by predicted regime should match uniform-budget accuracy with fewer retrieval calls, or exceed it at equal calls.

Throughout, we report the same quantities with the consistency filter removed. This shows how much hallucinated edges disguise a fragmented domain as a connected one.