Spectral-LSH: Sub-Quadratic Prompt Compression via Krylov-Projected Locality-Sensitive Hashing
Quick Answer
Spectral-LSH introduces a training-free prompt compression method that reduces the quadratic scaling of long-prompt inference.
Quick Take
Evaluating models like Qwen2.5-7B and Qwen2.5-14B, it achieves significant compression ratios, improving performance metrics while maintaining quality. Notably, at a 16x compression, Qwen2.5-7B reduces PPL from 353.409 to 196.963.
Key Points
- Spectral-LSH uses Krylov subspace methods for efficient prompt compression.
- Compression ratios show a phase transition, with optimal performance at specific thresholds.
- At 8x compression, local LSH outperforms chunking across all metrics.
- Qwen2.5-14B achieves a PPL reduction from 9.533 to 3.427 at 16x compression.
- Adaptive backend balances chunking and spectral clustering for varying compression needs.
Paper Resources
📖 Reader Mode
~2 min readAbstract: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.
| Subjects: | Artificial Intelligence (cs.AI); Computation and Language (cs.CL) |
| Cite as: | arXiv:2607.19368 [cs.AI] |
| (or arXiv:2607.19368v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2607.19368 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Azadeh Zamanifar [view email]
[v1]
Fri, 12 Jun 2026 01:11:17 UTC (34 KB)
— Originally published at arxiv.org
Want this in your inbox every morning?
Daily brief at your local 8am — bilingual EN/中文, free.
More from arXiv cs.AI
See more →HOBA: Hierarchical On-Policy Bidding Agents for Adaptive Online Advertising
HOBA (Hierarchical On-policy Bidding Agents) is a novel hierarchical reinforcement learning framework that enhances online advertising bidding systems by improving adaptability and reducing hyperparameter tuning costs. It utilizes a for hyperparameter inference, a SARSA agent for expert model selection, and a dynamic expert pool for bid execution, achieving a +3.6% increase in target cost during large-scale deployment and outperforming state-of-the-art baselines on AuctionNet.