Bole: Efficient Tree Speculation for Hybrid-Attention Language Models

Research Context and Motivation

Hybrid-attention large language models (LLMs) improve inference efficiency by interleaving full-attention layers with recurrent linear-attention layers. While this reduces the memory footprint compared to pure full-attention models, autoregressive decoding remains a bottleneck. Tree speculative decoding—a technique where a drafter proposes multiple candidate tokens and the target model verifies them in parallel—is a proven accelerator for full-attention models. However, existing tree-speculation systems fail to support hybrid models because they are built around the append-only key-value (KV) caches of full-attention architectures, leading to inefficient state management and high verification latency when applied to recurrent linear-attention layers.

The Bole Approach

Bole introduces a kernel-runtime co-design to address these limitations through three primary mechanisms:

1. Parallel Tree Solver: Bole derives a tree-structured closed form for linear-attention recurrence, allowing the system to verify all proposal nodes in parallel rather than traversing branches sequentially. This is implemented via a resource-efficient GPU kernel.
2. Factorized State Lifecycle: Instead of materializing full recurrent states for every proposal node, Bole encodes state updates as token-level factors. It reconstructs only the state of the accepted path after sampling, which reduces transient memory consumption by 82–99%.
3. Hardware-Aware Verification Budget: The system profiles the target model's efficient verification capacity on specific hardware and dynamically allocates this budget across request trees, ensuring optimal performance without exceeding compute-bound thresholds.

Impact and Performance

Integrated into the SGLang serving engine, Bole significantly improves throughput and latency across diverse models and GPU platforms. It achieves up to 4.72x the offline decode throughput of standard autoregressive decoding and up to 2.03x the throughput of the strongest tree-speculative baseline. In online agent workloads, Bole reduces Time to First Token (TTFT) by up to 67.6% and Time Per Output Token (TPOT) by up to 49.9%.