Sparse Tensor

A sparse tensor stores only non-zero values and their corresponding indices, discarding all zero elements. This is in stark contrast to a dense tensor, which allocates memory for every position in the multi-dimensional array. Common storage formats include:

• COO (Coordinate List): Stores a list of (index, value) tuples.
• CSR/CSC (Compressed Sparse Row/Column): Compresses row or column indices for more efficient matrix operations.
• ELLPACK: A format optimized for GPUs, storing non-zero values in a dense 2D array aligned by row. The choice of format is a critical engineering decision that balances memory efficiency with computational access patterns for specific operations like SpMM (Sparse Matrix-Matrix multiplication).

The distribution of non-zero values defines the sparsity pattern, which dictates computational efficiency. Key patterns include:

• Unstructured Sparsity: Non-zero values are randomly distributed. This offers the highest theoretical compression but requires specialized software or hardware (like NVIDIA's Ampere architecture Sparse Tensor Cores) for speedups.
• Structured Sparsity: Non-zero values follow a regular pattern, such as entire pruned channels or blocks (e.g., 2:4 or 4:8 sparsity). This pattern is more readily accelerated on standard hardware like CPUs and GPUs without exotic support.
• Semistructured Sparsity: A hybrid approach, like NVIDIA's 2:4 fine-grained sparsity, where two of every four elements are zero, balancing regularity with flexibility.

The efficacy of a sparse representation is quantified by its compression ratio and sparsity percentage.

• Sparsity Percentage: Calculated as (1 - (nnz / total_elements)) * 100%, where nnz is the number of non-zero values. A model with 95% sparsity has only 5% non-zero parameters.
• Theoretical Compression Ratio: The inverse of the density: total_elements / nnz. A 95% sparse tensor has a 20x theoretical compression ratio.
• Effective Compression: The actual memory savings depend on the overhead of the chosen storage format's index data. For very high sparsity (>99%), index overhead can become significant.

The primary benefit is the elimination of FLOPs (Floating Point Operations). Operations involving sparse tensors skip multiplications and additions with zero, leading to direct reductions in:

• Inference Latency: Faster execution by computing only meaningful operations.
• Energy Consumption: Fewer computations translate directly to lower power draw, a paramount concern for battery-powered edge devices.
• Memory Bandwidth Pressure: Loading only non-zero values and indices reduces data movement, which is often the bottleneck in modern systems. This enables larger, more capable models to fit within the limited SRAM of edge accelerators, avoiding slow DRAM access.

Sparsity in tensors can originate from two primary sources:

• Induced Sparsity (Model Sparsification): Created deliberately through techniques like pruning applied to neural network weights. The goal is to transform a dense, over-parameterized model into a sparse one with minimal accuracy loss. This is a core technique in edge model compression.
• Natural Sparsity: Inherent in the input data itself. Common examples include:
  • Bag-of-Words text representations.
  • User-item interaction matrices in recommendation systems.
  • 3D point clouds from LiDAR sensors.
  • Graph adjacency matrices for social or molecular networks. Leveraging natural sparsity is key for efficient on-device processing of sensor and user data.

Realizing the theoretical gains of sparsity requires co-designed software libraries and hardware support.

• Software Libraries: Frameworks like PyTorch (torch.sparse), TensorFlow, and cuSPARSE (NVIDIA) provide APIs for creating and manipulating sparse tensors and executing sparse linear algebra operations.
• Compiler Support: AI compilers like Apache TVM and MLIR include passes to identify, maintain, and optimize for sparsity patterns during graph compilation for target hardware.
• Hardware Acceleration: Modern AI accelerators feature dedicated units for sparse computation. NVIDIA Sparse Tensor Cores (from Ampere onward) and specialized NPU designs include circuitry to skip zero-valued weights and activations, delivering real-world speedups for pruned models.

The Coordinate (COO) format is the most intuitive sparse representation, storing three parallel arrays:

• Values: The non-zero elements.
• Row Indices: The row coordinate of each value.
• Column Indices: The column coordinate of each value.

It is highly flexible for constructing and modifying sparse tensors but inefficient for arithmetic operations due to unsorted indices. It's often used as an intermediate format before conversion to more efficient structures like CSR or CSC.

The Compressed Sparse Row (CSR) format is optimized for row-wise access and operations. It uses three arrays:

• Values: The non-zero values.
• Column Indices: The column index for each value.
• Row Pointers: An array of size rows + 1 where element i points to the start of row i in the values/column indices arrays.

CSR enables fast SpMV (Sparse Matrix-Vector Multiplication) and row slicing. It is the standard format for sparse linear algebra libraries like SciPy and Intel MKL. Its counterpart for column access is Compressed Sparse Column (CSC).

The ELLPACK (ELL) format is designed for vectorized and GPU-friendly computation. It stores data in two dense matrices of shape (rows, max_nonzeros_per_row):

• Data Matrix: Contains the non-zero values, padded with zeros.
• Column Indices Matrix: Contains the corresponding column indices, padded with an invalid index (e.g., -1).

This structure allows coalesced memory access on GPUs. However, performance degrades significantly if row lengths are highly irregular, leading to excessive zero padding. The HYB format often combines ELL with COO to handle tail rows.

The Block Compressed Sparse Row (BSR) format extends CSR by grouping non-zero elements into dense blocks. Instead of storing individual scalar values, it stores small, dense sub-matrices (e.g., 2x2, 4x4). Its arrays are:

• Block Values: The dense blocks.
• Block Column Indices: The block column index for each block.
• Block Row Pointers: Pointers to the start of each block row.

BSR exploits structure in problems with inherent blockiness (e.g., from PDE discretizations) to improve cache utilization and enable the use of optimized BLAS routines on the dense blocks.

The Compressed Sparse Fiber (CSF) format is a generalization of CSR for higher-order tensors (order > 2). It recursively compresses the tensor along each mode (dimension). The format is a tree-like structure where:

• The root node corresponds to the first mode and contains pointers.
• Each subsequent level corresponds to the next mode, eventually leading to leaf nodes containing the non-zero values.

CSF minimizes memory overhead for high-dimensional sparse data and can be more efficient than flattening a tensor into a 2D matrix. It is foundational for sparse tensor algebra libraries (e.g., SPLATT).

The Dictionary of Keys (DOK) format represents a sparse tensor using a Python dictionary (or hash map) where the key is a tuple of coordinates (i, j, k) and the value is the non-zero element at that location.

• Advantage: O(1) access time for random element lookup and efficient incremental construction.
• Disadvantage: Inefficient for sequential iteration and linear algebra operations due to hash table overhead.

DOK is primarily used for fast, dynamic building of sparse tensors in memory, after which it is typically converted to a COO or CSR format for computation.

Model sparsification is the process of inducing a high percentage of zero-valued parameters within a neural network's weight matrices. This is a core technique for creating models that can be stored and executed as sparse tensors. The goal is to reduce the memory footprint and enable computational shortcuts by skipping operations involving zeros.

• Primary Methods: Includes pruning (removing weights), regularization (encouraging weights to zero during training), and specialized sparse training algorithms.
• Sparsity Patterns: Can be unstructured (random zeros) or structured (entire channels/filters set to zero). Unstructured sparsity offers higher compression but requires specialized runtimes for speedup.

Unstructured pruning is a model compression technique that removes individual, less important weights from a neural network, resulting in an irregular, sparse pattern. This creates a model whose weights are a sparse tensor.

• Key Challenge: The irregular pattern does not align with standard dense matrix multiplication hardware, requiring sparse linear algebra libraries or specialized hardware (like NVIDIA's Sparsity support) to realize inference speedups.
• High Compression: Can achieve >90% sparsity with minimal accuracy loss, drastically reducing the model's storage size.

Compressed Sparse Row (CSR) is a standard storage format for representing a 2D sparse matrix (a 2D sparse tensor). It is a cornerstone format in sparse linear algebra libraries used for efficient sparse tensor computations.

• Storage Components: Uses three arrays:
  • values: Stores only the non-zero elements.
  • col_indices: Stores the column index for each non-zero value.
  • row_ptr: Stores the cumulative count of non-zeros up to each row.
• Efficiency: Enables faster row-wise operations and is memory-efficient for very sparse matrices. Variants like Compressed Sparse Column (CSC) exist for column-wise operations.

Sparse neural network execution refers to the software and hardware systems designed to perform inference or training on models with sparse weights and/or activations. This is where the theoretical benefits of sparse tensors are realized in practice.

• Software Runtimes: Frameworks like PyTorch with torch.sparse, TensorFlow, and specialized kernels in ONNX Runtime provide APIs for sparse tensor operations.
• Hardware Support: Modern AI accelerators (e.g., NVIDIA Ampere+ GPUs, some NPUs) include features to skip computations with zero values, turning sparsity into direct latency and power savings.

The Lottery Ticket Hypothesis is a research finding that within a large, dense neural network, there exists a much smaller, sparse subnetwork (a 'winning ticket') that, when trained from its original initialization, can match the accuracy of the full network. This provides a theoretical basis for pruning and sparsification.

• Implication for Sparsity: Suggests that highly accurate, inherently sparse architectures exist within dense models, waiting to be discovered via pruning algorithms.
• Iterative Pruning: A common method to find these tickets involves training, pruning a percentage of smallest weights, resetting the remaining weights to their original values, and repeating.

Coordinate Format (COO) is a simple, flexible storage scheme for sparse tensors. It explicitly stores a list of tuples, each containing the indices of a non-zero element and its value. It is often used as an intermediate format.

• Structure: For an N-dimensional tensor, each non-zero entry is stored as (index_1, index_2, ..., index_N, value).
• Use Case: Intuitive and easy to construct, making it ideal for incremental construction of sparse tensors. It can be less efficient for mathematical operations than formats like CSR or CSC, which are often derived from COO for computation.