FASA: Frequency-aware Sparse Attention

AI summary

Overview

Research area: Efficient large language model inference, specifically KV cache compression and sparse attention for long-context decoding. Technical level: Advanced (requires familiarity with transformer attention, rotary positional embeddings, and KV cache mechanics). Scope: The paper introduces FASA, a training-free token-eviction framework that uses frequency-chunk structure inside RoPE to predict which context tokens matter for the current query.

What This Paper Is About

Long inputs make the Key-Value (KV) cache in LLMs grow linearly, and every generated token must read that cache from memory, creating a memory-bandwidth bottleneck. Existing token-eviction methods either drop tokens by fixed rules (risking irreversible information loss) or rank tokens with heuristics that ignore the query-dependent nature of importance. FASA addresses this by identifying a small set of RoPE "frequency chunks" that carry contextual information and using them as a free, query-aware proxy for token importance.

Key Contributions

1. The paper reports the first discovery of functional sparsity at the frequency-chunk (FC) level induced by RoPE: a small subset of "dominant" FCs consistently carries the contextual selection behavior of a full attention head.
2. It introduces FASA, a training-free framework that dynamically predicts token importance during decoding by aggregating scores from only the pre-calibrated dominant FCs, then performs full-fidelity attention on the retained token subset.
3. It presents two hardware-aware variants: FASA-M (memory-optimized, offloading the value cache and non-dominant key components to CPU memory) and FASA-C (computation-optimized, keeping the full cache on GPU but accessing only a sparse subset of key states), which the paper reports achieve equivalent downstream task performance with different efficiency profiles.
4. It evaluates FASA on long-context understanding, long-sequence modeling, and long chain-of-thought (LongCoT) reasoning across Llama, Mistral, and Qwen models, reporting near-oracle accuracy and consistent gains over Stream, SnapKV, RKV, Quest, and H2O.

Main Findings

• Functional sparsity is sparse, universal, and task-invariant: Dominant FCs account for less than 1% of all FCs, while non-dominant FCs with low Contextual Agreement scores make up approximately 90% or more; low-scoring FCs typically have CA below 0.15. The overlap of dominant FCs across different calibration datasets consistently exceeds 70% in all tested models, and the pattern appears across model architectures and scales.
• Dominant FCs approximate full attention cheaply: Using only 1/8 of the components (F = 8) at a budget of 64 tokens yields a compound CA score of 43.0, which the paper says surpasses the strong baseline SnapKV by an average of 10.3% across all budget levels. At F = 16 (1/4 of FCs), scores rise from 55.3 at budget 64 to 81.4 at budget 2048, versus SnapKV's 37.9 to 66.6.
• Long-context performance near the full-cache ceiling: On LongBench-V1 with only 256 tokens retained and 25% of FCs, FASA averages 41.5 on Llama3.2-3B versus 42.2 for the full-KV baseline (FKV), 47.9 versus 47.8 on Qwen2.5-7B, 47.8 versus 47.4 on Mistral-7B-v0.3, 48.2 versus 48.7 on Llama3.1-8B, and 49.2 versus 50.3 on Qwen2.5-14B-1M. The paper reports an overall reduction of less than 0.7% relative to full KV cache and says FASA reaches nearly 100% of full-KV performance when only keeping 256 tokens.
• FASA occasionally beats the full cache: Under extreme budgets it sometimes surpasses FKV (for example, on Mistral-7B), which the authors attribute to reduced distraction from irrelevant tokens; the Oracle upper bound also sometimes outperforms FKV, supporting this explanation.
• Baselines degrade sharply: Quest's accuracy drops by 13.4% on NarrativeQA. On LongBench-V1 with a 256-token budget, Quest averages 25.5 and Stream 31.8 on Llama3.2-3B, versus 41.5 for FASA and 42.2 for FKV.
• Long-CoT reasoning is preserved: On paper reports that on the R1-Llama model SnapKV's accuracy collapses to 21.6 on MATH500, against 72.4 for FKV, while FASA reaches 86.4 at its smallest reported budget of 300 tokens on DeepSeek-R1-Distill-Qwen-32B, narrowly trailing the 92.6 FKV upper bound on that model.
• Concrete efficiency numbers: On LongBench-V1, FASA reaches nearly 100% of full-KV performance keeping only 256 tokens, and the paper reports a 2.56× speedup using just 18.9% of the cache on AIME24. FASA-M gives 8× KV cache compression; FASA-C delivers 2.6× speedups with 25% of FCs selected.
• Decoding dominates latency: Decoding constitutes 90% of total latency at a 32K context, which motivates reducing memory traffic rather than only FLOPs.
• Output length is preserved: FASA keeps output lengths nearly identical to FKV, whereas the paper reports H2O induces generative verbosity and Stream terminates generation prematurely, truncating reasoning.
• Compatibility with other methods: Combined with the layer-wise budget allocation scheme PyramidKV, FASA improves from 43.7 to 44.4 on Qasper at a 256 budget (+0.7) and from 61.8 to 62.2 on Lcc (+0.4).
• Robustness to hyperparameters: Ablating the CA computation window K gives average scores of 44.5 (K=128), 44.1 (K=256), 43.9 (K=512), and 44.1 (K=1024). Ablating the calibration source (Base, NarrativeQA, Qasper, MultiNews, Self) produced only small differences, with coefficient-of-variation values of .007 to .014 reported.

Methodology in Plain English

RoPE encodes position by rotating pairs of dimensions at different angular frequencies, so a d-dimensional query or key splits into d/2 two-dimensional "frequency chunks" (FCs), each with its own rotation speed. The authors hypothesize that a few FCs handle context-dependent matching while the rest mainly inject positional patterns such as recency bias and attention sinks.

To test this, they define a Contextual Agreement (CA) metric: for a given head and query, they compare the top-K token indices produced by a single FC's raw scores with those produced by the full head's scores, and measure the overlap divided by K. Averaging CA across samples reveals which FCs are "dominant."

Because this dominance turns out to be stable across tasks, the dominant FC indices per head can be found offline once, by selecting the subset of FCs of size N_tip that maximizes expected CA over a small calibration set. This is a one-time, task-invariant cost.

At inference, FASA runs two stages. The Token Importance Predictor (TIP) stage computes attention scores using only the dominant FCs (bypassing the other frequencies entirely) to produce an importance vector, and keeps the top N_fac tokens. The Focused Attention Computation (FAC) stage then gathers the keys and values for just those tokens

Authors’ abstract

The deployment of Large Language Models (LLMs) faces a critical bottleneck when handling lengthy inputs: the prohibitive memory footprint of the Key Value (KV) cache. To address this bottleneck, the token pruning paradigm leverages attention sparsity to selectively retain a small, critical subset of tokens. However, existing approaches fall short, with static methods risking irreversible information loss and dynamic strategies employing heuristics that insufficiently capture the query-dependent nature of token importance. We propose FASA, a novel framework that achieves query-aware token eviction by dynamically predicting token importance. FASA stems from a novel insight into RoPE: the discovery of functional sparsity at the frequency-chunk (FC) level. Our key finding is that a small, identifiable subset of "dominant" FCs consistently exhibits high contextual agreement with the full attention head. This provides a robust and computationally free proxy for identifying salient tokens. Building on this insight, FASA first identifies a critical set of tokens using dominant FCs, and then performs focused attention computation solely on this pruned subset. Across a spectrum of long-context tasks, from sequence modeling to complex CoT reasoning, FASA consistently outperforms all token-eviction baselines and achieves near-oracle accuracy, demonstrating remarkable robustness even under constraint budgets. Notably, on LongBench-V1, FASA reaches nearly 100\% of full-KV performance when only keeping 256 tokens, and achieves 2.56$\times$ speedup using just 18.9\% of the cache on AIME24.