Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 3 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 3 also cleared it.

Automatic differentiation and backpropagation — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Checkpointed reverse sweep recomputes an intermediate

Example

For $x \in R$ , take the two-transition real-arithmetic computation $x_{1} = F_{1} (x) = x^{2}$ , $x_{2} = F_{2} (x_{1}) = \sin (x_{1})$ , with scalar output $f (x) = x_{2}$ . Both transitions are $C^{1}$ on $R$ . Run the uniform-block checkpoint schedule with $T = 2$ and one saved-state slot $m = 1$ . The schedule stores the initial state, recomputes $x_{1}$ when reversing $F_{2}$ , and returns the same derivative as an uncheckpointed reverse pass: $f^{'} (x) = 2 x \cos (x^{2})$ .

Facts & Assumptions

Given: The two $C^{1}$ transitions, initial state $x$ , and uniform-block schedule with $T = 2$ and $m = 1$ .

[F1]

Uniform-block and binomial checkpoint schedules for reverse sweeps: uniform-block mode saves its scheduled checkpoints, restores a block start, replays the transitions needed to reach each step, records that step's local tape, and reverses the step.

[F2]

Uniform-block and binomial checkpoint schedules preserve reverse adjoints with stated costs: when deterministic replays stay in the declared domains, uniform-block checkpointing returns the same terminal value and initial-state cotangent as the uncheckpointed reverse sweep.

[F3]

The chain rule for total derivatives: $D (g \circ f) (a) = D g (f (a)) \circ D f (a)$ : the derivative of a composition of totally differentiable maps is the ordered composition of their total derivatives.

[F4]

Chain sum product and composition rules for Banach derivatives: on the real Banach space $R$ , multiplication $(a, b) \mapsto a b$ is bounded bilinear because $∣ a b ∣ \leq ∣ a ∣ ∣ b ∣$ , and the identity map has Fréchet derivative $1$ . Applying the bounded-bilinear product rule to two identity maps gives $D (x \mapsto x^{2}) = 2 x$ , a continuous derivative.

[F5]

The derivatives of sine and cosine are cosine and minus sine: on $R$ , $D (\sin u) = \cos u$ and $D (\cos u) = - \sin u$ for every $u \in R$ ; these one-dimensional derivatives are total derivatives.

[F6]

Total differentiability gives a local $O (∥ h ∥_{2})$ increment bound and therefore continuity: a totally differentiable map on $R$ is continuous; in particular, $\cos$ is continuous because it is differentiable by [F5], so $u \mapsto \sin u$ is $C^{1}$ .

Verification

1.1F1givenconstructalgebra

Here $q = ⌈ T / m ⌉ = 2$ , so the uniform-block schedule stores only $x_{0} = x$ and has one block $[0, 2]$ . In the reverse pass it first restores $x_{0}$ and replays $F_{1}$ , obtaining $x_{1} = x^{2}$ before recording the local tape for $F_{2}$ ; it then restores $x_{0}$ again to process $F_{1}$ . Both transitions are defined on all of $R$ , so every replay stays in its declared domain.

2.1F1F4F5step 1.1algebra

Starting with output cotangent ${\overset{ˉ}{x}}_{2} = 1$ , the local derivative of $F_{2}$ gives ${\overset{ˉ}{x}}_{1} = \cos (x^{2})$ by [F5], and the local derivative of $F_{1}$ gives ${\overset{ˉ}{x}}_{0} = 2 x \cos (x^{2})$ by [F4]. This includes $x = 0$ , where the derivative is $0$ , and $x = 1$ , where it is $2 \cos (1)$ .

3.1F2F3step 2.1algebraF6∎

The deterministic replay preserves the local inputs and reverse rules, so [F2] identifies the returned cotangent with the uncheckpointed derivative; [F3] gives $f^{'} (x) = F_{2}^{'} (F_{1} (x)) F_{1}^{'} (x) = \cos (x^{2}) 2 x$ , the same value. The example shows a recomputation trade-off and asserts no schedule optimality.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A ReLU kink has no classical backpropagated derivative

Example

Let $r (u) = \max {0, u}$ , with $r (0) = 0$ , and consider the one-step scalar objective $J (θ) = r (θ)$ represented by initial state $h_{0} (θ) = θ$ , transition $h_{1} = r (h_{0})$ , and loss $ℓ (θ, h_{1}) = h_{1}$ . The ReLU transition is $C^{1}$ on each of the open regions $u < 0$ and $u > 0$ , with its value specified at $u = 0$ . At $θ = 0$ , $J$ has no classical derivative, and the stated forward-, reverse-, and recurrence-backpropagation procedures return NONDIFFERENTIABLE with no tangent or gradient rather than selecting a subgradient.

Facts & Assumptions

Given: The one-step graph at $θ = 0$ with ReLU transition $r (u) = \max {0, u}$ .

[F1]

Finite straight-line computational programs and real-arithmetic tapes: for a piecewise- $C^{1}$ primitive, a branch-boundary input returns NONDIFFERENTIABLE; the definition does not silently choose a subgradient or generalized derivative.

[F2]

Backpropagation through a finite shared-parameter recurrence: on a piecewise- $C^{1}$ map the recurrence procedure uses a derivative only on a unique strict active branch and returns NONDIFFERENTIABLE at a boundary.

[F3]

Forward-mode automatic differentiation on a finite computational graph: a forward-mode input on a branch boundary returns NONDIFFERENTIABLE and no tangent.

[F4]

Reverse-mode automatic differentiation for a scalar graph output: a reverse-mode input on a branch boundary returns NONDIFFERENTIABLE and no gradient.

Verification

1.1givenchoosealgebra

Since $J (0) = 0$ , for every $h < 0$ the difference quotient $(J (h) - J (0)) / h$ equals $0$ , while for every $h > 0$ it equals $1$ . The two one-sided limits differ, so $J$ is not differentiable at $0$ .

1.2F1given

The executed ReLU primitive receives $h_{0} = 0$ , the boundary between its $u < 0$ and $u > 0$ branches. By [F1] this input has no selected strict branch.

2.1F2F3step 1.2

At that boundary, the recurrence procedure in [F2] and the forward procedure in [F3] both return NONDIFFERENTIABLE and no derivative value.

2.2F4step 1.2

The reverse procedure in [F4] also returns NONDIFFERENTIABLE and no gradient at this boundary.

3.1step 1.1step 2.1step 2.2∎

This boundary status agrees with step 1.1: there is no classical derivative for these procedures to propagate, and their specified output does not invent one.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Backpropagation through a two-layer network with a shared weight

Example

Take a scalar-input, one-hidden-unit, scalar-output two-layer feedforward network with identity activations and zero biases, and constrain both layer weights to be the same real parameter $θ$ . For input $x \in R$ , its hidden value is $h_{1} = θ x$ , its output is $y = θ h_{1} = θ^{2} x$ , and the scalar loss is $J (θ) = \frac{1}{2} y^{2}$ . Backpropagation accumulates the two uses of $θ$ and returns $\frac{d J}{d θ} = 2 θ^{3} x^{2}$ , including the zero cases $x = 0$ or $θ = 0$ .

Facts & Assumptions

Given: The two-layer scalar network, the tied layer weight $θ$ , input $x$ , identity activations, zero biases, and loss $J = \frac{1}{2} y^{2}$ .

[F1]

Finite feedforward computation graphs and layered MLPs: a layered perceptron evaluates a finite acyclic graph by applying each vertex's activation to its bias plus the weighted sum of its parents; output vertices may use the identity activation.

[F2]

Backpropagation through a finite shared-parameter recurrence: for a repeated transition using the same $θ$ , reverse mode adds each transition's parameter pullback to a single parameter-gradient accumulator.

[F3]

Reverse accumulation sums gradients over shared parameter uses: the reverse recurrence returns the loss's direct parameter derivative plus all transition-use contributions and the initial-state contribution.

[F4]

Chain sum product and composition rules for Banach derivatives: on the real Banach space $R$ , multiplication $(a, b) \mapsto a b$ is bounded bilinear because $∣ a b ∣ \leq ∣ a ∣ ∣ b ∣$ . The coordinate projections on $R^{2}$ are bounded linear, hence Fréchet differentiable. Applying the product rule to the projections of $(θ, h)$ gives $D_{θ} Φ_{t} = h_{t - 1}$ and $D_{h} Φ_{t} = θ$ ; applying it to $ℓ (θ, z) = \frac{1}{2} z^{2}$ gives $D_{θ} ℓ = 0$ and $D_{z} ℓ = z$ . These derivative factors are continuous, so the transitions and loss satisfy the recurrence's $C^{1}$ premise.

Verification

1.1F1givenconstructalgebra

The network is the two-step recurrence $h_{0} = x$ , $h_{1} = Φ_{1} (θ, h_{0}) = θ h_{0}$ , $h_{2} = Φ_{2} (θ, h_{1}) = θ h_{1}$ , with loss $J = \frac{1}{2} h_{2}^{2}$ . Hence $h_{1} = θ x$ , $h_{2} = θ^{2} x$ , and $J = \frac{1}{2} θ^{4} x^{2}$ .

2.1F2F3F4step 1.1algebra

By [F4], the loss gives $λ_{2} = h_{2}$ and its direct parameter contribution is zero; both transition pullbacks have $D_{θ} Φ_{t} = h_{t - 1}$ and $D_{h} Φ_{t} = θ$ . Thus the $t = 2$ use adds $h_{1} h_{2}$ , the $t = 1$ use adds $h_{0} (θ h_{2})$ , and $h_{0} = x$ has zero parameter derivative. Their sum is $θ^{3} x^{2} + θ^{3} x^{2} = 2 θ^{3} x^{2}$ , including $x = 0$ or $θ = 0$ .

3.1F3F4step 1.1step 2.1algebra∎

Applying the product rule [F4] repeatedly to the scalar expression from step 1.1 gives $J^{'} (θ) = 2 θ^{3} x^{2}$ , equal to the reverse accumulation in step 2.1. For $x = 1$ and $θ = 1$ , both calculations give $2$ .