---
title: "Vecalign: Improved Sentence Alignment in — Thompson 2019"
description: "Sentence alignment pairs up minimal groups of sentences in parallel documents that translate each other."
authors: ["Brian Thompson", "Philipp Koehn"]
year: 2019
venue: "Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)"
source: "https://aclanthology.org/D19-1136/"
doi: "10.18653/v1/d19-1136"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/thompson-2019-vecalign-improved-sentence-alignment-linear/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/thompson-2019-vecalign-improved-sentence-alignment-linear/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2019](https://md.research.elamur.ai/free/en/papers/2019/page/5/) / Vecalign: Improved Sentence Alignment in Linear Time and Space

# Vecalign: Improved Sentence Alignment in Linear Time and Space

**Authors:** [Brian Thompson](https://md.research.elamur.ai/free/en/authors/brian-thompson/), [Philipp Koehn](https://md.research.elamur.ai/free/en/authors/philipp-koehn/) · **Year:** 2019 · **Venue:** Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/D19-1136/) · [PDF](https://aclanthology.org/D19-1136.pdf) · [DOI 10.18653/v1/d19-1136](https://doi.org/10.18653/v1/d19-1136) · [OpenAlex](https://openalex.org/W2986148666)

**Citations:** 64 citations (openalex-snapshot · 2026-10-14) · [80](#cited-by) in our library, of the 140884 papers whose bibliographies we read

## Summary
Sentence alignment pairs up minimal groups of sentences in parallel documents that translate each other. Older aligners are slow on long documents because their search grows quadratically, and stronger systems such as Bleualign rely on an MT system. Thompson and Koehn present Vecalign, an aligner that needs only multilingual sentence embeddings (LASER). Its scoring function is cosine distance, normalized against randomly sampled sentence pairs to counter hubness and weighted by the number of sentences involved, so that small one-to-one units are preferred over large many-to-many blocks. Because a group of sentences can be represented by averaging their vectors, the authors adapt a recursive coarse-to-fine dynamic programming scheme from dynamic time warping (Salvador and Chan, 2007). This makes time and memory linear in document length. Vecalign beats prior methods on a German–French benchmark and clearly outperforms Hunalign on low-resource Bible alignment. It also produces better NMT training data from web-crawled text. This matters for building bitext in low-resource languages, which applies directly to Ukrainian-related pairs.

## Key points
- On the Text+Berg De–Fr test set (from Bleualign), Vecalign reaches F1 0.90, compared with 0.85 for Coverage-Based and 0.84 for Bleualign using NMT output.
- On Bible verse alignment across 10 pairs drawn from Arabic, Turkish, Somali, Afrikaans, Tagalog and Norwegian, verse-level F1 is on average 28 points higher than Hunalign. This holds even for Norwegian, which LASER was not trained on.
- Re-aligning Paracrawl data improves NMT on FLoRes test sets by 1.7 BLEU for Sinhala→English and 1.6 BLEU for Nepali→English, relative to the Hunalign-based pipeline.
- Vecalign aligns 32k sentences in about 30 s using about 1 GB of memory, with window size w = 10. Bleualign and Gargantua ran out of memory at that size.
- The skip (insertion/deletion) cost is defined as a quantile of the 1–1 cost distribution, so it transfers across language pairs. The code is released at github.com/thompsonb/vecalign.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

Topics: [Machine translation](https://md.research.elamur.ai/free/en/topics/machine-translation/)

## Cited by

Cited by

80 papers of our library cite it (of the 140884 whose bibliographies we read); 5 of them have a page here, 75 not yet.

- [ParaCrawl: Web-Scale Acquisition of Parallel Corpora](https://md.research.elamur.ai/free/en/papers/banon-2020-paracrawl-web-scale-acquisition-parallel/)
- [Neural CRF Model for Sentence Alignment in Text Simplification](https://md.research.elamur.ai/free/en/papers/jiang-2020-neural-crf-model-sentence-alignment/)
- [Ancient Greek to Modern Greek Machine Translation: A Novel Benchmark and Fine-Tuning Experiments on LLMs and NMT Models](https://md.research.elamur.ai/free/en/papers/mavromatis-2026-ancient-greek-modern-greek-machine/)
- [Samanantar: The Largest Publicly Available Parallel Corpora Collection for 11 Indic Languages](https://md.research.elamur.ai/free/en/papers/ramesh-2022-samanantar-largest-publicly-available-parallel/)
- [Culture-Aware Machine Translation in Large Language Models: Benchmarking and Investigation](https://md.research.elamur.ai/free/en/papers/yuan-2026-culture-aware-machine-translation-large/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{thompson2019vecalign,
  title = {{Vecalign: Improved Sentence Alignment in Linear Time and Space}},
  author = {Thompson, Brian and Koehn, Philipp},
  booktitle = {Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)},
  year = {2019},
  doi = {10.18653/v1/d19-1136},
  url = {https://doi.org/10.18653/v1/d19-1136}
}
```

- [← previous Utilizing BERT for Aspect-Based Sentiment Analysis via Constructing Auxiliary Sentence](https://md.research.elamur.ai/free/en/papers/sun-2019-utilizing-bert-aspect-based-sentiment/)
- [next → VerbAtlas: a Novel Large-Scale Verbal Semantic Resource and Its Application to Semantic Role Labeling](https://md.research.elamur.ai/free/en/papers/fabio-2019-verbatlas-novel-large-scale-verbal/)
- [↑ back to papers of 2019](https://md.research.elamur.ai/free/en/papers/2019/page/5/)

## References

27 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Sadaf Abdul-Rauf, Mark Fishel, Patrik Lambert, Sandra Noubours, and Rico Sennrich. 2012. Extrinsic evaluation of sentence alignment systems. Workshop on Creating Cross-language Resources for Disconnected Languages and Styles, pages 6–10. [find](https://scholar.google.com/scholar?q=Sadaf+Abdul%2DRauf%2C+Mark+Fishel%2C+Patrik+Lambert%2C+Sandra+Noubours%2C+and+Rico+Sennrich%2E+2012%2E+Extrinsic+evaluation+of+sentence+alignment+systems%2E+Workshop+on+Creating+Cross%2Dlanguage+Resources+for+Disconnec)
2. Mikel Artetxe and Holger Schwenk. 2018. Massively multilingual sentence embeddings for zero-shot cross-lingual transfer and beyond. arXiv preprint arXiv:1812.10464. [find](https://scholar.google.com/scholar?q=Mikel+Artetxe+and+Holger+Schwenk%2E+2018%2E+Massively+multilingual+sentence+embeddings+for+zero%2Dshot+cross%2Dlingual+transfer+and+beyond%2E+arXiv+preprint+arXiv%3A1812%2E10464%2E) [our card](https://md.research.elamur.ai/free/en/papers/artetxe-2018-massively-multilingual-sentence-embeddings-zero/)
3. Mikel Artetxe and Holger Schwenk. 2019. Margin-based parallel corpus mining with multilingual sentence embeddings. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3197–3203, Florence, Italy. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Mikel+Artetxe+and+Holger+Schwenk%2E+2019%2E+Margin%2Dbased+parallel+corpus+mining+with+multilingual+sentence+embeddings%2E+In+Proceedings+of+the+57th+Annual+Meeting+of+the+Association+for+Computational+Lingui) [our card](https://md.research.elamur.ai/free/en/papers/artetxe-2019-margin-based-parallel-corpus-mining/)
4. Richard Bellman. 1953. An introduction to the theory of dynamic programming. Technical report, RAND Corporation, Santa Monica, CA. [find](https://scholar.google.com/scholar?q=Richard+Bellman%2E+1953%2E+An+introduction+to+the+theory+of+dynamic+programming%2E+Technical+report%2C+RAND+Corporation%2C+Santa+Monica%2C+CA%2E)
5. Fabienne Braune and Alexander Fraser. 2010. Improved unsupervised sentence alignment for symmetrical and asymmetrical parallel corpora. In Coling 2010: Posters, pages 81–89, Beijing, China. [find](https://scholar.google.com/scholar?q=Fabienne+Braune+and+Alexander+Fraser%2E+2010%2E+Improved+unsupervised+sentence+alignment+for+symmetrical+and+asymmetrical+parallel+corpora%2E+In+Coling+2010%3A+Posters%2C+pages+81%E2%80%9389%2C+Beijing%2C+China%2E)
6. Coling 2010 Organizing Committee. [find](https://scholar.google.com/scholar?q=Coling+2010+Organizing+Committee%2E)
7. Peter F. Brown, Jennifer C. Lai, and Robert L. Mercer. 1991. Aligning sentences in parallel corpora. In Proceedings of the 29th Annual Meeting on Association for Computational Linguistics, ACL ’91, pages 169–176, Stroudsburg, PA, USA. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Peter+F%2E+Brown%2C+Jennifer+C%2E+Lai%2C+and+Robert+L%2E+Mercer%2E+1991%2E+Aligning+sentences+in+parallel+corpora%2E+In+Proceedings+of+the+29th+Annual+Meeting+on+Association+for+Computational+Linguistics%2C+ACL+%E2%80%9991%2C+pa) [our card](https://md.research.elamur.ai/free/en/papers/brown-1991-aligning-sentences-parallel-corpora/)
8. Christian Buck and Philipp Koehn. 2016. Findings of the WMT 2016 bilingual document alignment shared task. In Proceedings of the First Conference on Machine Translation: Volume 2, Shared Task Papers, pages 554–563, Berlin, Germany. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Christian+Buck+and+Philipp+Koehn%2E+2016%2E+Findings+of+the+WMT+2016+bilingual+document+alignment+shared+task%2E+In+Proceedings+of+the+First+Conference+on+Machine+Translation%3A+Volume+2%2C+Shared+Task+Papers%2C+)
9. Vishrav Chaudhary, Yuqing Tang, Francisco Guzmn, Holger Schwenk, and Philipp Koehn. 2019. Low-resource corpus filtering using multilingual sentence embeddings. In Proceedings of the Fourth Conference on Machine Translation (Volume 3: Shared Task Papers, Day 2), pages 263–268, Florence, Italy. Associ… [find](https://scholar.google.com/scholar?q=Vishrav+Chaudhary%2C+Yuqing+Tang%2C+Francisco+Guzmn%2C+Holger+Schwenk%2C+and+Philipp+Koehn%2E+2019%2E+Low%2Dresource+corpus+filtering+using+multilingual+sentence+embeddings%2E+In+Proceedings+of+the+Fourth+Conference+) [our card](https://md.research.elamur.ai/free/en/papers/chaudhary-2019-low-resource-corpus-filtering-multilingual/)
10. Christos Christodouloupoulos and Mark Steedman. 2015. A massively parallel corpus: the Bible in 100 languages. Language resources and evaluation, 49(2):375–395. [find](https://scholar.google.com/scholar?q=Christos+Christodouloupoulos+and+Mark+Steedman%2E+2015%2E+A+massively+parallel+corpus%3A+the+Bible+in+100+languages%2E+Language+resources+and+evaluation%2C+49%282%29%3A375%E2%80%93395%2E) [our card](https://md.research.elamur.ai/free/en/papers/christodouloupoulos-2014-massively-parallel-corpus-bible-100/)
11. William A Gale and Kenneth W Church. 1993. A program for aligning sentences in bilingual corpora. Computational linguistics, 19(1):75–102. [find](https://scholar.google.com/scholar?q=William+A+Gale+and+Kenneth+W+Church%2E+1993%2E+A+program+for+aligning+sentences+in+bilingual+corpora%2E+Computational+linguistics%2C+19%281%29%3A75%E2%80%93102%2E) [our card](https://md.research.elamur.ai/free/en/papers/gale-1993-program-aligning-sentences-bilingual-corpora/)
12. Luı́s Gomes and Gabriel Pereira Lopes. 2016. First steps towards coverage-based sentence alignment. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016), pages 2228–2231, Portorož, Slovenia. European Language Resources Association (ELRA). [find](https://scholar.google.com/scholar?q=Lu%C4%B1%CC%81s+Gomes+and+Gabriel+Pereira+Lopes%2E+2016%2E+First+steps+towards+coverage%2Dbased+sentence+alignment%2E+In+Proceedings+of+the+Tenth+International+Conference+on+Language+Resources+and+Evaluation+%28LREC+2016)
13. Cyril Goutte, Marine Carpuat, and George Foster. 2012. The impact of sentence alignment errors on phrase-based machine translation performance. In The Tenth Biennial Conference of the Association for Machine Translation in the Americas (AMTA 2012). [find](https://scholar.google.com/scholar?q=Cyril+Goutte%2C+Marine+Carpuat%2C+and+George+Foster%2E+2012%2E+The+impact+of+sentence+alignment+errors+on+phrase%2Dbased+machine+translation+performance%2E+In+The+Tenth+Biennial+Conference+of+the+Association+for+)
14. Mandy Guo, Qinlan Shen, Yinfei Yang, Heming Ge, Daniel Cer, Gustavo Hernandez Abrego, Keith Stevens, Noah Constant, Yun-Hsuan Sung, Brian Strope, and Ray Kurzweil. 2018. Effective parallel corpus mining using bilingual sentence embeddings. In Proceedings of the Third Conference on Machine Translatio… [find](https://scholar.google.com/scholar?q=Mandy+Guo%2C+Qinlan+Shen%2C+Yinfei+Yang%2C+Heming+Ge%2C+Daniel+Cer%2C+Gustavo+Hernandez+Abrego%2C+Keith+Stevens%2C+Noah+Constant%2C+Yun%2DHsuan+Sung%2C+Brian+Strope%2C+and+Ray+Kurzweil%2E+2018%2E+Effective+parallel+corpus+mini) [our card](https://md.research.elamur.ai/free/en/papers/guo-2018-effective-parallel-corpus-mining-bilingual/)
15. Hany Hassan, Anthony Aue, Chang Chen, Vishal Chowdhary, Jonathan Clark, Christian Federmann, Xuedong Huang, Marcin Junczys-Dowmunt, William Lewis, Mu Li, et al. 2018. Achieving human parity on automatic Chinese to English news translation. arXiv preprint arXiv:1803.05567. [find](https://scholar.google.com/scholar?q=Hany+Hassan%2C+Anthony+Aue%2C+Chang+Chen%2C+Vishal+Chowdhary%2C+Jonathan+Clark%2C+Christian+Federmann%2C+Xuedong+Huang%2C+Marcin+Junczys%2DDowmunt%2C+William+Lewis%2C+Mu+Li%2C+et+al%2E+2018%2E+Achieving+human+parity+on+automat) [our card](https://md.research.elamur.ai/free/en/papers/hassan-2018-achieving-human-parity-automatic-chinese/)
16. Huda Khayrallah and Philipp Koehn. 2018. On the impact of various types of noise on neural machine translation. In Proceedings of the 2nd Workshop on Neural Machine Translation and Generation, pages 74–83, Melbourne, Australia. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Huda+Khayrallah+and+Philipp+Koehn%2E+2018%2E+On+the+impact+of+various+types+of+noise+on+neural+machine+translation%2E+In+Proceedings+of+the+2nd+Workshop+on+Neural+Machine+Translation+and+Generation%2C+pages+7) [our card](https://md.research.elamur.ai/free/en/papers/khayrallah-2018-impact-various-types-noise-neural/)
17. Philipp Koehn. 2005. Europarl: A parallel corpus for statistical machine translation. In Machine Translation summit, volume 5, pages 79–86. [find](https://scholar.google.com/scholar?q=Philipp+Koehn%2E+2005%2E+Europarl%3A+A+parallel+corpus+for+statistical+machine+translation%2E+In+Machine+Translation+summit%2C+volume+5%2C+pages+79%E2%80%9386%2E)
18. Philipp Koehn, Francisco Guzmn, Vishrav Chaudhary, and Juan Pino. 2019. Findings of the WMT 2019 shared task on parallel corpus filtering for low-resource conditions. In Proceedings of the Fourth Conference on Machine Translation (Volume 3: Shared Task Papers, Day 2), pages 56–74, Florence, Italy. A… [find](https://scholar.google.com/scholar?q=Philipp+Koehn%2C+Francisco+Guzmn%2C+Vishrav+Chaudhary%2C+and+Juan+Pino%2E+2019%2E+Findings+of+the+WMT+2019+shared+task+on+parallel+corpus+filtering+for+low%2Dresource+conditions%2E+In+Proceedings+of+the+Fourth+Conf) [our card](https://md.research.elamur.ai/free/en/papers/koehn-2019-findings-wmt-2019-shared-task/)
19. Angeliki Lazaridou, Georgiana Dinu, and Marco Baroni. 2015. Hubness and pollution: Delving into cross-space mapping for zero-shot learning. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Proces… [find](https://scholar.google.com/scholar?q=Angeliki+Lazaridou%2C+Georgiana+Dinu%2C+and+Marco+Baroni%2E+2015%2E+Hubness+and+pollution%3A+Delving+into+cross%2Dspace+mapping+for+zero%2Dshot+learning%2E+In+Proceedings+of+the+53rd+Annual+Meeting+of+the+Association)
20. Robert C Moore. 2002. Fast and accurate sentence alignment of bilingual corpora. In Conference of the Association for Machine Translation in the Americas, pages 135–144. Springer. [find](https://scholar.google.com/scholar?q=Robert+C+Moore%2E+2002%2E+Fast+and+accurate+sentence+alignment+of+bilingual+corpora%2E+In+Conference+of+the+Association+for+Machine+Translation+in+the+Americas%2C+pages+135%E2%80%93144%2E+Springer%2E)
21. Miloš Radovanović, Alexandros Nanopoulos, and Mirjana Ivanović. 2010. Hubs in space: Popular nearest neighbors in high-dimensional data. Journal of Machine Learning Research, 11(Sep):2487–2531. [find](https://scholar.google.com/scholar?q=Milos%CC%8C+Radovanovic%CC%81%2C+Alexandros+Nanopoulos%2C+and+Mirjana+Ivanovic%CC%81%2E+2010%2E+Hubs+in+space%3A+Popular+nearest+neighbors+in+high%2Ddimensional+data%2E+Journal+of+Machine+Learning+Research%2C+11%28Sep%29%3A2487%E2%80%932531%2E)
22. Stan Salvador and Philip Chan. 2007. Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis, 11(5):561–580. [find](https://scholar.google.com/scholar?q=Stan+Salvador+and+Philip+Chan%2E+2007%2E+Toward+accurate+dynamic+time+warping+in+linear+time+and+space%2E+Intelligent+Data+Analysis%2C+11%285%29%3A561%E2%80%93580%2E)
23. Rico Sennrich and Martin Volk. 2010. MT-based sentence alignment for OCR-generated parallel texts. In The Ninth Conference of the Association for Machine Translation in the Americas (AMTA 2010). [find](https://scholar.google.com/scholar?q=Rico+Sennrich+and+Martin+Volk%2E+2010%2E+MT%2Dbased+sentence+alignment+for+OCR%2Dgenerated+parallel+texts%2E+In+The+Ninth+Conference+of+the+Association+for+Machine+Translation+in+the+Americas+%28AMTA+2010%29%2E)
24. Jörg Tiedemann. 2012. Parallel data, tools and interfaces in OPUS. In Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC-2012), pages 2214–2218, Istanbul, Turkey. European Languages Resources Association (ELRA). [find](https://scholar.google.com/scholar?q=Jo%CC%88rg+Tiedemann%2E+2012%2E+Parallel+data%2C+tools+and+interfaces+in+OPUS%2E+In+Proceedings+of+the+Eighth+International+Conference+on+Language+Resources+and+Evaluation+%28LREC%2D2012%29%2C+pages+2214%E2%80%932218%2C+Istanbul%2C+T)
25. Dániel Varga, Péter Halácsy, András Kornai, Viktor Nagy, László Németh, and Viktor Trón. 2007. Parallel corpora for medium density languages. Amsterdam Studies In The Theory And History Of Linguistic Science Series 4, 292:247. [find](https://scholar.google.com/scholar?q=Da%CC%81niel+Varga%2C+Pe%CC%81ter+Hala%CC%81csy%2C+Andra%CC%81s+Kornai%2C+Viktor+Nagy%2C+La%CC%81szlo%CC%81+Ne%CC%81meth%2C+and+Viktor+Tro%CC%81n%2E+2007%2E+Parallel+corpora+for+medium+density+languages%2E+Amsterdam+Studies+In+The+Theory+And+History+Of+Lin)
26. Martin Volk, Noah Bubenhofer, Adrian Althaus, Maya Bangerter, Lenz Furrer, and Beni Ruef. 2010. Challenges in building a multilingual alpine heritage corpus. In Proceedings of the Seventh conference on International Language Resources and Evaluation (LREC’10), Valletta, Malta. European Languages Res… [find](https://scholar.google.com/scholar?q=Martin+Volk%2C+Noah+Bubenhofer%2C+Adrian+Althaus%2C+Maya+Bangerter%2C+Lenz+Furrer%2C+and+Beni+Ruef%2E+2010%2E+Challenges+in+building+a+multilingual+alpine+heritage+corpus%2E+In+Proceedings+of+the+Seventh+conference+o)
27. Pierre Zweigenbaum, Serge Sharoff, and Reinhard Rapp. 2018. Overview of the third BUCC shared task: Spotting parallel sentences in comparable corpora. In Proceedings of 11th Workshop on Building and Using Comparable Corpora, pages 39–42. [find](https://scholar.google.com/scholar?q=Pierre+Zweigenbaum%2C+Serge+Sharoff%2C+and+Reinhard+Rapp%2E+2018%2E+Overview+of+the+third+BUCC+shared+task%3A+Spotting+parallel+sentences+in+comparable+corpora%2E+In+Proceedings+of+11th+Workshop+on+Building+and+U)