Numerically Stable Log-Sum-Exp and Softmax
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:
[ 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)$.softmax(logits)-- $n$ values, $e^{x_j - m} / \sum_i e^{x_i - m}$.[ ce_loss ]-- the cross-entropy loss $-\log s_{\text{target}}$, computed stably aslse - logits[target].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
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium