A parser trained only on English and then run on Hindi or Japanese works roughly like a linear approximation of a nonlinear system. It is accurate near the point where it was fitted, which is English-like word order, and it becomes unreliable as the input moves away from that point. Robotics already has a working recipe for this situation. Engineers treat the error of a linearized model as a bounded quantity that grows with distance from the operating point, and they tighten safety margins only where that bound is large. Uniform margins either let the system violate constraints or freeze it in place. We propose to apply the same recipe to inference-time correction of cross-lingual dependency parsers. The parser's output is corrected toward target-language word-order statistics, with the strength of the correction set sentence by sentence. Sentences whose surface order looks English-like are left almost untouched. Sentences far from English are pulled hard toward typological expectations. The size of each correction comes from an empirically fitted, conservative envelope on how wrong the English parser is likely to be at that distance.
This matters because the best existing inference-time method applies one corpus-level constraint to every sentence of a target language. It already yields large gains on distant languages, but it gives no handle on the sentences it damages and no account of when its constraints should bind. Our claim is narrow and testable. Making constraint strength depend on each sentence's local structural distance from the source language, through a calibrated error envelope, beats the best-tuned uniform constraints. The gain should show up both in attachment accuracy and in protecting the target sentences that the base parser already handles well.
Core Claim
Target Language-Aware Constrained Inference for Cross-lingual Dependency Parsing (Meng et al.) keeps an English-trained parser fixed. It adjusts the parser's output distribution so that expected counts of three word-order features match corpus-level ratios from the World Atlas of Language Structures (WALS): noun–adposition, noun–adjective and noun–head order. The adjustment is done with Lagrangian relaxation or posterior regularization. This motivates our work: gains correlate with word-order divergence from English at $r = 0.938$. That correlation is exactly the "error grows with distance from the operating point" signature. Implicit Word Reordering with Knowledge Distillation for Cross-Lingual Dependency Parsing reports the matching failure from the other side, a correlation of $r = -0.88$ between word-order distance and parsing accuracy. Neither paper uses distance at the level of the individual sentence. Meng et al. impose the same constraint on every sentence of a language, including target sentences whose local order is English-like, where the base parser is probably right and the constraint can only hurt. This is the language analog of the "conservatism trap" that Iterative Convex Optimization for Model Predictive Control with Discrete-Time High-Order Control Barrier Functions describes. There, fixed linear safety planes discard large parts of the feasible space.
The method we borrow comes from Nonlinear Robust Optimization for Planning and Control. That paper treats the Taylor remainder of a linearized model as a deterministic, state-dependent bounded disturbance. In its car-steering benchmark, this raises constraint satisfaction from 84.2% for standard robust optimization to 100%. Conservative Linear Envelopes for Nonlinear, High-Dimensional, Hamilton-Jacobi Reachability does the same for reachability analysis, and it warns that envelopes become too conservative when the bound is loose over a wide operating range. We take the structural idea from these papers but not their guarantees. A parser's error cannot be bounded analytically the way a Taylor remainder can. We therefore fit the bound empirically on languages with treebanks and test its coverage on held-out languages. This is the main departure from the control literature, and we state it openly rather than claiming formal guarantees.
Method
Let $p(y \mid s)$ be the fixed English-trained biaffine parser's distribution over trees $y$ for a target sentence $s$. Let $\phi_k(y)$ count the arcs of order type $k$ in $y$, for example the number of adpositions placed after their noun.
We first compute a local structural distance $d_k(s)$ from the input alone, using predicted part-of-speech (POS) tags. It is the surprisal of the POS bigrams relevant to feature $k$ under an order model estimated on English POS sequences. The distance is high when the sentence's local order around nouns, adpositions and verbs is un-English.
Two error envelopes are then fitted on a pool of development languages with gold trees, using leave-one-language-out quantile regression at level $1-\alpha$. The first is the base-model envelope $g_k(d)$. It bounds $|\mathbb{E}_p[\phi_k] - \phi_k(y^*)|$, the gap between what the parser expects and the gold count, as a function of distance. It plays the role of the linearization remainder. The second is the prior envelope $v_k$. It bounds how far a single sentence's gold count deviates from the target-language prior $\mu_k(s)$, where $\mu_k(s)$ is the WALS-derived ratio times the number of candidate pairs. It captures legitimate sentence-level exceptions to typological tendencies.
Inference then solves a posterior-regularization problem. It seeks the distribution $q$ closest to $p$ whose expected counts lie inside both envelopes:
$$ \min_{q} \ \mathrm{KL}(q \,\|\, p) \quad \text{s.t.} \quad \big|\mathbb{E}_q[\phi_k] - \mu_k(s)\big| \le v_k, \qquad \big|\mathbb{E}_q[\phi_k] - \mathbb{E}_p[\phi_k]\big| \le g_k(d_k(s)) \quad \forall k. $$
When $d_k(s)$ is small, $g_k$ is small and $q$ stays close to the parser even if the prior disagrees. When $d_k(s)$ is large, $g_k$ widens and the prior constraint dominates.
If the two intervals do not intersect for some $k$, the constraints for that feature are infeasible. In that case we widen the narrower envelope by the minimum amount needed, and we log the event as an infeasibility rate. This is the parsing counterpart of the infeasible-subproblem problem in the control papers, and it is a diagnostic we report.
The dual of this problem has one multiplier pair per feature per sentence. It reuses the projected-gradient machinery of Meng et al., so the cost is a small constant factor over their method and requires no retraining.
Research Program
The work has three stages. The first establishes the empirical premise. On the development languages we test whether base-parser error on feature $k$ actually rises with sentence-level $d_k(s)$ within a language, not only across languages. Meng et al. and Li et al. report only cross-language correlations, and a within-language effect is what this proposal needs. If the within-language relationship is flat, the idea reduces to per-language tuning and we stop there.
The second stage fits and validates the envelopes. We report held-out coverage, meaning how often the true error exceeds $g_k$ on unseen languages, alongside envelope width. The trade-off between coverage and width is the analog of the trade-off between satisfaction rate and conservatism in Nonlinear Robust Optimization for Planning and Control.
The third stage extends the feature set beyond Meng et al.'s three relations to object–verb and relative-clause order. A target-language POS-only order model, in the spirit of the order-free teacher of Li et al., supplies $\mu_k(s)$ where WALS is silent.
A secondary question connects to the few-shot trade-off documented by Do We Need Word Order Information for Cross-lingual Sequence Labeling. That paper finds that removing word order helps zero-shot transfer, but the advantage disappears as target labels grow from 1% to 10%. In our method a handful of target trees can refit $g_k$ for that language. The question is whether the envelope tightens smoothly toward the unconstrained parser as data grows, rather than imposing a fixed trade-off.
Baselines
The naive reference point is the English-trained biaffine parser applied zero-shot with no inference-time adjustment. We use the setup of Meng et al., trained on English UD v2.2 and evaluated on their 19 target languages across 13 families. Every other method is reported as a change over this parser.
The strongest existing inference-time competitor is Meng et al.'s constrained inference with Lagrangian relaxation and with posterior regularization. It is the right opponent because it uses the same fixed parser, the same WALS knowledge and the same optimization family. Any gain we show is therefore attributable to the distance-scaled envelopes and not to extra information. Meng et al. report an average UAS improvement of 3.5 points for Lagrangian relaxation and 3.1 for posterior regularization across the 19 languages, with gains of 19.1 points on Hindi and 15.7 on Urdu. UAS, the unlabeled attachment score, is the share of words given the correct head. We will rerun their method rather than copy numbers. Both methods get identical predicted POS tags, the same constraint features (the original three in the head-to-head comparison) and the same development-language pool for tuning their constraint margins. Beating it means a higher 19-language average UAS than our rerun of their best variant, with no average loss on the near-English languages. Because our method spends more of its tuning on the development pool, we also give Meng et al. per-language margins tuned on that pool.
The strongest training-time competitor is IWR-KD from Li et al. It distills an order-free target-POS teacher into the student parser and reports an average of 74.1 UAS and 61.7 LAS over 31 languages on UD v2.14. LAS, the labeled attachment score, additionally requires the correct relation label. Its per-language numbers for Japanese and Korean are not available in the file. Our method is inference-only, so the fair comparison is our method on the base parser versus IWR-KD. The more interesting test is our method applied on top of IWR-KD, in their 31-language setting with their source and target split. Showing complementarity there would count as success even if IWR-KD alone beats our method alone.
Two ablations isolate the key ingredient. The distance-blind envelope replaces $g_k(d)$ with its average over $d$. This makes the method a sentence-level version of Meng et al. with no distance dependence and tests whether distance carries the gain. The confidence-gated variant replaces $d_k(s)$ with the base parser's own arc entropy. It tests whether a model-internal uncertainty signal suffices. We also vary the quantile level $\alpha$ to trace the trade-off between accuracy and conservatism.
Why not just…?
Why not just tune a single constraint strength per target language? This is the most serious threat. If error does not vary with structure within a language, per-language tuning captures everything our method does. The distance-blind ablation, with per-language tuned margins, is exactly this alternative. The first stage of the program tests the premise directly by measuring the within-language slope of error on $d_k(s)$. If the slope is negligible, we will report that per-language tuning suffices and drop the claim.
Why not just gate constraints by the parser's own confidence? Entropy-based gating needs no envelope fitting and is a natural reviewer suggestion. The concern is that neural parsers trained on English may be confidently wrong on head-final order. That is the structural overfitting that On the Cross-lingual Transferability of Monolingual Representations and COSY: COunterfactual SYntax for Cross-Lingual Understanding document, so confidence may not track error under this kind of shift. We do not assume this. The confidence-gated variant is run head to head, and we also report how well entropy versus $d_k(s)$ predicts per-arc error on held-out languages. If entropy wins, the proposal simplifies to entropy-scaled envelopes.
Why not just remove word order from the model? Do We Need Word Order Information for Cross-lingual Sequence Labeling shows that order-reduced Transformers gain 3.69 F1 over standard Transformers zero-shot. The same paper shows the advantage vanishing once modest target data exists. Li et al. also argue that order-agnostic parsing gives up cues needed for fine-grained relations. Order removal is a uniform, maximally conservative envelope, which is the situation our method is designed to avoid. We include an order-reduced parser in the 19-language comparison to measure this rather than assert it.
Why not just translate into English and parse there? For dependency parsing, translate-test returns a tree over different words and would need an alignment-projection step, so it is not comparable on UAS. XNLI: Evaluating Cross-lingual Sentence Representations notes that translation pipelines are computationally heavy and degrade with machine-translation quality on low-resource languages. We treat translation as out of scope for the parsing comparison and say so, rather than build a weak version of it.
Proposed Experiments
The primary experiment reproduces Meng et al.'s 19-language UD v2.2 setting. Development languages for envelope fitting come from the UD languages outside the evaluation set, so no evaluation language ever informs its own envelope. We report UAS and LAS per language. We also report three diagnostics: held-out envelope coverage, the infeasibility rate (how often the two envelopes fail to overlap before widening), and accuracy on a target-side subset.
That subset gives the decisive check. Within each distant target language, we split sentences by $d_k(s)$ into an English-like tercile and a far tercile. The proposal predicts two things. On the English-like tercile, uniform constraints from Meng et al. lower accuracy relative to the base parser while our method does not. On the far tercile, our method matches or exceeds them. If both methods behave the same on the English-like tercile, then local distance is not doing the work, whatever the averages say.
The secondary experiment runs on UD v2.14 in Li et al.'s 31-language setting and applies our inference on top of IWR-KD to test complementarity. The few-shot extension refits $g_k$ with 10, 50 and 200 target trees for the distant languages. It checks whether the gap to the unconstrained parser closes smoothly, which would show the envelope adapting to data instead of fixing a trade-off in advance.
References
- Target Language-Aware Constrained Inference for Cross-lingual Dependency Parsing
- Implicit Word Reordering with Knowledge Distillation for Cross-Lingual Dependency Parsing
- Iterative Convex Optimization for Model Predictive Control with Discrete-Time High-Order Control Barrier Functions
- Nonlinear Robust Optimization for Planning and Control
- Conservative Linear Envelopes for Nonlinear, High-Dimensional, Hamilton-Jacobi Reachability
- Do We Need Word Order Information for Cross-lingual Sequence Labeling
- On the Cross-lingual Transferability of Monolingual Representations
- COSY: COunterfactual SYntax for Cross-Lingual Understanding
- XNLI: Evaluating Cross-lingual Sentence Representations