# Towards Example-Based NMT with Multi-Levenshtein Transformers

Maxime Bouthors, Josep Crego, François Yvon

► To cite this version:

Maxime Bouthors, Josep Crego, François Yvon. Towards Example-Based NMT with Multi-Levenshtein Transformers. Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, Dec 2023, Singapour, Singapore. pp.1830-1846. hal-04332427

HAL Id: hal-04332427

https://hal.science/hal-04332427v1

Submitted on 8 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Towards Example-Based NMT with Multi-Levenshtein Transformers

Maxime Bouthors ♡, ♣, Josep Crego ♣, and François Yvon ♡

♡ Sorbonne Université, CNRS, ISIR, F-75005 Paris, France
firstname.lastname@isir.upmc.fr

♣Systran, 5 rue Feydeau, F-75002 Paris, France
firstname.lastname@systrangroup.fr

## Abstract

Retrieval-Augmented Machine Translation (RAMT) is attracting growing attention. This is because RAMT not only improves translation metrics, but is also assumed to implement some form of domain adaptation. In this contribution, we study another salient trait of RAMT, its ability to make translation decisions more transparent by allowing users to go back to examples that contributed to these decisions. For this, we propose a novel architecture aiming to increase this transparency. This model adapts a retrieval-augmented version of the Levenshtein Transformer and makes it amenable to simultaneously edit multiple fuzzy matches found in memory. We discuss how to perform training and inference in this model, based on multi-way alignment algorithms and imitation learning. Our experiments show that editing several examples positively impacts translation scores, notably increasing the number of target spans that are copied from existing instances.

## 1 Introduction

Neural Machine Translation (NMT) has become increasingly efficient and effective thanks to the development of ever larger encoder-decoder architectures relying on Transformer models (Vaswani et al., 2017). Furthermore, these architectures can readily integrate instances retrieved from a Translation Memory (TM) (Bulte and Tezcan, 2019; Xu et al., 2020; Hoang et al., 2022), thereby improving the overall consistency of new translations compared to past ones. In such context, the autoregressive and generative nature of the decoder can make the process (a) computationally inefficient when the new translation has very close matches in the TM; (b) practically ineffective, as there is no guarantee that the output translation, regenerated from scratch, will resemble that of similar texts.

An alternative that is attracting growing attention is to rely on computational models tailored to edit existing examples and adapt them to new source

<table><caption>Table 1: Modified precision of copy vs. generated unigrams and bigrams for TM-LevT. For bigrams, we consider four cases: bigrams made of two copy tokens, two generated tokens, and one token of each type.</caption><thead><tr><th></th><th></th><th>precision</th><th>% units</th></tr></thead><tbody><tr><td rowspan="2">unigram</td><td>copy</td><td>87.5</td><td>64.9</td></tr><tr><td>gen</td><td>52.6</td><td>35.1</td></tr><tr><td rowspan="4">bigram</td><td>copy-copy</td><td>81.4</td><td>55.0</td></tr><tr><td>copy-gen</td><td>40.1</td><td>8.9</td></tr><tr><td>gen-copy</td><td>39.5</td><td>10.7</td></tr><tr><td>gen-gen</td><td>34.2</td><td>25.4</td></tr></tbody></table>

sentences, such as the Levenshtein Transformer (LevT) model of Gu et al. (2019). This model can effectively handle *fuzzy matches* retrieved from memories, performing minimal edits wherever necessary. As decoding in this model occurs is non-autoregressive, it is likely to be computationally more efficient. More important for this work, the reuse of large portions of existing translation examples is expected to yield translations that (a) are more correct; (b) can be transparently traced back to the original instance(s), enabling the user to inspect the edit operations that were performed. To evaluate claim (a) we translate our test data (details in Section 5.1) using a basic implementation of a retrieval-augmented LevT with TM (TM-LevT). We separately compute the modified unigram and bigram precisions (Papineni et al., 2002) for tokens that are copied from the fuzzy match and tokens that are generated by the model.<fnref n="1" /> We observe that copies account for the largest share of output units and have better precision (see Table 1).

Based on this observation, our primary goal is to optimize further the number of tokens copied from the TM. To do so, we propose simultaneously editing multiple fuzzy matches retrieved from memory, using a computational architecture – Multi-LevT,

<footnote n="1">¹Copies and generations are directly inferred from the sequence of edit operations used to compute the output sentence.</footnote>
or TM$^N$-LevT for short – which extends TM-LevT to handle several initial translations. The benefit is twofold: (a) an increase in translation accuracy; (b) more transparency in the translation process. Extending TM-LevT to TM$^N$-LevT however requires solving multiple algorithmic and computational challenges related to the need to compute Multiple String Alignments (MSAs) between the matches and the reference translation, which is a notori- ously difficult problem; and designing appropriate training procedures for this alignment module.

Our main contributions are the following:

1. a new variant of the LevT model that explicitly maximizes target coverage (§4.2);

2. a new training regime to handle an extended set of editing operations (§3.3);

3. two novel multiway alignment (§4.2) and re- alignment (§6.2) algorithms;

4. experiments in 11 domains where we observe an increase of BLEU scores, COMET scores, and the proportion of copied tokens (§6).

Our code and experimental configurations are available on github.<fnref n="2" />

# 2 Preliminaries / Background

## 2.1 TM-based machine translation

Translation Memories, storing examples of past translations, is a primary component of profes- sional Computer Assisted Translation (CAT) en- vironments (Bowker, 2002). Given a translation request for source sentence x, TM-based transla- tion is a two-step process: (a) retrieval of one or several instances (x̃, ȳ) whose source side resem- bles x, (b) adaptation of retrieved example(s) to produce a translation. In this work, we mainly fo- cus on step (b), and assume that the retrieval part is based on a fixed similarity measure Δ between x and stored examples. In our experiments, we use:

$$ \Delta(\mathbf{x}, \tilde{\mathbf{x}}) = 1 - \frac{\mathrm{ED}(\mathbf{x}, \tilde{\mathbf{x}})}{\max(|\mathbf{x}|, |\tilde{\mathbf{x}}|)}, \quad (1) $$

with ED(x, x̃) the edit distance between x and x̃ and |x| the length of x. We only consider TM matches for which Δ exceeds a predefined thresh- old τ and filter out the remaining ones. The next step, adaptation, is performed by humans with CAT

tools. Here, we instead explore ways to perform this step automatically, as in Example-Based MT (Nagao, 1984; Somers, 1999; Carl et al., 2004).

## 2.2 Adapting fuzzy matches with LevT

The Levenshtein transformer of Gu et al. (2019) is an encoder-decoder model which, given a source sentence, predicts edits that are applied to an ini- tial translation in order to generate a revised out- put (Figure 1). The initial translation can either be empty or correspond to a match from a TM. Two editing operations – insertion and deletion – are considered. The former is composed of two steps: first, *placeholder insertion*, which predicts the position and number of new tokens; second, the *predictions of tokens* to fill these positions. Edit- ing operations are applied iteratively in rounds of refinement steps until a final translation is obtained.

In LevT, these predictions rely on a joint encod- ing of the source and the current target and apply in parallel for all positions, which makes LevT a rep- resentative of non-autoregressive translation (NAT) models. As editing operations are not observed in the training data, LevT resorts to Imitation Learn- ing, based on the generation of decoding configu- rations for which the optimal prediction is easy to compute. Details are in (Gu et al., 2019), see also (Xu and Carpuat, 2021), which extends it with a repositioning operation and uses it to decode with terminology constraints, as well as the studies of Niwa et al. (2022) and Xu et al. (2023) who also explore the use of LevT in conjunction with TMs.

<figure><img src="image_2.png" /><figcaption>Figure 1: First decoding pass of TM-LevT, a variant of LevT augmented with Translation Memories.</figcaption></figure>

## 2.3 Processing multiple fuzzy matches

One of the core differences between TM$^N$-LevT and LevT is its ability to handle multiple matches. This

<footnote n="2">²https://github.com/Maxwell11447/fairseq/</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 2: A high-level overview of TM$^N$-Levt's architecture. Additions w.r.t. TM-Levt are in a dashed box.</figcaption></figure>

implies adapting the edit steps (in inference) and the roll-in policy (in imitation learning).

**Inference in TM$^N$-Levt** Decoding follows the same key ideas as for LevT (see Figure 1) but enables co-editing an arbitrary number $N$ of sentences. Our implementation (1) applies deletion, then placeholder insertion simultaneously on each retrieved example; (2) combines position-wise all examples into one single candidate sentence; (3) performs additional steps as in LevT: this includes first completing *token prediction*, then performing *Iterative Refinement* operations that edit the sentence to correct mistakes and improve it (§3.2).

**Training in TM$^N$-Levt** TM$^N$-Levt is trained with imitation learning and needs to learn the edit steps described above for both the first pass (1-2) and the iterative refinement steps (3). This means that we teach the model to perform the sequence of *correct* edit operations needed to iteratively generate the reference output, based on the step-by-step reproduction of what an expert 'teacher' would do. For this, we need to compute the *optimal operation* associated with each configuration (or state) (§4). The *roll-in* and *roll-out policies* specify how the model is trained (§3.3).

# 3 Multi-Levenshtein Transformer

## 3.1 Global architecture

TM$^N$-Levt has two modes of operations: (a) the combination of multiple TM matches into one single sequence through alignment, (b) the iterative refinement of the resulting sequence. In step (a), we use the Transformer encoder-decoder architecture,

extended with additional embedding and linear layers (see Figure 2) to accommodate multiple matches. In each of the $N$ retrieved instances $\mathbf{y} = (\mathbf{y}_1, \dots, \mathbf{y}_N)$, $\mathbf{y}_{n,i}$ (the $i^{th}$ token in the $i^{th}$ instance) is encoded as $E_{\mathbf{y}_{n,i}} + P_i + S_n$, where $E \in \mathbb{R}^{|V| \times d_{model}}$, $P_i \in \mathbb{R}^{L_{max} \times d_{model}}$ and $S_n \in \mathbb{R}^{(N+1) \times d_{model}}$ are respectively the token, position and sequence embeddings. The sequence embedding identifies TM matches, and the positional encodings are reset for each $\mathbf{y}_n$. The extra row in $S$ is used to identify the results of the combination and will yield a different representation for these single sequences.³ Once embedded, TM matches are concatenated and passed through multiple Transformer blocks, until reaching the last layer, which outputs $(h_1, \dots, h_{|V|})$ for a single input match or $(h_{1,1}, \dots, h_{1,|y_1|}, \dots, h_{N,1}, \dots, h_{N,|y_N|})$ in the case of multiple ones. The *learned policy* $\pi_\theta$ computes its decisions from these hidden states. We use four classifiers, one for each sub-policy:

1. **deletion**: predicts *keep* or *delete* for each token $\mathbf{y}_{n,i}^{del}$ with a projection matrix $A \in \mathbb{R}^{2 \times d_{model}}$:

$$ \pi_{\theta}^{del}(d|n, i, \mathbf{y}_{1}^{del}, \dots, \mathbf{y}_{N}^{del}; \mathbf{x}) = \mathrm{softmax}(h_{n,i} A^{T}) $$

2. **insertion**: predicts the number of placeholder insertions between $\mathbf{y}_{n,i}^{plh}$ and $\mathbf{y}_{n,i+1}^{plh}$ with a projection matrix $B \in \mathbb{R}^{(K_{max}+1) \times 2d_{model}}$:

$$ \pi_{\theta}^{plh}(p|n, i, \mathbf{y}_{1}^{plh}, \dots, \mathbf{y}_{N}^{plh}; \mathbf{x}) = \mathrm{softmax}([h_{n,i}, h_{n,i+1}] B^{T}), $$

with $K_{max}$ the max number of insertions.

3. **combination**: predicts if token $\mathbf{y}_{n,i}^{cmb}$ in sequence $n$ must be kept in the combination, with a projection matrix $C \in \mathbb{R}^{2 \times d_{model}}$:

$$ \pi_{\theta}^{cmb}(c|n, i, \mathbf{y}_{1}^{cmb}, \dots, \mathbf{y}_{N}^{cmb}; \mathbf{x}) = \mathrm{softmax}(h_{n,i} C^{T}). $$

4. **prediction**: predicts a token in vocabulary $V$ at each placeholder position, with a projection matrix $D \in \mathbb{R}^{|V| \times d_{model}}$:

$$ \pi_{\theta}^{tok}(t|n, i, \mathbf{y}^{tok}; \mathbf{x}) = \mathrm{softmax}(h_{j} D^{T}) $$

Except for step 3, these classifiers are similar to those used in the original LevT.
<figure><img src="image_4.png" /><figcaption>Figure 3: The first decoding pass in TM$^N$-LevT.</figcaption></figure>

## 3.2 Decoding

Decoding is an iterative process: in a first pass, the *N* fuzzy matches are combined to compute a candidate translation; then, as in LevT, an additional series of *iterative refinement* rounds (Gu et al., 2019) is applied until convergence or timeout. Figure 3 illustrates the first pass, where *N* = 2 matches are first edited in parallel, then combined into one output.

To predict deletions (*resp.* insertions and token predictions), we apply the *argmax* operator to $\pi_{\theta}^{del}$ (*resp.* $\pi_{\theta}^{plh}$, $\pi_{\theta}^{tok}$). For combinations, we need to aggregate separate decisions $\pi_{\theta}^{cmb}$ (one per token and match) into one sequence. For this, at each position, we pick the most likely token.

During iterative refinement, we bias the model towards generating longer sentences since LevT outputs tend to be too short (Gu et al., 2019). As in LevT, we add a penalty to the probability of inserting 0 placeholder in $\pi_{\theta}^{plh}$ (Stern et al., 2019). This only applies in the refinement steps to avoid creating more misalignments (see §6.2).

## 3.3 Imitation learning

We train TM$^N$-LevT with Imitation Learning (Daumé et al., 2009; Ross et al., 2011), teaching the system to perform the right edit operation for each decoding state. As these operations are unobserved in the training data, the standard approach is to simulate decoding states via a *roll-in policy*; for each of these, the optimal decision is computed via an *expert policy* $\pi_*$, composed of intermediate experts $\pi_*^{del}$, $\pi_*^{plh}$, $\pi_*^{cmb}$, $\pi_*^{tok}$. The notion of optimality is discussed in §4. Samples of pairs (*state, decision*) are then used to train the system policy $\pi_{\theta}$.

First, from the initial set of sentences $y^{init}$, the unrolling of $\pi_*$ produces intermediate states ($y^{del}$, $del^*$), ($y^{plh}$, $plh^*$), ($y^{cmb}$, $cmb^*$), ($y^{tok}$, $tok^*$) (see top left in Figure 4). Moreover, in this framework, it is critical to mitigate the *exposure bias* and generate states that result from non-optimal past decisions (Zheng et al., 2023). For each training sample ($x$, $y_1$, ..., $y_N$, $y_*$), we simulate multiple additional states as follows (see Figure 4 for the full picture). We begin with the operations involved in the first decoding pass:<fnref n="4" />

1. **Additional triplets**#: $\pi^{rnd-del \cdot N}$ turns $y_*$ into $N$ random substrings, which simulates the edition of $N$ artificial examples.

2. **Token selection**# (uses $\pi^{sel}$): our expert policy never aligns two distinct tokens at a given position (§4.3). We simulate such cases that may occur at inference, as follows: with probability $\gamma$, each <PLH> is replaced with a random token from fuzzy matches (Figure 5).

The expert always completes its translation in one decoding pass. Policies used in iterative refinement are thus trained with the following simulated states, based on roll-in and roll-out policies used in LevT and its variants (Gu et al., 2019; Xu et al., 2023; Zheng et al., 2023):

3. **Add missing words** (uses $\pi^{rnd-del} \cdot 1$): with probability $\alpha$, $y^{post-plh}=y_*$. With probability $1-\alpha$, generate a subsequence $y^{post-plh}$ with length sampled uniformly in $[0, |y_*|]$.

4. **Correct mistakes** (uses $\pi_{\theta}^{tok}$): using the output of token prediction $y^{post-del}$, teach the model to erase the wrongly predicted tokens.

5. **Remove extra tokens**# (uses $\pi_{\theta}^{ins}$, $\pi_{\theta}^{tok}$): insert placeholders in $y^{post-tok}$ and predict tokens, yielding $y^{post-del-extra}$, which trains the model to delete wrong tokens. These sequences differ from case (4) in the way <PLH> are inserted.

6. **Predict token**# (uses $\pi^{rnd-msk}$): each token in $y_*$ is replaced by <PLH> with probability $\epsilon$. As token prediction applies for both decoding steps, these states also improve the first pass.

The expert decisions (e.g. inserting deleted tokens like in state (3); or deleting wrongly predicted

<footnote n="3">³$y_n^{op}$ denotes an intermediary sequence before applying edit operation *op*. $y_n^{op} \in \mathbb{N}^L$ is encoded with $S_n$; $y_n^{op} \in \mathbb{N}^L$ with $S_N$.</footnote>

<footnote n="4">⁴Families of (*state, decision*) pairs that are novel with respect to TM-LevT are marked with #.</footnote>
<figure><img src="image_5.png" /><figcaption>Figure 4: Roll-in policies used in training. Blue cells contain sets of target sentences (e.g. $y^{del}$), optionally associated with the expert prediction (e.g. $del^*$). Model's predictions are in Thistle and circumflexed (e.g. $del^-$). Pairs of model / expert predictions are summed in the loss: $(del^-, del^*)$, $(plh^-, plh^*)$, $(cmb^-, cmb^*)$, $(post \cdot del^-, post \cdot del^*)$, $(post \cdot plh^-, post \cdot plh^*)$, $(post \cdot del \cdot extra^-, post \cdot plh \cdot extra^*)$. "post" denotes policies applied in refinement steps.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: Noising $y^{cmb}$ with $\pi^{sel}$ using tokens from $y^{init} = (y_1, \dots, y_N)$.</figcaption></figure>

tokens in state (4)) associated with most states are
obvious, except for the initial state and state (5),
which require an optimal alignment computation.

4 Optimal Alignment

Training the combination operation introduced
above requires specifying the expert decision for
each state. While LevT derives its expert policy $\pi_*$
from the computation of *edit distances*, we intro-
duce another formulation based on the computation
of *maximal covers*. For $N=1$, these formulations
can be made equivalent<fnref n="5" /> (Gusfield, 1997).

4.1 N-way alignments

We formulate the problem of optimal editing as an
N-way alignment problem (see figure 6) that we de-
fine as follows. Given *N* examples (*y*₁, ..., *y*ₙ) and the target sentence *y*<sub>*</sub>, a N-way alignment of (y<sub>1</sub>, ..., y<sub>N</sub>) w.r.t. *y*<sub>*</sub> is represented as a bipartite
graph (*V*, *V*<sub>*</sub>, *E*), where *V* is further partitioned
into *N* mutually disjoint subsets V<sub>1</sub> ... V<sub>N</sub>. Ver-
tices in each V<sub>n</sub> (resp. V<sub>*</sub>) correspond to tokens in
y<sub>n</sub> (resp. y<sub>*</sub>). Edges (n, i, j) ∈ E connect node i

in $V_n$ to node $j$ in $V_*$: An N-way alignment satisfies
properties (i)-(ii):

(i) Edges connect identical (matching) tokens:

$$
(n, i, j) \in E \Rightarrow y_{n,i} = y_{*,j}.
$$

(ii) Edges that are incident to the same subset $V_n$
do not cross:

$$
(n, i, j), (n, i', j') \in E \Rightarrow (i' - i)(j' - j) > 0.
$$

An optimal N-way alignment $E_*$ maximizes the
coverage of tokens in $y_*$, then the total number
of edges, where $y_{*,j}$ is covered if there exists at
least one edge $(n, i, j) \in E$. Denoting $\mathbb{E}$ the set of
alignments maximizing target coverage:

$$
\mathbb{E} = \arg \max_{E} |\{y_{*,j} : \exists (n, i), (n, i, j) \in E\}|.
$$

$$
E_* = \arg \max_{E \in \mathbb{E}} |E|.
$$

4.2 Solving optimal alignment

Computing the optimal N-way alignment is NP-
hard (see Appendix D). This problem can be solved
using Dynamic Programming (DP) techniques
similar to Multiple Sequence Alignment (MSA)
(Carrillo and Lipman, 1988) with a complexity
$O(N|y_*| \prod_n |y_n|)$. We instead implemented the
following two-step heuristic approach:

1. separately compute alignment graphs between each $\mathbf{y}_n$ and $\mathbf{y}_*$, then extract $k$-best 1-way alignments $\{E_{n,1} \dots E_{n,k}\}$. This requires time $O(k|\mathbf{y}_n||\mathbf{y}_*|)$ using DP (Gusfield, 1997);

<footnote n="5">⁵When the cost of replace is higher than insertion + deletion. This is the case in the original LevT code.</footnote>
<figure><img src="image_7.png" /><figcaption>Figure 6: Illustration of the optimal N-way alignment which maximizes a global coverage criterion (6b), while independent alignments do not guarantee optimal usage of information present in TM examples (6a).</figcaption></figure>

2. search for the optimal recombination of these graphs, selecting 1-way alignments ($E_{1,k_1} \dots E_{N,k_N}$) to form $E_* = \bigcup_n E_{n,k_n}$. Assuming $N$ and $k$ are small, we perform an exhaustive search in $O(k^N)$.

## 4.3 From alignments to edits

From an alignment $(V, V_*, E)$, we derive the optimal edits needed to compute $y_*$, and the associated intermediary sequences. Edges in $E$ indicate the tokens that are preserved throughout this process:

1. deletion: $\forall n, \forall i, y_{n,i}$ is kept only if $(n, i, j) \in E$ for some $j$; otherwise it is deleted. The resulting sequences are $\{y_n^{ph}\}_{n=1...N}$.

2. insertion: Placeholders are inserted between successive tokens in all $y_n^{ph}$, resulting in the set $\{y_n^{cmb}\}_{n=1...N}$, under the constraints that (a) all $y_n^{cmb}$ have the same length as $y_*$ and (b) non Placeholder tokens $y_{n,i}^{cmb}$ are equal to the reference token $y_{*,i}$.

3. combination: Sequences $\{y_n^{cmb}\}_{n=1...N}$ are combined into $y^{tok}$ such that for each position $i$, $y_{n,i}^{cmb} \neq \langle \text{PLH} \rangle \Rightarrow y_i^{tok} = y_{n,i}^{cmb}$. If $\forall n, y_{n,i}^{cmb} = \langle \text{PLH} \rangle$, then $y_i^{tok} = \langle \text{PLH} \rangle$.

4. prediction: The remaining $\langle \text{PLH} \rangle$ symbols in $y^{tok}$ are replaced by the corresponding target token in $y_*$ at the same position.

The expert policy $\pi_*$ edits examples $y_1, \dots, y_N$ into $y_*$ based on the optimal alignment $(V, V_*, E_*)$. It comprises $\pi_*^{del}, \pi_*^{ph}, \pi_*^{cmb}$, and $\pi_*^{tok}$, corresponding to the four steps listed above.

# 5 Experiments

## 5.1 Data and metrics

We focus on translation from English to French and consider multiple domains. This allows us to consider a wide range of scenarios, with a varying density of matching examples: our datasets include

ECB, EMEA, Europarl, GNOME, JRC-Acquis, KDE4, PHP, Ubuntu, where high-quality matches are often available, but also News-Commentary, TED2013, and Wikipedia, where matches are more scarce (see Table 6, §B).

For each training sample $(x, y)$, we retrieve up to 3 in-domain matches. We filter matches $x_n$ to keep only those with $\Delta(x, x_n) > 0.4$. We then manually split each of the 11 datasets into train, valid, test-0.4, test-0.6, where the valid and test sets contain 1,000 lines each. test-0.4 (resp. test-0.6) contains samples whose best match is in the range [0.4, 0.6] (resp. [0.6, 1]). As these two test sets are only defined based on the best match score, it may happen that some test instances will only retrieve 1 or 2 close matches (statistics are in Table 6).

For the pre-training experiments (§6.2), we use a subsample of 2M random sentences from WMT’14. For all data, we use Moses tokenizer and 32k BPEs trained on WMT’14 with SentencePiece (Kudo, 2018). We report BLEU scores (Papineni et al., 2002) and ChrF scores (Popović, 2015) as computed by SacreBLEU (Post, 2018) and COMET scores (Rei et al., 2020).

## 5.2 Architecture and settings

Our code<fnref n="6" /> extends Fairseq<fnref n="7" /> implementation of LevT in many ways. It uses Transformer models (Vaswani et al., 2017) (parameters in Appendix A). Roll-in policy parameters (§3.3) are empirically set as: $\alpha=0.3, \beta=0.2, \gamma=0.2, \delta=0.2, \varepsilon=0.4$. The AR baseline uses OpenNMT (Klein et al., 2017) and uses the same data as TM-LevT (Appendix A).

# 6 Results

## 6.1 The benefits of multiple matches

We compare two models in Table 2: one trained with one TM match, the other with three. Each

<footnote n="6">⁶https://github.com/Maxwell11447/fairseq</footnote>

<footnote n="7">⁷https://github.com/facebookresearch/fairseq</footnote>
<table><caption>Table 2: BLEU/ChrF and COMET scores on the full test set. All BLEU/ChrF differences are significant ($p$ = 0.05).</caption><thead><tr><th>Model \N</th><th>1</th><th>2</th><th>3</th><th>all</th></tr></thead><tbody><tr><td>size</td><td>4,719</td><td>2,369</td><td>14,912</td><td>22,000</td></tr><tr><td>TM<sup>1</sup>-LevT</td><td>45.8/63.6</td><td>48.7/65.0</td><td>55.0/68.4</td><td>52.0/66.8</td></tr><tr><td>TM<sup>3</sup>-LevT</td><td>46.6/64.1</td><td>50.0/65.8</td><td>56.0/69.3</td><td>53.0/67.5</td></tr></tbody></table>

model is evaluated with, at most, the same number of matches seen in training. This means that TM¹-LevT only uses the 1-best match, even when more examples are found. In this table, test sets test-0.4 and test-0.6 are concatenated, then partitioned between samples for which exactly 1, 2, and 3 matches are retrieved. We observe that TM³-LevT, trained with 3 examples, consistently achieves better BLEU and ChrF scores than TM¹-LevT, even in the case $N=1$, where we only edit the closest match.<fnref n="8" /> These better BLEU scores are associated with a larger number of copies from the retrieved instances, which was our main goal (Table 3). Similar results for the other direction are reported in the appendix § E (Table 7).

<table><caption>Table 3: Proportion of unigrams and bigram from a given origin (copy vs. generation) for various models.</caption><thead><tr><th></th><th></th><th>TM-LevT</th><th>TM<sup>1</sup>-LevT</th><th>TM<sup>3</sup>-LevT</th></tr></thead><tbody><tr><td rowspan="2">unigram</td><td>copy</td><td>64.9</td><td>64.5</td><td>68.8</td></tr><tr><td>gen</td><td>35.1</td><td>35.5</td><td>31.2</td></tr><tr><td rowspan="4">bigram</td><td>copy-copy</td><td>55.0</td><td>54.5</td><td>58.0</td></tr><tr><td>copy-gen</td><td>8.9</td><td>9.0</td><td>10.1</td></tr><tr><td>gen-copy</td><td>10.7</td><td>10.8</td><td>11.0</td></tr><tr><td>gen-gen</td><td>25.4</td><td>25.7</td><td>20.9</td></tr></tbody></table>

We report the performance of systems trained using $N=1, 2, 3$ for each domain and test set in Table 4 (BLEU) and 12 (COMET). We see comparable average BLEU scores for $N=1$ and $N=3$, with large variations across domains, from which we conclude that: (a) using 3 examples has a smaller return when the best match is poor, meaning that bad matches are less likely to help (test-0.4 vs. test-0.6); (b) using 3 examples seems advantageous for narrow domains, where training actually exploits several close matches (see also Appendix F). We finally note that COMET scores<fnref n="9" /> for TM³-LevT are

always slightly lower than for TM¹-LevT, which prompted us to develop several extensions.

## 6.2 Improving TM$^N$-LevT

<figure><img src="image_8.png" /><figcaption>Figure 7: Fixing misalignments with realignment</figcaption></figure>

**Realignment** In preliminary experiments, we observed that small placeholder prediction errors in the first decoding pass could turn into catastrophic misalignments (Figure 7). To mitigate such cases, we introduce an additional realignment step during inference, where some predicted placeholders are added/removed if this improves the global alignment. Realignment is formulated as an optimization problem aimed to perform a tradeoff between the score $-\log \pi_{\theta}^{\text{plh}}$ of placeholder insertion and an alignment cost (see Appendix C).

We assess realignment for $N=3$ (Tables 4 and 12) and observe small, yet consistent average gains (+0.2 BLEU, +1.5 COMET) for both test sets.

**Pre-training** Another improvement uses pre-training with synthetic data. For each source/target pair $(x, y)$ in the pre-training corpus, we simulate $N$ fuzzy matches by extracting from $y$ $N$ substrings $y_n$ of length $\approx |y| \cdot r$, with $r \in [0, 1]$. Each $y_n$ is then augmented as follows:

1. We randomly insert placeholders to increase the length by a random factor between 1 and $1+f$, $f = 0.5$ in our experiments.

2. We use the CamemBERT language model (Martin et al., 2020) to fill the masked tokens.

These artificial instances simulate diverse fuzzy matches and are used to pre-train a model, using the same architecture and setup as in §5.2. Pre-training yields markedly higher scores than the baseline (+1.3 BLEU, +6.4 COMET for test-0.4 and +0.9 BLEU, +4.6 COMET for test-0.6). Training curves also suggest that pre-trained models are faster to converge. Combining with realignment yields additional gains for TM³-LevT, which outperforms TM¹-LevT in all domains and both metrics.

<footnote n="8">⁸This is because the former model has been fed with more examples during training, which may help regularization.</footnote>

<footnote n="9">⁹Those numbers are harder to interpret, given the wide range of COMET scores across domains (from ≈ -40 to +86).</footnote>
<table><caption>Table 4: Per domain BLEU scores for TM-LevT, TM$^N$-LevT and variants. Bold (resp. italic) for scores significantly higher (resp. lower) than TM$^1$-LevT (p = 0.05). p-values from SacreBLEU paired bootstrap resampling (n = 1000). The Autoregressive (AR) system is our implementation of (Bulte and Tezcan, 2019).</caption><thead><tr><th></th><th></th><th>ECB</th><th>EME</th><th>Epp</th><th>GNO</th><th>JRC</th><th>KDE</th><th>News</th><th>PHP</th><th>TED</th><th>Ubu</th><th>Wiki</th><th>all</th></tr></thead><tbody><tr><td rowspan="7">test-0.4</td><td>AR</td><td><b>63.0</b></td><td><b>63.6</b></td><td><b>43.6</b></td><td><b>69.3</b></td><td><b>75.1</b></td><td><b>62.8</b></td><td><b>28.8</b></td><td><b>41.2</b></td><td><b>42.2</b></td><td><b>59.1</b></td><td><b>42.2</b></td><td><b>55.8</b></td></tr><tr><td>TM-LevT</td><td>50.5</td><td>50.7</td><td>31.3</td><td>54.3</td><td>62.4</td><td>47.9</td><td>18.0</td><td>30.1</td><td>24.2</td><td>43.3</td><td>29.8</td><td>42.8</td></tr><tr><td>TM<sup>1</sup>-LevT</td><td>53.1</td><td>53.7</td><td>35.5</td><td>60.3</td><td>65.6</td><td>51.8</td><td>22.2</td><td>31.7</td><td>30.2</td><td>48.8</td><td>32.0</td><td>46.2</td></tr><tr><td>TM<sup>2</sup>-LevT</td><td><b>54.0</b></td><td>54.3</td><td>34.0</td><td>60.5</td><td>66.0</td><td>53.2</td><td>20.7</td><td><b>33.7</b></td><td>28.9</td><td>48.0</td><td>32.6</td><td>46.5</td></tr><tr><td>TM<sup>3</sup>-LevT</td><td><b>53.9</b></td><td><b>55.6</b></td><td>34.2</td><td>60.8</td><td>66.0</td><td><b>53.5</b></td><td>20.4</td><td><b>33.1</b></td><td>28.6</td><td>47.5</td><td>32.9</td><td><b>46.5</b></td></tr><tr><td>+pre-train</td><td><b>54.9</b></td><td><b>55.9</b></td><td>34.4</td><td><b>62.7</b></td><td><b>67.4</b></td><td><b>54.1</b></td><td>21.1</td><td><b>34.7</b></td><td>30.1</td><td>49.3</td><td><b>33.5</b></td><td><b>47.5</b></td></tr><tr><td>+realign</td><td><b>54.4</b></td><td><b>55.9</b></td><td>34.4</td><td><b>61.2</b></td><td>66.2</td><td>53.2</td><td>20.4</td><td><b>33.3</b></td><td>28.4</td><td>47.9</td><td><b>33.1</b></td><td><b>46.7</b></td></tr><tr><td>+both</td><td><b>55.0</b></td><td><b>56.0</b></td><td>34.9</td><td><b>62.8</b></td><td><b>67.5</b></td><td><b>54.0</b></td><td>21.4</td><td><b>34.8</b></td><td>30.8</td><td>49.6</td><td><b>33.9</b></td><td><b>47.8</b></td></tr><tr><td rowspan="7">test-0.6</td><td>AR</td><td><b>69.7</b></td><td><b>70.4</b></td><td><b>57.4</b></td><td><b>80.6</b></td><td><b>82.4</b></td><td><b>68.2</b></td><td><b>26.1</b></td><td><b>46.4</b></td><td><b>62.5</b></td><td><b>68.5</b></td><td><b>68.7</b></td><td><b>66.6</b></td></tr><tr><td>TM-LevT</td><td>59.0</td><td>64.0</td><td>45.8</td><td>66.9</td><td>73.5</td><td>53.4</td><td>18.8</td><td>34.7</td><td>49.1</td><td>53.2</td><td>58.9</td><td>55.8</td></tr><tr><td>TM<sup>1</sup>-LevT</td><td>60.5</td><td>64.6</td><td>48.9</td><td>69.7</td><td>75.7</td><td>57.2</td><td>21.0</td><td>36.2</td><td>55.0</td><td>58.3</td><td>62.2</td><td>58.2</td></tr><tr><td>TM<sup>2</sup>-LevT</td><td><b>62.7</b></td><td><b>67.0</b></td><td><b>50.0</b></td><td><b>71.7</b></td><td>76.2</td><td><b>60.2</b></td><td>21.7</td><td><b>38.6</b></td><td>54.2</td><td><b>59.8</b></td><td>62.8</td><td><b>59.7</b></td></tr><tr><td>TM<sup>3</sup>-LevT</td><td><b>63.8</b></td><td><b>67.4</b></td><td><b>50.0</b></td><td><b>71.1</b></td><td><b>76.4</b></td><td><b>60.0</b></td><td>21.5</td><td><b>39.2</b></td><td>54.3</td><td><b>59.6</b></td><td>62.3</td><td><b>60.0</b></td></tr><tr><td>+pre-train</td><td><b>64.9</b></td><td><b>68.3</b></td><td><b>50.3</b></td><td><b>72.7</b></td><td><b>77.3</b></td><td><b>62.3</b></td><td><b>21.8</b></td><td><b>40.7</b></td><td>54.6</td><td><b>61.3</b></td><td><b>65.0</b></td><td><b>61.1</b></td></tr><tr><td>+realign</td><td><b>64.0</b></td><td><b>68.0</b></td><td><b>50.2</b></td><td><b>71.5</b></td><td><b>76.5</b></td><td><b>59.9</b></td><td>21.6</td><td><b>39.0</b></td><td>54.7</td><td><b>60.0</b></td><td>63.1</td><td><b>60.2</b></td></tr><tr><td>+both</td><td><b>65.0</b></td><td><b>68.3</b></td><td><b>50.8</b></td><td><b>73.7</b></td><td><b>77.4</b></td><td><b>62.3</b></td><td><b>22.0</b></td><td><b>40.6</b></td><td>54.7</td><td><b>61.4</b></td><td><b>65.3</b></td><td><b>61.3</b></td></tr></tbody></table>

**Knowledge distillation** *Knowledge Distillation* (KD) (Kim and Rush, 2016) is used to mitigate the effect of multimodality of NAT models (Zhou et al., 2020) and to ease the learning process. We trained a TM$^N$-LevT model with distilled samples $(x, \tilde{y}_1, \dots, \tilde{y}_N, \tilde{y})$, where automatic translations $\tilde{y}_i$ and $\tilde{y}$ are derived from their respective source $x_i$ and x with an auto-regressive teacher trained with a concatenation of all the training data.

We observe that KD is beneficial (+0.3 BLEU) for low-scoring matches (*test-0.4*) but hurts performance (-1.7 BLEU) for the better ones in *test-0.6*. This may be because the teacher model, with a BLEU score of 56.7 on the *test-0.6*, fails to provide the excellent starting translations the model can access when using non-distilled data.

## 6.3 Ablation study

We evaluate the impact of the various elements in the mixture roll-in policy via an ablation study (Table 13). Except for $\pi^{sel}$, every new element in the roll-in policy increases performance. As for $\pi^{sel}$, our system seems to be slightly better with than without. An explanation is that, in case of misalignment, the model is biased towards selecting the first, most similar example sentence. As an ablation, instead of aligning by globally maximizing coverage (§ 4.2), we also compute alignments that maximize coverage independently as in figure 6a.

A complete run of TM$^N$-LevT is in Appendix F.

<table><caption>Table 5: Ablation study. We build models with variable roll-in policies: -sel: no random selection noise ($\gamma$=0); -delx: no extra deletion; -rd-del: no random deletion ($\beta$=0); -mask: no random mask ($\delta$=0); -dum-plh: never start with $y_{post-del}=y_*$ ($\alpha$=0); -indep-align: alignments are independent. Full results in Appendix F.</caption><thead><tr><th></th><th>test-0.4</th><th>test-0.6</th></tr></thead><tbody><tr><td>TM<sup>3</sup>-LevT</td><td><b>46.5</b></td><td><b>60.1</b></td></tr><tr><td>-sel</td><td>46.2</td><td>60.0</td></tr><tr><td>-delx</td><td>44.8</td><td>58.6</td></tr><tr><td>-rnd-del</td><td>38.6</td><td>51.9</td></tr><tr><td>-rnd-mask</td><td>46.0</td><td>59.0</td></tr><tr><td>-dum-plh</td><td>41.0</td><td>50.9</td></tr><tr><td>-indep-align</td><td>42.6</td><td>56.4</td></tr></tbody></table>

## 7 Related Work

As for other Machine Learning applications, such as text generation (Guu et al., 2018), efforts to integrate a retrieval component in neural-based MT have intensified in recent years. One motivation is to increase the transparency of ML models by providing users with tangible traces of their internal computations in the form of retrieved examples (Rudin, 2019). For MT, this is achieved by integrating fuzzy matches retrieved from memory as an additional conditioning context. This can be performed simply by concatenating the retrieved target instance to the source text (Bulte and Tezcan, 2019), an approach that straightforwardly accommodates several TM matches (Xu et al., 2020), or the simultaneous exploitation of their source and target sides (Pham et al., 2020). More complex schemes to combine retrieved examples with the source sentence are in (Gu et al., 2018; Xia et al.,
2019; He et al., 2021b). The recent work of Cheng et al. (2022) handles multiple complementary TM examples retrieved in a *contrastive manner* that aims to enhance source coverage. Cai et al. (2021) also handle multiple matches and introduce two novelties: (a) retrieval is performed in the target language and (b) similarity scores are trainable, which allows to evaluate retrieved instances based on their usefulness in translation. Most of these attempts rely on an auto-regressive (AR) decoder, meaning that the impact of TM match(es) on the final output is only indirect.

The use of TM memory match with a NAT decoder is studied in (Niwa et al., 2022; Xu et al., 2023; Zheng et al., 2023), which adapt LevT for this specific setting, using one single retrieved instance to initialize the edit-based decoder. Other evolutions of LevT, notably in the context of constraint decoding, are in (Susanto et al., 2020; Xu and Carpuat, 2021), while a more general account of NAT systems is in (Xiao et al., 2023).

Zhang et al. (2018) explore a different set of techniques to improve translation using retrieved segments instead of full sentences. Extending KNN-based language models (He et al., 2021a) to the conditional case, Khandelwal et al. (2021) proposes *k*-nearest neighbor MT by searching for target tokens that have similar contextualized representations at each decoding step, an approach further elaborated by Zheng et al. (2021); Meng et al. (2022) and extended to chunks by Martins et al. (2022).

## 8 Conclusion and Outlook

In this work, we have extended the Levenshtein Transformer with a new combination operation, making it able to simultaneously edit multiple fuzzy matches and merge them into an initial translation that is then refined. Owing to multiple algorithmic contributions and improved training schemes, we have been able to (a) increase the number of output tokens that are copied from retrieved examples; (b) obtain performance improvements compared to using one single match. We have also argued that retrieval-based NMT was a simple way to make the process more transparent for end users.

Next, we would like to work on the retrieval side of the model: first, to increase the diversity of fuzzy matches e.g. thanks to contrastive retrieval, but also to study ways to train the retrieval mechanism and extend this approach to search monolingual (target side) corpora. Another line of work will

combine our techniques with other approaches to TM-based NMT, such as keeping track of the initial translation(s) on the encoder side.

## 9 Limitations

As this work was primarily designed a feasibility study, we have left aside several issues related to performance, which may explain the remaining gap with published results on similar datasets. First, we have restricted the encoder to only encode the source sentence, even though enriching the input side with the initial target(s) has often been found to increase performance (Bulte and Tezcan, 2019), also for NAT systems (Xu et al., 2023). It is also likely that increasing the number of training epochs would yield higher absolute scores (see Appendix F).

These choices were made for the sake of efficiency, as our training already had to fare with the extra computing costs incurred by the alignment procedure required to learn the expert policy. Note that in comparison, the extra cost of the realignment procedure is much smaller, as it is only paid during inference and can be parallelized on GPUs.

We would also like to outline that our systems do not match the performance of an equivalent AR decoder, a gap that remains for many NAT systems (Xiao et al., 2023). Finally, we have only reported here results for one language pair – favoring here domain diversity over language diversity – and would need to confirm the observed improvements on other language pairs and conditions.

## 10 Acknowledgements

This work was performed using HPC resources from GENCI-IDRIS (Grant 2022-AD011013583) and Lab-IA from Saclay-IA.

The authors wish to thank Dr. Jitao Xu and Dr. Caio Corro for their guidance and help.

## References

* Lynne Bowker. 2002. *Computer-aided translation technology: A practical introduction*. University of Otawa Press.

* Bram Bulte and Arda Tezcan. 2019. *Neural fuzzy repair: Integrating fuzzy matches into neural machine translation*. In *Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics*, pages 1800–1809, Florence, Italy. Association for Computational Linguistics.
Deng Cai, Yan Wang, Huayang Li, Wai Lam, and Lemao Liu. 2021. Neural machine translation with monolingual translation memory. In *Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)*, pages 7307–7318, Online. Association for Computational Linguistics.

Michael Carl, Andy Way, and Walter Daelemans. 2004. Recent advances in example-based machine translation. *Computational Linguistics*, 30:516–520.

Humberto Carrillo and David Lipman. 1988. The multiple sequence alignment problem in biology. *SIAM Journal on Applied Mathematics*, 48(5):1073–1082.

Xin Cheng, Shen Gao, Lemao Liu, Dongyan Zhao, and Rui Yan. 2022. Neural machine translation with contrastive translation memories. In *Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (EMNLP)*. Association for Computational Linguistics.

Hal Daumé, John Langford, and Daniel Marcu. 2009. Search-based structured prediction. *Machine Learning*, 75(3):297–325.

Michael R. Garey and David S. Johnson. 1979. Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company, New York.

Jiatao Gu, Changhan Wang, and Junbo Zhao. 2019. Levenshtein transformer. In *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc.

Jiatao Gu, Yong Wang, Kyunghyun Cho, and Victor O.K. Li. 2018. Search Engine Guided Neural Machine Translation. *Proceedings of the AAAI Conference on Artificial Intelligence*, 32(1).

Dan Gusfield. 1997. *Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology*. Cambridge University Press.

Kelvin Guu, Tatsunori B. Hashimoto, Yonatan Oren, and Percy Liang. 2018. Generating sentences by editing prototypes. *Transactions of the Association for Computational Linguistics*, 6:437–450.

Junxian He, Graham Neubig, and Taylor Berg-Kirkpatrick. 2021a. Efficient nearest neighbor language models. In *Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing*, pages 5703–5714, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.

Qiuxiang He, Guoping Huang, Qu Cui, Li Li, and Lemao Liu. 2021b. Fast and accurate neural machine translation with translation memory. In *Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing*

(Volume 1: Long Papers), pages 3170–3180, Online. Association for Computational Linguistics.

Cuong Hoang, Devendra Sachan, Prashant Mathur, Brian Thompson, and Marcello Federico. 2022. Improving Retrieval Augmented Neural Machine Translation by Controlling Source and Fuzzy-Match Interactions. ArXiv:2210.05047 [cs].

Urvashi Khandelwal, Angela Fan, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2021. Nearest Neighbor Machine Translation. In *Proceedings of the International Conference on Learning Representations*.

Yoon Kim and Alexander M. Rush. 2016. Sequence-level knowledge distillation. In *Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing*, pages 1317–1327, Austin, Texas. Association for Computational Linguistics.

Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senelart, and Alexander Rush. 2017. OpenNMT: Open-source toolkit for neural machine translation. In *Proceedings of ACL 2017, System Demonstrations*, pages 67–72, Vancouver, Canada. Association for Computational Linguistics.

Taku Kudo. 2018. Subword regularization: Improving neural network translation models with multiple subword candidates. In *Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)*, pages 66–75, Melbourne, Australia. Association for Computational Linguistics.

Louis Martin, Benjamin Muller, Pedro Javier Ortiz Suárez, Yoann Dupont, Laurent Romary, Éric de la Clergerie, Djamé Seddah, and Benoît Sagot. 2020. CamemBERT: a tasty French language model. In *Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics*, pages 7203–7219, Online. Association for Computational Linguistics.

Pedro Henrique Martins, Zita Marinho, and André F. T. Martins. 2022. Chunk-based nearest neighbor machine translation. In *Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing*, pages 4228–4245, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.

Yuxian Meng, Xiaoya Li, Xiayu Zheng, Fei Wu, Xi-aofei Sun, Tianwei Zhang, and Jiwei Li. 2022. Fast nearest neighbor machine translation. In *Findings of the Association for Computational Linguistics: ACL 2022*, pages 555–565, Dublin, Ireland. Association for Computational Linguistics.

Makoto Nagao. 1984. A framework of a mechanical translation between Japanese and English by analogy principle. In *Artificial and human intelligence*. Elsevier Science Publishers. B.V.
Ayana Niwa, Sho Takase, and Naoaki Okazaki. 2022. Nearest neighbor non-autoregressive text generation. CoRR, abs/2208.12496.

Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.

Minh Quang Pham, Jitao Xu, Josep Crego, François Yvon, and Jean Senellart. 2020. Priming neural machine translation. In Proceedings of the Fifth Conference on Machine Translation, pages 516–527, Online. Association for Computational Linguistics.

Maja Popović. 2015. chrF: character n-gram F-score for automatic MT evaluation. In Proceedings of the Tenth Workshop on Statistical Machine Translation, pages 392–395, Lisbon, Portugal. Association for Computational Linguistics.

Matt Post. 2018. A call for clarity in reporting BLEU scores. In Proceedings of the Third Conference on Machine Translation: Research Papers, pages 186–191, Brussels, Belgium. Association for Computational Linguistics.

Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie. 2020. COMET: A neural framework for MT evaluation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2685–2702, Online. Association for Computational Linguistics.

Stephane Ross, Geoffrey Gordon, and Drew Bagnell. 2011. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 627–635, Fort Lauderdale, FL, USA. PMLR.

Cynthia Rudin. 2019. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206–215.

Harold Somers. 1999. Review article: Example-based machine translation. Machine Translation, 14(2):113–157.

Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. 2019. Insertion transformer: Flexible sequence generation via insertion operations. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5976–5985. PMLR.

Raymond Hendy Susanto, Shamil Chollampatt, and Lil-ing Tan. 2020. Lexically constrained neural machine translation with Levenshtein transformer. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3536–3543, On-line. Association for Computational Linguistics.

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 6000–6010, Red Hook, NY, USA. Curran Associates Inc.

Mengzhou Xia, Guoping Huang, Lemao Liu, and Shum-ing Shi. 2019. Graph based translation memory for neural machine translation. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):7297–7304.

Yisheng Xiao, Lijun Wu, Junliang Guo, Juntao Li, Min Zhang, Tao Qin, and Tie-Yan Liu. 2023. A survey on non-autoregressive generation for neural machine translation and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1–20.

Jitao Xu, Josep Crego, and Jean Senellart. 2020. Boost-ing neural machine translation with similar transla-tions. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1580–1590, Online. Association for Computational Linguistics.

Jitao Xu, Josep Crego, and François Yvon. 2023. Inter-grating translation memories into non-autoregressive machine translation. In Proceedings of the 17th Con-ference of the European Chapter of the Association for Computational Linguistics, pages 1326–1338, Dubrovnik, Croatia. Association for Computational Linguistics.

Weijia Xu and Marine Carpuat. 2021. EDITOR: An edit-based transformer with repositioning for neu-ral machine translation with soft lexical constraints. Transactions of the Association for Computational Linguistics, 9:311–328.

Jingyi Zhang, Masao Utiyama, Eiichro Sumita, Gra-ham Neubig, and Satoshi Nakamura. 2018. Guiding neural machine translation with retrieved translation pieces. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 1325–1335, New Orleans, Louisiana. Association for Computa-tional Linguistics.

Kangjie Zheng, Longyue Wang, Zhihao Wang, Binqi Chen, Ming Zhang, and Zhaopeng Tu. 2023. To-wards a unified training for Levenshtein transformer. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1–5.

Xin Zheng, Zhirui Zhang, Junliang Guo, Shujian Huang, Boxing Chen, Weihua Luo, and Jiajun Chen. 2021. Adaptive nearest neighbor machine translation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 368–374, Online. Association for Computational Linguistics.
Chunting Zhou, Jiatao Gu, and Graham Neubig.
2020. Understanding knowledge distillation in non-
autoregressive machine translation. In Proceedings
of the International Conference on Learning Repre-
sentations.

A Model Configuration

We use a Transformer architecture with embed-
dings of dimension 512; feed-forward layers of size
2048; number of heads 8; number of encoder and
decoder layers: 6; batch size: 3000 tokens; shared-
embeddings; dropout: 0.3; number of GPUs: 6.
The maximal number of additional placeholders is
Kmax = 64.

During training, we use Adam optimizer with (β₁, β₂)=(0.9, 0.98); inverse sqrt scheduler; learning rate: 5e⁻⁴; label smoothing: 0.1; warmup updates: 10,000; float precision: 16. We fixed the number of iterations at 60k. For decoding, we use iterative refinement with an empty placeholder penalty of 3, and a max number of iterations of 10 (Gu et al., 2019).

For the *n*-way alignment (§4.1), we use *k*=10.

The hyper-parameters of the realigner (§C) were
tuned on a subset of 1k samples extracted from the
ECB training set.

Metrics are used with default settings: Sacre-
BLEU signature is nrefs:1|case:mixed|eff:no
|tok:13a|smooth:exp|version:2.1.0; the
ChrF signature is nrefs:1|case:mixed|eff:yes
|nc:6|nw:0|space:no|version:2.1.0; as for
COMET we use the default model of version 1.1.3:
Unbabel/wmt22-comet-da.

B Data Analysis

Table 6 contains statistics about all 11 domains. They notably highlight the relationship between the average number of retrieved sentences during training and the ability of TM³-LeVT to perform better than TM¹-LeVT in Table 4. The domains with retrieval rates lesser than 1 (Epp, News, TED, Ubu) have quite a broad content, meaning that training instances have fewer close matches, which also means that for these domains, TM³-LeVT hardly sees two or three examples that it needs to use in inference.

C Realignment

The realignment process is an extra inference step
aiming to improve the result of the placeholder in-
sertion stage. To motivate our approach, let us con-

sider the following sentences before placeholder
insertion:

$$
\begin{align*}
\mathbf{y}_0^{\text{plh}}: & < \mathbf{A} \ \mathbf{B} \ \mathbf{C} \ > \times \\
\mathbf{y}_1^{\text{plh}}: & < \mathbf{B} \ \mathbf{C} \ > \times \\
\mathbf{y}_2^{\text{plh}}: & < \mathbf{A} \ \mathbf{D} \ \mathbf{C} \ \mathbf{D} >,
\end{align*}
$$

where letters represent tokens, × denotes padding,
< and > respectively stand for <BOS> and <EOS>.

The output of this stage is a prediction for all
pairs of consecutive tokens. This prediction takes
the form of a tensor log π<sub>θ</sub><sup>plh</sup> of dimensions N ×
(L−1)×(K<sub>max</sub>+1), corresponding respectively to
the number of retrieved sentences N, the maximum
sentence length L, and the maximum number of
additional placeholders K<sub>max</sub>.

Let $P$ (a $N \times (L-1)$ tensor) denote the arg max,

0 0 0 2 0

e.g. $P = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{pmatrix}$

0 1 0 0 0

Inserting the prescribed number of placehold-
ers (figured by _ ) then yields the following y<sup>cmb</sup>:

$$
\begin{align*}
\mathbf{y}_0^{\text{cmb}}: & < \mathbf{A} \ \mathbf{B} \ \mathbf{C} \ \_ \ \_ \ > \\
\mathbf{y}_1^{\text{cmb}}: & < \mathbf{B} \ \mathbf{C} \ \_ \ > \ \times \ \times \\
\mathbf{y}_2^{\text{cmb}}: & < \mathbf{A} \ \_ \ \mathbf{D} \ \mathbf{C} \ \mathbf{D} \ >
\end{align*}
$$

This result is far from perfect, as it fails to align
the repeated occurrences of *C*. For instance, a
preferable alignment requiring 3 changes (1 change
consists in a modification of ±1 in *P*) could be:

$$
\begin{align*}
\mathbf{y}_0^{\text{cmb'}}: & < \mathbf{A} \ \mathbf{B} \ \mathbf{C} \ \_ \ > \times \\
\mathbf{y}_1^{\text{cmb'}}: & < \_ \ \mathbf{B} \ \mathbf{C} \ \_ \ > \times \\
\mathbf{y}_2^{\text{cmb'}}: & < \mathbf{A} \ \mathbf{D} \ \mathbf{C} \ \mathbf{D} \ > \times
\end{align*}
$$

The general goal of realignment is to improve
such alignments by performing a small number
of changes in *P*. We formalize this problem as
a search for a good tradeoff between (a) the indi-
vidual placeholder prediction scores, aggregated
in $\mathcal{L}_L$ (likelihood loss) and (b) $\mathcal{L}_A$ an alignment
loss. Under its simplest form, this problem is again
an optimal multisequence alignment problem, for
which exact dynamic programming solutions are
computationally intractable in our setting.

We instead develop a continuous relaxation that
can be solved effectively with SGD and is also
easy to parallelize on GPUs. We, therefore, relax
the integer condition for *P* and assume that *P*<sub>*i*,*j*</sub>
can take continuous real values in [*0*, *K*<sub>*max*</sub>], then
solve the continuous optimization problem before
turning *P*<sub>*i*,*j*</sub> values back into integers.

The likelihood loss aims to keep the $P_{i,j}$ values
close to the model predictions. Denoting $(\mu, \sigma)$
respectively the mean and variance of the model
<table><caption>Table 6: Number of samples, average number of retrieved sentences and average length of sentences after tokenization for all 11 domains.</caption><thead><tr><th>domain</th><th>ECB</th><th>EME</th><th>Epp</th><th>GNO</th><th>JRC</th><th>KDE</th><th>News</th><th>PHP</th><th>TED</th><th>Ubu</th><th>Wiki</th><th>all</th></tr></thead><tbody><tr><td>size</td><td>195k</td><td>373k</td><td>2.0M</td><td>55k</td><td>503k</td><td>180k</td><td>151k</td><td>16k</td><td>159k</td><td>9k</td><td>803k</td><td>4.4M</td></tr><tr><td>retrieval rate</td><td>1.66</td><td>2.12</td><td>0.91</td><td>1.18</td><td>1.71</td><td>1.10</td><td>0.24</td><td>1.20</td><td>0.96</td><td>0.62</td><td>1.22</td><td>1.18</td></tr><tr><td>mean length</td><td>29.2</td><td>16.7</td><td>26.6</td><td>9.4</td><td>28.8</td><td>10.5</td><td>26.4</td><td>14.5</td><td>17.7</td><td>5.2</td><td>19.6</td><td>18.6</td></tr></tbody></table>

predictions, our initial version of this loss is

$$ \mathcal{L}_L(P) = \sum_{i,j} \frac{(P_{i,j} - \mu_{i,j})^2}{2\sigma^2}. $$

In practice, we found that using a weighted average $\hat{\mu}$ and clamping the variance $\hat{\sigma}^2$ both yield better realignments, yielding:

$$ \mathcal{L}_L(P) = \sum_{i,j} \frac{(P_{i,j} - \hat{\mu}_{i,j})^2}{2\hat{\sigma}^2} $$

To define the alignment loss, we introduce a position matrix $X$ of dimension $N \times L$ in $\mathbb{R}^+$, where $X_{n,i}$ corresponds to the (continuous) position of token $y_{n,i}$ after inserting a real number of placeholders. $X$ is defined as:

$$ X_{n,i}(P) = i + \sum_{j<i} P_{n,j} $$

with $i$ the number of tokens occurring before $X_{n,i}$ and $\sum_{j<i} P_{n,j}$ the cumulated sum of placeholders. Using $X$, we derive the distance tensor $D$ of dimension $N \times L \times N \times L$ in $\mathbb{R}^+$ as:

$$ D_{n,i,m,j}(P) = |X_{n,i} - X_{m,j}| $$

Finally, let $G$ be an $N \times L \times N \times L$ alignment graph tensor, where $G_{n,i,m,j} = 1$ if and only if $y_{n,i} = y_{m,j}$ and $n \neq m$ and $D_{n,i,m,j} < D_{max}$. $G$ connects identical tokens in different sentences when their distance after placeholder insertion is at most $D_{max}$. This last condition avoids perturbations from remote tokens that coincidentally appear to be identical.

Each token $y_{n,i}$ is associated with an individual loss:

$$ d_{n,i}(P) = \begin{cases} \min_{m,j} \{D_{n,i,m,j}(P) : G_{n,i,m,j} = 1\} & \text{if } \exists(m, j) \text{ s.t. } G_{n,i,m,j} = 1 \\ 0 & \text{otherwise.} \end{cases} $$

The alignment loss aggregates these values over sentences and positions as:

$$ \mathcal{L}_A(P) = \sum_{n=0}^{N-1} \sum_{i=0}^{L-1} d_{n,i}(P) $$

A final ingredient in our realignment model is related to the final discretization step. To avoid rounding errors, we further constrain the optimization process to deliver near-integer solutions. For this, we also include a *integer constraint loss* defined as:

$$ \mathcal{L}_{\text{int}}(P) = \mu_t \sum_{i,j} \sin^2(\pi P_{i,j}) $$

where $\mu_t$ controls the scale of $\mathcal{L}_{\text{int}}(P)$. As $x \to \sin^2(\pi x)$ reaches its minimum 0 for integer values, minimizing $\mathcal{L}_{\text{int}}(P)$ has the effect of enforcing a near-integer constraint to our solutions. Overall, we minimize in $P$:

$$ \mathcal{L} = \mathcal{L}_L(P) + \mathcal{L}_A(P) + \mathcal{L}_{\text{int}}(P), $$

slowly increasing the scale of $\mu_t$ according to the following schedule

$$ \mu_t = \begin{cases} 0 & \text{if } t < t_0 \\ \mu_T & \text{if } t > T \\ \mu_T \frac{(t-t_0)^2}{(T-t_0)^2} & \text{otherwise} \end{cases}, $$

with $t_0$, $T$ the timestamps for respectively the activation of the *integer constraint loss*, and the activation of the clamping. This optimization is performed with gradient descent directly on GPUs, with a small additional cost to the inference procedure.

## D NP-hardness of Coverage Maximization in N-way Alignment

Given the set of possible N-way alignments, the problem of finding the one that maximizes the target coverage is NP-hard. To prove it, we can reduce the NP-hard set cover problem (Garey and Johnson, 1979) to the N-way alignment coverage maximization problem.
* Cover set decision problem (A):

Let $X = \{x_1, \dots, x_N\}$ and $C_0 \subset 2^X$. Is there $c^* = (c_1, \dots, c_K) \in C_0^K$ s.t. $|\cup_k c_k^*| = |X|$?

* N-way alignment coverage maximization decision problem (B):

Let $X = \{x_1, \dots, x_N\}$ and $C = (C_1, \dots, C_K) \subset (2^X)^K$. For $p \in \mathbb{N}$, is there $c \in \prod_{k=1}^K C_k$ s.t. $|\cup_k c_k| \ge p$?

A solution of (B) can be certified in polynomial time: we simply compute the cardinal of a union. Any instance of (A) can be transformed in polynomial time and space into a special instance of (B) where all $C_k = C_0$ and $p = |X|$.

## E Results for fr-en

Table ?? reports the BLEU scores for the reverse direction (fr→en), using exactly the same configuration as in Table 2. Note that since we used the same data split (retrieving examples based on the similarity in English), and since the retrieval procedure is asymmetrical, 4,749 test samples happen to have no match. That would correspond to an extra column labeled "0", which is not represented here.

<table><caption>Table 7: BLEU scores on the full test set. TM³-LevT is improved with pre-training and realignment. All BLEU differences are significant ($p$ = 0.05). $p$-values from SacreBLEU paired bootstrap resampling ($n$ = 1000).</caption><thead><tr><th>Model \N</th><th>1</th><th>2</th><th>3</th><th>all</th></tr></thead><tbody><tr><td>size</td><td>2,753</td><td>1,675</td><td>12,823</td><td>17,251</td></tr><tr><td>TM<sup>1</sup>-LevT</td><td>57.2</td><td>57.6</td><td>61.5</td><td>60.2</td></tr><tr><td>TM<sup>3</sup>-LevT</td><td>58.2</td><td>59.4</td><td>64.0</td><td>62.4</td></tr><tr><td>+pt +ra</td><td></td><td></td><td></td><td></td></tr></tbody></table>

The reverse direction follows a similar pattern, providing further evidence of the method's effectiveness.

## F Complementary Analyses

**Diversity and difficulty** Results in Table 4 show that some datasets do not seem to benefit from multiple examples. This is notably the case for Europarl, News-Commentary, TED2013, and Ubuntu. We claim that this was due to the lack of retrieved examples at training (as stated in §B), of diversity, and the noise in fuzzy matches. To further investigate this issue, we report two scores in Table 8. The first is the increase of bag-of-word coverage

of the target gained by using $N=3$ instead of $N=1$; the second is the increase of noise in the examples, computed as the proportion of tokens in the examples that do not occur in the target. We observe that, in fact, low diversity is often associated with poor scores for TM³-LevT, and higher diversity with better performance.

<table><caption>Table 8: Coverage and noise scores increase. "Difficulty" is highlighted in bold (< 8.0 for cover; > 6.0 for noise).</caption><thead><tr><th rowspan="2"></th><th colspan="2">cover</th><th colspan="2">noise</th></tr><tr><th>test-0.4</th><th>test-0.6</th><th>test-0.4</th><th>test-0.6</th></tr></thead><tbody><tr><td>ECB</td><td>+8.2</td><td>+8.9</td><td>+3.7</td><td>+4.4</td></tr><tr><td>EME</td><td>+8.9</td><td>+8.5</td><td>+4.0</td><td>+5.0</td></tr><tr><td>Epp</td><td>+10.5</td><td>+13.7</td><td>+2.2</td><td>+4.0</td></tr><tr><td>GNO</td><td><strong>+7.1</strong></td><td><strong>+6.2</strong></td><td><strong>+7.6</strong></td><td><strong>+9.3</strong></td></tr><tr><td>JRC</td><td><strong>+7.2</strong></td><td><strong>+6.8</strong></td><td>+4.8</td><td>+5.2</td></tr><tr><td>KDE</td><td>+8.0</td><td><strong>+7.5</strong></td><td><strong>+6.9</strong></td><td><strong>+7.8</strong></td></tr><tr><td>News</td><td><strong>+7.2</strong></td><td>+12.5</td><td>+2.3</td><td>+5.0</td></tr><tr><td>PHP</td><td><strong>+7.2</strong></td><td><strong>+7.6</strong></td><td>+4.2</td><td>+5.4</td></tr><tr><td>TED</td><td>+9.4</td><td>+11.4</td><td>+2.9</td><td>+4.6</td></tr><tr><td>Ubu</td><td><strong>+5.5</strong></td><td><strong>+6.0</strong></td><td><strong>+6.7</strong></td><td><strong>+8.6</strong></td></tr><tr><td>Wiki</td><td>+8.0</td><td>+8.0</td><td>+2.5</td><td>+3.6</td></tr><tr><td>all</td><td>+8.1</td><td>+8.9</td><td>+4.4</td><td>+5.7</td></tr></tbody></table>

**Long run** All results in the main text were obtained with models trained for 60k iterations, which was enough to compare the various models while saving computation resources. For completeness, we also performed one longer training for 300k iterations for TM³-LevT (see Table 9), which resulted in an improvement of around +2 BLEU for each test set. This is without realignment nor pretraining.

<table><caption>Table 9: BLEU score of TM³-LevT: 60k iterations; and TM³-LevT long: 300k iterations.</caption><thead><tr><th>model</th><th>test-0.4</th><th>test-0.6</th></tr></thead><tbody><tr><td>TM³-LevT</td><td>46.5</td><td>60.0</td></tr><tr><td>+ realign</td><td>46.7</td><td>60.2</td></tr><tr><td>TM³-LevT long</td><td>48.7</td><td>61.9</td></tr><tr><td>+ realign</td><td><strong>48.9</strong></td><td><strong>62.0</strong></td></tr></tbody></table>

**The Benefits of realignment** Table 10 shows that realignment also decreases the average number of refinement steps to converge. These results suggest that the edition is made easier with realignment.

In Table 11, we present detailed results of the unigram modified precision of LevT, TM³-LevT and
<table><caption>Table 10: Average number of extra refinement rounds.</caption><thead><tr><th>model</th><th>test-0.4</th><th>test-0.6</th></tr></thead><tbody><tr><td>TM<sup>3</sup>-LevT</td><td>3.55</td><td>2.07</td></tr><tr><td>+realign</td><td><strong>3.37</strong></td><td><strong>1.93</strong></td></tr></tbody></table>

TM³-LevT+realign. Using more examples indeed increases copy (+4.4), even though it diminishes copy precision (-1.7). Again we observe the positive effect of realignment, which amplifies the tendency of our model to copy input tokens.

<table><caption>Table 11: Modified precision of copy vs. generated unigrams of LevT vs. TM³-LevT.</caption><thead><tr><th>model</th><th></th><th>precision</th><th>% units</th></tr></thead><tbody><tr><td rowspan="2">TM-LevT</td><td>copy</td><td><strong>87.5</strong></td><td>64.9</td></tr><tr><td>gen</td><td>52.6</td><td>35.1</td></tr><tr><td rowspan="2">TM³-LevT</td><td>copy</td><td>85.4</td><td>68.8</td></tr><tr><td>gen</td><td>54.9</td><td>31.2</td></tr><tr><td rowspan="2">+realign</td><td>copy</td><td>85.8</td><td><strong>69.3</strong></td></tr><tr><td>gen</td><td>54.7</td><td>30.7</td></tr></tbody></table>

**COMET scores** We compute COMET scores (Rei et al., 2020) separately for each domain with default wmt20-comet-da similarly to Table 4 (see Table 12). We observe that the basic version of TM³-LevT underperforms TM¹-LevT; we also see a great variation in the scores. A possible explanation can be a fluency decline when using multiple examples, which is not represented by the precision scores computed by BLEU. The improved version, using realignment and pre-training, confirms that adding more matches is overall beneficial for MT quality.

**Per-domain ablation study** Table 13 details the results of our ablation study separately for each domain.

**Illustration** A full inference run is in Table 14, illustrating the benefits of considering multiple examples and realignment. Even though the realignment does not change here the final output, it reduces the number of atomic edits needed to generate it, making the inference more robust.
<table><caption>Table 12: Per domain COMET scores (x 100) for TM<sup>n</sup>-LevT and variants. Bold for scores better than TM<sup>1</sup>-LevT.</caption><thead><tr><th></th><th></th><th>ECB</th><th>EME</th><th>Epp</th><th>GNO</th><th>JRC</th><th>KDE</th><th>News</th><th>PHP</th><th>TED</th><th>Ubu</th><th>Wiki</th><th>all</th></tr></thead><tbody><tr><td rowspan="5">test-0.4</td><td>TM<sup>1</sup>-LevT</td><td>33.0</td><td>43.1</td><td>39.9</td><td>56.3</td><td>70.7</td><td>37.4</td><td>-2.0</td><td>-39.6</td><td>-0.8</td><td>41.6</td><td>-9.9</td><td>24.5</td></tr><tr><td>TM<sup>2</sup>-LevT</td><td>27.2</td><td>42.0</td><td>31.1</td><td>48.0</td><td>64.4</td><td>32.6</td><td>-10.8</td><td>-42.7</td><td>-8.7</td><td>35.3</td><td>-15.7</td><td>18.4</td></tr><tr><td>TM<sup>3</sup>-LevT</td><td>27.3</td><td>42.1</td><td>26.8</td><td>51.5</td><td>64.2</td><td>33.5</td><td>-10.1</td><td>-39.9</td><td>-14.8</td><td>38.6</td><td>-16.3</td><td>18.4</td></tr><tr><td>+pre-train</td><td>30.6</td><td><strong>44.7</strong></td><td>38.7</td><td><strong>57.9</strong></td><td>67.8</td><td><strong>37.9</strong></td><td>-6.2</td><td><strong>-35.3</strong></td><td><strong>2.7</strong></td><td>41.5</td><td><strong>-5.0</strong></td><td><strong>25.0</strong></td></tr><tr><td>+realign</td><td>31.0</td><td><strong>45.1</strong></td><td>32.0</td><td>53.2</td><td>66.4</td><td>34.9</td><td>-10.9</td><td>-39.0</td><td>-11.9</td><td>41.1</td><td>-10.8</td><td>21.0</td></tr><tr><td></td><td>+both</td><td><strong>33.7</strong></td><td><strong>46.4</strong></td><td><strong>42.4</strong></td><td><strong>59.9</strong></td><td><strong>69.9</strong></td><td><strong>40.1</strong></td><td><strong>-1.0</strong></td><td><strong>-33.0</strong></td><td><strong>5.1</strong></td><td><strong>43.5</strong></td><td><strong>-3.7</strong></td><td><strong>27.5</strong></td></tr><tr><td rowspan="5">test-0.6</td><td>TM<sup>1</sup>-LevT</td><td>51.7</td><td>53.9</td><td>56.9</td><td>65.3</td><td>85.4</td><td>37.0</td><td>-3.0</td><td>-17.0</td><td>48.5</td><td>57.6</td><td>64.5</td><td>45.5</td></tr><tr><td>TM<sup>2</sup>-LevT</td><td>51.2</td><td><strong>54.2</strong></td><td>56.3</td><td>64.2</td><td>82.5</td><td>34.6</td><td>-9.0</td><td><strong>-15.9</strong></td><td>46.1</td><td>55.5</td><td>61.6</td><td>43.7</td></tr><tr><td>TM<sup>3</sup>-LevT</td><td>50.9</td><td><strong>55.8</strong></td><td>54.1</td><td>65.1</td><td>81.1</td><td>33.6</td><td>-9.8</td><td><strong>-16.2</strong></td><td>41.1</td><td>57.4</td><td>61.7</td><td>43.1</td></tr><tr><td>+pre-train</td><td><strong>54.6</strong></td><td><strong>56.5</strong></td><td><strong>58.0</strong></td><td><strong>68.2</strong></td><td>84.7</td><td><strong>41.5</strong></td><td>-4.3</td><td><strong>-11.8</strong></td><td><strong>48.9</strong></td><td><strong>62.7</strong></td><td><strong>65.6</strong></td><td><strong>47.7</strong></td></tr><tr><td>+realign</td><td><strong>53.0</strong></td><td><strong>56.4</strong></td><td>56.3</td><td>65.4</td><td>83.6</td><td>34.3</td><td>-7.2</td><td><strong>-16.1</strong></td><td>42.8</td><td><strong>58.3</strong></td><td>63.7</td><td>44.6</td></tr><tr><td></td><td>+both</td><td><strong>55.7</strong></td><td><strong>57.4</strong></td><td><strong>58.8</strong></td><td><strong>70.5</strong></td><td><strong>85.8</strong></td><td><strong>43.2</strong></td><td>-4.4</td><td><strong>-10.6</strong></td><td><strong>49.4</strong></td><td><strong>62.3</strong></td><td><strong>67.7</strong></td><td><strong>48.7</strong></td></tr></tbody></table>

<table><caption>Table 13: Ablation study. We report BLEU scores for various settings. -sel: no random selection noise (γ=0); -delx: no extra deletion loss; -rd-del: no random deletion (β=0); -mask: no random mask (δ=0); -dum-plh: null probability to start with y<sub>post-del</sub>=y<sub>*</sub> (α = 0); -indep-align: the alignments are performed independently.</caption><thead><tr><th></th><th></th><th>ECB</th><th>EME</th><th>Epp</th><th>GNO</th><th>JRC</th><th>KDE</th><th>News</th><th>PHP</th><th>TED</th><th>Ubu</th><th>Wiki</th><th>all</th></tr></thead><tbody><tr><td rowspan="7">test-0.4</td><td>TM<sup>3</sup>-LevT</td><td>53.9</td><td><strong>55.6</strong></td><td><strong>34.2</strong></td><td>60.7</td><td><strong>66.0</strong></td><td><strong>53.5</strong></td><td><strong>20.4</strong></td><td>33.0</td><td><strong>28.6</strong></td><td>47.5</td><td><strong>32.8</strong></td><td><strong>46.5</strong></td></tr><tr><td>-sel</td><td><strong>54.5</strong></td><td><strong>55.6</strong></td><td>32.7</td><td><strong>61.2</strong></td><td>65.9</td><td>52.2</td><td>19.5</td><td><strong>33.3</strong></td><td>27.7</td><td><strong>48.1</strong></td><td>31.3</td><td>46.2</td></tr><tr><td>-delx</td><td>52.2</td><td>53.4</td><td>31.8</td><td>58.7</td><td>64.0</td><td>52.0</td><td>19.6</td><td>31.2</td><td>27.5</td><td>46.8</td><td>31.5</td><td>44.8</td></tr><tr><td>-rd-del</td><td>49.7</td><td>47.6</td><td>22.2</td><td>48.2</td><td>56.7</td><td>38.8</td><td>13.2</td><td>29.5</td><td>16.9</td><td>32.2</td><td>21.4</td><td>38.6</td></tr><tr><td>-mask</td><td>53.4</td><td>54.7</td><td>33.7</td><td>58.9</td><td>65.3</td><td>52.4</td><td>20.3</td><td>33.1</td><td>27.5</td><td>47.1</td><td>32.2</td><td>46.0</td></tr><tr><td>-dum-plh</td><td>50.8</td><td>43.3</td><td>32.7</td><td>45.6</td><td>61.2</td><td>42.4</td><td>21.0</td><td>30.9</td><td>24.3</td><td>35.6</td><td>28.2</td><td>41.0</td></tr><tr><td>-indep-align</td><td>51.5</td><td>52.4</td><td>29.7</td><td>53.8</td><td>60.7</td><td>47.2</td><td>16.9</td><td>30.4</td><td>21.8</td><td>39.0</td><td>28.4</td><td>42.6</td></tr><tr><td rowspan="7">test-0.6</td><td>TM<sup>3</sup>-LevT</td><td><strong>64.2</strong></td><td><strong>68.0</strong></td><td>49.4</td><td><strong>73.0</strong></td><td><strong>76.4</strong></td><td><strong>60.1</strong></td><td>21.2</td><td><strong>39.6</strong></td><td>52.2</td><td><strong>60.1</strong></td><td>61.6</td><td><strong>60.1</strong></td></tr><tr><td>-sel</td><td>63.8</td><td>67.5</td><td><strong>50.0</strong></td><td>71.2</td><td>76.3</td><td>60.0</td><td><strong>21.5</strong></td><td>39.1</td><td><strong>54.2</strong></td><td>59.7</td><td><strong>62.2</strong></td><td>60.0</td></tr><tr><td>-delx</td><td>62.1</td><td>66.7</td><td>47.7</td><td>70.6</td><td>75.0</td><td>58.8</td><td>20.1</td><td>37.9</td><td>53.5</td><td>58.4</td><td>60.9</td><td>58.6</td></tr><tr><td>-rd-del</td><td>58.4</td><td>59.6</td><td>39.7</td><td>59.0</td><td>67.6</td><td>47.7</td><td>16.9</td><td>35.0</td><td>39.8</td><td>44.1</td><td>47.4</td><td>51.9</td></tr><tr><td>-mask</td><td>63.1</td><td>65.3</td><td>49.1</td><td>69.4</td><td>74.2</td><td>58.2</td><td>21.8</td><td>38.6</td><td>50.9</td><td>58.7</td><td>59.7</td><td>59.0</td></tr><tr><td>-dum-plh</td><td>57.3</td><td>55.5</td><td>44.9</td><td>51.8</td><td>68.5</td><td>44.5</td><td>20.2</td><td>35.7</td><td>42.6</td><td>38.7</td><td>50.7</td><td>50.9</td></tr><tr><td>-indep-align</td><td>60.6</td><td>64.0</td><td>46.6</td><td>64.3</td><td>71.9</td><td>55.5</td><td>18.6</td><td>35.6</td><td>44.6</td><td>51.6</td><td>56.0</td><td>56.4</td></tr></tbody></table>
<table><caption>Table 14: Examples of full inference of several models on a test sample from test-0.4-PHP (sample n°571). Copied parts are in red.</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>src:</td><td>The swf _ setfont () sets the current font to the value given by the fontid parameter.</td></tr><tr><td>tgt:</td><td>swf _ setfont () replace la police courante par la police repérée par l' identifiant fontid.</td></tr><tr><td colspan="2">LevT</td></tr><tr><td>y<sup>del</sup>:</td><td>swo f _ fon to size () remplace la taille de la police par la taille size.</td></tr><tr><td>y<sup>plh</sup>:</td><td>swo f _ +2 () remplace la +1 de police +1 par la +5.</td></tr><tr><td>y<sup>tok</sup>:</td><td>swo f _ set police () remplace la police de police courante par la valeur de paramètre ti d.</td></tr><tr><td>y<sup>del</sup>:</td><td>swo f _ set police () remplace la police de police courante par la valeur de paramètre ti d.</td></tr><tr><td>y<sup>plh</sup>:</td><td>+1 swo f _ set police () remplace la police de police courante +1 par la valeur de paramètre +1 ti d.</td></tr><tr><td>y<sup>tok</sup>:</td><td>Le swo f _ set police () remplace la police de police courante donnée par la valeur de paramètre fon ti d.</td></tr><tr><td>hyp:</td><td>Le swf _ setpolice () replace la police de police courante donnée par la valeur de paramètre fontid.</td></tr><tr><td colspan="2">TM<sup>2</sup>-LevT</td></tr><tr><td>y<sup>del</sup>:</td><td>swo f _ fon to size () remplace la taille de la police par la taille size.<br>swo f _ defin e font () définit la police fon to name et lui affecte l' identi fiant fon ti d.</td></tr><tr><td>y<sup>plh</sup>:</td><td>swo f _ +2 () remplace la police +6 par +4.<br>swo f _ +1 font () définit la police +9 fon ti d.</td></tr><tr><td>y<sup>cmb</sup>:</td><td>swo f _ () remplace la police par :<br>swo f _ font () définit la police fon ti d.</td></tr><tr><td>y<sup>tok</sup>:</td><td>swo f _ set font () remplace la police actuelle à la valeur donnée par le paramètre fon ti d.</td></tr><tr><td>y<sup>del</sup>:</td><td>swo f _ set font () remplace la police actuelle à la valeur donnée par le paramètre fon ti d.</td></tr><tr><td>y<sup>plh</sup>:</td><td>swo f _ set font () remplace la police actuelle +1 la valeur donnée par le paramètre fon ti d.</td></tr><tr><td>y<sup>tok</sup>:</td><td>swo f _ set font () remplace la police actuelle à la valeur donnée par le paramètre fon ti d.</td></tr><tr><td>hyp:</td><td>swf _ setfont () replace la police actuelle à la valeur donnée par le paramètre fontid.</td></tr><tr><td colspan="2">TM<sup>3</sup>-LevT</td></tr><tr><td>y<sup>del</sup>:</td><td>swo f _ fon to size () rempo place la taille de la police par la taille size.<br>swo f _ defin e font () définit la police fon to name et lui affecte l' identi fiant fon ti d.</td></tr><tr><td>y<sup>plh</sup>:</td><td>swo f _ text seto font () remplace la police courante par font.<br>swo f _ +2 () remplace la police +4 par +5.<br>swo f _ +1 font () définit la police +7 ti d.<br>swo +2 seto font () remplace la police courante +4 par +5.</td></tr><tr><td>y<sup>cmb</sup>:</td><td>swo f _ () remplace la police par :<br>swo f _ font () définit la police fon ti d.<br>swo seto font () remplace la police courante par :<br>swo seto font () remplace la police courante au valeur donnée par le paramètre fon ti d...</td></tr><tr><td>y<sup>tok</sup>:</td><td>swo f _ seto font () remplace la police courante au valeur donnée par le paramètre fon ti d...</td></tr><tr><td>y<sup>del</sup>:</td><td>swo f _ seto font () remplace la police courante au valeur donnée par le paramètre fon ti d.</td></tr><tr><td>y<sup>plh</sup>:</td><td>+1 swo f _ seto font () remplace la police courante +2 valeur +1 par le +1 fon ti d.</td></tr><tr><td>y<sup>tok</sup>:</td><td>Le swo f _ seto font () remplace la police courante à la valeur donnée par le paramètre fon ti d.</td></tr><tr><td>hyp:</td><td>Le swf _ setfont () replace la police courante à la valeur donnée par le paramètre fontid.</td></tr><tr><td colspan="2">TM<sup>3</sup>-LevT + realign</td></tr><tr><td>y<sup>del</sup>:</td><td>swo f _ fon to size () rempo place la taille de la police par la taille size.<br>swo f _ defin e font () définit la police fon to name et lui affecte l' identi fiant fon ti d.</td></tr><tr><td>y<sup>plh</sup>:</td><td>swo f _ text seto font () remplace la police courante par font.<br>swo f _ +2 () remplace la police +4 par +5.<br>swo f _ +1 font () définit la police +8 ti d.<br>swo +2 seto font () remplace la police courante +3 par +5.</td></tr><tr><td>y<sup>cmb</sup>:</td><td>swo f _ () remplace la police par :<br>swo f _ font () définit la police fon ti d.<br>swo seto font () remplace la police courante par :<br>swo seto font () remplace la police courante au valeur donnée par le paramètre fon ti d.</td></tr><tr><td>y<sup>tok</sup>:</td><td>swo f _ seto font () remplace la police courante au valeur donnée par le paramètre fon ti d.</td></tr><tr><td>y<sup>del</sup>:</td><td>swo f _ seto font () remplace la police courante au valeur donnée par le paramètre fon ti d.</td></tr><tr><td>y<sup>plh</sup>:</td><td>+1 swo f _ seto font () remplace la police courante +2 valeur donnée par le paramètre fon ti d.</td></tr><tr><td>y<sup>tok</sup>:</td><td>Le swo f _ seto font () remplace la police courante à la valeur donnée par le paramètre fon ti d.</td></tr><tr><td>hyp:</td><td>Le swf _ setfont () replace la police courante à la valeur donnée par le paramètre fontid.</td></tr></tbody></table>