Skip to content

nosa native and offloadable sparse attention

content_hash: c20753a96bf036e7 ---# NOSA: Native and Offloadable Sparse Attention

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/thunlp/NOSA
Area: Model Compression
Keywords: Sparse Attention, KV Cache Offloading, Locality Constraint, Algorithm-System Co-Design, Long-Context Inference

TL;DR

Addressing the severe training-inference mismatch of training-free KV offloading and the communication-bound PCIe bottleneck of unconstrained trainable sparse attention, NOSA introduces a natively offloadable sparse attention mechanism with a theoretical locality lower bound alongside a co-designed inference system NOSI, achieving up to 5.04× decoding throughput speedup while maintaining lossless long-generation quality.

Background & Motivation

Serving large language models (LLMs) on long-context inputs and ultra-long generative tasks—such as multi-step complex reasoning and autonomous agent rollouts—is fundamentally constrained by memory capacity and bandwidth during decoding. Increasing inference batch size is the primary lever to boost decoding throughput, yet GPU high-bandwidth memory (HBM) is rapidly exhausted by the linear expansion of key-value (KV) caches. To mitigate this memory wall, training-free KV cache offloading methods (e.g., InfLLM, ShadowKV) keep the majority of KV caches in host CPU DRAM and transfer only a sparse subset over the PCIe bus to GPU HBM on demand. However, selecting sparse blocks using training-free heuristics introduces an acute distribution mismatch between training and inference; because these sparse activation patterns are never exposed during optimization, approximation errors compound rapidly across multi-token generation, culminating in catastrophic perplexity explosion and repetitive generation collapse.

Conversely, emerging trainable sparse attention mechanisms (such as NSA and InfLLMv2) successfully bridge the training-inference gap via continual pre-training, achieving near-lossless retrieval and generation capabilities. Nonetheless, these methods treat attention sparsity purely from an algorithmic standpoint and disregard the physical constraints of hardware memory hierarchies. In standard trainable sparse attention, any query token is permitted to freely retrieve arbitrary KV entries across consecutive decoding steps, yielding weak temporal and spatial locality. When deployed in KV offloading systems, such unconstrained access patterns trigger constant, fine-grained host-to-device transfers that completely saturate the PCIe bus, causing the system to become severely communication-bound—with over 80% of total decoding time wasted waiting on attention transfers.

Faced with the core dilemma between quality degradation in training-free offloading and PCIe communication bottlenecks in unconstrained trainable sparse attention, this paper proposes to incorporate hardware memory transfer constraints directly into the algorithmic design and pre-training stages. Core idea: by decomposing block selection into query-aware retrieval and query-agnostic eviction components, NOSA establishes an explicit theoretical lower bound on step-to-step KV reuse locality (\(\gamma(t) \ge \frac{k_e}{k}\)) during continual pre-training, and pairs this with a co-designed inference engine NOSI to eliminate PCIe communication bottlenecks and deliver high-throughput, near-lossless long-sequence decoding.

Method

Overall Architecture

NOSA centers on actively inducing and enforcing KV cache access locality during model training, maintaining high attention representational capacity while strictly bounding the volume of data fetched across the PCIe bus per decoding step. Given an input sequence, NOSA organizes the KV cache into fixed-size blocks and selects an active attention context budget of \(k\) tokens (equivalent to \(k/n_b\) blocks). The pipeline integrates a query-aware branch for dynamic associative recall and a query-agnostic branch with an eviction head that ensures cache retention, coupled with attention bias gradient backpropagation. At the system level, the NOSI inference engine eliminates framework overheads through specialized memory layouts, fused CUDA kernels, and unified virtual memory addressing.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Hidden States H and Linear Weights"] --> B["Fused Projection and Scoring<br/>Decoupled Q, K, V & eviction importance scores"]
    B --> C["Hierarchical Pooling & Dual-Path Selection<br/>Query-aware retrieval + Exp-Delayed eviction head"]
    C --> D["Explicit Locality Lower Bound Guarantee<br/>Theoretically bounded step-to-step cache hit rate"]
    D --> E["Set-Difference Replacement & UVA Transfer<br/>NOSI kernel resolves mapping & accelerates PCIe I/O"]
    E --> F["Sparse FlashAttention Decoding Output"]

Key Designs

1. Fused Projection and Scoring: Decoupled Q, K, V and Importance Score Generation

To overcome the severe host-to-device transfer fragmentation and low PCIe bandwidth utilization caused by element-wise token sparsity, NOSA adopts a block-wise structure and computes query-agnostic importance scores via a dedicated eviction head. At each decoding step, hidden states are linearly projected into \(Q, K, V\), while a lightweight eviction head calculates scalar importance scores \(s_j^e = \tau(v_j W_1) W_2\) for each position, where \(W_1 \in \mathbb{R}^{d_{kv} \times n_{kv}}, W_2 \in \mathbb{R}^{n_{kv} \times 1}\) are learnable parameters and \(\tau\) denotes the Softplus non-linear activation. To eliminate the overhead of launching separate lightweight kernels, NOSA fuses the \(Q, K, V\) splitting and importance score calculation into a single unified Triton kernel, minimizing kernel dispatch latency.

2. Hierarchical Pooling and Dual-Path Selection: Query-Aware Retrieval and Exp-Delayed Eviction

To evaluate block-level significance efficiently, NOSA employs a two-stage hierarchical pooling scheme. For each block of \(n_b\) tokens, mean pooling is first executed over sub-blocks using stride \(l_{stride}\) and kernel size \(l_{kernel}\), followed by block-level max pooling to obtain query-aware scores \(s_{i[j]}^q\) and query-agnostic scores \(s_{[j]}^e\). In block allocation, the total budget is partitioned into query-aware budget \(k_q\) and query-agnostic budget \(k_e\) (\(k = k_q + k_e\)). The top \(k_q/n_b\) blocks matching the query are selected first via \(s_{i[j]}^q\) and assigned score \(+\infty\); subsequently, the remaining \(k_e/n_b\) blocks are chosen based on \(s_{[j]}^e\). Addressing the high numerical sensitivity of exponential transformations, NOSA introduces Exp-Delayed DMA (ED-DMA): candidate blocks are ranked strictly on pre-exponential scores \(s_{[j]}^e\), while the attention bias \(b_j = s_j^e\) is injected only during the final attention computation:

\[o_t = \sum_{j=1}^t \frac{\exp(q_t k_j^\top + m_j + b_j)}{\sum_{l=1}^t \exp(q_t k_l^\top + m_l + b_l)} v_j\]

3. Explicit Locality Lower Bound Guarantee: Bounding Step-to-Step KV Cache Hit Rate

Because the query-agnostic eviction head operates with an intrinsic monotonic discard property—a KV block not retained by the query-agnostic policy at step \(t\) cannot reappear via query-agnostic selection at subsequent steps unless recalled by the query-aware branch—NOSA establishes a rigorous mathematical guarantee on cache overlap. In Theorem 3.1, the authors prove that for any decoding step \(t\) with budget \(k = k_q + k_e\), the locality ratio \(\gamma(t)\) between selected token sets \(\Gamma(t-1)\) and \(\Gamma(t)\) satisfies:

\[\forall t \in \{2, \cdots, n\}, \quad \gamma(t) = \frac{|\Gamma(t) \cap \Gamma(t-1)|}{|\Gamma(t)|} \ge \frac{k_e}{k} = 1 - \frac{k_q}{k}\]

Under default configurations (\(k=4096, k_q=1024\)), query-agnostic selections constitute 75% of the active cache. Even ignoring the static residence of attention sinks and local sliding windows, at least 75% of active KV blocks are guaranteed to remain resident on the GPU across consecutive steps, strictly capping newly fetched blocks below 25% and dismantling the PCIe bandwidth wall.

4. Set-Difference Replacement and UVA Transfer: System-Level Optimizations in NOSI

To realize these algorithmic gains in physical hardware throughput, the authors build the specialized inference system NOSI. In vanilla PyTorch implementations, dynamic memory allocation and intermediate tensor shuffling conceal the underlying communication cost. NOSI implements three key optimizations: first, a custom CUDA kernel solves the set-difference mapping between consecutive step indices in \(O(k)\) per thread, utilizing shared memory to generate replacement positions; second, host-to-device transfers utilize a tailored Triton kernel with Unified Virtual Addressing (UVA) to directly read pinned host memory, eliminating PyTorch buffer overheads; third, CUDA Graphs capture operations from pooling through index selection, mitigating runtime CPU launch bottlenecks.

Loss & Training

NOSA integrates into standard long-context adaptation pipelines without auxiliary losses. Pre-trained base models (4K context) undergo continual pre-training (CPT) with NOSA attention, where the context window is extended to 16K using LongRoPE. Training runs on approximately 5B tokens from the InfLLMv2-data-5B corpus with AdamW and WSD learning rate schedules, followed by supervised fine-tuning (SFT). Gradients flow back from the attention bias \(b_j\) directly into the eviction head parameters, ensuring end-to-end co-adaptation.

Key Experimental Results

Main Results

On 8B models evaluated on long-context benchmarks, NOSA is compared against full attention (FULLATTN), training-free offloading baselines (SHADOWKV, INFLLM, ARKVALE), and trainable baselines (INFLLMV2, DMA) across LongBench and HELMET (16K context) under both Full Prefill and Sparse Prefill settings:

Method Prefill Setting LongBench (Avg. ↑) HELMET (Avg. ↑) HELMET Recall (%)
FULLATTN Full 43.9 42.6 ± 0.3 89.5 ± 0.3
SHADKV8 Full 43.3 38.8 ± 0.6 78.3 ± 0.4
SHADKV64 Full 42.9 33.5 ± 0.3 55.3 ± 0.2
ARKVALE Full 39.5 36.2 ± 0.4 56.2 ± 1.5
DMA-F Full 40.1 31.2 ± 0.5 33.1 ± 0.2
NOSA-F (Ours) Full 43.7 40.4 ± 0.5 86.3 ± 0.0
INFLLMV2 Sparse 44.3 40.3 ± 0.3 72.7 ± 0.2
SHADKVM8 Sparse 41.1 36.5 ± 0.4 74.6 ± 0.2
SHADKVM64 Sparse 41.1 32.3 ± 0.4 54.5 ± 0.9
INFLLM64 Sparse 41.0 16.4 ± 0.7 5.5 ± 0.5
DMA-S Sparse 35.9 26.3 ± 0.3 22.7 ± 0.7
NOSA-S (Ours) Sparse 43.3 37.6 ± 0.7 67.2 ± 0.8

In terms of real decoding throughput (tokens/s) on an 8B model with 16K input context under varied Equivalent Batch Sizes (EB), NOSA paired with NOSI achieves dramatic speedups:

Method Implementation Offloading EB: 16 EB: 32 EB: 64 EB: 128
FULLATTN vLLM ✗ 233.21 (4) 417.99 (8) 678.41 (16) 927.99 (32)
FULLATTN SGLang ✗ 180.28 (4) 358.56 (8) 774.74 (16) 1267.20 (32)
INFLLMV2 NOSI ✗ 226.51 (4) 440.76 (8) 824.09 (16) 1475.43 (32)
INFLLMV2 NOSI ✓ 563.88 (16) 759.35 (32) 1389.40 (64) 1441.32 (128)
SHADOWKV SHADKV ✓ 585.92 (16) 769.84 (32) 970.19 (64) 1071.36 (128)
NOSA NOSI ✓ 743.18 (16) 1056.27 (32) 1630.80 (64) 1961.17 (128)

Ablation Study

Ablations on the eviction head formulation on a 1B model evaluated on the 16K context RULER benchmark:

Implementation Variant Scoring / Mechanism Detail RULER Average Accuracy (%) Note
INFLLMV2 Query-aware sparse baseline without eviction head 60.3 Upper bound reference
LOCRET Trainable MLP predictor \(s_j^e = \text{MLP}(h_j)\) 55.9 Notable drop on multi-key retrieval
DMA Vanilla DMA (applying \(\exp(b_j)\) before selection) 56.2 Significant degradation due to precision loss
S-DMA Straight-Through gradient without explicit bias 60.9 Matches dense baseline but lacks bias filtering
ED-DMA (NOSA) Exp-Delayed DMA (selection on pre-exp logits) 61.9 Best performance, surpassing InfLLMv2

Key Findings

  • Robust Long-Range Retrieval: On the challenging HELMET Recall benchmark, training-free methods suffer dramatic declines (SHADKV64 down to 55.3%, DMA-F down to 33.1%), whereas NOSA-F maintains 86.3% accuracy, closely matching Full Attention (89.5%).
  • Stability in Long Reasoning Generation: On multi-step mathematical and scientific reasoning benchmarks (MATH-500, Gaokao) requiring 8K token outputs, SHADOWKV suffers acute perplexity explosion with scores dropping to 12.5%; NOSA preserves stable low perplexity, achieving 49.6% (comparable to FULLATTN's 51.6%).
  • Realized Bandwidth Decoupling: In controlled experiments at equal batch size (B=16), enabling offloading causes INFLLMV2 throughput to drop by 31.6% (from 824.09 to 563.16 tok/s), whereas NOSA experiences only a 9.1% drop (817.16 to 743.18 tok/s) and scales up to 1961.17 tok/s at batch size 128.

Highlights & Insights

  • Internalizing System Bottlenecks into Algorithm Design: Rather than treating offloading purely as post-training system engineering, NOSA shows that enforcing PCIe transfer locality during continual pre-training provides mathematical guarantees (\(\gamma(t) \ge k_e / k\)) that eliminate communication saturation.
  • Exp-Delayed DMA (ED-DMA) Insight: Uncovering that numerical precision degradation from the exponential operator severely corrupts discrete top-k rankings leads to a simple, highly effective fix—ranking pre-exponential logits yields an immediate +5.7% accuracy boost.
  • Hardware-Aware Co-Design via NOSI: Constructing a dedicated inference engine removes framework-induced masking of communication costs, allowing UVA-based block streaming and fused kernels to realize the theoretical speedup in actual wall-clock time.

Limitations & Future Work

  • Model Size and Architecture Scope: Validated primarily on 1B to 8B parameter models; evaluation on 70B+ scale, Mixture-of-Experts (MoE) architectures, and multimodal foundation models remains open for future exploration.
  • Integration with Distributed Serving Frameworks: Current peak throughput requires the standalone NOSI engine; porting its fused CUDA/Triton kernels and memory management into production frameworks such as vLLM or SGLang requires non-trivial engineering effort.
  • Extrapolation Hyperparameter Tuning: Generalizing beyond trained sequence lengths (e.g., 64K+) requires manually tuning RoPE \(\theta\) and budget parameter \(k\); adaptive dynamic budget allocation represents a promising future enhancement.
  • vs. ShadowKV: ShadowKV is a training-free offloading system relying on SVD decomposition of K and on-demand V offloading, but suffers from cumulative approximation drift in long-generation tasks; NOSA eliminates distribution mismatch via native training and bounded locality.
  • vs. InfLLMv2 / NSA: While InfLLMv2 provides high representational power via trainable block-sparse attention, its unconstrained access triggers frequent PCIe memory swaps; NOSA partitions budgets to enforce strict cache reuse bounds without sacrificing quality.
  • vs. DMA / Locret: DMA applies element-wise query-agnostic eviction that cannot recover dropped tokens and severely fragments PCIe memory access; NOSA combines block-wise structure with dual-path query-aware recovery and ED-DMA refinement.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Formulates the first natively offloadable sparse attention with a theoretical locality lower bound enforced during training.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive evaluations across 1B/3B/8B scales, LongBench, HELMET, long reasoning tasks, NUMA topologies, and H100 GPU benchmarks.
  • Writing Quality: ⭐⭐⭐⭐⭐ Rigorous theoretical proofs, insightful hardware-software co-design analysis, and clear exposition.
  • Value: ⭐⭐⭐⭐⭐ Highly practical paradigm for scaling throughput in memory-constrained long-context LLM serving.