Revisiting the M arkov Property for Machine Translation (2024)

Abstract: In this paper, we re-examine the Markov property in the context of neural machine translation. We design a Markov Autoregressive Transformer (MAT) and undertake a comprehensive assessment of its performance across four WMT benchmarks. Our findings indicate that MAT with an order larger than 4 can generate translations with quality on par with that of conventional autoregressive transformers. In addition, counter-intuitively, we also find that the advantages of utilizing a higher-order MAT do not specifically contribute to the translation of longer sentences.

## introduction markov models are classic probabilistic graphical models based on the markov property. the markov property reduces computation complexity and thus makes markov models highly appealing. markov models have been extensively used in many nlp tasks such as part-of-speech tagging @xcite and dependency parsing @xcite . statistical machine translation (smt) has also employed markov models, e.g., @xcite . however, with the rise of deep learning in machine translation, autoregressive models @xcite @xcite , particularly autoregressive transformers @xcite , have gradually become mainstream. during decoding, autoregressive models rely on all the previous tokens. as a result, they can model long-range dependencies and are thus considered to have superior abilities to express token dependency than markov models. the performance of recent advanced markov models @xcite @xcite in mt are also significantly lower than those of the autoregressive model. the markov property dictates that, during decoding, each token can only observe the previous k tokens. this characteristic is a considerable drawback for generation tasks that require long contexts, such as story generation. however, we believe that in translation, since the source sentence is fully visible, introducing the markov property on the decoder side might not greatly affect translation performance. to investigate this hypothesis, we introduce the markov autoregressive transformer (mat) and evaluate its performance on translation. mat possesses two main features: 1) minimal modifications to autoregressive transformers, and 2) support for high-order markov models. specifically, the key idea of the kth-order markov property is that the next output token by the model is only dependent on the previous k tokens. in this paper, we point out that this objective can be achieved with a simple modification to the causal mask in the decoder part. in contrast to previous markov models, this simple modification ensures that our mat has only marginal alterations compared to the autoregressive transformer. this allows us to effectively isolate and examine the effects of the markov property in a manner akin to a controlled variable experiment. in addition to the aforementioned benefit, this straightforward modification also enables us to train mat in parallel, like the vanilla transformer. we evaluate mat on several wmt benchmarks and make the following observations: in addition to the aforementioned findings, we also discover that mat also enjoys the following advantages: 1) linear complexity of attention. to generate a sentence with the length of n, the complexity of attention is only o(kn) compared with o(n 2 ) in vanilla autoregressive transformers. for a sample length of 25, the computation for decoder self-attention is reduced by approximately threefold. 2) key-value cache free inference. because mat only attends to the embeddings of the previous k tokens, it does not require caching any keys and values of the previous tokens during inference. this reduces the memory bandwidth required by the cache at the decoding stage. by limiting the dependence on a fixed number of preceding tokens, the markov property can potentially simplify the translation model, thereby reducing complexity and computational requirements. this might lead to a balance where adequate performance can be achieved more efficiently. ## markov autoregressive transformer (mat) our mat consists of two parts: 1) an encoder, and 2) a markov decoder. we keep the encoder the same as in the vanilla transformer. for the markov decoder, the only difference lies in the attention mechanism, which is elaborated as follows. ## conclusions in this paper, we re-examine the markov property in machine translation. we design an experimental markov model based on the transformer architecture. we verify that higher-order markov properties have a very slight impact on the model's translation quality. moreover, we find that longer sentences do not necessarily require higher-order markov models. in the future, we aim to design faster and more lightweight models to leverage the advantages of the markov property. and also extend this idea to large language model and other tasks needs realtime decoding like rumor detection @xcite and infodemic surveillance @xcite .