Standard sequence generation models—such as those powering modern large language models and machine translation systems—rely on an autoregressive paradigm. To generate a sequence of tokens $Y = (y_1, y_2, \dots, y_L)$ given an input $X$, an autoregressive model factorizes the joint probability distribution using the chain rule of probability:
$$P(Y|X) = \prod_{t=1}^L P(y_t | y_{<t}, X)$$
This factorization imposes a strict sequential dependency: the model cannot compute the probability distribution for the next token $y_t$ until it has fully generated all preceding tokens $y_{<t}$.
While this causal structure mirrors the sequential nature of human language, it introduces a severe computational bottleneck during inference. Modern hardware accelerators, such as GPUs and TPUs, derive their efficiency from massive parallelization. Autoregressive decoding forces these processors to execute $L$ sequential forward passes to generate a sequence of length $L$. At each step, the hardware sits largely idle, bound by memory bandwidth rather than compute capacity. Consequently, inference latency scales linearly ($O(L)$) with the output length, creating a significant barrier for real-time applications.
To break this sequential bottleneck, researchers have developed Non-Autoregressive (NAR) sequence models. These architectures eliminate the causal constraint, allowing the model to predict all tokens or dimensions simultaneously in a single forward pass, reducing the theoretical inference time complexity to $O(1)$.
The Core Challenge: The Multimodality Problem
The naive approach to non-autoregressive generation is to assume complete conditional independence among the target tokens given the source input:
$$P(Y|X) = \prod_{t=1}^L P(y_t | X)$$
Under this formulation, a model can emit every token in parallel. However, this independence assumption introduces the multimodality problem.
Consider a machine translation scenario where a source phrase can be translated into multiple valid target sequences (modes). For instance, the English phrase "Thank you" can be translated into German as either "Danke" or "Vielen Dank". An autoregressive model resolves this ambiguity at the first step: if it emits "Vielen", the causal history forces the subsequent tokens to follow the "Vielen Dank" path.
An independent NAR model lacks this coordination mechanism. When predicting all positions simultaneously, the distribution at position 1 may favor "Vielen", while the distribution at position 2 independently favors "Danke". The resulting parallel output becomes an incoherent mixture of different modes (e.g., "Vielen Danke"), frequently manifesting as token duplication, omissions, or structural gibberish.
To make parallel generation work, NAR architectures must introduce mechanisms that allow tokens to coordinate their predictions without reverting to slow, step-by-step autoregressive decoding.
Structural Guidance and Latent Variables
One prominent strategy for mitigating the multimodality problem is to introduce latent variables or structural priors that pre-plan the global layout of the sequence before the parallel generation step occurs.
Target Length and Token Fertility
In their foundational work on non-autoregressive translation, Jiatao Gu et al. introduced the concept of "fertility" in Non-Autoregressive Neural Machine Translation. Fertility acts as a latent variable that dictates how many target tokens each source token should produce. By predicting these fertilities in advance, the model explicitly defines the overall length and rough structural layout of the target sequence. The decoder then uses this fertility-mapped input to generate all target tokens in parallel, significantly reducing structural misalignment and achieving up to a 15x speedup over autoregressive baselines.
Syntactic Skeletons and Hierarchical Trees
Rather than relying solely on abstract latent variables, other approaches leverage explicit linguistic structures to guide parallel generation. Kalpesh Krishna et al. proposed a two-stage decoding process in Syntactically Supervised Transformers for Faster Neural Machine Translation. The model first autoregressively predicts a highly condensed syntactic "skeleton" or chunk-level representation of the sentence. Because this skeleton is much shorter than the full text, its sequential generation is extremely fast. In the second stage, the model fills in the specific words within each syntactic chunk simultaneously, preserving global grammatical coherence while accelerating inference.
Taking structural guidance further, Shangtong Gui integrated a Probabilistic Context-Free Grammar (PCFG) directly into the non-autoregressive framework. By modeling sentences as hierarchical trees rather than flat, linear sequences, the author demonstrated that a parallel model can capture complex, non-adjacent token dependencies, closing the performance gap with autoregressive models while maintaining a 12.6x speedup.
Iterative Refinement and Continuous Flow Matching
A powerful compromise between pure $O(1)$ parallel generation and $O(L)$ sequential generation is iterative refinement. Instead of producing the final sequence in a single shot, the model generates an initial rough draft in parallel and refines it over a small, fixed number of steps ($O(K)$, where $K \ll L$).
[Input X] ---> [Initial Parallel Draft Y^0] ---> [Refinement Step 1] ---> [Refinement Step K] ---> [Final Output]
Denoising Autoencoders and Realignment
Jason Lee et al. formalized this in Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinement by treating the generation process as a sequence of denoising steps. The model learns to take a corrupted or poorly coordinated parallel sequence and iteratively improve its quality.
In domains like speech recognition, where the length of the audio input does not map one-to-one with the text output, iterative refinement is paired with alignment mechanisms. A. Ethan et al. developed Align-Refine: Non-Autoregressive Speech Recognition via Iterative Realignment, which iteratively adjusts the latent alignments between audio frames and text tokens, allowing the model to insert, delete, or modify words across a few parallel steps rather than predicting them one-by-one.
Continuous Probability Paths
The iterative refinement concept has converged with continuous generative frameworks like diffusion and flow matching. For discrete categorical sequences (such as DNA or text), standard continuous diffusion can be mathematically awkward. To resolve this, Hannes Stark et al. introduced Dirichlet Flow Matching with Applications to DNA Sequence Design. By defining continuous probability paths on a simplex using Dirichlet distributions, the authors enabled high-fidelity, parallelized sequence generation that avoids the token-by-token bottleneck entirely, offering substantial speedups for long biological sequences.
Alignment Objectives and Knowledge Distillation
Because NAR models cannot rely on step-by-step history to correct their course, they require specialized training objectives and optimization frameworks to learn coherent target distributions.
Connectionist Temporal Classification (CTC)
One way to bypass the strict ordering penalty of standard cross-entropy loss is to allow the model flexibility in where it places tokens during its parallel forward pass. Jindrich Libovický et al. adapted Connectionist Temporal Classification (CTC) from speech processing to machine translation in End-to-End Non-Autoregressive Neural Machine Translation with Connectionist Temporal Classification. The CTC loss integrates out all possible alignments that collapse into the correct target sequence (allowing for blanks and repeated tokens), effectively absorbing the spatial uncertainty inherent in parallel decoding.
Imitation Learning and Energy Minimization
NAR models struggle to learn directly from raw, highly multimodal human data. To simplify the data distribution, researchers frequently use an autoregressive "teacher" model to generate simplified, deterministic targets—a process known as sequence-level knowledge distillation.
To maximize the effectiveness of this distillation, Bingzhen Wei et al. framed NAR training as an imitation learning problem in Imitation Learning for Non-Autoregressive Neural Machine Translation, forcing the parallel student to match the policy and action distributions of the sequential teacher.
Alternatively, Lifu Tu et al. introduced ENGINE: Energy-Based Inference Networks for Non-Autoregressive Machine Translation. Instead of forcing the NAR model to mimic the teacher's top-1 token outputs, ENGINE trains the parallel model to minimize an energy function defined by the autoregressive teacher's full joint probability space, allowing the student to capture richer contextual dependencies without sacrificing inference speed.
Generalization Beyond Text Translation
The sequential generation bottleneck is not unique to natural language processing; it represents a fundamental constraint across various machine learning domains. The principles of non-autoregressive modeling have been widely adapted to unlock real-time performance in other areas:
- Reinforcement Learning and Control: In model-based reinforcement learning, generating synthetic trajectory rollouts or planning multi-agent actions autoregressively introduces severe latency that prevents real-time environmental response. Wenzhe Fan et al. bypassed this in Towards Efficient Collaboration via Graph Modeling in Reinforcement Learning by implementing a parallel decoding scheme for multi-agent action selection. Similarly, Kehan Wen et al. utilized a bidirectional masked trajectory model in M^3PC: Test-time Model Predictive Control using Pretrained Masked Trajectory Model to evaluate multiple potential future scenarios simultaneously, accelerating test-time model predictive control.
- Set and List Generation: When generating unordered collections of data (such as document keyphrases or recommendation lists), forcing an autoregressive model to serialize the items introduces artificial order bias and unnecessary latency. Zixian Huang et al. resolved this in A Branching Decoder for Set Generation by introducing a decoder that dynamically branches out to generate multiple independent sequences in parallel. For recommendation systems, Qijiong Liu et al. developed FANS: Fast Non-Autoregressive Sequence Generation for Item List Continuation, which replaces item-by-item generation with a parallel hierarchical classifier to meet the strict response-time constraints of production environments.
By shifting the computational paradigm from sequential dependency to parallel coordination, non-autoregressive sequence modeling allows deep learning architectures to fully exploit modern parallel hardware, transforming high-latency sequence generation into a fast, scalable operation.
Key Foundational Work
Multimodal Transitions for Generative Stochastic Networks (2014) — contributed 2 concept elements to this direction.