Distilling Knowledge-Graph Path Search into a Single Checkable Pass

Language models answering expert questions often invent facts. One of the more reliable fixes is to make the model walk a knowledge graph: a database of entities joined by typed edges, such as gene A —regulates→ gene B. The model hops from edge to edge until it reaches an answer, and the chain of edges it followed serves as the explanation. The best such systems are slow because they search at answer time. Paths-over-Graph runs beam search over candidate paths with a language model pruning candidates at each step, and GALAX runs a reinforcement-learning agent that builds a subgraph one edge at a time. Running several searches and combining them would likely be more robust still, but that multiplies the cost again.

This proposal trains one small model to write out a complete knowledge-graph path, from the entities in the question to the answer, in a single greedy pass. Its teacher is an ensemble of expensive searches. Because the output is a sequence of symbolic edges, a plain database lookup (a few milliseconds, no language-model call) can check whether every edge exists. The explanation therefore stays auditable even though no search happens at answer time. The lookup also yields a nearly free hallucination signal, which decides when to fall back to the full search. The target setting is biomedical target identification, where general models are known to lack the underlying domain rules. The Freebase question-answering suite serves as a controlled comparison.

Core Claim

Existing distillation work compresses ensembles, but into outputs that cannot be checked. MAGDi distills multi-agent debate transcripts into Mistral-7B and reports a 9x token reduction, but its graph nodes are free-text debate turns with no factual anchor, so teachers that share a false belief pass it straight to the student. Distilling Knowledge for Search-based Structured Prediction supplies the training recipe we reuse. It matches the ensemble's soft distribution at reference states, and it adds exploration states where the ensemble has wandered off the correct path, so the student learns to recover. That work, however, was applied to syntactic parsing and translation, not factual paths.

Our claim has three parts. First, an ensemble of knowledge-graph path searches can be distilled into a single generator whose paths are verifiable by construction. Second, training on the ensemble's disagreements and recoveries, rather than on one best path, is what keeps the student accurate. Third, the fraction of emitted edges that the lookup cannot confirm is a hallucination detector that costs essentially nothing. That last point matters because step-by-step verifiers such as FlowScore need a language-model judge call for every reasoning step.

Research Program

The teacher ensemble. For each training question we run several path searches. These are PoG-style beam search, a GALAX-style reward-guided walk on the biomedical graph, and variants of each driven by different prompts and different backbone language models. Each search produces scored complete paths, together with the partial paths it abandoned.

Training targets. From these runs we build two kinds of training data. The reference states are the prefixes of paths that reach the gold answer. At each such prefix the target is the ensemble's pooled distribution over the next relation and entity, so the student learns that several paths can be valid. The exploration states are prefixes where some teacher took a wrong hop. At each of these the target is the continuation the stronger teachers used to recover, or an explicit backtrack token. The loss is

$$L = \sum_{s \in R} \mathrm{KL}\big(p_{\text{ens}}(\cdot \mid s)\,\|\,p_\theta(\cdot \mid s)\big) + \lambda \sum_{s \in E} -\log p_\theta(y^{*}_s \mid s),$$

where $R$ and $E$ are the reference and exploration prefixes, $p_{\text{ens}}$ is the pooled teacher distribution, $p_\theta$ is the student, $y^{*}_s$ is the recovery step, and $\lambda$ weights the exploration term. Paths are serialized with canonical entity identifiers, so the student also learns entity linking. Entity linking is the step PoG identifies as the point where traversal most often fails to start.

Inference. The student greedily emits a path and then a short answer. A symbolic checker looks up each edge. If every edge is found, the path is returned as the explanation. The unconfirmed-edge rate $u = (\text{edges not found})/(\text{edges emitted})$ is the detector score. When $u$ exceeds a threshold tuned on validation data, the question is routed to the full teacher search. The knowledge graph is incomplete, so an unfound edge is labeled unverified, not false. We report separately how often unverified edges turn out to be true facts missing from the graph.

Motivating evidence. The domain focus is motivated by two findings. MedHalu shows GPT-4 at layperson level on medical fact conflicts (macro-F1 0.56 against 0.57 for laypeople and 0.79 for experts). MHB reports a 29.1% hallucination rate even for Claude-4-Sonnet. Together these suggest the missing knowledge has to come from outside the model, not from more prompting.

Constraining evidence. Prompt engineering in consistency and reliability with the evidence-based guideline for LLMs found that fine-tuning on guideline text did not improve consistency. This is why we supervise with symbolic paths rather than domain prose, and why plain fine-tuning is a baseline we must beat, not assume away.

Baselines

The naive reference point is the base student, the same 7B open model, answering directly with no graph and no training. It sets the floor for accuracy and for hallucination.

Standard retrieval-augmented generation, meaning top-k text chunks from the same domain sources, represents flat retrieval. On lab-test interpretation, LAB-KG reports that standard RAG reached F1 0.56 against 0.76 for graph grounding. We expect a similar gap, but we will measure it ourselves.

The strongest existing method on Freebase is full test-time PoG, which is also one member of our teacher ensemble. The file reports it improving average accuracy by 18.9% over the prior graph method ToG and using over 50% fewer tokens. No absolute per-dataset accuracy for PoG was found on Lacuna, so we will rerun it on CWQ and WebQSP with the same graph snapshot and entity index.

The strongest existing method on the biomedical side is GALAX on Target-QA, which reports Hit@10 of 0.8815 and Hit@5 of 0.9249. We will reproduce it on the identical split before comparing.

All searches, whether in the teacher ensemble or used as baselines, get the same backbone models and the same graph. Each baseline gets the same hyperparameter-search budget as the student.

"Beating" a full-search baseline here means something different from beating the naive baselines. Against PoG and GALAX, success is staying within 2 accuracy points (or 0.02 Hit@10) of the full search while using at least 10x fewer language-model tokens and calls. With fallback enabled, success is matching them at a fallback rate below 20%. Against RAG and the base model, success is higher accuracy, higher edge validity, and a lower hallucination rate.

Three ablations isolate the key ingredient. The first is a student trained only on the single best teacher path, which is the MAGDi-style single-teacher comparison moved onto graph paths. The second is a student trained with the ensemble but without exploration states. The third is a student without the edge checker, which measures how much of the benefit comes from routing rather than from generation.

Why not just…?

Why not just fine-tune on the single best path from one search? This is the real threat. If single-path fine-tuning matches the ensemble student, then the ensemble and exploration machinery is unnecessary. Search distillation reported gains from exploration states (dependency-parsing LAS of 92.14 against 90.83 for the greedy baseline), and MAGDi reported a 4.61% gain over single-teacher distillation, but neither result concerns knowledge-graph paths. The single-path ablation settles the question directly. We also run a targeted stress test: we force a wrong first hop and measure whether the student recovers. Recovery is exactly what exploration states should teach and what single-path training should not. If the two students tie on both accuracy and recovery, we will report that and simplify the method.

Why not just use self-consistency sampling with the base model? Sampling multiplies cost and fails when the model is consistently wrong. FlowScore reports sampling-based detection near 25% average precision on HumanEval against 83.08% for structural verification. We run self-consistency with 10 samples as a detection and accuracy baseline at matched token cost, and we expect it to fail most on the domain questions where the model's own prior knowledge is weakest.

Why not just run PoG with a cheaper backbone? This competitor is plausible, since it keeps verifiability. However, PoG still makes several language-model calls per query for pruning, so cutting model size does not remove its per-query search. We include a small-backbone PoG using the student's own base model, and compare accuracy against both tokens and wall-clock time.

Why not just use FlowScore-style step verification? It needs one judge call per step and fails on unstated premises. Our paths turn those premises into explicit graph edges, and checking them requires lookups, not judge calls. On HotpotQA and Target-QA we compare the detection quality and cost of our unconfirmed-edge rate against FlowScore.

Proposed Experiments

For the controlled comparison we use CWQ and WebQSP over Freebase, reporting accuracy, the edge-validity rate, the share of answers supported by fully confirmed paths (PoG reports up to 95% for its own answers), tokens per query, language-model calls per query, and latency. For the domain setting we use Target-QA for training and evaluation and PedDep for zero-shot transfer, with Hit@5 and Hit@10 as the metrics.

For hallucination detection we use MedHalu's fact-conflicting subset. This applies wherever entities in the answer can be linked to the biomedical graph, and we report how many items that coverage includes. We score the unconfirmed-edge rate as a detector, reporting macro-F1 and average precision against DEEP-style prompt ensembling. DEEP reports 71.9% balanced accuracy on AggreFact-XSUM, but with several LLM calls per item.

Three decisive checks will judge the proposal. The first is whether the ensemble student beats the single-path student on first-hop-error recovery and on PedDep transfer. The second is whether the accuracy-versus-cost curve, traced by varying the fallback threshold, dominates both small-backbone PoG and GALAX. The third is whether the unconfirmed-edge rate reaches FlowScore-level detection quality at a fraction of its token cost. A tie on the first check would narrow the contribution to cheap verifiable path generation. A loss on the second would mean amortizing the search is not worth it in this setting.