<!-- examples/online-softmax/README.md -->

# Online softmax reference

Run `python3 examples/online-softmax/online_softmax.py` from the repository root,
or `python3 online_softmax.py` after downloading the script. Python 3.10 or later
is sufficient; no packages or accelerator are needed. `--json` emits the authored
six-logit trace and final probabilities for comparison with the browser model.

This educational implementation follows Algorithms 2 and 3 and the parallel
summary operation in Milakov and Gimelshein,
[Online normalizer calculation for softmax, arXiv v2](https://arxiv.org/abs/1805.02867v2).
The TopK example uses a Python heap instead of Algorithm 4's insertion array.
Ties select the smaller original index. It returns selected probabilities from
the full softmax distribution; it does not renormalize them to sum to one.

The normalizer consumes its iterator once with constant auxiliary state. The
full-softmax wrapper materializes the input so it can revisit every logit in the
output pass. That Python tuple is not a model of GPU memory residency or traffic.
The TopK reference accepts an iterator and retains only k candidates plus the
normalizer. It still examines every logit.

Inputs must be finite, nonempty logits for full softmax. Empty normalizer chunks
return the identity `(-inf, 0)`, with explicit merge branches to avoid
`-inf - -inf`. Masked logits, NaNs, infinities, gradients and accelerator kernels
are outside this example. Python floats use double precision; changes in
precision and reduction order can change rounding.

Self-checks compare the online recurrence against a maximum-first reference with
`math.fsum`, including equal/extreme logits, constant shifts, every two-way split
of deterministic random vectors, empty chunk identities and TopK probabilities.
No timings, pretrained outputs or reproduction of the paper's V100 benchmarks
are claimed.

Source regions are canonical. `scripts/sync-paper-examples.mjs` owns the generated
browser snippets and downloadable copies. Crop provenance lives in
`public/images/papers/online-softmax/source-crops.json`.
