Research map / Large language models / Reasoning and chain of thought
Reinforced Context Order Recovery for Adaptive Reasoning and Planning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ReCOR, an RL-based framework that learns data-dependent token generation orders from plain text via a self-supervised, V-information-motivated objective, outperforming CLMs, MDMs and adaptive MDM inference on arithmetic and puzzle tasks.
Problem
Fixed (left-to-right or random) token generation orders in causal and masked diffusion language models fail on reasoning and planning tasks that need adaptive, instance-dependent orders; existing adaptive methods need order annotations or apply adaptivity only at inference.
Approach
Cast generation order recovery as an MDP: a soft Q-learning policy selects the next position to generate, rewarded by the log-probability of the token predictor (a GPT-2 multi-stream model trained online on-policy), so that the order is adaptive during both training and inference without order annotations.
Key results
- On Sudoku, ReCOR reaches 0.9017 accuracy versus 0.8718 for the ground-truth-order oracle AR-GT and 0.0973 for CLM.
- On Zebra, ReCOR reaches 0.9905 versus 0.9117 for AR-GT and 0.8031 for CLM.
- On ARG, ReCOR reaches 0.987 versus 0.035 for MDM and 0.174 for AdaMDM, while AR-GT gets 0.994.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive order recovery instead of left-to-right generation | GPT-2 · ARG | accuracy: 0.017 ± 0.002 -> 0.987 ± 0.007 | Helped |
| Use adaptive order recovery instead of left-to-right generation | GPT-2 · MUL | accuracy: 0.594 ± 0.018 -> 0.964 ± 0.007 | Helped |
| Use adaptive order recovery instead of ground-truth-order AR-GT | GPT-2 · Sudoku | accuracy: 0.8718 -> 0.9017 ± 0.0004 | Helped |
| Use adaptive order recovery instead of ground-truth-order AR-GT | GPT-2 · Zebra | accuracy: 0.9117 -> 0.9905 ± 0.0021 | Helped |
| Add suffix unmasking during training (ablation) | AdaMDM · ARG | accuracy: 0.174 ± 0.036 -> 0.536 ± 0.051 | Helped |
| Add suffix unmasking during training (ablation) | MDM · ARG | accuracy: 0.035 ± 0.010 -> 0.040 ± 0.005 | Helped |
| Increase adaptive MDM inference from T=2 to T=20 (ablation) | AdaSufMDM · ARG | accuracy: 0.028 ± 0.009 -> 0.536 ± 0.051 | Helped |
| Increase adaptive MDM inference from T=2 to T=20 | AdaMDM · MUL | accuracy: 0.875 ± 0.043 -> 0.951 ± 0.038 | Helped |
| Use ReCOR rather than adaptive MDM with 10x inference compute | ARG · ARG | accuracy: 0.536 ± 0.051 -> 0.987 ± 0.007 | Helped |
| Use ReCOR rather than adaptive MDM with 10x inference compute | MUL · MUL | accuracy: 0.951 ± 0.038 -> 0.964 ± 0.007 | Helped |
Surprising findings
- ReCOR outperforms the ground-truth-order oracle AR-GT on Sudoku and Zebra.
- Inference-only adaptive MDM decoding (AdaMDM) fails on ARG because random masking during training rarely exposes complete contexts, and suffix unmasking only partially closes the gap.
Limitations
- Experiments limited to reasoning and planning datasets (arithmetic, Sudoku, Zebra).
- RL formulation left many design choices (RL algorithms, discount factor, rewards) unexplored due to limited resources.
- Unobserved variables beyond generation order are not modeled.
Experimental setup
Datasets: Synthetic Autoregression (ARG) Multiplication (MUL) Sudoku Zebra
Benchmarks: Synthetic Autoregression (ARG) Multiplication (MUL) Sudoku Zebra
Metrics: full response match accuracy
Baselines: AR-GT CLM MDM AdaMDM AdaSufMDM
Builds on: any-order autoregressive models masked diffusion models XLNet soft Q-learning predictive V-information
Closest papers by meaning
- $\textbf{Re}^{2}$: Unlocking LLM Reasoning via Reinforcement Learning with Re-solving (ICLR 2026 · similarity 0.87)
- Reinforcement Mid-Training (ICLR 2026 · similarity 0.87)
- Do Not Let Low-Probability Tokens Over-Dominate in RL for LLMs (ICLR 2026 · similarity 0.87)
- The Flexibility Trap: Rethinking the Value of Arbitrary Order in Diffusion Language Models (ICML 2026 · similarity 0.87)
- Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions (ICML 2025 · similarity 0.87)
- IAPO: Information-Aware Policy Optimization for Token-Efficient Reasoning (ICML 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.