When a pretrained language model turns a meaning graph into a sentence, it never sees the graph itself. It sees a string: the graph written out in some traversal order, with each token's position standing in for where that concept sits in the graph. That substitution is a metric embedding, meaning a map that places the graph's nodes at points in another space so that the distances between points should mirror distances in the graph. Here the other space is a line, and some pairs end up badly stretched. Two concepts one edge apart, such as a predicate and an argument it shares with another predicate, can land dozens of tokens apart. Metric embedding theory says this stretch cannot be avoided. Some trees need distortion growing like $\sqrt{n}$ even in the plane (Plane Embeddings of Planar Graph Metrics.), and a line can do no better than the plane it sits inside.
We propose to treat the distortion of the model's position signal as an experimental dial instead of an accident of formatting. The dial runs from the usual one-line encoding, which distorts heavily but carries a strong word-order hint, to encodings that are almost distance-preserving but carry no order. Turning it lets us measure a trade-off no one has measured. Meaning graphs are deliberately underspecified: they omit word order, articles, and tense, so one graph matches many valid sentences. A traversal order quietly supplies a guess at surface word order. Removing distortion therefore also removes that guess and forces the model to infer order on its own. Our claim is that the faithfulness errors of graph-to-text models (dropped arguments, swapped roles, invented content) concentrate on high-stretch node pairs. We further claim that a moderate number of position coordinates gets most of the faithfulness benefit of a distance-preserving encoding while keeping the order hint that fluency relies on.
Core Claim
Two linked hypotheses carry the proposal. The first is diagnostic. In standard PENMAN fine-tuning (PENMAN is the bracketed depth-first text format for AMR graphs), the probability that a graph relation is dropped or role-swapped in the output rises with how much the linearization stretches that relation's endpoints. The effect is strongest at re-entrancies, nodes with several parents that often encode coreference. The second is interventional. If each token gets $m$ position coordinates instead of one, each coordinate a one-dimensional distance taken from a shortest-path decomposition of the graph, then position distortion falls as $m$ grows. Faithfulness should improve along with it, up to a point where the lost order hint begins to hurt fluency. The thing that would be new is the dose-response curve and the encoding that lets us trace it. Here dose means distortion of the position channel, and response means faithfulness and fluency. A new state-of-the-art BLEU score is not the goal.
To make "distortion" concrete for a model, let $d_G(u,v)$ be the shortest-path distance between concepts $u$ and $v$ in the undirected AMR graph. Let $p(u,v)$ be the distance the encoding presents to the model. For a single linearization this is the token offset. For $m$ coordinates it is the sum of per-coordinate offsets. We measure average stretch over the pairs that carry meaning, namely those joined by a labeled edge or sharing a re-entrant node:
$$\mathrm{stretch}(G) = \frac{1}{|E_{\mathrm{sem}}|}\sum_{(u,v)\in E_{\mathrm{sem}}} \frac{p(u,v)}{d_G(u,v)},$$
where $E_{\mathrm{sem}}$ is that set of pairs. We use the average because the worst case is fixed by the lower bounds above and is uninformative on graphs of about twenty nodes.
Where This Sits in Prior Work
Several papers motivate the gap. Promoting Graph Awareness in Linearized Graph-to-Text Generation shows that T5 loses up to 20 to 30 BLEU when the same graph is linearized differently, and adds scaffolding losses (masked graph modeling, reordering) as a fix. It treats linearization as an ordering nuisance and never quantifies how far each ordering bends the graph's distances. Investigating Pretrained Language Models for Graph-to-Text Generation finds that pretrained models keep high BLEU even on shuffled bags of labels. That is direct evidence the order hint and the model's memory do much of the work. A Human Evaluation of AMR-to-English Generation Systems attributes 37% of low-adequacy outputs to missing information and 18% to added information. Those error categories are the response variable we will relate to stretch.
The closest structural work is Investigating the Effect of Relative Positional Embeddings on AMR-to-Text Generation with Structural Adapters. It shows that relative position embeddings over the linearized string carry implicit graph-distance information, which matters both for BLEU and for robustness to edge deletion. We take that finding as a premise and make the position channel the object we vary, which that paper does not do. Two older systems, Generation from Abstract Meaning Representation using Tree Transducers and AMR-to-text generation as a Traveling Salesman Problem, already use graph geometry for realization. The first breaks re-entrancies with an ad hoc breadth-first spanning tree. The second feeds shortest-path distance as one feature into a word-ordering cost. Both use distance heuristically inside pre-neural pipelines. Neither measures the distortion they introduce.
The construction is borrowed from Metric Embedding via Shortest Path Decompositions. That paper repeatedly removes a shortest path and gives each vertex coordinates based on its distance to the removed path and to the path's root. Graphs that decompose in few rounds, which includes trees and near-trees like most AMRs, embed with distortion depending on that depth and not on graph size. We use the coordinate recipe, not the worst-case guarantee: AMRs are small, and the theory's sawtooth randomization exists to control expansion on large graphs. We will test whether it matters at all. Two other theory results act as constraints. Plane Embeddings of Planar Graph Metrics. rules out any single clever linearization fixing distortion, since a line cannot beat the plane. Labelings vs. Embeddings: On Distributed Representations of Distances distinguishes giving each node its own distance-preserving coordinates from giving each pair a label. That is the same distinction as between our coordinate encoding and simply handing the model a pairwise distance matrix, and it frames the most important baseline below.
Research Program
The first stage is pure measurement and needs no new model. We fine-tune T5 on AMR 2.0 (LDC2017T10) with canonical PENMAN input. We then compute the stretch of every semantic pair under the canonical and the randomized linearizations from the graph-awareness study. Each output is parsed back to an AMR and aligned to the gold graph, and every gold relation is marked as realized, dropped, or role-swapped. A logistic model then predicts the failure of each relation from its stretch, controlling for depth, edge label, node frequency, and graph size. If stretch does not predict failure once these controls are in, the program stops there. That negative result would be worth publishing: it would mean linearization brittleness is about memorized formatting, not distance.
The second stage builds the dial. For each graph we run the shortest-path decomposition on the undirected AMR. Each round contributes a coordinate per node: position along the removed path for nodes on it, and distance to the path plus offset of the nearest path point for nodes off it. The first coordinate is always the canonical PENMAN token position, so $m=1$ recovers standard fine-tuning exactly. Every coordinate gets its own copy of T5's bucketed relative-position bias, initialized from the pretrained bias, and the biases are summed inside attention. Pretrained position knowledge therefore transfers to every coordinate, and the only new parameters are scalar mixing weights. We sweep $m$ from 1 up to the decomposition depth. As a zero-distortion endpoint we also include an encoding that biases attention directly by exact graph distance. At each setting we record the measured stretch, BLEU, chrF++, parse-back Smatch (overlap between the parsed output graph and the gold graph), and per-relation drop and swap rates.
The third stage asks whether the order hint is what $m$ trades away. We run the same sweep with canonical, randomized, and reference-oracle linearizations as coordinate one. The oracle orders concepts by their aligned position in the reference sentence and is used only as a diagnostic upper bound, never at test time. If fluency loss at large $m$ disappears under the oracle, the trade-off is about underspecified word order, as claimed.
Baselines
The naive reference point is T5-large fine-tuned on canonical PENMAN with no structural additions, trained on LDC2017T10 with the same steps and learning-rate search as every other system. This is $m=1$ in our sweep, so beating it on faithfulness is necessary but not sufficient. For context, the strongest published number in the file is 49.72 BLEU on LDC2017T10 for T5-large with task-adaptive pretraining on 2 million silver graphs (Investigating Pretrained Language Models for Graph-to-Text Generation). That system uses silver data we will not use in the main comparison. We will report against our own non-pretrained reproduction, and add silver pretraining to both arms only if compute allows. GPT-too: A language-model-first approach for AMR-to-text generation reports 33.02 BLEU and 63.89 chrF++ on the same split with cycle-consistency reranking, and serves as the faithfulness-by-reranking reference.
The strongest structural competitor is the structural-adapter model with relative position embeddings from Investigating the Effect of Relative Positional Embeddings on AMR-to-Text Generation with Structural Adapters. It reports 35.1±0.5 BLEU under graph attack with a GCN adapter on LDC2020T02, versus 13.9±0.5 without position embeddings. We will rerun it on LDC2020T02 at matched size and tuning budget, under both clean and attacked inputs. Beating it means higher parse-back Smatch and lower relation-drop rate on clean input at equal or better BLEU, with at least the same robustness under attack.
The scaffolding method of Promoting Graph Awareness in Linearized Graph-to-Text Generation is run with its auxiliary losses on the same data. It is the main competitor on robustness to randomized linearization, and beating it means a smaller BLEU drop between canonical and randomized input.
Two ablations isolate the key ingredient. The first gives the model $m$ coordinates taken from $m$ random traversal orders instead of shortest-path rounds. This keeps the number of channels fixed but drops the structure, which tells us whether the decomposition matters or whether any extra positions help. The second is the exact-graph-distance bias. It removes distortion entirely, and it is the test of whether per-node coordinates offer anything over pairwise distances.
Why not just…?
Why not just give the model exact graph distances as an attention bias? This is the real threat. If it matches our best $m$ on both faithfulness and fluency, the coordinate construction adds nothing and the conclusion is simply "remove distortion." We include it as an endpoint of the sweep for that reason. Our prediction rests on the bag-of-labels finding of Investigating Pretrained Language Models for Graph-to-Text Generation: pretrained models lean on order cues. The prediction is that exact distances, which are symmetric and carry no order, will raise Smatch but cost fluency, especially on longer graphs. The oracle-order experiment will show whether that cost comes from lost order information. If exact distances win outright, we will report that as the main result.
Why not just train on many random linearizations? Augmentation teaches invariance to order without lowering stretch: every training string still places some semantic pairs far apart. The random-coordinates ablation tests a close cousin of this idea. The scaffolding baseline, which includes a reordering objective, is reported to lose its benefit as data grows (Promoting Graph Awareness in Linearized Graph-to-Text Generation). We will add plain augmentation as an extra arm. If it closes the faithfulness gap at equal compute, the stretch hypothesis is in trouble.
Why not just use a graph neural encoder or adapter? Graph adapters see true adjacency, yet Investigating the Effect of Relative Positional Embeddings on AMR-to-Text Generation with Structural Adapters found that they still lose 12.5% BLEU without sequence position embeddings. Graph structure alone does not replace the position channel; the two interact, which is exactly what our sweep measures. The adapter is our strongest structural baseline above, so this question is settled empirically.
Why not just rerank outputs by parsing them back? Reranking only selects among candidates the generator already produced. If high-stretch relations are systematically dropped, every candidate may drop them. We will apply the same parse-back reranker on top of both the $m=1$ model and our best model. If reranking alone matches our gain, the position-channel story is unnecessary.
Proposed Experiments
Data are AMR 2.0 (LDC2017T10) for the main study and AMR 3.0 (LDC2020T02) for the comparison with structural adapters. We additionally report results on the subset of test graphs containing re-entrancies and on the largest graph-size quintile, where stretch is highest.
Metrics are BLEU and chrF++ for comparability. Faithfulness is measured by parse-back Smatch and by per-relation drop and swap rates. The robustness gap is BLEU under canonical minus BLEU under randomized linearization. On 300 sampled outputs per system, a human evaluation follows the adequacy categories of A Human Evaluation of AMR-to-English Generation Systems (missing, added, incomprehensible). Because that study reports only moderate agreement on error types (kappa 0.28 to 0.53), we will double-annotate and report agreement.
Three results decide the outcome. First, in the stage-one regression, stretch must predict relation failure beyond the controls. Without that, the premise fails. Second, the sweep must show that relation-drop rate falls as measured stretch falls. The shortest-path coordinates must reach a given faithfulness level at lower $m$ than random coordinates. Otherwise the decomposition is not doing the work. Third, fluency must dip at the distortion-free endpoint, and the dip must vanish under oracle order. That pattern would confirm that the trade-off comes from the graph's missing word order, and it would identify the intermediate $m$ as the setting worth using. A flat curve on any of these is a clear, publishable negative result.
References
- Plane Embeddings of Planar Graph Metrics.
- Promoting Graph Awareness in Linearized Graph-to-Text Generation
- Investigating Pretrained Language Models for Graph-to-Text Generation
- A Human Evaluation of AMR-to-English Generation Systems
- Investigating the Effect of Relative Positional Embeddings on AMR-to-Text Generation with Structural Adapters
- Generation from Abstract Meaning Representation using Tree Transducers
- AMR-to-text generation as a Traveling Salesman Problem
- Metric embedding via shortest path decompositions
- Labelings vs. Embeddings: On Distributed Representations of Distances
- GPT-too: A Language-Model-First Approach for AMR-to-Text Generation