📊 statistics

WildCat: Near-Linear Attention in Theory and Practice

WildCat is a high-accuracy, low-cost attention compression method that achieves near-linear time complexity and super-polynomial error decay by selecting and weighting a small coreset via randomly pivoted Cholesky subsampling, outperforming prior approximations in both theoretical guarantees and practical performance across image and language tasks.

Original authors: Tobias Schröder, Lester Mackey

Published 2026-06-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Tobias Schröder, Lester Mackey

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to remember a conversation with a friend that lasted for hours. In a standard AI model (like the ones powering today's chatbots), trying to recall every single word from that entire conversation at once is like trying to hold a library of books in your head while simultaneously writing a new one. The more words you add, the harder it gets, and the memory required grows quadratically. This means if you double the length of the conversation, the effort to remember it doesn't just double; it quadruples. Eventually, the computer runs out of memory or takes forever to think.

The paper introduces a new method called WILDCAT (Weighted Iterative Low-rank Decomposition for Coreset ATtention) to solve this problem. Here is how it works, using simple analogies:

The Problem: The "Library" Bottleneck

Think of the AI's memory as a massive library. When the AI needs to answer a question, it usually has to scan every single book (every word in the conversation) to find the relevant information.

The Old Way: If the library has 1,000 books, the AI checks 1,000 books. If the library grows to 10,000 books, the AI has to check 10,000 books, but the effort to cross-reference them explodes. It's like trying to find a specific needle in a haystack by comparing every single straw to every other straw.

The Solution: The "Expert Panel" (WILDCAT)

WILDCAT changes the strategy. Instead of trying to remember everything perfectly, it realizes that not every word in a conversation is equally important. Some words are crucial, while others are just filler.

WILDCAT does two main things:

Selecting the "Coreset" (The Expert Panel):
Imagine you have a massive crowd of 10,000 people, and you need to know the general mood of the room. Instead of interviewing everyone, WILDCAT uses a clever, fast algorithm (called "Randomly Pivoted Cholesky") to pick a tiny, representative group of, say, 50 people.
- The Magic: It doesn't just pick them randomly; it picks the most important ones that best represent the whole crowd. It's like picking the most vocal and diverse members of a town to form a council that can speak for everyone else.
Weighting the Voices:
Once it has this small group of 50, WILDCAT doesn't treat them all equally. It assigns "weights" to them.
- The Analogy: If one person in the small group is a very loud, opinionated leader, their voice counts for more. If another person is quiet, their voice counts for less. WILDCAT calculates the perfect "volume" for each of these 50 people so that when you listen to just them, it sounds exactly like listening to the whole crowd of 10,000.

Why This is a Big Deal

The paper claims WILDCAT achieves three major breakthroughs:

Speed (Near-Linear): Because it only listens to the small group of 50 instead of the whole crowd of 10,000, the time it takes to think grows very slowly. If you double the conversation length, the time only increases a tiny bit, not a massive amount. It's like switching from reading every page of a book to just reading a highly accurate summary.
Accuracy (Super-Polynomial): Usually, when you summarize something, you lose details. WILDCAT is special because it claims to lose almost no important details. The paper proves mathematically that as the conversation gets longer, the error (the missing details) shrinks incredibly fast—faster than almost any other method currently in use.
Practicality: The authors didn't just do the math; they built a working version on powerful computer chips (GPUs). They tested it on:
- Making Images: It generated high-quality images faster than other methods without making them look blurry or weird.
- Classifying Images: It recognized objects in photos just as well as the full, slow method but much faster.
- Long Conversations: It allowed a language model to remember a much longer history of a chat without running out of memory, performing better than other "memory compression" tricks.

The Bottom Line

WILDCAT is like a super-efficient secretary who can listen to a 10-hour meeting, instantly pick out the 50 most important moments, assign them the right level of importance, and then summarize the whole meeting so accurately that the boss feels like they heard everything, but the secretary only had to write down a few pages.

This allows AI models to handle much longer conversations and larger tasks without needing super-computers, making them faster, cheaper to run, and capable of remembering more context.

Technical Summary: WILDCAT: Near-Linear Attention in Theory and Practice

Problem Statement

The attention mechanism is a cornerstone of modern transformer-based architectures, enabling the modeling of long-range dependencies in sequences. However, its deployment is notoriously expensive because resource requirements scale quadratically ( $\Theta(n^2d)$ ) with the input sequence length $n$ . While numerous approximate attention methods exist, a significant gap remains between theoretical guarantees and practical performance:

Practical approximations (e.g., Reformer, Performer, ScatterBrain) often lack rigorous error guarantees or require quadratic runtime to ensure high fidelity.
Theoretical advances (e.g., Alman & Song, 2023) demonstrate that near-linear time ( $O(n^{1+o(1)})$ ) with super-polynomial error decay is possible for bounded inputs, but existing practical implementations either fail to achieve this decay in near-linear time or require quadratic time to guarantee it.

The paper identifies the need for an approach that is simultaneously computationally efficient (near-linear time), spectrally accurate (super-polynomial error decay), and practically implementable on modern hardware.

Methodology

The authors introduce WILDCAT (Weighted Iterative Low-rank Decomposition for Coreset ATtention), a method that approximates the softmax attention mechanism by attending only over a small, weighted coreset of input keys. The methodology consists of three core components:

1. Weighted Coreset Selection via Randomly Pivoted Cholesky (RPC)

Instead of attending to all $n$ keys, WILDCAT selects a subset of $r$ keys ( $r \ll n$ ) to form a coreset $K_S$ .

Algorithm: The selection uses a parallelized Randomly Pivoted Cholesky (RPC) algorithm (adapted from Chen et al., 2022a). This algorithm builds a partial Cholesky decomposition of the kernel matrix $H = \exp(\beta K K^\top)$ .
Pivoting Rule: In each iteration, a pivot index is sampled from the diagonal of the current residual kernel matrix. This ensures the selected points are spectrally representative of the full dataset.
Efficiency: The selection runs in $O(nr^2)$ time. To maximize GPU throughput, the authors employ a divide-and-conquer strategy, partitioning the input into $B$ bins and processing them in parallel, reducing the runtime to $O(nr^2/B^3 + nrd/B^2)$ .

2. Optimal Reweighting via Nyström Approximation

Once the coreset $K_S$ is selected, the method computes optimal weights to minimize the reconstruction error of the attention matrix.

Nyström Weights: The weights $W$ are derived using the Nyström method: $W = h(K_S, K_S)^+ h(K_S, K)$ . This provides the optimal linear combination of the coreset features to approximate the full kernel features.
Value Compression: The value matrix $V$ is compressed to $V_S = WV$ , allowing the final attention output to be computed using only the $r$ coreset elements.

3. Invariance and Rescaling

The authors leverage the invariance of the softmax attention under global recentering of keys and rescaling of keys and queries.

Recentering: Keys are recentered by subtracting their mean ( $K \leftarrow K - \bar{k}$ ).
Temperature Scaling: A closed-form rescaling parameter $\tau$ is derived to balance the trade-off between making the kernel matrix low-rank approximable (by increasing $\tau$ ) and minimizing the query-based error inflation factor. This parameter depends on the Lambert-W function and the norms of the queries and keys.

Key Contributions

The paper establishes the following desirable properties for WILDCAT:

Near-Linear Runtime: WILDCAT avoids the quadratic cost of exact attention. By attending over a coreset of size $r \in n^{o(1)}$ , the algorithm runs in near-linear time $O(n^{1+o(1)})$ .
Super-Polynomial Error Decay: Under bounded input assumptions, WILDCAT approximates exact attention with super-polynomial error decay of $O(n^{-\sqrt{\log(\log(n))}})$ . This is achieved while maintaining near-linear runtime, a feat previous practical approximations could not guarantee without quadratic time.
Robustness to Growth: Theoretical analysis (Corollary 2) shows that WILDCAT maintains super-polynomial error decay even when input entries or dimensions grow super-logarithmically with $n$ , pushing beyond the limits of prior computational hardness results for attention.
KV Cache Compression: The method includes a COMPRESSKV module that reduces the memory footprint of KV caches from linear $\Theta(nd)$ to near-constant $O(rd)$, facilitating long-context inference.
Practical Implementation: The authors provide a GPU-optimized PyTorch implementation, bridging the gap between theoretical spectral guarantees and real-world performance.

Experimental Results

The authors evaluated WILDCAT across three domains:

Image Generation (BigGAN): WILDCAT achieved a 4.33× speed-up over exact attention. It demonstrated the smallest degradation in Inception Score (1.22%) and zero degradation in Fréchet Inception Distance (FID) compared to the ImageNet validation set, outperforming Reformer, Performer, KDEformer, and Thinformer.
Image Classification (T2T-ViT): On the ImageNet classification benchmark, WILDCAT achieved the highest mean Top-1 accuracy (82.19%, compared to 82.55% for exact attention) among all approximations. It provided an 11.59× speed-up for the computationally dominant first layer.
Long-Context Language Models (KV Cache Compression): Using the Qwen2.5-7B-Instruct model on 13 LongBench-E tasks, WILDCAT (via COMPRESSKV) consistently outperformed five leading KV cache compression methods (including StreamingLLM, PyramidKV, and SnapKV) in terms of average compression quality across varying compression levels (75%, 87.5%, 93.75%).
Comparison with FlashAttention 2: Benchmarks against FlashAttention 2 showed that as sequence length increases (from $2^{13}$ to $2^{18}$ ), WILDCAT's speed-up grows from 1.1× to 68×, while the approximation error steadily decreases.

Significance and Claims

The paper claims to successfully bridge the theory-practice gap in attention approximation.

Theoretical Breakthrough: It demonstrates that super-polynomial error decay is achievable in near-linear time for practical, bounded inputs, a guarantee previously only theoretical or requiring quadratic runtime.
Practical Utility: The method is not just a theoretical construct; it is implemented efficiently on GPUs and validated on state-of-the-art models for generation, classification, and language understanding.
Scalability: By reducing KV cache memory requirements to near-constant size, WILDCAT enables the deployment of long-context language models on resource-constrained hardware.

The authors note limitations, specifically that the current work does not address streaming generation with causal masking (though they suggest extensions via prefix sums or divide-and-conquer are possible) and that the sequential nature of the pivot selection in RPC could be improved via oversampling mechanisms in future work.