See Every Block Once: Variance-Reduced Post-Training for Masked Diffusion Language Models

Yunzhen He, Hiroaki Yamagiwa, Hidetoshi ShimodairaarXiv 2026 · arXiv

Aligning Large Language Models (LLMs) with human preferences typically relies on policy gradient methods like RLHF. These methods require calculating the log-likelihood of a model's response—a straightforward task for standard auto-regressive models. However, for the emerging class of Masked Diffusion Language Models (MDLMs), which generate text by progressively unmasking tokens in a non-linear fashion, computing exact log-likelihoods is computationally intractable.

A new paper from researchers at Kyoto University, SB Intuitions, and RIKEN AIP proposes a simple yet powerful fix: the Full-block Estimator. By ensuring the training process "sees every block once," they significantly stabilize the alignment of MDLMs, leading to dramatic performance gains in reasoning and coding tasks.

TL;DR

The authors propose a "full-block estimator" for post-training Masked Diffusion Language Models that replaces random block sampling with a deterministic evaluation of every sequence block. This approach eliminates variance caused by block selection, resulting in an average 12.79-point accuracy improvement across five major benchmarks.

What Problem Does This Paper Address?

MDLMs are gaining traction because they can generate text more flexibly than traditional left-to-right models. To make them useful, we need to "align" them—training them to follow instructions or prefer certain types of answers. Since we can't compute exact log-likelihoods for MDLMs, researchers use a surrogate objective based on the Evidence Lower Bound (ELBO).

Modern MDLMs often use blockwise generation, where the sequence is divided into chunks (blocks) generated sequentially. To estimate the training objective, current methods randomly sample these blocks. However, as the authors point out, random sampling is incredibly noisy. If you have four blocks and take four samples, there is a 91% probability that at least one block will be missed entirely, while others are duplicated. This "block selection variance" makes the training signal unstable and hinders the model's ability to learn complex reasoning.

The instability of random sampling: even with K=4 samples for C=4 blocks, many blocks are frequently missed (red boxes).

Methods

The core contribution is the Full-block Estimator. Instead of independently sampling blocks for each Monte Carlo step, the method evaluates every single block in the sequence exactly once and averages the results.

Comparison of the proposed Full-block Estimator (top) vs. the existing Random Block Sampling (bottom).

Mathematically, this is equivalent to stratified sampling where each block is its own stratum. The authors prove that this estimator remains unbiased but successfully eliminates the "between-group variance"—the noise that comes from which blocks you happened to pick. This ensures that every part of the generated response provides a learning signal to the model in every training step.

Datasets

The researchers evaluated their method using LLaDA-8B-Instruct as the base model across five diverse benchmarks:

  • Mathematics: GSM8K and MATH-500.
  • Planning/Search: Countdown and Sudoku (4x4).
  • Coding: HumanEval (using training data from Open R1).

Key Insights and Ideas

  • The "Missing Block" Problem: The paper highlights that the primary weakness in current MDLM post-training isn't the objective itself, but the instability of the estimator. Missing a block means the model receives no feedback on that part of its output for that iteration.
  • Variance Reduction for "Free": By simply changing the sampling strategy to be deterministic across blocks, the authors achieved a variance reduction of approximately 10x at the estimator level compared to random sampling.
  • Superior Estimation Quality: The full-block estimator with only 4 samples achieves a Spearman rank correlation (a measure of how well it ranks different outputs) comparable to a random sampler using 32 samples. This represents a massive increase in sample efficiency.
Estimation quality on GSM8K. The Full-block estimator (star) at K=4 matches the quality of random sampling at K≈32.

Key Results

The Full-block Estimator outperformed the random sampling baseline on all five benchmarks, often by huge margins:

  • Sudoku: Jumped from 61.20% to 91.39% accuracy.
  • Countdown: Improved by over 22 points compared to the random baseline.
  • Average Gain: Across all tasks, the method outperformed the random block sampling baseline by 12.79 points and the previous state-of-the-art (SPG) by 5.05 points.
  • Consistency: The method achieved the highest accuracy on four out of the five benchmarks tested.

Limitations and Future Work

  • Memory Overhead: Evaluating all blocks in parallel increases GPU VRAM usage linearly with the number of blocks ($C$). While manageable for $C=4$ or $8$, very long sequences with many blocks might require sequential gradient accumulation, trading off training time for memory.
  • Task Scope: The evaluation focused on "hard" reasoning and coding tasks where rule-based verifiers are available. Its effectiveness on open-ended natural language generation (like creative writing or summarization) remains to be seen.
  • Disentanglement: The authors note they haven't fully disentangled how much of the gain comes from pure variance reduction versus the benefit of providing a "learning signal" to every block simultaneously. Exploring this balance is a suggested path for future research.

Summary updated

Abstract

Policy gradient methods are widely used to align large language model outputs with human preferences, but the log-likelihoods they require cannot be directly computed in Masked Diffusion Language Models (MDLMs). MDLM post-training therefore relies on a surrogate objective based on the Evidence Lower Bound (ELBO), and recent work estimates a blockwise variant of this objective via Monte Carlo methods to support blockwise generation. However, existing estimation schemes randomly sample the block index, so they may evaluate the same block more than once and leave some blocks unevaluated. This introduces variance arising from block selection into the estimates. In this work, we propose a full-block estimator that evaluates every block exactly once and averages the results. We theoretically show that the proposed estimator remains unbiased while eliminating the between-group variance arising from block selection, thereby achieving lower variance than the baseline for the same sample size. In experiments on five benchmarks spanning mathematics, planning, and coding, our method achieves the highest accuracy on four benchmarks and outperforms the random block sampling baseline by an average of 12.79 points.
BibTeX
@misc{he2026see,
  author = {Yunzhen He and Hiroaki Yamagiwa and Hidetoshi Shimodaira},
  title = {{See Every Block Once: Variance-Reduced Post-Training for Masked Diffusion Language Models}},
  year = {2026},
  eprint = {2611.17754},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17754},
}
Figure