Research map / Large language models / Reasoning and chain of thought

Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes PRISM, a test-time scaling framework for discrete diffusion LLMs that combines hierarchical trajectory search with partial remasking and self-verified Yes/No feedback from the same dLLM, matching best-of-N accuracy at a fraction of NFE.

Problem

Test-time scaling for discrete diffusion language models is underexplored; best-of-N over full denoising trajectories is compute-heavy (O(NT) NFE) and external verifiers add memory overhead.

Approach

Geometric-decay pruning of trajectories during an early-to-mid denoising window, guided by a self-verification Yes-probability score from the dLLM itself, with local branching via partial remasking of low-confidence tokens to create diverse children from surviving states.

Key results

• On LLaDA-8B, PRISM (K=8) raises GSM8K from 67.58% to 85.30% using 1,048 NFE, versus 87.50% for Best-of-16 at 4,096 NFE.
• PRISM (K=8) on LLaDA-2.0-mini reaches 82.32% on HumanEval (NFE 3168), matching Best-of-16's 82.32% at 8192 NFE.
• Replacing SVF with random pruning drops GSM8K accuracy by 3.56 to 4.32 points across K settings on LLaDA-8B.

Surprising findings

• Self-verification from the same dLLM matched or beat some external Qwen verifiers on GSM8K, with PRISM at 85.30 vs Qwen-7B verifier 84.39 but below Qwen2-7B (85.98) and Qwen3-8B (87.35).

Limitations

• Gains are reported primarily on math and code benchmarks; SVF reliability is only moderate (F1 0.63-0.73).
• Some comparisons (MEDAL, RFG) rely on published numbers under different inference settings.
• Hyperparameters such as pruning window, decay, and survivors are tuned on the evaluation benchmarks, mainly HumanEval.

Experimental setup

Datasets: GSM8K MATH500 HumanEval MBPP TruthfulQA

Benchmarks: GSM8K MATH500 HumanEval MBPP TruthfulQA

Metrics: accuracy pass@1 NFE ROUGE-1/2/L F1 ECE

Baselines: Best-of-N (N=1,4,8,16) ReMDM MEDAL RFG PG-DLM HEX Qwen-7B verifier Qwen2-7B verifier Qwen3-8B verifier

Builds on: best-of-N masked diffusion models ReMDM self-consistency

Closest papers by meaning

• TEST-TIME SCALING IN DIFFUSION LLMS VIA HIDDEN SEMI-AUTOREGRESSIVE EXPERTS (ICLR 2026 · similarity 0.92)
• UnMaskFork: Test-Time Scaling for Masked Diffusion via Deterministic Action Branching (ICML 2026 · similarity 0.91)
• d2: Improving Reasoning in Diffusion Language Models via Trajectory Likelihood Estimation (ICML 2026 · similarity 0.90)
• Fast-dLLM++: Fr\'{e}chet Profile Decoding for Faster Diffusion LLM Inference (NeurIPS 2026 · similarity 0.90)
• Lookahead Path Likelihood Optimization for Diffusion LLMs (ICML 2026 · similarity 0.90)
• DISC: Dynamic Decomposition Improves LLM Inference Scaling (NeurIPS 2025 · similarity 0.90)