CSR Format (Compressed Sparse Row)

CSR represents a sparse matrix using three one-dimensional arrays:

• values (val or data): Stores all non-zero values in row-major order.
• column_indices (col_idx): Stores the column index for each corresponding non-zero value.
• row_pointers (row_ptr): Stores the cumulative number of non-zero elements up to each row. The non-zero values for row i are found in values[row_ptr[i]:row_ptr[i+1]].

This structure eliminates the storage of zeros, trading memory for the overhead of storing explicit indices.

The row_pointers array enables constant-time lookup to find the start and end of any row's non-zero elements. This makes CSR exceptionally efficient for algorithms that iterate over rows, such as:

• Sparse Matrix-Vector Multiplication (SpMV): The canonical operation where CSR excels.
• Row slicing and access.
• Forward passes in neural networks, which are often expressed as sequences of SpMV-like operations.

Its efficiency diminishes for operations requiring fast column access, for which the Compressed Sparse Column (CSC) format is better suited.

For an M x N matrix with NZ non-zeros, CSR storage cost is:

• values: NZ elements.
• column_indices: NZ integer elements.
• row_pointers: M + 1 integer elements.

This is typically far smaller than the dense M * N storage. The break-even point depends on the sparsity level and the bit-width of the indices. For highly sparse weight matrices in pruned models, CSR can reduce memory footprint by 10x or more compared to dense storage.

Executing Sparse Matrix-Dense Matrix Multiplication (SpMM)—the workhorse of sparse inference—with CSR involves a nested loop:

1. Outer loop iterates over rows (i).
2. Inner loop iterates over non-zeros in row i (using row_ptr).
3. For each non-zero, multiply it with the corresponding row of the dense input matrix (indexed by col_idx).

Performance is dominated by indirect memory access (gather) into the dense matrix and potential load imbalance if rows have highly variable non-zero counts. Optimized SpMM kernels use techniques like row grouping and warp-level parallelism to mitigate these issues.

CSR is often compared to the simpler Coordinate (COO) Format, which stores a list of (row, column, value) tuples.

CSR is generally preferred for efficient computation, while COO is useful for incremental matrix construction before conversion.

Efficient execution of CSR-based models depends on the underlying hardware and software stack:

• GPUs with Sparse Tensor Cores (e.g., NVIDIA Ampere+): Can accelerate CSR/SpMM but often require a structured sparsity pattern (e.g., 2:4) for peak performance, necessitating a conversion from the unstructured CSR format.
• Compiler Mapping: AI compilers (e.g., TVM, MLIR) must map the abstract CSR operations to optimized gather-compute-scatter kernels on the target architecture.
• Overhead: The sparse efficiency gap is real; the theoretical FLOP reduction from sparsity is offset by kernel overhead for index processing and irregular memory access. Profiling is essential.

The CSR format represents a sparse matrix using three one-dimensional arrays:

• data: Stores all non-zero values in row-major order.
• indices: Stores the column index for each corresponding non-zero value in the data array.
• indptr (index pointer): Stores the start and end indices in the data and indices arrays for each row. For row i, non-zero values are found at data[indptr[i]:indptr[i+1]] with column indices indices[indptr[i]:indptr[i+1]]. This structure eliminates the storage of zeros, compressing memory footprint, but introduces indirect memory access via the indices array.

The primary operation enabled by CSR is Sparse Matrix-Dense Matrix Multiplication (SpMM), a key kernel in sparse neural network inference. For a sparse weight matrix W in CSR and a dense input activation matrix X, the output Y = W @ X is computed row-by-row:

• Each row of W defines a sparse dot product.
• The indptr array allows efficient iteration over rows.
• For each non-zero weight W[i, j] at column j, the operation gathers the dense vector X[j, :], multiplies it by the weight, and scatters the result into Y[i, :]. Performance hinges on optimizing these gather-scatter operations and managing load imbalance from varying row lengths.

Major frameworks provide specialized APIs and backends for CSR:

• PyTorch: Offers torch.sparse_csr tensor type with operators like torch.sparse.mm() for SpMM. Sparse tensors can be created from dense ones via to_sparse_csr(). The TorchInductor compiler can fuse sparse operations.
• TensorFlow / JAX: Use scipy.sparse.csr_matrix as an interoperable standard. JAX's jax.experimental.sparse module provides JIT-compatible CSR operations. TensorFlow has historical support via tf.sparse.SparseTensor (in COO format, convertible to CSR).
• Framework Kernels: These APIs dispatch to optimized backend libraries like cuSPARSE (NVIDIA GPU), MKL (Intel CPU), or Eigen for actual computation, abstracting the complex kernel implementation.

While CSR is versatile, its irregular memory access pattern poses challenges for peak hardware utilization:

• GPU Execution: NVIDIA's Sparse Tensor Cores (on Ampere+ GPUs) do not natively support arbitrary CSR. They require the 2:4 fine-grained structured sparsity pattern, where a custom compressed format is used. Generic CSR SpMM relies on cuSPARSE libraries which can suffer from load imbalance and metadata overhead.
• CPU Execution: Optimized MKL/OpenBLAS kernels use vectorization, but performance is often memory-bandwidth bound due to indirect accesses.
• Specialized NPUs: Many edge AI accelerators have dedicated units for structured sparsity (e.g., channel pruning). Irregular CSR from unstructured pruning may not achieve peak throughput, leading to the sparse efficiency gap. The choice between CSR and other formats (like Blocked CSR) is a hardware-aware decision.

A critical concept in sparse inference is that the theoretical FLOP reduction from pruning does not translate linearly to speedup. With CSR, this gap is caused by:

• Kernel Overhead: Decoding indptr and indices arrays, conditional branching, and pointer chasing add fixed costs.
• Inefficient Memory Access: The gather of dense inputs via indices results in non-contiguous, cache-unfriendly reads, often stalling the compute pipeline.
• Load Imbalance: Rows with vastly different numbers of non-zeros cause thread divergence in parallel execution, leaving some cores idle. Thus, a model with 90% weight sparsity (a 10x FLOP reduction) may only achieve a 2-3x actual speedup using generic CSR kernels, emphasizing the need for hardware-aligned sparsity patterns.

CSR is one of several sparse storage formats, each with trade-offs:

• CSC (Compressed Sparse Column): The column-major analogue of CSR. Optimal for operations that access columns of the sparse matrix.
• COO (Coordinate Format): Stores explicit (row, column, value) tuples. Simpler to construct but often less efficient for SpMM due to lack of row compression.
• Blocked CSR (BSR): Groups non-zeros into small dense blocks (e.g., 4x4). Improves memory access regularity and enables use of vector/SIMD units, trading some sparsity for better hardware utilization.
• Structured Sparsity Formats (e.g., 2:4): Used by NVIDIA Sparse Tensor Cores. Stores a compressed matrix of non-zero values plus a bitmask, enabling predictable, aligned memory accesses and 2x theoretical speedup on supported GPUs.

A sparse tensor storage format that explicitly stores a list of (row, column, value) tuples for each non-zero element. It offers simplicity and ease of construction but can have higher memory overhead for arithmetic operations compared to compressed formats like CSR or CSC. COO is often used as an intermediate representation before conversion to a more compute-efficient format.

The fundamental computational kernel for multiplying a sparse matrix by a dense matrix. It is the core operation in sparse linear layers and attention projections. Efficient SpMM implementations for formats like CSR must:

• Skip multiplications with zero elements.
• Efficiently gather input values using column indices.
• Scatter and accumulate partial results across rows. Performance is heavily dependent on the sparse data layout and memory access patterns.

Fundamental parallel computing primitives critical for sparse computation. Gather collects data from non-contiguous memory addresses (specified by an index array) into a contiguous vector for processing. Scatter writes a contiguous result vector back to non-contiguous addresses. In CSR-based SpMM, gather is used to fetch the dense input values corresponding to sparse column indices, and scatter is used to accumulate outputs into the correct row locations.

A specialized hardware unit within modern NVIDIA GPUs (Ampere architecture and later) designed to accelerate sparse matrix operations. It leverages a structured 2:4 sparsity pattern, where in every block of 4 weights, 2 must be zero. This pattern allows the hardware to effectively double the theoretical compute throughput for dense matrix math by skipping the zero operations. While more restrictive than the unstructured sparsity stored in CSR, it represents a major hardware-in-the-loop optimization for sparse inference.

A software runtime or framework component specifically designed to load and execute sparse neural network models. It contains optimized kernels (like SpMM) for target hardware (CPUs, GPUs, NPUs) that understand formats like CSR. Examples include specialized backends in TensorFlow Lite, PyTorch with torch.sparse, and proprietary vendor SDKs. The engine manages the decoding of sparse formats, memory allocation, and scheduling to maximize hardware utilization.

The observed performance difference between the theoretical speedup predicted by the reduction in FLOPs (from zero-skipping) and the actual speedup achieved on hardware. This gap is caused by overheads inherent to sparse computation, including:

• Metadata processing: Decoding CSR row pointers and column indices.
• Irregular memory access: Leading to poor cache utilization and memory bandwidth saturation.
• Load imbalance: Where threads process rows with vastly different numbers of non-zeros. Bridging this gap is a primary goal of kernel and hardware optimization.