Non-Monotonic Autoregressive Sequence Model

Autoregressive models generate sequences monotonically, where any sampled token, even if erroneous or sub-optimal, becomes a permanent condition for all subsequent steps. This structural limitation means that autoregressive models cannot revisit or revise earlier decisions, i.e., a capability essential for complex generation tasks where exploration and correction are necessary. To this end, we propose N-MARS, a Non-Monotonic AutoregRessive Sequence modeling framework that enables models to generate, evaluate, and revise tokens within a single forward pass, effectively allowing exploration before commitment. We operationalize this framework through a learned erase token that retracts the previous token, enabling on-the-fly revision within standard autoregressive decoding. To train the model, we introduce a sequence augmentation method that constructs error-correction trajectories from model-generated deviations paired with ground-truth references. We then propose masked supervised fine-tuning (mSFT) that exposes the model to errors as context for learning when to revise, without optimizing their likelihood. Finally, we refine the model with group relative policy optimization (GRPO) that incentivizes judicious usage, i.e., rewarding effective corrections while penalizing unsuccessful ones. We conduct comprehensive theoretical and empirical analysis to validate the effectiveness of N-MARS, demonstrating a robust foundation for non-monotonic sequence modeling.

Today's AI language models write one word at a time, and once a word is out, it is locked in for good. If the model makes an early mistake, it cannot go back and fix it, so the error gets baked into everything that follows — like a wrong turn that throws off the rest of a trip. Existing remedies require the model to write a full draft, then critique and rewrite it, which is slow and cumbersome. Instead, we give the model an "undo" button: a learned erase action, like a keyboard's backspace key, that lets it delete its recent words and try again while it is still writing, in a single pass. To teach this skill, we show the model examples of mistakes paired with their fixes, preventing it from copying the mistakes, and then reward it for erasing wisely — correcting real errors without needless fidgeting. With this built-in self-correction, our method solves more math and coding problems than previous approaches and does so faster because it repairs errors on the fly rather than starting over. More broadly, it points toward AI that can catch and fix its own reasoning as it goes.