# Simplex Random Features

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 54 references that are in the map.
- First posted on arXiv 31 Jan 2023.

## Builds on (most cited first, 24 of 24)

- [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)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [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)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Linear Transformers Are Secretly Fast Weight Programmers](https://mlsanity.com/paper/2102.11174/) (2021)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding](https://mlsanity.com/paper/2106.12566/) (2021)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [Relative Positional Encoding for Transformers with Linear Complexity](https://mlsanity.com/paper/2105.08399/) (2021)
- [Learning Model Predictive Controllers with Real-Time Attention for Real-World Navigation](https://mlsanity.com/paper/2209.10780/) (2022)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [Sub-Linear Memory: How to Make Performers SLiM](https://mlsanity.com/paper/2012.11346/) (2020)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Demystifying Orthogonal Monte Carlo and Beyond](https://mlsanity.com/paper/2005.13590/) (2020)
- [Structured adaptive and random spinners for fast machine learning computations](https://mlsanity.com/paper/1610.06209/) (2016)
- [Translational Equivariance in Kernelizable Attention](https://mlsanity.com/paper/2102.07680/) (2021)
- [On Binary Embedding using Circulant Matrices](https://mlsanity.com/paper/1511.06480/) (2015)

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

- [Towards Understanding How Transformers Learn In-context Through a Representation Learning Lens](https://mlsanity.com/paper/2310.13220/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [Variance-Reducing Couplings for Random Features](https://mlsanity.com/paper/2405.16541/) (2024)
- [All Random Features Representations are Equivalent](https://mlsanity.com/paper/2406.18802/) (2024)
- [The kernel of graph indices for vector search](https://mlsanity.com/paper/2506.20584/) (2025)
- [SWING: Unlocking Implicit Graph Representations for Graph Random Features](https://mlsanity.com/paper/2602.12703/) (2026)

## Abstract (arXiv)

We present Simplex Random Features (SimRFs), a new random feature (RF) mechanism for unbiased approximation of the softmax and Gaussian kernels by geometrical correlation of random projection vectors. We prove that SimRFs provide the smallest possible mean square error (MSE) on unbiased estimates of these kernels among the class of weight-independent geometrically-coupled positive random feature (PRF) mechanisms, substantially outperforming the previously most accurate Orthogonal Random Features at no observable extra cost. We present a more computationally expensive SimRFs+ variant, which we prove is asymptotically optimal in the broader family of weight-dependent geometrical coupling schemes (which permit correlations between random vector directions and norms). In extensive empirical studies, we show consistent gains provided by SimRFs in settings including pointwise kernel estimation, nonparametric classification and scalable Transformers.