AI Revolutionized by Sparsity: Towards More Efficient Models

The Rise of AI Models and Their Energy Challenges

In the field of artificial intelligence, model size is often synonymous with power. Language models, or LLMs, are at the heart of this dynamic. However, increasing their size does not come without problems. While some experts point out that growing model size can lead to diminishing returns in terms of performance, companies continue to develop increasingly larger tools. For example, the latest version of Llama, developed by Meta, stands out with its 2 trillion parameters.

This exponential growth of models is accompanied by an increase in energy needs and the time required to run them, significantly burdening their carbon footprint. In response to these challenges, researchers have explored the possibility of creating smaller models that use lower precision numbers for parameters to reduce energy consumption.

However, another promising approach involves leveraging the zeros present in these massive models. Indeed, in many models, a large portion of the parameters, such as weights and activations, are either zeros or so close to zero that they can be treated as such without compromising accuracy. This characteristic, known as sparsity, offers an opportunity to significantly reduce computational needs: instead of wasting time and energy multiplying or adding zeros, these operations can be omitted, and only the non-zero parameters need to be stored in memory.

Sparsity: A Key Concept for Efficiency

Neural networks and the data they manipulate are often represented in the form of numerical arrays, which can be vectors, matrices, or tensors. When an array primarily contains zeros, it is referred to as sparse. Sparsity can be natural or induced. For example, a social network is naturally sparse: each node represents a person, and each link represents a friendship, but most people are not friends with each other, resulting in a matrix predominantly composed of zeros.

In the case of a four-by-four matrix, it occupies 16 memory spaces, regardless of the proportion of zeros. If it is sparse, it can be more efficiently represented in the form of a fibertree, a structure that only stores the coordinates and non-zero values. This method reduces the memory space required.

In addition to natural sparsity, it is possible to induce sparsity in an AI model. For example, the company Cerebras has demonstrated that it is possible to set up to 70 to 80% of the parameters of a language model to zero without significant loss of accuracy, as was achieved with Meta's Llama 7B model.

The Benefits of Sparsity

The efficiency of sparse computation relies on two fundamental principles: zero compression and the mathematical properties of zeros. Algorithms and hardware dedicated to sparse computation exploit these two ideas.

First, sparse data can be compressed, making their storage in memory more efficient. For example, a four-by-four matrix with only three non-zero elements traditionally requires 16 memory spaces. By compressing it, only the non-zero elements are retained, thus reducing the required memory space.

Second, the mathematical properties of zero allow for the avoidance of many calculations. Multiplying any number by zero always yields zero, so multiplication can be omitted. Similarly, adding zero to a number does not change that number, allowing addition to be avoided.

In the context of a matrix-vector multiplication, a common operation in AI workloads, only calculations involving non-zero elements are necessary. For example, in a four-by-four matrix and a vector of four numbers, only two multiplications are needed in a sparse calculation, compared to 16 in a dense calculation.

The Limitations of Current GPUs and CPUs

Unfortunately, modern computing hardware is not designed to fully leverage sparsity. For instance, in a matrix-vector multiplication, a traditional CPU would multiply each element of the vector sequentially, which is slow. CPUs with vector support or GPUs can perform these multiplications in parallel, thus speeding up the process. However, if the data is extremely sparse, these devices spend most of their time multiplying by zero, which is inefficient.

Modern GPUs can exploit sparsity, but only in a particular form called structured sparsity, which assumes that two of the four adjacent parameters are zero. However, some models benefit more from unstructured sparsity, where any parameter can be zero, regardless of its position. GPUs can execute unstructured sparse calculations via software libraries like cuSparse, but support is often limited, and the hardware is underutilized, wasting energy.

Modern CPUs, while more flexible, are often slowed down by the indirect searches required to find non-zero data. They pre-load data based on what they anticipate needing, but...

Stanford's Innovation: Revolutionary Hardware

At Stanford University, a group of researchers has made a significant breakthrough by developing hardware capable of efficiently handling all types of workloads, whether sparse or traditional. This innovative hardware has been designed to fully exploit sparsity, allowing for substantial energy savings.

The results obtained with this new hardware are impressive. On average, the developed chip consumes one-sixtieth of the energy required by a traditional CPU while executing calculations eight times faster. This advancement has been made possible through a complete rethinking of the hardware, low-level firmware, and application software, all redesigned to take advantage of sparsity.

Stanford researchers hope that this innovation is just the beginning of a new era of developing more energy-efficient hardware and AI models. By optimizing the use of sparsity, they are paving the way for AI models that not only maintain high performance but also reduce their environmental impact.

What is Sparsity?

Neural networks, along with the data that feeds them, are represented in the form of arrays of numbers. These arrays can be one-dimensional (vectors), two-dimensional (matrices), or more (tensors). A sparse vector, matrix, or tensor primarily contains zero elements. The level of sparsity varies, but when zeros represent more than 50% of any type of array, it can benefit from sparsity-specific computation methods. Conversely, an object that is not sparse — meaning it has few zeros compared to the total number of elements — is called dense.

Sparsity can be naturally occurring or induced. For example, a social network graph will be naturally sparse. Imagine a graph where each node (point) represents a person, and each edge (a line segment connecting the points) represents a friendship. Since most people are not friends with each other, a matrix representing all possible edges will be primarily composed of zeros. Other popular AI applications, such as other forms of graph learning and recommendation models, also contain naturally occurring sparsity.

Normally, a four-by-four matrix occupies 16 memory spaces, regardless of the number of null values. If the matrix is sparse, meaning a large fraction of the values are null, it is more efficiently represented as a fibertree: a "fiber" of coordinates i representing the rows containing non-zero elements, linked to fibers of coordinates j representing the columns with non-zero elements, ultimately connecting to the non-zero values themselves. To store a fibertree in computer memory, the "segments," or endpoints, of each fiber are saved along with the coordinates and values.

Beyond naturally occurring sparsity, sparsity can also be induced in an AI model in several ways. Two years ago, a team from Cerebras showed that it is possible to set up to 70 to 80% of the parameters of an LLM to zero without losing accuracy. Cerebras demonstrated these results specifically on Meta's Llama 7B model, but the ideas extend to other LLMs like ChatGPT and Claude.

The Case for Sparsity

The efficiency of sparse computation arises from two fundamental properties: the ability to compress zeros and the practical mathematical properties of zeros. The algorithms used in sparse computation and the hardware dedicated to it leverage these two foundational ideas.

First, sparse data can be compressed, making their storage more efficient in memory. Compression also makes data movement more energy-efficient when dealing with large quantities. For example, a four-by-four matrix with three non-zero elements would traditionally be stored in memory as is, occupying 16 spaces. This matrix can also be compressed into a sparse data type, eliminating the zeros and retaining only the non-zero elements. In our example, this results in 13 memory spaces instead of 16 for the uncompressed dense version. These memory savings increase with sparsity and matrix size.

Multiplying a vector by a matrix traditionally takes 16 multiplication steps and 16 addition steps. With a sparse number format, the computational cost depends on the number of non-zero values that overlap in the problem. Here, the entire calculation is performed in three search steps and two multiplication steps.

In addition to the actual data values, compressed data also requires metadata. The locations of the rows and columns of the non-zero elements must also be stored. This is generally considered a "fibertree": the row labels containing non-zero elements are listed and linked to the column labels of the non-zero elements, which are then linked to the values stored in those elements.

In memory, things become a bit more complicated: the row and column labels for each non-zero value must be stored along with the "segments" that indicate how many such labels to expect, so that the metadata and data can be clearly delineated.

In a type of uncompressed dense matrix data, values can be accessed either one at a time or in parallel, and their locations can be calculated directly with a simple equation. However, accessing values in compressed and sparse data requires searching for the row index coordinates and using that information to indirectly search for the column index coordinates before finally reaching the value. Depending on the actual locations of the sparse data values, these indirect searches can be extremely random, making computation data-dependent and requiring on-the-fly memory search allocation.

Secondly, two mathematical properties of zero allow software and hardware to skip many calculations. Multiplying any number by zero will yield zero, so there is no need to perform the multiplication. Adding zero to any number will always return that number, so there is no need to perform the addition either.

In matrix-vector multiplication, one of the most common operations in AI workloads, all calculations except those involving two non-zero elements can simply be omitted. For example, take the four-by-four matrix from the previous example and a vector of four numbers. In dense calculation, each element of the vector must be multiplied by the corresponding element in each row and then summed to compute the final vector. In this case, it would require 16 multiplication operations and 16 additions (or four accumulations).

In sparse calculation, only the non-zero elements of the vector need to be considered. For each non-zero element of the vector, an indirect search can be used to find any corresponding non-zero matrix element, and only these need to be multiplied and added. In the example presented here, only two multiplication steps will be performed instead of 16.

Problems with GPUs and CPUs

Unfortunately, modern hardware is not well-suited to accelerate sparse computation. For example, let's say we want to perform a matrix-vector multiplication. In the simplest case, on a single CPU core, each element of the vector would be multiplied sequentially and then written to memory. This is slow, as we can only perform one multiplication at a time. This is why people use CPUs with vector support or GPUs. With this hardware, all elements would be multiplied in parallel, significantly speeding up the application. Now, imagine that the matrix and vector contain extremely sparse data. The vectorized CPU and GPU would spend most of their efforts multiplying by zero, performing completely inefficient calculations.

Newer generations of GPUs are capable of leveraging sparsity in their hardware, but only of a particular type called structured sparsity. Structured sparsity assumes that two of the four adjacent parameters are zero. However, some models benefit more from unstructured sparsity — the ability for any parameter (weight or activation) to be zero and compressed, regardless of where it is and what surrounds it. GPUs can execute unstructured sparse calculations in software, for example, using the cuSparse library for GPUs. However, support for sparse calculations is often limited, and GPU hardware is underutilized, wasting energy on burdensome calculations.

When executing sparse calculations in software, modern CPUs can be a better alternative to GPU computation, as they are designed to be more flexible. However, sparse calculations on the CPU are often hindered by the indirect searches used to find non-zero data. CPUs are designed to "preload" data based on what they expect to need from memory, but...