# Loki: Low-rank Keys for Efficient Sparse Attention

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

## Key facts

- Cited by 89 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 35 references that are in the map.
- First posted on arXiv 4 Jun 2024.

## Builds on (most cited first, 25 of 25)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference](https://mlsanity.com/paper/1712.05877/) (2017)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [TinyLlama: An Open-Source Small Language Model](https://mlsanity.com/paper/2401.02385/) (2024)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [A White Paper on Neural Network Quantization](https://mlsanity.com/paper/2106.08295/) (2021)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [ZeroQuant-V2: Exploring Post-training Quantization in LLMs from Comprehensive Study to Low Rank Compensation](https://mlsanity.com/paper/2303.08302/) (2023)
- [Memory-efficient Transformers via Top-k Attention](https://mlsanity.com/paper/2106.06899/) (2021)
- [Sparse Attention with Linear Units](https://mlsanity.com/paper/2104.07012/) (2021)
- [AxoNN: An asynchronous, message-driven parallel framework for extreme-scale deep learning](https://mlsanity.com/paper/2110.13005/) (2021)
- [A 4D Hybrid Algorithm to Scale Parallel Training to Thousands of GPUs](https://mlsanity.com/paper/2305.13525/) (2023)

## Built on by (most cited first, 30 of 89)

- [ShadowKV: KV Cache in Shadows for High-Throughput Long-Context LLM Inference](https://mlsanity.com/paper/2410.21465/) (2024)
- [A Survey on Large Language Model Acceleration based on KV Cache Management](https://mlsanity.com/paper/2412.19442/) (2024)
- [RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval](https://mlsanity.com/paper/2409.10516/) (2024)
- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [MagicDec: Breaking the Latency-Throughput Tradeoff for Long Context Generation with Speculative Decoding](https://mlsanity.com/paper/2408.11049/) (2024)
- [ThinK: Thinner Key Cache by Query-Driven Pruning](https://mlsanity.com/paper/2407.21018/) (2024)
- [RocketKV: Accelerating Long-Context LLM Inference via Two-Stage KV Cache Compression](https://mlsanity.com/paper/2502.14051/) (2025)
- [Tensor Product Attention Is All You Need](https://mlsanity.com/paper/2501.06425/) (2025)
- [HashAttention: Semantic Sparsity for Faster Inference](https://mlsanity.com/paper/2412.14468/) (2024)
- [SCOPE: Optimizing Key-Value Cache Compression in Long-context Generation](https://mlsanity.com/paper/2412.13649/) (2024)
- [Lattice: Learning to Efficiently Compress the Memory](https://mlsanity.com/paper/2504.05646/) (2025)
- [Lexico: Extreme KV Cache Compression via Sparse Coding over Universal Dictionaries](https://mlsanity.com/paper/2412.08890/) (2024)
- [Past- and Future-Informed KV Cache Policy with Salience Estimation in Autoregressive Video Diffusion](https://mlsanity.com/paper/2601.21896/) (2026)
- [Learning to Evict from Key-Value Cache](https://mlsanity.com/paper/2602.10238/) (2026)
- [BLASST: Dynamic BLocked Attention Sparsity via Softmax Thresholding](https://mlsanity.com/paper/2512.12087/) (2025)
- [LoLA: Low-Rank Linear Attention With Sparse Caching](https://mlsanity.com/paper/2505.23666/) (2025)
- [SALS: Sparse Attention in Latent Space for KV cache Compression](https://mlsanity.com/paper/2510.24273/) (2025)
- [Router-Tuning: A Simple and Effective Approach for Enabling Dynamic-Depth in Transformers](https://mlsanity.com/paper/2410.13184/) (2024)
- [Hardware-Efficient Attention for Fast Decoding](https://mlsanity.com/paper/2505.21487/) (2025)
- [KQ-SVD: Compressing the KV Cache with Provable Guarantees on Attention Fidelity](https://mlsanity.com/paper/2512.05916/) (2025)
- [Kascade: A Practical Sparse Attention Method for Long-Context LLM Inference](https://mlsanity.com/paper/2512.16391/) (2025)
- [SpeCache: Speculative Key-Value Caching for Efficient Generation of LLMs](https://mlsanity.com/paper/2503.16163/) (2025)
- [FASA: Frequency-aware Sparse Attention](https://mlsanity.com/paper/2602.03152/) (2026)
- [Value-Aware Stochastic KV Cache Eviction for Reasoning Models](https://mlsanity.com/paper/2606.03928/) (2026)
- [A2ATS: Retrieval-Based KV Cache Reduction via Windowed Rotary Position Embedding and Query-Aware Vector Quantization](https://mlsanity.com/paper/2502.12665/) (2025)
- [Mustafar: Promoting Unstructured Sparsity for KV Cache Pruning in LLM Inference](https://mlsanity.com/paper/2505.22913/) (2025)
- [HATA: Trainable and Hardware-Efficient Hash-Aware Top-k Attention for Scalable Large Model Inference](https://mlsanity.com/paper/2506.02572/) (2025)
- [SVDq: 1.25-bit and 410x Key Cache Compression for LLM Attention](https://mlsanity.com/paper/2502.15304/) (2025)
- [GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction](https://mlsanity.com/paper/2509.00388/) (2025)
- [vAttention: Verified Sparse Attention](https://mlsanity.com/paper/2510.05688/) (2025)

## Abstract (arXiv)

Inference on large language models (LLMs) can be expensive in terms of the compute and memory costs involved, especially when long sequence lengths are used. In particular, the self-attention mechanism used in LLM inference contributes significantly to these costs, which has sparked an interest in approximating the self-attention computation to reduce such costs. In this work, we propose to approximate self-attention by focusing on the dimensionality of key vectors computed in the attention block. Our analysis reveals that key vectors lie in a significantly lower-dimensional space, consistently across several datasets and models. Exploiting this observation, we propose Loki, a novel sparse attention method that ranks and selects tokens in the KV-cache based on attention scores computed in low-dimensional space. Our evaluations show that Loki is able to speed up the attention computation due to reduced data movement (load/store) and compute costs while maintaining the efficacy of the models better than other popular approximation methods.