Paying for Word Order: A Permutation Bottleneck for Cross-Lingual Parsing

A parser trained only on English and then applied to Hindi, Japanese, or Arabic loses accuracy roughly in proportion to how differently those languages order their words. The correlation between word-order distance and transfer loss is about 0.90 (On Difficulties of Cross-Lingual Transfer with Order Differences). Current fixes are blunt. Some delete or freeze positional information. Others rewrite English sentences into the target language's order, which requires a target-language treebank. We propose a softer, measurable alternative. For each English training sentence, generate several rearrangements that keep every phrase intact and leave the syntax tree unchanged. Then train the parser's word representations to carry as little information as possible about which rearrangement they came from, while still predicting the tree.

This is an information bottleneck: a training penalty that charges the model for every bit of information it keeps about some variable. Here the charge falls specifically on source word order given the words themselves, not on the input as a whole. A single knob sets how much order the model may retain. We also propose a way to set that knob using only English data. The payoff is a parser that should close more of the gap to distant languages than order deletion does, without the target-language resources that reordering needs. It also yields a direct diagnostic of how much English linear order a representation still encodes.

Core Claim

Order overfitting in cross-lingual transfer is a problem of conditional information. The representation should know the words and their hierarchical relations, but not whether English happens to put the object after the verb. Existing remedies act on the architecture rather than on that quantity, so they cannot tell useful local-order cues from harmful directional ones. We claim that directly penalizing $I(Z;\pi \mid X)$, the information a token's representation $Z$ carries about the arrangement $\pi$ of a fixed sentence $X$, estimated over tree-preserving permutations, will beat both order deletion and permutation data augmentation on typologically distant languages. We expect it to cost little on English and on close languages.

Relation to Prior Work

The method comes from Specializing Word Embeddings (for Parsing) by Information Bottleneck. That paper compresses contextual embeddings with a variational bottleneck, a stochastic layer whose Gaussian output is pulled toward a fixed prior. Its bottlenecked parsers beat uncompressed ELMo and MLP reduction in 8 of 9 languages. It also notes that contextual encoders cheat the bottleneck by pulling token identity from neighbors. However, it evaluates each language monolingually, and it compresses all input information rather than order specifically. We keep its variational machinery but replace the generic compression target with an order-specific one, and we move the question into zero-shot transfer.

The motivation comes from two order-reduction papers. On Difficulties of Cross-Lingual Transfer with Order Differences shows that an order-free self-attention encoder with non-directional distances and a graph decoder beats an RNN-plus-graph parser by 1.3 UAS and 1.2 LAS across 30 languages. It also finds that removing positional information entirely hurts, so some middle ground is needed. Do We Need Word Order Information for Cross-lingual Sequence Labeling shows that removing positional embeddings, shuffling tokens, or freezing multilingual BERT's positional embeddings helps slot filling. It leaves open tasks that need structure. Both papers pick the middle ground by hand. Our penalty makes the middle ground a continuous, learned quantity.

The main constraint comes from Improving Cross-lingual Transfer through Subtree-aware Word Reordering. It rewrites English training sentences into each target language's order by keeping subtrees whole and using ordering statistics from at least 1,000 target-treebank sentences. Trained as an ensemble of original and reordered English, it gains 2.3–4.1 LAS on distant languages and 2.0–6.1 exact match on MTOP. We borrow its insight that subtree-preserving permutations keep sentences meaningful. We differ in two ways. We sample permutations without any target data, and we enforce invariance across them rather than matching one target order. Older preordering work (Fast and Accurate Preordering for SMT using Neural Networks, Improving fast_align by Reordering) shows that reordering is valuable. It also shows the approach is brittle to parser errors (Han et al.). Our permutations are applied only to gold English training trees, and at test time nothing is reordered, so errors from parsing the input into a tree cannot cascade into the permutation step.

Interpreting Positional Information in Perspective of Word Order is the apparent counterpoint: preserving order more sharply improves En-De and En-Fr translation. We take this seriously. It is why we do not delete order but price it, and why the penalty is tuned rather than maximal.

Research Program

We would build the following. Start with a multilingual encoder (multilingual BERT and XLM-R base). Add a token-level variational bottleneck layer that outputs Gaussian posteriors $q(z_i \mid x, \pi)$. On top, place a biaffine graph parser. It scores arcs from $z$ together with a non-directional distance feature, following the order-free decoder of Ahmad et al., so that the parser's output space does not reward direction.

For each English UD training sentence, draw $K$ permutations $\pi_1,\dots,\pi_K$ of its gold tree. At every head, each dependent is placed left or right of the head, and every subtree stays contiguous, so the gold arcs and labels are identical across all $K$ versions. We compare three samplers: uniform random, biased toward head-final orders, and biased toward head-initial orders. None of them uses target-language data.

The training objective, for token $i$, is

$$\mathcal{L} = -\log p(y \mid z) + \frac{\beta_o}{K^2}\sum_{k,j} \mathrm{KL}\big(q(z_i \mid x,\pi_k)\,\|\,q(z_i \mid x,\pi_j)\big) + \beta_c\,\mathrm{KL}\big(q(z_i \mid x,\pi_k)\,\|\,\mathcal{N}(0,I)\big),$$

where $y$ is the gold tree, $\beta_o$ weights the order penalty, and $\beta_c$ is a small generic compression weight. The middle term is a closed-form upper bound on $I(Z;\pi \mid X)$ under uniform sampling of the $K$ permutations. The true quantity is the average KL from each posterior to the mixture of all $K$ posteriors, and convexity of KL bounds that by the pairwise average. Because the term compares the same token in different arrangements, it also directly penalizes the neighbor-leakage route that Li and Eisner had to patch with a separate type encoder.

Setting $\beta_o$ is the known weak point of bottleneck methods. We propose choosing it on a held-out English development set that has itself been permuted with the head-final sampler. The idea is that this set stands in for "English content in unfamiliar order." We will test whether this English-only criterion ranks $\beta_o$ values the same way that true target-language LAS does.

Baselines

The naive reference point is multilingual BERT or XLM-R with the same biaffine parser, fine-tuned on English UD with its positional embeddings trainable. This is what practitioners do by default, and it marks the size of the order-induced gap.

The first strong competitor is order reduction. We will run two versions. One freezes the encoder's positional embeddings during fine-tuning, as in Do We Need Word Order Information for Cross-lingual Sequence Labeling. The other is the order-free encoder and decoder setup of On Difficulties of Cross-Lingual Transfer with Order Differences. The latter reports +1.3 UAS and +1.2 LAS over an RNN-graph parser averaged across 30 UD languages. No absolute per-language LAS appears in the file, so we will reproduce its numbers on our encoder rather than quote them. These are the strongest target-free competitors because they attack the same failure with zero added cost.

The strongest existing method overall is subtree-aware reordering to the target order (Improving Cross-lingual Transfer through Subtree-aware Word Reordering), trained as its original-plus-reordered ensemble. Its reported result is a gain of 2.3–4.1 LAS for distant languages on UD v2.10. That result uses target treebank statistics we deliberately forgo, so we treat it as an upper reference. Matching it within about one LAS point without target data would count as a strong result. Beating it would be surprising.

Two ablations isolate our key ingredient. The first trains on the same $K$ tree-preserving permutations as plain data augmentation, with no invariance term ($\beta_o=0$). The second applies a standard variational bottleneck with only the generic term ($\beta_c$ tuned, $\beta_o=0$), as in Li and Eisner. We also include an adversarial baseline: a classifier tries to predict from $z$ whether each head precedes its dependent, and the encoder is trained through gradient reversal to defeat it.

Every system gets the same encoder, the same English training data (augmentation variants see the same $K$ permutations), the same number of optimizer steps, and an equal hyperparameter search budget of 20 trials. All model selection uses English-only development data, so no method sees target-language labels. Beating a baseline means a higher LAS averaged over the distant-language group, significant across three seeds, with English LAS within half a point.

Why not just…?

Why not just freeze or remove positional embeddings? This is the cheapest fix and a real threat on parsing, where Ahmad et al. already show that order-free components help. Their own finding, though, is that dropping position entirely costs local context, which is why they fall back to non-directional distance. Freezing leaves whatever directional bias the pretrained encoder already has. Our experiment settles the question directly: if frozen embeddings plus a non-directional decoder match our distant-language LAS, the penalty is not needed. We will also report the arc-direction probe for both, since a method can hold accuracy while still encoding English direction.

Why not just augment with the permuted sentences? This is the ablation we fear most. Tree-preserving augmentation alone may teach the parser to cope with other orders. The difference is that augmentation lets the model memorize a separate strategy for each order it sees, whereas the invariance term forces one representation to serve all of them. The prediction that separates the two is on target orders absent from the sampler's bias. If augmentation equals the full method there too, we will report that the gain comes from the data and not the bottleneck.

Why not reorder English into the target order? Arviv et al. show this works well. It needs about 1,000 target-treebank sentences per language and doubles training data through ensembling, and it gains least on languages near English. Our comparison against it on the same languages measures how much of its gain survives without target data. We will also report results on target languages that have no UD treebank for the reordering statistics, where their method cannot run.

Why not an adversarial order discriminator? Gradient-reversal adversaries remove only what one particular classifier can detect, and they are known to be unstable. The KL term measures order dependence without training a second network. We include the adversary as a baseline and compare both final accuracy and variance across seeds.

Proposed Experiments

The main experiment trains on English UD and evaluates zero-shot on the 30-language UD v2.2 set of Ahmad et al. We group languages by their word-order distance to English and report UAS and LAS per group. The central prediction is that the regression slope of transfer loss against order distance flattens relative to all baselines, with the largest gains on Hindi, Japanese, Korean, Turkish, and Arabic and near-zero change on French or Spanish.

Three checks decide whether the mechanism is real.

The first is a probing test. A linear probe trained on frozen $z$ to predict whether a head precedes its dependent should fall toward chance as $\beta_o$ rises. A probe predicting the attachment itself should not fall. If direction stays decodable while target LAS rises, our explanation is wrong.

The second is the $\beta_o$-selection test. The rank correlation between English-permuted-dev LAS and mean distant-language LAS across the sweep should be high. If it is not, the method needs target data to tune and loses its main advantage.

The third tests the Posnet tension. We apply the same penalty to MTOP semantic parsing, where Arviv et al. report 2.0–6.1 exact-match gains from reordering. If the penalty helps parsing but hurts this structured-output task at every $\beta_o$, that bounds where pricing order is useful.

Secondary analyses measure English accuracy cost as a function of $\beta_o$ and training overhead relative to the naive baseline. That overhead is roughly $K$ encoder passes, which we will compare against the ensemble cost of reordering.