# Butterfly Transform: An Efficient FFT Based Neural Architecture Design

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2019.

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

- [Mobile-Former: Bridging MobileNet and Transformer](https://mlsanity.com/paper/2108.05895/) (2021)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Simple Hardware-Efficient Long Convolutions for Sequence Modeling](https://mlsanity.com/paper/2302.06646/) (2023)
- [Deep Frequency Filtering for Domain Generalization](https://mlsanity.com/paper/2203.12198/) (2022)
- [MicroNet: Improving Image Recognition with Extremely Low FLOPs](https://mlsanity.com/paper/2108.05894/) (2021)
- [Rethinking Neural Operations for Diverse Tasks](https://mlsanity.com/paper/2103.15798/) (2021)
- [Enabling Design Methodologies and Future Trends for Edge AI: Specialization and Co-design](https://mlsanity.com/paper/2103.15750/) (2021)
- [MoCoViT: Mobile Convolutional Vision Transformer](https://mlsanity.com/paper/2205.12635/) (2022)
- [ButterflyQuant: Ultra-low-bit LLM Quantization through Learnable Orthogonal Butterfly Transforms](https://mlsanity.com/paper/2509.09679/) (2025)
- [Nonlinear Initialization Methods for Low-Rank Neural Networks](https://mlsanity.com/paper/2202.00834/) (2022)
- [Governance-Aware Hybrid Fine-Tuning for Multilingual Large Language Models](https://mlsanity.com/paper/2512.17344/) (2025)
- [Efficient Joint Detection and Multiple Object Tracking with Spatially Aware Transformer](https://mlsanity.com/paper/2211.05654/) (2022)
- [Dimension Mixer: Group Mixing of Input Dimensions for Efficient Function Approximation](https://mlsanity.com/paper/2311.18735/) (2023)
- [Fast Inference with Kronecker-Sparse Matrices](https://mlsanity.com/paper/2405.15013/) (2024)

## Abstract (arXiv)

In this paper, we show that extending the butterfly operations from the FFT algorithm to a general Butterfly Transform (BFT) can be beneficial in building an efficient block structure for CNN designs. Pointwise convolutions, which we refer to as channel fusions, are the main computational bottleneck in the state-of-the-art efficient CNNs (e.g. MobileNets ). We introduce a set of criteria for channel fusion and prove that BFT yields an asymptotically optimal FLOP count with respect to these criteria. By replacing pointwise convolutions with BFT, we reduce the computational complexity of these layers from O(n2) to O(nlog n) with respect to the number of channels. Our experimental evaluations show that our method results in significant accuracy gains across a wide range of network architectures, especially at low FLOP ranges. For example, BFT results in up to a 6.75% absolute Top-1 improvement for MobileNetV1, 4.4 % for ShuffleNet V2 and 5.4% for MobileNetV3 on ImageNet under a similar number of FLOPS. Notably, ShuffleNet-V2+BFT outperforms state-of-the-art architecture search methods MNasNet, FBNet and MobilenetV3 in the low FLOP regime.