Training-Free Hashing-Based Attention via Binary Principal Components

Long-context large language models (LLMs) are increasingly deployed in real-world applications, yet self-attention remains a major efficiency bottleneck -- especially during decoding -- due to the necessity of repeatedly processing ever-growing key-value (KV) caches. Existing sparse attention reduce computation by attending to fewer KV pairs, but often suffer from substantial accuracy degradation, require additional training, or rely on expensive hashing. In this work, we present \textbf{BinaryPC}, a training-free, data-aware hashing-based sparse attention for long-context LLMs. BinaryPC constructs compact binary hash codes and corresponding hash function by computing binary principal components of data. Unlike Locality-Sensitive Hashing (LSH) with data-independent random projections or learned non-linear hashing methods, BinaryPC constructs binary codes that explicitly preserve the structural information of data without requiring gradient-based training. Comprehensive experiments across multiple model families and long-context benchmarks show that BinaryPC preserves accuracy relative to full attention while achieving superior performance among sparse and hashing-based baselines. On modern GPUs, BinaryPC improves end-to-end decoding throughput by 3.56$\times$ over the FlashAttention kernel. Our code is available at https://github.com/yudaohai666/BPC.

Large language models are increasingly asked to work with very long inputs, such as long documents, code repositories, or extended conversations. However, as the input gets longer, the model must repeatedly look back at more and more stored information while generating each new word. This makes long-context models slow and expensive to use. We propose BinaryPC, a method that helps the model quickly decide which past information is most relevant, instead of checking everything. BinaryPC creates short binary “fingerprints” for the stored information by looking at the structure of the model’s own data. These fingerprints make it possible to efficiently group and retrieve similar pieces of information. Unlike some previous approaches, BinaryPC does not require additional training, model-specific tuning, or costly random projections. Across several long-context language models and benchmarks, BinaryPC keeps performance close to standard full attention while making generation much faster. On modern GPUs, it improves decoding throughput by up to 3.56× compared with FlashAttention. This makes long-context language models more practical for real-world applications that require fast and accurate processing of large amounts of text.