Goose: Anisotropic Speculation Trees for Training-Free Speculative Decoding

• URL: http://arxiv.org/abs/2604.02047v1
• Date: Thu, 02 Apr 2026 13:48:42 GMT
• Title: Goose: Anisotropic Speculation Trees for Training-Free Speculative Decoding
• Abstract summary: Speculative decoding accelerates large language model inference by drafting multiple candidate tokens and verifying them in a single forward pass.<n>Existing training-free methods draft from a single token source and shape their trees without distinguishing candidate quality across origins.<n>We observe that two common training-free token sources - n-gram matches copied from the input context, and statistical predictions from prior forward passes - differ dramatically in acceptance rate.<n>We prove that the number of tokens accepted per step is at least as large as that of either source used alone.
• Score: 13.709230136542594
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Speculative decoding accelerates large language model inference by drafting multiple candidate tokens and verifying them in a single forward pass. Candidates are organized as a tree: deeper trees accept more tokens per step, but adding depth requires sacrificing breadth (fallback options) under a fixed verification budget. Existing training-free methods draft from a single token source and shape their trees without distinguishing candidate quality across origins. We observe that two common training-free token sources - n-gram matches copied from the input context, and statistical predictions from prior forward passes - differ dramatically in acceptance rate (~6x median gap, range 2-18x across five models and five benchmarks). We prove that when such a quality gap exists, the optimal tree is anisotropic (asymmetric): reliable tokens should form a deep chain while unreliable tokens spread as wide branches, breaking through the depth limit of balanced trees. We realize this structure in GOOSE, a training-free framework that builds an adaptive spine tree - a deep chain of high-acceptance context-matched tokens with wide branches of low-acceptance alternatives at each node. We prove that the number of tokens accepted per step is at least as large as that of either source used alone. On five LLMs (7B-33B) and five benchmarks, GOOSE achieves 1.9-4.3x lossless speedup, outperforming balanced-tree baselines by 12-33% under the same budget.

Related papers

• DARTree: Speculative Diffusion Decoding with Autoregressive Draft Trees [40.61855455828842]
  Speculative decoding losslessly accelerates autoregressive language models by verifying multiple draft tokens in parallel.<n>Dartree is a training-free speculative decoding method that extends a pretrained AR correction head from chains to trees.
  arXiv  Detail & Related papers  (2026-08-13T17:43:44Z)
• 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)
• 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)
• Entropy-Tree: Tree-Based Decoding with Entropy-Guided Exploration [52.52685988964061]
  Entropy-Tree is a tree-based decoding method that exploits entropy as a signal for branching decisions.<n>It unifies efficient structured exploration and reliable uncertainty estimation within a single decoding procedure.
  arXiv  Detail & Related papers  (2026-01-02T07:14:05Z)
• 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)
• Traversal Verification for Speculative Tree Decoding [15.720388162422978]
  Speculative decoding is a promising approach for accelerating large language models.<n>This paper introduces Traversal Verification, a novel speculative decoding algorithm.<n>We show that our method consistently improves acceptance length and throughput over existing methods.
  arXiv  Detail & Related papers  (2025-05-18T12:51:55Z)
• C2T: A Classifier-Based Tree Construction Method in Speculative Decoding [9.663330370149428]
  Speculative decoding methods often face inefficiencies in the construction of token trees and the verification of candidate tokens.<n>We propose a novel method named C2T that adopts a lightweight classifier to generate and prune token trees dynamically.
  arXiv  Detail & Related papers  (2025-02-19T11:57:02Z)
• OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure [40.9990864658776]
  Speculative decoding employs a "draft and then verify" mechanism to allow multiple tokens to be generated in one step.<n>Existing methods mainly adopt fixed draft structures, which fail to adapt to different situations.<n>We propose OPT-Tree, an algorithm to construct adaptive and scalable draft trees.
  arXiv  Detail & Related papers  (2024-06-25T04:45:53Z)
• Tree Cross Attention [59.8891512435847]
  Tree Cross Attention (TCA) is a module based on Cross Attention that only retrieves information from a logarithmic $mathcalO(log(N))$ number of tokens for performing inference. We show that TCA performs comparable to Cross Attention across various classification and uncertainty regression tasks while being significantly more token-efficient.
  arXiv  Detail & Related papers  (2023-09-29T16:50:23Z)
• An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
  adversarial attacks on tree based ensembles such as gradient boosting decision trees (DTs) and random forests (RFs) We show that our method can be thousands of times faster than the previous mixed-integer linear programming (MILP) based approach. Our code is available at https://chong-z/tree-ensemble-attack.
  arXiv  Detail & Related papers  (2020-10-22T10:59:49Z)
• On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
  We develop an efficient programming based algorithm for sound verification of ensemble stumps. We demonstrate the first certified defense method for training ensemble stumps and trees with respect to $ell_p$ norm perturbations.
  arXiv  Detail & Related papers  (2020-08-20T03:42:40Z)

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.