Towards Example-Based NMT with Multi-Levenshtein Transformers
Authors: Maxime Bouthors
Josep Crego
François Yvon
Venue: EMNLP 2023 Main (2023)
Keywords: Neural Machine Translation
Non Autoregressive Transformers
Levenshtein Transformer
Translation Memory
Computer Assisted Translation
TL;DR: We extend Non Autoregressive Machine Translation to simultaneously edit multiple fuzzy matches from Translation Memory.

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.

Towards Example-Based NMT with Multi-Levenshtein Transformers
Maxime Bouthors
Josep Crego and François Yvon
O SSrbonnee Université, CNRS, ISIR F-75005 Paris, France firstname lastname@isir upmc. fr Systran 5 rue Feydeau, F-75002 Paris, France firstname las taaaeesysttanggroup
Abstract
precision
% units
unigram
copy
87.5
64.9
Retrieval-Augmenned Machine Translation (RAMT) is attracting growing attention. This is because RAMT not only improves transla- tion metrics, but is also assumed to implement form of domain adaptation. In this contri- bution, we study another salient trait of RAMT, its ability to make translation decisions more transparent by allowing users go back to amples that contributed to these decisions. For this, we propose novel architecture aiming to increase this transparency. This model adapts serreval-augmentee version of the Levenshtein Transformer and makes it amenable to simulta- neously edit multiple fuzzy matches found in memory. We discuss how to perform training and inference this model, based multi- way alignment algorithms and imitation learn- ing. Our experiments show that editing several examples positively impacts translation scores, notably increasing the number of target spans that are copied from existing instances.
gen
52.6
35.1
bigram copy-copy
81.4
55.0
copy-gen
40.1
8.9
gen-copy 39.5
10.7
gen-gen
34.2
25.4
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.
sentences, such as the Levenshtein Transformer (LevT) model of Gu et al. (2019). This model can effectively fuzzy matches retrieved from memories, performing minimal edits wherever nec- essary. 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 cxisting translation ex- amples 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 in- spect the edit operations that were performed. To evaluate claim (a) we translate our test data (details in Section 5.1) using basic implementation of a vetrieval-augmmnnte LevT with TM (TM-LevT). We separately compute the modified unigram and bi- gram precisions (Papineni et al., 2002) for tokens that are copied from the fuzzy match and tokens that are generated by the model.' We observe that copies account for the largest share of output units and have better precision (see Table 1).
1 Introduction
Neural Machine Translation (NMT) has become increasingly efficient and effective thanks to the development of ever larger encoder-decoder archi- tectures relying Transformer models (Vaswani et al., 2017). Furthermore, these architectures can readily integrate instances retrieved from Trans- lation Memory (TM) (Bulte and Tezcan, 2019; Xu al., 2020; Hoang al., 2022), thereby improving the overall consistency of new translations com- pared to past ones. In such context, the autoregres- sive 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, there is guar- antee that the output translation, regenerated from scratch, will resemble that of similar texts.
Based this observation, our primary goal is optimize further the number of tokens copied from the TM. To do so, we propose simultaneously edit- ing multiple fuzzy matches retrieved from memory, using computational architecture Multi-LevT,
An alternative that is attracting growing attention is to rely on computational models tailored to edit existing examples and adapt them to new source
'Copies and generations are directly infered from the se- quence of edit operations used to compute the output sentence.

---

-Lev for short which extends TM-LevT handle several initial translations. The benefit is twofold: (a) an increase in translation accuracy; (b) more transparency in the translation process. Ex- tending TM-LevT to TM"=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 notori- ously difficult problem; and designing appropriate training procedures for this alignment module. Our main contributions are the following:
tools. Here, we instead explore ways to perform this step automatically, as in Example-Base 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 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 match from 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 obtained.
1. new variant of the LevT model that explicitly maximizes target coverage ($4.2);
2. 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;
In LevT, these predictions rely joint encod- ing of the source and the current target and apply in parallel for all positions, which makes LevT rep- resentative of non-autoregressive translation (NAT) models. As editing operations are not observed 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 repositioning operation and uses it decode with terminoloyy constraints, as well as the studies of Niwa et al. (2022) and Xu al. (2023) who also explore the use of LevT in conjunction with TMs.
4. experiments in 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.?
2
Preliminaries / Background
2.1 TM-based machine translation
Translation Memories, storing examples of past translations, is primary component of profes- sional Computer Assisted Translation (CAT) en- vironments (Bowker, 2002). Given translation request for source sentence TM-based transla- tion two-step process: (a) retrieval of one or several instances (x, y) whose source side resem- bles x, (b) adaptation of retrieved example(s) to produce a translation. this work, we mainly fo- cus on step (b), and assume that the retrieval part is
The cat sits on the mat
sits the mat token prediction The cat on 20
TM-LevT
placehoder insertion
based on fixed similarity measure A between x
Le chat est tspis.
The cat on
and stored examples. In our experiments, we use:
deletion
ED x) A(x, x) max x {
The cat sleeps bed.
(1)
Figure 1: First decoding pass of TM-LevT, variant of LevT augmented with Translation Memories.
with ED(x, x) the edit distance between x and x and |x] the length of x. We only consider TM matches for which A exceeds a predefined thresh- old r and filter out the remaining ones. The next step, adaptation, is performed by humans with CAT
2.3 Processing multiple fuzzy matches
One of the core differences between T- and LevT is its ability to handle multiple matches. This
Phttps: http://ggghuuuuomaarrrree www//awwe /

---

ture, extended with additional embedding and lin- ear layers (see Figure 2) to accommodate multi- ple matches. In each of the retrieved instances y - (y1, .NN,, Vn,i (the 7t token in the 1h instance) is encoded as Fry.. + P + Sn, where E E [[Vixddddel P E IL (gLmmexxdmode Xdmoddl and S [[N-1)xdmoddd are respectively the token, position and sequence embeddings. The sequence embed- ding identifies TM matches, and the positional en- codings are reset for each yn- The extra row in $ is used to identify the results of the combination and will yield different representation for these sin- gle sequences. 3 Once embedded, TM matches are concatenated and passed through multiple Trans- former blocks, until reaching the last layer, which outputs (h,, hly)) for a single input match or (h1,1.-. ... ,yl."" IN..1. JNN, ywl) in the case multiple ones. The learned policy To com- putes its decisions from these hidden states. We use four classifiers, one for each sub-policy:
toob
Lingar Selimax
Sulimse
Sollows
Sotimex
x. Cross Attention
Encoder
Decoder
X Self Attention
Self Attention
Positionl Encoding
SSequiince [Enooding
Source
TM examples
Figure 2: A high-level overview of TM -LevT's archi- tecture.
Additions w.r.t. TM-LevT are in a dashed box.
implies adapting the edit steps (in inference) and the roll-in policy (in imitation lcarning).
Inference in TM -LeVT Decoding follows the same key ideas as for LevT (see Figure 1) but en- ables co-editing an arbitrary number N of sen- tences. Our implementation (1) applies deletion, then placeholder insertion simultaneously on each retrieved example; (2) combines position-wise all examples into single candidate sentence; (3) performs additional steps in LevT: this includes first completing token prediction, then performing Iterative Refinement operations that edit the sen- tence to correct mistakes and improve it ($3.2).
deletion: predicts keep or delete for each token y ydlel with a projection matrix A E IR 2x2d 2xdddmodd
del (d|n, iyd ;N:x) x) softmax (Am,sT
2. insertion: predicts the number of placeholder insertions between wh and plh nni+1 with pro- jection matrix B E Te (Kmax 1)x2dmod:;
Training in -LeVT -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 gener- ate the reference output, based on the step-by bee-bby-tepp reproduction of what an expert 'teacher' would do. For this, need 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).
pih ip yIth
plh . ;x)
T
softmax (lhagi bnst1) B²),
with Kmaz the max number of insertions.
3. combination: predicts if token yomb in se- quence n must be kept in the combination, with projection matrix C E 2xddodii;;
(c|n, yfmb softmax C
YN x)
4. prediction: predicts token in vocabulary y at each placeholder position, with projection matrix D R [xxdmoddi
3
Multi-Levenshtein Transformer
3.1 Global architecture
-LevT has two modes of operations: (a) the combination of multiple TM matches into one sin- gle sequence through alignment, (b) the iterative refinement of the resulting sequence. In step (a), we use the Transformer mecoder-decoder architec-
tok (t|n, i, tok; x) softmax (h, T
Except for step 3, these classifiers are similar to those used the original LevT.

---

The cat sits on the nat First, from the initial set of sentences yimit, the unrolling of TT produces intermedi- ate states (ydel, del"), (y plh"), (y .mb"). (y'ok, tok") (see top left in Figure 4). Moreover, in this framework, is critical to mitigate the ex- posure bias and generate states that result from non-optimal past decisions (Zheng et al., 2023). For each training sample y1, .YN: we simulate multiple additional states follows (see Figure 4 for the full picture). We begin with the operations involved in the first decoding pass:*
token prediciton
mbb
2i13 nat combination The on the nat
1010110 10
The
Insertion
16
00101 01
The cat +1 on yell
020000 %
The -2 on the nat
deletion
001 1
The cat steeps on a bed The dog-2o the green
01100100
Figure 3: The first decoding pass TM -LevT.
1. Additional tripletsi: ruud-del-N turns y. into N random substrings, which simulates the edition of N artificial examples.
3.2 Decoding
Decoding is an iterative process: in first pass, the N fuzzy matches are combined to compute candidate translation; then, as in LevT, an ad- ditional series of iterative refinement rounds (Gu al., 2019) is applied until convergence or time- out. Figure 3 illustrates the first pass, where N = matches are first edited in paraliel, then combined into one output.
2. Token selection" (uses π: >= our expert pol- icy never aligns two distinct tokens at given position ($4.3). We simulate such cases that may occur at inference, as follows: with prob- ability 7, each <PLH> is replaced with ran- dom 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 roll-in and roll-out policies used in LevT and its variants (Gu et al., 2019; Xu et al., 2023; Zheng et al., 2023):
To predict deletions (resp. insertions and token predictions), we apply the argmax operator to ng del (resp. T .. For combinations, we need to aggregate separate decisions ngmb (one per token and match) into one sequence. For this, at each position, we pick the most likely token.
3. Add missing words (uses x r probability a, poost-pth-y... With probability
); with
During iterative refinement, we bias the model towards generating longer sentences since LevT outputs tend to be too short (Gu al.. 2019). As the probability of
1 a, generate subsequence posst-plh with length sampled uniformly in [y.]]]
in LevT, we add a penalty inserting placeholder in mith (Stern et al., 2019). This only applies in the refinement steps to avoid creating more misalignments (see $6.2).
4. Correct mistakes (uses maak): using the out- put of token prediction des teach the model erase the wrongly predicted tokens.
3.3 Imitation learning
5. Remove extra tokens" sert placeholders in post-tok and predict to- kens, yielding poost-del-eatte which trains the model delete wrong tokens. These quences differ from case (4) in the way <PLH> are inserted.
(uses T
" iins =f00):: ) in-
We train -LevT with Imitation Learning (Daumé et al., 2009; Ross et al., 1), 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 sim- ulate decoding states via a roll-in policy; for each of these, the optimal decision is computed via an expert policy T. composed of intermediate experts ndel me Tmmb, - The notion of optimality is discussed in $4. Samples of pairs (state, decision)
6. Predict token' (uses rnd-mskky each token in y is replaced by <PLH> with probability e. As token prediction applies for both decoding steps, these states also improve the first pass.
are then used to train the system policy Tg-
The expert decisions (c.g. inserting deleted to- kens like in state (3) or deleting wrongly predicted
" denotes an intermediary sequence before applying edit operation op. y E 14 is encoded with S.;; o e N with Sx.
"Families of (state, decision) pairs that are novel with respect to TM-LevT are marked with

---

your jdet" youh both" youk lembl" y tta fook"
yobril
des Hasl"
del
youh bulh'
m
plh
y del ide!"
jomb"
arih
/cmbb"
omub
post del
ded NV yoth folts"
y tok hold
y.
yomb lemb" y Lok book
B
y
Lok
/sok
Lok
y pood del
post
Loak "ook"
sT 7nd-mas
y.
apety
post -ph
post Aok
post del extra
yo
post pih
Bob
post del extra'
Roll-in policies used training. Blue cells contain sets of target sentences (e.g. ydel), optionally associated with the expert prediction (e.g. del"). Model's predictions are Thistle and circumflexed (e.g. del). Pairs of model/ / expert predictions are summed in the loss: (del, ), (pth, plh"), ) (emb, cmb*), (post del, post del"), (post plh, post most.plh")) plh"), (post del extra, post plh- exxta")t)" "post" denotes policies applied in refinement steps.
Figure 4:
y Intt
cmb
in Vn node j in V.. An N-way alignment satisfies properties (i)-(ii::
The cat sits on bed.
dog the floor
bed
floor
on the mat
(i) Edges connect identical (matching) tokens: (n,i,j) E = Yn,i Yaj-
Figure 5: Noising yamb with x using tokens from initt (y1. .Nx).
(ii) Edges that are incident to the same subset Vn, do not cross:
tokens in state (4)) associated with most states are obvious, except for the initial state and state (5), which require an optimal alignment computation.
(n, (n, 1l ,' E (8' 1--00'11 5) 0.
An optimal N-way alignment E, maximizes the coverage of tokens in y.. then the total number of edges, where Yaj is covered if there exists at least one edge (n, 4, E E. Denoting E the set of alignments maximizing target coverage:
4 Optimal Alignment
Training the combination operation introduced above requires specifying the expert decision for each state. While LevT derives its expert policy m from the computation of edit distances, we intro- duce another formulation based on the computation maximal covers. For N=1, these formulations can be made equivalent (Gusfield, 1997).
E = arg max
(y+ En, i), (,, E EH.
E
E. arg max EE REB
4.2 Solving optimal alignment
4.1 N-way alignments
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 complexity O(Nly, II, lynl). We instead implemented the following two-step heuristic approach:
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 (y1,.... .x) and the target sentence ys, N-way alignment of (y1,..., .Yn) w.r.t. y. is represented as a bipartite graph V., E), where V is further partitioned into N mutually disjoint subsets Vi... Vv. Ver- tices in each Vn (resp. V,,) correspond tokens in Yn (resp. y.). Edges (n, i, E connect node
separately compute alignment graphs between each yn and y., then extract k-best 1-way alignments {En,1 ... En,a)- This requires time O llyl)))) using DP (Gusfield, 1997);
*When the cost of replace is higher than insertion deletion. This is the case in the original LevT code.

---

y+
the cat sits on the mat cveerage 67%
the cat sits the mat contragn 100%
the cat sits on it Y1
it's on the mat where the pat sits on y2
the cat sits 31 coverage 67%
it's the mat where the cat sits coverage
oveerage 67%
oneeruge 67%
(a) Combination the optimal 1-way alignments.
(b) Optimal 2-way alignment.
Figure 6: Illustration of the optimal N-way alignment which maximizes global coverage criterion (6b), while independent alignments do not guarantee optimal usage of information present in TM examples (6a).
2. search for the optimal recombination of these graphs, selecting 1-way alignments (ELA) ... .......... EN form E. Un En Assuming N and & are small, we perform an exhaustive search in O...).
ECB, EMEA, Europarl, GNOME, JRC-Acquis, KDE4, PHP, Ubuntu, where high-quality matches are often available, but also News- 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,, to keep only those with A(x, x,) > 0.4. We then manually split each of the 11 datasets into train, valid, lest-0.4, lest-0.6, where the valid and test contain 1,000 lines each. test-0.4 (resp. test-0.6) contains samples whose best match is 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 or 2 close matches (statistics are in Table 6).
4.3 From alignments to edits
From an alignment (V, Ve, E), we derive the opti- mal edits needed to compute y., and the associated intermediary sequences. Edges in E indicate the tokens that are preserved throughout this process:
1. deletion: Vn, Vi, Yn,i is kept only (n,t, i, E E for some j: otherwise it deleted. The resulting sequences are [yn I==I...N
2. insertion: Placeholders are inserted between successive tokens all al resulting in the set {y J==1..., under the constraints that (a) all yamb have the same length as y. and (b) plachhhceh tokens yo are equal to the reference token y+,i.
For the pre- pre-training experiments ($6.2), we use 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ć, 20155) as com- puted by SacreBLEU (Post, 2018) and COMET scores (Rei al., 2020).
3. combination: Sequences {y W..... are combined into y tok such that for each position i, y <PLH> + -y!k = youu.
If Vn, ynu <PLH>, then y <PLH>>
5.2 Architecture and settings
4. prediction: The remaining <PLH> symbols in tok are replaced by the corresponding target token in y. at the same position.
Our code extends Fairseq implementation of LevT in many ways. uses Transformer models (Vaswani et al., 2017) (parameters in Appendix A). Roll-in policy parameters ($3.3) are empirically set as: a=0.3, f=0.2, 7=0.2, 8=0.2, ==0.1. The AR baseline uses OpenNMT (Klein et al., 2017) and uses the same data TM-LevT (Appendix A).
The expert policy т. edits examples y1,-.. NVN into y. based on the optimal alignment (V, V. E.). It comprises ded with semb and fol correspond- ing to the four steps listed above.
6 Results
5 Experiments
6.1 The benefits of multiple matches
5.1 Data and metrics
We compare two models in Table 2: one trained with one TM match, the other with three. Each
We focus on translation from English 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
phttps://eg thub. com//haweel11444//airsss thub. http://tttt...ooo//ccooerrrrrra/

---

Model IN
2
3
all
always slightly lower than for TM--LevT, which prompted to develop several extensions.
size
4,719
2,369
14,912
22,000
45.8/63.6
48.7/65.0
55.0/68.4
$2.0/66.
TMe-LevT
19.6
26.2
41.5
35.0
6.2
Improving TM"
46.6/64.1
50.0/65.8
56.0/69.3
53.0/67.5
-LevL
14.0
16.0
38.2
30.8
The
the
Y1
yg
Table BLEEU/CrrF and COMET scores on the full test set. All BLEU/Chr differences are significant 0.05).
Reeligner Module
The cal, on Uhe the seerss..
cmb
The cal
on
Use mat
The the
seems
y3
model is evaluated with, at most, the same num- ber of matches seen training. This means that TM--LevT only uses the 1-best match, even when more examples are found. In this table, test sets lest-0.4 and lest-0.6 are concatenated, then parti- tioned between samples for which exactly 1, 2, and 3 matches are retrieved. We observe that TMe-LevT, trained with examples, consistently achieves bet- ter BLEU and Chrli scores than TM--LevT, even in the case N=1, where we only edit the closest match. These better BLEU scores are associated with larger number copies from the retrieved instances, which was our main goal (Table 3). Sim- ilar results for the other direction are reported in the appendix & E (Table 7).
Figure 7: Fixing misalignments with realignment
In preliminary experiments, ob- served that small placeholder prediction errors 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 align- ment. Realignment is formulated as an optimiza- tion problem aimed to perform a tradeoff between the score log mh plh of placeholder insertion and an alignment cost (see Appendix C).
Realignment
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.
TM-LevT
-MV-LevT
TM -LvT
unigrum copy
64.9
64.5
68.8
gen
35.1
31.2
Pre-training Another improvement uses pre- training with synthetic data. For each source/target simu- late N fuzzy matches by extracting from y N sub- strings yn of length sz ly| rr, with r E [0, 1]. Each
bigram
copy-copy
55.0
54.5
58.0
copy-gen
8.9
9.0
10.1
pair (x,y) in the pre-training corpus,
gen-copy 10.7
11.0
gen-gen 25.4
25.7
20.9
Table 3:
Proportion of unigrams and bigram from given origin (copy vs. generation) for various models.
Yn is then augmented follows:
1. We randomly insert placeholders to increase the length by random factor between and + f. 0.5 in our experiments.
We report the performance of systems trained using =11,2,, for each domain and test set in Ta- ble 4 (BLEU) and 12 (COMET). We compara- ble 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 examples seems advantageous for narrow domains, where training actually exploits several close matches (see also Appendix F). We finally note that COMET 9 for -LeVT are
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 bascline (+1.3 BLEU, +6.4 COMET for test-0.4 and +0.9 BLEU, +4.6 COMET for test-0.6). Train- ing curves also suggest that pre-trained models are faster converge. Combining with realignment yields additional gains for - which outper- forms TM' -LevT in all domains and both metrics.
"This because the former model has been fed with more examples during training, which may help regularization. "Those numhers are harder to interpret, given the wide range of COMET scores across domains (from z -40 to +86).

---

BCB
EME
Lpp
GNO
JRC
KDE
News
PHP
TED
Ubu
Wiki
all
test-0.4
AR
63.0
63.6
43.6
69.3
75.1
62.8
28.8
41.2
42.2
59.1
42.2
55.8
TM-LevT
50.5
50.7
31.3
54.3
62.4
47.9
18.0
30.1
24.2
43.3
29.8
42.8
TMvvLevT
53.1
53.7
35.5
60.3
65.6
51.8
22.2
31.7
30.2
48.8
32.0
46.2
TMF-LevT
54.0
54.3
34.0
60.5
66.0
53.2
20.7
33.7
28.9
48.0
32.6
46.5
TM"-LevT
53.9
55.6
34.2
60.8
66.0
53.5
20.4
33.1
28.6
47.5
32.9
46.5
*pre +pre-train
54.9
55.9
34.4
62.7
67.4
54.1
21.1"
34.7
30.1
49.3
33,5
47.5
+realign
54.4
55.9
34.4
61.2
66.2
53.2
20.4
33.3
28.4
47.9
33.1
46.7
+both
55.0
56.0
34.9
62.8
67.5
54.0
21.4
34.8
30.8
49.6
33,9
47.8
lest-0..
AR
69.7
70.4
57.4
80.6
82.4
68.2
26.1
46.4
62.5
68.5
68.7
66.6
TM-LevT
59.0
64.0
45.8
66.9
73.5
53.4
18.8
34.7
49.7
33.2
38.9
33..8"
-Lvv
60.5
64.6
48.9
69.7
75.7
57.2
21.0
36.2
55.0
58.3
62.2
58.2
TM"-Lev)
62.7
67.0
50.0
71.7
76.2
60.2
21.7
38.6
54.2
59.8
62.8
59.7
TH"-LevT
63.8
67.4
50.0
71.1
76.4
60.0
21.5
39.2
54.3
59.6
62.3
60.0
*pre-train
64.9
68.3
50.3
72.7
77.3
62.3
21.8
40.7
54.6
61.3
65.0
61.1
+realign
64.0
68.0
50.2
71.5
76.5
59,9
21.6
39,0
54.7
60.0
60.2
+both 65.0
68.3
50.8
73.7
77.4
62.3
22.0
40.6
54.7
61.4
65.3
61.3
Table 4: Per domain BLEU scores for TM-LevT, TM -LevT and variants. Bold (resp. italic) for scores significantly higher (resp. lower) than TM -LeVT (p = 0.05). p-vauues from BacreBLEU paired bootstrap resampling (n 1000).
The Autoregressive (AR) system implementation of (Bulte and Tezcan, 2019).
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 -LevT model with distilled samples (x, "1.-.. ................................ , ý), where automatic translations Y: and y are derived from their respective source x; and x with an auto-regressive teacher trained with a concatenation of all the training data.
test-0.4
test-0.6
TM"-Levi
46.5
60.1
-sel
46.2
60.0
-delx
44.8
58.6
rrnd-del
38.6
51.9
rrnd-mask
46.0
59.0
-dum-plh
41.0
50.9
-indep-align 42.6
56.4
Table 5: Ablation study. We build models with variable roll-in policies: -sel: no random selection noise (y=0); -delx no extra deletion;-rd-del: no random deletion (8=0); -mask: no random mask (6=0); (6=0):-dumppp) -dum-plh: never start with Ypoet-delFy. (a=0); aande--aligm align- ments are independent. Full results in Appendix F.
We observe that KD is beneficial (+0.3 BLEU) for low-scoring matches (lest-0.4) but hurts perfor- mance 1.7. BLEU) for the better ones in rest-0.6. This may be because the teacher model, with BLEU score of 56.7 on the test-0.6, fails provide the excellent starting translations the model can access when using non-distilled data.
7 Related Work
As for other Machine Learning applications, such as text generation (Guu et al., 2018), efforts to in- tegrate 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 inter- nal computations in the form of retrieved examples (Rudin, 2019). For MT, this is achieved by inte- grating 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), approach that straightforwardly accom- modates several TM matches (Xu et al., 2020), the simultaneous exploitation of their source and target sides (Pham al., 2020). More complex schemes to combine retrieved examples with the source sentence are in (Gu et al., 2018; Xia et al.,
6.3 Ablation study
We evaluate the impact of the various elements in the mixture roll-in policy via an ablation study (Ta- ble 13). Except for =e every new element in the roll-in policy increases performance. As for eel our system seems to be slightly better with than without. An explanation is that, in case of mis- alignment, the model is biased towards selecting the first, most similar example sentence. As ab- lation, instead of aligning by globally maximizing coverage (S 4.2), we also compute alignments that maximize coverage independently as in figure 6a.
complete run of -LevT is in Appendix F.

---

2019; He et al., 2021b). The recent work of Cheng al. (2022) handles multiple complementary TM examples retrieved 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 evaluate retrieved instances based 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.
combine our techniques with other approaches TM-based NMT, such as keeping track of the initial translation(s) on the encoder side.
Limitations
As this work was primarily designed feasibil- ity study, we have left aside several issues related to performance, which may explain the remain- ing gap with published results on similar datasets. First, we have restricted the encoder to only encode the source sentence, even though enriching the in- put 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 train- ing epochs would yield higher absolute scores (see Appendix F).
The use of TM memory match with NAT de- coder 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 in- stance to initialize the edit-based decoder. Other evolutions of LevT, notably in the context of con- straint 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).
These choices were made for the sake of effi- ciency, as our training already had to fare with the extra computing costs incurred by the alignment procedure required learn the expert policy. Note that in comparison, the extra cost of the realign- ment procedure much smaller, as is only paid during inference and can be parallelized on GPUs.
Zhang al. (2018) explore different set of tech- niques to improve translation using retrieved seg- ments instead of full sentences. Extending KNN- based language models (He et al., 2021a) to the con- ditional 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 al. (2022) and extended to chunks by Martins et al. (2022).
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 sys- tems (Xiao et al., 2023). Finally, reported here results for one language pair - favor- ing here domain diversity over language diversity and would need to confirm the observed improve- ments on other language pairs and conditions.
have only
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 trans- lation that is then refined. Owing to multiple algorithmic contributions and improved training schemes, have been able to (a) increase the num- ber 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-basee NMT was a simple way to make the process more transparent for end users. Next, we would like to work the retrieval side of the model: first, to increase the diversity of fuzzy matches e.g. thanks to contrastive retrieval, but also study ways to train the retrieval mechanism and extend this approach to search monolingual (target side) corpora. Another line of work will
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 tech- nology: A practical introduction. University of Ot- tawa Press.
Bram Bulte and Arda Tezcan, 2019. Neural fuzzy pair: Integrating fuzzy matches into neural machine translation. In Proceedings of the 57th Amnual Meet- ing 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 1 1ith International Joint Conference on Natural Language Processing (Volume I: Long Papers), pages 7307-7318, Online. Association for Computational Linguistics.
(Volume 1:
Long Papers), pages 3170-3180, Online. Association for Computational Linguistics.
Cuong Hoang, Devendra Sachan, Prashant Mathur, Brian Thompson, and Marcello Federico. 2022. Im- proving Retrieval Augmented Neural Machine Trans- lation by Controlling Source and Fuzzy-Match Inter- actions. ArXiv:2210.05047 [es].
Michael Carl, Andy Way, and Walter Daelemans. 2004, Recent advances in example-base based machine transla- tion. Computational Linguistics, 30:516-520.
Urvashi Khandelwal, Angela Fan, Dan Jurafsky, Luke Zeullemyee, and Mike Lewis. 2021. Nearest Neigh- bor Machine Translation. In Proceedings of the Inter- national Conference on Learning Representations.
Humberto Carrillo and David Lipman. 1988. The mul- tiple sequence alignment problem in biology. SIAM Journal on Applied Mathematics, 48(5):1073-1088
Yoon Kim and Alexander M. Rush. 2016. Sequence- level knowledge distillation. In Proceedings of the 2016 Conference on Empirical Methods in Natu- ral Language Processing, pages 1317-1327, Austin, Texas. Association for Computational Linguistics.
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.
Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senel- lart, and Alexander Rush. 2017. OpenNMT: Open- source toolkit for neural machine translation. In Pro- ceedings of ACL 2017, System Demonstrations, pages 67-72. Vancouver, Canada. Association for Compu- tational Linguistics.
Hal Daumé, John Langford, and Daniel Marcu. 2009. bearch-based structured prediction. Machine Learn- ing. 75(3)2997-325.
Michael Garey and David S. Johnson. 1979. Com- puters and intractability: a guide to the theory of NP- completeness. W.H. Freeman and Company, New York.
Taku Kudo. 2018. Subword regularization: Improv- ing neural network translation models with multiple subword candidates. In Proceedings of the 56th An- nual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 66-75, Melbourne, Australia. Association for Computational Linguistics.
Jiatao Gu, Changhan Wang, and Junbo Zhao, 2019, Lev- enshtein transformer. In Advances in Neural Infor- mation Processing Systems, volume 32. Curran Asso- ciates, Inc.
Louis Martin, Benjamin Muller, Pedro Javier Or- tiz Suárez, Yoann Dupont, Laurent Romary, Éric de la Clergerie, Djamé Seddah, and Benoit Sagot. 2020. CamemBERT: tasty French language model, In Proceedings of the 58th Annual Meeting of the As- sociation for Computational Linguistics, pages 7203- 7219, Online. Association for Computational Lin- guistics.
Jiatao Gu, Yong Wang, Kyunghyun Cho, and Vic- tor O.K. Li. 2018. Search Engine Guided Neural Machine Translation. Proceedings of the AAAI Con- ference on Artificial Intelligence, 32(1).
Dan Gusfield, 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
Pedro Henrique Martins, Zita Marinho, and André F. T. Martins. 2022. Chunk-based nearest neighbor ma- chine translation. In Proceedings of the 2022 Con- ference on Empirical Methods in Natural Language Processing, pages 4228-4245, Abu Dhabi, United Arab Emirates. Association for Computational Lin- guistics.
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. Efficientt nearest neighbor lan- guage models. In Proceedings of the 2021 Confer- ence on Empirical Methods in Natural Language Pro- cessing. pages 5703-5714, Online and Punta Cana, Dominican Republic. 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.
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
Makoto Nagao. 1984, A framework of a mechanical translation between Japanese and English by anal- ogy principle. In Artificial and human intelligence. Elsevier Science Publishers. B.V.

---

Ayana Niwa, Sho Takase, and Naoaki Okazaki. 2022. Nearest neighbor -on-autoreeressive text generation. CoRR, abs/2208. 12496.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Sys- tems, NIPS"17, 17, page 6000-6010, Red Hook, NY, USA. Curran Associates Inc.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei- Jing Zhu. 2002. Bleu: method for automatic evalu- ation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Compu- kational Linguistics, pages 311-318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
Mengzhou Xia, Guoping Huang, Lemao Liu, and Shum- ing Shi. 2019. Graph based translation memory for neural machine translation. Proceedings of the AAAI Conference Artificial Intelligence, 33(01):7227- 7304.
Minh Quang Pham, Jitao Xu, Josep Crego, François Yvon, and Jean Senellart. 2020. Priming neural ma- chine translation. In Proceedings of the Fifth Confer- ence on Machine Translation, pages 316-527,00 Online. Association for Computational Linguistics.
Yisheng Xiao, Lijun Wu, Junliang Guo, Juntao Li, Min Zhang, Tao Qin, and Tie- Yin Liu. 2023. A survey on non-autoregressive generation for neural machine translation and beyond. IEEE Transactions on Pat- tern Analysis and Machine Intelligence, pages 1-20.
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.
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.
Matt Post. 2018. A call for clarity in reporting BLEU scores. Proceedings of the Third Conference on Muchine Translation: Research Pupers, pages 186- 191. Brussels, Belgium. Association for Computa- tional Linguistics.
Jitao Xu, Josep Crego, and François Yvon. 2023. Inte- grating tramslation memories into non-autoregressivee 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.
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 Process- ing (EMNLP), pages 2685-2702, Online. Association for Computational Linguistics.
Weijia Xu and Marine Carpuat. 2021. EDITOR: An edit- buit-based transformer with repositioning for neu- ral machine translation with soft lexical constraints. Transactions of the Association for Computational Linguistics, 9:311-328.
Stephane Ross, Geoffrey Gordon, and Drew Bagnell. 2011. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In Pro- ceedings 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.
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 Tech- Rologies, Volume I (Long Papers), pages 1335-335, New Orleans. Louisiana. Association for Computa- tional Linguistics.
Cynthia Rudin. 2019, Stop explaining black box ma- chine 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.
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 Confer- ence on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. 2019. Insertion transformer: Flexible se- quence generation via insertion operations. In Pro- ceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Ma- chine Learning Research, pages 5976-5985. PMI.R.
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 Asso- ciation for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Processing ( (Volume 2: Short Papers), pages 368-374, Online. Association for Computational Linguistics.
Raymond Hendy Susanto, Shamil Chollampatt, and Lil- ing Tan. 2020. Lexically constrained neural machine translation with Levenshtein transformer. In Proceed- ings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3536-3543, On- line. 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- seniations.
sider the following sentences before placeholder
insertion:
you yoth
A
B
C
X
X
y2 plh
A
D
C
D
A Model Configuration
where letters represent tokens, x denotes padding, and > respectively stand for <BOS> and <EOS>.
We use 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:
The output of this stage is a prediction for all pairs of consecutive tokens. This prediction takes the form of tensor log phh of dimensions N (L-1)x (mazz +1), corresponding respectively the number of retrieved sentences N, the maximum sentence length L, and the maximum number of additional placeholders Kmea-
The maximal number of additional placeholders is Kmaz- = 64.
During training, use Adam optimizer with (81, (0.9, 0.98); inverse sqrt scheduler; learn- ing rate: 5e-4; label smoothing: 0.1: warmup up- dates: 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).
Let (a NaNx (L. -T- tensor) denote the arg max,
0 0
0
e.g. P
0 0 1 0
0
0
0
Inserting the prescribed number of placehold-
ers (figured by _ then yields the following y cmb,
you yimb.
A
B
C
For the naway alignment ($4.1), use k=100 The hyper-parameter of the realigner ($C) were tuned on a subset of 1k samples extracted from the ECB training set.
B
C
D
I
ymmb
A
D
This result is far from perfect, as fails to align the repeated occurrences of C. For instance, a preferable alignment requiring 3 changes (1 change consists in a modification of + in P) could be:
Metrics are used with default settings: Sacre- BLEU signature is nrefs: case: w tok: 13a| smooth: 2
the ChrF signature is nrefs: ccae: eff: Inc: nw: 0 space: no/ version::: as for COMET we use the default model of version 1.1.3:
yamb' yombl yomb',
A
B
C
B
C
2
A
D
C
D
X
The general goal of realignment is to improve such alignments by performing a small number of changes in P. We formalize this problem search for good tradeoff between (a) the indi- vidual placeholder prediction scores, aggregated in Li. (likelihood loss) and (b) La 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.
mnbabel/wmt22-come
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 -Lev to perform better than -LeVT in Table The domains with retrieval rates lesser than 1 (Epp. News, TED, Ubu) have quite broad content, meaning that training instances have fewer close matches, which also means that for these domains, -LvV hardly sees two or three examples that it needs to use in inference.
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 Più can take continuous real values in [0, K Kmax], then solve the continuous optimization problem before turning Ps,j values back into integers.
Realignment
The realignment process an extra inference step aiming to improve the result of the placcholder in- sertion stage. To motivate our approach, let us con-
The likelihood loss aims keep the P.g values close to the model predictions. Denoting (μ, o) respectively the mean and variance of the model

---

domain
ECB
EME
Epp
GNO
JRC
KDE
News
PHP
TED
Ubu
Wiki
all
size
195k
373k
2.0M
55k
503k
180k
151k
16k
159k
9k
803k
4.4M
retrieval rate
1.66
2.12
0.91
1.18
1.71
1.10
0.24
1.20
0.96
0.62
1.22
1.18
mcan length
29.2
16.7
26.6
9.4
28.8
10.5
26.4
14.5
17.7
5.2
19.6
18.6
Table 6: Number of samples, average number of retrieved sentences and average length of sentences after tokeniza- tion for all 11 domains.
predictions, our initial version of this loss is
N-1L-1 CP = Σ Σ dn.(P) ==0 ==
(Prg - 12a)²
(P) Σ 1.j
20²
A final ingredient in our realignment model is related the final discretization step. To avoid rounding errors, we further constrain the optimiza- tion process to deliver near-integer solutions. For this, we also include a integer constraint loss de- fined as:
In practice, we found that using weighted average á and clamping the variance d² both yield better realignments, yielding:
(Prj )
(1(
Σ 1 202
Cine(P) = pt Σ (Tis) i
To define the alignment loss, we introduce a po- sition matrix X of dimension N x L in IR where
Xn, corresponds the (continuouspposition of token yn after inserting real number of place- holders. X defined as:
where 14 controls the scale of Lint (P)).)). (P). As sin² (TT)) reaches its minimum for integer values. minimizing Line (P) has the effect of enforcing a near-integer constraint to our solutions. Overall, we minimize in P:
(P) - i Pnr
Pao
jEi
with the number of tokens occuring before Xn,i and Ej<r Pag the cumulated sum of placeholders. Using X, we derive the distance tensor D of di- mension N x x N L in R as:
L - Lz CA(P) Line
slowly increasing the scale of #4 according to the following schedule
Dujim (P) = [X Xmyl
if < to if T otherwise
14
μT PT
Finally, let G be an N X L x N x L alignment graph tensor, where Gniimm = 1 if and only if Un.i = Ymjj and n # m and Dn..mm < Dmaz- G connects identical tokens in different sentences when their distance after placeholder insertion is most Daaz- This last condition avoids perturba- tions from remote tokens that coincidentally appear be identical.
to) (T fu)
with 4. T the timestamps for respectively the ac- tivation of the integer constraint loss, and the ac- tivation of the clamping. This optimization is per- formed with gradient descent directly GPUs, with small additional cost to the inference proce- dure.
Each token Vn,i is associated with an individual loss:
D NP-hardness of Coverage Maximization in N-way Alignment
min (Dnjim((P) Gnimm = 1) mi if (f,, f) Gniim, =1
Given the set of possible N-way alignments, the problem of finding the one that maximizes the tar- get coverage NP-hard. To prove can reduce the NP-hard set cover problem (Garey and Johnson, 1979) to the N-way alignment coverage maximiza- tion problem.
dp,((P)
otherwise.
The alignment loss aggregates these values over sentences and positions as:

---

Cover decision problem (A):
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 exam- ples that do not occur in the target. We observe that, in fact, low diversity often associated with scores for -MevLevT, and higher diversity with better performance.
Let X = {.1, NN and Co C 2x Is there c² = (c1,",,, CK) E Co s.t. Uk c [X]?
N-way alignment coverage maximization de- cision problem (B):
Let = {z1, IN} and C = [CI,... Ck) C (2*)A, For N, is there e E II Ck s.t. UR Ch p?
Cover
noise
lest-0.4
test-0.6
lest-0.4
test-0.6
ECB
+8.2
+8.9
+3.7
+4.4
A solution of (B) can be certified in polynomial time: simply compute the cardinal of union. Any instance of (A) can be transformed polyno- mial time and space into a special instance of (B)
EME
+8.9
+8.5
+4.0
+5.0
Epp
+10.5
+13.7
+2.2
+4.0
GNO
+7.1
+6.2
+7.6
+9.3
JRC
+7.2
+6.8
+4.8
+5.2
where C = Co and = [X].
KDE
+8.0
+7.5
+6.9
+7.8
News
+7.2
+12.5
+2.3
+5.0
E Results for fr-en
РHP
+7.2
+7.6
+4.2
+5.4
TED
+9.4
+11.4
+2.9
+4.6
Table ?? reports the BLEU scores for the reverse direction (fr->en), using exactly the same config- uration as Table 2. Note that since we used the same data split (retrieving examples based on the similarity in English), and since the retrieval proce- dure is asymmetrical, 4,749 test samples happen to have no match. That would correspond to an extra column labeled "O", which is not represented here.
Ubu
+5.5
+6.0
+6.7
+8.6
Wiki
+8.0
+8.0
+2.5
+3.6
all
+8.1
+8.9
+4.4
+5.7
Table 8: Coverage and noise scores increase. "Diffi- culty" highlighted bold (< 8.0 for cover; >> 6.0 noise).
Long run All results in the main text were ob- tained with models trained for 60k iterations, which was enough compare the various models while saving computation resources. For completeness, also performed one longer training for 300k it- erations for -LeV (see Table 9), which resulted in an improvement of around +2 BLEU for cach test set. This is without realignment nor pretrain- ing.
Model IN
2
3
all
size
2,753
1,675
12,823
17,251
TM -LeTT 57.2
57.6
61.5
60.2
T -LeVT 58.2
59.4
64.0
62.4
+pt
+ra
Table 7: BLEU scores on the full test set. -LevT is improved with pre-training and realignment. All BLEU differences significant SacreBLEU paired bootstrap resampling (n 1000).
0.05). p-values from
model
lest-0.4
fest-0.6
The reverse direction follows similar pattern, providing further evidence of the method's 's effec- tiveness.
TMe-LevT
46.5
60.0
realign
46.7
60.2
3
long
48.7
61.9
realign
48.9
62.0
F Complementary Analyses
Table 9: BLEU score of TM9-LevT: 60k iterations; and - long: 300k iterations.
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 Eu- roparl, News-Commentury TED2013, and Ubuntu. We claim that this due the lack of retrieved examples training (as stated in $B), of diversity, and the noise in fuzzy matches. To further inves- tigate this issue, we report two scores in Table The first the increase of bag-oft word coverage
The Benefits of realignment Table 10 shows that realignment also decreases the average number of refinement steps converge. These results suggest that the edition is made casier with realignment. In Table 11, we present detailed results of the unigram modified precision of LevT, TM3-LevT and

---

model
test-0.4
test-0.6
-LeT
3.55
2.07
+realign
3.37
1.93
Table 10: Average number of extra refinement rounds.
Teg-LevTtreallgn. Using more examples indeed increases copy (+4.4), even though it diminishes copy precision (-1.7). Again we observe the posi-
tive effect of realignment, which amplifies the ten- dency of our model to copy input tokens.
model
precision
% units
TM-LevT
copy
87.5
64.9
gen
52.6
35.1
-Me-L copy
85.4
68.8
gen
54.9
31,2
+realign copy 85.8
69.3
gen 54.7
30.7
Table 11: Modified precision of copy vs. generated
unigrams LevT vs. TMe-L
COMET scores We compute COMET scores (Rei et ul., 2020) separately for each domain with default
similarly to Table 4 (see Table 12). We observe that the basic version of Twf-LevTundeeperforms TM- great variation in the scores. A possible explana- tion can be fluency decline when using multiple examples, which 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.
also
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 ex- amples and realignment. Even though the realign- ment does not change here the final output, it re- duces the number of atomic edits needed gener- ate it, making the inference more robust.

---

ECB
EME
Epp
GNO
JRC
KDE
News
PHP
TED
Ubu
Wiki
all
lext-0.4
LevT
33.0
43.1
39.9
56.3
70.7
37.4
-2.0
-39.6
-0.8
41.6
-9.9
24.5
-eVT
27.2
42.0
31.1
48.0
64.4
32.6
-10.8
-42.7
-8.7
35.3
-15.7
18.4
LevT
27.3
42.1
26.8
51.5
64.2
33.5
-10.1
-39.9
-14.8
38.6
-16.3
18.4
+pre-train
30.6
44.7
38.7
57.9
67.8
37.9
-6.2
-35.3
2.7
41.5
-5.0
25.0
+realign
31.0
45.1
32.0
53.2
66.4
34.9
-10.9
-39.0
-1.99
41.1
-00.8
21.0
+both
33.7
46.4
42.4
59.9
69.9
40.1
-1.0
-33.0
5.1
43.5
-3.7
27.5
test-0.6
TM--
51.7
53.9
56.9
65.3
85.4
37.0
-3.0
-17.0
48.5
57.6
64.5
45.5
TMP-LevT
51.2
54.2
56.3
64.2
82.5
34.6
99.0
-15.9
46.1
55.5
61.6
43.7
TM9-LevT
50.9
55.8
54.1
65.1
81.1
33.6
-9.8
-16.2
41.1
57.4
61.7
43.1
+pre-train
54.6
56.5
58.0
68.2
84.7
41.5
-4.3
-11.8
48.9
62.7
65.6
47.7
+realign
53.0
56.4
56.3
65.4
83.6
34.3
-7.2
-16.1
42.8
58.3
63.7
44.6
+both
55.7
57.4
58.8
70.5
85.8
43.2
-44
-10.6
49.4
62.3
67.7
48.7
Table 12: Per domain COMET scores (x 100) for TM" -LeVT and variants. Bold for scores better than TM--LevT
ECB
EME
Epp
GNO
JRC
KDE
News
PHP
TED
Ubu
Wiki
all
lest-0.4
-LevL
53.9
55.6
60.7
66.0
53.5
20.4
33.0
28.6
32.8
46.5
-sel
54.5
55.6
32.7
61.2
65.9
52.2
19.5
33.3
27.7
48.1
31.3
46.2
-delx
52.2
53.4
31.8
58.7
64.0
52.0
19.6
31.2
27.5
46.8
31.5
44.8
-rd-del
49.7
47.6
22.2
48.2
56.7
38.8
13.2
29.5
16.9
32.2
21.4
38.6
-mask
53.4
54.7
33.7
58.9
65.3
52.4
20.3
33.1
27.5
47.1
32.2
46.0
ddumpphh
50.8
43.3
32.7
45.6
61.2
42.4
21.0
30.9
24.3
35.6
28.2
41.0
-indep-alll align
51.5
52.4
29.7
53.8
60.7
47.2
16.9
30.4
21.8
39.0
28.4
42.6
test-0.6
-LevL
64.2
68.0
.4
73.0
76.4
60.1
21.2
39.6
52.2
60.1
61.6
60.1
-sel
63.8
67.5
50.0
71.2
76.3
60.0
21.5
39.1
54.2
59.7
62.2
60.0
-eex
62.1
66.7
47.7
70.6
75.0
58.8
20.1
37.9
53.5
58.4
60.9
58.6
rrd-dll
58.4
59.6
39.7
59.0
67.6
47.7
16.9
35.0
39.8
44.1
47.4
51.9
-ask
63.1
65.3
49.1
69.4
74.2
58.2
21.8
38.6
50.9
59.7
59.0
-dum-phh
57.3
55.5
44.9
51.8
68.5
44.5
20.2
35.7
42.6
38.7
50.7
50.9
Lindepaaigg
60.6
64.0
46.6
64.3
71.9
55.5
18.6
35.6
44.6
51.6
56.0
56.4""
Table 13: Ablation study. We report BLEU scores for various settings. -sel: no random selection noise (y=0); delxx no extra deletion loss;-rd-del: no random deletion (8=0); -mask: no random mask (6=0); -dum-plh: null probability start with de (a 0); -indep-align the alignments are performed independently.

---

src:
The swf setfont () sets the current font to the value given by the fontid parameter.
tgt:
swf setfont () remplace la police courante par la police repérée par 1 identifiant fontid.
LeVT
swe fone size O) remplace taille de la police par taille size. yith swe f_+2 () remplace la+1 1 de police+1 i par la+5
ydd,
ydok swe set police remplace la police de police courante par la valeur de paramètre ti d.
yda. sw f set police remplace la police de police courante par la valeur de paramètre ti d.
you +1 sw sct police remplace la police de police courante+ par la valcur de paramètre+ tie d.
yook: Le sw f set police remplace la police de police courante donnée par la valeur de paramètre fon tie hyp: Le swf setpolice remplace la police de police courante donnée par la valeur de paramètre fontid.
TM -LeVT
swe fone to size () remplace la taille de la police par la taille size
define font () définit la police fone te name et lui affecte I 2 identio fiant fon ti d.
y
sw +2 () remplace la police+6 par+-4..
+1 font () définit la police+9 fone tie d.
SW
( remplace la police
par
SW
font () définit police
fone
ylok:
SW f set font () remplace la police actuelle à à la valeur donnée par le paramètre fone ti
ydde
Sw sete font remplace la police actuelle la valeur donnée pur paramètre fone
yiuh:
sct font remplace la police actuelle++] la valeur donnée par le paramètre fone tio d
yook;
Sw sete font remplace la police actuelle la valeur donnée par paramètre fone d. comeinteennn
hyp:
swf setfont () remplace la police actuelle la valeur donnée par le paramètre fontid.
TH3 -LeVT
sw f fene to size () rempe place la taille de la police par la taille size.
swe define ee font défimit la police fone te name et lui affecte! identti fannt fone tie d.
sw fo text sete font remplace la police courante par font.
swe r_+2 () remplace la policc+4 par+5..
f_+1 font définit la policc+7 tie d
Sw +2 sct font () remplace police courante+4 par+5.
yomb
remplace la policc
par
Swe font () définit la police
Sct font remplace la police courante
peF
fok.
Swe
set font remplace la police courante au valeur donnée par le fone tie d font remplace la police courante ae valcur donnée par le fone mo..
yida
d... +1 sw f set font remplace la police courante+2 valeur+1 1 par le+1 fone tie d
yith
Le sw f set font () remplace la police courante la valeur donnée par le paramètre fone ti
hyp:
Le swf setfont remplace la police courante à la valeur donnée par le paramètre fontid.
TM LevTT + realign
swe fene to size () rempe place la taille de la police par la taille size.
define font définit la police fene name et lui affeete I : identie fiant fone tie d.
sw fo text -stt font remplace la police courante par fent.
yib.
[=22 remplace la police+4 par+5..
sw 1+1 font () définit la policc+8 tie d.
sw +2 sct font remplace police courante+3 par+5..
yomb
SW f
() remplace la police
par
Sw
font () définit la police
ti d
SW set font () remplace la police courante
par
sw
sete font rempluce police courante au valeur donnée par le paramètre fone tie d set font () remplace la police courante valeur donnée par le paramètre fone ti d
yalh
+1 sw f set font () remplace la police courante+2 valeur donnée par le paramètre fone tie
tok.
Le f set font () remplace la
courante à la valeur donnée -pr le puramètre fone tie d - wn wer.e...........................
mo depprrann Le swf setfont () remplace la police courante à la valeur donnée par le paramètre fontid.
hyp:
Table 14: Examples full inference several models on a test sample from text-0.4-PHIP (sample 5711)). Copied parts are in red.


Reviews:
[{"review_id": "HuDC6tZHnG", "reviewer": "Reviewer_4qBu", "summary": "", "questions": "* Lines 32-33: \"the autoregressive nature of the decoder can make the process...\" What does it have to do with the autoregressive decoder? One can have an edit-based MT system with an autoregressive decoder.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the review. We will fix factual errors and typos. We also reckon that for the sake of space, several technical details had to be compressed. Having one extra page will give us the opportunity to make our presentation less dense in the revised version.\n\nWe noted worries about the reproducibility. Note that both code and data split will be released on github upon publication with detailed instructions (this is mentioned in *lines 089-090*).\n\nSection 3.3 and 4 have been reported to be hard to grasp. We will do our best to make them more readable, and to better illustrate the alignment process. We will also change subsection \"Learning\" to \"Imitation Learning\". Please, do not hesitate to share ideas to improve these sections.\n\n**Some remarks**:\n\nWe give a high-level presentation of Gu et al.'s LevT in section 2.2; in the revised version, we will better expand it and also illustrate the commonalities and differences with our own approach in Figure 2\n\n**Answers to questions raised**:\n* *Lines 32-33*: While point (a) is linked to the autoregressive nature, (b) is due to the generative nature (i.e. to the fact translation is generated from scratch). You are right to point out that an edit-based model could also be auto-regressive -- we will rephrase this sentence.\n\n* About the *combination*:\nThe combination operation can yield to deletions when it selects a placeholder at some position. In the ideal case (when the deletion model is error-free), this would not happen. But since there might be mistakes with undeleted tokens in the deletion component, the combination can act as a safety layer of deletion. But it is more an implication in the design choice than a \"second deletion\". An initial deletion/insertion is still necessary to generate aligned sequences, from which the combination module selects the right sequence of positions (see Figure 3).\nWe will add an explanation to clarify this point.\n\n* About *training* (section 3.3), except for the initial state and for state (5), we claim the computation of optimal edition is \"obvious\" (see *line 288*). This is because training examples are generated by randomly perturbing sequences in a way that we can easily reverse. For instance, when deleting random tokens with $\\pi^{rnd.del.N}$, the optimal insertion is to put back placeholders where the deletions occurred.\nWe will clarify this point.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* The paper presents an interesting extension of Levenshtein Transformer to a more realistic scenario where multiple examples from the translation memory are found relevant to the translation at hand.\n* The solution (the combination operation and the modification to the training via imitation learning) is novel and technically interesting.\n* The solution leads to performance improvements over Levenshtein Transformer.", "reasons_to_reject": "I find the paper not very well structured and not clearly written.\n\n  + The model of Gu et al. 2019, to which this work makes modifications, should be explained in all necessary detail. Without this context, the paper is hard to follow. Also, presenting Gu et al. 2019 first would make it clear which modifications and additions this paper makes. \n\n  + The combination operation is not clear. Ostensibly (Figure 3), combination also performs deletions (just mark a token to not be selected for the combination). So why do we need deletion before combination? Combination is one of the main contributions of the paper, it has to be explained accordingly.\n\n  + Section 3.3 is hard to understand. The problem is not in the subject matter (imitation learning roll-ins), but the content presentation. Figure 4 needs clarification. Also, what exactly are the contributions of this paper in this section?\n\n  + The heuristic N-way alignment (Section 4.2) needs clarification and examples. It would also be helpful to see examples of when the heuristic alignment fails to recover the optimal alignment.\n\n  + I don't understand how expert roll-outs are computed in non-initial states. A detailed explanation of how the training works is in order.\n\n  + Generally, here and there, there is a lot of notation that is not properly introduced.", "questions_to_authors": "* Lines 32-33: \"the autoregressive nature of the decoder can make the process...\" What does it have to do with the autoregressive decoder? One can have an edit-based MT system with an autoregressive decoder.", "paper_topic_and_main_contributions": "The paper extends the Levenshtein Transformer of Gu et al. 2019 to work on editing multiple examples from the translation memory. To this end, the set of edit operations is expanded with combination, which selects tokens from each example sentence that will be kept in the combined sentence. To train the model, the training via imitation learning is modified so that the expert policy tracks a heuristically optimal N-way alignment between translation memory examples and the target. The paper reports improvements from this model over Levenshtein Transformer from a single example.", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "T2vFC5Dm5p", "reviewer": "Reviewer_k9eN", "summary": "", "questions": "For the learning part, I think the idea of shuffling top_k fuzzy matches during training (i.e. shuffle 3 examples from top-10 instead of using top-3 references) maybe useful for training your model.\nReference: \nImproving Robustness of Retrieval Augmented Translation via Shuffling of Suggestions, Cuong Hoang et al., 2023 https://arxiv.org/abs/2210.05059\n\n[Updated after author response] - I thank authors for their response.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the review. We will fix factual errors and typos. We also reckon that for the sake of space, several technical details had to be compressed. Having one extra page will give us the opportunity to make our presentation less dense in the revised version.\n\nThank you also for suggesting the idea of shuffling top_k matches. We will consider it in our future work, along with other approaches to improve retrieval (e.g. with contrastive examples, etc).\n \nWe noted worries about the reproducibility. Note that both code and data split indices will be released on github upon publication with detailed instructions (cf. *lines 089-090*).\n\nSection 3.3 and 4 have been reported to be hard to grasp. Admittedly, they are very technical and hard to clearly synthesize. We will do our best to make them more readable. We were also suggested to add an illustration of the alignment process.\n\n**Some remarks**:\n\nWe indeed did not enrich the source side with the TM examples due to practical reasons. In fact, it inevitably yields longer inputs and smaller batch sizes. Large batch sizes are essential in NAT setups, so this would have to be compensated with more GPUs or cumulative gradients, which would likely have increased the training time in our experiments. Note that in principle, mLevT could also benefit from an enriched source side.\n\nNonetheless, we agree that there is still a gap between AR and NAT models (cf. results in Table 4). Our work aims to improve TM-augmented NAT and close this gap (which it partially does), also for the sake of explaining (more precisely tracing back) some translation outputs, which an AR system cannot do.\n\n**Answers to questions raised**:\n\n* Inference complexity: Our method yields a higher computational cost at training due to the alignment step, which has an algorithmic complexity of $O(k^N)$. In practice, it approximately doubles the training time. As for inference, the first cycle of edition only has one extra combination step compared to LevT. So it barely increases the latency in theory and in practice. This will be clarified in the revised version.\n* *line 177*: $E_{y_{n,i}}$, $P_i$ and $S_n$ all have dimension $d_{model}$ since the written indices select the columns in matrices $E$, $P$ and $S$. Moreover, $S$ has a role of discrimination between the multiple TMs. $S_n$ thus identifies TM $y_n$. As for the extra dimension, $S_N$ identifies the combined sentence obtained through combination ($y^{tok}$), which undergoes refinement. We can add a sentence explaining this point that is not obvious.\n* *line 195*: Matrix $A$ has a $2 \\times d$ shape since the decision of deletion is formulated as a classification problem with 2 classes, and not a logistic regression with a decision threshold. This is the choice made in the original LevT paper.\n* *line 195-198*: $y^{del}$ is the TM sentences before deletion while $y^{plh}$ is the result of applying deletions, and before insertion of placeholders.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* Novelty of the idea of having a combination of N fuzzy matches for generating the final translation from a Levenshtein Transformer is the strongest point of the paper in my opinion. Using N fuzzy matches is an obvious approach to improve translation accuracy of Retrieval-Augmented Machine Translation in general. Nonetheless it is not obvious at all how it works (especially both training and decoding part) with Levenshtein Transformer. The paper shows that there is a way to do so, and there is some benefit (i.e. improving in translation accuracy)", "reasons_to_reject": "While I like the work a lot, I think there are two main critical feedbacks of the paper:\n* The complexity of the framework is not straightforward at all to implement, let alone it is very expensive to train the model (btw how is about the complexity of the inference?). I tried to pay very close attention to the details but I give up at some point because it is not obvious at all some details of the paper. While I recommend the authors to revise the writing a bit to make sure the technical part of the paper is clear, releasing the implementation if possible is very useful for this work.\n* The baseline for the experiment is not that strong, for two reasons. First, the baseline does not enrich source sentence with fuzzy matches, which would make a much stronger baseline (I even suspect the improvement of the proposed method will be very little in that case). Second, the baseline is with NAT, which is not strong compared to using auto-regressive model. So it is hard to convince the usefulness of the framework.", "questions_to_authors": "For the learning part, I think the idea of shuffling top_k fuzzy matches during training (i.e. shuffle 3 examples from top-10 instead of using top-3 references) maybe useful for training your model.\nReference: \nImproving Robustness of Retrieval Augmented Translation via Shuffling of Suggestions, Cuong Hoang et al., 2023 https://arxiv.org/abs/2210.05059\n\n[Updated after author response] - I thank authors for their response.", "paper_topic_and_main_contributions": "The Levenshtein transformer (TM-LevT) of Gu et al. (2019) is an encoder-decoder model which, given a source sentence, predicts edits including insertion and deletion that are applied to an initial translation and generate a revision of the output. The initial translation corresponds to a match from a TM (or an empty output). The paper proposes simultaneously extends TM-LevT to TM^N -LevT, which the goal is to handle several initial translations retrieved from TMs. This sounds pretty straightforward but it is actually not obvious at all, involving multiple algorithmic and computational challenges. The authors present preliminary experiments, showing that using TM^N -LevT\ngives better translation accuracy to TM -LevT. I could not follow all the details because the paper itself is extremely technical to me. But I like the novelty of the work a lot. I think it is the strongest point of the work. Meanwhile, there is clear concern with the complexity of the framework, and whether the baseline is strong enough for a good conclusion of how useful the framework is.", "excitement": 3, "reproducibility": 2, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "See the question for the reference that could be useful to your work."}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "Unfortunately the framework is very technical. I don't blame the paper at all about this, just I think some of the following things need to be clear:\n* Extending TM-LevTto -> add extra space (line 72)\n* which extends TM-LevTto -> add extra space (line 68)\n* an increase in translation performance -> performance can mean different things. I guess what you meant here is the accuracy.\n* As editing operations are not observed in 132 the training data, LevT resorts to Imitation Learn- 133 ing, based on the generation of decoding configu- 134 rations for which the optimal prediction is easy to 135 compute -> This detail is important but the paper is not self-contained at this point.\n* Line 177 - Denoting y = (y1, · · · , yN ), N retrieved instances, yn,i is encoded as Eyn,i + Pi + Sn -> I supposed E is the embedding of the token, P is the positional encoding of the token, Sn is the encoding of the source sentence.\nSn is explained in line 183 but it is very vague what it is. Plus why would we sum all of them (Eyn,i + Pi + Sn as they have different shapes) and why would the lenth of S is N + 1 instead of N?\n* In Figure 2, please explain in the description about del (delete), plh (insert), cmb (combination) and tok (prediction).\n* Line 195: Why A has dimension of 2xd_model instead of d_model?\n* Line 195 and line 198: each deleted token y_{n, i}^{del} and each insertation y_{n, i}^{plh} -> I don't think I could follow the difference between these two tokens. They should be the same???\n\nI could not follow in detail section 3.3 and 4. I think these are very technical and I hope the authors will make them more readable."}}, {"review_id": "otnJXiaej6", "reviewer": "Reviewer_Fysf", "summary": "", "questions": "- Is there an attempt to increase the TM matches so that (2) assumption in Section 4.2 becomes intractable? \"For each training sample (x, y), we retrieve up to 3 in-domain matches\", does that mean that N=3 and you've set k=10 according to the settings in the Appendix A. Is my understanding of N and k correct? \n\n- Would the source for the proposed method be open sourced?\n\n- Will the splits of the train/dev/test sets be release? \n\n\n", "limitations": "", "rating": 4, "confidence": 4, "soundness": 5, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review.\n\nNote that both code and data split indices will be released on github upon publication with detailed instructions (cf. *lines 89-90*).\n\n**Some remarks**:\n\nmgiza++, nltk.align are for bilingual alignments. In our case, we perform an exact monolingual lexical N-way alignment in the target language only (the target-side TMs aligned with the reference). Only identical words can be aligned -- which means that the lexical alignment model is trivial and does not need to be learned.\n\nThanks for the additional reference to MSA for word alignment.\n\nIt is true that we only experimented with one pair (en-fr), while we could have used WMT14 and (en-de) to be in line with recent MT works.\nWe explain this choice with two reasons:\n* It makes it comparable to some other works using the same multidomain data, like Xu et al., 2023, who used a similar setup.\n* We can already widely explain the observed differences in performances across the multiple domains with our data (see Appendix E).\nWe intend to also reproduce experiments for the other language direction, and eventually other language pairs. \n\n\n**Answers to questions raised**:\n\n* Your understanding of N and k is correct. As for N, we did not perform experiments with higher value since the computational cost of the alignment is exponential with respect to N. The training would become too slow, while still theoretically feasible. A future work could consist of further improving the complexity of the N-way alignment.\n* The versions of SacreBleu and Comet used in the experiments are documented in Appendix A.\n* We will add chrf scores from SacreBleu in the appendix as suggested", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Well-written and clear presentation and writing. Thorough work done to the proposed architecture. The strengths of the paper definitely outweighs the weakness, see above for details.\n\n", "reasons_to_reject": "Mainly the experiment evaluation being carried out in one direction of translation and for a single language from an older test sets but these are minor weakness given precedence that this particular topic has always been evaluated this way. More details, see weaknesses above\n", "questions_to_authors": "- Is there an attempt to increase the TM matches so that (2) assumption in Section 4.2 becomes intractable? \"For each training sample (x, y), we retrieve up to 3 in-domain matches\", does that mean that N=3 and you've set k=10 according to the settings in the Appendix A. Is my understanding of N and k correct? \n\n- Would the source for the proposed method be open sourced?\n\n- Will the splits of the train/dev/test sets be release? \n\n\n", "paper_topic_and_main_contributions": "Summary: This paper adapts a retrieval based levenshtein transformers (LevT) to utilize translation memory in machine translation (TM3-LevT). The main contributions for this paper:\n \n- introducing the combination layer in LevT (layers here also refers to \"edit operations\")\n- using maximal cover policy instead of levenshtein distance (Section 4); proposing a simplified method to align TM matches to target sentence and using the alignments to determine edit policy\n\n\nStrength:\n- Interesting simplified approach in Section 4.2 for alignment capitalizing on the fact that the no. of n-way TM matches are small. An old-timer MT practitioner from phrase-based MT era might simply added IBM model 2 or model 4 alignments to the translation inputs, e.g. https://aclanthology.org/W16-2206 \n- [major] following up on the experiments results, highlighting limitations and proposing methods to overcome the limitations\n- [major] Rigorous work done to show comparison of proposed architecture against (i) vanillia auto-regressive model, (ii) default LevT model, (iii) various ablation of components in the proposed architecture and (iv) models with refinements made after initial experiments\n\n\nWeakness:\n- [minor] The simplified alignment method, word / token alignment is extremely hard in MT. While the simplified approach + realignment efforts (Appendix C) is commendable, it'll be make the paper even better if the proposed alignment is compared to well-studied and battle-proofed IBM models, e.g. from mgiza++. (Putting this down as a minor weakness because the older software/tools that runs IBM models are not that well-documented but might not be that accessible to researchers who are unfamiliar with the tools)\n- [minor] WMT14 only evaluation is generally frowned upon in recent MT works but in the case of lexically constraint MT or TM-MT, that seems to be the only WMT14 evaluation set that are comparable to previous work. Also, usually people also compare results to the EN-DE portion of WMT14 that comes with a dictionary https://aclanthology.org/P19-1294/ but this wasn't present in the paper (I understand the choice of dataset might be arbitrary so putting this down as a minor weakness).", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "- Related to Section 4.2, a long time ago https://aclanthology.org/2005.eamt-1.23/ actually used MSA to bootstrap word alignments. A mention to it when referencing \"This problem can be solved using Dynamic Programming (DP) techniques similar to Multiple Sequence Alignment (MSA)\" would be good.\n", "Typos_Grammar_Style_and_Presentation_Improvements": "**Stylistic:**\n\n- Section 3, line 181 \"The latter component ...\", if you are referring to S (sequence embedding), avoid ambiguity in the writing, \"The latter component\" -> \"The sequence embedding ...\"\n- \"Conclusion and outlook \" -> \"Conclusion and Outlook\"\n- Also keep the headings of \\section{} and \\subsection{} consistent, sometimes it's titlecase, sometimes is capitalized only on the first word, choose one. Personal preference is title case for all \\section{} and caps for only first word for \\subsection{}\n\n**Content (Please add to revision)**:\n\n- Please put in footnote or experimental setup in appendix the version of sacrebleu and also the version and model used in reported comet score\n- Please also report chrf scores from sacrebleu for Table 2, you can put it in the appendix if there's space constraints\n\n\n**Content Suggestions:**\n\n- Take a look at Section 2.2 of https://aclanthology.org/W16-4618 to get the mgiza software working in a quick/fast manner, use those alignments to get  (V, V∗, E) and see if it works better than the proposed method. Alternatively, there's https://www.nltk.org/api/nltk.align.html but it's rather slow.\n\n- The \"excitement\" score would be a 5 if this weakness is resolve by re-running the Table 8 experiments on:\n   - (reverse direction) FR-EN on WMT14\n   - (comparable to previous LevT work) EN-DE with lexicon on WMT14\n   - Try a lower resource language, some previous LevT papers put additional language experiments in the appendix to be supporting evidence that methods work beyond a single language pair while keeping the narrative in the main text simple. "}}]

Author rebuttal:

Meta-review: The reviewers agree that the paper presents a novel and interesting contribution and agree on a good soundness score. There were a couple of issues raised by the reviewers, that were also acknowledged by the authors, and for some I want to go a bit into more detail here.

Some reviewers complained about the paper being hard to follow and too technical at some points. While I understand the position of the reviewer, the exact mathematical notation is necessary for such complex systems and it actually makes the paper stronger, although perhaps more difficult to follow for a wider audience. Nevertheless I would encourage the authors to add some more intuitive explanation for the most complex concepts. Maybe including a fully detailed example in the appendix might help?

Another reviewer also complained about older test sets being used in the evaluation. Regretfully this is an extended "evil" among our community and the authors defended their decision arguing comparison with previous work. In the rebuttal period the authors provided evidence of generalization to another language pair. These results should definitely be included in the final version to make the paper stronger.

All in all, the paper presents an interesting contribution. In its current form there are some issues in the presentation that have been pointed out by the reviewers, but all can be addressed in a final version of the paper, making use of the extra page of content or expanding the appendix if necessary.
Decision: Accept-Main