# Self-Aware Markov Models for Discrete Reasoning

arXiv: https://arxiv.org/abs/2603.16661 · HTML: https://mlsanity.com/paper/2603.16661/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 20 of its 24 references that are in the map.
- First posted on arXiv 17 Mar 2026.

## Placed in

- Diffusion models / [Discrete and text diffusion](https://mlsanity.com/diffusion/discrete-and-text-diffusion/)

## Builds on (most cited first, 20 of 20)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Scalable Diffusion Models with Transformers](https://mlsanity.com/paper/2212.09748/) (2022)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Variational Diffusion Models](https://mlsanity.com/paper/2107.00630/) (2021)
- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [Discrete Flow Matching](https://mlsanity.com/paper/2407.15595/) (2024)
- [Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design](https://mlsanity.com/paper/2402.04997/) (2024)
- [Flow Matching Guide and Code](https://mlsanity.com/paper/2412.06264/) (2024)
- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Remasking Discrete Diffusion Models with Inference-Time Scaling](https://mlsanity.com/paper/2503.00307/) (2025)
- [d1: Scaling Reasoning in Diffusion Large Language Models via Reinforcement Learning](https://mlsanity.com/paper/2504.12216/) (2025)
- [Hierarchical Reasoning Model](https://mlsanity.com/paper/2506.21734/) (2025)
- [A Reparameterized Discrete Diffusion Model for Text Generation](https://mlsanity.com/paper/2302.05737/) (2023)
- [Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning](https://mlsanity.com/paper/2410.14157/) (2024)
- [wd1: Weighted Policy Optimization for Reasoning in Diffusion Language Models](https://mlsanity.com/paper/2507.08838/) (2025)
- [Generalized Interpolating Discrete Diffusion](https://mlsanity.com/paper/2503.04482/) (2025)
- [Fine-Tuning Masked Diffusion for Provable Self-Correction](https://mlsanity.com/paper/2510.01384/) (2025)
- [Diffusion of Thoughts: Chain-of-Thought Reasoning in Diffusion Language Models](https://mlsanity.com/paper/2402.07754/) (2024)
- [Telegrapher's Generative Model via Kac Flows](https://mlsanity.com/paper/2506.20641/) (2025)
- [Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error](https://mlsanity.com/paper/2509.22023/) (2025)

## Built on by (most cited first, 1 of 1)

- [Spherical Flows for Sampling Categorical Data](https://mlsanity.com/paper/2605.05629/) (2026)

## Abstract (arXiv)

Standard masked discrete diffusion models face limitations in reasoning tasks due to their inability to correct their own mistakes on the masking path. Since they rely on a fixed number of denoising steps, they are unable to adjust their computation to the complexity of a given problem. To address these limitations, we introduce a method based on learning a Markov transition kernel that is trained on its own outputs. This design enables tokens to be remasked, allowing the model to correct its previous mistakes. Furthermore, we do not need a fixed time schedule but use a trained stopping criterion. This allows for adaptation of the number of function evaluations to the difficulty of the reasoning problem. Our adaptation adds two lightweight prediction heads, enabling reuse and fine-tuning of existing pretrained models. On the Sudoku-Extreme dataset we clearly outperform other flow based methods with a validity of 95%. For the Countdown-4 we only need in average of 10 steps to solve almost 96% of them correctly, while many problems can be solved already in 2 steps.