On the Efficiency of Temperature-Adaptive Monte Carlo Tree Diffusion for Diffusion Language Model Reasoning

Monte Carlo Tree Diffusion (MCTD) [1] reframed continuous diffusion planning as tree-structured search via UCB1-guided Monte Carlo Tree Search (MCTS); unlike MEDAL [2], however, it provided no mechanism for adapting sampling temperature. We extend this "denoising-as-tree-search" paradigm to discrete diffusion language models (dLLMs), framing the block-wise denoising trajectory of LLaDA-8B-Instruct [3] as a search tree in which each node is a partially denoised sequence state and each action denoises the next block under a chosen sampling temperature. On GSM8K, we compare four decoders under a compute-matched budget, matched by number of function evaluations (NFEs): greedy decoding, best-of-N sampling, fixed-temperature UCB1-MCTS with progressive widening, and a depth-varying temperature-adaptive schedule applying high temperatures to early coarse blocks and low temperatures to late refinement blocks—in contrast to concurrent token-level dLLM search methods that restrict search to a capped initialization prefix without temperature control. Under matched NFE, all search-based decoders substantially outperform greedy decoding (65–75% vs. 45%, the greedy figure reflecting our constrained per-block NFE budget rather than the model's unconstrained accuracy). Fixed-temperature MCTS further improves over best-of-N (70% vs. 65%), indicating that UCB1 trajectory sharing contributes structural value beyond independent resampling. However, once full tree depth is restored, the adaptive and fixed-temperature schedules perform indistinguishably. We attribute this to algorithmic redundancy: UCB1 action selection combined with progressive widening already manages the exploration–exploitation balance across search depths, leaving explicit temperature scheduling little to add. These results suggest that tree structure, not temperature control, drives the gains for discrete-diffusion reasoning, and motivates a shift toward tree depth and node-selection mechanisms in future test-time dLLM search.