# FSA: An Alternative Efficient Implementation of Native Sparse Attention Kernel

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 41 references that are in the map.
- First posted on arXiv 25 Aug 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Yi: Open Foundation Models by 01.AI](https://mlsanity.com/paper/2403.04652/) (2024)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://mlsanity.com/paper/2502.11089/) (2025)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads](https://mlsanity.com/paper/2410.10819/) (2024)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [MoBA: Mixture of Block Attention for Long-Context LLMs](https://mlsanity.com/paper/2502.13189/) (2025)
- [InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memory](https://mlsanity.com/paper/2402.04617/) (2024)
- [Online normalizer calculation for softmax](https://mlsanity.com/paper/1805.02867/) (2018)
- [SageAttention: Accurate 8-Bit Attention for Plug-and-play Inference Acceleration](https://mlsanity.com/paper/2410.02367/) (2024)
- [XAttention: Block Sparse Attention with Antidiagonal Scoring](https://mlsanity.com/paper/2503.16428/) (2025)
- [FlexPrefill: A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inference](https://mlsanity.com/paper/2502.20766/) (2025)
- [SageAttention2: Efficient Attention with Thorough Outlier Smoothing and Per-thread INT4 Quantization](https://mlsanity.com/paper/2411.10958/) (2024)
- [Beyond the Limits: A Survey of Techniques to Extend the Context Length in Large Language Models](https://mlsanity.com/paper/2402.02244/) (2024)
- [SageAttention3: Microscaling FP4 Attention for Inference and An Exploration of 8-Bit Training](https://mlsanity.com/paper/2505.11594/) (2025)
- [Explicit Sparse Transformer: Concentrated Attention Through Explicit Selection](https://mlsanity.com/paper/1912.11637/) (2019)
- [SampleAttention: Near-Lossless Acceleration of Long Context LLM Inference with Adaptive Structured Sparse Attention](https://mlsanity.com/paper/2406.15486/) (2024)
- [HexGen: Generative Inference of Large Language Model over Heterogeneous Environment](https://mlsanity.com/paper/2311.11514/) (2023)
- [Star Attention: Efficient LLM Inference over Long Sequences](https://mlsanity.com/paper/2411.17116/) (2024)
- [HexGen-2: Disaggregated Generative Inference of LLMs in Heterogeneous Environment](https://mlsanity.com/paper/2502.07903/) (2025)
- [From 128K to 4M: Efficient Training of Ultra-Long Context Large Language Models](https://mlsanity.com/paper/2504.06214/) (2025)

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

- [NOSA: Native and Offloadable Sparse Attention](https://mlsanity.com/paper/2510.13602/) (2025)
- [OServe: Accelerating LLM Serving via Spatial-Temporal Workload Orchestration](https://mlsanity.com/paper/2602.12151/) (2026)
- [Rethinking Data Curation in LLM Training: Online Reweighting Offers Better Generalization than Offline Methods](https://mlsanity.com/paper/2605.05227/) (2026)
- [Power-based Partial Attention: Bridging Linear-Complexity and Full Attention](https://mlsanity.com/paper/2601.17334/) (2026)
- [Superlinear Multi-Step Attention](https://mlsanity.com/paper/2601.18401/) (2026)
- [HexAGenT: Efficient Agentic LLM Serving via Workflow- and Heterogeneity-Aware Scheduling](https://mlsanity.com/paper/2605.16637/) (2026)
- [Beyond Memory Leaderboards: Evaluating Scientific Memory as Budgeted Context Restoration](https://mlsanity.com/paper/2607.16848/) (2026)

## Abstract (arXiv)

Recent advances in sparse attention mechanisms have demonstrated strong potential for reducing the computational cost of long-context training and inference in large language models (LLMs). Native Sparse Attention (NSA), one state-of-the-art approach, introduces natively trainable, hardware-aligned sparse attention that delivers substantial system-level performance boosts while maintaining accuracy comparable to full attention. However, the kernel implementation of NSA forces a loop order that is only efficient with a relatively large number of query heads in each Grouped Query Attention (GQA) group, whereas existing LLMs widely adopt a much smaller number of query heads in each GQA group -- such an inconsistency significantly limits the applicability of this sparse algorithmic advance. In this work, we propose Flash Sparse Attention (FSA), an alternative kernel implementation that enables efficient NSA computation across a wide range of popular LLMs with a varied, smaller number of heads in each GQA group on modern GPUs. Compared to vanilla NSA kernel implementation, our empirical evaluation demonstrates that FSA achieves (i) up to 3.5x and on average 1.6x kernel-level latency reduction, (ii) up to 1.25x and 1.09x on average end-to-end training speedup on state-of-the-art LLMs, and (iii) up to 1.36x and 1.11x on average for prefill-phase speedup in LLM generative inference. The source code is open-sourced and publicly available at https://github.com/Relaxed-System-Lab/Flash-Sparse-Attention.