Checkable Rationales: Training Language Models to Separate Graph-Grounded Steps from Guesses

When a language model explains its answer, the explanation can itself be made up. It may cite facts that do not exist, or reach the right answer for the wrong reason. The core difficulty is that free-text explanations are hard to check, so fabricated steps cannot be penalized directly during training. We propose a different format. The model writes its explanation as a chain of knowledge-graph facts, each a triple of the form (subject, relation, object) serialized as text, and it tags every step. A [KG] tag means "this fact appears in the graph I was given." A [HYP] tag means "I am asserting this from memory because the graph is missing it." Each [KG] step can then be checked exactly by looking it up. Each [HYP] step can be scored against held-out edges during training. The model learns from these per-step checks through a small low-rank adapter, meaning a thin set of trainable weights added to a frozen model.

The payoff is a model whose explanations are verifiable wherever the graph covers the question and honestly marked where it does not. The second case is where existing faithful-reasoning methods fail. Hard-constrained decoding guarantees that every step exists in the graph, but it cannot produce the right answer when the needed edge is missing. Unconstrained explanations cover missing edges but hallucinate freely. We aim for a model that does both: it grounds what it can, flags what it cannot, and is calibrated about the flags.

Core Claim

Serializing rationales as tagged graph triples turns rationale hallucination from something that needs a learned judge into an exact label at each step. That exact label is a strong enough signal to train a parameter-efficient adapter to do two things under realistic graph incompleteness. First, it should almost never mislabel a guess as grounded. Second, it should assign calibrated confidence to its guesses.

The claim is falsifiable in a specific way. The approach must beat hard trie-constrained decoding on questions whose reasoning path crosses a missing edge. It must also match that decoding on grounding fidelity when the graph is complete.

Where This Sits in Prior Work

The motivating evidence comes from three places. Explain Yourself! showed that conditioning a classifier on generated explanations lifts CommonsenseQA accuracy from 54.8% to 64.7%. With human explanations the classifier reaches about 90%, which isolates explanation quality as the bottleneck. Self-Rationale Calibration attacks "right answer, wrong reason" by adapting a model with a low-rank adapter and preference optimization. It scores free-text rationales with a distilled 1.5B judge model. We keep the adapter-plus-preference recipe but replace the learned judge with an exact lookup, which is only possible because our rationales are graph-structured. HaluEval explains why a judge-free signal matters: ChatGPT detects hallucinations in summaries only 58.53% of the time, so self-judgment is weak supervision.

The closest competitor is Graph-constrained Reasoning (GCR). GCR builds a prefix tree of valid graph paths and masks the model's vocabulary so that only real paths can be decoded. This gives 100% faithful paths and a 9.1% Hit-rate gain over earlier graph methods on Complex WebQuestions. It also reports that unconstrained models hallucinate paths about 33% of the time. GCR's constraint is hard and applies only at inference time, so a missing edge simply cannot be traversed.

Our proposal differs in three ways:

  • The grounding pressure is learned rather than imposed.
  • The model has a sanctioned outlet for memory-based steps.
  • The per-step labels double as training and evaluation signal.

Two papers supply methods we reuse. GNN-RAG retrieves shortest paths with a graph neural network and serializes them as text chains such as "Jamaica -> official_language -> English". It reaches 62.8% Hit on Complex WebQuestions with LLaMA2-7B, against 62.6% for GPT-4. We use its retrieval and serialization to build both the in-context subgraph and the gold rationales. However, GNN-RAG answers directly from its paths and never writes a rationale. Graph Linearization Methods shows that model accuracy is sensitive to edge order and node labeling, with roughly 35% gains on degree estimation. We therefore fix a degree-ordered serialization and treat order as a controlled variable.

Two papers constrain the design. KG-Adapter argues that prompt-based linearization triggers "knowledge conflicts," where the model's memory overrides the graph text in its prompt. It abandons linearization in favor of graph encoders and cross-attention. We take the conflict seriously but respond differently: the [KG]/[HYP] tags make the memory-versus-context choice explicit and penalizable instead of hidden. Small Updates, Big Doubts finds two things about parameter-efficient fine-tuning:

  • It barely improves factual accuracy (0.1–3.1 points on SQuAD and NQ-Open) but improves black-box hallucination detection by up to about 8% AUROC. This suggests it reshapes how uncertainty is expressed more than it adds knowledge.
  • It degrades linear probes on hidden states.

This is exactly why we target calibrated tagging rather than knowledge injection. It also gives us a secondary question: does training on step-level truth labels reverse the probe degradation?

SRM-LoRA and CAMP reduce direct-answer hallucination by reshaping adapter geometry or preference margins. Neither examines intermediate steps. They are orthogonal optimizers that could be stacked with our signal later.

Research Program

Data construction. For each training question on Freebase-backed benchmarks, we retrieve a subgraph as in GNN-RAG and serialize it in degree order. We then simulate incompleteness by deleting a random fraction $\rho$ of subgraph edges from the model's input while keeping the full graph as an oracle. The gold rationale is the shortest oracle path from question entity to answer. A step is tagged [KG] if its edge survived deletion and [HYP] if it was deleted.

Stage 1: supervised training. A low-rank adapter is trained on the target format: question plus serialized subgraph, then the tagged path, then the answer.

Stage 2: step-level preference optimization. We sample several rationales per question and score each one automatically. The score for a rationale with steps $s_1,\dots,s_n$ and final answer $a$ is

$$ R = \sum_{i=1}^{n} r(s_i) \;+\; \lambda\,\mathbb{1}[\mathrm{exec}(s_{1:n}) = a] \;+\; \mu\,\mathbb{1}[a = a^*]. $$

In this expression:

  • $r(s_i)$ is the reward for step $i$. It is a large penalty if the step is tagged [KG] but is absent from the input subgraph, which we treat as fabricated grounding. It is 0 if the step is a valid [KG] step. If the step is tagged [HYP], its reward is $+c_i$ when the oracle confirms it and $-c_i$ otherwise, where $c_i$ is the model's stated confidence for that step.
  • $\mathrm{exec}(s_{1:n})$ is the entity reached by following the path, so the $\lambda$ term rewards answers that actually follow from the rationale. This addresses rationale–answer misalignment.
  • $a^*$ is the gold answer, and $\mu$ weights answer correctness.

Pairs ranked by $R$ feed a standard preference-optimization loss. The step penalty is exact and needs no judge model.

Classification transfer. The same format is applied to multiple-choice classification, where the label is the chosen option and the rationale is a path connecting question concepts to that option. We use CommonsenseQA and OpenBookQA with the knowledge graph used in KG-Adapter's setup. As a structured-evidence stress test, we also use FEVEROUS claim verification with table cells serialized in the context-aware style of Kotonya et al..

Scale as a constraint. We train the adapter on 3B, 8B, and 70B backbones, using 4-bit quantized low-rank adaptation for the 70B model. We stay under the 65B scale at which QLoRA established parity with full fine-tuning, so 70B is a mild extrapolation that we flag explicitly. At each scale we sweep adapter rank from 4 to 64. This asks whether calibrated tagging saturates at low rank, as the "reshaping uncertainty" view predicts, while answer accuracy keeps depending on backbone size.

Baselines

The naive reference point is the frozen instruction-tuned backbone prompted with the same serialized subgraph and asked for a tagged rationale and answer, with no training. It shows how much of the effect is format alone.

The strongest existing method on grounding is GCR, run from its official code with the same backbone, the same subgraphs, and the same deleted-edge input, so that its prefix tree is built only from edges the model can see. The file reports a 9.1% Hit-rate improvement over RoG and GNN-RAG on Complex WebQuestions and a 100% faithfulness ratio, but no reported result found on Lacuna for GCR's absolute Complex WebQuestions Hit. We will therefore rerun it rather than quote a number. To avoid a strawman, we also run GCR with a fallback: when no valid path reaches a plausible answer, the model reverts to unconstrained generation. Beating GCR means two things. Our method must be within one point of its Hit and have no more than 1% mislabeled [KG] steps at $\rho=0$. It must also have significantly higher Hit on the subset of questions whose gold path crosses a deleted edge at $\rho \ge 0.2$.

GNN-RAG is the strongest answer-accuracy baseline without rationales. Its reported result is 62.8% Hit on Complex WebQuestions with LLaMA2-7B (GNN-RAG). We rerun it on our backbones with identical retrieval. The bar is to match its Hit while additionally producing checkable rationales.

For classification, the explanation-augmented reference is the CAGE result of 64.7% on CommonsenseQA from Explain Yourself!. It used an older data version and older models, so it serves as a historical anchor. The comparison we will actually rely on is to a free-text-rationale adapter trained with Self-Rationale Calibration-style preference optimization using a learned judge. That adapter gets the same backbone, rank, data, and number of preference pairs.

Two ablations isolate the key ingredients. The first uses Stage 1 only: supervised training on tagged paths without the step-level reward. It tests whether the exact verification signal matters beyond imitation. The second removes the tags, so the model must write every step as a plain triple. It tests whether the explicit memory outlet, rather than the reward alone, is what prevents fabricated grounding. All trained systems share the same backbone, adapter rank, token budget, and a fixed hyperparameter search of 12 configurations.

Why not just…?

Why not just use GCR's hard constraint and fall back to free generation when it fails? This is the real threat. We include it as a baseline for that reason. Its weakness is that the fallback is all-or-nothing. Once it triggers, every step is unchecked, and it has no way to mark which single hop was guessed. If GCR-with-fallback matches our method on answer Hit and on [HYP] calibration on deleted-edge questions, the soft approach is not justified, and we would report that. We expect it to lose on the precision of the graph-supported steps in fallback outputs and on rationale–answer consistency.

Why not just put retrieved paths in the prompt and answer directly, as GNN-RAG does? Answer accuracy may be comparable, and that is fine. The proposal's contribution is a rationale whose every step is labeled grounded or guessed, which GNN-RAG does not produce. Moreover, KG-Adapter reports that in-context graph text is often overridden by the model's memory, and direct answering hides when that happens. Our execution-consistency metric exposes it directly.

Why not just fine-tune on gold paths with ordinary supervised learning? This is the Stage-1-only ablation. Small Updates, Big Doubts suggests that plain adapter tuning shifts output behavior modestly. SRM-LoRA shows that plain adapter updates trade fixed hallucinations against new errors, with net improvements of 552 versus 696 for geometry-aware updates on DROP. We predict that imitation alone yields tags that look right but are poorly calibrated on [HYP] steps. If Stage 1 already matches Stage 2 on calibration, the preference stage is unnecessary.

Why not just prompt a frontier model for chain-of-thought? GCR documents about 33% hallucinated paths in unconstrained reasoning, and HaluEval shows weak self-detection. We will still run a frontier model with the tagged format, few-shot, and check its tags against the graph. This measures whether scale alone yields honest tagging.

Decisive Experiments

The main experiment sweeps the deletion rate $\rho \in \{0, 0.1, 0.2, 0.35, 0.5\}$ on Complex WebQuestions and WebQSP. At each rate we report:

  • answer Hit and F1;
  • the rate of fabricated [KG] steps;
  • precision of [HYP] steps against the oracle graph;
  • expected calibration error of [HYP] confidences;
  • rationale–answer execution consistency.

The proposal succeeds if our method stays near GCR at $\rho=0$, overtakes it as $\rho$ grows, and keeps fabricated [KG] steps near zero throughout.

The second experiment tests transfer to natural incompleteness. We train on synthetic deletion and evaluate on questions whose gold path is genuinely absent from the retrieved subgraph, with no synthetic deletion. This checks that the model learned "flag what is not in context" rather than the specific pattern of our deletions.

The third experiment is diagnostic. It revisits the probe degradation reported in Small Updates, Big Doubts. We train linear probes on hidden states to predict whether the current step is supported by the context, and compare the frozen model, plain adapter tuning, and our adapter. If step-level verified supervision restores or improves probe accuracy where plain tuning degrades it, that is evidence the gains are not only surface behavior.

Finally, we repeat the main sweep across backbone sizes and adapter ranks. This tells us whether calibrated tagging is a low-rank behavior that small adapters capture at every scale, or whether it needs capacity that grows with the backbone.