# From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 48 references that are in the map.
- First posted on arXiv 16 Jul 2021.

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

- [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)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Stand-Alone Self-Attention in Vision Models](https://mlsanity.com/paper/1906.05909/) (2019)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Scaling Local Self-Attention for Parameter Efficient Visual Backbones](https://mlsanity.com/paper/2103.12731/) (2021)
- [Funnel-Transformer: Filtering out Sequential Redundancy for Efficient Language Processing](https://mlsanity.com/paper/2006.03236/) (2020)
- [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)
- [Relative Positional Encoding for Transformers with Linear Complexity](https://mlsanity.com/paper/2105.08399/) (2021)
- [Relative Positional Encoding for Speech Recognition and Direct Translation](https://mlsanity.com/paper/2005.09940/) (2020)
- [Improving Generalization of Transformer for Speech Recognition with Parallel Schedule Sampling and Relative Positional Embedding](https://mlsanity.com/paper/1911.00203/) (2019)
- [On Graph Classification Networks, Datasets and Baselines](https://mlsanity.com/paper/1905.04682/) (2019)

## Built on by (most cited first, 30 of 38)

- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Attending to Graph Transformers](https://mlsanity.com/paper/2302.04181/) (2023)
- [GIMLET: A Unified Graph-Text Model for Instruction-Based Molecule Zero-Shot Learning](https://mlsanity.com/paper/2306.13089/) (2023)
- [Polynormer: Polynomial-Expressive Graph Transformer in Linear Time](https://mlsanity.com/paper/2403.01232/) (2024)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems](https://mlsanity.com/paper/2405.01009/) (2024)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Learning the RoPEs: Better 2D and 3D Position Encodings with STRING](https://mlsanity.com/paper/2502.02562/) (2025)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Are More Layers Beneficial to Graph Transformers?](https://mlsanity.com/paper/2303.00579/) (2023)
- [A Survey of Graph Transformers: Architectures, Theories and Applications](https://mlsanity.com/paper/2502.16533/) (2025)
- [Tensor-view Topological Graph Neural Network](https://mlsanity.com/paper/2401.12007/) (2024)
- [Gradformer: Graph Transformer with Exponential Decay](https://mlsanity.com/paper/2404.15729/) (2024)
- [Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers](https://mlsanity.com/paper/2302.01925/) (2023)
- [Mnemosyne: Learning to Train Transformers with Transformers](https://mlsanity.com/paper/2302.01128/) (2023)
- [Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products](https://mlsanity.com/paper/2402.08450/) (2024)
- [Efficient Graph Field Integrators Meet Point Clouds](https://mlsanity.com/paper/2302.00942/) (2023)
- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers](https://mlsanity.com/paper/2406.15881/) (2024)
- [Instruction-Based Molecular Graph Generation with Unified Text-Graph Diffusion Model](https://mlsanity.com/paper/2408.09896/) (2024)
- [Building on Efficient Foundations: Effectively Training LLMs with Structured Feedforward Layers](https://mlsanity.com/paper/2406.16450/) (2024)
- [Graph Transformers Dream of Electric Flow](https://mlsanity.com/paper/2410.16699/) (2024)
- [Rotary Position Encodings for Graphs](https://mlsanity.com/paper/2509.22259/) (2025)
- [Continuous Predictive Modeling of Clinical Notes and ICD Codes in Patient Health Records](https://mlsanity.com/paper/2405.11622/) (2024)
- [GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers](https://mlsanity.com/paper/2411.17296/) (2024)
- [TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows](https://mlsanity.com/paper/2508.05070/) (2025)
- [ToTMNet: FFT-Accelerated Toeplitz Temporal Mixing Network for Lightweight Remote Photoplethysmography](https://mlsanity.com/paper/2601.04159/) (2026)
- [Size-Transferability of Graph Transformers with Convolutional Positional Encodings](https://mlsanity.com/paper/2602.15239/) (2026)
- [RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodings](https://mlsanity.com/paper/2605.10706/) (2026)

## Abstract (arXiv)

In this paper we provide, to the best of our knowledge, the first comprehensive approach for incorporating various masking mechanisms into Transformers architectures in a scalable way. We show that recent results on linear causal attention (Choromanski et al., 2021) and log-linear RPE-attention (Luo et al., 2021) are special cases of this general mechanism. However by casting the problem as a topological (graph-based) modulation of unmasked attention, we obtain several results unknown before, including efficient d-dimensional RPE-masking and graph-kernel masking. We leverage many mathematical techniques ranging from spectral analysis through dynamic programming and random walks to new algorithms for solving Markov processes on graphs. We provide a corresponding empirical evaluation.