Planner-Guided Recursive Exploration for Diffusion Language Model Decoding

Masked diffusion language models (DLMs) enable parallel text generation by iteratively refining masked tokens, offering a promising alternative to autoregressive decoding. Recent search-based decoding methods improve the accuracy--efficiency trade-off by exploring multiple candidate decoding trajectories before committing token updates. However, existing search-based decoding methods face two key limitations. First, they offer limited guidance on when search is actually beneficial for the current decoding state. Second, they typically rely on a shallow one-step search horizon, which may favor locally promising but suboptimal decoding trajectories. To address these limitations, we propose PRED, a planner-guided recursive exploration framework for DLM decoding. PRED employs a learned planner to determine when search should be triggered, and performs adaptive multi-step rollout to evaluate candidate trajectories over longer horizons. Moreover, the same planner is recursively applied to intermediate rollout states to determine whether additional branch expansion is needed, allowing PRED to re-initiate search when necessary. Experiments across multiple benchmarks and DLM backbones show that PRED achieves a better accuracy--efficiency trade-off than existing confidence-based and search-based decoding methods.