Online normalizer calculation for softmax

Maxim Milakov, Natalia GimelsheinarXiv 2018 · arXiv

TL;DR

Researchers at NVIDIA have developed a more efficient way to compute the ubiquitous Softmax function by reducing the number of memory passes required. By calculating the normalization term "online" in a single pass, they achieved up to a 1.3x speedup for standard Softmax and a massive 5x speedup when fusing Softmax with a TopK operation on modern GPUs.

What Problem Does This Paper Address?

Softmax is a fundamental building block in deep learning, particularly for language modeling and classification tasks. However, it is notoriously memory-intensive.

A "naive" implementation of Softmax often leads to numerical instability (overflow or underflow) because it involves exponentiating large numbers. To solve this, practitioners use "Safe Softmax," which first finds the maximum value in a vector and subtracts it from all elements before exponentiating.

While numerically stable, Safe Softmax is inefficient on hardware like GPUs. It typically requires three passes over the input data:

  1. Find the maximum value ($m$).
  2. Compute the sum of the exponentials ($d$).
  3. Compute the final probabilities ($y_i$).

On modern hardware, performance is often limited by memory bandwidth rather than raw compute power. Safe Softmax requires four memory accesses per vector element (three loads and one store), creating a significant bottleneck.

Methods

The authors propose Online Softmax (Algorithm 3 in the paper), which reduces the process to two passes (three memory accesses: two loads, one store).

The core innovation is calculating the running maximum and the normalization term simultaneously. Inspired by Welford’s algorithm for online variance calculation, the authors use a clever adjustment factor. As the algorithm iterates through the vector, if it encounters a new maximum ($m_j$), it rescales the existing partial sum ($d_{j-1}$) by multiplying it by $e^{m_{j-1} - m_j}$ before adding the new element.

To make this work on parallel hardware like GPUs, the authors defined a binary operation for this online calculation that is both associative and commutative. This allows the computation to be distributed across multiple threads and combined using a tree-based reduction.

Finally, they introduced Softmax + TopK fusion. In many inference scenarios (like beam search), we only care about the top $K$ probabilities. By keeping track of the TopK values during the single-pass normalizer calculation, the system can avoid writing the full Softmax output back to memory entirely, reducing memory traffic to just one load per element.

Datasets

The paper does not use standard training datasets (like ImageNet or WikiText). Instead, it uses synthetic benchmarks designed to measure raw kernel performance across various vector sizes ($V$) and batch sizes.

  • Large Batch (4,000 vectors): Simulates training or high-throughput batch inference.
  • Small Batch (10 vectors): Simulates low-latency online inference.
  • Hardware: All benchmarks were performed on an NVIDIA Tesla V100 PCIe 16 GB.

Key Insights and Ideas

  • Memory is the Bottleneck: The primary "aha" moment is that adding a few extra floating-point operations (the rescaling factor) is a winning trade-off if it eliminates an entire pass over the data in memory.
  • Fusion is a Force Multiplier: The most significant gains don't come from Softmax alone, but from fusing it with the subsequent operation. By combining Softmax and TopK, the authors reduced memory accesses from five down to one.
  • Numerical Parity: The online method provides the same numerical stability guarantees as the standard Safe Softmax, making it a "drop-in" optimization.

Key Results

The benchmarks confirmed that reducing memory accesses translates directly into real-world performance gains:

  • Standard Softmax: For large vectors ($V \ge 4000$), Online Softmax is consistently 1.3x faster than Safe Softmax in large batch settings. As seen in Figure 1, the performance improvement (the light blue bars) stabilizes as the vector size increases.
Figure 1: Benchmarking softmax, Tesla V100, fp32, batch size 4000 vectors
  • Small Batch Inference: Even in latency-sensitive small batch scenarios, the algorithm outperforms Safe Softmax by approximately 1.15x for vectors larger than 1,000 elements (Figure 2).
Figure 2: Benchmarking softmax, Tesla V100, fp32, batch size 10 vectors
  • Fused Softmax + TopK: This showed the most dramatic results, reaching up to a 5x speedup for large batches (Figure 3). This is a combination of the 2.5x gain from fusion and the 2x gain from the online algorithm itself.
Figure 3: Benchmarking softmax and top-k, Tesla V100, fp32, batch size 4000 vectors

Limitations and Future Work

  • The "K" Limit: The benefits of TopK fusion diminish as $K$ increases. The cost of maintaining a sorted list of the top $K$ elements (lines 10-15 of Algorithm 4) eventually outweighs the memory savings. The authors note significant drops in speedup once $K > 15$.
  • Hardware Scope: The study focused exclusively on GPUs. While the authors hypothesize similar speedups for vectorized CPU code, they did not perform those experiments.
  • Further Fusion: The authors suggest that even more performance could be squeezed out by fusing Softmax with the preceding projection layer (the matrix multiplication), though they acknowledge this is a more challenging engineering task.

Summary updated

Abstract

The Softmax function is ubiquitous in machine learning, multiple previous works suggested faster alternatives for it. In this paper we propose a way to compute classical Softmax with fewer memory accesses and hypothesize that this reduction in memory accesses should improve Softmax performance on actual hardware. The benchmarks confirm this hypothesis: Softmax accelerates by up to 1.3x and Softmax+TopK combined and fused by up to 5x.
BibTeX
@misc{milakov2018online,
  author = {Maxim Milakov and Natalia Gimelshein},
  title = {{Online normalizer calculation for softmax}},
  year = {2018},
  eprint = {1805.02867},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.02867},
}
Figure