Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models

Inference-time compute has re-emerged as a practical way to improve LLM reasoning. Most test-time scaling (TTS) algorithms rely on autoregressive decoding, which is ill-suited to discrete diffusion language models (dLLMs) due to their parallel decoding over the entire sequence. As a result, developing effective and efficient TTS methods to unlock dLLMs' full generative potential remains an underexplored challenge. To address this, we propose \textbf{LLaDA-S}, an efficient TTS framework for dLLMs that (i) performs \textbf{Hierarchical Trajectory Search} (HTS) which dynamically prunes and reallocates compute in an early-to-mid denoising window, (ii) replaces external verifiers with \textbf{Self-Verified Feedback} (SVF) obtained via self-evaluation prompts on intermediate completions, and (iii) introduces \textbf{Local branching with partial remasking} to explore diverse implementations while preserving a high-confidence tokens. Across four mathematical reasoning and code generation benchmarks on three dLLMs, including LLaDA 8B Instruct, Dream 7B Instruct, and LLaDA 2.0-mini, our LLaDA-S achieves a favorable performance-efficiency trade-off, matching best-of-$N$ performance with substantially fewer function evaluations (NFE). The code will be released.

Large language models can often answer difficult math and programming questions better when they spend more computation at test time, for example by trying several possible solutions and choosing the best one. However, most existing methods are designed for models that write answers strictly from left to right. This makes them less suitable for a newer class of language models that generate text by repeatedly improving an entire draft. This paper introduces PRISM, a method that helps these models use extra computation more efficiently. Instead of fully completing many independent answers, PRISM first explores several possible drafts, then gradually focuses computation on the more promising ones. It also revises uncertain parts of a draft while keeping confident parts unchanged, allowing the model to explore alternatives without starting over. To decide which drafts are promising, PRISM asks the same model to judge its own intermediate answers, avoiding the need for a separate verifier model. Across math reasoning and code generation benchmarks, PRISM improves answer quality while using substantially less computation than simple repeated sampling.