Numerically Stable Log-Sum-Exp and Softmax

MediumML Coding

Reported in interviews at Citadel NVIDIA

Problem statement

Naive computation of $\log \sum_i e^{x_i}$ and $\text{softmax}(x)_j = e^{x_j} / \sum_i e^{x_i}$ blows up or underflows when entries of $x$ are large in magnitude. Implement numerically stable versions of both, then build cross-entropy loss and its gradient on top -- all bundled into a single function.

Implement stable_ops(logits, target) where logits is a list of n floats and target is the integer index of the correct class. Return ONE flat list of length 2 + 2*n:

  1. [ lse ] -- $\log \sum_i e^{x_i}$, computed via the max-shift trick $m + \log \sum_i e^{x_i - m}$ with $m = \max(x)$.
  2. softmax(logits) -- $n$ values, $e^{x_j - m} / \sum_i e^{x_i - m}$.
  3. [ ce_loss ] -- the cross-entropy loss $-\log s_{\text{target}}$, computed stably as lse - logits[target].
  4. cross_entropy_gradient -- $n$ values, $\partial L / \partial x_j = s_j - \mathbf{1}[j = \text{target}]$.

All outputs must be free of NaN and Inf for valid inputs, even when entries are on the order of $\pm 10^3$.

Constraints:

  • Input is a 1-D list of floats with $1 \le n \le 10^5$.
  • Do not use any library softmax / logsumexp.

Example

stable_ops([1.0, 2.0, 3.0], 0) -> [3.4076059644443806, 0.09003057317038046, 0.24472847105479764, 0.6652409557748218, 2.4076059644443806, -0.9099694268296196, 0.24472847105479764, 0.6652409557748218]

Here $n=3$, so the returned list has length $2 + 2\cdot3 = 8$: the log-sum-exp (3.4076...), then the 3 softmax probabilities, then the cross-entropy loss for target=0 (2.4076...), then the 3 gradient components (note the target's gradient is softmax[0] - 1 = -0.9099...).

Show hint

What constant can you subtract from every logit without changing the log-sum-exp beyond an additive term, and which choice keeps every exponent safe?

Relevant roles: ML Engineer, LLM Engineer, Deep Learning Engineer and Research Scientist.

Related free problems