@inproceedings{huang-etal-2026-diffusion,
    title = "Diffusion Language Model Inference with {M}onte {C}arlo Tree Search",
    author = "Huang, Zheng  and
      Ramnath, Kiran  and
      Chen, Yueyan  and
      Feng, Aosong  and
      Woo, Sangmin  and
      Srinivasan, Balasubramaniam  and
      Xu, Zhichao  and
      Zhou, Kang  and
      Wang, Shuai  and
      Ding, Haibo  and
      Cheong, Lin Lee",
    editor = "Demberg, Vera  and
      Inui, Kentaro  and
      Marquez, Llu{\'i}s",
    booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {EACL} 2026",
    month = mar,
    year = "2026",
    address = "Rabat, Morocco",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-eacl/2026.findings-eacl.180/",
    pages = "3493--3512",
    ISBN = "979-8-89176-386-9",
    abstract = "Diffusion language models (DLMs) have recently emerged as a compelling alternative to autoregressive generation, offering parallel generation and improved global coherence. During inference, DLMs generate text by iteratively denoising masked sequences in parallel; however, determining which positions to unmask and which tokens to commit forms a large combinatorial search problem. Existing inference methods approximate this search using heuristics, which often yield suboptimal decoding paths; other approaches instead rely on additional training to guide token selection. To introduce a principled search mechanism for DLMs inference, we introduce MEDAL, an inference-time scaling framework that integrates Monte Carlo Tree SEarch initialization for Diffusion LAnguage Model inference. We employ Monte Carlo Tree Search at the initialization stage to explore promising unmasking trajectories, providing a robust starting point for subsequent refinement. This design enables efficient inference-time scaling, allowing generation quality to improve as the search budget increases, without additional training. Across multiple benchmarks, MEDAL achieves up to 22.0{\%} improvement over existing inference strategies, establishing a new paradigm for search-based inference in DLMs."
}