Introduction
Standard Large Language Models (LLMs) typically generate text in a rigid, left-to-right autoregressive fashion. While effective for natural language prose, this fixed order often fails on complex reasoning tasks where the logical starting point is not necessarily the first token in a sequence. Reinforced Context Order Recovery (ReCOR) introduces a novel framework that leverages reinforcement learning to allow models to autonomously discover the optimal generation order, prioritizing "easy" components to build the necessary context for more difficult sub-problems.
The Challenge of Rigid Autoregression
Most modern AI models predict the next token based strictly on preceding context ($P(y_i | y_{<i})$). In tasks like Sudoku or multi-digit arithmetic, this constraint can be catastrophic. If a model is forced to fill a grid from the top-left corner, it may encounter a cell that is mathematically impossible to solve without information located further down the grid.
Humans naturally solve such problems by scanning for the easiest constraints first. Previous attempts to mimic this behavior, such as Masked Diffusion Models, often rely on random masking during training. This forces models to attempt "impossible" predictions, leading to training inefficiencies and suboptimal performance.
ReCOR: Learning the Optimal Order
ReCOR treats token generation as a decision-making process modeled as a Markov Decision Process (MDP). The framework consists of two primary components: an order policy ($\pi_\theta$) and a token predictor ($p_\psi$).
The "Easy-First" Mechanism
The core of ReCOR is the $\mathcal{V}$-information framework, which defines "token hardness." A token is considered "easy" if the current context provides sufficient information to predict it accurately under specific computational constraints. Using Soft Q-Learning (SQL), the model is rewarded based on the accuracy of its token predictions. By choosing to predict easier tokens first, the agent maximizes its reward and naturally develops a problem-solving curriculum.
Architectural Innovations
To implement this efficiently, ReCOR utilizes a multi-stream architecture inspired by XLNet. A "main stream" processes the existing context, while an "order/token query stream" evaluates the hardness of all remaining empty slots in parallel. Crucially, ReCOR maintains alignment between training and inference by using the learned adaptive order in both phases, eliminating the distribution shift common in other adaptive methods.
Key Results and Insights
The researchers evaluated ReCOR across several benchmarks requiring non-linear reasoning, including Sudoku, Zebra logic puzzles, and complex multiplication.
- Arithmetic Dominance: In a Synthetic Autoregression (ARG) task where tokens depend on subsequent values, standard Causal LMs achieved only 1.7% accuracy. ReCOR reached 98.7%.
- Outperforming the Oracle: In Sudoku, ReCOR achieved 90.17% accuracy, significantly outperforming standard Causal LMs (9.7%) and even surpassing "oracle" models (87.18%) that were supervised with ground-truth logical orders. This suggests the RL agent discovered generation orders more optimized for model processing than human-designed sequences.
- Efficiency: ReCOR proves more efficient than diffusion-based alternatives. By utilizing autoregressive generation with KV-caching, it requires fewer FLOPs to achieve superior accuracy.
Conclusion and Future Directions
ReCOR demonstrates that allowing models to choose their own path through a problem significantly enhances reasoning capabilities. While currently tested on models ranging from 6M to 11M parameters, the framework shows great promise for scaling. Future research will explore applying ReCOR to open-ended tasks like creative writing or coding, where multiple "correct" paths may exist, and investigating the recovery of unobserved latent variables in the generation process.
Summary updated