Online alignment in machine translation refers to the task of aligning a target word to a source word when the target sequence has only been partially decoded. Good online alignments facilitate important applications such as lexically constrained translation where user-defined dictionaries are used to inject lexical constraints into the translation model. We propose a novel posterior alignment technique that is truly online in its execution and superior in terms of alignment error rates compared to existing methods. Our proposed inference technique jointly considers alignment and token probabilities in a principled manner and can be seamlessly integrated within existing constrained beam-search decoding algorithms. On five language pairs, including two distant language pairs, we achieve consistent drop in alignment error rates. When deployed on seven lexically constrained translation tasks, we achieve significant improvements in BLEU specifically around the constrained positions. Online alignment seeks to align a target word to a source word at the decoding step when the word is output in an auto-regressive neural translation model (Kalchbrenner and Blunsom, 2013; Cho et al., 2014; Sutskever et al., 2014). This is unlike the more popular offline alignment task that uses the entire target sentence (Och and Ney, 2003). State of the art methods of offline alignment based on matching of whole source and target sentences (Jalili Sabet et al., 2020; Dou and Neubig, 2021) are not applicable for online alignment where we need to commit on the alignment of a target word based on only the generated prefix thus far. An important application of online alignment is lexically constrained translation which allows injection of domain-specific terminology and other phrasal constraints during decoding (Hasler et al., 2018; Hokamp and Liu, 2017; Alkhouli et al., 2018; Crego et al., 2016). Other applications include preservation of markups between the source and target (Mller, 2017), and supporting source word edits in summarization (Shen et al., 2019). These applications need to infer the specific source token which aligns with output token. Thus, alignment and translation is to be done simultaneously. Existing online alignment methods can be categorized into Prior and Posterior alignment methods. Prior alignment methods (Garg et al., 2019; Song et al., 2020) extract alignment based on the attention at time step t when outputting token y t . The attention probabilities at time-step t are conditioned on tokens output before time t . Thus, the alignment is estimated prior to observing y t . Naturally, the quality of alignment can be improved if we condition on the target token y t (Shankar and Sarawagi, 2019). This motivated Chen et al. (2020) to propose a posterior alignment method where alignment is calculated from the attention probabilities at the next decoder step t + 1 . While alignment quality improved as a result, their method is not truly online since it does not generate alignment synchronously with the token. The delay of one step makes it difficult and cumbersome to incorporate terminology constraints during beam decoding. We propose a truly online posterior alignment method that provides higher alignment accuracy than existing online methods, while also being synchronous. Because of that we can easily integrate posterior alignment to improve lexicon-constrained translation in state of the art constrained beam-search algorithms such as VDBA (Hu et al., 2019). Our method (Align-VDBA) presents a significant departure from existing papers on alignment-guided constrained translation (Chen et al., 2020; Song et al., 2020) that employ a greedy algorithm with poor constraint satisfaction rate (CSR). For example, on a ja  en their CSR is 20 points lower than ours. Moreover, the latter does not benefit 6675 from larger beam sizes unlike VDBA-based methods that significantly improve with larger beam widths. Compared to Chen et al. (2020), our method improves average overall BLEU scores by 1.2 points and average BLEU scores around the constrained span by up to 9 points. In the evaluations performed in these earlier work, VDBA was not allocated the slightly higher beam size needed to pro-actively enforce constraints without compromising BLEU. Compared to Hu et al. (2019) (VDBA), this paper's contributions include online alignments and their use in more fluent constraint placement and efficient allocation of beams. Contributions  A truly online posterior alignment method that integrates into existing NMT sytems via a trainable light-weight module. Higher online alignment accuracy on five language pairs including two distant language pairs where we improve over the best existing method in seven out of ten translation tasks. Principled method of modifying VDBA to incorporate posterior alignment probabilities in lexically-constrained decoding. VDBA enforces constraints ignoring source alignments; our change (Align-VDBA) leads to more fluent constraint placement and significant BLEU increase particularly for smaller beams. Establishing that VDBA-based pro-active constrained inference should be preferred over prevailing greedy alignment-guided inference (Chen et al., 2021; Song et al., 2020). Further, VDBA and our Align-VDBA inference with beam size 10 provide 1.2 BLEU increase over these methods with the same beam size. Given a sentence x = x 1 , . . . , x S in the source language and a sentence y = y 1 , . . . , y T in the target language, an alignment A between the word strings is a subset of the Cartesian product of the word positions (Brown et al., 1993; Och and Ney, 2003): A  { ( s, t ) : s = 1 , . . . , S ; t = 1 , . . . , T } such that the aligned words can be considered translations of each other. An online alignment at time-step t commits on alignment of the t th output token conditioned only on x and y <t = y 1 , y 2 , . . . y t  1 . Additionally, if token y t is also available we call it a posterior online alignment. We seek to embed online alignment with existing NMT systems. We will first briefly describe the architecture of state of the art NMT systems. We will then elaborate on how alignments are computed from attention distributions in prior work and highlight some limitations, before describing our proposed approach. Transformers (Vaswani et al., 2017) adopt the popular encoder-decoder paradigm used for sequence-to-sequence modeling (Cho et al., 2014; Sutskever et al., 2014; Bahdanau et al., 2015). The encoder and decoder are both multi-layered networks with each layer consisting of a multi-headed self-attention and a feedforward module. The decoder layers additionally use multi-headed attention to encoder states. We elaborate on this mechanism next since it plays an important role in alignments. 2.1.1 Decoder-Encoder Attention in NMTs The encoder transforms the S input tokens into a sequence of token representations H  RS  d . Each decoder layer (indexed by (cid:96)  { 1 , . . . , L } ) computes multi-head attention over H by aggregating outputs from a set of  independent attention heads. The attention output from a single head n  { 1 , . . . ,  } in decoder layer (cid:96) is computed as follows. Let the output of the self-attention sub-layer in decoder layer (cid:96) at the t th target token be denoted as g (cid:96)t . Using three projection matrices W (cid:96),nQ , W (cid:96),nV , W (cid:96),nK  R d  d n , the query vector q (cid:96),nt  R 1  d n and key and value matrices, K (cid:96),n  RS  d n and V (cid:96),n  RS  d n , are computed using the following projections: q (cid:96),nt = g (cid:96)t W (cid:96),nQ , K (cid:96),n = HW (cid:96),nK , and V (cid:96),n = HW (cid:96),nV . 1 These are used to calculate the attention output from head n , Z (cid:96),nt = P ( a (cid:96),nt | x , y <t ) V (cid:96),n , where: P ( a (cid:96),nt | x , y <t ) = softmax (cid:32) q (cid:96),nt ( K (cid:96),n ) (cid:124)  d (cid:33) (1) For brevity, the conditioning on x , y <t is dropped and P ( a (cid:96),nt ) is used to refer to P ( a (cid:96),nt | x , y <t ) in the following sections. Finally, the multi-head attention output is given by [ Z (cid:96), 1 t , . . . , Z (cid:96),t ] WO where [ ] denotes the column-wise concatenation of matrices and WO  R d  d is an output projection matrix. Several prior work have proposed to extract word alignments from the above attention prob-1 abilities. For example Garg et al. (2019) propose a simple method called NAIVEATT that aligns a source word to the t th target token using argmax j 1   (cid:88) n =1 P ( a (cid:96),nt,j | x , y <t ) where j indexes the source tokens. In NAIVEATT, we note that the attention probabilities P ( a (cid:96),nt,j | x , y <t ) at decoding step t are not conditioned on the current output token y t . Alignment quality would benefit from conditioning on y t as well. This observation prompted Chen et al. (2020) to extract alignment of token y t using attention P ( a (cid:96),nt,j | x , y  t ) computed at time step t + 1 . The asynchronicity inherent to this shift-by-one approach (SHIFTATT) makes it difficult and more computationally expensive to incorporate lexical constraints during beam decoding. We propose POSTALN that produces posterior alignments synchronously with the output tokens, while being more computationally efficient compared to previous approaches like SHIFTATT. We incorporate a lightweight alignment module to convert prior attention to posterior alignments in the same decoding step as the output. Figure 1 illustrates how this alignment module fits within the standard Transformer architecture. The alignment module is placed at the penultimate decoder layer (cid:96) = L  1 and takes as input (1) the encoder output H , (2) the output of the self-attention sub-layer of decoder layer (cid:96) , g (cid:96)t and, (3) the embedding of the decoded token e ( y t ) . Like in standard attention it projects H to obtain a key matrix, but to obtain the query matrix it uses both decoder state g (cid:96)t (that summarizes y <t ) and e ( y t ) to compute the posterior alignment P ( a post t ) as: P ( a post t ) = 1   (cid:88) n =1 softmax (cid:18) q n t, post ( K n post ) (cid:124)  d (cid:19) , q nt, post = [ g (cid:96)t , e ( y t )] W nQ, post , K n post = HW nK, post Here W nQ, post  R 2 d  d n and W nK, post  R d  d n . This computation is synchronous with producing the target token y t , thus making it compatible with beam search decoding (as elaborated further in Section 3). It also accrues minimal computational overhead since P ( a post t ) is defined using H and g L  1 t , that are both already cached during a standard decoding pass. Note that if the query vector q nt, post is computed using only g L  1 t , without concatenating e ( y t ) , then we get prior alignments Inputs x Input Emb PositionalEncoding Layer 1 Layer 2 Layer L H Outputs y <t Output Emb PositionalEncoding Layers 1 to   1 Self-Attention Add and Norm Cross-Attention AlignmentModule Add and Norm Feed Forward Add and Norm Layers  + 1 to L Linear & Softmax Output Probabilities AlignmentProbabilities y t g t Figure 1: Our alignment module is an encoder-decoder attention sub-layer, similar to the existing cross-attention sub-layer. that we refer to as PRIORATT. In our experiments, we explicitly compare PRIORATT with POSTALN to show the benefits of using y t in deriving alignments while keeping the rest of the architecture intact. Training Our posterior alignment sub-layer is trained using alignment supervision, while freezing the rest of the translation model parameters. Specifically, we train a total of 3 d 2 additional parameters across the matrices W nK, post and W nQ, post . Since gold alignments are very tedious and expensive to create for large training datasets, alignment labels are typically obtained using existing techniques. We use bidirectional symmetrized SHIFTATT alignments, denoted by S i,j that refers to an alignment between the i th target word and the j th source word, as reference labels to train our alignment sub-layer. Then the objective (following Garg et al. (2019)) can be defined as: max W nQ, post , W nK, post 1 TT (cid:88) i =1 S (cid:88) j =1 S i,j log( P ( a post i,j | x , y  i )) Next, we demonstrate the role of posterior online alignments on an important downstream task. In the lexicon constrained translation task, for each to-be-translated sentence x , we are given a set of source text spans and the corresponding target tokens in the translation. A constraint C j comprises a pair ( C xj , C yj ) where C xj = ( p j , p j + 1 . . . , p j + (cid:96) j ) indicates input token positions, and C yj = ( y j 1 , y j 2 . . . , y jm j ) denote target tokens that are translations of the input tokens x p j . . . x p j + (cid:96) j . For the output tokens we do not know their positions in the target sentence. The different constraints are non-overlapping and each is expected to be used exactly once. The goal is to translate the given sentence x and satisfy as many constraints in C = (cid:83) j C j as possible while ensuring fluent and correct translations. Since the constraints do not specify target token position, it is natural to use online alignments to guide when a particular constraint is to be enforced. Existing inference algorithms for incorporating lexicon constraints differ in how pro-actively they enforce the constraints. A passive method is used in Song et al. (2020) where constraints are enforced only when the prior alignment is at a constrained source span. Specifically, if at decoding step t , i = argmax i (cid:48) P ( a t,i (cid:48) ) is present in some constraint C xj , the output token is fixed to the first token y j 1 from C yj . Otherwise, the decoding proceeds as usual. Also, if the translation of a constraint C j has started, the same is completed ( y j 2 through y jm j ) for the next m j  1 decoding steps before resuming unconstrained beam search. The pseudocode for this method is provided in Appendix G. For the posterior alignment methods of Chen et al. (2020) this leads to a rather cumbersome inference (Chen et al., 2021). First, at step t they predict a token  y t , then start decoding step t + 1 with  y t as input to compute the posterior alignment from attention at step t + 1 . If the maximum alignment is to the constrained source span C xj they revise the output token to be y j 1 from C yj , but the output score for further beam-search continues to be of  y t . In this process both the posterior alignment and token probabilities are misrepresented since they are both based on  y t instead of the finally output token y j 1 . The decoding step at t + 1 needs to be restarted after the revision. The overall algorithm continues to be normal beam-search, which implies that the constraints are not enforced pro-actively. Many prior methods have proposed more proactive methods of enforcing constraints, including the Grid Beam Search (GBA, Hokamp and Liu (2017)), Dynamic Beam Allocation (DBA, Post and Vilar (2018)) and Vectorized Dynamic Beam Allocation (VDBA, Hu et al. (2019)). The latest of these, VDBA, is efficient and available in pub-lic NMT systems (Ott et al., 2019; Hieber et al., 2020). Here multiple banks , each corresponding to a particular number of completed constraints, are maintained. At each decoding step, a hypothesis can either start a new constraint and move to a new bank or continue in the same bank (either by not starting a constraint or progressing on a constraint mid-completion). This allows them to achieve near 100% enforcement. However, VDBA enforces the constraints by considering only the target tokens of the lexicon and totally ignores the alignment of these tokens to the source span. This could lead to constraints being placed at unnatural locations leading to loss of fluency. Examples appear in Table 4 where we find that VDBA just attaches the constrained tokens at the end of the sentence. We modify VDBA with alignment probabilities to better guide constraint placement. The score of a constrained token is now the joint probability of the token, and the probability of the token being aligned with the corresponding constrained source span. Formally, if the current token y t is a part of the j th constraint i.e. y t  C yj , the generation probability of y t , P ( y t | x , y <t ) is scaled by multiplying with the alignment probabilities of y t with C xj , the source span for constraint i . Thus, the updated probability is given by: P ( y t , C xj | x , y <t ) (cid:124) (cid:123)(cid:122) (cid:125) Joint Prob = P ( y t | x , y <t ) (cid:124) (cid:123)(cid:122) (cid:125) Token Prob (cid:88) r C xj P ( a post t,r | x , y  t ) (cid:124) (cid:123)(cid:122) (cid:125) Src Align. P ( y t , C xj | x , y <t ) denotes the joint probability of outputting the constrained token and the alignment being on the corresponding source span. Since the supervision for the alignment probabilities was noisy, we found it useful to recalibrate the alignment distribution using a temperature scale T , so that the recalibrated probability is  Pr( a post t,r | x , y  t ) 1 T . We used T = 2 i.e., square-root of the alignment probability. Currently, VDBA attempts beam allocation for each unmet constraint since it has no way to discriminate. In Align-VDBA we allocate only when the alignment probability is greater than a threshold. When the beam size is small (say 5) this yields higher accuracy due to more efficient beam utilization. We used a threshold of 0.1 for all language pairs other than ro  en for which a threshold of 0.3 was used. Further, the thresholds were used for the smaller beam size of 5 and not for larger beam sizes of 10 and 20. We present the pseudocode of our modification (steps 5, 6 and 7, in blue) to DBA in Algorithm 1. Other details of the algorithm including the handling of constraints and the allocation steps (step 11) are involved and we refer the reader to Post and Vilar (2018) and Hu et al. (2019) to understand these details. The point of this code is to show that our proposed posterior alignment method can be easily incorporated into these algorithms so as to provide a more principled scoring of constrained hypothesis in a beam than the ad hoc revision-based method of Chen et al. (2021). Additionally, posterior alignments lead to better placement of constraints than in the original VDBA algorithm. We first compare our proposed posterior online alignment method on quality of alignment against existing methods in Section 4.2, and in Section 4.3, we demonstrate the impact of the improved alignment on the lexicon-constrained translation task. We deploy the fairseq toolkit (Ott et al., 2019) and use transformer_iwslt_de_en pre-configured model for all our experiments. Other configuration parameters include: Adam optimizer with  1 = 0 . 9 ,  2 = 0 . 98 , a learning rate of 5e  4 de-en en-fr ro-en en-hi ja-en Training 1.9M 1.1M 0.5M 1.6M 0.3M Validation 994 1000 999 25 1166 Test 508 447 248 140 1235 Table 1: Number of sentence pairs for the five datasets used. with 4000 warm-up steps, an inverse square root schedule, weight decay of 1e  4 , label smoothing of 0 . 1 , 0 . 3 probability dropout and a batch size of 4500 tokens. The transformer models are trained for 50,000 iterations. Then, the alignment module is trained for 10,000 iterations, keeping the other model parameters fixed. A joint byte pair encoding (BPE) is learned for the source and the target languages with 10k merge operation (Sennrich et al., 2016) using subword-nmt . All experiments were done on a single 11GB Nvidia GeForce RTX 2080 Ti GPU on a machine with 64 core Intel Xeon CPU and 755 GB memory. The vanilla Transformer models take between 15 to 20 hours to train for different datasets. Starting from the alignments extracted from these models, the POSTALN alignment module trains in about 3 to 6 hours depending on the dataset. We evaluate online alignments on ten translation tasks spanning five language pairs. Three of these are popular in alignment papers (Zenkel et al., 2019): German-English (de-en), English-French (en-fr), Romanian-English (ro-en). These are all European languages that follow the same subject-verb-object (SVO) ordering. We also present results on two distant language pairs, English-Hindi (en-hi) and English-Japanese (ja-en), that follow a SOV word order which is different from the SVO 6679 D e l a y de-en en-fr ro-en en-hi ja-en Method de  en en  de en  fr fr  en ro  en en  ro en  hi hi  en ja  en en  ja Statistical Methods (Not Online) GIZA++ (Och and Ney, 2003) End 18.9 19.7 7.3 7.0 27.6 28.3 35.9 36.4 41.8 39.0 FastAlign (Dyer et al., 2013) End 28.4 32.0 16.4 15.9 33.8 35.5 --No Alignment Training NAIVEATT (Garg et al., 2019) 0 32.4 40.0 24.0 31.2 37.3 33.2 49.1 53.8 62.2 63.5 SHIFTATT (Chen et al., 2020) +1 20.0 22.9 14.7 20.4 26.9 27.4 35.3 38.6 53.6 48.6 With Alignment Training PRIORATT 0 23.4 25.8 14.0 16.6 29.3 27.2 36.4 35.1 52.7 50.9 SHIFTAET (Chen et al., 2020) +1 15.8 19.5 10.3 10.4 22.4 23.7 29.3 29.3 42.5 41.9 POSTALN [Ours] 0 15.5 19.5 9.9 10.4 21.8 23.2 28.7 28.9 41.2 42.2 Table 2: AER for de-en, en-fr, ro-en, en-hi, ja-en language pairs. Evaluation Method: For evaluating alignment performance, it is necessary that the target sentence is exactly the same as for which the gold alignments are provided. Thus, for the alignment experiments, we force the output token to be from the gold target and only infer the alignment. We then report the Alignment Error Rate (AER) (Och and Ney, 2000) between the gold alignments and the predicted alignments for different methods. Though our focus is online alignment, for comparison to previous works, we also report results on bidirectional symmetrized alignments in Appendix D. Methods compared : We compare our method with both existing statistical alignment models, namely GIZA++ (Och and Ney, 2003) and FastAlign (Dyer et al., 2013), and recent Transformer-based alignment methods of Garg et al. (2019) (NAIVEATT) and Chen et al. (2020) (SHIFTATT and SHIFTAET). Chen et al. (2020) also propose a variant of SHIFTATT called SHIFTAET that delays computations by one time-step as in SHIFTATT, and additionally includes a learned attention sublayer to compute alignment probabilities. We also present results on PRIORATT which is similar to POSTALN but does not use y t . Results: The alignment results are shown in Table 2. First, AERs using statistical methods FastAlign and GIZA++ are shown. Here, for fair comparison, the IBM models used by GIZA++ are trained on the same sub-word units as the Transformer models and sub-word alignments are converted to word level alignments for AER calculations. (GIZA++ has remained a state-of-the-art alignment technique and continues to be compared against.) Next, we present alignment results for two vanilla Transformer models NAIVEATT and SHIFTATT that do not train a separate alignment module. The high AER of NAIVEATT shows that attention-as-is is very distant from alignment but posterior attention is closer to alignments than prior. Next we look at methods that train alignment-specific parameters: PRIORATT, a prior attention method; SHIFTAET and POSTALN , both posterior alignment methods. We observe that with training even PRIORATT has surpassed non-trained posterior. The posterior attention methods outperform the prior attention methods by a large margin, with an improvement of 4.0 to 8.0 points. Within each group, the methods with a trained alignment module outperform the ones without by a huge margin. POSTALN performs better or matches the performance of SHIFTAET (achieving the lowest AER in nine out of ten cases in Table 2) while avoiding the one-step delay in alignment generation. Even on the distant languages, POSTALN achieves significant reductions in error. For ja  en, we achieve a 1.3 AER reduction compared to SHIFTAET which is not a truly online method. Figure 2 shows examples to illustrate the superior alignments of POSTALN compared to NAIVEATT and PRIORATT. We next depict the impact of improved AERs from our posterior alignment method on a downstream lexicon-constrained translation task. Following previous work (Hokamp and Liu, 2017; Post and Vilar, 2018; Song et al., 2020; Chen et al., 2020, 2021), we extract constraints using the gold alignments and gold translations. Up to three constraints of up to three words each are used for each sentence. Spans correctly translated by a greedy decoding 6680 a u c h k  nn e n d i e s d i e z u s t  n d i g e n i nn e r @@ s t aa t li c h e n b e h  r d e n r e g e l n , s o f e r n s i ee s f  r e r f o r d e r li c h h a l t e n . Metrics: Following prior work (Song et al., 2020), we report BLEU (Papineni et al., 2002), time to translate all test sentences, and Constraint Satisfaction Rate (CSR). However, since it is trivial to get 100% CSR by always copying, we report another metric to evaluate the appropriateness of constraint placement: We call this measure BLEU-C and compute it as the BLEU of the constraint (when satisfied) and a window of three words around it. All numbers are averages over five different sets of randomly sampled constraint sets. The beam size is set to ten by default; results for other beam sizes appear in Appendix E. Methods Compared: First we compare all the alignment methods presented in Section 4.2 on the constrained translation task using the alignment based token-replacement algorithm of Song et al. (2020) described in Section 3.1. Next, we present a comparison between VBDA (Hu et al., 2019) and our modification Align-VDBA. Results: Table 3 shows that VDBA and our Align-VDBA that pro-actively enforce constraints have a much higher CSR and BLEU-C compared to the other lazy constraint enforcement methods. For example, for ja  en greedy methods can only achieve a CSR of 76% compared to 96% of the VDBA-based methods. In terms of overall BLEU too, these methods provide an average increase in BLEU of 1.2 and an average increase in BLEU-C of 5 points. On average, Align-VDBA has a 0.7 point greater BLEU-C compared to VDBA. It also has a greater BLEU than VDBA on all the five datasets. In Table 9 of Appendix we show that for smaller beamsize of 5, the gap between Align-VDBA and VDBA is even larger (2.1 points greater BLEU-C and 0.4 6681 Constraints (gesetz zur, law also ), (dealer, pusher ) Gold of course, if a drug addict becomes a pusher , then it is right and necessary that he should pay and answer before the law also . points greater BLEU). Table 4 lists some example translations by VDBA vs. Align-VDBA. We observe that VDBA places constraints at the end of the translated sentence (e.g., pusher", develop-ment") unlike Align-VDBA. In some cases where constraints contain frequent words (like of, the, etc.), VDBA picks the token in the wrong position to tack on the constraint (e.g., strong backing of", of qualified") while Align-VDBA places the constraint correctly. Real World Constraints: We also evaluate our method using real world constraints extracted from IATE and Wiktionary datasets by Dinu et al. (2019). Table 5 compares Align-VDBA with the soft-constraints method of Dinu et al. (2019) that requires special retraining to teach the model to copy constraints. We reproduced the numbers from their paper in the first three rows. Their baseline is almost 4 BLEU points worse than ours since they used a smaller transformer NMT model, thus making running times incomparable. When we compare the increment  in BLEU over the respective baselines, Align-VDBA shows much greater gains of +1.2 vs. their +0.5. Also, Align-VDBA provides a larger CSR of 99.6 compared to their 92. Results for other beam sizes and other methods and metrics appear in Appendix F. 5 Related Work Online Prior Alignment from NMTs : Zenkel et al. (2019) find alignments using a single-head attention submodule, optimized to predict the next token. Garg et al. (2019) and Song et al. (2020) supervise a single alignment head from the penultimate multi-head attention with prior alignments from GIZA++ alignments or FastAlign. Bahar et al. (2020) and Shankar et al. (2018) treat alignment as a latent variable and impose a joint distribution over token and alignment while supervising on the token marginal of the joint distribution. Online Posterior Alignment from NMTs : Shankar and Sarawagi (2019) first identify the role of posterior attention for more accurate alignment. However, their NMT was a single-headed RNN. Chen et al. (2020) implement posterior attention in a multi-headed Transformer but they incur a delay of one step between token output and alignment. We are not aware of any prior work that extracts truly online posterior alignment in modern NMTs. Offline Alignment Systems : Several recent methods apply only in the offline setting: Zenkel et al. (2020) extend an NMT with an alignment module; Nagata et al. (2020) frame alignment as a question answering task; and Jalili Sabet et al. (2020); Dou and Neubig (2021) leverage similarity between contextual embeddings from pretrained multilingual models (Devlin et al., 2019). (2019) modify beam search to ensure that target phrases from a given constrained lexicon are present in the translation. These methods ignore alignment with the source but ensure high success rate for appearance of the target phrases in the constraint. Song et al. (2020) and Chen et al. (2021) do consider source alignment but they do not enforce constraints leading to lower CSR. Dinu et al. (2019) and Lee et al. (2021) propose alternative training strategies for constraints, whereas we focus on working with existing models. Recently, non autoregressive methods have been proposed for enforcing target constraints but they require that the constraints are given in the order they appear in the target translation (Susanto et al., 2020). In this paper we proposed a simple architectural modification to modern NMT systems to obtain accurate online alignments. The key idea that led to high alignment accuracy was conditioning on the output token. Further, our designed alignment module enables such conditioning to be performed synchronously with token generation. This property led us to Align-VDBA, a principled decoding algorithm for lexically constrained translation based on joint distribution of target token and source alignments. Future work includes increase efficiency of constrained inference and harnessing such joint distributions for other forms of constraints, for example, nested constraints. Limitations: All existing methods for hard constrained inference, including ours, come with considerable runtime overheads. Soft constrained methods are not accurate enough. We are grateful to the reviewers for their detailed analysis, thoughtful comments and insightful questions which have helped us improve the paper. We are grateful to Priyesh Jain for providing alignment annotations for 50 English-Hindi sentences.
abstain abstain objective objective result result abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain objective result result abstain abstain result abstain abstain objective result objective result objective method other abstain abstain method abstain abstain other other other abstain other other other other other other other abstain abstain abstain abstain abstain abstain abstain method method abstain abstain other abstain abstain method method method method method abstain method method abstain other abstain abstain abstain abstain other other other other other other other other other other other other other other other other other other abstain method abstain abstain other abstain abstain method abstain abstain abstain method abstain method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain result abstain result abstain abstain abstain abstain result abstain abstain result abstain abstain abstain abstain result abstain abstain abstain abstain other method method abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain objective abstain method abstain abstain abstain abstain other other