# Hybrid Random Features

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 36 references that are in the map.
- First posted on arXiv 8 Oct 2021.

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

- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Conformer: Convolution-augmented Transformer for Speech Recognition](https://mlsanity.com/paper/2005.08100/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linear Transformers Are Secretly Fast Weight Programmers](https://mlsanity.com/paper/2102.11174/) (2021)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Using the Output Embedding to Improve Language Models](https://mlsanity.com/paper/1608.05859/) (2016)
- [On Wasserstein Two Sample Testing and Related Families of Nonparametric Tests](https://mlsanity.com/paper/1509.02237/) (2015)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Tying Word Vectors and Word Classifiers: A Loss Framework for Language Modeling](https://mlsanity.com/paper/1611.01462/) (2016)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding](https://mlsanity.com/paper/2106.12566/) (2021)
- [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)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [Adaptive Sampled Softmax with Kernel Based Sampling](https://mlsanity.com/paper/1712.00527/) (2017)
- [Sampled Softmax with Random Fourier Features](https://mlsanity.com/paper/1907.10747/) (2019)
- [Large-Scale Kernel Methods for Independence Testing](https://mlsanity.com/paper/1606.07892/) (2016)
- [Recycling Randomness with Structure for Sublinear time Kernel Expansions](https://mlsanity.com/paper/1605.09049/) (2016)
- [Random Features for Compositional Kernels](https://mlsanity.com/paper/1703.07872/) (2017)
- [Unlocking Pixels for Reinforcement Learning via Implicit Attention](https://mlsanity.com/paper/2102.04353/) (2021)

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

- [Socratic Models: Composing Zero-Shot Multimodal Reasoning with Language](https://mlsanity.com/paper/2204.00598/) (2022)
- [The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicry](https://mlsanity.com/paper/2402.04347/) (2024)
- [Efficient Attention via Control Variates](https://mlsanity.com/paper/2302.04542/) (2023)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [MetaLA: Unified Optimal Linear Approximation to Softmax Attention Map](https://mlsanity.com/paper/2411.10741/) (2024)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Scaling Linear Attention with Sparse State Expansion](https://mlsanity.com/paper/2507.16577/) (2025)
- [Attention-based Random Forest and Contamination Model](https://mlsanity.com/paper/2201.02880/) (2022)
- [Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers](https://mlsanity.com/paper/2302.01925/) (2023)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [Selective Rotary Position Embedding](https://mlsanity.com/paper/2511.17388/) (2025)
- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Collaborative Bayesian Optimization via Wasserstein Barycenters](https://mlsanity.com/paper/2504.10770/) (2025)
- [TRAMS: Training-free Memory Selection for Long-range Language Modeling](https://mlsanity.com/paper/2310.15494/) (2023)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [ZeroS: Zero-Sum Linear Attention for Efficient Transformers](https://mlsanity.com/paper/2602.05230/) (2026)
- [Attention and Self-Attention in Random Forests](https://mlsanity.com/paper/2207.04293/) (2022)
- [FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Features](https://mlsanity.com/paper/2302.00787/) (2023)
- [Implicit Two-Tower Policies](https://mlsanity.com/paper/2208.01191/) (2022)
- [Generalization Bound for Diffusion Models using Random Features](https://mlsanity.com/paper/2310.04417/) (2023)
- [Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products](https://mlsanity.com/paper/2311.01960/) (2023)
- [Generalized Reference Kernel for One-class Classification](https://mlsanity.com/paper/2205.00534/) (2022)
- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)
- [LARF: Two-level Attention-based Random Forests with a Mixture of Contamination Models](https://mlsanity.com/paper/2210.05168/) (2022)

## Abstract (arXiv)

We propose a new class of random feature methods for linearizing softmax and Gaussian kernels called hybrid random features (HRFs) that automatically adapt the quality of kernel estimation to provide most accurate approximation in the defined regions of interest. Special instantiations of HRFs lead to well-known methods such as trigonometric (Rahimi and Recht, 2007) or (recently introduced in the context of linear-attention Transformers) positive random features (Choromanski et al., 2021). By generalizing Bochner's Theorem for softmax/Gaussian kernels and leveraging random features for compositional kernels, the HRF-mechanism provides strong theoretical guarantees - unbiased approximation and strictly smaller worst-case relative errors than its counterparts. We conduct exhaustive empirical evaluation of HRF ranging from pointwise kernel estimation experiments, through tests on data admitting clustering structure to benchmarking implicit-attention Transformers (also for downstream Robotics applications), demonstrating its quality in a wide spectrum of machine learning problems.