# HASTE: Hardware-Aware Dynamic Sparse Training for Large Output Spaces

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 34 references that are in the map.
- First posted on arXiv 31 May 2026.

## Builds on (most cited first, 23 of 23)

- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch](https://mlsanity.com/paper/2102.04010/) (2021)
- [The Hardware Lottery](https://mlsanity.com/paper/2009.06489/) (2020)
- [AttentionXML: Label Tree-based Attention-Aware Deep Model for High-Performance Extreme Multi-Label Text Classification](https://mlsanity.com/paper/1811.01727/) (2018)
- [DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification](https://mlsanity.com/paper/1609.02521/) (2016)
- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [Bonsai -- Diverse and Shallow Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/1904.08249/) (2019)
- [LightXML: Transformer with Dynamic Negative Sampling for High-Performance Extreme Multi-label Text Classification](https://mlsanity.com/paper/2101.03305/) (2021)
- [Dynamic Sparse Training with Structured Sparsity](https://mlsanity.com/paper/2305.02299/) (2023)
- [NGAME: Negative Mining-aware Mini-batching for Extreme Classification](https://mlsanity.com/paper/2207.04452/) (2022)
- [VENOM: A Vectorized N:M Format for Unleashing the Power of Sparse Tensor Cores](https://mlsanity.com/paper/2310.02065/) (2023)
- [CascadeXML: Rethinking Transformers for End-to-end Multi-resolution Training in Extreme Multi-label Classification](https://mlsanity.com/paper/2211.00640/) (2022)
- [S-STE: Continuous Pruning Function for Efficient 2:4 Sparse Pre-training](https://mlsanity.com/paper/2409.09099/) (2024)
- [Towards Memory-Efficient Training for Extremely Large Output Spaces -- Learning with 500k Labels on a Single Commodity GPU](https://mlsanity.com/paper/2306.03725/) (2023)
- [Generalized test utilities for long-tail performance in extreme multi-label classification](https://mlsanity.com/paper/2311.05081/) (2023)
- [Sign-In to the Lottery: Reparameterizing Sparse Training From Scratch](https://mlsanity.com/paper/2504.12801/) (2025)
- [SPLAT: A framework for optimised GPU code-generation for SParse reguLar ATtention](https://mlsanity.com/paper/2407.16847/) (2024)
- [Accelerating a Triton Fused Kernel for W4A16 Quantized Inference with SplitK work decomposition](https://mlsanity.com/paper/2402.00025/) (2024)
- [Navigating Extremes: Dynamic Sparsity in Large Output Spaces](https://mlsanity.com/paper/2411.03171/) (2024)
- [BLaST: High Performance Inference and Pretraining using BLock Sparse Transformers](https://mlsanity.com/paper/2507.03117/) (2025)
- [ELMO: Efficiency via Low-precision and Peak Memory Optimization in Large Output Spaces](https://mlsanity.com/paper/2510.11168/) (2025)

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

- [BARTER: Compact Dynamic Sparse Training with Standard Dense Kernels](https://mlsanity.com/paper/2610.16147/) (2026)

## Abstract (arXiv)

Extreme multi-label classification (XMC) involves learning models over large output spaces with millions of labels, making the output layer a memory-compute bottleneck. While sparsity-based methods reduce arithmetic complexity, they often fail to yield proportional speedups due to irregular memory access, poor hardware utilization, or reliance on auxiliary architectural components in long-tailed regimes. We introduce group-shared fixed fan-in sparsity, a semi-structured output-layer design in which semantically related labels share a sparse input pattern while retaining independent weights. This grouping introduces a task-aligned inductive bias -- encouraging related labels to share feature subsets -- while reducing index memory overhead, increasing feature reuse across labels, and enabling efficient GPU execution via custom CUDA kernels that leverage modern accelerator primitives. As an alternative to auxiliary objectives, we exploit the long-tailed structure of XMC by decomposing the output layer into a small dense head over frequent labels and a group-shared sparse tail over the remainder, providing an informative gradient pathway while preserving the memory benefits of sparsity. Through kernel-level microbenchmarking, we show that group-shared fixed fan-in translates arithmetic reductions into practical wall-clock gains, achieving up to 4.4× speedup in the forward pass and up to 25× speedup in backward passes over standard fixed fan-in sparsity, while operating within a few percent of a FLOPs-matched dense bottleneck. Across large-scale XMC benchmarks, our approach matches or improves precision@k over prior sparse baselines, while narrowing the performance gap to dense.