CodeAuditor
WildCat Attention Implementation Issues
WildCat: Near-Linear Attention in Theory and Practice
Published: 12 May 2026 · Updated: 13 July 2026
Read the original sourceWhat the paper says
WildCat achieves super-polynomial error decay O(n^{-√log(log(n))}) in near-linear O(n^{1+o(1)}) time.
The Critique
Runtime analysis shows only 1.24x speedup vs standard attention at n=8192, while random sampling achieves 1.62x. Missing baselines: uniform random sampling, attention weight thresholding. 'Near-linear' hides large constants. No end-to-end model quality degradation measured.
Why It Matters
If theoretical advantages don't translate to practical speedups, research effort may be misdirected. Understanding when sophisticated approximation is worth complexity is crucial.
What They Missed
The error bound O(n^{-√log(log(n))}) decays extremely slowly—for n=1e6, √log(log(n)) ≈ 1.4, so error decays as n^{-1.4}. This is polynomial, not 'super-polynomial' in any practical sense.
The Big Question
When do WildCat's theoretical advantages actually materialize in practice, and how does approximation error affect downstream task performance?