Scaling Unsupervised Word Alignment to Documents via Structural Constraints

AI summary

Overview

• Research area: Natural Language Processing, specifically unsupervised word alignment (finding which words correspond across a translated text pair), extended from the sentence level to the full-document level.
• Technical level: Advanced. The paper assumes familiarity with embedding-based alignment, cosine similarity matrices, alignment error rate (AER), and coarse-to-fine search; it is not an introductory read.
• Scope: The paper proposes two training-free methods (MDPAlign and CTFAlign) that constrain the search space of document-length token similarity matrices, evaluates them across six language pairs and three multilingual encoders, and shows the gains transfer to two downstream tasks.

What This Paper Is About

Word alignment — identifying which words in a text correspond to which words in its translation — has almost always been studied between individual sentences. Modern multilingual embedding models can now encode entire documents in one pass, so the paper asks whether sentence-level alignment algorithms can simply be applied to whole documents. The authors show that doing so causes severe performance degradation because document-scale similarity matrices are larger and noisier, and they propose two structural constraints that restrict the alignment search space without any sentence segmentation, sentence alignment, or model training.

Key Contributions

1. MDPAlign (Main Diagonal Prior): A lightweight method that applies a positional prior to the token similarity matrix, biasing alignments toward the main diagonal, with either a "strict" hard-banded or "fuzzy" Gaussian-decay masking scheme.
2. CTFAlign (Coarse-to-Fine Alignment): A method that recursively identifies likely alignment regions at coarse grid resolutions (starting from a 2×2 grid) and zeroes out all regions not retained, refining to token resolution; it includes buffer-based neighborhood retention and a recovery step for blocks with fully empty rows and columns.
3. A multi-pair, multi-encoder empirical study: Evaluation across six language pairs (en–fr, en–ro, en–ja, en–zh, en–cz, la–gr) that vary in typological distance, resourcedness, and document length, using Qwen3-Embedding-4B, mmBERT-base, and LaBSE.
4. Downstream validation and released artifacts: Demonstrating transfer to translation coverage evaluation (omission/addition detection) and recognition of semantic differences (RSD), plus release of a Python package and public code and data.

Main Findings

• Unconstrained document-level alignment collapses: Applying SimAlign directly to full documents degrades alignment quality across all models and language pairs relative to sentence-level performance. With mmBERT on long documents (en–fr, en–ja, la–gr), document-level AER can exceed 0.8 (en–ja, la–gr). Manual inspection attributed many spurious alignments to repeated named entities, conjunctions, prepositions, and punctuation.
• Average AER reduction: Averaged over three models, CTFAlign reduces word alignment error rate from 0.412 to 0.326.
• CTFAlign+Argmax is the most robust configuration: Averaged over all six language pairs it brings average AER down from 0.341 to 0.248 with LaBSE, within 0.041 of the sentence-level upper bound (0.207), and closes the gap between sentence- and document-level alignment with Qwen (0.294 vs. 0.295).
• MDPAlign works when alignments stay near the diagonal: It improves over the unconstrained baseline on document pairs whose alignment paths stay close to the global diagonal, but it fails on en–ja, where it falls under the unconstrained baseline (Qwen + MDPAlign 0.752/0.728 vs. SimAlign 0.602), because en–ja gold labels show curved alignment paths that a fixed diagonal prior systematically penalizes.
• CTFAlign adapts to curved or shifted alignment regions: On en–ja with LaBSE, CTFAlign+Itermax reaches 0.481 AER, closing more than two thirds of the gap to the sentence-level baseline; on la–gr with Qwen, CTFAlign+Argmax meets the sentence-level upper bound (0.293 vs. 0.292); on en–fr with LaBSE it achieves the strongest document-level result overall (0.068), despite en–fr being the longest document pair in the dataset.
• Document-level can surpass sentence-level for Qwen: With Qwen, document-level word alignment surpasses sentence-level alignment for en–ro across all configurations, en–ja with CTFAlign, and la–gr and en–cz with CTFAlign+Argmax.
• Encoder choice interacts with the constraints: With mmBERT, CTFAlign is outperformed on average by MDPAlign (0.437 vs. 0.387 AER for the Argmax variants). Because CTFAlign refines recursively, coarse-resolution errors can propagate, whereas MDPAlign's fixed band sidesteps that failure mode.
• Pairwise cross-lingual supervision is associated with alignment quality: LaBSE remains the strongest embedding model across nearly all settings despite being smaller and older. LaBSE was explicitly trained on large-scale translation pairs; Qwen underwent contrastive embedding training on large-scale multi-task text pairs including bitext-mining data; mmBERT was pretrained as a general-purpose masked language model without parallel data or a pairwise embedding objective. The authors rule out gold sentence segmentation as the primary reason for LaBSE's strength, since sentence embedding concatenation improves mmBERT-base only slightly (Table 9).
• 1-shot LLM prompting does not scale to documents: With GPT-5.4-mini, sentence-level AER is competitive on some pairs (la–gr 0.179, en–fr 0.185), but document-level AER collapses to near 1.0 on all six pairs (0.995, 0.968, 0.986, 0.935, 0.996, 0.982).
• Downstream task 1 — translation coverage evaluation: With Qwen3-Embedding-4B, DiffAlign CTF+Argmax is strongest at the document level on both language pairs and both error types, improving over unconstrained DiffAlign by +0.055 (ja–zh omissions), +0.008 (ja–zh additions), +0.036 (en–de omissions), and +0.02 (en–de additions) in ROC AUC.
• Downstream task 2 — recognition of semantic differences: On SwissGov-RSD, search-space restriction improves over the DiffAlign baseline across all three language pairs (+0.044 en–de, +0.033 en–fr, +0.035 en–it in Spearman ρ), with DiffAlign CTF+Argmax establishing new state-of-the-art results. MDPAlign offers little improvement and underperforms the baseline on en–it.
• En–ja and la–gr document-level gaps narrow to thousandths in places: en–ro with LaBSE + MDPAlign + Itermax (0.222 document- vs. 0.220 sentence-level), and en–zh with mmBERT + MDPAlign + Argmax (0.200 vs. 0.192).

Methodology in Plain English

The authors start from SimAlign, which uses a multilingual encoder to turn each word into a vector and then builds a table of cosine similarities between every source word and every target word. On sentences this table is small enough that picking the highest-similarity pairs (Argmax) or iterating that procedure (Itermax) works well. On whole documents the table becomes huge, so many plausible-but-wrong matches appear and the methods produce spurious alignments.

Their fix is to shrink the table before running the alignment algorithm. MDPAlign assumes that corresponding content sits at roughly the same relative position in both documents, so it suppresses entries far from the main diagonal — either zeroing them out entirely (strict) or down-weighting them with a Gaussian curve (fuzzy), controlled by a bandwidth k that is anchored to the longer document in absolute token count. CTFAlign makes no such fixed assumption: it starts with a 2×2 grid of average-pooled similarities, aligns the blocks, keeps only those regions (plus a buffer of width w around them), adds a recovery step for blocks whose rows and columns are otherwise empty, then halves the block size and repeats until token resolution is reached. When document lengths are skewed, the shorter side is held at token resolution while the other keeps refining.

Evaluation uses human-annotated sentence-level word alignment datasets that include document membership and sentence order, from which the authors reconstruct documents. They use development/test splits where available, split la–gr 25% into development and leave 75% as test, and treat en–cz as test-only. Hyperparameters are chosen on the development set, yielding MDPAlign fuzzy with k=150 and CTFAlign with w=8 for the test evaluation. The main metric is AER (lower is better), with F1, Precision, Recall, and macro averages in the appendix. They also compare against a 1-shot GPT-5.4-mini-2026-03-17 baseline using a "full-mode" prompt adapted from Miao et al. (2025), generated as JSON in structured output mode with temperature 0. For downstream tasks, they adapt the same structural priors to DiffAlign's dissimilarity scoring with Qwen3-Embedding-4B (layer 20).

Why This Matters

Impact on research. The paper shows that a bottleneck long assumed to require a pipeline — segment into sentences, align sentences, then align words — can instead be handled in a single encoder pass with a structural constraint on the similarity matrix. It also provides evidence that pairwise cross-lingual supervision in an encoder is associated with alignment-friendly representations, motivating further work on adapting long-context multilingual encoders specifically for word alignment.

Real-world applications:

• Hallucination and omission detection in machine translation: token-level correspondences identify content that is missing from or added to a translation, which the paper demonstrates with MQM-annotated WMT24 outputs.
• Cross-lingual document comparison: recognizing where otherwise comparable documents (e.g., government publications) differ semantically at the token level.
• Label projection: transferring annotations from one language to another via alignment links.
• Cross-lingual representation learning and MT system development, both of which consume word alignments as a component.

Industry relevance. The methods are training-free, model-agnostic post-processing steps on a similarity matrix, so they can be dropped into existing embedding-based pipelines without retraining or fine-tuning. Removing the dependence on sentence segmentation and sentence alignment also removes engineering and maintenance overhead, and matters especially for languages or domains where reliable segmentation and alignment tools are unavailable.

Future Directions

• Optimizing long-context encoders for fine-grained alignment: The authors note that when cross-lingual token similarities are insufficiently distinctive, structural constraints cannot fully compensate, and suggest that long-context multilingual encoders could be optimized to produce representations better suited to fine-grained cross-lingual alignment.
• Building genuinely document-level alignment data: Current gold data is sentence-level and had to be reconstructed into documents, so document structures remain largely monotonic and may lack reordering, insertions, or deletions, and sentence-level annotation may miss long-range reordering, cross-sentence dependencies, discourse-driven translation shifts, and multi-sentence omissions/additions.
• Addressing error propagation in recursive refinement: CTFAlign's coarse-resolution errors can propagate to later stages, particularly with Itermax; improving coarse-level robustness is an open problem.
• Fine-tuning LLMs for document-level alignment: The paper's own experiments show 1-shot prompting collapses at document scale, and notes consistency with Miao et al. (2025), who found LLM-based alignment becomes competitive only after supervised fine-tuning.

Target Audience

Researchers and practitioners in machine translation and multilingual NLP who work with word alignment, embedding-based cross-lingual similarity, or document-level cross-lingual tasks such as quality estimation, hallucination detection, and comparable-document analysis. It is also relevant to engineers who need a lightweight, training-free way to align long parallel texts without building a sentence segmentation and sentence alignment pipeline, and to researchers interested in how encoder pretraining objectives relate to alignment quality.

Authors’ abstract

Word alignment has traditionally been studied between sentences, but many cross-lingual tasks increasingly require correspondences across full documents. While recent multilingual embedding models can encode long inputs, we show that applying algorithms designed for sentences directly to documents leads to performance degradation. To address this, we introduce CTFAlign, a lightweight, training-free approach for document-level word alignment. CTFAlign applies a coarse-to-fine refinement strategy that restricts the alignment search space to semantically similar regions. Additionally, we introduce MDPAlign, a simpler alternative that constrains alignments by position with a main diagonal prior. Both approaches operate directly on full documents without relying on sentence segmentation or sentence alignment. We evaluate these methods across six language pairs varying in typological distance, resourcedness, and document length. Averaged over three models, CTFAlign reduces word alignment error rate from 0.412 to 0.326. These gains transfer downstream, leading to improvements in document-level translation coverage evaluation and recognition of semantic differences. We release CTFAlign as a Python package and make the code and data to reproduce our experiments publicly available.