$S^3$: Stratified Scaling Search for Test-Time in Diffusion Language Models
This addresses the challenge of inefficient compute use in test-time scaling for diffusion language models, offering a practical solution for researchers and practitioners, though it is incremental as it builds on existing search methods.
The paper tackled the problem of improving output quality in diffusion language models at test-time without additional training, by proposing S^3, a verifier-guided search method that reallocates compute during denoising, and it achieved consistent performance gains across benchmarks, with the largest improvements on mathematical reasoning tasks.
Test-time scaling investigates whether a fixed diffusion language model (DLM) can generate better outputs when given more inference compute, without additional training. However, naive best-of-$K$ sampling is fundamentally limited because it repeatedly draws from the same base diffusion distribution, whose high-probability regions are often misaligned with high-quality outputs. We propose $S^3$ (Stratified Scaling Search), a classical verifier-guided search method that improves generation by reallocating compute during the denoising process rather than only at the final output stage. At each denoising step, $S^3$ expands multiple candidate trajectories, evaluates them with a lightweight reference-free verifier, and selectively resamples promising candidates while preserving diversity within the search frontier. This procedure effectively approximates a reward-tilted sampling distribution that favors higher-quality outputs while remaining anchored to the model prior. Experiments with LLaDA-8B-Instruct on MATH-500, GSM8K, ARC-Challenge, and TruthfulQA demonstrate that $S^3$ consistently improves performance across benchmarks, achieving the largest gains on mathematical reasoning tasks while leaving the underlying model and decoding schedule unchanged. These results show that classical search over denoising trajectories provides a practical mechanism for test-time scaling in DLMs.