---
id: "20260706-0200-what-exact-numeric-bound"
title: "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\"?"
type: "capture"
status: "promoted"
promoted_to: ["claim-cheap-gradient-bound-two-figures"]
not_promoted: ["the two open verification threads (Baur-Strassen 1983 primary wording; Griewank 1989 as the '5x' source) are carried as queued queue-topics, not shelved as claims yet"]
origin: "batch"
model: "claude-sonnet-5"
date_created: "2026-07-06T00:00:00.000Z"
provenance: "batch run 2026-07-06 — harvested from 2026-06-29-what-is-the-reverse-mode-automatic-differentiation-backpropagation-correspondence-stated-precisely. Primary book (Griewank & Walther, Evaluating Derivatives, 2nd ed., SIAM 2008) accessed indirectly via a scanned-copy host relayed through a summarizing fetch tool, not a certified OCR/PDF extraction — see access notes below. Corroborated independently by two peer-reviewed papers that cite the book directly."
derived_from: []
tags: ["automatic-differentiation","reverse-mode","cheap-gradient-principle","griewank-walther","baur-strassen","backpropagation","computational-complexity"]
source_url: "https://vdoc.pub/documents/evaluating-derivatives-principles-and-techniques-of-algorithmic-differentiation-20j6sr1p9frg"
source_author: "Andreas Griewank and Andrea Walther"
source_date: "2008"
source_tier: 2
---


## 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.

> [!note] Seek's commentary:
> This is a case where "the exact number" turns out not to be a single number — the book's own casual framing ("one to four times") and the field's canonical theorem-citation ("5 times") are both real, both traceable, and describe slightly different things (an illustrative prose bound vs. a proven worst-case complexity bound). Anyone promoting this note should preserve that distinction rather than collapsing it into one figure — picking either "4×" or "5×" alone and presenting it as *the* Griewank & Walther number would overstate precision that the sources don't actually agree on. The book-quote itself is the weaker link here (Tier 2, tool-mediated access) and would benefit most from a follow-up with a direct PDF/library read to fully certify it at Tier 1.

## 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.