Spectral-LSH: Sub-Quadratic Prompt Compression via Krylov-Projected Locality-Sensitive Hashing

Researchers propose Spectral-LSH, a training-free prompt compression method that uses Krylov subspace methods and SimHash to reduce long-prompt inference costs by grouping similar tokens into macro-tokens. On Qwen2.5-7B at 16x compression, the method reduces perplexity ratio from 353.409 to 196.963, and on Qwen2.5-14B from 9.533 to 3.427. The adaptive backend switches between chunking and spectral clustering based on compression ratio to optimize latency and quality.

arXiv:2607.19368v1 Announce Type: new Abstract: Long-prompt inference remains expensive because prefill attention scales quadratically with sequence length. We propose Spectral-LSH, a training-free prompt compression method that operates before the prompt enters the language model. Spectral-LSH approximates the dominant components of an implicit attention-kernel operator using a Krylov subspace method together with random features, avoiding explicit $O N^2 $ attention-kernel materialization. It then applies SimHash in the resulting attention eigenspace to group similar tokens and aggregate them into macro-tokens with causal positional assignments. We evaluate Mistral-7B-Instruct-v0.3, Qwen2.5-7B-Instruct, and Qwen2.5-14B-Instruct on C4. Our experiments reveal a compression-ratio phase transition. Below $\rho = 4 \times$, local token redundancy is low enough that lightweight chunking typically provides the best latency--quality trade-off. Above $\rho = 8 \times$, the spectral path preserves quality that chunking loses. At $\rho = 16 \times$, Qwen2.5-7B adaptive reduces the PPL ratio from 353.409 to 196.963, while Qwen2.5-14B adaptive reduces it from 9.533 to 3.427. On a small long-context structured stress test containing JSON-like, code-like, and table-like inputs, local LSH also improves every metric over chunking at $8 \times$. The adaptive backend captures both regimes by using the chunk path at low compression and spectral clustering at high compression, although chunking remains the fastest backend in total latency.