Skip to content

Scaling Unsupervised Word Alignment to Documents via Structural Constraints

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/ZurichNLP/CTFAlign
Area: Multilingual & Translation
Keywords: Word Alignment, Document-level Word Alignment, Coarse-to-Fine Alignment, Structural Constraints, Unsupervised Representations

TL;DR

Addressing the severe performance degradation caused by noise explosion and spurious matches when scaling unsupervised word alignment to full documents, this paper proposes training-free, segmentation-free structural constraint methods (CTFAlign and MDPAlign) that reduce document-level alignment error rate (AER) from 0.412 to 0.326 across six language pairs and significantly enhance downstream translation coverage evaluation and semantic difference recognition.

Background & Motivation

Word alignment is a foundational task in natural language processing that identifies semantic correspondences between words in parallel texts. It serves as an essential backbone for machine translation hallucination detection, cross-lingual annotation projection, translation quality assessment, and representation learning. With the recent advent of long-context multilingual embedding models such as Qwen3-Embedding and mmBERT, downstream cross-lingual tasks have increasingly transitioned from isolated sentences to full documents. However, existing word alignment techniques remain predominantly confined to sentence pairs. While embedding-based frameworks such as SimAlign can technically process entire document sequences in a single forward pass and compute full document token similarity matrices, directly applying sentence-level algorithms to documents causes dramatic performance degradation.

The core tension stems from the quadratic expansion of the alignment search space and the absence of local structural constraints. In document pairs spanning thousands of tokens, similarity matrices become exceptionally large and noisy. Repetitive entities, high-frequency function words, and punctuation across the document induce numerous spurious yet locally high-scoring similarity pairs, causing greedy alignment algorithms to fail. The standard engineering workaround decomposes the document through a cascaded pipeline of "sentence segmentation \(\to\) sentence alignment \(\to\) sentence-level word alignment". Nevertheless, this pipeline is brittle in low-resource languages or domains lacking robust segmentation tools; segmentation and sentence alignment errors cascade irreversibly into word alignment while discarding document-wide context and introducing substantial engineering overhead.

To eliminate rigid dependencies on sentence segmentation and alignment while fully utilizing document-level contextual representations, this paper investigates structural priors applied directly to the document similarity matrix. Core idea: without sentence segmentation or additional supervision, restrict the document-level word alignment search space via structural constraintsโ€”either by penalizing off-diagonal candidates using a global position prior (MDPAlign) or by adaptively focusing on promising regions via a recursive coarse-to-fine refinement strategy (CTFAlign)โ€”to achieve robust, high-accuracy document-level alignment in a single encoder pass.

Method

Overall Architecture

Given a source document \(x = (x_1, \dots, x_m)\) and a target document \(y = (y_1, \dots, y_n)\), a long-context multilingual encoder processes both texts in a single forward pass to produce contextualized token embeddings. The cosine similarity matrix \(S \in \mathbb{R}^{m \times n}\) is computed (with negative similarities truncated to zero). Rather than applying bipartite matching algorithms directly to the noisy matrix \(S\), the framework applies lightweight, model-agnostic structural constraints to yield a modified matrix \(\tilde{S}\). Finally, standard matching algorithms (such as Argmax or Itermax) extract token-level alignment links, which are mapped back to parent words to produce the word alignment set \(A \subseteq \{1, \dots, m\} \times \{1, \dots, n\}\).

Two complementary structural constraint mechanisms are introduced: MDPAlign, which assumes monotonic progression along the main diagonal, and CTFAlign, which dynamically identifies arbitrary non-monotonic alignment manifolds across multiple resolutions.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Bilingual Document Input<br/>Single Forward Pass Token Embeddings"] --> B["Compute Document-level Similarity Matrix S"]
    B --> C["Main Diagonal Prior (MDPAlign)<br/>Strict Truncation or Gaussian Decay"]
    B --> D["Coarse-to-Fine Grid Refinement (CTFAlign)<br/>2ร—2 Initial Average Pooling"]
    D --> E["Bidirectional Block Alignment & Buffer Expansion<br/>Retain Aligned Blocks with w-Width Neighborhood"]
    E --> F["Empty Row/Column Recovery Mechanism<br/>Prevent Coarse-level Error Cascading"]
    F --> G{"Reached Token Resolution?"}
    G -- "No: Halve Block Dimensions" --> D
    G -- "Yes" --> H["Constrained Bipartite Matching<br/>Argmax / Itermax Word Alignment"]
    C --> H

Key Designs

1. Main Diagonal Prior (MDPAlign): Suppressing spurious long-range matches via relative positional constraints

In standard translation corpora, parallel texts generally advance in a shared linear narrative order, meaning corresponding segments appear at approximately identical relative positions within their respective documents. Mapping source token \(i\) to \(i/m\) and target token \(j\) to \(j/n\), MDPAlign measures the relative distance of cell \((i, j)\) from the main diagonal: $\(d_{ij} = \left| \frac{i}{m} - \frac{j}{n} \right|\)$ To ensure that the allowable absolute token displacement does not loosen unrealistically for longer documents, the bandwidth hyperparameter \(k\) is anchored to the length of the longer document. MDPAlign provides two masking variants: - Strict: Truncates all entries outside the diagonal band to zero if \(d_{ij} > \frac{k}{\max(m, n)}\), while retaining original values within the band. - Fuzzy: Strict cutoff can abruptly sever local reorderings near the boundary. The fuzzy variant introduces an exponential Gaussian decay that smoothly discounts off-diagonal similarity scores: $\(\tilde{S}_{ij} = S_{ij} \cdot \exp\left( -\frac{d_{ij}^2}{2\sigma^2} \right), \quad \sigma = \frac{k}{\max(m, n)}\)$ This smooth suppression neutralizes spurious distant matches while tolerating local structural shifts.

2. Coarse-to-Fine Grid Refinement (CTFAlign): Adaptively tracking non-monotonic and displaced alignment paths

While a diagonal prior is effective for rigid sentence-by-sentence translations, authentic documents often feature structural reorganization, non-linear discourse shifts, and asymmetric insertions/deletions. In these situations, the true alignment manifold curves away from the diagonal, causing MDPAlign to penalize valid correspondences. CTFAlign resolves this through adaptive multi-scale refinement. The matrix \(S\) is initially partitioned into a \(2 \times 2\) grid. Cell similarities are average-pooled (with negative values counting as zero), and base alignment (e.g., SimAlign) is executed on this coarse matrix. Every aligned coarse block flags a region likely containing genuine token alignments; all unaligned regions are masked to zero. At each subsequent resolution level \(t\), block heights and widths are halved, doubling resolution. If document lengths are asymmetric and one side reaches single-token granularity first, that dimension remains frozen while the other continues refinement, terminating when both dimensions reach token resolution.

3. Neighborhood Buffer Expansion and Empty Row/Column Recovery: Preventing coarse-resolution error propagation

A primary challenge with hierarchical search-space pruning is false-negative error cascading: if a true correspondence is missed at a coarse resolution due to pooling dilution, it becomes permanently masked. CTFAlign integrates two robust safeguards: - Neighborhood Buffer (\(w\)): Whenever a coarse block \((i, j)\) is aligned, a buffer of \(w\) adjacent blocks in all directions is retained (\([i-w, i+w] \times [j-w, j+w]\)), accommodating boundary crossings and slight shifts. - Empty Row/Column Recovery: Following mask generation at any level, the algorithm detects whether any source row or target column has zero retained blocks. Any cell located at the intersection of a completely empty row and empty column is forcibly recovered along with its \(w\)-width buffer. This ensures that no paragraph or sentence is eliminated due to initial pooling artifacts.

Key Experimental Results

Main Results

Experiments are conducted on reconstructed document-level benchmarks spanning six language pairs (enโ€“fr, enโ€“ro, enโ€“ja, enโ€“zh, laโ€“gr, enโ€“cz). Comparisons include unconstrained document-level SimAlign, sentence-level SimAlign (approximate upper bound), 1-shot LLM prompting (GPT-5.4-mini), and the proposed structural constraints.

The table below reports alignment error rate (AER, lower is better) and macro averages on the test set using Qwen3-Embedding-4B:

Language Pair / Granularity Sentence (Upper Bound) Doc SimAlign (Baseline) Doc MDPAlign (fuzzy) Doc CTFAlign (Ours) GPT-5.4-mini (1-shot)
enโ€“fr 0.117 0.252 0.232 0.151 0.995
enโ€“ro 0.366 0.366 0.342 0.339 0.968
enโ€“ja 0.542 0.602 0.752 0.535 0.986
enโ€“zh 0.253 0.282 0.254 0.255 0.935
laโ€“gr 0.297 0.443 0.397 0.293 0.996
enโ€“cz 0.197 0.208 0.221 0.191 0.982
Average AER 0.295 0.359 0.366 0.294 0.977
Average F1 0.704 0.639 0.632 0.705 0.023

Note: Base matching utilizes Argmax; hyperparameters are set to \(k=150\) for MDPAlign and \(w=8\) for CTFAlign.

Ablation Study

Ablations on the development set across three embedding models (Qwen3-Embedding-4B, mmBERT-base, LaBSE) examine constraint formulations, bandwidth parameters, and matching algorithms:

Constraint Method Hyperparameter (\(k\) or \(w\)) Decoding Operator Avg F1 Avg AER Note
CTFAlign \(w = 8\) (Default) Argmax 0.677 0.321 Best performing adaptive configuration overall
CTFAlign \(w = 4\) Argmax 0.666 0.331 Smaller buffer clips off-center correspondences
CTFAlign \(w = 0\) Argmax 0.140 0.858 Severe coarse-to-fine error cascading without buffer
MDPAlign (fuzzy) \(k = 150\) (Default) Argmax 0.669 0.330 Gaussian decay reaches optimal performance plateau
MDPAlign (fuzzy) \(k = 50\) Argmax 0.633 0.365 Band too narrow; penalizes valid off-diagonal links
MDPAlign (strict) \(k = 50\) Argmax 0.655 0.343 Best strict setting, but less flexible than Gaussian decay
CTFAlign \(w = 8\) Itermax 0.723* 0.278* Strong recall on LaBSE, but prone to noise on mmBERT
Unconstrained Doc - Argmax 0.589 0.408 Unconstrained baseline degraded by long-range noise

Note: Data averaged across development sets of all three models from Tables 8 and 9.

Key Findings

  • Failure of diagonal priors on curved alignment paths: In enโ€“ja Wikipedia documents exhibiting extensive structural displacement and non-linear narrative ordering, gold alignments diverge markedly from the main diagonal. MDPAlign penalizes these valid correspondences, deteriorating AER to 0.752 (substantially worse than the unconstrained 0.602 baseline). In contrast, CTFAlign's adaptive search space readily tracks the bend, achieving 0.535 AER and outperforming the sentence-level upper bound (0.542).
  • Collapse of 1-shot LLM prompting on documents: While GPT-5.4-mini achieves a competitive 0.362 AER on sentence pairs, its performance collapses to near-total failure (0.977 AER, 0.023 F1) when applied to full documents. The model severely suffers from hallucination and omissions over long context sequences, confirming that continuous representation matrices remain far superior to un-finetuned LLM generation for dense token alignment.
  • Interaction with encoder training objectives: Encoders pre-trained with pairwise cross-lingual supervision (LaBSE and contrastively trained Qwen) benefit most from CTFAlign (LaBSE achieves the lowest test AER of 0.068 on enโ€“fr). Conversely, mmBERT, trained purely via masked language modeling without parallel supervision, produces less distinctive cross-lingual representations. On mmBERT, CTFAlign can amplify early coarse-level misalignments, whereas MDPAlign's static diagonal band acts as a safer regularizer.

Highlights & Insights

  • Training-free and segmentation-free simplicity: Operates directly on long-context token similarity matrices via spatial pooling or Gaussian masking, eliminating the engineering overhead, latency, and error cascading inherent in sentence segmentation and alignment pipelines.
  • Seamless transfer to downstream discriminative tasks: When integrated into DiffAlign, CTFAlign improves document-level ROC AUC by up to +0.055 on WMT24 translation coverage evaluation (detecting omissions and additions) and establishes new state-of-the-art Spearman correlation on SwissGov-RSD for token-level semantic difference recognition.
  • Generalized hierarchical search without monotonicity assumptions: Unlike VecAlign's strict reliance on monotonic dynamic programming for sentence alignment, CTFAlign operates on token grids and naturally accommodates arbitrary non-monotonic, non-contiguous alignment topologies.

Limitations & Future Work

  • Dependency on initial encoder representations: Because CTFAlign prunes search regions hierarchically, severe cross-lingual representational collapse in weaker base encoders can cause misaligned coarse blocks that propagate irreversibly into later stages.
  • Reconstructed nature of evaluation datasets: Due to the scarcity of native document-level word alignment annotations, test benchmarks are reconstructed from sentence-level gold labels. Although this setup accurately captures document-wide lexical repetition noise, it does not fully encompass extreme macro-discourse reordering.
  • Future directions: Exploring parameter-efficient contrastive fine-tuning on long-context encoders specifically for alignment, and extending the coarse-to-fine matrix constraint framework to cross-modal alignment (e.g., audio/video temporal grounding to text).
  • vs SimAlign (Jalili Sabet et al., 2020): SimAlign demonstrated high-quality unsupervised word alignment on sentences, but collapses on full documents due to unbounded search space noise; this work preserves SimAlign's lightweight unsupervised nature while scaling it to document contexts via MDP and CTF constraints.
  • vs VecAlign (Thompson and Koehn, 2019): VecAlign employs coarse-to-fine search for sentence alignment under monotonic dynamic programming assumptions; CTFAlign operates directly at the token level without requiring monotonic or contiguous alignment paths.
  • vs LLM-based Word Alignment (Miao et al., 2025): Autoregressively predicting word alignment indices via LLM prompting fails to scale to documents; embedding-based matrix constraints offer vastly superior precision, recall, and computational efficiency.

Rating

  • Novelty: โญโญโญโญโ˜† Pioneers the investigation of document-level unsupervised word alignment and designs an elegant, training-free coarse-to-fine constraint strategy.
  • Experimental Thoroughness: โญโญโญโญโญ Rigorously evaluated across six language pairs, three encoders, two downstream document tasks, hyperparameter ablations, and qualitative failure analyses.
  • Writing Quality: โญโญโญโญโญ Lucid narrative flow, clear mathematical formulation, and illuminating visualizations of geometric alignment manifolds.
  • Value: โญโญโญโญโญ Releases the open-source Python library CTFAlign, providing an essential, practical tool for long-document cross-lingual NLP pipelines.