When the Plan Jumps: Faithful Ordered Verbalization of Knowledge Graphs

Users often want to control the order in which a language model talks about a set of facts. A biography, for example, might need to give career first, then family, then awards. When the facts come from a knowledge graph, which stores facts as (subject, relation, object) links between entities, the usual way to give them to a model is linearization: flattening the graph into a token sequence. The obvious control knob is to put the facts in the desired order. This proposal argues that the knob has a hidden cost. Whenever two consecutive facts in the requested order share no entity, the plan makes a topological jump. The model then tends to fill the gap by inventing a relation that is not in the graph, such as "his award-winning work at X" when nothing links the award to X. Order control and faithfulness therefore trade off, and the trade-off is governed by a measurable property of the plan.

We propose to measure this trade-off directly and to remove it for frozen, off-the-shelf models. The method has two parts. First, a jump-aware linearization marks plan steps that share no entity with an explicit boundary token. Second, a cheap sentence-level verify-and-resample loop runs during decoding. After each generated sentence, a verifier checks two things: that the sentence realizes the planned fact, and that it asserts no relation between entity pairs that are not adjacent in the graph. A failing sentence is resampled. The claim is narrow and testable. As the requested plan becomes less coherent with the graph, prompting and fine-tuning baselines will produce more spurious edges. The proposed method should keep that rate roughly flat without losing order adherence or fluency.

Core Claim

Prior work treats linearization order either as a fixed preprocessing choice or as a training-time device for controlling realization order. Neither treats the order as a user constraint that can conflict with the input's structure.

Controllable Meaning Representation to Text Generation supplies the method we build on. It orders input attributes to match the reference (alignment training), adds phrase-level data augmentation, and reaches 0% semantic error rate with over 99% order accuracy on E2E. But its inputs are flat slot-value records about one restaurant, so every order is coherent and jumps cannot occur.

Two papers motivate the gap. The Topological Information Loss of Graph Linearization documents spurious adjacency, meaning that disconnected nodes end up next to each other in the string. Random Search Neural Networks argues that sequence models misread traversal jumps as edge continuations unless the jumps are marked. Both make this point about graph reasoning, not about generation under a user-chosen order.

Graph Linearization Methods for Reasoning on Graphs with Large Language Models constrains our design. It shows that LLMs are highly order-sensitive, with roughly 35% swings in degree-estimation accuracy depending on edge ordering. We should therefore expect order to matter a great deal, and we must control for ordering effects that have nothing to do with jumps.

Our contribution is to connect these findings. We define plan coherence as the fraction of consecutive plan steps that share an entity. We show that the spurious-edge rate depends on plan coherence, and we show that marking jumps plus local verification breaks that dependence for frozen models.

Research Program

The first component is an evaluation instrument. We count a spurious edge when a generated sentence asserts a direct relation between two input entities that are not linked in the graph.

We detect spurious edges in three steps. We locate entity mentions using the input entity list and alias matching, in the spirit of the entity memory buffer in Knowledge Infused Decoding. For every co-mentioned pair in a sentence, we classify whether the sentence asserts a direct relation between them. For that classification we will compare a fine-tuned natural-language-inference model with an LLM judge. We then validate the detector against about 300 human-annotated outputs and report its agreement before using it for any claim. Alongside spurious edges we compute order accuracy (whether planned facts appear in the planned sequence) and fact coverage or semantic error rate.

The second component is a plan generator with controlled coherence. On WebNLG we recover the gold fact order from references using alignment heuristics like those in the meaning-representation paper. We then permute that order to produce plans at fixed coherence levels while holding plan length and graph size constant. This lets us vary coherence without varying anything else. AGENDA serves as a natural stress test because its graphs contain many disconnected components, so some jumps are unavoidable. Modeling Graph Structure via Relative Position notes this property and handles it by modifying attention, which we cannot do with a frozen model.

The third component is the method itself. The linearization lists facts in plan order and inserts a boundary token before any step that shares no entity with the previous one. It optionally appends the graph's shortest connecting path as background, flagged as "do not verbalize unless planned." Decoding proceeds sentence by sentence. Each sentence goes to the verifier. A failing sentence is resampled up to $k$ times, and the best-scoring candidate is kept if none passes.

We deliberately check constraints at sentence boundaries rather than adjusting tokens one at a time. This avoids two costs. It avoids the gradient computation that Plug and Play Language Models performs on hidden states. It also avoids the long, fixed-length optimization of MUCOCO, which needs about 90 minutes for 1,200 sentences against 20 for FUDGE. The rationale is that a spurious edge is a sentence-level property: it can only be judged once both entities have appeared.

The fourth component tests interaction with other controls. Why is constrained neural language generation particularly challenging? reports that satisfaction collapses beyond about three simultaneous constraints. We predict a specific mechanism behind part of that collapse in this setting. A tight length budget forces the model to merge facts into one sentence. Merging facts across a jump is exactly where invented bridges appear. We will therefore cross plan coherence with a length budget and, separately, with a formality target.

Baselines

The naive reference point is a frozen instruction-tuned LLM (Llama 3 8B and 70B, as in the linearization study) prompted with the facts in plan order and an instruction to follow that order. It receives no jump markers and no verification. Every other system uses the same models, prompts, and plans.

The strongest trained competitor is alignment training with phrase augmentation, as in Controllable Meaning Representation to Text Generation, applied to BART and T5-large on WebNLG with gold-aligned orders. That paper reports 0% semantic error rate and over 99% order accuracy on E2E with AT+NUP+P, and about 95% order accuracy on ViGGO. It is the strongest competitor because it already achieves near-perfect order control by training. We found no reported result on Lacuna for order accuracy or spurious-edge rate on WebNLG, so we will establish this baseline ourselves, with the same tuning budget we give any learned part of our verifier.

For general generation quality, the reference points are Stage-wise Fine-tuning and BDCC. Stage-wise fine-tuning (T5-large + Wiki + Position) reports 66.07 BLEU seen and 53.87 BLEU unseen on WebNLG 2017. BDCC reports 66.58 BLEU and 47.44 METEOR on WebNLG 2.0. These numbers come from gold-order evaluation, so we use them only to check that our outputs remain competitive under coherent plans, within a few BLEU points. We do not treat them as the bar on our main metric.

The compute-matched competitor is best-of-$N$: sample $N$ full outputs and keep the one the same verifier scores highest, with $N$ chosen so total generated tokens match our method's average.

Two ablations isolate the key ingredients: jump markers without verification, and verification without jump markers.

Beating the baselines means the following. Our method should show a significantly flatter slope of spurious-edge rate against plan coherence than both the prompted LLM and the alignment-trained model. Order accuracy and coverage should stay within one point of the best baseline. All of this must hold at equal token budget relative to best-of-$N$.

Why not just…?

Why not just prompt the model with the facts in order and tell it not to invent relations? This costs nothing, so it is our naive baseline with an added instruction, not a strawman. The evidence that it degrades under stacked constraints comes from Why is constrained neural language generation particularly challenging?. Link Prediction on Textual Edge Graphs also found direct prompting on serialized graphs weaker than structured decomposition. Neither paper measured invented relations, however. If the instructed prompt keeps the spurious-edge rate flat across coherence levels, our hypothesis is wrong and we will report that.

Why not just extend alignment training to knowledge graphs? This is the most serious threat. On coherent plans it may match or beat us, because it learns order adherence directly. Our bet is that training on gold orders, which are mostly coherent, never shows the model how to verbalize a jump faithfully, so the model will invent bridges at low coherence. The coherence sweep settles this question directly. Even if alignment training holds up, it requires retraining for each combination of controls, which Control, Generate, Augment identifies as the scaling problem. It also cannot be applied to a frozen commercial model.

Why not just sample many outputs and rerank with the verifier? If whole-output reranking matches sentence-level resampling at equal compute, then the contribution reduces to the verifier and the jump markers. We would say so plainly. We expect incremental checking to win because errors compound: the chance that every sentence in a long output is clean falls roughly geometrically with the number of jumps. The compute-matched comparison, broken down by the number of jumps per plan, tests this prediction.

Why not use a graph-aware encoder instead? Graformer and BDCC preserve structure by changing the architecture. That rules out frozen LLMs, and neither method accepts a user-specified plan. We include BDCC as a quality reference but do not claim it fails at faithfulness.

Proposed Experiments

The primary experiment sweeps plan coherence from 1.0 to 0.0 on WebNLG 2017, using both seen and unseen splits. For each system we plot spurious-edge rate, order accuracy, and fact coverage. We use AGENDA to test whether the pattern holds when some jumps are forced by disconnected components rather than created by permutation.

The secondary experiment crosses coherence with a length budget and a formality target, using the formality classifier setup from the GYAFC work in MUCOCO. It tests the prediction that length compression raises the spurious-edge rate mainly at jump points.

Human evaluation on a stratified sample of 300 outputs checks two things: that the automatic spurious-edge detector agrees with people, and that fluency does not drop under resampling.

Three results would decide the outcome. The hypothesis fails if the naive and alignment-trained baselines show no coherence-dependent rise in spurious edges, since then there is no trade-off to fix. The method fails if compute-matched best-of-$N$ equals it. The method succeeds if jump markers and verification together flatten the curve while each alone recovers only part of the gain.