# ButterflyFlow: Building Invertible Layers with Butterfly Matrices

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 42 references that are in the map.
- First posted on arXiv 28 Sep 2022.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Analyzing and Improving the Image Quality of StyleGAN](https://mlsanity.com/paper/1912.04958/) (2019)
- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [Video Diffusion Models](https://mlsanity.com/paper/2204.03458/) (2022)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [DiffWave: A Versatile Diffusion Model for Audio Synthesis](https://mlsanity.com/paper/2009.09761/) (2020)
- [Normalizing Flows for Probabilistic Modeling and Inference](https://mlsanity.com/paper/1912.02762/) (2019)
- [NICE: Non-linear Independent Components Estimation](https://mlsanity.com/paper/1410.8516/) (2014)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Masked Autoregressive Flow for Density Estimation](https://mlsanity.com/paper/1705.07057/) (2017)
- [NVAE: A Deep Hierarchical Variational Autoencoder](https://mlsanity.com/paper/2007.03898/) (2020)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [Invertible Residual Networks](https://mlsanity.com/paper/1811.00995/) (2018)
- [Flow++: Improving Flow-Based Generative Models with Variational Dequantization and Architecture Design](https://mlsanity.com/paper/1902.00275/) (2019)
- [Residual Flows for Invertible Generative Modeling](https://mlsanity.com/paper/1906.02735/) (2019)
- [Parallel WaveNet: Fast High-Fidelity Speech Synthesis](https://mlsanity.com/paper/1711.10433/) (2017)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [Densely connected normalizing flows](https://mlsanity.com/paper/2106.04627/) (2021)
- [VFlow: More Expressive Generative Flows with Variational Data Augmentation](https://mlsanity.com/paper/2002.09741/) (2020)
- [Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps](https://mlsanity.com/paper/2012.14966/) (2020)
- [MaCow: Masked Convolutional Generative Flow](https://mlsanity.com/paper/1902.04208/) (2019)
- [Emerging Convolutions for Generative Normalizing Flows](https://mlsanity.com/paper/1901.11137/) (2019)
- [The Convolution Exponential and Generalized Sylvester Flows](https://mlsanity.com/paper/2006.01910/) (2020)
- [Invertible DenseNets with Concatenated LipSwish](https://mlsanity.com/paper/2102.02694/) (2021)

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

- [Concrete Score Matching: Generalized Score Matching for Discrete Data](https://mlsanity.com/paper/2211.00802/) (2022)
- [Counterfactual Identifiability of Bijective Causal Models](https://mlsanity.com/paper/2302.02228/) (2023)
- [On Efficient Training of Large-Scale Deep Learning Models: A Literature Review](https://mlsanity.com/paper/2304.03589/) (2023)
- [Maximum Entropy Reinforcement Learning via Energy-Based Normalizing Flow](https://mlsanity.com/paper/2405.13629/) (2024)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [Anomaly Detection with Variance Stabilized Density Estimation](https://mlsanity.com/paper/2306.00582/) (2023)
- [Training Energy-Based Normalizing Flow with Score-Matching Objectives](https://mlsanity.com/paper/2305.15267/) (2023)
- [FInC Flow: Fast and Invertible k × k Convolutions for Normalizing Flows](https://mlsanity.com/paper/2301.09266/) (2023)
- [CDFlow: Building Invertible Layers with Circulant and Diagonal Matrices](https://mlsanity.com/paper/2510.25323/) (2025)
- [Kernelised Normalising Flows](https://mlsanity.com/paper/2307.14839/) (2023)
- [MixerFlow: MLP-Mixer meets Normalising Flows](https://mlsanity.com/paper/2310.16777/) (2023)
- [Parallel Backpropagation for Inverse of a Convolution with Application to Normalizing Flows](https://mlsanity.com/paper/2410.14634/) (2024)

## Abstract (arXiv)

Normalizing flows model complex probability distributions using maps obtained by composing invertible layers. Special linear layers such as masked and 1x1 convolutions play a key role in existing architectures because they increase expressive power while having tractable Jacobians and inverses. We propose a new family of invertible linear layers based on butterfly layers, which are known to theoretically capture complex linear structures including permutations and periodicity, yet can be inverted efficiently. This representational power is a key advantage of our approach, as such structures are common in many real-world datasets. Based on our invertible butterfly layers, we construct a new class of normalizing flow models called ButterflyFlow. Empirically, we demonstrate that ButterflyFlows not only achieve strong density estimation results on natural images such as MNIST, CIFAR-10, and ImageNet 32x32, but also obtain significantly better log-likelihoods on structured datasets such as galaxy images and MIMIC-III patient cohorts -- all while being more efficient in terms of memory and computation than relevant baselines.