acceptodds
Under review as a conference paper at ICLR 2027

PRESTO: Prefix-Aligned Tree Drafting for Diffusion Speculative Decoding

10 views

Abstract

Diffusion LLMs (dLLMs) have emerged as effective draft models for speculative decoding (SD), generating a block of draft tokens in a single forward pass. However, existing diffusion drafters follow a single draft path, even though dLLMs produce multiple candidates at every position, inducing a large combinatorial space of paths; exploring only a tiny fraction of it fundamentally limits acceptance length. We introduce tree-based drafting for diffusion drafters to exploit this multi-candidate structure, but find that naive tree drafting is suboptimal: diffusion marginals are inherently prefix-blind, mismatching prefix-based AR verification and yielding unreliable path ranking. We propose PRESTO (PREfix-aligned Scoring and priority-based Tree search for diffusion speculative decOding), a principled framework built on two principles: (1) candidate ranking should align with the prefix-based nature of AR verification, and (2) tree construction should prioritize paths with high verification potential to maximize acceptance length. PRESTO exhibits strong generalizability across diffusion drafting paradigms, applying unchanged as a drop-in framework to both dedicated diffusion drafters and self-speculative dLLMs that draft and verify within a single forward pass. Across diverse benchmarks, PRESTO achieves average end-to-end speedups of 1.5× over the diffusion drafter DFlash and up to 2.14× over self-speculative dLLMs.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Speculative Decoding, Diffusion Language Model

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_WQKxOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

PRESTO constructs draft trees from the parallel position-wise predictions of diffusion drafters. It combines diffusion marginal probabilities with a prefix-dependent compatibility signal, implemented using an n-gram model built from target-model-generated text, and uses additive path scores to guide priority-based tree search. The framework supports both dedicated diffusion drafters and self-speculative diffusion models. Experiments report improvements over single-path drafting, comparisons with DDTree, and ablations of the scoring signal, search parameters, and n-gram order.

Critical strengths
  1. Practically useful integration into self-speculative diffusion decoding.

Extending tree drafting to a pipeline that jointly verifies previous drafts and generates subsequent candidates is a valuable systems contribution. The treatment of branch-specific attention, accepted-path state, and reusable speculative outputs provides a concrete way to exploit multiple candidates without additional full-model forward passes for tree construction.

  1. The evaluation provides evidence beyond single-path comparisons.

Appendix K reports improvements over DDTree across two models and three node budgets, with acceptance-length gains of 0.29–0.35 and throughput ratios of 1.04–1.10×. Appendix J further investigates n-gram order, memory footprint, and an alternative neural prefix scorer. These results support the usefulness of an inexpensive prefix signal for improving draft-tree quality.

Critical weaknesses
  1. The distinct contribution over existing prefix-aware and causally conditioned tree construction remains insufficiently isolated.

DART already combines parallel draft probabilities with n-gram conditional scores and uses beam expansion with global node retention. PRESTO makes meaningful distinctions through target-generated counts and its self-speculation integration. However, the experiments do not compare the scoring rules under a matched drafter, candidate set, search procedure, and tuning budget, or directly isolate the benefit of target-generated counts over ordinary corpus counts.

Related methods such as DominoTree and DARTree also explore causal correction along individual branches. The Qwen3-0.6B comparison in Appendix J is useful, but a general-purpose small LM used as a scorer does not fully represent a specialized lightweight causal-correction head. The current evidence therefore more clearly establishes that prefix information helps than it establishes PRESTO’s quality–cost advantage over alternative prefix models. Concurrent methods can be addressed through technical discussion or targeted experiments without requiring reproduction of every baseline.

  1. The independent contribution of tree construction and pruning, and the advantage under cost-aware budgets, remain unclear.

Global reranking and retention after expansion have established precedents, including EAGLE-2. PRESTO includes beam-versus-best-first comparisons and search-parameter ablations, but should more clearly separate improvements attributable to prefix scoring, candidate coverage, and the expansion/pruning policy itself. In particular, the numbers of scored candidates, nodes retained for further expansion, and nodes passed to verification should be distinguished.

Moreover, CaDDTree already jointly considers acceptance gains and verification costs to select diffusion-tree budgets per round. PRESTO’s throughput-based selection among fixed budgets and its latency breakdown are valuable, but do not fully establish whether its advantage persists under matched time budgets or adaptive budget selection. Evaluation with a default batch size of one on B200 GPUs also limits conclusions about other workloads and hardware conditions.

Questions for authors
  1. Causally conditioned scoring: How does PRESTO compare with lightweight branch-state-based causal correction in acceptance length, tree-construction latency, and memory usage? If a direct comparison is infeasible, please clarify the applicability and key design differences.

  2. Pruning and cost-aware budgets: With scoring and verification budget fixed, how much improvement comes from expansion, candidate retention, and pruning? Can the authors provide a cost-aware DDTree baseline, or acceptance–latency curves across node budgets and context lengths?

Reviewer_pYMwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

PRESTO improves speculative decoding when a diffusion model supplies parallel draft-token distributions. The paper argues that multiplying position-wise diffusion marginals overlooks dependencies on the chosen draft prefix, leading to suboptimal tree ranking. PRESTO supplements these marginals with a prefix-conditioned n-gram score estimated from target-generated text and uses the resulting scores for budgeted tree construction.

The framework supports both separate diffusion drafters for autoregressive targets and hybrid models performing verification and diffusion drafting within one forward pass. Experiments report substantial improvements over linear dFlash drafting and gains in both linear and quadratic self-speculation. Additional comparisons with DDTree isolate the incremental contribution of prefix-conditioned scoring.

Critical strengths

1 A useful diagnosis supported by targeted experiments. The paper identifies a plausible limitation of using parallel diffusion marginals to rank prefix-dependent verification paths. The acceptance analysis suggests that the prefix-conditioned signal contains information beyond marginal confidence. The matched-search DDTree comparison is particularly useful: it reports approximately 0.29–0.35 additional accepted tokens and 4%–10% higher throughput, providing evidence that the correction contributes beyond merely replacing a chain with a tree.

2 Meaningful integration across distinct decoding pipelines. PRESTO is evaluated with several Qwen targets and with Nemotron-Labs-Diffusion under both linear and quadratic self-speculation. The SGLang integration strengthens the practical evidence: even in that optimized linear pipeline, reported average throughput improves by approximately 6% under greedy decoding and 17% under sampling. The larger gains in quadratic self-speculation further demonstrate that the framework can exploit different verification layouts.

Critical weaknesses
  1. The implemented score does not equal the surrogate prefix probability used to justify tree construction. Equation 6 defines normalized conditionals, and Appendix C explicitly introduces the prefix-dependent normalization factor. Consequently, the log probability of a path should satisfy S(P)−∑d=1klog⁡Zd(cd).S(P)-\sum_{d=1}^{k}\log Z_d(c_d).

Equation 8 omits these terms, while Section 4.2 equates its score with the log surrogate probability. The normalization factors vary across prefixes, so they cannot generally be discarded when comparing branches or allocating nodes across depths. This undermines the claimed connection between the implemented search and maximizing expected acceptance under the stated surrogate. The scoring rule may remain an effective heuristic, but the current probabilistic derivation does not justify it as written.

  1. The incremental contribution and practical cost need stronger positioning. Much of the headline improvement is measured against linear drafting; the closest tree baseline, DDTree, narrows the additional throughput gain to 4%–10%. The paper also describes DART as using n-gram-guided tree pruning, but provides no direct experimental comparison establishing the advantage of PRESTO’s scoring formulation. Moreover, the proposed prefix signal requires a corpus of one billion target-generated tokens and a 4.5 GB trigram trie. These are material preparation and storage requirements. The five-minute counting time does not account for generating the corpus, and comparisons against ordinary-text n-grams or smaller target-generated corpora are missing.
Questions for authors
  1. Scoring clarification: Does the implementation include the prefix-dependent normalization factors? If not, can the theoretical claims be revised and normalized versus unnormalized scoring compared under the same tree budget?

  2. Contribution relative to prior work: How does PRESTO compare with DART under matched candidates, node budgets, and verification backends? Does using target-generated text outperform an n-gram model built from the original corpus at comparable size?

  3. Practical preparation cost: What is the GPU cost of producing the one-billion-token corpus, and is it regenerated for each target? Where does the 4.5 GB trie reside during inference, and how do acceptance and end-to-end throughput change with smaller corpora or compressed tries?

  4. Verification and evaluation clarification: At temperature one, is a single target sample drawn at each reached prefix and shared across sibling comparisons? Please specify the sampling procedure supporting distribution preservation. Appendix H reports task-level quality rather than distributional equivalence; greedy token-agreement measurements and repeated timing results would also strengthen the implementation evidence.

Reviewer_fLcbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper argues that naively applying tree-based drafting to diffusion drafters in speculative decoding is suboptimal because diffusion marginals are inherently prefix-blind and thus mismatched with prefix-based AR verification. To address this, the authors propose PRESTO, a training-free tree drafting framework for diffusion drafters. It applies a prefix-dependent correction to the diffusion marginals using a lightweight target-aligned n-gram model. Experiments on both dedicated diffusion drafters and self-speculative dLLMs show that PRESTO improves average acceptance length and end-to-end throughput over the corresponding linear drafting baselines.

Critical strengths
  • The motivation is clear, and the paper empirically shows that diffusion marginals provide an informative estimate of the global acceptance likelihood but are insufficient for ranking candidate tokens (Figure 2).
  • PRESTO consistently improves the average acceptance length and end-to-end throughput over linear drafting baselines.
  • PRESTO is applicable to both dedicated diffusion drafters and self-speculative dLLMs.
  • The additional target-aligned n-gram model is training-free and adds little overhead at inference time.
Critical weaknesses
  • While the paper argues that "naively applying tree-based drafting to diffusion drafters is suboptimal," the main results in Tables 2–4 compare PRESTO only against linear drafting baselines, not against naive tree drafting baselines.
  • The paper introduces qdq_{d} as the diffusion marginal of a candidate token, but Observation 2 describes the predicted confidence as the exponentiated cumulative log-probability along a path. Figure 2(b) nevertheless labels its horizontal axis qdq_{d}, so it is unclear whether the figure shows token-level or path-level calibration.
  • For each target model, a new corpus of 1B tokens must be generated by that model, which limits the generality of the method across target models. The paper states only that the counting step is cheap, and the cost of generating the corpus, which is likely substantial, is not reported.
  • Section 4.2 states that maximizing Eq. (3) amounts to selecting the top-B prefixes by log⁡p~⋆(u)=S(u)\log{\tilde{p}}^{\star }(u)=S(u). However, since pd⋆p_{d}^{\star } in Eq. (6) is normalized by Zd(cd)Z_{d}(c_{d}) (Appendix C), which depends on the prefix, log⁡p~⋆(u)=S(u)−∑d≤∣u∣log⁡Zd(cd)\log{\tilde{p}}^{\star }(u)=S(u)-\sum_{d\leq |u|}\log Z_{d}(c_{d}). Hence, ranking by S does not in general maximize Eq. (3).
Questions for authors
  • The paper cites DDTree, DiffuSpec, and DART, which also apply tree drafting to diffusion drafters, identify the same mismatch, or score draft paths with n-gram models. Please clarify in the main text how this work differs from these methods, and state its novel contributions explicitly.
  • Please compare PRESTO with naive tree drafting baselines that are identical to PRESTO except for the prefix-dependent correction (i.e., λd=0{\lambda }_{d}=0 with the same expansion policy and node budget) in terms of τ\tau and speedup for all settings in Tables 2–4.
  • Please make the horizontal axis label of Figure 2(b) consistent with the path-level confidence described in Observation 2.
  • What is the computational cost (e.g., GPU hours) of generating the 1B-token corpus for each target model? Can an n-gram model built for one target (e.g., Qwen3-4B) be reused for another target with the same tokenizer (e.g., Qwen3-8B)?
  • Please provide a proof of the equality log⁡p~⋆(u)=S(u)\log{\tilde{p}}^{\star }(u)=S(u) in Section 4.2, or revise the statement.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.