Research map / Large language models / Reasoning and chain of thought

On the Reasoning Abilities of Masked Diffusion Language Models

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 0 citations (OpenAlex)

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.

Characterizes the expressivity of idealized masked diffusion language models by showing they are equivalent to padded looped transformers, can simulate chain-of-thought (and vice versa up to overhead), and are provably more efficient than CoT on parallelizable problems such as regular languages.

Problem

What reasoning problems masked diffusion language models (MDMs) can provably solve and how efficiently, given their parallel generation, compared to chain-of-thought transformers and looped transformers.

Approach

Introduces an idealized MDM with a learned planner (choosing which positions to unmask, allowing resampling) and a predictor, all implemented as finite-precision log-width transformers; connects it to padded looped transformers and parallel CoT to derive exact complexity-class characterizations.

Key results

• MDMs with polylogarithmically many denoising steps and polynomial padding are equivalent to uniform AC^d; with log n steps they converge to NC, so MDMs with log n steps can recognize all regular languages.
• Finite-precision MDMs with O(1) denoising steps are equivalent to LUniform AC0, no more powerful than standard transformers.
• CoT transformers with log n steps are contained in TC0 while MDMs with log n steps (polynomial padding) contain NC1-complete regular languages, giving a strict separation CoT[log n] subsetneq MDM[log n, n].

Surprising findings

• Causal masking exact simulation requires quadratically more output space, so unmasked MDMs are less efficient than CoT in padding terms.

Limitations

• Results are for idealized MDMs with a perfect planner and perfect unmasker; learnability of the planner is not addressed.
• No empirical validation; lack of training on formal languages makes practical implications unclear.
• Analysis restricted to transformer-implemented MDMs with log-width finite-precision and external positional encodings.

Experimental setup

Builds on: chain-of-thought expressivity results padded looped transformers masked diffusion models log-precision transformer circuit analysis

Closest papers by meaning

• Scaling up Masked Diffusion Models on Text (ICLR 2025 · similarity 0.93)
• Theoretical Benefit and Limitation of Diffusion Language Model (NeurIPS 2025 · similarity 0.92)
• Looped Diffusion Language Models (NeurIPS 2026 · similarity 0.91)
• The Flexibility Trap: Rethinking the Value of Arbitrary Order in Diffusion Language Models (ICML 2026 · similarity 0.90)
• UnMaskFork: Test-Time Scaling for Masked Diffusion via Deterministic Action Branching (ICML 2026 · similarity 0.90)
• d2: Improving Reasoning in Diffusion Language Models via Trajectory Likelihood Estimation (ICML 2026 · similarity 0.90)