Dynamic Tree Topology for Speculative Decoding

48 concepts34 papers1 proposal

Speculative decoding has emerged as a core strategy for accelerating Large Language Model (LLM) inference. The standard recipe relies on a small, fast "draft" model to generate a sequence of candidate tokens, which a large "target" model verifies in parallel. If the target model accepts the draft, the system generates multiple tokens for the computational cost of a single forward pass.

However, traditional speculative decoding suffers from a structural rigidity: it relies on fixed-length chains or static tree structures to propose candidates. This article explores the shift toward dynamic tree topology, where the shape, depth, and width of the speculative token tree are reshaped in real time based on the model's confidence and context.

The Inefficiency of Static Speculation

To understand why dynamic trees work, we must first look at why static structures fail. In any text generation task, the predictability of the next token varies wildly depending on the context.

Consider two scenarios:

  1. High Certainty: The model is completing a common idiom, such as "The capital of France is..." The next token ("Paris") is nearly guaranteed.
  2. High Uncertainty: The model is generating a complex reasoning path or a creative story where multiple grammatically and semantically valid choices exist.

As noted by Tianhao Wu et al. in DySpec: Faster speculative decoding with dynamic token tree structure, fixed-structure approaches fail to adapt to these varying confidence levels. If a system uses a rigid, narrow chain, it wastes an opportunity to guess much further ahead during high-certainty phases. Conversely, during uncertain phases, a static tree will waste computational resources exploring deep, improbable token paths that the target model will ultimately reject, as argued by Yuhui Li et al. in EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees.

The Core Intuition: Confidence Maps to Acceptance

The foundational insight behind dynamic tree adaptation is that a draft model’s output probability is highly correlated with its actual acceptance rate by the target model.

Cunxiao Du et al. demonstrate this relationship in GliDe with a CaPE: A Low-Hassle Method to Accelerate Speculative Decoding. Because the draft model's confidence serves as a reliable proxy for verification success, the system can use real-time token probabilities to dynamically allocate its computational budget between depth (exploitation) and width (exploration).

Low Confidence (High Entropy)        High Confidence (Low Entropy)
       Branching Tree                       Deep Linear Chain
            [Token]                             [Token]
           /       \                               |
     [Draft A]   [Draft B]                      [Draft 1]
       /   \       /   \                           |
     [...] [...] [...] [...]                    [Draft 2]
                                                   |
                                                [Draft 3]

Instead of forcing the draft model into a one-size-fits-all topology, dynamic tree decoding continuously reshapes the proposal structure at each generation step:

  • When confidence is high, the tree grows deeper. The system builds long, linear token chains, maximizing the number of tokens verified in a single step because the path is highly predictable.
  • When confidence drops, the tree grows wider. Rather than guessing blindly down a single path, the draft model forks, proposing multiple high-probability alternative candidates for the same token position. This creates a branching structure that presents the target model with a portfolio of options to verify in parallel.

Mechanisms of Real-Time Tree Adaptation

Several algorithmic frameworks have been developed to manage this real-time reshaping without introducing significant computational overhead.

Confidence-Aware Expansion and Pruning

One direct approach is to trigger branching or pruning based on explicit probability thresholds. In GliDe with a CaPE, Cunxiao Du et al. introduce Confidence-Aware Proposal Expansion (CAPE), which selects multiple candidates for a single position only when the top token's probability falls below a certain threshold.

To prevent the tree from growing exponentially, low-confidence branches must be pruned on the fly. Fangcheng Liu et al. implement this in Kangaroo: Lossless Self-Speculative Decoding for Accelerating LLMs via Double Early Exiting, halting the drafting process entirely when the cumulative confidence of the sequence drops too low, ensuring that the target model's parallel verification capacity is reserved only for high-quality candidates.

Mathematical Optimization of Tree Shape

Rather than relying purely on heuristics, some frameworks treat tree construction as a formal optimization problem.

In OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure, Jikai Wang et al. propose a greedy search algorithm designed to maximize the mathematical expectation of the accepted sequence length at each inference step. By evaluating the joint probabilities of candidate sequences, the system constructs a tree topology that offers the highest statistical payoff.

Taking this further, Avner May introduces Sequoia: Scalable and Robust Speculative Decoding, which uses dynamic programming to find the provably optimal token tree structure for a given hardware computational budget.

Multi-Armed Bandit Control

Another perspective treats the speculation length as a sequential decision-making problem under uncertainty. Jiahao Liu et al. develop a Thompson Sampling control mechanism in Speculative Decoding via Early-exiting for Faster LLM Inference with Thompson Sampling Control Mechanism. By modeling the drafting process as a multi-armed bandit, the system dynamically adjusts the speculation depth based on the historical acceptance rates of recent tokens, automatically scaling down when text complexity rises.

Generalizing Beyond Autoregressive Models

The intuition that decoding structures should dynamically adapt to model confidence is not restricted to standard autoregressive draft-verify pairs. It has successfully generalized to other modalities and architectures.

Vision-Language Models

In multimodal settings, the density of information varies between processing visual tokens and generating textual responses. Mingxiao Huo et al. adapt dynamic tree structures to vision-language models in Spec-LLaVA: Accelerating Vision-Language Models with Dynamic Tree-Based Speculative Decoding, demonstrating that adjusting search breadth and depth based on visual-textual context alignment yields substantial throughput improvements without quality degradation.

Diffusion Large Language Models (dLLMs)

Diffusion-based language models generate text by iteratively unmasking or refining blocks of tokens in parallel. Traditional dLLMs use rigid, fixed-size decoding windows, which suffer from premature commitment to low-confidence tokens.

To resolve this, Guanxi Lu et al. introduce AdaBlock-dLLM: Semantic-Aware Diffusion LLM Inference via Adaptive Block Size, a mechanism that dynamically adjusts decoding block boundaries based on the model's prediction confidence across the sequence.

Similarly, the authors of Wide-In, Narrow-Out: Revokable Decoding for Efficient and Effective DLLMs utilize a confidence-based verification loop where the model aggressively drafts wide token blocks and uses bidirectional context to revoke and re-mask errors. This allows the system to naturally scale its computational effort to the inherent difficulty of the text, achieving massive speedups while maintaining logical consistency.

Key Foundational Work

EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees (2024) — contributed 4 concept elements to this direction.
DySpec: Faster speculative decoding with dynamic token tree structure (2025) — contributed 3 concept elements to this direction.
OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure (2024) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dynamic_tree_adaptation_c98d8c1d,
  title = {dynamic tree adaptation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-tree-adaptation/rdr_c98d8c1d6c724419929fdc6f0b101fc3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_dynamic_tree_adaptation_c98d8c1d_v1,
  title = {dynamic tree adaptation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-tree-adaptation/rdr_c98d8c1d6c724419929fdc6f0b101fc3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake