# STree: Speculative Tree Decoding for Hybrid State-Space Models

arXiv: https://arxiv.org/abs/2505.14969 · HTML: https://mlsanity.com/paper/2505.14969/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving.
- Builds on 19 of its 29 references that are in the map.
- First posted on arXiv 20 May 2025.

## Placed in

- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 19 of 19)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality](https://mlsanity.com/paper/2405.21060/) (2024)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [Jamba: A Hybrid Transformer-Mamba Language Model](https://mlsanity.com/paper/2403.19887/) (2024)
- [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024)
- [Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models](https://mlsanity.com/paper/2402.19427/) (2024)
- [Zamba: A Compact 7B SSM Hybrid Model](https://mlsanity.com/paper/2405.16712/) (2024)
- [The Mamba in the Llama: Distilling and Accelerating Hybrid Models](https://mlsanity.com/paper/2408.15237/) (2024)
- [Judge Decoding: Faster Speculative Sampling Requires Going Beyond Model Alignment](https://mlsanity.com/paper/2501.19309/) (2025)
- [SpecExec: Massively Parallel Speculative Decoding for Interactive LLM Inference on Consumer Devices](https://mlsanity.com/paper/2406.02532/) (2024)
- [Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement](https://mlsanity.com/paper/2402.14160/) (2024)
- [B'MOJO: Hybrid State Space Realizations of Foundation Models with Eidetic and Fading Memory](https://mlsanity.com/paper/2407.06324/) (2024)
- [Optimized Multi-Token Joint Decoding with Auxiliary Model for LLM Inference](https://mlsanity.com/paper/2407.09722/) (2024)
- [Stacked Residuals of Dynamic Layers for Time Series Anomaly Detection](https://mlsanity.com/paper/2202.12457/) (2022)

## Built on by (most cited first, 10 of 10)

- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [Make Every Draft Count: Hidden State based Speculative Decoding](https://mlsanity.com/paper/2602.21224/) (2026)
- [SpecLA: Efficient Speculative Decoding for Linear-Attention Models](https://mlsanity.com/paper/2607.16673/) (2026)
- [KVBuffer: IO-aware Serving for Linear Attention](https://mlsanity.com/paper/2605.19049/) (2026)
- [Trees from Marginals: Autoregressive drafting with factorized priors](https://mlsanity.com/paper/2607.06763/) (2026)
- [Bole: Efficient Tree Speculation for Hybrid-Attention Language Models](https://mlsanity.com/paper/2608.01651/) (2026)
- [Bastion: Budget-Aware Speculative Decoding with Tree-structured Block Diffusion Drafting](https://mlsanity.com/paper/2605.29727/) (2026)
- [ReplaySSM: Cache SSM Inputs, Not State](https://mlsanity.com/paper/2610.13778/) (2026)
- [Component-Aware Self-Speculative Decoding in Hybrid Language Models](https://mlsanity.com/paper/2605.01106/) (2026)
- [LumoTree: Path-Parallel Speculative Verification for Hybrid Language Models](https://mlsanity.com/paper/2609.23900/) (2026)

## Abstract (arXiv)

Speculative decoding is a technique to leverage hardware concurrency in order to enable multiple steps of token generation in a single forward pass, thus improving the efficiency of large-scale autoregressive (AR) Transformer models. State-space models (SSMs) are already more efficient than AR Transformers, since their state summarizes all past data with no need to cache or re-process tokens in the sliding window context. However, their state can also comprise thousands of tokens; so, speculative decoding has recently been extended to SSMs. Existing approaches, however, do not leverage the tree-based verification methods, since current SSMs lack the means to compute a token tree efficiently. We propose the first scalable algorithm to perform tree-based speculative decoding in state-space models (SSMs) and hybrid architectures of SSMs and Transformer layers. We exploit the structure of accumulated state transition matrices to facilitate tree-based speculative decoding with minimal overhead relative to current SSM implementations. Along with the algorithm, we describe a hardware-aware implementation that improves naive application of AR Transformer tree-based speculative decoding methods to SSMs. Furthermore, we outperform vanilla speculative decoding with SSMs even with a baseline drafting model and tree structure on three different benchmarks, opening up opportunities for further speed up with SSM and hybrid model inference. Code can be found at: https://github.com/wyc1997/stree.