Standard autoregressive language models operate under a strict constraint: they generate text token-by-token, moving monotonically from left to right. This design is mathematically convenient because it aligns perfectly with the chain rule of probability. However, it does not reflect how humans write or reason. When composing a sentence, we rarely plan every word in a strict linear sequence; instead, we often start with a core concept, an important keyword, or a structural outline, and then fill in the surrounding context.
Forcing a model to generate text strictly from left to right introduces a significant planning bottleneck. If a sentence must include a specific keyword near the end, a left-to-right model must perfectly anticipate that constraint from the very first token. If it fails to plan ahead, it will either produce a grammatically awkward transition or miss the constraint entirely.
To overcome this limitation, researchers have developed non-monotonic sequence generation. Instead of sticking to a fixed linear path, these models treat sequence generation as a flexible process where tokens can be placed in any order, built outward from central anchors, or inserted dynamically into an evolving canvas.
Outward Expansion: Generating From the Middle Out
The most intuitive way to break the left-to-right constraint is to anchor a sentence around a high-information keyword and expand outward. This approach is particularly powerful for lexically constrained generation, where specific words must appear in the final output.
Lili Mou et al. introduced an early realization of this concept with the seq2BF (sequence to backward and forward) framework in Sequence to Backward and Forward Sequences: A Content-Introducing Approach to Generative Short-Text Conversation. Instead of starting at the beginning of a response, the model first predicts a high-content noun relevant to the conversation topic. It then uses two separate decoders to build the sentence: one moving backward to generate the prefix, and another moving forward to generate the suffix. This ensures that the most informative word dictates the structure of the surrounding sentence, preventing the model from falling into generic, high-frequency prefixes like "I don't know."
This "middle-out" approach was formalized into a generalized architecture by Shikib Mehri et al. in Middle-Out Decoding. By combining concurrent directional decoders with a dual self-attention mechanism, the authors allowed sequences to grow simultaneously in both directions from a fixed semantic core.
Standard Autoregressive: [The] -> [cat] -> [sat] -> [on] -> [the] -> [mat]
Middle-Out Decoding: [sat]
/ \
[cat] < > [on]
/ \
[The] < > [the] -> [mat]
This bidirectional expansion guarantees that forced keywords integrate naturally into the text without sacrificing grammatical fluency. The mechanism has proven highly effective across several specialized domains:
- Creative and Controllable Text: Arjun Chandrasekaran et al. utilized bidirectional generation to force phonetic puns into fixed positions within image descriptions (Punny Captions: Witty Wordplay in Image Descriptions), while Minlie Huang et al. used it to anchor dialogue responses around explicit personality profiles (Assigning Personality/Profile to a Chatting Machine for Coherent Conversation Generation). Similarly, Ya-Li Li et al. demonstrated that anchoring generation on user-selected objects ensures their inclusion in image captions (Intention Oriented Image Captions With Guiding Objects).
- Asynchronous and Alternating Growth: Rather than completing one direction before the other, Xiao Sun et al. proposed an asynchronous framework that bridges two non-adjacent keywords first, then fills in the remaining prefixes and suffixes (A Syntactically Constrained Bidirectional-Asynchronous Approach for Emotional Conversation Generation). For headline generation, Kosuke Yamada et al. showed that alternating step-by-step between backward and forward token generation around a central phrase yields superior contextual consistency (Transformer-based Lexically Constrained Headline Generation).
- Non-Textual Sequences: The utility of middle-out generation extends beyond natural language. In BAnG: Bidirectional Anchored Generation for Conditional RNA Design, Roman Klypa et al. applied this strategy to biological sequences, growing RNA strands outward from a central functional motif to ensure that critical binding properties are preserved.
Even when no explicit external constraint is provided, starting from the middle can improve generation quality by leveraging future context. Jian Yang et al. introduced Smart-Start Decoding for machine translation, which predicts a median word first, completes the right side of the sentence, and then fills in the left (Smart-Start Decoding for Neural Machine Translation). This allows the model to resolve early linguistic ambiguities by looking ahead to how the sentence will end. Similarly, in speech processing, Feijun Jiang et al. used multi-directional decoding to initiate generation from the most acoustically clear portion of an audio signal, allowing the model to anchor on high-confidence segments and recover from local noise (Speech2Slot: A Limited Generation Framework with Boundary Detection for Slot Filling from Speech).
Insertion-Based Modeling: Token-Location Joint Prediction
While middle-out decoding expands from a single center, a more general framework allows models to insert tokens anywhere in a sequence at any time. To achieve this, the model's action space must be redefined. Instead of simply selecting the next token from a vocabulary $V$, the model jointly predicts a content-location pair: $(token, slot\_index)$.
Dmitrii Emelianenko et al. explored this unconstrained generation order in Sequence Modeling with Unconstrained Generation Order, demonstrating that allowing arbitrary token insertion significantly enhances performance in structured tasks like code generation and image captioning. Crucially, William Chan et al. conducted an empirical study showing that insertion-based models trained on arbitrary generation paths can achieve translation quality comparable to standard left-to-right models, proving that the strict left-to-right order is not a mathematical necessity for high-quality text synthesis (An Empirical Study of Generation Order for Machine Translation).
This framework naturally accommodates variable-length text infilling. In Multichannel Generative Language Model: Learning All Possible Factorizations Within and Across Channels, Harris Chan et al. demonstrated that learning content-location pairs allows a single model to perform complex cross-lingual infilling tasks natively. Dhruvesh Patel et al. formalized this capability in Insertion Language Models: Sequence Generation with Arbitrary-Position Insertions, showing that Insertion Language Models (ILMs) handle complex planning and variable-length infilling significantly better than traditional autoregressive or masked diffusion models because they can add tokens at any available gap between previously generated elements.
Canvas: [The] [cat] [mat]
Step 1: Predict token "sat" at slot 2 -> [The] [cat] [sat] [mat]
Step 2: Predict token "on" at slot 3 -> [The] [cat] [sat] [on] [mat]
Step 3: Predict token "the" at slot 4 -> [The] [cat] [sat] [on] [the] [mat]
In automatic speech recognition (ASR), Shinji Watanabe et al. applied insertion-based modeling to eliminate the need for separate length prediction modules (Insertion-Based Modeling for End-to-End Automatic Speech Recognition). Because the model naturally terminates when it decides no further insertions are required between any existing tokens, it handles variable output lengths inherently.
For data augmentation, Manoj Kumar developed the Generative Insertion Transformer (GIT), which synthesizes diverse training data by iteratively inserting tokens into the gaps between fixed slot values or named entities (Controlled Data Generation via Insertion Operations for NLU). This guarantees that the critical semantic labels remain in their intended positions while the model generates varied surrounding context. Extending this concept to multimodal settings, Marton Havasi introduced OneFlow, which frames text generation as an iterative insertion process driven by model confidence over a continuous-time Markov chain, allowing for the concurrent generation of interleaved text and images (OneFlow: Concurrent Mixed-Modal and Interleaved Generation with Edit Flows).
Easy-First and Tree-Structured Generation
When a model is freed from a fixed linear order, it naturally tends to adopt an easy-first strategy: it generates the tokens it is most confident about first, establishing a structural skeleton before filling in the finer details.
Sean Welleck et al. operationalized this by decoupling generation order from the final linear sequence in Non-Monotonic Sequential Text Generation. Their framework builds sentences as binary trees, starting with any arbitrary word and recursively filling in the left and right branches. In subsequent work, Sean Welleck framed non-monotonic generation as a policy-driven process, demonstrating that prioritizing high-confidence structural components first is exceptionally effective for complex structured predictions like dependency trees (Order and Learning in Sequential Neural Structured Prediction).
Binary Tree Generation:
[sat] (Root/First word chosen)
/ \
[cat] [on] (Left and right children)
/ / \
[The] [the] [mat] (Leaf nodes)
Yosuke Higuchi et al. confirmed the efficiency of these tree-based canvas insertion methods in speech-to-text tasks, showing that they allow for parallel token generation while maintaining structural integrity (A Comparative Study on Non-Autoregressive Modelings for Speech-to-Text Generation).
This skeleton-first approach is also highly valuable for managing content flow:
- Video Captioning: Fenglin Liu et al. stabilized non-autoregressive video captioning by first identifying key semantic objects and fixing their positions within a sentence skeleton, providing structural anchors that prevent the model from generating repetitive or inconsistent word sequences during parallel decoding (O2NA: An Object-Oriented Non-Autoregressive Approach for Controllable Video Captioning).
- Abstractive Summarization: Kaiqiang Song et al. treated summarization as a non-sequential task, filling in high-confidence tokens first regardless of position to better prioritize critical information and manage content flow (A New Approach to Overgenerating and Scoring Abstractive Summaries).
Global Optimization and Adaptive Reasoning
Beyond text creation, non-monotonic generation unlocks the ability to perform global optimization, text editing, and complex reasoning by allowing models to look ahead, revise, or fill in gaps dynamically.
In COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics, Lianhui Qin et al. used gradient-based optimization on continuous token representations to enable non-monotonic text generation. Because updates can be applied to any position in the sequence at any time during the decoding process, the model can modify the beginning of a sentence to satisfy hard lexical or soft topical constraints that appear at the very end.
For text editing, Aliaksei Severyn et al. developed FELIX, a framework that decomposes generation into tagging and insertion sub-tasks (FELIX: Flexible Text Editing Through Tagging and Insertion). By utilizing a pointer mechanism for reordering, FELIX achieves massive speedups and handles significant structural changes without needing complex delete-and-re-insert operations. When generating text within a localized masked span, Devrim Cavusoglu et al. introduced an inward-alternating span decoding strategy that moves from the outer edges toward the center, allowing the model to incorporate context from both sides simultaneously for every token generated (DisGeM: Distractor Generation for Multiple Choice Questions with Span Masking).
Finally, this flexibility is crucial for complex reasoning. Standard left-to-right models often fail at multi-step reasoning because they are forced to generate a solution linearly, regardless of where the easiest dependencies lie. Long Ma et al. addressed this in Reinforced Context Order Recovery for Adaptive Reasoning and Planning, demonstrating that adaptive sequence generation allows a model to navigate complex reasoning problems by filling in computationally accessible or highly constrained tokens first. By solving simpler dependencies first, the model unlocks the necessary context to solve more complex dependencies later, bypassing the rigid bottlenecks of traditional autoregressive decoding.
Key Foundational Work
Sequence to Backward and Forward Sequences: A Content-Introducing Approach to Generative Short-Text Conversation (2016) — contributed 3 concept elements to this direction.
Emotional Conversation Generation Orientated Syntactically Constrained Bidirectional-Asynchronous Framework (2018) — contributed 2 concept elements to this direction.
Punny Captions: Witty Wordplay in Image Descriptions (2018) — contributed 2 concept elements to this direction.