# FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 79 of its 114 references that are in the map.
- First posted on arXiv 10 Nov 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [A ConvNet for the 2020s](https://mlsanity.com/paper/2201.03545/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [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)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [GLaM: Efficient Scaling of Language Models with Mixture-of-Experts](https://mlsanity.com/paper/2112.06905/) (2021)
- [Natural TTS Synthesis by Conditioning WaveNet on Mel Spectrogram Predictions](https://mlsanity.com/paper/1712.05884/) (2017)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [Jukebox: A Generative Model for Music](https://mlsanity.com/paper/2005.00341/) (2020)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)

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

- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [SiMBA: Simplified Mamba-Based Architecture for Vision and Multivariate Time series](https://mlsanity.com/paper/2403.15360/) (2024)
- [Hydragen: High-Throughput LLM Inference with Shared Prefixes](https://mlsanity.com/paper/2402.05099/) (2024)
- [Mamba-360: Survey of State Space Models as Transformer Alternative for Long Sequence Modelling: Methods, Applications, and Challenges](https://mlsanity.com/paper/2404.16112/) (2024)
- [State Space Model for New-Generation Network Alternative to Transformers: A Survey](https://mlsanity.com/paper/2404.09516/) (2024)
- [CATS: Contextually-Aware Thresholding for Sparsity in Large Language Models](https://mlsanity.com/paper/2404.08763/) (2024)
- [ThunderKittens: Simple, Fast, and Adorable AI Kernels](https://mlsanity.com/paper/2410.20399/) (2024)
- [State-Free Inference of State-Space Models: The Transfer Function Approach](https://mlsanity.com/paper/2405.06147/) (2024)
- [SambaNova SN40L: Scaling the AI Memory Wall with Dataflow and Composition of Experts](https://mlsanity.com/paper/2405.07518/) (2024)
- [State Space Models on Temporal Graphs: A First-Principles Study](https://mlsanity.com/paper/2406.00943/) (2024)
- [GroupMamba: Efficient Group-Based Visual State Space Model](https://mlsanity.com/paper/2407.13772/) (2024)
- [Tiled Flash Linear Attention: More Efficient Linear RNN and xLSTM Kernels](https://mlsanity.com/paper/2503.14376/) (2025)
- [Systems and Algorithms for Convolutional Multi-Hybrid Language Models at Scale](https://mlsanity.com/paper/2503.01868/) (2025)
- [Parallelization of Non-linear State-Space Models: Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling](https://mlsanity.com/paper/2505.21717/) (2025)
- [Flash STU: Fast Spectral Transform Units](https://mlsanity.com/paper/2409.10489/) (2024)
- [Orchid: Flexible and Data-Dependent Convolution for Sequence Modeling](https://mlsanity.com/paper/2402.18508/) (2024)
- [Unlocking the Secrets of Linear Complexity Sequence Model from A Unified Perspective](https://mlsanity.com/paper/2405.17383/) (2024)
- [SE(3)-Hyena Operator for Scalable Equivariant Learning](https://mlsanity.com/paper/2407.01049/) (2024)
- [PACE: Pacing Operator Learning to Accurate Optical Field Simulation for Complicated Photonic Devices](https://mlsanity.com/paper/2411.03527/) (2024)
- [AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs](https://mlsanity.com/paper/2403.03772/) (2024)
- [A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic](https://mlsanity.com/paper/2410.12389/) (2024)
- [Flash Inference: Near Linear Time Inference for Long Convolution Sequence Models and Beyond](https://mlsanity.com/paper/2410.12982/) (2024)
- [Reparameterized Multi-Resolution Convolutions for Long Sequence Modelling](https://mlsanity.com/paper/2408.09453/) (2024)
- [Recurrence-Complete Frame-based Action Models](https://mlsanity.com/paper/2510.06828/) (2025)
- [Alias-Free ViT: Fractional Shift Invariance via Linear Attention](https://mlsanity.com/paper/2510.22673/) (2025)
- [Want to train KANS at scale? Now UKAN!](https://mlsanity.com/paper/2408.11200/) (2024)
- [Birdie: Advancing State Space Models with Reward-Driven Objectives and Curricula](https://mlsanity.com/paper/2411.01030/) (2024)
- [Otter Weather: Skillful and Computationally Efficient Medium-Range Weather Forecasting](https://mlsanity.com/paper/2606.26421/) (2026)
- [TileMaxSim: IO-Aware GPU MaxSim Scoring with Dimension Tiling and Fused Product Quantization](https://mlsanity.com/paper/2606.26439/) (2026)
- [Enabling Long FFT Convolutions on Memory-Constrained FPGAs via Chunking](https://mlsanity.com/paper/2601.06065/) (2025)

## Abstract (arXiv)

Convolution models with long filters have demonstrated state-of-the-art reasoning abilities in many long-sequence tasks but lag behind the most optimized Transformers in wall-clock time. A major bottleneck is the Fast Fourier Transform (FFT)--which allows long convolutions to run in O(N logN) time in sequence length N but has poor hardware utilization. In this paper, we study how to optimize the FFT convolution. We find two key bottlenecks: the FFT does not effectively use specialized matrix multiply units, and it incurs expensive I/O between layers of the memory hierarchy. In response, we propose FlashFFTConv. FlashFFTConv uses a matrix decomposition that computes the FFT using matrix multiply units and enables kernel fusion for long sequences, reducing I/O. We also present two sparse convolution algorithms--1) partial convolutions and 2) frequency-sparse convolutions--which can be implemented simply by skipping blocks in the matrix decomposition, enabling further opportunities for memory and compute savings. FlashFFTConv speeds up exact FFT convolutions by up to 7.93× over PyTorch and achieves up to 4.4× speedup end-to-end. Given the same compute budget, FlashFFTConv allows Hyena-GPT-s to achieve 2.3 points better perplexity on the PILE and M2-BERT-base to achieve 3.3 points higher GLUE score--matching models with twice the parameter count. FlashFFTConv also achieves 96.1% accuracy on Path-512, a high-resolution vision task where no model had previously achieved better than 50%. Furthermore, partial convolutions enable longer-sequence models--yielding the first DNA model that can process the longest human genes (2.3M base pairs)--and frequency-sparse convolutions speed up pretrained models while maintaining or improving model quality.