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:
- Find the maximum value ($m$).
- Compute the sum of the exponentials ($d$).
- 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.
- 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).
- 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.
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