# Chefs' Random Tables: Non-Trigonometric Random Features

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 73 references that are in the map.
- First posted on arXiv 30 May 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Masked Autoencoders Are Scalable Vision Learners](https://mlsanity.com/paper/2111.06377/) (2021)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Conformer: Convolution-augmented Transformer for Speech Recognition](https://mlsanity.com/paper/2005.08100/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Energy and Policy Considerations for Deep Learning in NLP](https://mlsanity.com/paper/1906.02243/) (2019)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [Ethical and social risks of harm from Language Models](https://mlsanity.com/paper/2112.04359/) (2021)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (2020)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers](https://mlsanity.com/paper/2006.03555/) (2020)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Random feature neural networks learn Black-Scholes type PDEs without curse of dimensionality](https://mlsanity.com/paper/2106.08900/) (2021)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Operator-Valued Bochner Theorem, Fourier Feature Maps for Operator-Valued Kernels, and Vector-Valued Learning](https://mlsanity.com/paper/1608.05639/) (2016)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)

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

- [Efficient Attention via Control Variates](https://mlsanity.com/paper/2302.04542/) (2023)
- [SARA-RT: Scaling up Robotics Transformers with Self-Adaptive Robust Attention](https://mlsanity.com/paper/2312.01990/) (2023)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers](https://mlsanity.com/paper/2302.01925/) (2023)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Mnemosyne: Learning to Train Transformers with Transformers](https://mlsanity.com/paper/2302.01128/) (2023)
- [Scalable Neural Network Kernels](https://mlsanity.com/paper/2310.13225/) (2023)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Features](https://mlsanity.com/paper/2302.00787/) (2023)
- [Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products](https://mlsanity.com/paper/2311.01960/) (2023)
- [SeTformer is What You Need for Vision and Language](https://mlsanity.com/paper/2401.03540/) (2024)
- [Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs](https://mlsanity.com/paper/2410.10368/) (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)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2601.22563/) (2026)
- [Orthogonal Random Features: Explicit Forms and Sharp Inequalities](https://mlsanity.com/paper/2310.07370/) (2023)
- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)
- [SLAY: Geometry-Aware Spherical Linearized Attention with Yat-Kernel](https://mlsanity.com/paper/2602.04915/) (2026)
- [Multiple View Performers for Shape Completion](https://mlsanity.com/paper/2209.06291/) (2022)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2410.09771/) (2024)
- [Rationally Linearized MLPs](https://mlsanity.com/paper/2610.13568/) (2026)

## Abstract (arXiv)

We introduce chefs' random tables (CRTs), a new class of non-trigonometric random features (RFs) to approximate Gaussian and softmax kernels. CRTs are an alternative to standard random kitchen sink (RKS) methods, which inherently rely on the trigonometric maps. We present variants of CRTs where RFs are positive, a key requirement for applications in recent low-rank Transformers. Further variance reduction is possible by leveraging statistics which are simple to compute. One instantiation of CRTs, the optimal positive random features (OPRFs), is to our knowledge the first RF method for unbiased softmax kernel estimation with positive and bounded RFs, resulting in exponentially small tails and much lower variance than its counterparts. As we show, orthogonal random features applied in OPRFs provide additional variance reduction for any dimensionality d (not only asymptotically for sufficiently large d, as for RKS). We test CRTs on many tasks ranging from non-parametric classification to training Transformers for text, speech and image data, obtaining new state-of-the-art results for low-rank text Transformers, while providing linear space and time complexity.