ChainAlign: Cross-lingual sentence alignment via sparse co-linear chaining

Cross-lingual sentence alignment establishes correspondence between a document and its translation, where correspondence is not always complete, one-to-one, or monotonic. Current embedding-based aligners score sentence pairs with a multilingual encoder, then trace a single monotonic path across the full alignment grid. This forced path cascades errors through non-parallel or reordered content. We present ChainAlign, which instead adapts seed-chain-extend from computational genomics: it seeds multi-resolution candidate anchors from multilingual embeddings, selects the maximum-weight non-crossing subset by co-linear chaining in O(NlogN) via a Fenwick tree, and fills the residual gaps with local dynamic time warping. Because the chain imposes no coverage requirement, non-parallel content becomes unaligned gaps rather than cascading errors, and multi-chain extraction handles reordering that a monotonic path cannot represent. On three benchmarks across four language pairs, ChainAlign achieves the highest strict and lax F1, ahead of Bertalign, SentAlign, and Vecalign. Evaluation shows the sparse formulation outperforms exhaustive dynamic programming using the same edge weight function.