# Low-Rank Thinning

arXiv: https://arxiv.org/abs/2502.12063 · HTML: https://mlsanity.com/paper/2502.12063/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 45 references that are in the map.
- First posted on arXiv 17 Feb 2025.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Improved Techniques for Training GANs](https://mlsanity.com/paper/1606.03498/) (2016)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNet](https://mlsanity.com/paper/2101.11986/) (2021)
- [Learning Deep Kernels for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2002.09116/) (2020)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Massively scalable Sinkhorn distances via the Nystr"om method](https://mlsanity.com/paper/1812.05189/) (2018)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [A Wild Bootstrap for Degenerate Kernel Tests](https://mlsanity.com/paper/1408.5404/) (2014)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Discrepancy Minimization via a Self-Balancing Walk](https://mlsanity.com/paper/2006.14009/) (2020)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [LDMNet: Low Dimensional Manifold Regularized Neural Networks](https://mlsanity.com/paper/1711.06246/) (2017)
- [Distribution Compression in Near-linear Time](https://mlsanity.com/paper/2111.07941/) (2021)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [Balancing Covariates in Randomized Experiments with the Gram-Schmidt Walk Design](https://mlsanity.com/paper/1911.03071/) (2019)
- [The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues](https://mlsanity.com/paper/1708.01079/) (2017)
- [Differentially Private Permutation Tests](https://mlsanity.com/paper/2310.19043/) (2023)
- [Debiased Distribution Compression](https://mlsanity.com/paper/2404.12290/) (2024)

## Built on by (most cited first, 7 of 7)

- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [A Critical Look at Targeted Instruction Selection: Disentangling What Matters (and What Doesn't)](https://mlsanity.com/paper/2602.14696/) (2026)
- [The risk of KV cache compression](https://mlsanity.com/paper/2607.01520/) (2026)
- [Stationary MMD Points](https://mlsanity.com/paper/2505.20754/) (2025)
- [Thinned Mean Field Langevin Dynamics](https://mlsanity.com/paper/2605.28589/) (2026)
- [Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention](https://mlsanity.com/paper/2608.28150/) (2026)
- [Express Language Modeling](https://mlsanity.com/paper/2606.10944/) (2026)

## Abstract (arXiv)

The goal in thinning is to summarize a dataset using a small set of representative points. Remarkably, sub-Gaussian thinning algorithms like Kernel Halving and Compress can match the quality of uniform subsampling while substantially reducing the number of summary points. However, existing guarantees cover only a restricted range of distributions and kernel-based quality measures and suffer from pessimistic dimension dependence. To address these deficiencies, we introduce a new low-rank analysis of sub-Gaussian thinning that applies to any distribution and any kernel, guaranteeing high-quality compression whenever the kernel or data matrix is approximately low-rank. To demonstrate the broad applicability of the techniques, we design practical sub-Gaussian thinning approaches that improve upon the best known guarantees for approximating attention in transformers, accelerating stochastic gradient training through reordering, and distinguishing distributions in near-linear time.