SSV: Sparse Speculative Verification for Efficient LLM Inference

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

SSV: Sparse Speculative Verification for Efficient LLM Inference

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

operatingsystems virtualization

operating systems, kernel, virtualization

arXiv:2605.19893v2 [cs.OS] 20 May 2026

SSV: Sparse Speculative Verification for Efficient LLM Inference Zhibin Wang

Ziyu Zhong

Nuo Shen

State Key Laboratory for Novel Software Technology Nanjing University Nanjing, China

Yuhang Zhou

Rong Gu

Sheng Zhong

State Key Laboratory for Novel Software Technology Nanjing University Nanjing, China

Abstract

Typically, for Llama-3.1-8B-Instruct [14, 24] with a 64K context on an NVIDIA H100 PCIe GPU [27], the attention computation accounts for 97.20% of each decoding step. To relieve the pressure of KV-cache access, two complementary optimizations have emerged: speculative decoding [7, 20] mitigates the bandwidth bottleneck by increasing arithmetic intensity, while sparse attention [15] directly reduces the volume of accessed KV cache. Speculative decoding shifts the target model’s execution toward the compute-bound by enlarging the effective query batch size. Instead of invoking the target model for each newly generated token, a lightweight draft model proposes candidate continuations, and the target model verifies multiple candidates in parallel. In dense verification, these verifier queries access the same committed-prefix KV cache simultaneously, amortizing the expensive KV-cache loads across multiple candidates. Many frameworks further organize candidates into draft trees [6, 21, 22, 25] to improve the acceptance rate. However, tree-structured verification introduces complex tree masks and speculative path dependencies. As the context size increases, these irregularities may also increase the access cost of KV cache. Sparse attention takes another approach of shrinking the per-query KV working set. Instead of performing attention over the full KV history, dynamically selected sparse attention [11, 13, 15, 23, 33] routes each query to a subset of relevant context blocks, reducing both computation and KVcache access in long-context decoding. Taking the Native Sparse Attention (NSA) [33] as an example, it combines blocklevel dynamic selection, compressed long-range context, and dense local windows with hardware-friendly sparse execution. Specifically, NSA first compresses the KV cache into blocks and selects the Top-𝑛 relevant blocks for each query, while also preserving a sliding window of recent tokens. These branches are fused with learned gates to preserve complementary context while reducing KV access.

Speculative decoding and dynamic sparse attention are two complementary approaches for accelerating long-context LLM inference: the former amortizes target-model execution across multiple verifier queries, while the latter reduces each query’s KV-cache working set. Directly combining them, however, exposes a structural mismatch: speculative verification relies on cross-query commonality, whereas dynamic sparse attention assigns query-specific sparse layouts. This mismatch limits KV-block reuse, amplifies NSA’s branchwise overheads, and makes verification strategy selection input- and regime-dependent. We present SSV, a sparse speculative-verification framework that turns dynamic sparse attention into a verification-oriented workload. SSV combines overlap-aware grouped-query execution, refresh/reusebased NSA kernel fusion, and profile-guided prompt-adaptive orchestration to improve cross-query reuse, reduce selectedindex and branch-fusion overheads, and select effective draftverification strategies under user-specified precision classes. Experiments on NVIDIA H100 GPUs show that SSV achieves up to 3.49× end-to-end throughput over autoregressive NSA decoding and up to 6.86× kernel speedups for sparse speculative verification. Keywords: speculative decoding, sparse attention, large language model inference, kernel optimization, long-context inference

Introduction

Attention [30] is the core mechanism of large language models (LLMs) that enables them to capture long-range dependencies in text. During autoregressive decoding, generating each new token requires loading the entire accumulated keyvalue (KV) cache from memory to compute attention, which results in a heavy memory bandwidth cost, especially as the increasingly demanding of long-context applications [10, 17]. 1

Wang et al.

Intuitively, the two directions are naturally complementary, but their direct integration exposes a fundamental mismatch: The per-query selectivity of dynamic sparse attention conflicts with the cross-query commonality of speculative verification. This mismatch creates three practical challenges: (1) Crossquery reuse is hidden behind query-specific routing. We observe that nearby verifier queries often select overlapping KV blocks, but decoding-oriented sparse kernels process each query independently and reload these blocks, while prefill-oriented kernels may fetch blocks unused by any verifier query. A practical verifier must exploit this overlap without losing the option to preserve exact per-query selected-block semantics. (2) NSA’s branch structure fragments short verifier work. The compression, selection, and sliding-window branches are normally orchestrated through separate paths [33]. During verification, the query batch is larger than single-token decoding but still too small to amortize repeated kernel launches and intermediate materialization. (3) The best verification strategy is input-dependent. Sparse verification changes how draft length, tree traversal, selected-block overlap, and refresh/reuse scheduling interact. As a result, a fixed speculative-decoding configuration can be suboptimal when acceptance behavior or sparse-kernel performance shifts across prompts and context-length regimes. To address these challenges, we present SSV, a sparse speculative-verification framework that integrates dynamic sparse attention into speculative decoding with three key mechanisms: First, SSV introduces an overlap-aware kernel design (Section 4) that flattens draft trees with selected traversal orders and groups up to 𝐶 adjacent verifier queries in one thread block. Each group can use an exact merged schedule that deduplicates overlapping selected blocks while preserving per-query NSA semantics, or an approximate shared-index layout that reuses one representative query’s sparse layout for higher KV reuse. Second, SSV redesigns NSA kernel fusion around refresh and reuse layers (Section 5). Refresh layers recompute selected indices and partially fuse the downstream selection and sliding-window branches, reducing branch-output materialization. Reuse layers inherit the nearest refresh indices, skip repeated index construction, and run a fully fused NSA path without intermediate branch writes. Third, SSV uses profile-guided prompt-adaptive orchestration (Section 6) to search complete strategy tuples covering draft-tree shape, traversal order, coarsening mode and factor, and refresh/reuse schedule. The planner ranks candidates offline for each context regime and precision class, then uses accepted-token observations to refine the selected strategy when runtime behavior deviates from the offline profile for that prompt. In addition, SSV allows users to specify precision classes that trade off acceptance rate and speed,

supporting strict accuracy-preserving execution and faster controlled-approximation modes, while optimizing verification for the chosen setting. In this paper, we make the following contributions: • We propose SSV, a sparse speculative-verification framework that applies speculative decoding to dynamic sparse attention. SSV adapts draft-tree verification to NSA-style sparse attention while preserving sparse-layout semantics and speculative accept/reject behavior. • We introduce three optimizations that make sparse speculative verification efficient: overlap-aware kernel design for cross-query KV reuse, refresh/reuse-based NSA kernel fusion to reduce branch fragmentation and indexconstruction overhead, and profile-guided prompt-adaptive orchestration for complete strategy selection. • We evaluate SSV on NVIDIA H100 GPUs across isolated kernels, target verification, EAGLE-3 integration, and profileguided planning, showing up to 6.86× kernel speedup, 1.45× verification-stage speedup, 3.49× end-to-end throughput speedup, and 33.2% higher accepted-token throughput from planning.

Background

2.1

Speculative Decoding

Speculative Decoding (SD) [7, 20] accelerates LLM inference via a "draft-and-verify" workflow (Figure 1(a)). A lightweight draft model first proposes multiple candidate tokens, which are then verified concurrently by a larger target model. By verifying multiple candidate positions in a single forward pass, these queries share the prefix and access the same KV cache during attention. This amortizes memory access and execution overhead across candidate tokens, thereby increasing the effective query batch size and GPU utilization. Recent research has further improved the acceptance rate by organizing candidates into trees [6, 21, 22, 25]. By allowing the draft model to expand multiple branches into a candidate tree, the target model can evaluate multiple potential paths concurrently, resulting in a higher acceptance rate but more complex verification. Specifically, tree-based speculation requires complex tree masks to track dependencies between draft tokens, which complicates attention execution. In addition, tree-based speculation increases the number of draft tokens per step, which requires more efficient kernel design to maintain the amortization benefits. 2.2

Sparse Attention

In long-context decoding, dense attention cost scales linearly with the KV-cache length. Sparse attention reduces this cost by restricting computation to a smaller working set of context tokens or blocks. Early methods rely on static patterns, such as sliding windows or predefined strided connections (e.g., Longformer [4], BigBird [34]). However, static 2

SSV : Sparse Speculative Verification for Efficient LLM Inference

(a) Speculative Decoding

(b) Native Sparse Attention

Figure 1. Background and mismatch when combining speculative decoding with sparse attention. patterns struggle to capture the complex semantic relationships; dynamic methods (e.g., Top-𝑘 attention [15]) have become the preferred standard. Recent systems often employ structured, hardware-aligned blockwise sparsity to better align KV-cache access with GPU execution [13, 33]. Among them, Native Sparse Attention (NSA) [33] is a representative, and also the main focus of this paper. As illustrated in Figure 1(b), NSA [33] reduces KV access by fusing three complementary branches via learned gates: (1) Compression branch: Aggregates historical tokens into compressed blocks (length 𝑙, stride 𝑑) to capture broad context. (2) Selection branch: Uses compressed representations to route queries to the Top-𝑛 relevant raw KV blocks (size 𝑙 ′ ). For a query 𝑞𝑡 at layer 𝑗, we denote these selected block indices as 𝐼𝑡( 𝑗 ) . (3) Sliding-window branch: Retains dense access to the most recent 𝑤 tokens to preserve local semantics. By operating at block granularity, the compression and selection branches ensure hardware-friendly, contiguous KV-cache access.

each query. Intuitively, integrating them can provide a compounding acceleration for long-context inference. However, their direct combination exposes a structural mismatch: Speculative decoding depends on cross-query regularity, whereas dynamic sparse attention introduces queryspecific sparse layouts. This structural mismatch arises because the two techniques extract efficiency from different forms of structure. Dense speculative verification benefits when many verifier queries remain aligned: they share the committed prefix, traverse the same KV-cache region, and therefore amortize target-model execution and KV-cache loads across the batch. Dynamic sparse attention, in contrast, derives efficiency from differentiating queries: each query independently selects a subset of relevant KV blocks, so its execution path is determined by its own routing result rather than by the batch-wide shared prefix. In summary, combining them faces following challenges:

Beyond NSA. Although SSV utilizes NSA as its concrete backend, the architectural insights extend to other dynamic sparse-attention frameworks that decouple routing from execution. Extending to methods like DeepSeek Sparse Attention (DSA) [23] is theoretically feasible but strictly conditioned. Specifically, transferring our approach requires: (1) explicitly exposed routing metadata, (2) the capability for query-level selection, and (3) sufficient cross-query index overlap. In the absence of these precise conditions, a backend-specific redesign is mandatory.

Speculative Decoding Meets Sparse Attention

Heavy redundant access. As shown in Figure 1(c), existing sparse-attention kernels can be classified into two categories: 1) Decoding-oriented kernels [11, 13, 19, 23, 32, 33] that execute one query as well as load the corresponding KV blocks, and 2) Prefilling-oriented kernels [11, 13, 23, 33] that load the entire KV cache and for each token’s KV, the query selecting the corresponding token are combined into one thread block. However, both categories fail to support the verification workload: employing decoding-oriented kernels leads to duplicated KV-block loads across queries, while prefillingoriented kernels may load many KV blocks that are irrelevant to any query.

The preceding text shows that SD and NSA optimize orthogonal dimensions of the attention bottleneck: SD amortizes target execution and dense KV-cache access across verifier queries, whereas NSA reduces the KV working set within

Costly branch-wise kernel orchestration and intermediate data movement. NSA inherently evaluates compression, selection, and sliding-window branches and then combines their results. This structure is particularly awkward

2.3

Wang et al. 100%

Overlap Ratio (%)

for speculative verification. Unlike single-query decoding, verification involves multiple queries, which heavily amplifies branch-wise kernel launches and intermediate-result materialization. Unlike prefilling, the verifier batch is too small to amortize these fixed overheads, resulting in low arithmetic intensity per branch. As a result, kernel launches, intermediate writes and reads, and cross-branch data movement account for a disproportionate share of latency. Full fusion is further limited because each branch maintains its own normalization state before gated aggregation. Input-dependent acceptance and varied kernel performance. Compared with speculative decoding with dense verification, the performance of sparse verification presents varied patterns related to the draft length. Dense attention uses a regular layout, whereas NSA changes the sparse execution plan as the draft length changes: selected-block sets, index-construction overhead, and cross-query layout overlap all depend on the generated draft positions. Even worse, we observe that the acceptance rate and kernel performance are both highly input-dependent (Table 2), which makes it difficult to select a single optimal configuration for all inputs.

80% 60% 40% 20%

Layer 03

Layer 07 20

Layer 11

Token Position in Verification Batch

Layer 15 60

Figure 2. Selected-block overlap ratio between adjacent verifier queries (8K context). sec 6 Profile-Guided Planner

D, k, T

(휃� , 휃� ) = (D, k, T, C, M, S)

runtime adaption

C, M, S

tree-based input

Draft Construction

Acceptance/ Deferred Commit verified logits

sec 5

Sparse Verification

depth = D, branching = k

Token compression

SMEM / regs

sec 4 input

System Overview

This section proposes SSV to address the above challenges. We first summarize the design insights behind sparse speculative verification, and then show how SSV integrates the corresponding mechanisms into the draft–verify–accept workflow.

...

Cross-query execution

Token selection

Shared KV-block only loads once

Cross query overlap

Sliding window Verification-oriented fusion

Partial: selection + window Full: compression + selection + window

Figure 3. Overview of SSV. 3.1

Design Insights

nearest preceding refresh layer, bypass index derivation, and directly enter a fully fused kernel.

Insight 1: Nearby verifier queries have highly overlapping selected blocks. Tree-based speculative verification processes multiple draft positions in the same target-model pass. Although dynamic sparse attention gives each query its own selected-block set, verifier queries that are close in position often have semantically similar contexts and therefore select many of the same KV blocks. Our profiling confirms this trend: as shown in Figure 2, under an 8K context, the selected-block overlap ratio between adjacent verifier queries typically remains around 50%–90% across most layers. This overlap suggests grouping positionally close queries for joint execution, while the kernel can either preserve each query’s own layout or use a faster approximate shared layout.

Insight 3: Long decode horizons enable prompt-aware adaptive planning. Speculative decoding typically spans many verification rounds when generating a response, which gives the system a natural adaptation window for each prompt. Rather than committing to one fixed strategy for the entire generation, SSV can start from a strong initial choice and refine it as prompt-specific acceptance behavior becomes observable. This observation motivates SSV’s throughputaware planner, which combines offline strategy preselection with low-overhead prompt-aware reselection during decoding. 3.2

Insight 2: Cross-layer stability enables fully fused execution. Selected-block layouts are often stable across nearby Transformer layers, consistent with prior observations [3, 11, 13]; our profiling confirms the same trend during speculative verification (Table 1). SSV therefore organizes execution into Refresh/Reuse layers: refresh layers recompute selected indices and retain the routing-aware partial-fusion path, whereas reuse layers inherit the latest layout from the

Overview

Figure 3 illustrates how SSV integrates these mechanisms into the standard draft-verify-accept loop. While the outer interface remains unchanged, SSV fundamentally overhauls the verification internals. Rather than naively replacing dense attention with an off-the-shelf sparse kernel, SSV treats verification as a jointly planned workload: the planner synergizes draft construction with sparse verification, while the verifier 4

SSV : Sparse Speculative Verification for Efficient LLM Inference

90%

Layer 03

Layer 07

Layer 11

Layer 15

with overlap decreasing as token-position distance grows. Exploiting this spatial locality, SSV employs overlap-aware cross-query coarsening, grouping adjacent queries into a single thread block to amortize KV-block loads and scheduling overheads. We develop two variants of kernel execution: an exact merged-schedule variant that preserves precise perquery selection semantics, and an approximate shared-index variant that aggressively reuses a single selected-block set across the group, trading exact selection semantics for lower scheduling overhead.

Overlap Ratio (%)

80% 70% 60% 50% 40%

Query Distance

Figure 4. Selected-block overlap ratio versus absolute tokenposition distance Δ (8K context). The cross-query overlap consistently peaks at small Δ and decays as queries become further apart in the sequence.

4.1

Grouping design. To balance cross-query KV reuse and kernel scheduling overhead, SSV avoids the extremes of singlequery grouping (zero reuse) and all-query grouping (massive scheduling overhead and low parallelism). Instead, as shown in Figure 5(a), it employs a middle-ground strategy: partitioning verifier queries into thread blocks of up to 𝐶 adjacent queries. This design balances the tradeoff between reuse and overhead by keeping the group size 𝐶 manageable. While grouping is trivial for a flat draft sequence, treebased speculation introduces structural differences. Specifically, a tree node can be grouped either with its siblings (candidates for the same position that are likely synonymous) or with its parent and children (candidates across nearby positions with strong semantic proximity). In practice, SSV reorganizes the draft tree into a flattened batch using two traversal orders [9]: breadth-first search (BFS) to enforce sibling-based grouping, and depth-first search (DFS) to enforce parent/child-based grouping. Because the optimal grouping strategy depends heavily on the specific verification setting and realized query ordering, no single tree-local rule is universally superior. Therefore, rather than using a static heuristic, SSV delegates this choice to the throughput-aware planner (Section 6), which adaptively selects the best traversal order based on offline profiles and runtime states. Driven by the selected traversal order, SSV partitions the flattened batch into groups of up to 𝐶 adjacent queries. Following the principle of thread coarsening [31], each group is processed in parallel by a single thread block. By sharing register tiles across query heads in grouped-query attention (GQA) [1], this execution amortizes memory access and scheduling overheads without altering the logical tree masks or absolute positions. This grouped execution naturally extends to the sliding-window branch, which advances a shared window scan while enforcing per-query local masks. After grouping verifier queries, the remaining question is how the kernel handles their non-identical selected-block sets. We will delve into two distinct execution variants.

exploits cross-query index overlap and fused execution to maximize hardware efficiency. Overlap-aware cross-query execution (Section 4). The first optimization module targets redundant KV-block traffic inside sparse verification. SSV groups nearby verifier queries according to the draft traversal order and executes them within a shared thread block, so overlapping selected blocks are loaded once and reused across queries. Depending on the deployment precision budget, this module either preserves per-query sparse layouts through an exact merged schedule or uses a faster approximate shared-index layout for highly overlapping query groups. Verification-oriented kernel fusion (Section 5). The second module reduces the branch fragmentation introduced by NSA’s compression, token-selection, and sliding-window paths. In refresh layers, SSV keeps the routing-dependent compression path separate but fuses token selection, slidingwindow attention, and gated aggregation into a downstream kernel. In reuse layers, stable selected-block indices remove the routing dependence, enabling a fully fused kernel that computes all NSA branches with on-chip intermediate state and writes back only the final output. Profile-guided adaptive planning (Section 6). The third module coordinates draft construction and sparse verification as one strategy-selection problem. An offline profiler ranks joint configurations over draft-tree shape, traversal order, cross-query coarsening, and refresh/reuse schedules for each context regime and precision class. At runtime, SSV starts from the profiled best strategy and refines it during the early decoding window when prompt-specific acceptance or kernel behavior deviates from the profile.

Cross-Query Grouping

Overlap-Aware Kernel Design

Insight 1 and Figure 4 show that verifier queries that are close in sequence position tend to select overlapping KV blocks, 5

Wang et al. (a) Query Grouping

푞�

푞� 푞�

…

grouped

12 18 ② merge

12 18

③ load shared KV

푞�

✓ Exact per-query selection; load each block once (c) Approximate variant

✓

-∞

✓

grouped

푞�

② select 푞� compressed block

-∞ ✓

✓

Attention mask

① designate q0 as rep. grouped

Table 1. Benchmark results (%) on a 1B NSA model, evaluated on PIQA, HellaSwag, ARC-Easy, and ARC-Challenge. “SSV + reuse layers” uses the training-free IndexCachestyle [3] refresh/reuse schedule S = {3, 6, 7, 8, 12, 13, 14, 15}, and “𝐶 = 4” denotes the approximate shared-index variant with grouping factor 4.

Attention mask

① select compressed 2 푞� block

bfs flatten

푞�

(b) Exact variant

12 18

③ load Shared KV

≈ Approximate selection; no merge step

푞�

✓

Benchmark

✓

73.78 ± 1.03 58.37 HellaSwag / % ± 0.49 69.49 ARC-Easy / % ± 0.94 36.95 ARC-Challenge / % ± 1.41

73.88 ± 1.02 58.53 ± 0.49 69.82 ± 0.94 37.37 ± 1.41

73.88 ± 1.02 58.47 ± 0.49 69.82 ± 0.94 37.29 ± 1.41

Exact Merged-Schedule Variant

The exact merged-schedule variant reduces memory traffic by jointly scheduling shared KV blocks without altering per-query selection semantics. As shown in Figure 5(b), the kernel achieves this through three steps: (1) Independent Selection: It computes the selected block-index set 𝐼𝑡( 𝑗 ) independently for each query in the group. (2) On-chip Merging: It concatenates these per-query indices, sorts them, and performs a linear scan to deduplicate identical entries. This creates a unified schedule containing the union of all selected blocks while tracking query-to-block ownership. (3) Shared Loading and Masking: Each unique KV block in the merged schedule is loaded from HBM exactly once and shared across the group. To preserve exact semantics, the kernel applies a row-wise mask during attention computation: logits are masked to −∞ if the key block does not belong to a specific query’s original selected set. This design effectively amortizes the HBM load costs of overlapping blocks while remaining semantically equivalent to independent query execution. 4.3

73.99 ± 1.02 58.55 ± 0.49 69.57 ± 0.94 37.12 ± 1.41

PIQA / %

Figure 5. Overlap-aware kernel design.

4.2

SSV SSV + reuse SSV + reuse (𝐶 = 4) (𝐶 = 4)

SSV

(a) Original NSA separate launches Compute path

푞�

HBM-resident values

gating

slc

cmp

win

read branch outputs

read idx

output W/R

fresh indices W/R

output W/R

표�

final output W

output W/R

(b) Refresh layer: partial fusion 2 launches Compute path

푞�

cmp

HBM-resident values ①Routing output W/R

gating

②

Downstream fusion

slc

win

on-chip state

read idx

fresh indices W/R

output on-chip

read cmp output

표�

③

Write-back

final output W

output on-chip

푞�

cmp

HBM-resident values ①Skip routing read idx output on-chip

reused indices R

slc

② win Full fusion output on-chip

output on-chip

③Reg. aggregation in-register gating

표�

final output W

Figure 6. Demonstration of three fusion strategies.

Approximate Shared-index Variant

Prior work [26] has shown that leveraging the same index for neighboring tokens barely affects model quality. Therefore, this variant aims to maximize reuse by forcing all 𝐶 queries in the group to share the same selected block set. As shown in Figure 5(c), instead of computing per-query indices and merging them, the kernel simply: 1) designates a single representative query for the group (e.g., the one with the longest prefix); 2) computes the selected block-index set 𝐼𝑡( 𝑗 ) solely for this representative; and 3) applies this shared layout to compute attention for the entire group. This strategy completely bypasses the sort-and-merge overhead and drastically reduces HBM traffic for KV-block loading. The approximation arises because non-representative queries may miss their individually preferred KV blocks. However, while the sparse-attention branch becomes approximate, the sliding-window branch remains entirely precise,

enforcing strict per-row boundaries and causal masks using each query’s individual absolute position. Accuracy evaluation. To validate its quality impact, we conduct a model-integrity study on a 1B NSA target model [36, 37]. We evaluate the variant using lm-evaluation-harness [12] on PIQA [5], HellaSwag [35], ARC-Easy, and ARC-Challenge [8] (using 3-, 10-, and 25-shot, respectively). As shown in Table 1, the approximate variant (𝐶 = 4) exhibits negligible accuracy degradation compared to the exact SSV baseline. In practice, SSV applies this aggressive coarsening only in regimes with sufficient concurrent queries (typically at larger draft length 𝛾) where cross-query reuse heavily outweighs the approximation penalty. 6

SSV : Sparse Speculative Verification for Efficient LLM Inference

Kernel Fusion

motivating the index-reuse-enabled full-fusion path introduced next.

Figure 6(a) illustrates the branch-wise execution challenge of the original NSA. While evaluating branches through separate paths is tolerable in standard single-query decoding, it becomes a severe bottleneck in speculative verification. Because a verifier pass consists of many short, heterogeneous queries, repeatedly materializing intermediate indices and branch outputs to HBM for gated aggregation incurs disproportionate kernel-launch and memory-bound overheads. To eliminate this fragmentation, SSV employs a two-tiered kernel fusion strategy guided by cross-layer index stability (Insight 2) [3]: (1) Routing-aware partial fusion (Refresh layers): For layers that must compute fresh indices, SSV respects the strict data dependence between routing and selected attention. It isolates the compression/routing path while fusing the downstream token-selection and sliding-window branches. (2) Index-reuse-enabled full fusion (Reuse layers): For layers that inherit a stable selected-block layout from a preceding refresh layer, the data dependence is broken. SSV bypasses index derivation entirely and deploys a fully fused kernel that computes all three NSA branches and their gated aggregation in a single launch.

5.1

5.2

Index-Reuse-Enabled Full Fusion

Prior cross-layer index reuse studies observe that sparse indices are often stable across adjacent Transformer layers [3, 11]. Therefore, for reuse layers, the selected-block layout is inherited from the nearest preceding refresh layer [3, 11]. This inheritance provides a controlled approximation that bypasses layer-specific recomputation overhead while preserving concrete sparse evaluation. To initialize the stream, the first layer acts as a mandatory refresh layer. As illustrated in Figure 6(c), SSV exploits this by enabling a single-launch full-fusion path: (1) Zero-Overhead Routing: Because the sparse layout is already available, SSV completely bypasses the separate routing launch. (2) Monolithic Execution: It invokes a fully fused kernel that reads the inherited indices, interprets them under the current draft-position masks and compressed-block visibility constraints, and computes the compression, token-selection, and sliding-window branches in one unified pass. (3) In-Register Aggregation: The kernel keeps all intermediate branch outputs on-chip, performs gated aggregation directly in registers, and writes back only the final layer output to HBM. By transforming the expensive indices from a refresh layer into a reusable execution plan, this design drastically reduces launch overhead and avoids intermediate materialization.

Routing-Aware Partial Fusion

NSA leaves a natural partial-fusion opportunity: the tokenselection and sliding-window branches both consume the same verifier query and can share one downstream kernel, provided their independent normalization states are preserved. However, the compression/routing path must remain isolated in refresh layers for two reasons. First, there is a strict data dependency: selected attention cannot issue sparse KV loads until routing produces the Top-𝑛 indices. Second, they exhibit mismatched hardware execution patterns: routing is bound by importance scoring and Top-𝑛 reduction, whereas downstream attention is optimized for sparse memory gathering and attention accumulation. Forcing them into a monolithic kernel would couple conflicting resource requirements and offset the fusion benefits. To resolve this, SSV executes refresh layers using a twolaunch strategy, as shown in Figure 6(b): (1) Routing Launch: SSV first runs the compression/routing path to produce the compressed-branch output and the fresh selected indices. (2) Downstream Fusion: Once indices are available, SSV launches a partially fused kernel for the token-selection and slidingwindow branches. It reads the newly generated indices, computes both attention branches alongside their independent online softmax states, and performs gated aggregation directly in registers. (3) Unified Write-back: The kernel writes only the final aggregated layer output back to HBM, completely bypassing intermediate branch-output materialization. This removes downstream branch fragmentation but still leaves selected-index derivation outside the fused kernel,

Quality impact. Because index reuse is a controlled approximation, we evaluate its impact on model integrity using a 1B NSA target model [36, 37]. We apply a IndexCache-style [3] greedy calibration to determine the optimal schedule, yielding the reuse pattern S = {3, 6, 7, 8, 12, 13, 14, 15}. Evaluated via lm-evaluation-harness [12] on PIQA, HellaSwag, ARCEasy, and ARC-Challenge, both the standard index-reuse execution and its aggressive combination with approximate cross-query grouping (𝐶 = 4) exhibit negligible accuracy degradation (Table 1). This confirms that our schedule preserves reasoning capabilities while maximizing hardware efficiency.

Profile-Guided Prompt-Adaptive Orchestration

Compared with full-attention speculative decoding, sparseattention speculative decoding introduces several changes as follows: 1) Different draft-length behavior. As shown in Figure 7, full attention and SSV variants show different forwardlatency trends as the draft length 𝛾 changes, so the draft configuration preferred by a dense verifier may not be optimal for sparse verification; 2) Larger configuration space. Sparse verification introduces additional choices, including 7

Wang et al.

Full Attention

SSV

schedule), Reuse-only (exact coarsening, conservative refresh/reuse schedule), Approx-only (approximate coarsening, all-refresh schedule), or Approx+Reuse (both approximate coarsening and index reuse). This categorization explicitly balances exact sparse-attention semantics with peak verification efficiency.

Latency (ms)

60 50 40 30

Problem formulation. We formulate framework-level planning as a constrained discrete optimization problem. For a context-length regime 𝑟 and user-specified precision class P, SSV selects the strategy tuple (𝜃𝑑 , 𝜃 𝑠 ) that maximizes the expected accepted-token throughput:

20 0

100

150

Draft Length

200

250

Figure 7. Forward latency versus draft length 𝛾 on a Llama31B backbone at 32K context; SSV uses the same backbone with its attention layers replaced by NSA-based sparse verification.

arg max (𝜃𝑑 ,𝜃 𝑠 )

where 𝐴(𝜃𝑑 , 𝜃 𝑠 | 𝑟, P) is the number of accepted tokens per verification step, and 𝑇 (𝜃𝑑 , 𝜃 𝑠 | 𝑟, P) is the end-to-end step latency. E[·] denotes the expectation over prompts and verifier queries under regime 𝑟 and precision class P.

traversal order, coarsening mode, coarsening factor, and refresh/reuse schedule. These choices interact with draft construction because changing 𝛾 also changes the realized verifier batch size, the opportunity for cross-query coarsening, and the extent to which sparse-routing and fusion overheads are amortized; and 3) Prompt-dependent preference. As motivated by Insight 3 in Section 3.1, different prompts can favor different configurations because acceptance behavior and selected-index overlap are input-dependent. This section presents SSV’s profile-guided orchestration policy, using EAGLE-3 [22] as the primary framework. We first formalize the joint strategy space and throughput objective, then describe how offline profiles preselect strong initial strategies, and finally introduce a lightweight runtime guard that dynamically refines choices to handle prompt-specific deviations. 6.1

E[𝐴(𝜃𝑑 , 𝜃 𝑠 | 𝑟, P)] . E[𝑇 (𝜃𝑑 , 𝜃 𝑠 | 𝑟, P)]

6.2

Profile-Guided Strategy Preselection

Profiling. To solve the optimization problem without runtime overhead, SSV builds an offline profiler on the target platform. Given a small calibration prompt set, the profiler evaluates the valid candidate strategies for each (𝑟, P) by running the end-to-end speculative decoding workflow. During execution, it explicitly measures the expected accepted tokens E[𝐴(𝜃𝑑 , 𝜃 𝑠 | 𝑟, P)] and step latency E[𝑇 (𝜃𝑑 , 𝜃 𝑠 | 𝑟, P)] to compute the accepted-token throughput objective. The resulting profile is organized as a lookup table indexed by the tuple (𝑟, P). Each table entry contains a ranked list of valid strategy pairs (𝜃𝑑 , 𝜃 𝑠 ) sorted by descending throughput. Alongside the strategy, the table stores the expected acceptance rate E[𝐴(𝜃𝑑 , 𝜃 𝑠 | 𝑟, P)], which serves as the reference threshold for the runtime guard.

Strategy Space and Optimization Problem

Preselection. In our implementation, the offline profile forms a compact 192-entry lookup table spanning four contextlength buckets (0–4K, 4–8K, 8–12K, and 12–16K), four precision classes and 12 ranked candidates in each bucket. At runtime, SSV bypasses expensive online grid search via a direct 𝑂 (1) table lookup. Given the initial context length and user-specified precision class P, it maps them to the regime 𝑟 and retrieves the highest-ranked valid strategy (𝜃𝑑∗ , 𝜃 𝑠∗ ). This lookup gives a low-overhead initial configuration; since offline profiles rely on small calibration sets and coarse buckets, the runtime guard (Section 6.3) later refines the strategy when prompt-specific behavior deviates.

Strategy space. SSV formulates sparse speculative verification as a joint strategy-selection problem. To navigate the interacting draft-side and target-side choices, we categorize the search space into three types of variables, denoted by 𝜃𝑑 , 𝜃 𝑠 , and P: • Full-attention variables 𝜃𝑑 = (𝐷, 𝑘, T ): Draft-tree depth 𝐷, branching width 𝑘, and traversal order T . These dictate the number of verifier queries and their positional adjacency in the batch. • Sparse-attention variables 𝜃 𝑠 = (𝐶, 𝑀, S): Thread coarsening factor 𝐶, coarsening mode 𝑀, and refresh/reuse schedule S. These control how overlapping KV blocks are shared across queries and how often selected indices are recomputed across layers. • User-specified constraint P: A precision class P that bounds the valid subspace by restricting the strategy to one of four levels: Strict (exact coarsening, all-refresh

6.3

Prompt-Adaptive Strategy Refinement

Prompt sensitivity. A small profiling slice under the same deployment setting shows that the best profiled strategy is not uniform across prompt types. As shown in Table 2, 8

SSV : Sparse Speculative Verification for Efficient LLM Inference

Table 2. Prompt sensitivity of profiled strategies in the 0–4K context bucket under P = Strict. Values report acceptedtoken throughput in tok/s, with the best result for each prompt shown in bold.

on statistics already emitted by verification, its negligible bookkeeping overhead is further evaluated in Section 7.4.

7 Prompt

BFS-large-deep DFS-small-deep DFS-med-base (tok/s) (tok/s) (tok/s)

chat-gen. chat-plan. plain code

229.7 232.8 202.3 242.2

229.8 222.9 225.9 266.7

Evaluation

This section presents a comprehensive evaluation of SSV. We aim to investigate the following research questions to validate the effectiveness of our proposed optimizations: • Q1: Integration with Speculative Frameworks. When integrated with a real speculative decoding framework such as EAGLE-3 [22], how much end-to-end generation throughput can the full SSV system achieve? • Q2: Verification-Stage Performance. What is the impact of SSV on speculative verification latency? • Q3: Kernel Performance Breakdown. How do the various implementations of the SSV kernel perform? What is the breakdown performance of SSV kernels? • Q4: Effectiveness of Verification Planning. Does joint planning over draft construction and sparse verification improve accepted-token throughput over fixed configurations, and can lightweight runtime refinement recover from prompt-specific profile mismatch?

233.4 225.0 210.2 259.2

Algorithm 1 Prompt-adaptive runtime strategy refinement. 1: Input: Profile R, regime 𝑟 , precision class P 2: (𝜃𝑑 , 𝜃 𝑠 ) ← Preselect(R, 𝑟, P) 3: for each verification step 𝑡 do 4: Run verification, obtain 𝐴𝑡 ,𝑇𝑡 5: if Within the early steps then 6: (𝜃𝑑 , 𝜃 𝑠 ) ← Refine(R, 𝑟, P, 𝐴𝑡 ,𝑇𝑡 ) 7: end if 8: end for

Evaluation setup. Unless otherwise stated, all experiments are conducted on an NVIDIA H100 PCIe GPU [27]. Our baseline starts from the public NSA Triton reference implementation [18, 29] and extends to the verification-oriented execution. We instantiate the standard NSA configuration [33] with compression block size 𝑙 = 32 and stride 𝑑 = 16, selected block size 𝑙 ′ = 64 and selected block count 𝑛 = 16, and slidingwindow size 𝑤 = 512, together with 32 query heads, 8 KV heads, and head dimension 64. For end-to-end experiments, prompts are drawn from Children-Stories-Collection [2]. Unless specified, we use batch size 1 and bfloat16 precision [16]. All reported latencies are measured with CUDA events via torch.cuda.Event [28].

different prompts select different profiled strategies. This motivates prompt-aware reselection when observed acceptance deviates from the profile. The early decoding window provides enough observations for runtime adaptation. SSV therefore refines the preselected strategy only during the initial verification steps. At each step, it records the accepted tokens and step latency, then uses these observations to decide whether the profile-selected strategy should be updated. Prompt-aware runtime refinement. As outlined in Algorithm 1, SSV starts from the profile-preselected strategy and runs verification with the current (𝜃𝑑 , 𝜃 𝑠 ). Each step produces the accepted-token count 𝐴𝑡 and latency 𝑇𝑡 , which are already available from speculative verification. During the early steps, SSV updates the context-length state as tokens are accepted and invokes Refine with the profile, regime, precision class, and the latest observations. Inside Refine, SSV smooths the observed accepted-token counts and compares the smoothed value with the expected acceptance E[𝐴(𝜃𝑑 , 𝜃 𝑠 | 𝑟, P)] stored for the active strategy. In our experiments, the smoothing coefficient is 𝛼 = 0.40; after an 8-step warmup, if the smoothed value remains below 0.85× the profiled expectation for 5 consecutive steps, Refine switches to the next highest-ranked valid strategy in the current profile. To avoid oscillation, SSV permits at most two profile transitions per request and selects the best configuration explored in the current run if the mismatch persists. These constants are fixed across context buckets, precision classes, and held-out prompts. Since this policy relies only

7.1

End-to-End Evaluation in EAGLE-3 (Q1)

Configuration and metric. To evaluate whether SSV’s optimizations translate to visible end-to-end gains, we integrate vanilla NSA [18] and SSV into EAGLE-3 [22]. We evaluate a 1.2B-parameter NSA target model pretrained on ChildrenStories-Collection [2]. All experiments use a 16K context length, temperature 0.0, and 256 generated tokens. Under this setting, the plain autoregressive decode baseline reaches 49 token/s, and serves as the common speedup reference. We compare end-to-end throughput across draft-tree shapes parameterized by tree depth 𝐷 and branching width 𝑘. For larger draft lengths (𝛾 ≥ 64), we enable the exact mergedschedule variant with grouping factor 𝐶 = 2. In the SSV with reuse layers setting, the refresh/reuse schedule is calibrated using a training-free IndexCache-style policy [3], yielding S = {1, 2, 3, 6, 8, 10, 11, 15}. 9

Wang et al.

125

127

124

120

117

106

119

130

136

134

140

127

112

106

121

134

139

136

133

119

112

105

114 126 126 128 128 122 127 121 2 2.32x 2.57x 2.56x 2.62x 2.61x 2.50x 2.60x 2.47x

3 2.27x 2.54x 2.55x 2.59x 2.54x 2.45x 2.38x 2.16x

139

140

137

134

125

129

141

147

148

147

140

132

124

130

143

151

150

149

142

134

126

122 133 135 135 134 131 139 131 2 2.49x 2.72x 2.75x 2.75x 2.74x 2.67x 2.83x 2.66x

5 2.65x 2.93x 3.08x 3.06x 3.04x 2.90x 2.73x 2.58x 132 144 149 156 149 140 134 123 6 2.69x 2.93x 3.03x 3.18x 3.05x 2.86x 2.74x 2.50x

127

139

142

141

152

149

144

133

135

145

152

163

159

143

138

132

138

153

158

156

151

143

130

3 2.59x 2.83x 2.89x 2.89x 3.11x 3.03x 2.93x 2.71x

4 2.63x 2.87x 2.99x 3.02x 3.00x 2.86x 2.69x 2.53x

Tree Depth

123 134 141 142 133 125 112 101 6 2.51x 2.72x 2.88x 2.90x 2.71x 2.55x 2.28x 2.06x

135

3 2.48x 2.76x 2.84x 2.87x 2.87x 2.80x 2.73x 2.56x

4 2.43x 2.66x 2.77x 2.74x 2.85x 2.59x 2.28x 2.16x 5 2.48x 2.73x 2.84x 2.78x 2.71x 2.43x 2.29x 2.15x

121

4 2.76x 2.97x 3.09x 3.32x 3.24x 2.93x 2.82x 2.69x

Tree Depth

111

170 160 150

5 2.82x 3.11x 3.22x 3.23x 3.19x 3.07x 2.91x 2.66x

140

137 151 154 171 160 139 139 132 6 2.80x 3.09x 3.13x 3.49x 3.27x 2.84x 2.84x 2.69x

130

122 137 142 139 127 118 109 98 7 2.49x 2.79x 2.89x 2.83x 2.59x 2.41x 2.22x 2.00x

131 144 150 155 150 136 131 118 7 2.68x 2.95x 3.06x 3.17x 3.05x 2.78x 2.67x 2.42x

138 156 159 164 160 144 137 126 7 2.82x 3.19x 3.24x 3.34x 3.27x 2.95x 2.80x 2.58x

120

122 132 139 139 127 114 105 91 8 2.50x 2.69x 2.83x 2.84x 2.59x 2.33x 2.14x 1.86x

130 144 149 153 139 133 125 116 8 2.65x 2.95x 3.05x 3.13x 2.83x 2.71x 2.55x 2.36x

136 150 163 164 150 141 126 117 8 2.78x 3.06x 3.32x 3.34x 3.06x 2.88x 2.56x 2.39x

124 138 139 137 115 115 103 91 9 2.53x 2.82x 2.83x 2.80x 2.34x 2.35x 2.09x 1.85x

129 147 145 150 142 135 122 107 9 2.63x 3.01x 2.95x 3.07x 2.89x 2.76x 2.49x 2.17x

136 146 158 152 144 145 129 108 9 2.78x 2.99x 3.22x 3.10x 2.94x 2.97x 2.63x 2.21x

110

Draft Branching Width

(a) Vanilla NSA

Draft Branching Width

(b) SSV

Draft Branching Width

Throughput (token/s)

104 114 115 116 117 113 112 104 2 2.13x 2.33x 2.34x 2.37x 2.38x 2.31x 2.28x 2.11x

100

Figure 8. End-to-end generation throughput under EAGLE-3 with different draft-tree shapes. Each cell shows throughput on the first line and speedup on the second line, where the speedup baseline is the NSA decode throughput (49 token/s). Results. As shown in Figure 8, integrating sparse verification with speculative decoding yields large end-to-end gains over the 49 token/s decode baseline. Across the full grid of evaluated (𝐷, 𝑘) settings, vanilla NSA integrated with EAGLE-3 reaches 91–142 token/s, corresponding to 1.85×– 2.90× speedup. SSV consistently improves throughput across these tree shapes: without reuse layers, it reaches 107–156 token/s, or 2.17×–3.18× speedup, and enabling reuse layers further boosts throughput to 108–171 token/s, or 2.21×–3.49× speedup. The highest absolute throughput is achieved by SSV with reuse layers at (𝐷 = 6, 𝑘 = 4), where it reaches 171 token/s, or 3.49× over the decode baseline. Overall, these results show that the combination of sparse attention with speculative decoding delivers substantial end-to-end acceleration, and that the additional optimizations in SSV, especially reuselayer execution, can further improve throughput across the evaluated draft-tree settings.

7.2

over vanilla NSA [18] on both models. Enabling reuse layers significantly boosts this to 1.24×–1.28× (1B) and 1.17×– 1.25× (8B). For larger draft lengths (𝛾 ≥ 64), grouped-query execution brings additional independent gains. For instance, on the 1B model, the exact variant (𝐶 = 2) and approximate variant (𝐶 = 4) reach up to 1.10× and 1.23× speedups, respectively. The 8B model follows the same trend, albeit with slightly more modest gains, up to 1.02× and 1.12×. Crucially, the synergy of multiple optimizations delivers the strongest overall results, especially reuse layers plus the approximate shared-index variant. While combining reuse layers with the exact merged-schedule variant (𝐶 = 2) yields substantial speedups of 1.19×–1.26× (1B) and 1.06×–1.12× (8B), upgrading to the approximate shared-index variant (𝐶 = 4) unlocks peak performance across the board. This aggressive combination achieves the highest overall speedups of 1.30×–1.45× (1B) and 1.18×–1.23× (8B). These results confirm that while individual mechanisms provide measurable benefits, their synergy is required to unlock the largest practical acceleration for NSA verification.

Verification-Stage Performance (Q2) 7.3

Configuration and metric. To benchmark verification latency (Q2), we evaluate NSA target models adapted from Llama3-1B and Llama3-8B backbones [14, 33]. We test sequence lengths 𝑁 ∈ {16K, 32K, 64K} and draft lengths 𝛾 ∈ {4, 64, 128}. For reuse layers, we apply an alternating schedule S = {1, 3, 5, . . .}. At larger draft lengths (𝛾 ∈ {64, 128}), we also evaluate our most efficient grouped-query variants: exact merged-schedule (𝐶 = 2) and approximate sharedindex (𝐶 = 4). We report verification latency and speedup over vanilla NSA [18].

SSV Kernel Benchmarking Results (Q3)

Configuration and metric. To benchmark verification kernels (Q3), we evaluate draft lengths 𝛾 ∈ {4, 64} across sequence lengths 𝑁 ∈ {8K, 16K, 32K, 64K}. We fix the selectedblock count 𝑛 = 16 and control cross-query redundancy 𝑗) by varying the adjacent-query overlap 𝑠 = |𝐼𝑡( 𝑗 ) ∩ 𝐼𝑡(−1 | ∈ {3, 6, 10}. This range explicitly covers both the theoretical lower bound (𝑠 = 3, due to mandatory initial/local blocks [33]) and representative high-overlap scenarios (𝑠 ∈ {6, 10}) observed in real EAGLE traces. We report speedups over the vanilla NSA baseline [18] in Fig. 10.

Results. As shown in Figure 9, SSV consistently accelerates verification, with performance gains stacking clearly as optimizations are combined. At a short draft length (𝛾 = 4), SSV without reuse layers yields modest 1.05×–1.07× speedups

Comparison with Vanilla NSA. For short drafts (𝛾 = 4), the primary gains stem from kernel fusion. Compared to the vanilla NSA baseline [18], SSV without reuse layers achieves 10

SSV : Sparse Speculative Verification for Efficient LLM Inference

32K

64K

Sequence Length

16K

32K

64K

16K

32K

64K

Sequence Length

(e) Llama3-1B, 𝛾 = 128

16K

32K

0.2 0.0 8K 16K 32K 64K

Latency (ms)

(b) 𝛾 = 64, 𝑠 = 3

0.4 0.2 0.0 8K 16K 32K 64K

Sequence Length

16K

32K

0.4 0.2 0.0 8K 16K 32K 64K

Sequence Length

0.4

64K

(d) Llama3-8B, 𝛾 = 64

Latency (ms)

Sequence Length

Latency (ms)

0.4 0.2 0.0 8K 16K 32K 64K

(a) 𝛾 = 4, 𝑠 = 3

Sequence Length

64K

(b) Llama3-8B, 𝛾 = 4

Latency (ms)

32K

0.0 8K 16K 32K 64K

Sequence Length

(a) Llama3-1B, 𝛾 = 4

16K

0.2

Latency (ms)

16K

0.4

SSV (approximate, refresh) SSV (no grouping, reuse) SSV (exact, reuse) SSV (approximate, reuse)

(e) 𝛾 = 4, 𝑠 = 10

64K

Sequence Length

(d) 𝛾 = 64, 𝑠 = 6

Latency (ms)

Top-n Block Selection Vanilla NSA SSV (no grouping, refresh) SSV (exact, refresh)

Latency (ms)

SSV (no grouping, reuse) SSV (exact, reuse) SSV (approximate, reuse)

Latency (ms)

Vanilla NSA SSV (no grouping, refresh) SSV (exact, refresh) SSV (approximate, refresh)

0.4 0.2 0.0 8K 16K 32K 64K

Sequence Length

(f) 𝛾 = 64, 𝑠 = 10

Figure 10. Performance breakdown and ablation of SSV kernel variants. The charts compare grouped-query kernel variants, cross-query overlap 𝑠 (the number of shared selected blocks between adjacent queries), and reuse-layer execution under small and large draft lengths (𝛾 = 4 and 𝛾 = 64). Refresh/reuse indicates the layer type, and no grouping/exact/approximate indicates the grouped-query kernel mode.

(f) Llama3-8B, 𝛾 = 128

Figure 9. Speculative verification latency on NSA target models built from Llama3-1B and Llama3-8B backbones under different draft lengths 𝛾 and sequence lengths 𝑁 . We compare vanilla NSA [18], SSV without reuse layers, and SSV with reuse layers; for 𝛾 ∈ {64, 128}, we include the exact merged-schedule variant with 𝐶 = 2 and the approximate shared-index variant with 𝐶 = 4. Refresh/reuse indicates the layer type, and no grouping/exact/approximate indicates the grouped-query kernel mode.

measurable improvements, eliminating repeated index construction remains the dominant source of acceleration. Comparison between variants of the SSV kernel. The benefits of grouped-query execution are highly dependent on draft length, scaling effectively at larger 𝛾 (e.g., 𝛾 = 64). Furthermore, as cross-query overlap 𝑠 increases from 3 to 10, the grouped variants yield increasingly higher gains. This confirms that larger verification batches provide sufficient adjacent queries to successfully amortize scheduling and KV-loading costs. Crucially, cross-layer reuse and cross-query grouping act as highly complementary mechanisms. Skipping 𝐼𝑡( 𝑗 ) construction enables deeper kernel fusion, allowing reuse paths to consistently dominate non-reuse baselines. Meanwhile,

a 1.14×–1.18× speedup. Enabling full fusion in reuse layers removes significant index-construction overhead, catapulting the speedup to 4.45×–6.86×. For longer drafts (𝛾 = 64), grouped-query execution introduces additional independent gains. On their own, the exact (𝐶 = 2) and approximate (𝐶 = 4) variants yield speedups up to 1.13× and 1.22×, respectively. However, the most profound acceleration occurs when these are combined with reuse layers. While SSV with reuse layers alone achieves up to 2.44×, pairing it with the exact variant reaches 2.09×– 2.99×, and combining it with the approximate variant yields a 4.81×–6.30× speedup. Overall, while grouping provides 11

Wang et al.

Table 3. Effectiveness of throughput-aware planning on heldout prompts. Static-best uses the top-ranked profiled strategy without runtime refinement, Best+R adds runtime refinement, Gain reports the improvement of Best+R over Base, and RR indicates whether refinement is triggered. Throughput is measured in accepted tokens/s.

the higher 𝑠 overlap in large 𝛾 settings maximizes the efficiency of joint query execution. Together, they eliminate the index bottleneck and expose a shorter fused path. Performance breakdown of SSV. Constructing selected block indices is a severe memory-bound bottleneck in NSAstyle verification, accounting for 45%–56% of the total kernel runtime. In small-𝛾 scenarios (𝛾 = 4), this index-selection cost even exceeds the sparse attention computation itself (averaging 1.05× the attention cost), and it remains substantial (0.84×–0.88×) at 𝛾 = 64. This breakdown highlights exactly why reuse layers are so transformative. By inheriting 𝐼𝑡( 𝑗 ) from a preceding refresh layer instead of recomputing it, SSV entirely bypasses this massive overhead and unlocks more aggressive kernel fusion. Therefore, the reuse-layer design is not a marginal tweak, but the fundamental mechanism translating NSA’s algorithmic sparsity into concrete hardware acceleration. 7.4

Throughput-Aware Verification Planning (Q4)

Configuration and metric. For Q4, we evaluate the planner from Section 6 on held-out prompts using accepted-token throughput. We compare three settings: Base, Static-best, and Best+R. Base is a non-adaptive EAGLE-3 configuration with BFS traversal, a 128-token draft-tree budget, depth 𝐷 = 6, draft TopK 𝑘 = 10, exact coarsening with 𝐶 = 2, and an all-F sparse-verification schedule. Static-best uses the top-ranked profiled strategy for each context bucket and precision class without runtime refinement, while Best+R additionally enables runtime refinement. All three settings generate 128 output tokens with temperature set to 0.0, and run with a maximum context length of 16K. Thus, planner gains are measured against a fixed strategy under the same model, workload, and measurement protocol. The offline profile covers 16 bucket-class pairs, with 12 ranked candidate strategies stored for each pair. Static-best uses the top-ranked candidate for the active pair, while Best+R starts from the same candidate and may refine the choice using runtime observations. Table 3 therefore reports one row for each bucket-class pair.

Bucket

Class

Base

Static-best

Best+R

Gain

0–4K 0–4K 0–4K 0–4K 4–8K 4–8K 4–8K 4–8K 8–12K 8–12K 8–12K 8–12K 12–16K 12–16K 12–16K 12–16K

Strict Reuse-only Approx-only Approx+Reuse Strict Reuse-only Approx-only Approx+Reuse Strict Reuse-only Approx-only Approx+Reuse Strict Reuse-only Approx-only Approx+Reuse

196.3 196.3 196.3 196.3 169.0 169.0 169.0 169.0 168.6 168.6 168.6 168.6 137.4 137.4 137.4 137.4

164.2 232.7 207.6 206.1 197.0 216.0 182.7 192.4 171.5 189.3 176.6 192.0 156.2 165.5 137.2 182.6

192.4 230.7 206.8 247.9 200.5 217.4 181.8 192.4 172.3 189.4 176.5 192.5 154.4 164.7 168.0 183.0

−2.0% 17.5% 5.3% 26.3% 18.6% 28.6% 7.6% 13.8% 2.2% 12.3% 4.7% 14.2% 12.4% 19.9% 22.3% 33.2%

yes no no yes no no no no no no no no no no yes no

Runtime refinement. Best+R improves average throughput by 14.4% over Base and by 3.4% over Static-best. Runtime refinement is triggered in 3 of the 16 bucket-class settings, targeting cases where the initial profiled choice mismatches the held-out prompt behavior. The 0–4K Strict row illustrates this role: Static-best drops from 196.3 to 164.2 tok/s, but runtime refinement brings throughput back near Base at 192.4 tok/s. In 12–16K Approx-only, the same mechanism turns near-Base Static-best performance into a 22.3% gain. Overall, these results show that lightweight acceptance validation can correct prompt-specific profile mismatches without turning planning into online search. Refinement validation. We validate runtime refinement on a deployment profile that selects one strategy per context bucket: Approx+Reuse for 0–4K, Reuse-only for 4–8K, Approx+Reuse for 8–12K, and Approx+Reuse for 12–16K. With strategy refinement disabled, the bookkeeping needed for acceptance validation changes throughput by only −1.1% to +2.5% across buckets, which is within the run-to-run variation of our decode benchmark. Table 4 reports a one-factor sweep over the refinement constants. We denote the guard constants as the EMA coefficient 𝛼, the acceptance-drop ratio 𝜌, the minimum observation count 𝑚, and the hysteresis window ℎ. The default setting uses 𝛼 = 0.40, 𝜌 = 0.85, 𝑚 = 8, and ℎ = 5. Varying the EMA coefficient 𝛼, acceptance-drop ratio 𝜌, and minimum observation count 𝑚 keeps gains in the 25.2%–26.6% range. The main sensitivity is the hysteresis window ℎ: ℎ = 3 is too aggressive and triggers six refinement events across the four bucket runs, reducing throughput, while ℎ = 8 is too conservative and triggers no refinement

Offline ranking. The offline profiles show that no single parameter determines the best strategy: top choices vary across buckets and precision classes, with profiling-set gains ranging from 4.0% to 33.5% over the fixed baseline. On heldout prompts, Static-best improves throughput by 10.6% over Base on average, indicating that complete strategy tuples transfer beyond the profiling set. The remaining variation is prompt-specific: some rows, such as 0–4K Strict, expose a mismatch between the profiled top choice and the held-out prompt behavior, while small-gain rows such as 8–12K Strict and 8–12K Approx-only occur because the fixed baseline is already strong. These results support the need for runtime refinement on top of offline ranking. 12

SSV : Sparse Speculative Verification for Efficient LLM Inference

Table 4. Refinement sensitivity on the deployment profile used for validation. Refinement Events counts total refinement events across four bucket runs; each run allows at most two refinements. Setting

Throughput

Gain/Base

Default 𝛼 = 0.20 𝛼 = 0.60 𝜌 = 0.80 𝜌 = 0.90 𝑚 =4 𝑚 = 16 ℎ =3 ℎ =8

209.7 207.3 209.0 209.6 207.8 209.5 209.0 197.9 199.1

+26.6% +25.2% +26.1% +26.6% +25.4% +26.4% +26.1% +18.8% +21.0%

[8] Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. 2018. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv:1803.05457 (2018). [9] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press. [10] Tri Dao. 2023. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691 (2023). [11] Dhruv Deshmukh, Saurabh Goyal, Nipun Kwatra, and Ramachandran Ramjee. 2025. Kascade: A Practical Sparse Attention Method for LongContext LLM Inference. arXiv preprint arXiv:2512.16391 (2025). [12] Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Alain Le Noac’h, Haonan Li, Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. 2024. The Language Model Evaluation Harness. doi:10.5281/zenodo.12608602 [13] Yizhao Gao, Jianyu Wei, Qihao Zhang, Yu Cheng, Shimao Chen, Zhengju Tang, Zihan Jiang, Yifan Song, Hailin Zhang, Liang Zhao, et al. 2026. HySparse: A Hybrid Sparse Attention Architecture with Oracle Token Selection and KV Cache Sharing. arXiv preprint arXiv:2602.03560 (2026). [14] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Ankush Kadian, Amal Al-Dahle, Aiesha Letman, Anukriti Mathur, Ashwin Schelten, Angela Yang, et al. 2024. The Llama 3 Herd of Models. arXiv preprint arXiv:2407.21783 (2024). [15] Ankit Gupta, Guy Dar, Shaya Goodman, David Ciprut, and Jonathan Berant. 2021. Memory-efficient Transformers via Top-𝑘 Attention. arXiv preprint arXiv:2106.06899 (2021). [16] Dhiraj Kalamkar, Dheevatsa Mudigere, Naveen Mellempudi, Dipankar Das, Kunal Banerjee, Sasikanth Avancha, Dharma Teja Vooturi, Nataraj Jammalamadaka, Jianyu Huang, Hector Yuen, et al. 2019. A study of BFLOAT16 for deep learning training. arXiv preprint arXiv:1905.12322 (2019). [17] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium on operating systems principles. 611–626. [18] Xunhao Lai. 2025. native-sparse-attention-triton. https://github.com/ XunhaoLai/native-sparse-attention-triton. [19] Xunhao Lai, Jianqiao Lu, Yao Luo, Yiyuan Ma, and Xun Zhou. 2025. Flexprefill: A context-aware sparse attention mechanism for efficient long-sequence inference. arXiv preprint arXiv:2502.20766 (2025). [20] Yaniv Leviathan, Matan Kalman, and Yossi Matias. 2023. Fast Inference from Transformers via Speculative Decoding. In Proceedings of the 40th International Conference on Machine Learning. 19274–19286. [21] Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. 2024. Eagle: Speculative sampling requires rethinking feature uncertainty. arXiv preprint arXiv:2401.15077 (2024). [22] Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. 2025. Eagle-3: Scaling up inference acceleration of large language models via training-time test. arXiv preprint arXiv:2503.01840 (2025). [23] Aixin Liu, Aoxue Mei, Bangcai Lin, Bing Xue, Bingxuan Wang, Bingzheng Xu, Bochao Wu, Bowei Zhang, Chaofan Lin, Chen Dong, et al. 2025. Deepseek-v3. 2: Pushing the frontier of open large language models. arXiv preprint arXiv:2512.02556 (2025). [24] Meta. 2024. Llama-3.1-8B-Instruct. https://huggingface.co/metallama/Llama-3.1-8B-Instruct Accessed: 2026-05-13. [25] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, Chunan Shi, Zhuoming Chen, Daiyaan Arfeen, Reyna

Refinement Events 1 2 1 1 1 1 1 6 0

events, missing useful corrections. The default ℎ = 5 triggers one refinement event and achieves the overall tradeoff.

Conclusion

In this paper, we present SSV, a sparse verification framework to bridge the gap between dynamic sparse attention and speculative decoding. SSV uses cross-query coarsening and verification-oriented kernel fusion to reduce duplicated KV-block loads and fragmented branch execution, while profile-guided planning adapts the draft-verification strategy to input-dependent acceptance and kernel behavior. Experiments on H100 GPUs with Llama-based NSA models show that SSV substantially improves end-to-end generation throughput, achieving up to 3.49× speedup in our EAGLE-3 integration study.

References [1] Joshua Ainslie, James Lee-Thorp, Michiel De Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. 2023. Gqa: Training generalized multi-query transformer models from multi-head checkpoints. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 4895–4901. [2] ajibawa 2023. 2023. Children Stories Collection. doi:10.57967/hf/2480 [3] Yushi Bai, Qian Dong, Ting Jiang, Xin Lv, Zhengxiao Du, Aohan Zeng, Jie Tang, and Juanzi Li. 2026. IndexCache: Accelerating Sparse Attention via Cross-Layer Index Reuse. arXiv preprint arXiv:2603.12201 (2026). [4] Iz Beltagy, Matthew E Peters, and Arman Cohan. 2020. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150 (2020). [5] Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. 2020. Piqa: Reasoning about physical commonsense in natural language. In Proceedings of the AAAI conference on artificial intelligence, Vol. 34. 7432–7439. [6] Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D Lee, Deming Chen, and Tri Dao. 2024. Medusa: Simple llm inference acceleration framework with multiple decoding heads. arXiv preprint arXiv:2401.10774 (2024). [7] Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. 2023. Accelerating Large Language Model Decoding with Speculative Sampling. arXiv preprint arXiv:2302.01318 (2023). 13

Wang et al.

Abhyankar, and Zhihao Jia. 2024. SpecInfer: Accelerating Large Language Model Serving with Tree-based Speculative Inference and Verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3. 932–949. [26] Sanjit Neelam, Vaclav Cvicek, Daniel Heinlein, Akshay Mishra, Mahdi Nazemi, and Gilbert Hendry. 2025. Speculative Decoding with Blockwise Sparse Attention. MatX Research. https://matx.com/research/ sd_nsa Accessed: 2026-04-26. [27] NVIDIA Corporation. 2024. NVIDIA H100 Tensor Core GPU. https: //www.nvidia.com/en-us/data-center/h100/. Accessed: 2026-04-26. [28] PyTorch Contributors. 2025. torch.cuda.Event. https://docs.pytorch. org/docs/2.11/generated/torch.cuda.Event.html. PyTorch 2.11 documentation. Accessed: 2026-05-09. [29] Philippe Tillet, Hsiang-Tsung Kung, and David Cox. 2019. Triton: an intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages. 10–19. [30] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems 30 (2017). [31] W Hwu Wen-Mei, David B Kirk, and Izzat El Hajj. 2026. Programming massively parallel processors: a hands-on approach. Morgan Kaufmann.

[32] Ran Yan, Youhe Jiang, and Binhang Yuan. 2025. Flash sparse attention: An alternative efficient implementation of native sparse attention kernel. arXiv e-prints (2025), arXiv–2508. [33] Jingyang Yuan, Huazuo Gao, Damai Dai, Junyu Luo, Liang Zhao, Zhengyan Zhang, Zhenda Xie, Yuxing Wei, Lean Wang, Zhiping Xiao, et al. 2025. Native sparse attention: Hardware-aligned and natively trainable sparse attention. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 23078–23097. [34] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. 2020. Big bird: Transformers for longer sequences. Advances in neural information processing systems 33 (2020), 17283–17297. [35] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. 2019. Hellaswag: Can a machine really finish your sentence?. In Proceedings of the 57th annual meeting of the association for computational linguistics. 4791–4800. [36] zen-E. 2025. NSA-1B. https://huggingface.co/zen-E/NSA-1B. Accessed: 2026-05-05. [37] zhenyi4. 2025. SSA. https://github.com/zhenyi4/ssa. Accessed: 202605-05.

SSV: Sparse Speculative Verification for Efficient LLM Inference

Related documents