Order Agnostic Autoregressive Sequence Modeling

38 concepts28 papers2 proposals

Standard autoregressive (AR) models are bound by a strict sequential constraint. To generate a sequence of tokens $X = \{x_1, x_2, \dots, x_n\}$, they factorize the joint probability distribution chronologically or spatially:

$$P(X) = \prod_{i=1}^n P(x_i \mid x_{<i})$$

While highly effective for left-to-right text generation, this rigid factorization introduces severe directional biases. For example, standard language models suffer from the "reversal curse"—learning that "A is B" does not automatically mean they can infer "B is A". In computer vision, a fixed raster-scan order forces a model to generate the top-left of an image before the bottom-right, artificially limiting global spatial reasoning.

Order-agnostic autoregressive modeling breaks this constraint by training the model to factorize the joint distribution under any arbitrary permutation of the sequence tokens:

$$P(X) = \prod_{i=1}^n P(x_{\sigma(i)} \mid x_{\sigma(<i)})$$

where $\sigma$ represents a random permutation of the sequence indices. Instead of learning a single directional path, the model learns to predict the next token given an arbitrary subset of observed context tokens.

The Core Mechanism: Why Permutation Acts as a Regularizer

Training a model to predict variables in a randomized order forces it to learn the underlying structural correlations of the data rather than memorizing sequential trajectories.

Early foundational work by Benigno Uria et al. in Neural Autoregressive Distribution Estimation demonstrated that training an autoregressive model on arbitrary sequences acts as a powerful structural regularizer. By forcing the network to handle missing data through implicit marginalization, it effectively creates an ensemble of multiple conditional models within a single shared architecture.

This order independence prevents the model from over-relying on specific input sequences. For instance, Yin Zheng et al. adapted this concept to user preference modeling in Neural Autoregressive Collaborative Filtering for Implicit Feedback, showing that training on randomly sampled permutations allows the model to generalize across diverse user histories regardless of chronological order. Similarly, in conversational systems, Xianquan Wang et al. demonstrated in Personalized Visual Content Generation in Conversational Systems that sequence shuffling prevents generative models from becoming sensitive to the arbitrary placement or order of reference items in a user's history.

The Mathematical Equivalence of Masking and Permutation

Explicitly training a model on all $N!$ possible permutations is computationally intractable. Instead, modern architectures achieve order-agnostic generation through a clever mathematical shortcut: randomized masking.

Bo Peng et al. proved in Probabilistically Masked Language Model Capable of Autoregressive Generation in Arbitrary Word Order that optimizing a model with a random, uniform masking ratio is mathematically equivalent to sequence permutation training. By treating each prediction as independent and conditioned on all surrounding unmasked tokens, the model implicitly learns to handle all possible generation paths.

Standard AR (Left-to-Right):
[The] -> [cat] -> [sat] -> [on] -> [the] -> [mat]

Order-Agnostic AR (Permuted / Masked):
Step 1: [M]   [M]   [sat] [M]   [M]   [M]   -> Predict 'sat' given nothing
Step 2: [The] [M]   [sat] [M]   [M]   [M]   -> Predict 'The' given 'sat'
Step 3: [The] [M]   [sat] [M]   [the] [mat] -> Predict 'the', 'mat' given context

This any-order objective fundamentally alters how models learn dependencies. As Sangwoo Shin et al. show in Understanding the Reversal Curse Mitigation in Masked Diffusion Models through Attention and Training Dynamics, masked diffusion models naturally mitigate the reversal curse because their training does not prioritize a single conditional probability direction.

To smooth this learning process, Mahdi Karami et al. in Auto-Regressive Masked Diffusion Models introduce training schedules that progressively increase the randomness of token permutations, systematically moving the model beyond sequential biases. Jiaxin Shi et al. further demonstrate in Simplified and Generalized Masked Diffusion for Discrete Data that this flexibility allows order-agnostic discrete diffusion models to outperform equivalent fixed-order autoregressive models in pixel-level image modeling.

Anchoring to Space: Decoupling Order from Position

If tokens are processed in a completely randomized order, how does the model maintain spatial or structural coherence? The secret lies in decoupling the processing order from the spatial coordinates using absolute position embeddings or position queries.

Wenze Liu et al. demonstrate in Customize Your Visual Autoregressive Recipe with Set Autoregressive Modeling that as long as tokens are explicitly mapped to their global coordinates via absolute position embeddings, the specific spatial trajectory (whether spiral, raster, or random) becomes irrelevant to performance.

This insight allows standard decoder-only transformers to discard the raster-scan constraint entirely. For example, Ziqi Pang et al. show in RandAR: Decoder-only Autoregressive Visual Generation in Random Orders that simply adding a "position instruction token" before each visual token allows the model to effectively learn the underlying image distribution from completely shuffled sequences.

Standard Raster Input:  [Token A @ (0,0)] -> [Token B @ (0,1)] -> [Token C @ (0,2)]
RandAR Shuffled Input:  [Pos: (0,2)][Token C] -> [Pos: (0,0)][Token A] -> [Pos: (0,1)][Token B]

In the visual domain, Qi Yu et al. (Exploring Stochastic Autoregressive Image Modeling for Visual Representation) and Rongzhen Zhao et al. (Slot Attention with Re-Initialization and Self-Distillation) demonstrate that randomizing the prediction order of image patches forces the model to capture bidirectional spatial relationships, preventing scan-line biases and improving object-centric representations. This is echoed by Lijie Fan et al. in Fluid: Scaling Autoregressive Text-to-image Generative Models with Continuous Tokens, who show that discarding the raster scan in favor of a random-order generation strategy significantly improves global spatial reasoning and prompt adherence.

To implement this in convolutional architectures rather than transformers, Ajay Jain et al. developed Locally Masked Convolution for Autoregressive Models (LMCONV). Instead of applying global masks to weights, LMCONV applies location-specific masks to input patches, enabling CNNs to leverage arbitrary context for tasks like image completion.

This order independence is equally powerful for non-visual structural domains. For example, Raul Ortega Ochoa et al. leverage order-agnostic generation in MolMiner: Transformer architecture for fragment-based autoregressive generation of molecular stories to assemble molecular fragments starting from any arbitrary piece, acting as a structural regularizer that helps the model learn the underlying grammar of chemistry robustly. Similarly, in medical dialogue systems, Junying Chen et al. show in Diaformer: Automatic Diagnosis via Symptoms Sequence Generation that sequence shuffling prevents models from developing biases toward specific inquiry paths.

Unlocking Zero-Shot Infilling and Parallel Decoding

By training a model to handle arbitrary context subsets, order-agnostic sequence modeling unlocks two major capabilities: zero-shot localized manipulation and highly accelerated parallel decoding.

Zero-Shot Infilling and Editing

Because the model can condition on any arbitrary subset of observed patches, it can perform tasks like inpainting, outpainting, or shape completion without specialized fine-tuning. Paritosh Mittal et al. demonstrate this in AutoSDF: Shape Priors for 3D Completion, Reconstruction and Generation, where a transformer trained with randomized token ordering predicts missing 3D components from any arbitrary viewpoint.

In image editing, the authors of NEP (Next Editing Token Prediction) utilize randomized positional embeddings to treat specific masked regions as the next tokens to be generated. This allows the model to generate content exclusively for an arbitrary mask shape, enabling precise local modifications without altering the surrounding background.

Parallel Decoding

Fixed-order AR generation requires $N$ sequential steps for a sequence of length $N$. Order-agnostic models break this bottleneck. Sam Bond-Taylor et al. exploit this in Unleashing Transformers: Parallel Token Prediction with Discrete Absorbing Diffusion for Fast High-Resolution Image Generation from Vector-Quantized Codes by treating generation as a parallel denoising process of masked tokens, drastically accelerating sampling.

Furthermore, Yifei Wang 0003 et al. demonstrate in Train Once, and Decode As You Like that a single model trained on a permutation-based objective can dynamically switch between slow, accurate autoregressive decoding and fast, parallel non-autoregressive decoding.

To maximize this speedup, Zhuoyang Zhang et al. introduce Locality-aware Parallel Decoding for Efficient Autoregressive Image Generation, using flexible attention masks that allow tokens generated within the same parallel step to "see" each other. This reduces the required sampling steps by over 10x while maintaining high generation quality.

Key Foundational Work

Neural Autoregressive Collaborative Filtering for Implicit Feedback (2016) — contributed 2 concept elements to this direction.
Locally Masked Convolution for Autoregressive Models (2020) — contributed 1 concept elements to this direction.
Train Once, and Decode As You Like (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_order_agnostic_sequence_modeling_57626f28,
  title = {order-agnostic sequence modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/order-agnostic-sequence-modeling/rdr_57626f285ef747f79f1f33b04d174258},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_order_agnostic_sequence_modeling_57626f28_v1,
  title = {order-agnostic sequence modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/order-agnostic-sequence-modeling/rdr_57626f285ef747f79f1f33b04d174258/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake