Standard autoregressive models generate sequences under a rigid constraint: they predict tokens strictly from left to right. While effective, this monotonic approach forces a model to make hard choices early on without knowing the future context, often leading to compounding errors, infinite loops, or hallucinations.
Humans do not write or reason this way. When composing a sentence or solving a puzzle, we sketch out a structural skeleton, fill in the easy or certain parts first, and defer highly uncertain details until the surrounding context is established. To mimic this intuition, a growing body of research explores non-monotonic generation, where the order of token prediction is dynamically scheduled based on the model's own predictive confidence, entropy, or uncertainty.
The Intuition of Easy-First Decoding
Why change the generation order? In an unconstrained or non-autoregressive generation framework, a model can evaluate all ungenerated positions simultaneously. By committing to the highest-confidence tokens first, it establishes a stable structural scaffolding that simplifies the remaining generation steps.
As demonstrated by Sean Welleck in Order and Learning in Sequential Neural Structured Prediction, models permitted to generate non-linearly naturally prioritize simple structural elements before filling in complex information. Emelianenko et al. observed in Sequence Modeling with Unconstrained Generation Order that this "easy-first" strategy naturally prioritizes punctuation and conjunctions, building a framework that guides the subsequent generation of more difficult semantic elements like verbs.
Early implementations of this concept, such as the bidirectional sequence generation framework (BISON) introduced by Lawrence et al. in Attending to Future Tokens for Bidirectional Sequence Generation, decode text by iteratively replacing placeholder tokens at the position with the highest prediction probability across the entire sequence. Similarly, Welleck et al. in Non-Monotonic Sequential Text Generation structured sentence generation as a binary tree, allowing the model to place high-confidence anchor tokens first and defer difficult lexical choices until more context is established.
This mechanism has been formalized in modern architectures like the Any-order Any-subset Autoregressive (A3) framework by Du et al. in Autoregressive Models Rival Diffusion Models at ANY-ORDER Generation. Here, confidence-prioritized decoding enables the model to evaluate all ungenerated positions and commit to those with the highest predictive certainty first, dynamically refining the sequence step-by-step.
Information-Theoretic Error Minimization
The benefit of easy-first scheduling is not just intuitive; it has a rigorous information-theoretic foundation. In parallel sampling or discrete diffusion models, generating multiple tokens simultaneously can introduce massive cumulative errors if the model guesses blindly.
Li et al. provide a theoretical justification for this in Breaking AR’s Sampling Bottleneck: Provable Acceleration via Diffusion Language Models. They prove that minimizing error in parallel sampling requires a "minimum conditional entropy scheduling" policy. By unmasking or generating tokens with the lowest conditional entropy first given the currently visible context, the model minimizes the cumulative error introduced across parallel sampling steps.
This principle is mirrored in image generation. In BiGR: Harnessing Binary Latent Codes for Image Generation and Improved Visual Representation Capabilities, an entropy-ordered sampling strategy creates a stable global context by resolving the lowest-uncertainty regions first, mimicking a coarse-to-fine refinement process. By focusing on tokens where the model has the highest certainty, the system decomposes complex joint distributions into a sequence of simpler, more stable conditional steps.
The Information-Gain Alternative: Hard-First Scheduling
While the easy-first strategy is highly effective for stabilizing structure, an alternative perspective argues that prioritizing high-information or high-entropy tokens first can yield superior global semantic coherence. The intuition here is that filling in high-frequency filler words first wastes a model's capacity, whereas anchoring the generation around core keywords prevents the model from drifting into generic or irrelevant outputs.
For instance, Wang et al. introduce InfoDiffusion: Information Entropy Aware Diffusion Process for Non-Autoregressive Text Generation, showing that prioritizing high-information tokens early in the denoising process ensures that the core meaning of a sequence is established before the grammatical scaffolding is filled in.
Similarly, Wagner et al. demonstrate in CONTESTS: a Framework for Consistency Testing of Span Probabilities in Language Models that predicting high-entropy or high-uncertainty tokens before low-entropy ones can optimize decoding paths and yield more likely joint probability scores.
In complex multi-stage tasks like chemical retrosynthesis, Wang et al. find in RetroDiff: Retrosynthesis as Multi-stage Distribution Interpolation that resolving high-variance components first establishes a stable context that simplifies the subsequent prediction of more deterministic structural elements.
To move beyond hand-crafted heuristics for balancing these easy-first and hard-first trade-offs, Hong et al. developed Unmasking Policy Optimization in Improving Discrete Diffusion Unmasking Policies Beyond Explicit Reference Policies. By treating the generation sequence as a reinforcement learning problem, they trained a scheduler that prioritizes structurally deterministic or high-information positions dynamically, optimizing the logical consistency of the final output.
Broadening the Horizon Beyond Text
The paradigm of confidence-based ordering extends far beyond natural language processing into vision, video compression, and structural generation, proving that uncertainty-aware scheduling is a fundamental property of efficient sequence modeling:
- Image Captioning: Fei et al. implement this in Uncertainty-Aware Image Captioning, where low-uncertainty tokens (like primary objects) are predicted first to provide context for high-uncertainty relational descriptors, reducing the number of sequential steps required.
- Video Compression: In MIMT: Masked Image Modeling Transformer for Video Compression, Xiang et al. use an easy-to-hard scheduling based on entropy levels to progressively fix the most certain pixel predictions, using them as context to refine remaining masked regions.
- Molecular Generation: Wang et al. develop Learning-Order Autoregressive Models in Learning-Order Autoregressive Models with Application to Molecular Graph Generation, demonstrating that allowing a model to learn its own sequence causes it to naturally prioritize high-confidence structural skeletons before adding complex chemical details.
By breaking the rigid left-to-right bottleneck and ordering generation based on predictive certainty, these models achieve a more robust, human-like approach to structured prediction across diverse domains.
Key Foundational Work
Non-Monotonic Sequential Text Generation (2019) — contributed 2 concept elements to this direction.
Attending to Future Tokens for Bidirectional Sequence Generation (2019) — contributed 1 concept elements to this direction.
Sequence Modeling with Unconstrained Generation Order (2019) — contributed 1 concept elements to this direction.