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

• URL: http://arxiv.org/abs/2606.01117v1
• Date: Sun, 31 May 2026 09:25:47 GMT
• Title: HASTE: Hardware-Aware Dynamic Sparse Training for Large Output Spaces
• Abstract summary: Extreme multi-label classification (XMC) involves learning models over large output spaces with millions of labels.<n>Group-shared fixed fan-in sparsity is a semi-structured output-layer design in which semantically related labels share a sparse input pattern.<n>We show that group-shared fixed fan-in arithmetic reduces into practical wall-clock gains.
• Score: 11.730547294888707
• License: http://creativecommons.org/licenses/by/4.0/
• 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\times$ speedup in the forward pass and up to $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.

Related papers

• Faster Than Flash: Exploiting Attention Sparsity for Efficient Long-Context Decoding [51.48425605758328]
  We present Faster Flash Decoding (FFD), a novel hardware-algorithm co-design framework designed to break the memory wall in long-context decoding.<n>FFD integrates the selector and computer into a fully fused kernel, replacing external metadata indices with content-aware scanning.<n>It achieves up to 11.6x kernel-level speedup and scaling to 256K context length, with 2.37x end-to-end throughput improvement.
  arXiv  Detail & Related papers  (2026-08-31T15:13:20Z)
• FluxBin: Flexible LUT-based Ultra-low-bit LLM Inference by Algorithm-Kernel Synergy [32.21687694159134]
  FluxBin is an algorithm that synerizes binary quantization with a highly optimized kernel.<n>FluxBin achieves up to $5.92times speedup and $10.19times energy savings.<n>This effectively enables the deployment of 70B-scale models on one single A100 bases with a $4times memory reduction.
  arXiv  Detail & Related papers  (2026-08-16T08:01:06Z)
• You Only Index Once: Cross-Layer Sparse Attention with Shared Routing [61.29627714699688]
  Cross-layer sparse attention (A) is built on top of KV-sharing architectures such as YOCO.<n>A single indexer computes token-level top-k selection once and reuses the resulting index across layers.<n>Results show CLSA is both accurate and efficient, achieving up to 7.6x decoding speedup and 17.1x overall throughput improvement at 128K context.
  arXiv  Detail & Related papers  (2026-06-04T17:54:04Z)
• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
  arXiv  Detail & Related papers  (2026-05-28T15:53:34Z)
• OScaR: The Occam's Razor for Extreme KV Cache Quantization in LLMs and Beyond [50.440302567029654]
  Multi-modal intelligence has made the Key-Value cache a dominant memory bottleneck for efficient deployment.<n>In this work, we revisit the inherent limitations of the per-channel quantization paradigm.<n>We propose OScaR, an accurate and lightweight KV cache compression framework for X-LLMs.
  arXiv  Detail & Related papers  (2026-05-19T10:53:03Z)
• Beyond N-gram: Data-Aware X-GRAM Extraction for Efficient Embedding Parameter Scaling [24.48256429931821]
  X-GRAM is a frequency-aware dynamic token-injection framework.<n>It employs hybrid hashing and alias mixing to compress the tail while preserving head capacity.<n>It refines retrieved vectors via normalized SwiGLU ShortConv to extract diverse local n-gram features.
  arXiv  Detail & Related papers  (2026-04-23T14:27:10Z)
• Self-Indexing KVCache: Predicting Sparse Attention from Compressed Keys [30.377113902938678]
  Existing approaches treat sparsity prediction and compression as separate modules, relying on auxiliary index structures to select relevant tokens, and on complex quantization schemes to reduce memory usage.<n>We propose a novel paradigm: treating the compressed key representation not merely as storage, but as a self-indexing structure that directly enables efficient attention.<n>By designing a sign-based 1-bit vector quantization (VQ) scheme, our method unifies compression and retrieval in a single, hardware-friendly format.
  arXiv  Detail & Related papers  (2026-03-15T05:02:17Z)
• Bishop: Sparsified Bundling Spiking Transformers on Heterogeneous Cores with Error-Constrained Pruning [5.421489676274393]
  We introduce the concept of Token-Time Bundle (TTB) accelerator, a container that bundles spiking data of a set of tokens over multiple time points.<n>Bishop is the first dedicated hardware computation architecture and HW/SW co-design framework for spiking-based workloads.
  arXiv  Detail & Related papers  (2025-05-18T07:42:58Z)
• A Universal Framework for Compressing Embeddings in CTR Prediction [68.27582084015044]
  We introduce a Model-agnostic Embedding Compression (MEC) framework that compresses embedding tables by quantizing pre-trained embeddings.<n>Our approach consists of two stages: first, we apply popularity-weighted regularization to balance code distribution between high- and low-frequency features.<n> Experiments on three datasets reveal that our method reduces memory usage by over 50x while maintaining or improving recommendation performance.
  arXiv  Detail & Related papers  (2025-02-21T10:12:34Z)
• COMPASS: A Compiler Framework for Resource-Constrained Crossbar-Array Based In-Memory Deep Learning Accelerators [6.172271429579593]
  We propose a compiler framework for resource-constrained crossbar-based processing-in-memory (PIM) deep neural network (DNN) accelerators.<n>We propose an algorithm to determine the optimal partitioning that divides the layers so that each partition can be accelerated on chip.
  arXiv  Detail & Related papers  (2025-01-12T11:31:25Z)
• ThinK: Thinner Key Cache by Query-Driven Pruning [63.13363917871414]
  Large Language Models (LLMs) have revolutionized the field of natural language processing, achieving unprecedented performance across a variety of applications.<n>This paper focuses on the long-context scenario, addressing the inefficiencies in KV cache memory consumption during inference.<n>We propose ThinK, a novel query-dependent KV cache pruning method designed to minimize attention weight loss while selectively pruning the least significant channels.
  arXiv  Detail & Related papers  (2024-07-30T17:59:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.