{'fraction_non_alphanumeric': 0.034070249436404625, 'fraction_numerical': 0.01232637626354447, 'mean_word_length': 4.623185442649765, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Easy Guided Decoding in Providing Suggestions for Interactive Machine Translation

Fully machine translation scarcely guarantees error-free results. Humans perform post-editing on machine generated translations to correct errors in the scenario of computer aided translation. In favor of expediting the post-editing process, recent works have investigated machine translation in an interactive mode, where machines can automatically refine the rest of translations constrained on human's edits. In this paper, we utilize the parameterized objective function of neural machine translation and propose an easy constrained decoding algorithm to improve the translation quality without additional training. We demonstrate its capability and time efficiency on a benchmark dataset, WeTS, where it conditions on humans' guidelines by selecting spans with potential errors. In the experimental results, our algorithm is significantly superior to state-of-the-art lexically constrained decoding method by an increase of 10.37 BLEU in translation quality and a decrease of 63.4% in time cost on average. It even outperforms the benchmark systems trained with a large amount of annotated data on WeTS in English-German and German-English.


Introduction
Human translation is expensive and slow. The emergence of machine translation technology (Lopez 2008;Koehn 2009) assists human translation to improve efficiency and save costs (Green et al. 2014;Green, Heer, and Manning 2015). Even though there is still a quality gap between outputs of machine translation systems and manual translations by professional translators, it can practically reduces time that humans modify machine translation (MT) results (Läubli et al. 2013) rather than translate from scratch. It is called computer aided translation (CAT). Later, the explosive advances in the sequence to sequence model (Sutskever, Vinyals, and Le 2014;Bahdanau, Cho, and Bengio 2014;Vaswani et al. 2017) further make a breakthrough in translation technology, inspiring the industry to transform human translation to CAT (Knowles and Koehn 2016;Santy et al. 2019) to a great extent. CAT improves human's efficiency during translation/post-editing process that usually relies on a MT engine and a working platform with user-friendly interface (Bowker 2002;Lengyel et al. 2004;Bowker and Fisher 2010;Bowker 2014;Chatterjee 2019). Humans edit machine generated translations to achieve final results with quality in users' standards. The more powerful the translation engine, the more efficient the post-editing process.
Before, the post-editing process was typically static that machines would no longer respond to humans' modifications once humans started post-editing. Recent works (Domingo, Peris, and Casacuberta 2016;González-Rubio et al. 2016;Peris, Domingo, and Casacuberta 2017) investigate interactive protocols and algorithms so that humans and machines can collaborate and machines automatically refine the translations according to humans' operations in the process. One promising mode is Translation Suggestion (TS) (Yang et al. 2021), which requires machines to provide alternatives for specific spans of words given the machine generated contexts around. In practical applications, it usually happens when human translators would like to edit part of words in the entire document generated by machines. It is convenient if machines correctly provide suggestions for the selected spans with potential translation errors, and Wang et al. (2020) has shown its efficiency in post-editing. The importance of Translation Suggestion is also recognized by the Conference of Machine Translation (WMT), and they have decided to release this task in WMT 2022 2 . Yang et al. (2021) released a benchmark dataset for TS, WeTS, and trained an end-to-end Transformer-like model on it as baseline. The supervised model, which relies on a large amount of labeled data, is too heavy to be applied to other domains and languages. In addition, to say the least, due to the relatively complicated post-editing process, it is hard and expensive to obtain such annotated data.
One of the key solutions to TS can be inference with decoding algorithms given prefix and suffix constraints. Suggestions of spans with translation errors in the MT results need to be generated with the constrained decoding algorithm. We applied state-of-the-art lexically constrained decoding algorithms (Post and Vilar 2018;Hu et al. 2019) on the WeTS dataset, and found that omissions occur frequently that could not be accepted. There are two reasons behind regarding their methods: (1) the division of beams in their dy-namic beam allocation narrow the search space so that there would not be enough candidates that match constraints to be picked, especially in the situation when constraints are long and spans selected contain less than 10 percent of words in the MT results on average, such as TS; (2) their beam search stops at the step when the probability of eos, the sepcial token for the end of sentence, appears largest in the softmax distribution, but they didn't consider the probability of the entire generation. What's worse, their decoding method generates the translation step by step from the beginning of the translation to the end of the sentence, even when the prefix and suffix constraints are given. In terms of calculation cost, this way is very expensive, especially in TS where prefix and suffix constraints are particularly long.
In this paper, we utilize the objective function of the training of neural machine translation (NMT) and propose an prefix-suffix guided decoding (PSGD) algorithm for the Translation Suggestion task. Starting from the next word generation based on the prefix constraint, we adopt the typical auto-regressive decoding method from left to right, but allow the decoding to continue until the probability of the whole generation including the suffix constraint reaches the maximum rather than eos is met. This mechanism emphasizes the entire document generation, which is more important in constrained decoding in CAT. Our algorithm does not need to divide beams as in Hu et al. (2019), and therefore the quality of the generated translation suggestion is more guaranteed with the original beam search space.
Moreover, PSGD is more efficient since it just generates the span selected by humans rather than the whole sentence. In the scene of Translation Suggestion, when the prefix and suffix constraints are much longer than the average length of spans with potential errors in the MT results, PSGD saves more time. In our experimental results, PSGD is significantly superior to state-of-the-art lexically constrained decoding method by an increase of 10.37 BLEU in translation quality and a decrease of 63.4% in time cost on average. It even outperforms the TS benchmark systems trained with a large amount of annotated data on WeTS in English-German and German-English.

Related Work
Some related works have been explored in computer aided translation. Wuebker et al. (2016) and Knowles and Koehn (2016) proposed a NMT Interactive Translation Prediction (ITP) method, focusing on how to complete partial translations of words or phrases given a prefix. Santy et al. (2019) further presented an interactive translation system conditioned on hints from translators on low-resource language pairs. These post-editing applications paid attention to the overall performance but ignored the performance on suggestion parts. Yang et al. (2021) proposed the translation suggestion benchmark, and extensively took the performance of the suggested words or phrases into consideration, which would be highly appreciated in practical applications.
As for the constrained decoding algorithms, previous works tried to support lexical constraints when decoding with generative models. Hokamp and Liu (2017) introduced Symbol Definition x Sentence in source language y Translated sentence in target language p A given prefix of y s A given suffix of y r The remained part of y after p and s are removed t p The number of tokens in p t s The number of tokens in s t r The number of tokens in r bos The special begin of sentence token used in machine translation eos The special end of sentence token used in machine translation y i The i-th token of y, similar for The estimation/prediction of y, similar for Θ,r,r j , etc. v <t The first t tokens of sequence v v 1 , ..., v n Concatenation of sequences v 1 , ..., v n P MT The probabilistic model of machine translation P (n) r The probability of the entire sequence after the n-th decoding step for the remain part r pt Patience for decoding early stopping f (y t ) The softmax probability distribution at the t-th decoding step Grid Beam Search (GBS), modifying the inference procedure to promise the hard lexical constraints without iterating model parameters on any additional training data. Anderson et al. (2017) used the constrained beam search (CBS) for object captioning in image, which extends beam search by marking the constraints status with a finite-state machine. However, these two methods have linear and exponential computational complexities in the number of constraints respectively. Post and Vilar (2018) proposed Dynamic Beam Allocation (DBA) with O(1) computational complexities in the number of provided constraints. It tries to allocate slots in the beam to ensure a fixed-sized beam during generations regardless of the number of constraints. Another improved work, VDBA, was proposed by Hu et al. (2019), which accelerates decoding by using dynamic vectorization for batch decoding. Besides, VDBA uses a multi-state tries to avoid certain corners in DBA to further improve the translation quality. Considering the advantages of VDBA (Hu et al. 2019), we mainly regard it as the comparison algorithm.

Preliminary
Before introducing our Prefix-Suffix Guided Decoding (PSGD) algorithm, we first elaborate on the problem in the scene of TS with the mathematical notations in Table 1 Table 2: BLEU results on the WeTS test sets. PSGD outperforms VDBA by +10.37 BLEU on average, and it also outperforms the TS benchmark systems, SA-Transformer, trained with annotated data in German-English and English-German.
Transformer Decoder Transformer Encoder sequence-to-sequence machine translation model is generally a conditional auto-regressive language model that follows the factorized probability distribution.
Given enough training pairs of (x, y), maximizing the probability in Formula 1 will return an estimate of the model parameter,Θ. During inference, we are supposed to maximize the probability of the generated sequence: However, the solution space {y} is infinitive and impossible to search. Therefore, an auto-regressive decoding process is applied in practice. The decoder of the model decodes the sequence step by step greedily 3 as following until eos is decoded: In the scene of TS, a span r is masked for suggestion generation, and thus we need to guarantee that y starts with the given prefix p and ends with the given suffix s. Then, the problem becomes:

Methodology
As noted previously, prior algorithms for constrained decoding require step-by-step generations for the whole sentence even with prefix and suffix constraints. It causes efficiency issues especially when the constraints are long. 3 We don't involve beam-search here to simplify the equations, but in practice all our experiments are conducted with beam-search Algorithm 1: Algorithm of PSGD Input: x, p, s Parameter: pt Output: Considering that only one span requires alternative in TS, we propose a novel prefix and suffix guided decoding algorithm, that can generate sequence given prefix and suffix through maximizing the probability of the whole generated sequence. Instead of generating the whole sequence, PSGD only performs a step-by-step beam search generation for the span. At the same time, there is no need to divide beams in PSGD. Therefore, our algorithm can achieve higher quality while reducing the time cost for TS.

Decoding Process for TS
Similar to normal translation process, we apply the autoregressive decoding process here to overcome the issue of infinitive solution space {r}.
We can factorize the entire probability in Formula 4 into three parts: Notice that in Formula 5, as all p i and s k are given, only the second product indicates a step-by-step auto-regressive generation. The first product, referring to the probability of the prefix sequence p, can be calculated at the first step when r 1 is decoded. And when all of the decoding steps of r are completed, we can easily obtain the third product, which refers to the probability of the suffix sequence s. Hence, the decoding process at each step is actually: Theoretically, we only need to go forward through the model for t r times, which is smaller than that of a normal constraints decoding, i.e. t p + t r + t s . In particular, for the TS task, human translators might select a short span with errors, and then t p + t s could be larger than t r .

Condition for Stopping Decoding
The decoding process aforementioned is straightforward. Now, it comes to a problem: when should the decoding inference stop? In Post and Vilar (2018) and Hu et al. (2019), the model generates the full sequence and the generation stops when the eos is met. In comparison, in our PSGD, only the span r will be generated and r does not end with eos.
The key to solve this problem can be aligned with the objective function of NMT training as described in Formula 1. Assume that we have finished the decoding in Formula 6 for N steps, where N is large enough to obtain a hypothesis sequence r * . The solution space {r} becomes {r * <n } N n=1 . The most optimal sequence should satisfy: r = r * <n , wheren = max n P M T ( p, r * <n , s |x;Θ) (7) The normal decoding process stops when eos is reached, and it does not necessarily mean the probability of the entire sequence generation is maximized. In other words, there might be a better hypothesis if the model generates for fewer or more steps in the normal decoding process. Our condition for stop decoding in PSGD approaches the training objective function in Formula 1 as much as possible. It approximately maximizes the probability of the entire generated sequence. This is the reason why PSGD achieves better performance.
Early Stopping Though this simple workaround in PSGD provides a proper condition for stopping decoding, it might cause efficiency issues since the introduction of the hyperparameter N . And the number of decoding steps becomes N rather than t r . Obviously, N should be at least t r to achieve the best performance. However, in practice, we have no idea how large t r is. We have to set N to a very large value to cover as many cases as possible, which is unacceptable in practice.
Instead of setting a large N , we try to apply an early stopping mechanism to save unnecessary decoding steps, while it still makes sure N will be larger than t r . In Formula 6, after every decoding step, PSGD calculates and records the probability of entire sequence generation with both prefix and suffix concatenated, denoted as P (n) r as follows: and PSGD simply stops decoding when P (n) r does not increase within pt consecutive steps, where pt indicates patience for early stopping.
Parallel Acceleration Because the early stopping mechanism requires extra calculations for P (n) r at each step, it seems that we need to go forward through the model for 2 * (r t + pt) times. In fact, by utilizing the future mask in Transformer's decoder, we only need to run r t + pt times by obtaining P (n) r andr n+1 at one time, which will be explained in the following paragraph. Figure 1 shows the forward path for calculating P r , where f (ŷ t ) is the softmax probability distribution at the t-th decoding step, and f (y|y t ) indicates the probability of token y at (t+1)-th step, which is short for P M T (y|ŷ ≤t , x;Θ). We have: P (n) r =f (p 1 |bos) · f (p 2 |p 1 ) · · · · · f (p tp |p tp−1 ) · f (r 1 |t p ) ·f (r 2 |r 1 ) · · · · · f (r n |r n−1 ) · f (s 1 |r n ) ·f (s 2 |s 1 ) · · · · · f (s ts |s ts−1 ) · f (eos|s ts ) (9) and r n+1 = max r P MT (r| p,r <n , x) = max r f (p 1 |bos) · f (p 2 |p 1 ) · · · · · f (p tp |p tp−1 ) · f (r 1 |t p ) ·f (r 2 |r 1 ) · · · · · f (r n |r n−1 ) · f (r|r n ) = max r f (r|r n ) (10) At the n-th step, we obtain all outputs' probability distributions f (p i ), f (r j ), and f (s k ) at one time. Afterwards, according to Formula 9 and 10, P (n) r (the probability of entire sequence used for early stopping) andr n+1 (the token generated for next step) can be obtained together. Therefore, the total step for of the auto-regressive decoding in PSGD is t r + pt.

Summary
In this section, we provide full details of PSGD for interactive machine translation, where only one span in the MT result r requires an alternative. We adopt the step-by-step auto-regressive decoding for the span instead of the whole sequence, and utilize the parameterized objective function of the NMT model to determine the stop condition. With the early-stopping mechanism and parallel acceleration ofr n+1 and P (n) r , only t r + pt decoding steps are required in PSGD, which is smaller than t p + t r + t s in Hu et al. (2019) on average, especially in the scene of TS where t r is much smaller than t p + t s . Besides, in PSGD, the condition to stop decoding matches better with the training objective function so that the model generates higher-quality suggestions. The pseudo code of the PSGD is presented in Algorithm 1.

Experiments Generation Performance on Translation Suggestion
Dataset Translation suggestion is a typical CAT task where the human translator marks an incorrect word span in the MT result and it is interested in models to provide alternative for the span. WeTS (Yang et al. 2021) is the benchmark dataset for the TS task. Each sample consists of a source sentence, a masked MT sentence and a golden reference corresponding to the masked span. The masked spans with potential errors are selected by humans. The annotations mainly focus on three types of translation errors: under(over)-translation, grammatical or syntactic errors, and semantic errors.
Evaluation We use Sacre-BLEU score (Post 2018) as the metric between the golden references of the masked span and the alternatives generated to measure the performance.
Baseline We compare our method with two state-of-theart systems on WeTS: SA-Transformer and VDBA. SA-Transformer is an end-to-end transformer-like model proposed in Yang et al. (2021). VDBA (Hu et al. 2019) is an improved version of Dynamic Beam Allocation, proposed in Post and Vilar (2018). Notice that SA-Transformer requires supervised learning with labeled data for translation suggestion, while VDBA and our method PSGD generate solely based on the machine translation model without any additional training or labeled data. Results of SA-Transformer have been reported in Yang et al. (2021), while for VDBA, we use the implementation in fairseq toolkit  to generate results for evaluation.
Result Results on the test set of WeTS are presented in Table 2. From the experimental observations, our PSGD outperforms VDBA significantly by 10.37 BLEU on average. What's more, for German-English and English-German, even without any labeled data or training process, PSGD still beats the state-of-the-art supervised model SA-Transformer, that is particularly designed for the TS task and trained with a large amount of labeled data and pseudo corpus. For the other two language pairs, though PSGD is an outstanding decoding algorithm for TS, it cannot beats the supervised SA-Transformer method because the NMT models of Chinese-English and English-Chinese released by WeTS are with poor quality. The Chinese-English and English-Chinese NMT models only achieve 17.0 and 16.3 BLEU on the WMT21 news test set (state-of-the-art systems achieve 33.4 and 49.2 BLEU respectively (Akhbardeh et al. 2021)).

Patience of Decoding Early Stopping
In PSGD, we involved a hyper-parameter pt, the number of extra decoding steps we take for early stopping. Larger pt can avoid omissions, since when a local optimum is reached, the model is encouraged to generate more steps to make sure it is the global optimum. However, larger pt makes the decoding process slower. To determine a proper value of this hyperparameter, we test the BLEU metric and average time cost on the English-German test set. The results are shown in Figure 3, which indicates that when pt is relatively small, increasing pt improves the decoding quality significantly. But there's not much gain to further increase pt away from 5. Taking the trade-off between efficiency and the quality into consideration, we set pt = 5.

Experiments with Different Mask Ratios
Samples in the WeTS dataset have a short length of masked span as displayed in Figure 2. The average length of spans selected is less than 10 percent of the whole translation sentence. To further verify the performance of PSGD with longer masked spans, we randomly mask the golden reference sentences with different mask ratios. Then, PSGD and VDBA generate predictions based on the remaining prefix and suffix.
Dataset We use the translation test sets of WMT14 for English-French, WMT21 for English-German and German-English in the news domain from the Conference of Machine Translation. Notice that in the WeTS datasets, the translation sentences are not entirely correct. We are unable to get the golden reference of a randomly masked span for evaluation.
Evaluation We randomly mask tokens in the references with different mask ratios from 20% to 90% and obtain predictions from pre-trained NMT models for the masked spans by decoding algorithms PSGD and VDBA separately. For English-German and German-English, we use the NMT  Ng et al. (2019). For English-French, we use the NMT model released by Ott et al. (2018). Then, the predictions are evaluated by Sacre-BLEU.
Result Results are shown in Figure 4. They clearly show that our PSGD outperforms state-of-the-art algorithm VDBA in all language pairs with each mask ratios. Basically, the performance of VBDA reaches the lowest point at the mask ratio of 40%, and then dramatically increases as the mask ratio increases. In comparison, PSGD's performance has always been stable.

Computation Efficiency
As demonstrated in the methodology section, compared with Hu et al. (2019) with t p + t r + t s decoding steps, PSGD is more efficient with t r + pt decoding steps as long as pt is smaller than t p + t s . To illustrate how PSGD speeds up the decoding process quantitatively, we conduct a running-time analysis by collecting time costs of translation suggestions with different mask ratios.
Detail We conduct the experiments on news test sets of WMT21 English-German, WMT21 German-English, and WMT14 English-French respectively. Both VDBA and PSGD are implemented with the fairseq toolkit. All experiments are run on a single Tesla P-100 GPU with CUDA 10.2. The target sequences are generated with a batch size of 10 and a beam size of 5. The time cost is calculated by averaging time costs on all samples of each test set. Notice that time for prepossessing is not included. Hyper-parameter pt is empirically set to 5, the same value as experiment of Figure 4.
Result Time costs of PSGD and VDBA are displayed in Figure 5. PSGD runs faster than VDBA in all cases. In the scene of TS, the incorrect spans are usually short in practice. Shown in the histogram of the masked length ratio in Figure  2, the averaged masked ratio is around 10%. Correspondingly in Figure 5, our algorithm can speed up for at least 2x times compared with VDBA.

Robustness Test
In the above experiments, the given prefix and suffix constraints come from the entirely correct reference sentences. However, in practice of CAT, it is not necessary that the prefix and suffix constraints are error-free even if the span with potential errors has been selected. Therefore, it is reasonable to carry out the experiments when prefix and suffix constraints directly come from the machine translation results. This setup is similar to that of WeTS's.
Evaluation Similar to the above experiments, we use the the same dataset from experiments with mask ratios. Instead, we randomly mask tokens from NMT outputs with different mast ratios. What's different, we expect that the performances of the decoding algorithms will not decrease much when the prefix and suffix constraints are not so ideal. The BLEU score is then calculated between the entire golden reference and the prediction for the masked span alone with the prefix and suffix.  Figure 6: BLEU of whole sentences with different mask ratios when prefix and suffix constraints come from MT results.
Result Results of PSGD and VDBA plotted in Figure 6 show similar trends with the results in the experiments with perfect prefix and suffix constraints. It is clear that PSGD outperforms VDBA significantly at all mask ratios still. In addition, the gap between PSGD and VDBA is unsurprisingly small when the mask ratio is extremely low since a short span has limited impact on the whole sequence evaluation. When the mask ratio is extremely large, both generations are nearly equivalent to the original translation of the NMT model. Except for these two situations, the performance of VDBA remarkably vibrates while the performance of PSGD remains at a high level.

Summary
In this section, exhaustive experiments are conducted to demonstrate the quality of generation, the robustness and the efficiency of our proposed decoding algorithm in the scene of TS. PSGD can be applied to pre-trained NMT models directly without any additional training or labeled data. It outperforms state-of-the-art constrained decoding algorithm VDBA (Hu et al. 2019) from all aspects.
• Experimental results on the WeTS benchmark dataset for translation suggestion show that PSGD greatly outperforms VDBA by 10.37 BLEU on average. It's worthy noticing that PSGD even outperforms the benchmark supervised model, SA-Transformer in English-German and German-English. • We also evaluate PSGD on the WMT translation data sets for its stability and robustness. It can stably produce high-quality translation suggestions. • In terms of efficiency, we compare the time cost of decoding process between PSGD and VDBA, and the results show that PSGD saves 63.4% time compared with VDBA.

Conclusion
In this paper, we propose an easy prefix-suffix guided decoding algorithm (PSGD) for the TS task where prefix and suffix constraints are given as guidelines. We utilize the objective function of NMT training and introduce an early stopping mechanism in PSGD. It decodes step by step to generate suggestions of spans selected by humans with potential errors. Compared with state-of-the-art constrained de-coding algorithm (Hu et al. 2019), PSGD significantly generates suggestions with higher quality within shorter time. It even outperforms the TS benchmark supervised model learned with annotated training data in English-German and German-English.

Future Work
Though PSGD achieves state-of-the-art performance on the Translation Suggestion task in terms of suggestions quality and computation efficiency, its capability to generate a single continuous span in the target has a limitation in the scenario of constrained decoding with multiple constraints. How to adapt it for such tasks will be our future work.