# Adaptable Butterfly Accelerator for Attention-based NNs via Hardware and Algorithm Co-design

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 49 references that are in the map.
- First posted on arXiv 20 Sep 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [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)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [MLP-Mixer: An all-MLP Architecture for Vision](https://mlsanity.com/paper/2105.01601/) (2021)
- [Cross-lingual Language Model Pretraining](https://mlsanity.com/paper/1901.07291/) (2019)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [FNet: Mixing Tokens with Fourier Transforms](https://mlsanity.com/paper/2105.03824/) (2021)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning](https://mlsanity.com/paper/2012.09852/) (2020)
- [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)
- [A3: Accelerating Attention Mechanisms in Neural Networks with Approximation](https://mlsanity.com/paper/2002.10941/) (2020)
- [A Tensorized Transformer for Language Modeling](https://mlsanity.com/paper/1906.09777/) (2019)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [EdgeBERT: Sentence-Level Energy Optimizations for Latency-Aware Multi-Task NLP Inference](https://mlsanity.com/paper/2011.14203/) (2020)
- [A General Survey on Attention Mechanisms in Deep Learning](https://mlsanity.com/paper/2203.14263/) (2022)
- [FTRANS: Energy-Efficient Acceleration of Transformers using FPGA](https://mlsanity.com/paper/2007.08563/) (2020)

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

- [A Survey on Efficient Inference for Large Language Models](https://mlsanity.com/paper/2404.14294/) (2024)
- [Full Stack Optimization of Transformer Inference: a Survey](https://mlsanity.com/paper/2302.14017/) (2023)
- [FlightLLM: Efficient Large Language Model Inference with a Complete Mapping Flow on FPGAs](https://mlsanity.com/paper/2401.03868/) (2024)
- [MELTing point: Mobile Evaluation of Language Transformers](https://mlsanity.com/paper/2403.12844/) (2024)
- [A Survey of Techniques for Optimizing Transformer Inference](https://mlsanity.com/paper/2307.07982/) (2023)
- [Duplex: A Device for Large Language Models with Mixture of Experts, Grouped Query Attention, and Continuous Batching](https://mlsanity.com/paper/2409.01141/) (2024)
- [On Efficient Training of Large-Scale Deep Learning Models: A Literature Review](https://mlsanity.com/paper/2304.03589/) (2023)
- [PIM Is All You Need: A CXL-Enabled GPU-Free System for Large Language Model Inference](https://mlsanity.com/paper/2502.07578/) (2025)
- [ShiftAddViT: Mixture of Multiplication Primitives Towards Efficient Vision Transformer](https://mlsanity.com/paper/2306.06446/) (2023)
- [The Future of Consumer Edge-AI Computing](https://mlsanity.com/paper/2210.10514/) (2022)
- [LightMamba: Efficient Mamba Acceleration on FPGA with Quantization and Hardware Co-design](https://mlsanity.com/paper/2502.15260/) (2025)
- [HG-PIPE: Vision Transformer Acceleration with Hybrid-Grained Pipeline](https://mlsanity.com/paper/2407.17879/) (2024)
- [PQA: Exploring the Potential of Product Quantization in DNN Hardware Acceleration](https://mlsanity.com/paper/2305.18334/) (2023)
- [Sparse-DySta: Sparsity-Aware Dynamic and Static Scheduling for Sparse Multi-DNN Workloads](https://mlsanity.com/paper/2310.11096/) (2023)
- [SWAT: Scalable and Efficient Window Attention-based Transformers Acceleration on FPGAs](https://mlsanity.com/paper/2405.17025/) (2024)
- [Efficient N:M Sparse DNN Training Using Algorithm, Architecture, and Dataflow Co-Design](https://mlsanity.com/paper/2309.13015/) (2023)
- [M4BRAM: Mixed-Precision Matrix-Matrix Multiplication in FPGA Block RAMs](https://mlsanity.com/paper/2311.02758/) (2023)
- [When Monte-Carlo Dropout Meets Multi-Exit: Optimizing Bayesian Neural Networks on FPGA](https://mlsanity.com/paper/2308.06849/) (2023)
- [MCBP: A Memory-Compute Efficient LLM Inference Accelerator Leveraging Bit-Slice-enabled Sparsity and Repetitiveness](https://mlsanity.com/paper/2509.10372/) (2025)
- [TreeQ: Pushing the Quantization Boundary of Diffusion Transformer via Tree-Structured Mixed-Precision Search](https://mlsanity.com/paper/2512.06353/) (2025)
- [A Dataflow Compiler for Efficient LLM Inference using Custom Microscaling Formats](https://mlsanity.com/paper/2307.15517/) (2023)
- [Co-Designing Binarized Transformer and Hardware Accelerator for Efficient End-to-End Edge Deployment](https://mlsanity.com/paper/2407.12070/) (2024)
- [ITERA-LLM: Boosting Sub-8-Bit Large Language Model Inference via Iterative Tensor Decomposition](https://mlsanity.com/paper/2505.08981/) (2025)
- [BitStopper: An Efficient Transformer Attention Accelerator via Stage-fusion and Early Termination](https://mlsanity.com/paper/2512.06457/) (2025)
- [Dimension Mixer: Group Mixing of Input Dimensions for Efficient Function Approximation](https://mlsanity.com/paper/2311.18735/) (2023)
- [Enhancing Dropout-based Bayesian Neural Networks with Multi-Exit on FPGA](https://mlsanity.com/paper/2406.14593/) (2024)
- [Accelerating MRI Uncertainty Estimation with Mask-based Bayesian Neural Network](https://mlsanity.com/paper/2407.05521/) (2024)
- [Accelerating Sparse Transformer Inference on GPU](https://mlsanity.com/paper/2506.06095/) (2025)
- [Efficient In-Memory Acceleration of Sparse Block Diagonal LLMs](https://mlsanity.com/paper/2510.11192/) (2025)
- [Efficient Tensor Completion Algorithms for Highly Oscillatory Operators](https://mlsanity.com/paper/2510.17734/) (2025)

## Abstract (arXiv)

Attention-based neural networks have become pervasive in many AI tasks. Despite their excellent algorithmic performance, the use of the attention mechanism and feed-forward network (FFN) demands excessive computational and memory resources, which often compromises their hardware performance. Although various sparse variants have been introduced, most approaches only focus on mitigating the quadratic scaling of attention on the algorithm level, without explicitly considering the efficiency of mapping their methods on real hardware designs. Furthermore, most efforts only focus on either the attention mechanism or the FFNs but without jointly optimizing both parts, causing most of the current designs to lack scalability when dealing with different input lengths. This paper systematically considers the sparsity patterns in different variants from a hardware perspective. On the algorithmic level, we propose FABNet, a hardware-friendly variant that adopts a unified butterfly sparsity pattern to approximate both the attention mechanism and the FFNs. On the hardware level, a novel adaptable butterfly accelerator is proposed that can be configured at runtime via dedicated hardware control to accelerate different butterfly layers using a single unified hardware engine. On the Long-Range-Arena dataset, FABNet achieves the same accuracy as the vanilla Transformer while reducing the amount of computation by 10 to 66 times and the number of parameters 2 to 22 times. By jointly optimizing the algorithm and hardware, our FPGA-based butterfly accelerator achieves 14.2 to 23.2 times speedup over state-of-the-art accelerators normalized to the same computational budget. Compared with optimized CPU and GPU designs on Raspberry Pi 4 and Jetson Nano, our system is up to 273.8 and 15.1 times faster under the same power budget.