Accurate Computation of the Log-Sum-Exp and Softmax Functions

Pierre Blanchard, Desmond J. Higham, Nicholas J. HighamarXiv 2019 · OpenReview

Abstract

The Log-Sum-Exp (LSE) and Softmax functions are foundational to modern machine learning, yet their numerical stability is often taken for granted. This paper provides a rigorous rounding error analysis of these functions, focusing on the widely used "shifting trick." We demonstrate that while the shifted algorithm is forward stable even in low-precision arithmetic, alternative "division-free" implementations can lead to significant inaccuracies. Our analysis is supported by experiments on real-world data from neural network training.

1. Introduction

In machine learning, the Log-Sum-Exp (LSE) function, $LSE(x) = \log \sum_{i=1}^{n} e^{x_i}$, and its gradient, the Softmax function, $\sigma(x)_j = e^{x_j} / \sum_{i=1}^{n} e^{x_i}$, are ubiquitous. They appear in cross-entropy loss functions, attention mechanisms, and reinforcement learning. A primary challenge in their implementation is the use of the exponential function, which can easily exceed the range of standard floating-point formats, leading to overflow or underflow.

2. Floating-Point Arithmetic and Precision

The behavior of LSE and Softmax is intrinsically linked to the precision and range of the underlying hardware arithmetic. Modern deep learning increasingly relies on 16-bit formats like fp16 and bfloat16.

Table 1: Precision and range parameters for standard floating-point formats.

As shown in Table 1, fp16 offers higher precision (smaller unit roundoff $u$) but a very restricted range ($r_{\max} \approx 6.55 \times 10^4$). Conversely, bfloat16 provides a much larger range, comparable to fp32, at the cost of lower precision. These constraints necessitate robust algorithms to ensure numerical reliability.

Table 2: Logarithmic ranges for various floating-point formats.

Table 2 illustrates the logarithmic limits of these formats. For instance, in fp16, any input $x_i > \log(r_{\max}) \approx 11.0$ will cause $e^{x_i}$ to overflow to infinity.

3. Algorithmic Stability

We evaluate three primary approaches to computing these functions:

  1. Naive Algorithm: Direct implementation of the mathematical formulas.
  2. Shifted Algorithm: Subtracting $a = \max(x_i)$ from all inputs before exponentiation. This ensures the largest term is $e^0 = 1$, effectively preventing overflow.
  3. Division-Free Softmax: Computing $\sigma(x)_j = \exp(x_j - LSE(x))$.

Our rounding error analysis proves that the shifted algorithm is forward stable. A common concern in numerical analysis is subtractive cancellation; however, we show that in the shifted LSE, the terms being summed are bounded, mitigating this risk. In contrast, the "division-free" variant is shown to be less accurate, as errors in the $LSE(x)$ term are magnified by the final exponential.

4. Experimental Results

To validate our theoretical findings, we extracted 2,500 activation vectors from a convolutional neural network trained on the MNIST dataset. These vectors represent the typical inputs to a Softmax layer in a production environment.

In fp16 tests, the naive LSE failed for 19% of the test vectors due to overflow. The shifted version successfully processed all vectors. Furthermore, numerical experiments confirmed that the standard shifted Softmax is significantly more accurate than the division-free variant, often by several orders of magnitude. The shifted algorithm also superiorly maintains the "sum-to-one" property required for probability distributions.

5. Conclusion

This study provides the formal justification for the "shifting trick" in LSE and Softmax computations. We conclude that the shifted algorithm is the most reliable method for deep learning applications, particularly when utilizing low-precision formats like fp16. We recommend against the use of division-free Softmax implementations due to their inherent numerical instability.

Summary updated

Abstract

Evaluating the log-sum-exp function or the softmax function is a key step in many modern data science algorithms, notably in inference and classification. Because of the exponentials that these functions contain, the evaluation is prone to overflow and underflow, especially in low precision arithmetic. Software implementations commonly use alternative formulas that avoid overflow and reduce the chance of harmful underflow, employing a shift or another rewriting. Although mathematically equivalent, these variants behave differently in floating-point arithmetic. We give rounding error analyses of different evaluation algorithms and interpret the error bounds using condition numbers for the functions. We conclude, based on the analysis and numerical experiments, that the shifted formulas are of similar accuracy to the unshifted ones and that the shifted softmax formula is typically more accurate than a division-free variant.
BibTeX
@misc{blanchard2019accurate,
  author = {Pierre Blanchard and Desmond J. Higham and Nicholas J. Higham},
  title = {{Accurate Computation of the Log-Sum-Exp and Softmax Functions}},
  year = {2019},
  eprint = {1909.03469},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.03469},
}
Figure