What exact numeric bound does Griewank & Walther (2008) state for reverse-mode cost relative to the original function's cost in the "cheap gradient principle"?

Core finding

There are two distinct numeric figures in the literature for this bound, coming from different formulations of the same underlying result, not from disagreement about the facts:

1. "Between one and four times" — the specific phrasing used by Griewank & Walther themselves in the book's own prose statement of the cheap gradient principle.
2. "5 times" / "5·cost(f)" — the figure almost universally cited in the surrounding academic literature when papers formalize the same result via the Baur-Strassen theorem (1983), which Griewank & Walther's principle is built on and which Griewank himself restated in a 1989 paper.

These are not contradictory: the book's own informal statement ("one to four times") is a slightly tighter, example-motivated framing in the preface/introduction, while the "factor of 5" is the number nearly every paper reaches for when citing the formal theorem behind the principle. Both trace to the same underlying mathematical result but are phrased differently in different places.

Claim type: quantitative ("Nx" multiplier) — floor requires Tier 1-2 sourcing per 00-meta/sources.md.

1. The book's own statement — "between one and four times"

• Exact quote: "Even if our output y depended upon a million inputs x_i, we could still use this reverse or adjoint method of AD to obtain all 1 million components of ∇x y with an additional floating point operation count of between one and four times that required for a single evaluation of y."
• Location: Introduction, Chapter 1, section "Attractions of the Reverse Mode," p. 9 (per the scanned copy's pagination) — this is the passage that motivates and introduces the section later titled "3.3 Cheap Gradient Principle with Examples" in the book's table of contents.
• Source: Griewank, A. & Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd edition, SIAM, 2008.
• Access path: https://vdoc.pub/documents/evaluating-derivatives-principles-and-techniques-of-algorithmic-differentiation-20j6sr1p9frg — a scanned/hosted copy of the book. This is the book itself (nominally Tier 1), but access was mediated through a summarizing web-fetch tool rather than a certified OCR or direct PDF read. The identical sentence was independently returned across two separate fetch attempts (one by a research subagent, one directly) with word-for-word matching text, which gives reasonable confidence in the transcription. Given the indirect access method, this is recorded as Tier 2 rather than a fully certified Tier 1 capture — flagged [unverified-quant — needs primary] pending a direct, independently-verifiable read of the physical/PDF text (e.g., via an institutional library copy or a direct PDF-to-text extraction).
• Direct attempts to reach the authoritative SIAM page (https://epubs.siam.org/doi/abs/10.1137/1.9780898717761.ch3) returned HTTP 403 (paywalled); a review page on old.maa.org returned HTTP 521 (unreachable). Both are noted as access failures, not contradictions.

2. The literature's formalization — "5 times," via the Baur-Strassen theorem

• Exact quote: "According to the key complexity theory version of this result due to Baur and Strassen (1983), arithmetic complexity of the evaluation of the derivative of a rational function is at most 5 times the complexity of function evaluation."

  • Source: Bolte, J. & Pauwels, E., "Provably Correct Automatic Subdifferentiation for Qualified Programs," NeurIPS 2018 (arXiv:1809.08530).
  • URL: https://ar5iv.labs.arxiv.org/html/1809.08530 (verified to resolve)
  • Tier: 1-2 (peer-reviewed paper directly citing and paraphrasing Baur & Strassen 1983 and Griewank 1989, with an explicit reference to Griewank & Walther 2008 for the "cheap gradient principle" name).
  • The same paper also states, attributing the principle's name to Griewank & Walther 2008: "the computational cost of computing the vector of partial derivatives (∂f/∂x_1,...,∂f/∂x_d) is often nearly the same as that of simply computing the scalar function f(x) itself... This property [is] called the cheap gradient principle (Wolfe, 1982; Griewank and Walther, 2008)."

• Exact quote (independent corroboration): "for all rational functions, the striking Baur-Strassen theorem shows that this increase in computational complexity is a (dimension free) factor of 5" and "it is possible to compute both f(x) and all its partial derivatives ∇f(x) in time that is at most 5∗Runtime(f;x)."

  • Source: Bolte, J. & Pauwels, E., "On the Complexity of Nonsmooth Automatic Differentiation," ICLR 2023 (arXiv:2206.01730).
  • URL: https://ar5iv.labs.arxiv.org/html/2206.01730 (verified to resolve)
  • Tier: 1-2 (peer-reviewed; this paper's own contribution extends the classical factor to a factor of 6 for nonsmooth/ReLU programs via conservative gradients — that "6×" figure is their new result, not Griewank & Walther's, and is noted here only to avoid it being confused with the classical bound).

• Context on the original theorem (not independently re-verified — record with caution): Baur, W. & Strassen, V., "The complexity of partial derivatives," Theoretical Computer Science, 22, 1983, pp. 317–330, is reported (via search-engine snippet only; direct fetch of https://www.sciencedirect.com/science/article/pii/030439758390110X returned HTTP 403 Forbidden) to prove a bound of 3 times under the paper's own "multiplicative complexity" (L) measure — a different, narrower complexity model than the general operation-count/runtime model used in the "5×" restatements above. This figure is [unverified-quant — needs primary]: it was not independently confirmed against the primary paper's actual text.

Notably absent

Baydin, Pearlmutter, Radul & Siskind's widely-cited survey "Automatic Differentiation in Machine Learning: a Survey" (JMLR 2018, arXiv:1502.05767 — https://ar5iv.labs.arxiv.org/html/1502.05767, verified to resolve, Tier 1-2) cites Griewank & Walther (2008) repeatedly but does not state a specific numeric constant for this bound anywhere in its text — it only refers generally to AD's "small constant factor of overhead." This is a useful negative data point: even a major, oft-cited survey of the field doesn't repeat one canonical number, consistent with the finding that the "exact" figure varies by which formulation (book prose vs. formal theorem) is being cited.

Wikipedia's "Automatic differentiation" page was checked directly and does not state the cheap gradient principle or any numeric bound at all (only a passing historical mention of Griewank) — confirmed negative result, not used as a source here.

Summary answer to the core question

The book itself (Griewank & Walther 2008, in the passage introducing the cheap gradient principle) states the bound as "between one and four times" the cost of a single function evaluation for computing the full gradient via reverse mode — this is the closest available answer to "what exact numeric bound does the book state," though it rests on Tier 2 (indirect, tool-mediated) access to the primary text rather than a certified direct read, so it is marked [unverified-quant — needs primary] pending independent confirmation.

Separately and more prominently in the surrounding literature, the formal theorem the principle is built on (Baur-Strassen 1983, as restated by Griewank 1989 and repeated in essentially every modern paper on the topic, including two Tier 1-2 peer-reviewed sources quoted above) gives the bound as at most 5 times. This "5×" figure is well-sourced at Tier 1-2 and is the number most likely to be encountered when the "cheap gradient principle" is invoked in later work, even though it is not the exact phrase used in the book's own prose.

Further leads

• Obtain a directly-verifiable (non-tool-mediated) copy of Griewank & Walther (2008), e.g. via institutional library access or a clean PDF-to-text extraction, to certify the "between one and four times" quote at full Tier 1 and to locate the book's own restatement of the Baur-Strassen bound in Chapter 3 ("3.3 Cheap Gradient Principle with Examples"), which was not directly reached this session.
• Independently verify the Baur & Strassen (1983) original paper's "factor of 3" figure directly against its text (currently blocked by ScienceDirect's 403 paywall) — this is the one quantitative figure in this capture that rests only on a search-snippet paraphrase and should be treated as the weakest-sourced number here.
• Check Griewank's 1989 paper (the restatement that bridges Baur-Strassen's 1983 result to the "5×" figure commonly cited today) directly, if accessible, to confirm the chain of attribution.

Correction (2026-07-07, higher-model audit — origin of a promoted error)

Section 2 above cross-attributes its two supporting papers, and the error propagated into claim-cheap-gradient-bound-two-figures at promotion:

• The quote "According to the key complexity theory version… at most 5 times the complexity of function evaluation" is from arXiv:2206.01730, Bolte, Boustany, Pauwels & Pesquet-Popescu, "On the complexity of nonsmooth automatic differentiation" (ICLR 2023) — not from 1809.08530.
• arXiv:1809.08530 is Kakade & Lee, "Provably Correct Automatic Subdifferentiation for Qualified Programs" (NeurIPS 2018) — not Bolte & Pauwels — and it contains the other quote ("for all rational functions, the striking Baur-Strassen theorem… (dimension free) factor of 5").
• The "(Wolfe, 1982; Griewank and Walther, 2008)" attribution quoted in §2 also did not match 1809.08530's text on re-fetch: that paper credits the name to Griewank & Walther alone.

Both ar5iv pointers re-fetched and verified 2026-07-07; the claim-note was corrected the same day (Cali-accepted ruling on 00-meta/audit-morning-2026-07-07.md, correction 3). The capture text above is left as written — this annotation records the defect rather than rewriting it.