TL;DR
Researchers have developed two new kernels, FuseLSE and IntLSE, that dramatically speed up the ubiquitous Log-Sum-Exp (LSE) function. By fusing operations to bypass the "Memory Wall" on GPUs and using integer approximations to overcome the "Compute Wall" on CPUs, they achieve speedups of up to 11x over standard PyTorch implementations with minimal loss in accuracy.
What Problem Does This Paper Address?
The Log-Sum-Exp (LSE) function—defined as $\text{LSE}(\mathbf{x}) = \log \sum e^{x_i}$—is a workhorse of modern machine learning, essential for maintaining numerical stability when dealing with probabilities in the log-domain. It appears everywhere from Large Language Model (LLM) training to probabilistic circuits and particle filters.
Despite its ubiquity, standard implementations like torch.logsumexp are surprisingly inefficient:
- On GPUs (The Memory Wall): PyTorch dispatches a chain of nine separate sub-kernels for a single LSE call. This forces the GPU to move the entire input tensor between its fast registers and slower High-Bandwidth Memory (HBM) up to six times, creating a massive data-movement bottleneck.
- On CPUs (The Compute Wall): CPUs lack specialized hardware for transcendental functions like
expandlog. These operations are "hardware-hungry," consuming many clock cycles and becoming the primary bottleneck for LSE computation.
Methods
The authors propose two distinct strategies to tackle these bottlenecks:
- FuseLSE (GPU-focused): This kernel fuses the entire LSE operation into a single pass. Instead of multiple kernels, it uses a pair-wise recursive formulation: $\text{LSE}(x, y) = \max(x, y) + \log(1 + \exp(-|x-y|))$. On GPUs, it leverages the Special Function Unit (SFU)—dedicated hardware for fast
expandlog—to keep the computation extremely fast while reducing HBM traffic to a single read/write pass. - IntLSE (CPU-focused): On platforms without an SFU (like CPUs), even fused floating-point math is slow. IntLSE replaces the expensive
expandlogwith integer approximations based on Mitchell’s approximation ($2^v \approx 1+v$). It operates in Q16.16 fixed-point arithmetic, turning complex math into simple integer additions and bit-shifts. To maintain accuracy, it uses a small 64-entry Look-Up Table (LUT) to correct the approximation errors.
Datasets
The kernels were evaluated using a mix of synthetic microbenchmarks and three real-world application domains:
- RLHF Log-Probability: Benchmarked using a GPT-2 (124M) backbone on the Anthropic HH-RLHF text dataset, scaling vocabulary sizes to match Llama-2, Llama-3, and Gemma.
- Probabilistic Circuits: Evaluated using Hidden Chow–Liu Tree (HCLT) circuits trained on the MNIST dataset.
- Particle Filtering: Tested using a univariate stochastic-volatility model, a standard benchmark for Sequential Monte Carlo methods.
Key Insights and Ideas
- The "Aha" Moment on GPUs: On modern GPUs, the actual math of LSE is almost "free" because it's hidden by the time spent moving data. Therefore, replacing
expwith integer math (IntLSE) provides no extra speedup over FuseLSE on GPUs. The win comes entirely from kernel fusion. - The "Aha" Moment on CPUs: Because CPUs lack SFUs, the math is not free. Here, the integer pipeline of IntLSE becomes the "compute floor," outperforming even fused floating-point kernels by 3–6x.
- Precision vs. Speed: The authors found that for many ML applications, the slight approximation error of IntLSE is a non-issue, as it remains within the range of standard FP32 errors or is negligible compared to the overall model noise.
Key Results
- GPU Performance: Both FuseLSE and IntLSE are ~10–11x faster than PyTorch for small workloads (where launch overhead dominates) and ~6x faster for large workloads (where HBM traffic dominates).
- CPU Performance: IntLSE is the clear winner, beating PyTorch by 2.8–5.2x in particle filtering applications and outperforming FuseLSE by up to 6x in microbenchmarks.
- Application Impact: In RLHF training, the new kernels provided a ~6x speedup on the log-probability computation step, which translates to a significant reduction in overall training time as vocabulary sizes grow.
Limitations and Future Work
- Cumulative Error: While the error is low, it is cumulative. For extremely deep computation graphs (like very deep probabilistic circuits), the approximation error in IntLSE might eventually become significant.
- Integration: While the kernels are "drop-in" replacements, they currently require manual integration into high-level libraries. Future work could involve upstreaming these into compilers like TorchInductor.
- Hardware Specifics: The current IntLSE implementation is optimized for AVX2 on CPUs; further tuning for ARM (NEON) or newer AVX-512 sets could yield even higher gains.
Summary updated