DASH-KV: Asymmetric Hashing Accelerates Long-Context LLM Inference, Reducing Complexity from Quadratic to Linear

DASH-KV is an acceleration framework proposed to address the computational bottleneck in long-context LLM inference. Its core innovation lies in reconstructing the attention mechanism into Approximate Nearest Neighbor Search (ANNS) via asymmetric deep hashing, achieving a linear leap in computational complexity from O(N²) to O(N) while maintaining generation quality comparable to full attention. This framework performs excellently on the LongBench benchmark, significantly reducing latency and memory usage, and providing a feasible path for the practical deployment of long-context LLMs.

When large language models process long texts, the computational complexity of the standard attention mechanism is quadratic with the sequence length (O(N²)), leading to a sharp increase in computation and memory usage as the context length grows, which becomes the main source of latency. Existing KV cache compression methods alleviate memory pressure but often sacrifice generation quality and fail to address the high overhead of floating-point operations. How to reduce complexity while maintaining performance is a focus of the industry.

DASH-KV reformulates attention computation as an ANNS problem, adapting to the different characteristics of queries and keys through an asymmetric encoding architecture: queries are dynamically generated and require high precision, so deeper networks and high representation precision are used; keys are statically cached and reusable, so lightweight structures are adopted to reduce overhead. This design leverages the essence of attention (queries finding similar keys) and replaces exact dot products with efficient approximate algorithms to balance precision and efficiency.

DASH-KV introduces a dynamic mixed precision mechanism, which uses a lightweight importance evaluation module to real-time judge the criticality of tokens: key tokens (such as keywords and entities) retain full floating-point precision computation, while secondary tokens use hash approximation for acceleration. This adaptive strategy optimizes computing resources without losing important information, achieving a balance between efficiency and quality.

DASH-KV uses Locality-Sensitive Hashing (LSH) and a multi-layer hash table structure to map semantically similar vectors into the same hash bucket. When querying, it only looks for candidate keys in the corresponding bucket without traversing all of them. Combined with a candidate pruning strategy (pre-filtering low-correlation candidates and retaining Top-K keys), the computational complexity per query is reduced to a constant level, and the overall O(N) linear complexity is achieved.

In tests on the LongBench benchmark (covering multiple tasks with context lengths up to hundreds of thousands), DASH-KV significantly outperforms baseline methods such as H2O and SnapKV, reducing latency by 3-5 times and memory usage by 40-60%. Meanwhile, the gap in perplexity and accuracy compared to full attention is less than 1%, and it even surpasses full attention in some tasks, breaking the traditional trade-off between efficiency and quality.

DASH-KV can be applied to scenarios such as document analysis (long reports/contracts), code assistants (large codebase analysis), and multi-turn dialogues (maintaining ultra-long history). Its linear complexity reduces hardware costs, and its training-free feature supports rapid model iteration, simplifies operation and maintenance, and promotes the popularization of AI applications.

DASH-KV has limitations such as approximate errors (needs verification in high-precision scenarios), architectural complexity (asymmetric encoding increases engineering overhead), and simple importance evaluation. In the future, it can be extended to visual Transformers/multimodal models, and combined with more complex learning methods to optimize token importance judgment, further improving efficiency and quality.