Light Spanners as a Budget for Cross-Lingual Alignment

When a multilingual language model is aligned with only a few thousand translated sentence pairs, the usual training signal is pointwise: pull each sentence toward its translation and away from unrelated sentences. That signal says nothing about whether the shape of the target-language representation space matches the shape of the English space. Two Swahili sentences that are near-paraphrases may end up far apart, and two unrelated ones may be squashed together. This proposal borrows a tool from metric geometry, the light spanner, to control that shape cheaply. A spanner is a sparse graph over a point set whose shortest paths approximate every pairwise distance within a factor $t$. A light spanner is one whose total edge length is within a constant of the minimum spanning tree, the lightest graph that connects all the points. The central observation is simple. If a cross-lingual mapping preserves the lengths of the roughly $O(n)$ spanner edges, the triangle inequality guarantees it cannot stretch any of the $n^2$ pairs by much more. Those few edges are therefore a small, provably sufficient set of relations to supervise and to audit.

The proposal uses this in two ways. First, it serves as a certificate: a cheap, worst-case measure of how badly an aligned model distorts cross-lingual geometry, which can be compared with downstream transfer on XNLI. Second, it serves as a training signal: a relational loss on spanner edges, added to AFP-style contrastive alignment, with the aim of getting more alignment out of each parallel pair. That matters most for distant, low-resource languages, where parallel data is scarce and transfer is weakest.

Core Claim

Let $S$ be the hidden states of $n$ English sentences at a chosen layer, with Euclidean distance $d$. Let $f(u)$ denote the hidden state of the translation of sentence $u$. Let $H$ be a $t$-spanner of $S$. If every edge $(u,v)$ of $H$ satisfies $d(f(u),f(v)) \le (1+\delta)\, d(u,v)$, then chaining along the spanner path between any $u$ and $v$ gives

$$d(f(u),f(v)) \le t\,(1+\delta)\, d(u,v) \quad \text{for all pairs } u,v \in S.$$

Here $t$ is the spanner's stretch and $\delta$ is the worst edge expansion. Building a second spanner on the target side and checking the inverse direction bounds contraction the same way. Together the two spanners certify two-sided (bi-Lipschitz) distortion from about $O(n)$ edge checks instead of $n^2$.

The certificate holds for any metric, whatever its intrinsic dimension. Doubling dimension, a coordinate-free measure of how many half-size balls cover a ball, only governs how few and how light the edges are. The claim to be tested is that (a) this certified distortion predicts cross-lingual transfer better than average-case measures do, and (b) penalizing distortion on spanner edges makes a fixed parallel budget go further than pointwise contrastive alignment alone.

Where This Sits

The spanner side supplies the method. A light metric spanner showed that doubling metrics admit $(1+\epsilon)$-spanners with lightness $(\text{ddim}/\epsilon)^{O(\text{ddim})}$, independent of $n$. The Greedy Spanner is Existentially Optimal showed that the plain greedy algorithm matches this with constant degree. That algorithm sorts pairs by distance and adds an edge only when the current graph lacks a short enough path. We use the greedy spanner because it is simple and its stretch holds by construction. The guarantees on its size and weight are what make a relational loss over it affordable. Faster constructions such as A Unified Framework of Light Spanners I matter only if greedy becomes the bottleneck. None of these works touches learned representations.

The cross-lingual side supplies the problem and the constraints. AFP found that multilingual models keep languages in separate clusters. It showed that contrastive learning on translation pairs at the first transformer layer, combined with cross-lingual instruction following, largely removes those clusters using under one million pairs. It is our base method and main competitor. PreAlign argues that alignment after pretraining comes too late, reporting cross-lingual knowledge application of 90.3% versus 26.5% for joint training. That is a real challenge to any post-hoc method, so we treat PreAlign as a diagnostic comparison, measuring its certified distortion, rather than a method we try to beat at equal cost. CrossIn shows that about 5,000 mixed-language instruction samples suffice to surface latent multilingual ability, which motivates our small-budget regime.

The closest bridge is On Geometric Alignment in Low Doubling Dimension. It observed that cross-lingual word embeddings have low doubling dimension and used $k$-center coresets to speed up rigid Earth Mover's alignment of static 50-dimensional vectors. It collapses points into disconnected weighted centers, preserves no pairwise relations, and does not train a model. We keep every point, preserve relations through a spanner, and use the result inside contextual model training. Graph-Based Vector Search constrains the design. Its finding that pruned nearest-neighbor graphs work well but carry no stretch or weight guarantee is exactly why a k-nearest-neighbor graph is the natural ablation here.

Research Program

The first stage is measurement. Using XGLM-564M, the model AFP studies, we take XNLI's parallel development sentences across its 15 languages. For each English–target pair, we build greedy spanners on the English and target hidden states at the first layer and a middle layer, with $t \in \{1.1, 1.5, 2\}$. For $n$ up to roughly 20,000, exact greedy on all pairs is feasible offline. Beyond that, we restrict candidate pairs to an approximate-nearest-neighbor graph and verify stretch on held-out random pairs, reporting any violations. We record spanner size and lightness as an empirical proxy for intrinsic dimension, along with the two-sided certified distortion. We do this for the base model, AFP-aligned models, and small PreAlign-style models at the 150M scale. This directly addresses a gap neither alignment paper covers: what alignment does to the geometry.

The second stage is training. We add a relational term to AFP's first-layer contrastive loss:

$$L_{\text{rel}} = \sum_{(u,v) \in H} \big(\log d(f(u),f(v)) - \log d_0(u,v)\big)^2,$$

where $d_0$ is distance in a frozen snapshot of the English hidden states and $H$ is the spanner over the English side of the parallel budget. Minibatches are built from spanner neighborhoods so that each edge's endpoints appear together. We sweep parallel budgets of 1k, 5k, 20k, and 100k pairs drawn from the UN, Europarl, OpenSubtitles, and Bible corpora used by XNLI. The emphasis falls on Swahili, Urdu, Thai, and Hindi, where transfer is known to be weakest.

Baselines

The naive reference is the unaligned XGLM-564M evaluated zero-shot, together with Translate-Test. Translate-Test runs machine translation of each test item into English followed by the English model. XNLI reports it as strong, with English accuracy around 73.7% and a gap of about 3–6 points for the best translation-based methods.

The strongest competitor is AFP itself, re-run with its contrastive and instruction-following objectives on exactly the same parallel pairs, steps, and hyperparameter search budget as our method. AFP's paper reports that it reduced the English–Chinese XNLI gap for XGLM-564M by 6.53%, with an average improvement of 3.31% across five datasets. Beating it means that, at equal pair budget, adding $L_{\text{rel}}$ raises average target-language XNLI accuracy, with a larger gain on distant languages. Equivalently, it means matching AFP's full-budget accuracy with a quarter of the pairs.

Four ablations isolate the key ingredient, each using the same loss form and a similar edge count. The first uses the minimum spanning tree, which is maximally light but has unbounded stretch, and isolates what the stretch guarantee buys. The second uses a k-nearest-neighbor graph, which is local but carries no long-range guarantee. The third uses random pairs. The fourth uses all in-batch pairs, which is dense but mostly long-range.

Why not just…?

Why not just add more parallel data or translate the training set? Cost is the point. Active Learning for Multilingual Semantic Parser shows that careful choice reaches within 5% of full-translation performance using 32% of the data. CrossIn found that explicit translation tasks added little on top of mixed instruction data. Our budget sweep measures directly how many extra AFP pairs equal the relational gain. If that number is small, the method is not worth its complexity, and we will say so.

Why not a relational loss over all in-batch pairs, which is also cheap? This is the most serious threat. Random batches rarely contain near-paraphrases, so the in-batch loss mostly constrains long distances, whereas spanner edges are dominated by short ones. The in-batch ablation, and a variant using spanner-neighborhood batches without restricting the loss to edges, settles it. If in-batch matches spanner edges, the contribution reduces to the certificate.

Why not a k-nearest-neighbor graph, as vector-search indexes use? A k-nearest-neighbor graph can be disconnected and gives no bound on pairs it does not contain, so it cannot certify anything. Whether it trains as well is an empirical question answered by the ablation. It is also a real threat for the training use.

Proposed Experiments

The decisive checks are three.

The first is predictive. Across 14 target languages and five model variants (base, AFP at two budgets, ours, and PreAlign-style), we ask whether certified worst-case distortion predicts the XNLI English–target gap better than mean pairwise distortion or cosine similarity between translation pairs, measured by rank correlation. If average-case measures predict equally well, the certificate has no practical value.

The second is data efficiency. We plot target XNLI accuracy against parallel budget for AFP and AFP plus $L_{\text{rel}}$, with all four graph ablations, and report the budget each method needs to reach AFP's 100k-pair accuracy. We also report PAWS-X and Cross-XQuAD, the latter using CrossIn's accuracy-plus-consistency score. CrossIn reports 30–40% relative improvement on that score over English-tuned models.

The third is geometric. We test whether distant languages have larger spanner lightness, which would indicate higher intrinsic dimension, and whether alignment reduces it. This would give the first geometric account of why transfer to typologically distant languages is harder.

A negative outcome is also informative: certified distortion falling while XNLI does not improve would show that metric shape is not the bottleneck for low-resource transfer.