# PIT: Optimization of Dynamic Sparse Deep Learning Models via Permutation Invariant Transformation

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 69 references that are in the map.
- First posted on arXiv 26 Jan 2023.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [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)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Masked Autoencoders Are Scalable Vision Learners](https://mlsanity.com/paper/2111.06377/) (2021)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (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)
- [Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting](https://mlsanity.com/paper/2012.07436/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding](https://mlsanity.com/paper/2006.16668/) (2020)
- [GLaM: Efficient Scaling of Language Models with Mixture-of-Experts](https://mlsanity.com/paper/2112.06905/) (2021)
- [DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification](https://mlsanity.com/paper/2106.02034/) (2021)
- [Once-for-All: Train One Network and Specialize it for Efficient Deployment](https://mlsanity.com/paper/1908.09791/) (2019)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [A Discourse-Aware Attention Model for Abstractive Summarization of Long Documents](https://mlsanity.com/paper/1804.05685/) (2018)
- [Multi-News: a Large-Scale Multi-Document Summarization Dataset and Abstractive Hierarchical Model](https://mlsanity.com/paper/1906.01749/) (2019)
- [Dynamic Neural Networks: A Survey](https://mlsanity.com/paper/2102.04906/) (2021)
- [ST-MoE: Designing Stable and Transferable Sparse Expert Models](https://mlsanity.com/paper/2202.08906/) (2022)
- [SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning](https://mlsanity.com/paper/2012.09852/) (2020)
- [MegaBlocks: Efficient Sparse Training with Mixture-of-Experts](https://mlsanity.com/paper/2211.15841/) (2022)
- [Ansor: Generating High-Performance Tensor Programs for Deep Learning](https://mlsanity.com/paper/2006.06762/) (2020)
- [Tutel: Adaptive Mixture-of-Experts at Scale](https://mlsanity.com/paper/2206.03382/) (2022)
- [AutoFormer: Searching Transformers for Visual Recognition](https://mlsanity.com/paper/2107.00651/) (2021)
- [Block Pruning For Faster Transformers](https://mlsanity.com/paper/2109.04838/) (2021)

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

- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [PowerInfer: Fast Large Language Model Serving with a Consumer-grade GPU](https://mlsanity.com/paper/2312.12456/) (2023)
- [Sparse VideoGen: Accelerating Video Diffusion Transformers with Spatial-Temporal Sparsity](https://mlsanity.com/paper/2502.01776/) (2025)
- [Sparse VideoGen2: Accelerate Video Generation with Sparse Attention via Semantic-Aware Permutation](https://mlsanity.com/paper/2505.18875/) (2025)
- [Towards Efficient Generative Large Language Model Serving: A Survey from Algorithms to Systems](https://mlsanity.com/paper/2312.15234/) (2023)
- [SCBench: A KV Cache-Centric Analysis of Long-Context Methods](https://mlsanity.com/paper/2412.10319/) (2024)
- [Region-Adaptive Sampling for Diffusion Transformers](https://mlsanity.com/paper/2502.10389/) (2025)
- [MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention](https://mlsanity.com/paper/2504.16083/) (2025)
- [Vision Transformers on the Edge: A Comprehensive Survey of Model Compression and Acceleration Strategies](https://mlsanity.com/paper/2503.02891/) (2025)
- [FSMoE: A Flexible and Scalable Training System for Sparse Mixture-of-Experts Models](https://mlsanity.com/paper/2501.10714/) (2025)
- [Scattered Mixture-of-Experts Implementation](https://mlsanity.com/paper/2403.08245/) (2024)
- [Toward Sustainable GenAI using Generation Directives for Carbon-Friendly Large Language Model Inference](https://mlsanity.com/paper/2403.12900/) (2024)
- [Neuralink: Fast LLM Inference on Smartphones with Neuron Co-Activation Linking](https://mlsanity.com/paper/2410.19274/) (2024)
- [PiKV: KV Cache Management System for Mixture of Experts](https://mlsanity.com/paper/2508.06526/) (2025)
- [PLM: Efficient Peripheral Language Models Hardware-Co-Designed for Ubiquitous Computing](https://mlsanity.com/paper/2503.12167/) (2025)
- [Elastic On-Device LLM Service](https://mlsanity.com/paper/2409.09071/) (2024)
- [Samoyeds: Accelerating MoE Models with Structured Sparsity Leveraging Sparse Tensor Cores](https://mlsanity.com/paper/2503.10725/) (2025)
- [AccelGen: Heterogeneous SLO-Guaranteed High-Throughput LLM Inference Serving for Diverse Applications](https://mlsanity.com/paper/2503.13737/) (2025)
- [Long Exposure: Accelerating Parameter-Efficient Fine-Tuning for LLMs under Shadowy Sparsity](https://mlsanity.com/paper/2510.15964/) (2025)
- [Input-Dependent Power Usage in GPUs](https://mlsanity.com/paper/2409.18324/) (2024)
- [DualSparse-MoE: Coordinating Tensor/Neuron-Level Sparsity with Expert Partition and Reconstruction](https://mlsanity.com/paper/2508.18376/) (2025)
- [MTraining: Distributed Dynamic Sparse Attention for Efficient Ultra-Long Context Training](https://mlsanity.com/paper/2510.18830/) (2025)
- [MosaicKV: Serving Long-Context LLM with Dynamic Two-D KV Cache Compression](https://mlsanity.com/paper/2607.00760/) (2026)
- [To 2:4 Sparsity and Beyond: Neuron-level Activation Function to Accelerate LLM Pre-Training](https://mlsanity.com/paper/2602.06183/) (2026)
- [SparSEEty: Extracting Tokens from Sparsity-Exploiting LLM Serving Systems via Deterministic Side Channels](https://mlsanity.com/paper/2608.02995/) (2026)

## Abstract (arXiv)

Dynamic sparsity, where the sparsity patterns are unknown until runtime, poses a significant challenge to deep learning. The state-of-the-art sparsity-aware deep learning solutions are restricted to pre-defined, static sparsity patterns due to significant overheads associated with preprocessing. Efficient execution of dynamic sparse computation often faces the misalignment between the GPU-friendly tile configuration for efficient execution and the sparsity-aware tile shape that minimizes coverage wastes (non-zero values in tensor). In this paper, we propose PIT, a deep-learning compiler for dynamic sparsity. PIT proposes a novel tiling mechanism that leverages Permutation Invariant Transformation (PIT), a mathematically proven property, to transform multiple sparsely located micro-tiles into a GPU-efficient dense tile without changing the computation results, thus achieving both high GPU utilization and low coverage waste. Given a model, PIT first finds feasible PIT rules for all its operators and generates efficient GPU kernels accordingly. At runtime, with the novel SRead and SWrite primitives, PIT rules can be executed extremely fast to support dynamic sparsity in an online manner. Extensive evaluation on diverse models shows that PIT can accelerate dynamic sparsity computation by up to 5.9x (average 2.43x) over state-of-the-art compilers.