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

Researchers introduce HASTE, a hardware-aware sparse training method for extreme multi-label classification that uses group-shared fixed fan-in sparsity to optimize GPU execution. The approach achieves up to 25x speedup in backward passes compared to standard sparse methods while maintaining competitive accuracy, addressing the memory-compute bottleneck in models with millions of output labels.

HASTE represents a significant advancement in making large-scale machine learning models more computationally efficient without sacrificing performance. The core innovation lies in recognizing that sparsity alone doesn't guarantee practical speedups—irregular memory access patterns and poor hardware utilization often negate theoretical complexity reductions. By grouping semantically related labels to share sparse input patterns while maintaining independent weights, the researchers introduce task-aligned bias that encourages feature reuse and enables custom CUDA kernels optimized for modern GPU architectures.

This work addresses a growing computational challenge in the AI field. As models scale to handle millions of labels in extreme multi-label classification tasks, the output layer becomes the primary bottleneck. Previous sparsity approaches failed because they didn't account for real-world hardware constraints—a critical gap between theoretical improvements and practical performance. HASTE bridges this gap through co-design of algorithm and hardware execution.

The decomposition strategy—using a dense head for frequent labels and sparse tail for others—proves particularly elegant. This leverages the natural long-tailed distribution in XMC problems while providing clear gradient pathways during training, eliminating the need for auxiliary loss functions that complicate optimization. The empirical results demonstrate substantial practical gains: 4.4x speedup in forward passes and up to 25x in backward passes versus standard fixed fan-in sparsity, with accuracy remaining competitive against both sparse and dense baselines.

For the AI research community, HASTE establishes that hardware-aware algorithm design delivers tangible benefits in production environments. The custom kernel implementation signals a shift toward more specialized, architecture-conscious methods rather than purely algorithmic improvements. This approach has implications for scaling large language models and recommendation systems where output spaces are similarly massive.

• →HASTE achieves up to 25x backward pass speedup over standard sparse methods through GPU-optimized kernel design and group-shared sparsity patterns.
• →Group-shared fixed fan-in sparsity reduces memory overhead while enabling semantic label grouping that improves feature reuse across related outputs.
• →Decomposing into dense head and sparse tail leverages long-tailed distributions in extreme multi-label classification without requiring auxiliary training objectives.
• →Hardware-algorithm co-design proves essential for converting theoretical complexity reductions into practical wall-clock speedups in real GPU execution.
• →Method maintains competitive accuracy against both sparse and dense baselines while operating within few percent of FLOPs-matched dense performance.