# Tree Reward-Aligned Search for TReASURe in Masked Diffusion Language Models

arXiv: https://arxiv.org/abs/2509.23146 · HTML: https://mlsanity.com/paper/2509.23146/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Discrete and text diffusion, one of 14 directions in Diffusion models.
- Builds on 53 of its 60 references that are in the map.
- First posted on arXiv 27 Sep 2025.

## Placed in

- Diffusion models / [Discrete and text diffusion](https://mlsanity.com/diffusion/discrete-and-text-diffusion/)

## Builds on (most cited first, 30 of 53)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Visual Instruction Tuning](https://mlsanity.com/paper/2304.08485/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2-VL: Enhancing Vision-Language Model's Perception of the World at Any Resolution](https://mlsanity.com/paper/2409.12191/) (2024)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [InternVL: Scaling up Vision Foundation Models and Aligning for Generic Visual-Linguistic Tasks](https://mlsanity.com/paper/2312.14238/) (2023)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [PaLM-E: An Embodied Multimodal Language Model](https://mlsanity.com/paper/2303.03378/) (2023)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Diffusion Posterior Sampling for General Noisy Inverse Problems](https://mlsanity.com/paper/2209.14687/) (2022)
- [Neural Network Acceptability Judgments](https://mlsanity.com/paper/1805.12471/) (2018)
- [Large Language Diffusion Models](https://mlsanity.com/paper/2502.09992/) (2025)
- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [Dream 7B: Diffusion Large Language Models](https://mlsanity.com/paper/2508.15487/) (2025)
- [A Continuous Time Framework for Discrete Denoising Models](https://mlsanity.com/paper/2205.14987/) (2022)
- [TweetEval: Unified Benchmark and Comparative Evaluation for Tweet Classification](https://mlsanity.com/paper/2010.12421/) (2020)
- [LLaDA 1.5: Variance-Reduced Preference Optimization for Large Language Diffusion Models](https://mlsanity.com/paper/2505.19223/) (2025)
- [Scaling Diffusion Language Models via Adaptation from Autoregressive Models](https://mlsanity.com/paper/2410.17891/) (2024)
- [MMaDA: Multimodal Large Diffusion Language Models](https://mlsanity.com/paper/2505.15809/) (2025)
- [Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning](https://mlsanity.com/paper/2405.00451/) (2024)
- [Quark: Controllable Text Generation with Reinforced Unlearning](https://mlsanity.com/paper/2205.13636/) (2022)

## Built on by (most cited first, 2 of 2)

- [ProFlow: Zero-Shot Physics-Consistent Sampling via Proximal Flow Guidance](https://mlsanity.com/paper/2601.20227/) (2026)
- [UnMaskFork: Test-Time Scaling for Masked Diffusion via Deterministic Action Branching](https://mlsanity.com/paper/2602.04344/) (2026)

## Abstract (arXiv)

Tree search has recently emerged as a powerful framework for aligning generative models with task-specific rewards at test time. Applying tree search to Masked Diffusion Language Models, however, introduces two key challenges: (i) parallel unmasking yields highly correlated branches, limiting exploration, and (ii) reward evaluation via sampled completions produces high-variance estimates, making pruning unstable. We propose TReASURe, a tree-search test-time alignment method that addresses these issues. It introduces (i) UnmaskBranch, a branching strategy based on first-hitting unmasking that diversifies both token content and reveal order with a single model call per parent node, and (ii) ResubstituteScore, a pruning rule that uses deterministic resubstitution to score partially masked sequences with low-variance proxy completions. Theoretically, we quantify branching efficiency gains in NFEs (number of function evaluations), show that the scoring rule approximates the true reward with error bounded by predictive uncertainty, and prove improvements with larger tree widths. Empirically, TReASURe achieves state-of-the-art results on perplexity, linguistic acceptability, and control of sentiment and toxicity, outperforming prior methods under matched compute budgets, with especially strong gains in low-NFE regimes.