Bastion: Budget-Aware Speculative Decoding with Tree-structured Block Diffusion Drafting

• URL: http://arxiv.org/abs/2605.29727v1
• Date: Thu, 28 May 2026 10:21:34 GMT
• Title: Bastion: Budget-Aware Speculative Decoding with Tree-structured Block Diffusion Drafting
• Abstract summary: BASTION is a budget-aware speculative decoding framework with tree-based diffusion drafting.<n>Our framework integrates three synergistic components: (1) an acceptance surrogate that estimates expected accepted length via path confidence, (2) an online latency estimator that calibrates a hardware-aware roofline model, and (3) an adaptive best-first expansion that grows the tree until marginal gains no longer justify incremental verification costs.
• Score: 36.83545196908392
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Block-diffusion drafters have recently emerged as a powerful alternative for speculative decoding by predicting multiple future-token distributions in a single parallel step. However, since these parallel predictions are sampled from position-wise marginals rather than fully conditioned sequences, committing to a single greedy path often fails to capture the target model's preferred trajectory. To address this, we propose BASTION, a budget-aware speculative decoding framework with tree-based diffusion drafting. Unlike existing methods that rely on static tree topologies, BASTION dynamically constructs query-dependent trees by balancing draft quality against hardware constraints. Our framework integrates three synergistic components: (1) an acceptance surrogate that estimates expected accepted length via path confidence, (2) an online latency estimator that calibrates a hardware-aware roofline model, and (3) an adaptive best-first expansion that grows the tree until marginal gains no longer justify incremental verification costs. BASTION is training-free, preserves the target model's distribution, and requires no per-setting tuning. Across diverse benchmarks and GPU architectures, BASTION achieves up to a 6.61x speedup over standard autoregressive decoding, outperforming state-of-the-art block-diffusion baselines by 39%.

Related papers

• DBLAST: Dependent Block Drafting for Stochastic Speculative Decoding [26.72775347772003]
  We show that the accepted draft length degrades as the entropy of the target sampling distribution increases.<n>We propose a dependent block drafter based on a low-rank latent mixture over token positions, complemented by an acceptance-oriented training objective.
  arXiv  Detail & Related papers  (2026-08-05T22:49:54Z)
• Trees from Marginals: Autoregressive drafting with factorized priors [0.0]
  Speculative decoding greatly increases the interactivity of autoregressive language models.<n>We introduce Weaver, a lightweight autoregressive adapter that constructs proposal trees from the top-K marginals of a factorized drafter.
  arXiv  Detail & Related papers  (2026-07-07T19:48:36Z)
• PRESTO: Prefix-Aligned Tree Drafting for Diffusion Speculative Decoding [98.71600061506206]
  We propose PRESTO, a principled framework that extends tree-based drafting to diffusion drafters.<n> PRESTO achieves up to an average of $1.5times$ end-to-end throughput speedup on the state-of-the-art dedicated diffusion drafter SD.
  arXiv  Detail & Related papers  (2026-06-20T14:32:14Z)
• Teaching Diffusion to Speculate Left-to-Right [3.205247598097648]
  Large language models (LLMs) achieve remarkable performance across a wide range of tasks, but their autoregressive decoding process incurs substantial inference costs.<n> Speculative decoding addresses this bottleneck by employing a lightweight draft model to propose multiple future tokens that are subsequently verified in parallel by a larger target model.<n>Recent work has demonstrated that diffusion language models are well suited for this setting, as they can generate entire blocks of draft tokens in parallel.
  arXiv  Detail & Related papers  (2026-06-10T01:21:56Z)
• TreeFlash: Parallel AR-Approximation for Faster Speculative Decoding [32.75269650141292]
  One-shot block drafters for speculative decoding generate the full draft in a single forward pass.<n>They predict each draft token conditioned only on the prefix context, with no dependence on previously drafted tokens.<n>This non-autoregressive conditioning causes the drafter's distribution to diverge from the verifier's true autoregressive distribution as draft depth grows.<n>We propose TreeFlash, which addresses this by incorporating a layer conditioned on the drafter's hidden state and the previous token to approximate an autoregressive distribution.
  arXiv  Detail & Related papers  (2026-06-02T16:00:18Z)
• Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decoding [27.332123289262086]
  Graft is a compensation framework that couples pruning and retrieval as mutually reinforcing operations.<n>On short-context benchmarks, it achieves up to 5.41$times$ speedup and improves average speedup by up to 21.8% on the large-scale Qwen3-235B.<n>We also provide a preliminary exploration of applying Graft to the DFlash-style block drafting paradigm, offering initial evidence and insights for extending grafting beyond autoregressive draft trees.
  arXiv  Detail & Related papers  (2026-05-19T16:55:48Z)
• Accelerating Speculative Decoding with Block Diffusion Draft Trees [20.28933257827737]
  Speculative decoding accelerates autoregressive language models by using a lightweight drafter to propose multiple future tokens.<n>DFlash shows that a block diffusion drafter can generate an entire draft block in a single forward pass.<n> Vanilla DFlash verifies only a single drafted trajectory per round, potentially limiting its acceptance length.<n>We introduce DDTree, a method that constructs a draft tree directly from the per-position distributions of a block diffusion drafter.
  arXiv  Detail & Related papers  (2026-04-14T17:23:14Z)
• Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding [35.984745508100595]
  We present a systematic evaluation of verification strategies across model families, tasks, and sampling regimes.<n>Traversal Verification dominates consistently, with OT-based methods lagging far behind.<n>We propose delayed tree expansion, which drafts a partial single path, delaying the i.i.d. branching point.
  arXiv  Detail & Related papers  (2026-02-19T01:41:58Z)
• SAGE: Accelerating Vision-Language Models via Entropy-Guided Adaptive Speculative Decoding [15.734450444255787]
  Speculative decoding has emerged as a promising approach to accelerate inference in vision-language models.<n>Existing methods rely on static tree structures that remain fixed throughout the decoding process.<n>We propose SAGE, a novel framework that dynamically adjusts the speculation tree structure based on real-time prediction uncertainty.
  arXiv  Detail & Related papers  (2026-01-31T05:35:40Z)
• TALON: Confidence-Aware Speculative Decoding with Adaptive Token Trees [18.53532655905144]
  Speculative decoding (SD) has become a standard technique for accelerating LLM inference without sacrificing output quality.<n>We introduce TALON, a training-free, budget-driven adaptive tree expansion framework that can be plugged into existing tree-based methods.<n> TALON consistently outperforms state-of-the-art Eagle-3, achieving up to 5.16x end-to-end speedup over auto-regressive decoding.
  arXiv  Detail & Related papers  (2026-01-12T09:26:45Z)
• Fast Inference of Visual Autoregressive Model with Adjacency-Adaptive Dynamical Draft Trees [50.230925890958936]
  We propose an adjacency-adaptive dynamic draft tree that adjusts draft tree depth and width by leveraging adjacent token states and prior acceptance rates.<n>ADT-Tree achieves speedups of 3.13xand 3.05x, respectively, and integrates seamlessly with relaxed sampling methods such as LANTERN.
  arXiv  Detail & Related papers  (2025-12-26T04:45:49Z)
• Arbitrage: Efficient Reasoning via Advantage-Aware Speculation [71.45710345765528]
  Speculative Decoding accelerates inference by employing a fast but inaccurate draft model to autoregressively propose tokens.<n>But due to unnecessary rejections caused by token mismatches in semantically equivalent steps, traditional token-level Speculative Decoding struggles in reasoning tasks.<n>We propose Arbitrage, a novel step-level speculative generation framework that routes generation dynamically based on the relative advantage between draft and target models.
  arXiv  Detail & Related papers  (2025-12-04T17:50:53Z)
• Scaling LLM Speculative Decoding: Non-Autoregressive Forecasting in Large-Batch Scenarios [76.85739138203014]
  We present SpecFormer, a novel architecture that accelerates unidirectional and attention mechanisms.<n>We demonstrate that SpecFormer achieves lower training demands and reduced computational costs.
  arXiv  Detail & Related papers  (2025-11-25T14:20:08Z)
• DiffuSpec: Unlocking Diffusion Language Models for Speculative Decoding [66.40658898418316]
  We present DiffuSpec, a training-free drop-in framework that uses a pretrained diffusion language model (DLM) to produce multi-token drafts in a single forward pass.<n>Across benchmarks, DiffuSpec yields up to 3x wall-clock speedup, establishing diffusion-based drafting as a robust alternative to autoregressive drafters for speculative decoding.
  arXiv  Detail & Related papers  (2025-09-28T07:00:15Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  We improve the scalability of Branch and Bound (BaB) algorithms for formally proving input-output properties of neural networks. We present a novel activation-based branching strategy and a BaB framework, named Branch and Dual Network Bound (BaDNB) BaDNB outperforms previous complete verification systems by a large margin, cutting average verification times by factors up to 50 on adversarial properties.
  arXiv  Detail & Related papers  (2021-04-14T09:22:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.