# Bole: Efficient Tree Speculation for Hybrid-Attention Language Models

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

## Key facts

- Cited by 3 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 35 of its 54 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Placed in

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

## Builds on (most cited first, 30 of 35)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Get To The Point: Summarization with Pointer-Generator Networks](https://mlsanity.com/paper/1704.04368/) (2017)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [OpenHands: An Open Platform for AI Software Developers as Generalist Agents](https://mlsanity.com/paper/2407.16741/) (2024)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://mlsanity.com/paper/2104.04473/) (2021)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [Better & Faster Large Language Models via Multi-token Prediction](https://mlsanity.com/paper/2404.19737/) (2024)
- [EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test](https://mlsanity.com/paper/2503.01840/) (2025)
- [Atom: Low-bit Quantization for Efficient and Accurate LLM Serving](https://mlsanity.com/paper/2310.19102/) (2023)
- [FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving](https://mlsanity.com/paper/2501.01005/) (2025)
- [Kimi Linear: An Expressive, Efficient Attention Architecture](https://mlsanity.com/paper/2510.26692/) (2025)
- [Llumnix: Dynamic Scheduling for Large Language Model Serving](https://mlsanity.com/paper/2406.03243/) (2024)
- [Sequoia: Scalable, Robust, and Hardware-aware Speculative Decoding](https://mlsanity.com/paper/2402.12374/) (2024)
- [NanoFlow: Towards Optimal Large Language Model Serving Throughput](https://mlsanity.com/paper/2408.12757/) (2024)
- [POD-Attention: Unlocking Full Prefill-Decode Overlap for Faster LLM Inference](https://mlsanity.com/paper/2410.18038/) (2024)
- [Marconi: Prefix Caching for the Era of Hybrid LLMs](https://mlsanity.com/paper/2411.19379/) (2024)
- [Strata: Hierarchical Context Caching for Long Context Language Model Serving](https://mlsanity.com/paper/2508.18572/) (2025)
- [PAPI: Exploiting Dynamic Parallelism in Large Language Model Decoding with a Processing-In-Memory-Enabled Computing System](https://mlsanity.com/paper/2502.15470/) (2025)
- [DeFT: Decoding with Flash Tree-attention for Efficient Tree-structured LLM Inference](https://mlsanity.com/paper/2404.00242/) (2024)
- [Speculative Decoding: Performance or Illusion?](https://mlsanity.com/paper/2601.11580/) (2025)
- [STree: Speculative Tree Decoding for Hybrid State-Space Models](https://mlsanity.com/paper/2505.14969/) (2025)

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

- [TreeWY: Speculative Verification for Gated DeltaNet Hybrids](https://mlsanity.com/paper/2608.20961/) (2026)
- [LumoTree: Path-Parallel Speculative Verification for Hybrid Language Models](https://mlsanity.com/paper/2609.23900/) (2026)
- [UBTree: Parallel Tree Drafting via Unigram and Bigram Models for Speculative Decoding](https://mlsanity.com/paper/2609.39972/) (2026)

## Abstract (arXiv)

Hybrid-attention large language models combine full attention with recurrent linear attention to reduce long-context inference costs, yet their autoregressive decoding remains memory-bound. Tree speculative decoding offers an attractive acceleration path, but existing tree-speculation systems are designed around the key--value caches of full-attention models. On hybrid models, they traverse recurrent layers branch by branch and materialize a full state for every proposal node, causing verification latency and transient memory to scale poorly with tree and batch sizes. We present Bole, a kernel--runtime co-design that enables efficient tree speculation for hybrid-attention LLMs. Bole transforms the linear-attention recurrence into a tree-structured closed form and realizes it with a resource-efficient GPU kernel, verifying all proposal nodes in parallel and accelerating linear-attention tree verification by 3.4--7.7×. It losslessly encodes speculative state updates as token-level factors and reconstructs only the state selected after sampling, reducing transient state memory by 82--99× and freeing GPU capacity for KV caches. Its integration into SGLang, a widely deployed production LLM serving engine, couples efficient state management with a batch-wide verification budget calibrated to the complete hybrid forward. Across four models, two GPU platforms, and diverse datasets, Bole delivers up to 4.72× the offline decode throughput of autoregressive decoding and up to 2.03× that of the strongest tree-speculative baseline. Under online agent workloads, it reduces TTFT and TPOT by up to 67.6% and 49.9%, respectively, over the strongest tree-speculative baseline.