WildCat: Near-Linear Attention in Theory and Practice

We introduce WildCat, a high-accuracy, low-cost approach to compressing the attention mechanism in neural networks. While attention is a staple of modern network architectures, it is also notoriously expensive to deploy due to resource requirements that scale quadratically with the input sequence length $n$. WildCat avoids these quadratic costs by only attending over a small weighted coreset. Crucially, we select the coreset using a fast but spectrally-accurate subsampling algorithm -- randomly pivoted Cholesky -- and weight the elements optimally to minimise reconstruction error. Remarkably, given bounded inputs, WildCat approximates exact attention with super-polynomial $O(n^{-\sqrt{\log(\log(n))}})$ error decay while running in near-linear $O(n^{1+o(1)})$ time. In contrast, prior practical approximations either lack error guarantees or require quadratic runtime to guarantee such high fidelity. We couple this advance with a GPU-optimised PyTorch implementation and a suite of benchmark experiments demonstrating the benefits of WildCat for image generation, image classification, and language model KV cache compression.

Practically all modern AI systems, from large language models to image generators, rely on the so-called attention mechanism, which allows the model to weigh which parts of the input are most relevant when producing an output. However, this operation is notoriously expensive: doubling the input context size quadruples the computation cost, creating a major computational bottleneck. We introduce WildCat, a method that compresses the input into a compact summary (a “coreset”) so that the model only needs to attend over a fraction of the original data. Our central contribution is a fast randomised algorithm which selects and weights the coreset to guarantee minimal error introduced by the compression. In particular, WildCat is the first practical approximation method for the attention mechanism to achieve near-linear computational complexity together with provably fast error decay. By reducing computation and memory requirements while preserving output quality, WildCat can help lower the energy costs of running AI models, enable longer inputs to be processed on existing hardware, and extend access to powerful AI systems in resource-constrained settings.