Bole: Efficient Tree Speculation for Hybrid-Attention Language Models

• URL: http://arxiv.org/abs/2608.01651v1
• Date: Mon, 03 Aug 2026 03:43:14 GMT
• Title: Bole: Efficient Tree Speculation for Hybrid-Attention Language Models
• Abstract summary: Hybrid-attention large language models combine full attention with recurrent linear attention to reduce long-context inference costs.<n>Existing tree-speculation systems are designed around the key--value caches of full-attention models.<n>We present Bole, a kernel--runtime co-design that enables efficient tree speculation for hybrid-attention LLMs.
• Score: 14.999732832367307
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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$\times$. 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$\times$ 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\times$ the offline decode throughput of autoregressive decoding and up to $2.03\times$ 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.

Related papers

• HARTS: Efficient Agentic Reinforcement Learning for Hybrid-Attention Models over Arbitrary Rollout Trees [10.936836651826722]
  We present HARTS (Hybrid-Attention RL over Tree Structures)<n>HarTS is the first system to demonstrate arbitrary-rollout-tree prefix-sharing speedups on a real hybrid-attention model.
  arXiv  Detail & Related papers  (2026-08-28T10:18:54Z)
• TreeWY: Speculative Verification for Gated DeltaNet Hybrids [0.0]
  Modern open models are hybrids: layers are linear-attention (Gated DeltaNet, GDN) layers carrying a small fixed-size recurrent state instead of a growing key-value cache.<n>Today's systems snapshot the full recurrent state at every draft position for GDN layers, and those snapshots cannot be shared across branches of a draft tree.<n>We compute every draft node's output with a single triangular solve and reconstruct only the one accepted state on commit.
  arXiv  Detail & Related papers  (2026-08-21T10:31:15Z)
• 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)
• DSpark: Confidence-Scheduled Speculative Decoding with Semi-Autoregressive Generation [69.8840101036735]
  Speculative decoding accelerates Large Language Model (LLM) inference.<n>Recent parallel drafters efficiently propose long token sequences in a single forward pass, but suffer from rapid acceptance decay due to a lack of inter-token dependencies.<n>We introduce DSpark, a speculative decoding framework that unifies high- throughput parallel generation with adaptive, load-aware verification.
  arXiv  Detail & Related papers  (2026-07-06T14:28:06Z)
• Fractional Verkle Trees: A Hypertree Decomposition and Verified Proof Serialization Architecture for High-Performance Blockchain State Accumulators [0.0]
  We present Fractional Verkle Trees (FVT), a hypertree serialization decomposition global state into N independent sub-accumulators coordinated by a Merkle commitment tree.<n> Benchmarks on Apple M1 Pro show 57% heap allocation reduction (566,760 to 242,004 bytes per 10K$), parallel insertion at 2,433 ns/op, and network-wide elimination of 4.85 PB/year across 6,000 full nodes.
  arXiv  Detail & Related papers  (2026-06-15T07:16:07Z)
• GASim: A Graph-Accelerated Hybrid Framework for Social Simulation [56.12016729479412]
  GASim is a graph-accelerated hybrid multi-agent framework for large-scale social simulations.<n>For core agents driven by LLM, GASim introduces Graph-Jasmined Memory (GOM) to replace intensive LLM-based retrieval pipelines.<n>For the majority of ordinary agents, GASim employs Graph Message Passing (GMP), substituting sequential ABM execution with parallel updates.
  arXiv  Detail & Related papers  (2026-05-08T13:01:25Z)
• SMART: When is it Actually Worth Expanding a Speculative Tree? [26.986851887229054]
  Tree-based speculative decoding accelerates autoregressive generation by verifying a branching tree draft tokens in a single targetmodel forward pass.<n>Existing methods prioritize maximizing token-level likelihood of the number of accepted tokens while ignoring a critical efficiency paradox''<n>We propose SMART, a system-aware marginal analysis framework for runtime tree construction.
  arXiv  Detail & Related papers  (2026-04-09T13:17:56Z)
• Resource-Efficient Iterative LLM-Based NAS with Feedback Memory [49.44875022114861]
  Neural Architecture Search (NAS) automates network design, but conventional methods demand substantial computational resources.<n>We propose a closed-loop pipeline leveraging large language models (LLMs) to iteratively generate, evaluate, and refine convolutional neural network architectures.
  arXiv  Detail & Related papers  (2026-03-12T16:00:22Z)
• 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)
• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePO is a self-guided rollout algorithm that views sequence generation as a tree-structured searching process.<n>TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity.
  arXiv  Detail & Related papers  (2025-08-24T16:52:37Z)
• Hierarchical Quantized Diffusion Based Tree Generation Method for Hierarchical Representation and Lineage Analysis [49.00783841494125]
  HDTree captures tree relationships within a hierarchical latent space using a unified hierarchical codebook and quantized diffusion processes.<n> HDTree's effectiveness is demonstrated through comparisons on both general-purpose and single-cell datasets.<n>These contributions provide a new tool for hierarchical lineage analysis, enabling more accurate and efficient modeling of cellular differentiation paths.
  arXiv  Detail & Related papers  (2025-06-29T15:19:13Z)
• RETENTION: Resource-Efficient Tree-Based Ensemble Model Acceleration with Content-Addressable Memory [9.502789435634975]
  RETENTION is an end-to-end framework that significantly reduces CAM capacity requirement for tree-based model inference.<n>We present a tree mapping scheme that incorporates two innovative data placement strategies to alleviate the memory redundancy caused by the widespread use of don't care states in CAM.
  arXiv  Detail & Related papers  (2025-06-06T11:25:51Z)
• QuantSpec: Self-Speculative Decoding with Hierarchical Quantized KV Cache [67.84112700032007]
  Large Language Models (LLMs) are increasingly being deployed on edge devices for long-context settings.<n>In these scenarios, the Key-Value ( KV) cache is the primary bottleneck in terms of both GPU memory and latency.<n>We propose a novel self-speculative decoding framework, QuantSpec, where the draft model shares the architecture of the target model but employs a hierarchical 4-bit quantized KV cache and 4-bit quantized weights for acceleration.
  arXiv  Detail & Related papers  (2025-02-05T20:43:48Z)
• DeFT: Decoding with Flash Tree-attention for Efficient Tree-structured LLM Inference [22.684773338989007]
  Large language models (LLMs) are increasingly employed for complex tasks that process multiple generation calls in a tree structure with shared prefixes of tokens.<n>Existing inference systems for tree-based applications are inefficient due to improper partitioning of queries and KV cache during attention calculation.<n>We propose DeFT, a hardware-efficient attention algorithm with prefix-aware and load-balanced KV cache partitions.
  arXiv  Detail & Related papers  (2024-03-30T04:34:54Z)

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.