Can I Have Your Order? Monte-Carlo Tree Search for Slot Filling Ordering in Diffusion Language Models

2026-02-16 · Source: cs.AI updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, long

Summary

McDiffuSE is a novel framework that enhances the performance of Masked Diffusion Models (MDMs) for mathematical and code reasoning by optimizing slot infilling order using Monte Carlo Tree Search (MCTS). MDMs, while offering inference efficiency and non-sequential decoding, often underperform autoregressive models due to sensitivity to generation order. McDiffuSE addresses this by formulating slot selection as a sequential decision-making problem, employing look-ahead simulations to evaluate partial completions and explore the combinatorial space of generation orders. Experiments show McDiffuSE improves average performance by 3.2% over autoregressive baselines and 8.0% over baseline plan-and-infill methods, with significant gains of 19.5% on MBPP and 4.9% on MATH500. The framework's success stems from its ability to strategically incorporate non-sequential generation and its emphasis on exploration breadth over simulation depth to overcome model confidence biases.

Key takeaway

For research scientists developing or deploying Masked Diffusion Models for reasoning tasks, you should integrate MCTS-based planning to optimize slot infilling order. This approach, particularly with a high exploration constant, can significantly improve accuracy on benchmarks like MBPP and MATH500, closing the performance gap with autoregressive models by strategically balancing sequential and non-sequential generation.

Key insights

MCTS-guided slot ordering in diffusion models significantly improves reasoning task performance by balancing sequential and non-sequential generation.

Principles

• Optimal generation order is critical for MDM performance.
• MCTS can overcome model confidence biases.
• Exploration breadth is key for discovering effective orderings.

Method

McDiffuSE formulates slot selection as a Markov Decision Process, using MCTS with prior-guided expansion and a hybrid reward mechanism to identify optimal infilling orders through look-ahead simulations.

In practice

• Prioritize exploration constant over simulation depth in MCTS.
• Consider non-sequential generation for complex reasoning tasks.

Topics

• Diffusion Models
• Monte Carlo Tree Search
• Slot Filling Ordering
• LLM Reasoning
• Code Generation

Best for: Research Scientist, AI Researcher, AI Scientist, Machine Learning Engineer

Related on AIssential

• DiG-Plan: Mitigating Early Commitment for Tool-Graph Planning via Diffusion Guidance — Autoregressive decoding's "early commitment" limits tool-set exploration; diffusion models offer superior combinatorial search.
• Bastion: Budget-Aware Speculative Decoding with Tree-structured Block Diffusion Drafting — BASTION dynamically constructs query-dependent trees for speculative decoding, balancing draft quality and hardware constraints.
• Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs — Budget-Guided MCTS dynamically adjusts LLM tree-search from broad exploration to focused refinement based on remaining token budget.
• Beyond the Commitment Boundary: Probing Epiphenomenal Chain-of-Thought in Large Reasoning Models — Large language models exhibit a "commitment boundary" in Chain-of-Thought reasoning, after which subsequent steps are epiphenomenal.
• DreamReasoner-8B: Block-Size Curriculum Learning for Diffusion Reasoning Models — Block-size curriculum learning enables efficient diffusion models to achieve strong long chain-of-thought reasoning by bridging granularity gaps.
• Teaching Diffusion to Speculate Left-to-Right — Aligning bidirectional diffusion drafters with left-to-right autoregressive verification significantly boosts speculative decoding efficiency.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.AI updates on arXiv.org.