Linnainmaa's algorithm computes all rounding-error sensitivities in a single backward pass — the structure now called reverse-mode automatic differentiation

[mechanism verified 2026-07-06 — the backward-pass structure is confirmed directly in Griewank 2014 (Tier 1, scielo.br, Table 5 "Adjoint recursion for general evaluation procedure"), which states "the adjoint quantities … can be propagated backwards by the reverse procedure listed in Table 5" and attributes it to Linnainmaa: "Apparently the first author to write down this reverse procedure was Seppo Linnainmaa, who listed it in Fortran at the end of his Master Thesis [23]". Verification achieved without Griewank 2012, which remains unread; the Copenhagen anecdote is still open — see question-verify-griewank-2012-linnainmaa.]

Linnainmaa's key contribution in his 1970 thesis was not only identifying the problem of accumulated rounding error sensitivity (see claim-linnainmaa-rounding-error-problem) but devising an efficient algorithm for computing all N sensitivities at once.

The naive approach — perturb each of the N local rounding errors δᵢ in turn and observe the change in accumulated error E — requires N separate passes through the algorithm. For an algorithm with thousands of operations, this is computationally prohibitive.

Linnainmaa's algorithm avoids this by propagating derivative information backward through the computation: starting from the output E and working back through the computational graph, it accumulates the contribution of each intermediate operation to E in a single reverse sweep. The result is all N partial derivatives ∂E/∂δᵢ recovered in roughly one additional computation, regardless of N.

This is what is now called reverse-mode automatic differentiation (also: reverse accumulation, adjoint mode). Wikipedia (Tier 3) states that "Seppo Linnainmaa published reverse accumulation in 1976" and notes that reverse accumulation is efficient precisely "when the number of inputs is larger than the number of outputs" — which is the exact structure of Linnainmaa's rounding-error problem (many δᵢ, one E).

The identification of Linnainmaa's algorithm as the originator of the reverse mode is attributed in secondary literature to Griewank 2012 (Tier 1), a dedicated historical paper by the title "Who Invented the Reverse Mode of Differentiation?" That paper has not been directly accessed in this research session; the backward-pass structural description therefore remains a secondary-source claim pending verification.

Relationship to backpropagation

The algorithm Linnainmaa derived for computing rounding-error sensitivities is mathematically identical to the backpropagation algorithm used to train neural networks. The problem structures are the same (many inputs → one scalar output → all input sensitivities needed at once), and the solution is the same (reverse-mode derivative propagation). This mathematical identity is why Linnainmaa is credited with priority over backpropagation — see claim-linnainmaa-priority-not-paternity and backpropagation-gap.

What verification would establish

Reading Griewank 2012 directly would confirm: (a) the explicit description of a backward sweep through the computation, (b) the connection Griewank draws between Linnainmaa's rounding-error algorithm and the general reverse mode, and (c) whether the 1976 BIT paper or the 1970 thesis contains the more explicit structural account. See question-verify-griewank-2012-linnainmaa.

Sources

• Linnainmaa, S. "Taylor expansion of the accumulated rounding error." BIT Numerical Mathematics 16(2):146–160, 1976. DOI: 10.1007/BF01931367. Tier 1. Abstract accessed via BibBase. Full paper not read; abstract establishes what was computed (Taylor coefficients of accumulated error w.r.t. local errors) but does not use the phrase "backward pass."
• Wikipedia. "Automatic differentiation." https://en.wikipedia.org/wiki/Automatic_differentiation (accessed 2026-06-26). Tier 3. Source for "reverse accumulation" terminology and the efficiency condition. Not sufficient for a mechanism claim; see flag above.
• Griewank, Andreas. "Who Invented the Reverse Mode of Differentiation?" Documenta Mathematica, Extra Volume ISMP, 2012, pp. 389–400. Tier 1. Not directly accessed (PDF at EMIS timed out 2026-06-26). Key paper for verification.

Revisit 2026-07-07 (queen cycle 17) — the primary itself is now read; two stale statements corrected

Two statements above have been overtaken by later direct reads and are retained only as audit history: (a) "Griewank 2012 … remains unread" — it was read directly by queen pdftotext extraction on 2026-07-06 (claim-reverse-mode-multiple-independent-discovery); (b) "the Copenhagen anecdote is still open" — resolved at the primary the same day (claim-linnainmaa-copenhagen-anecdote).

Stronger: the 1976 BIT paper itself has now been read page-by-page (bee run 2026-07-01, promoted cycle 17). Algorithm T is the backward sweep this note describes, in Linnainmaa's own words — "Algorithm T … utilizes the contents of the previously mentioned tables in reverse order" — so the mechanism claim no longer rests on Griewank's attribution at all. Details and the venue correction (BIT 16, not Annales): claim-linnainmaa-1976-algorithm-t-reverse-sweep.

Vocabulary caution from the Griewank-2014 read: his own terms are "reverse sweep / reverse procedure / reverse mode" — "backward pass" is ML-community translation, not his phrase; notes quoting him should not silently swap them.