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

Nasib Ullah, Jinbin Zhang, Jean Lucien Randrianantenaina, Erik Schultheis, Rohit Babbar · 2026

Read HASTE: Hardware-Aware Dynamic Sparse Training for Large Output Spaces by Nasib Ullah, Jinbin Zhang, Jean Lucien Randrianantenaina, Erik Schultheis, Rohit Babbar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01117.txt.

Introduction

Ullah and co-authors make sparse output layers run fast on real chips in this 2026 paper. Extreme multi label classification sorts items into millions of labels. The output layer then eats memory and compute. Sparsity cuts the math, but irregular access and poor chip use often eat the gains. Long tailed label sets make it worse.

Their design, HASTE, uses group shared fixed fan in sparsity. Labels that mean near things share one sparse input pattern, each with its own weights. The grouping cuts index memory and reuses features across labels. Custom CUDA kernels turn the arithmetic savings into wall clock wins. The output layer splits in two: a small dense head for frequent labels, and a sparse tail for the rest. That split keeps a clean gradient path for rare labels. Kernel level microbenchmarks back the design, they report.

Catalog record

CREATORNasib Ullah, Jinbin Zhang, Jean Lucien Randrianantenaina, Erik Schultheis, Rohit Babbar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01117

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

HASTE: Hardware-Aware Dynamic Sparse Training for Large Output Spaces Nasib Ullah, Jinbin Zhang, Jean Lucien Randrianantenaina, Erik Schultheis, Rohit Babbar Abstract 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 × 4.4\times speedup in the forward pass and up to 25 × 25\times 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. (a) SPARTEX Encoder features size ( F_{s} ) S fan-in ( F_{in} ) label size ( L ) F_{s} Aux (b) HASTE Encoder F_{s} F_{in} GS Head F_{s} H T L (c) FLOPs 10M 100M 1.0B 1 1.5 2 2.5 3 3.5 4 4.5 5 Total FLOPs Wall-clock slowdown ( \times FLOPs-matched dense) Fixed fan-in Group-shared fixed fan-in FLOPs-matched dense (1.0 \times ) features labels S = fixed fan-in sparse layer features labels GS = group shared fixed fan-in layer label group features labels Block sparsity expressiveness speed expressiveness speed (d) Comparison of Sparsity Patterns Figure 1 : Architecture and Performance Overview. (a) Original Spartex . (b) Proposed Group-Shared architecture. (c) Performance benchmarks vs. FLOPs-matched dense (bottleneck) baseline. (d) Visual comparison of sparsity patterns showing trade-offs between expressiveness and speed. 1 Introduction In many real-world applications, such as tagging, product-to-product recommendation, or matching search queries to advertisements, the output space can be extremely large. Extreme multi-label classification (XMC) ( 3 ; 1 ; 2 ) , which trains classifiers over millions of labels, has therefore become central to several high-impact industrial systems. However, the enormous memory and computational demands, particularly that of the output layer of XMC models, has motivated a decade of research into more scalable training strategies. Early work explored label-tree-based dynamic negative sampling ( 18 ; 33 ; 20 ) and nearest-neighbor-based multistage methods ( 6 ; 7 ; 8 ) to reduce computational costs; however, these approaches largely left memory requirements unchanged. More recently, memory-efficient techniques such as skip-loss optimization ( 17 ) and training with low-precision via quantization ( 32 ) have been proposed to train state-of-the-art XMC models on consumer GPUs. As an alternative strand, there has been significant progress in training sparse neural networks ( 21 ; 9 ) . However, modern GPU architectures are optimized for dense, contiguous memory blocks; consequently, unstructured sparsity results in low hardware utilization and divergent execution paths. Therefore, most recent approaches for training sparse neural networks emphasize the need to simulate sparsity using dense masks ( 10 ) . However, an off-the-shelf application of these methods, simulating sparsity via dense masks, cannot potentially achieve any realistic savings in memory-intensive XMC settings. There have been attempts to find a middle ground between the two ends, (i) ill-suited nature of sparsity to GPU architecture and (ii) memory demands of dense (masked) training. In particular, a careful introduction of structure in the sparsity pattern via fixed fan-in per label in the output layer of XMC pipelines ( 26 ) partially addresses the GPU load balancing. In this vein, an example of an end-to-end training approach is Spartex ( 28 ) , which adopts semi-structured fixed fan-in sparsity ( 21 ) , where each output neuron connects to a fixed number of input features. This design reduces representational memory overhead and provides uniform load balancing across labels. Approaches such as Spartex , though successful in reducing the memory footprint, still face two fundamental limitations. Firstly , fixed fan-in sparsity per-label remains fundamentally memory-bound. For each label, it issues a fixed number of random, uncoalesced memory reads; although computation is parallelized across labels, the lack of shared feature access quickly saturates memory bandwidth on modern accelerators—an instance of the well-known memory wall ( 30 ) . This access pattern further limits utilization of Tensor Core units central to modern ML hardware. Improving efficiency, therefore, requires introducing structure into sparse feature access. Secondly , training in long-tailed regimes is prone to instability, as sparse connectivity provides weak and noisy gradient signals to the encoder. Spartex introduces an auxiliary objective that provides an additional gradient pathway to the encoder (Figure 1 .(a)). While effective in practice, this approach relies on auxiliary supervision that is not universally available and can be brittle: mismatches between auxiliary and primary objectives may introduce conflicting gradients, and auxiliary losses often require careful tuning. Moreover, in large-label regimes, the auxiliary branch can also incur nontrivial computational and memory overhead. In order to tackle the first limitation of memory-boundedness due to irregular memory accesses, two natural directions emerge: (i) increasing regularity to enable coalesced memory reads, and (ii) increasing feature reuse across labels to amortize data movement. Block sparsity ( 24 ) satisfies both by assigning contiguous blocks of features as the fan-in and sharing these blocks across groups of labels, yielding excellent hardware efficiency (Figure 1 .(b)). However, the strong regularity constraints imposed by block sparsity requiring features to be both contiguous and shared, significantly restrict model expressiveness and can degrade performance. In this work, we propose HASTE , a more flexible alternative based on group-shared fixed fan-in sparsity. Instead of assigning separate random fan-in locations to each label, we first form label groups, e.g., using semantic-based similarity, and assign each group a shared but randomly selected fan-in. This design preserves the benefits of feature reuse within label groups while enabling coalesced memory access patterns compatible with modern Tensor Core hardware. It also reduces representational memory overhead by a factor proportional to the group size. Importantly, it is also conceptually grounded in the structure of tasks: in applications such as product recommendation, semantically related products naturally benefit from accessing similar subsets of features. As shown in Figure 1 .(b), our approach sits between semi-structured fixed fan-in sparsity and fully regular block sparsity, striking a practical balance between latency and expressiveness. Figure 1 .(c) quantifies this trade-off via wall-clock slowdown measured relative to a FLOPs-matched dense bottleneck. To address the second limitation of the optimization challenges of training in long-tailed label distributions with sparse signals, we adopt a simpler, data-driven alternative by decomposing the label space itself. Specifically, we partition the label set into two disjoint subsets and

Read the complete text