Training-Free Hashing-Based Attention via Binary Principal Components

• URL: http://arxiv.org/abs/2608.04405v1
• Date: Wed, 05 Aug 2026 03:19:21 GMT
• Title: Training-Free Hashing-Based Attention via Binary Principal Components
• Abstract summary: Long-context large language models (LLMs) are increasingly deployed in real-world applications.<n>Existing sparse attention reduce computation by attending to fewer KV pairs, but often suffer from substantial accuracy degradation.<n>We present BinaryPC, a training-free, data-aware hashing-based sparse attention for long-context LLMs.
• Score: 62.88957443238231
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 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.

Related papers

• Image Hashing via Cross-View Code Alignment in the Age of Foundation Models [3.33876524834826]
  COCOVCA (Cross-View Code Alignment) is a simple and unified principle for learning binary codes that remain consistent across semantically aligned views.<n>HashCoder is a lightweight hashing network with a final batch normalization layer to enforce balanced codes.<n>CroVCA achieves state-of-the-art results in just 5 training epochs.
  arXiv  Detail & Related papers  (2025-10-31T16:08:46Z)
• Spotlight Attention: Towards Efficient LLM Generation via Non-linear Hashing-based KV Cache Retrieval [67.21678698740267]
  We introduce Spotlight Attention, a novel method that employs non-linear hashing functions to optimize the embedding distribution of queries and keys.<n>We also develop a lightweight, stable training framework using a Bradley-Terry ranking-based loss.
  arXiv  Detail & Related papers  (2025-08-27T10:11:27Z)
• Voronoi Diagram Encoded Hashing [9.339307138969193]
  Voronoi diagram is a suitable candidate because of its three properties.<n>We propose a simple and efficient no-learning binary hashing method, called Voronoi Diagram Encoded Hashing (VDeH)
  arXiv  Detail & Related papers  (2025-08-04T10:16:48Z)
• Deep Asymmetric Hashing with Dual Semantic Regression and Class Structure Quantization [9.539842235137376]
  We propose a dual semantic asymmetric hashing (DSAH) method, which generates discriminative hash codes under three-fold constrains. With these three main components, high-quality hash codes can be generated through network.
  arXiv  Detail & Related papers  (2021-10-24T16:14:36Z)
• Fast Class-wise Updating for Online Hashing [196.14748396106955]
  This paper presents a novel supervised online hashing scheme, termed Fast Class-wise Updating for Online Hashing (FCOH) A class-wise updating method is developed to decompose the binary code learning and alternatively renew the hash functions in a class-wise fashion, which well addresses the burden on large amounts of training batches. To further achieve online efficiency, we propose a semi-relaxation optimization, which accelerates the online training by treating different binary constraints independently.
  arXiv  Detail & Related papers  (2020-12-01T07:41:54Z)
• Making Online Sketching Hashing Even Faster [63.16042585506435]
  We present a FasteR Online Sketching Hashing (FROSH) algorithm to sketch the data in a more compact form via an independent transformation. We provide theoretical justification to guarantee that our proposed FROSH consumes less time and achieves a comparable sketching precision. We also extend FROSH to its distributed implementation, namely DFROSH, to further reduce the training time cost of FROSH.
  arXiv  Detail & Related papers  (2020-10-10T08:50:53Z)
• Learning to Hash with Graph Neural Networks for Recommender Systems [103.82479899868191]
  Graph representation learning has attracted much attention in supporting high quality candidate search at scale. Despite its effectiveness in learning embedding vectors for objects in the user-item interaction network, the computational costs to infer users' preferences in continuous embedding space are tremendous. We propose a simple yet effective discrete representation learning framework to jointly learn continuous and discrete codes.
  arXiv  Detail & Related papers  (2020-03-04T06:59:56Z)
• Auto-Encoding Twin-Bottleneck Hashing [141.5378966676885]
  This paper proposes an efficient and adaptive code-driven graph. It is updated by decoding in the context of an auto-encoder. Experiments on benchmarked datasets clearly show the superiority of our framework over the state-of-the-art hashing methods.
  arXiv  Detail & Related papers  (2020-02-27T05:58:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.