# Manifold Random Features

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 43 references that are in the map.
- First posted on arXiv 3 Feb 2026.

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

- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Learning Mesh-Based Simulation with Graph Networks](https://mlsanity.com/paper/2010.03409/) (2020)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Thingi10K: A Dataset of 10,000 3D-Printing Models](https://mlsanity.com/paper/1605.04797/) (2016)
- [The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicry](https://mlsanity.com/paper/2402.04347/) (2024)
- [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)
- [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)
- [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)
- [Efficient Attention Mechanisms for Large Language Models: A Survey](https://mlsanity.com/paper/2507.19595/) (2025)
- [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)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Recycling Randomness with Structure for Sublinear time Kernel Expansions](https://mlsanity.com/paper/1605.09049/) (2016)
- [Scalable Neural Network Kernels](https://mlsanity.com/paper/2310.13225/) (2023)
- [Exact heat kernel on a hypersphere and its applications in kernel SVM](https://mlsanity.com/paper/1702.01373/) (2017)
- [Efficient Graph Field Integrators Meet Point Clouds](https://mlsanity.com/paper/2302.00942/) (2023)
- [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)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)

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

- [Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling](https://mlsanity.com/paper/2609.32824/) (2026)

## Abstract (arXiv)

We present a new paradigm for creating random features to approximate bi-variate functions (in particular, kernels) defined on general manifolds. This new mechanism of Manifold Random Features (MRFs) leverages discretization of the manifold and the recently introduced technique of Graph Random Features (GRFs) to learn continuous fields on manifolds. Those fields are used to find continuous approximation mechanisms that otherwise, in general scenarios, cannot be derived analytically. MRFs provide positive and bounded features, a key property for accurate, low-variance approximation. We show deep asymptotic connection between GRFs, defined on discrete graph objects, and continuous random features used for regular kernels. As a by-product of our method, we re-discover recently introduced mechanism of Gaussian kernel approximation applied in particular to improve linear-attention Transformers, considering simple random walks on graphs and by-passing original complex mathematical computations. We complement our algorithm with a rigorous theoretical analysis and verify in thorough experimental studies.