Automatic differentiation and computational graphs

Fix an input dimension $n\ge 0$, finitely many operation nodes $1,\dots ,T$, and a designated output node $o$, either an input coordinate or an operation, whose value space is $\mathbb{R}$. Give input coordinate $i$ a label ${\mathrm{i}\mathrm{n}}_i$ distinct from all operation indices, and set $z_{{\mathrm{i}\mathrm{n}}_i}=x_i$ and $E_{{\mathrm{i}\mathrm{n}}_i}=\mathbb{R}$ with its standard Euclidean inner product. Operation node $j$ has an ordered list of parent slots $p_{j,1},\dots ,p_{j,r_j}$; each slot is either an input label ${\mathrm{i}\mathrm{n}}_i$ or an operation index $\mathrm{\ell }<j$. Repeated parent slots are allowed and count separately. The graph is a finite straight-line program because every operation reads only earlier values and there are no data-dependent loops.

For each operation $j$, choose a dimension $d_j\ge 0$, set $E_j={\mathbb{R}}^{d_j}$ with its standard Euclidean inner product, take an open set $U_j\subseteq E_{p_{j,1}}\times \cdots \times E_{p_{j,r_j}}$ with the product inner product, and choose a primitive map ${\varphi }_j:U_j\to E_j$. A smooth primitive is $C^1$: it is totally differentiable and its derivative matrix is continuous. For Hessian-vector products require the primitive to be $C^2$, meaning $C^1$ with a continuously differentiable derivative map. Derivatives are represented in these coordinates, and every transpose is the Euclidean transpose for the stated inner products; the gradient of a scalar output is the Euclidean gradient. The real-arithmetic primal recursion is $z_j={\varphi }_j(z_{p_{j,1}},\dots ,z_{p_{j,r_j}})$ whenever the parent tuple lies in $U_j$. Its admissible input domain is the set of $x\in {\mathbb{R}}^n$ for which every operation in this recursion is defined. The graph's scalar output function $f$ is the value at $o$: it is $x_i$ when $o$ is input coordinate $i$, and $z_j$ when $o$ is operation node $j$.

The primal tape is the finite ordered record of input and node values, parent-slot indices, primitive identities, and (when applicable) selected branch labels. A deterministic replay starts from the identical checkpoint state and applies the identical primitive maps in the identical order, so it reproduces the same real-arithmetic values and local derivative inputs. Opaque solver calls are not primitive operations unless their complete deterministic map and derivative rule are explicitly supplied.

A piecewise-$C^1$ primitive is specified by finitely many open branch regions and a $C^1$ formula on each region; its primal boundary value, if any, is specified separately. If the current parent tuple lies strictly inside exactly one declared branch, the program uses that branch and its derivative. At a branch boundary or ambiguous branch selection, forward or reverse AD returns NONDIFFERENTIABLE; it does not silently choose a subgradient or generalized derivative. If no primal value is specified at a boundary, that input is outside the program's domain. All correctness theorems below apply on a fixed strict branch. The same convention applies to piecewise-$C^2$ primitives for Hessian-vector products.

Let $R(z,\theta )$ be $C^2$ near an exact solution $R(z_{\ast },{\theta }_0)=0$, with $A(z)=R_z(z,{\theta }_0)$ invertible and $B(z)=R_{\theta }(z,{\theta }_0)$. The implicit sensitivity at a state $z$ is $S(z)=-A(z{)}^{-1}B(z)$. Suppose the local inverse $\mathrm{\Psi }$ of $z\mapsto R(z,{\theta }_0)$, supplied near $z_{\ast }$ by the implicit function theorem, is defined on a convex residual neighborhood containing $0$ and $r=R(\tilde{z},{\theta }_0)$, with $\mathrm{\parallel }D\mathrm{\Psi }(y)\mathrm{\parallel }\le \kappa$ along their segment. Suppose also that the segment from $z_{\ast }$ to $\tilde{z}=\mathrm{\Psi }(r)$ lies in a convex neighborhood where $\mathrm{\parallel }A(z{)}^{-1}\mathrm{\parallel }\le M$, $\mathrm{\parallel }B(z)\mathrm{\parallel }\le B_0$, and $A,B$ are Lipschitz with constants $L_A,L_B$. Then $\mathrm{\parallel }S(\tilde{z})-S(z_{\ast })\mathrm{\parallel }\le \kappa (M^2{L}_A{B}_0+M{L}_B)\mathrm{\parallel }r\mathrm{\parallel }\mathrm{.}$ This bounds the implicit sensitivity formula evaluated at an approximate state. It is not by itself a bound for the derivative of a stopped iteration.

Let $R:\mathrm{\Theta }\times Z\to {\mathbb{R}}^m$ be $C^1$, where $\mathrm{\Theta }\subseteq {\mathbb{R}}^p$ and $Z\subseteq {\mathbb{R}}^m$ are open. Suppose $R({\theta }_0,z_0)=0$ and the state Jacobian $R_z({\theta }_0,z_0)$ is invertible. The Euclidean implicit function theorem gives a local $C^1$ solution branch $z=\varphi (\theta )$, and $D\varphi ({\theta }_0)=-R_z({\theta }_0,z_0{)}^{-1}{R}_{\theta }({\theta }_0,z_0)\mathrm{.}$ For a scalar $C^1$ objective $J(\theta ,z)$, its derivative along that branch is $D(J(\theta ,\varphi (\theta ))){\mathrm{\mid }}_{{\theta }_0}=J_{\theta }-J_z{R}_z^{-1}{R}_{\theta }\mathrm{.}$ Equivalently, if $\lambda$ solves $R_z^T\lambda =J_z^T$, this derivative is $J_{\theta }-{\lambda }^T{R}_{\theta }$. These formulas concern the exact local solution branch; differentiating a stopped iteration is a separate finite-map derivative.

Input a graph from Finite straight-line computational programs and real-arithmetic tapes, an admissible point $x$, and a direction $v\in {\mathbb{R}}^n$. Require every primitive to be $C^1$ on its declared open domain or supplied as a piecewise-$C^1$ primitive with the branch rules of the graph definition. Evaluate all primal node values in topological order and store the tape. Set each input tangent to ${\dot{z}}_{{\mathrm{i}\mathrm{n}}_i}={\dot{x}}_i=v_i$, using the distinct input labels of the graph. For each operation $j=1,\dots ,T$, compute ${\dot{z}}_j=D{\varphi }_j(z_{p_{j,1}},\dots ,z_{p_{j,r_j}})({\dot{z}}_{p_{j,1}},\dots ,{\dot{z}}_{p_{j,r_j}})\mathrm{.}$ Return the primal scalar output $f(x)$ and its tangent: return $(z_o,{\dot{z}}_o)$ if $o$ is an operation node, and $(x_i,v_i)$ if $o$ is input coordinate $i$. If the input is outside the admissible domain, return DOMAIN_ERROR; if a piecewise primitive is at a branch boundary or has no unique strict active branch, return NONDIFFERENTIABLE and no tangent. All derivative evaluations in this definition are exact real-arithmetic operations on the specified primitive maps.

Input a graph from Finite straight-line computational programs and real-arithmetic tapes and an admissible point $x$. Require every primitive to be $C^1$ on its declared open domain or supplied as a piecewise-$C^1$ primitive with the branch rules of the graph definition. Evaluate and store all primal values in topological order. Initialize every operation cotangent and every input cotangent to zero. Seed the scalar output by setting its cotangent to $1$: if $o$ is an operation, set ${\bar{z}}_o=1$; if $o$ is input coordinate $i$, set ${\bar{x}}_i=1$. For $j=T,T-1,\dots ,1$, and for every parent slot $k=1,\dots ,r_j$, compute the contribution $c_{j,k}=D_k{\varphi }_j(z_{p_{j,1}},\dots ,z_{p_{j,r_j}}{)}^T{\bar{z}}_j$ and add it to the cotangent accumulator of that parent: use ${\bar{x}}_i$ if the parent is input coordinate $i$, and ${\bar{z}}_{\mathrm{\ell }}$ if it is operation node $\mathrm{\ell }$. If the same parent node occurs in multiple slots, add every slot contribution. Return the scalar output $f(x)$ and the input cotangents $({\bar{x}}_1,\dots ,{\bar{x}}_n)$ as the Euclidean gradient. A point outside the admissible domain returns DOMAIN_ERROR; a branch boundary or ambiguous active branch returns NONDIFFERENTIABLE and no gradient. The procedure differentiates the real-arithmetic graph; it makes no floating-point error claim.

For a finite straight-line program whose primitives are $C^1$, the recursively defined admissible input domain is open on each fixed strict branch. The scalar output $f$ is $C^1$ there, and its total derivative is obtained by the ordinary chain rule through the primitive maps.

If every primitive of a finite straight-line program is $C^2$ on the selected open branch domains, then the real-arithmetic scalar output is $C^2$ on each fixed strict branch.

The input is a finite sequence of deterministic $C^1$ transitions $F_j:U_j\subseteq E_{j-1}\to E_j$, $j=1,\dots ,T$, between compatible finite-dimensional Euclidean spaces with open domains, a starting state $x_0\in E_0$, and a terminal cotangent ${\bar{x}}_T\in E_T$. Every transition is evaluated on one fixed strict branch and has its exact local reverse rule. For $T\ge 1$, require the last transition's output space to be $E_T=\mathbb{R}$; when that scalar output is the objective, take ${\bar{x}}_T=1$. For $T=0$, the terminal value is $x_0$ and its matching cotangent ${\bar{x}}_0$ is supplied. A transition tape stores the local values needed by its exact reverse rule. A deterministic replay applies the same transition maps, in the same order, to the identical checkpoint state and therefore reproduces the same values and local derivative inputs. The procedure returns the terminal value and cotangent at $x_0$; an invalid domain evaluation returns DOMAIN_ERROR, and a branch boundary returns NONDIFFERENTIABLE. A checkpoint schedule is permitted only when its saved states and all deterministic replays lie in these declared domains.

Uniform-block mode. For $T=0$, return $x_0$ and the supplied cotangent without work. For $T\ge 1$, require an integer slot budget $m\ge 1$, set $q=\lceil T\mathrm{/}m\rceil$, and during one forward pass save $x_{jq}$ for $j=0,\dots ,\lceil T\mathrm{/}q\rceil -1$ (all indices are below $T$). This uses at most $m$ saved states. Partition the steps into blocks $[a,b]$ with $a=jq$ and $b=\min (a+q,T)$. Process the blocks from last to first. Within one block, for $\mathrm{\ell }=b,b-1,\dots ,a+1$, restore $x_a$, replay $F_{a+1},\dots ,F_{\mathrm{\ell }-1}$ without recording, evaluate $F_{\mathrm{\ell }}$ once while recording its local tape, apply its reverse rule to the current cotangent, and discard the one-step tape and replay workspace. Retain only the checkpoint states, the live state/cotangent, and the ordinary one-step reverse tape. Do not infer any optimality property of this schedule.

Binomial mode. Define $C(d,0)=C(0,t)=1$, and $C(d,t)=C(d-1,t)+C(d,t-1)$ for integers $d,t\ge 1$. The top-level call takes nonnegative integer budgets $d,t$ satisfying $T\le C(d,t)$. For $T=0$, return $(x_0,{\bar{x}}_0)$. For $T\ge 1$, allocate one scalar output register $y$. The recursive procedure REVERSE$(a,N,d,t,x_a,{\bar{x}}_{a+N})$ consumes its starting state as the live primal state and its terminal cotangent as the mutable cotangent buffer; it returns only the cotangent at $x_a$, retaining no terminal primal state. It requires integer indices $0\le a\le a+N\le T$, nonnegative integer budgets $d,t$, and $N\le C(d,t)$. If $N=0$, return the unchanged cotangent. If $N=1$, evaluate and record the unique transition, copy its scalar output to $y$ if $a+1=T$, apply its local reverse rule, discard the tape and primal state, and return the input cotangent. If $N\ge 2$, then $d,t\ge 1$. Put $L=\min (N-1,C(d,t-1))$, $R=N-L$. Save $x_a$ in one checkpoint slot and replay the first $L$ transitions into the live state $x_{a+L}$ without recording. Call REVERSE$(a+L,R,d-1,t,x_{a+L},{\bar{x}}_{a+N})$ on the right block, keeping the saved $x_a$ but no other primal state in the caller. Move the saved $x_a$ back into the live state, release its checkpoint slot, and tail-call REVERSE$(a,L,d,t-1,x_a,{\bar{x}}_{a+L})$, using the cotangent returned by the right child. Return this left child's cotangent. No call frame retains a primal vector outside the explicit checkpoint slots. Invoke this procedure at $a=0,N=T$ and return $y$ with its returned initial cotangent. A recursive call with $N>1$ and $d=0$ or $t=0$ is a schedule failure; the capacity condition makes that branch unreachable.

The parameter $d$ bounds the number of simultaneously saved state snapshots. The parameter $t$ bounds, for each transition, the number of additional unrecorded forward evaluations beyond its one recorded evaluation. Both are finite integer inputs. This mode provides no numerical error estimate or optimality guarantee for arbitrary nonuniform primitive costs. For the storage count in the paired theorem, $R_s$ bounds scalar storage for one full primal state. The binomial recursion may reuse one mutable cotangent workspace: each call consumes its terminal cotangent and returns the cotangent at its start, reusing the same buffer through both children. Let $G$ bound the largest one-step tape and local reverse scratch, the constant number of live cotangent/work vectors, the scalar output register, and the scalar call-frame records; it excludes the $d$ saved primal states and one live primal state.

Input a finite-dimensional $C^1$ map $G(z,\theta )$, a $C^1$ initial-state map $z_0(\theta )$, a parameter $\theta$ in an open subset of ${\mathbb{R}}^p$, and an integer budget $K\ge 0$; the states lie in ${\mathbb{R}}^m$, with $p,m\ge 0$. Use the specified maps $z_0$ and $G$, with their exact derivative evaluations, as primitive maps on their declared open domains. Evaluate $z_0(\theta )$ and then $z_{k+1}(\theta )=G(z_k(\theta ),\theta )$ for $k=0,\dots ,K-1$. A primitive-domain failure returns DOMAIN_ERROR; a branch boundary or ambiguous active branch returns NONDIFFERENTIABLE and no derivative. The admissible case requires every evaluation to remain in its declared domain and, for piecewise primitives, on a unique strict active branch.

Allocate an $m\times p$ Jacobian array $J$. For each state coordinate $a=1,\dots ,m$, form the finite scalar-output graph for $f_a(\theta )=(z_K(\theta ){)}_a$ by appending the coordinate projection to the finite recursion. For each parameter coordinate $\mathrm{\ell }=1,\dots ,p$, call Forward-mode automatic differentiation on a finite computational graph on this graph at $\theta$ with direction $e_{\mathrm{\ell }}$, the $\mathrm{\ell }$th standard basis vector of ${\mathbb{R}}^p$, and put its returned tangent in $J_{a\mathrm{\ell }}$. Propagate any DOMAIN_ERROR or NONDIFFERENTIABLE status from a call. Return $(z_K(\theta ),J)$ with status ITERATES_DIFFERENTIATED. For $K=0$ the recursion contains only the initial-state map. If $m=0$ or $p=0$, the corresponding loops are empty and $J$ has the specified empty shape; the primal recursion is still evaluated. This procedure differentiates the $K$-step map actually specified by $G,z_0,K$; it does not substitute the derivative of an exact fixed point.

Input a $C^2$ graph, a point $x$, and direction $v$. Run Forward-mode automatic differentiation on a finite computational graph and retain its primal tape and all input and operation tangents. If that call returns DOMAIN_ERROR or NONDIFFERENTIABLE, return the same status and stop without a Hessian-vector product. Otherwise initialize every operation and input cotangent and tangent-cotangent accumulator to zero. Seed the output by setting its cotangent/tangent-cotangent pair to $(1,0)$: if $o$ is an operation, set $({\bar{z}}_o,{\dot{\bar{z}}}_o)=(1,0)$; if $o$ is input coordinate $i$, set $({\bar{x}}_i,{\dot{\bar{x}}}_i)=(1,0)$. In reverse topological order, for each node $j$ and parent slot $k$, let $A_{j,k}=D_k{\varphi }_j(z_{p_{j,1}},\dots ,z_{p_{j,r_j}})$, compute $c_{j,k}=A_{j,k}^T{\bar{z}}_j,{\dot{c}}_{j,k}=A_{j,k}^T{\dot{\bar{z}}}_j+(D{A}_{j,k}(z_{p_{j,1}},\dots ,z_{p_{j,r_j}})[{\dot{z}}_{p_{j,1}},\dots ,{\dot{z}}_{p_{j,r_j}}]{)}^T{\bar{z}}_j,$ and add $c_{j,k}$ and ${\dot{c}}_{j,k}$ to the parent's cotangent and tangent-cotangent accumulators. Use $({\bar{x}}_i,{\dot{\bar{x}}}_i)$ for input coordinate $i$ and $({\bar{z}}_{\mathrm{\ell }},{\dot{\bar{z}}}_{\mathrm{\ell }})$ for operation node $\mathrm{\ell }$. If the same parent occurs in multiple slots, add every slot contribution. Return $({\dot{\bar{x}}}_1,\dots ,{\dot{\bar{x}}}_n)$. Repeated parent slots receive separate additions. The admissible case requires every primitive evaluation to be in its declared domain and, for a piecewise primitive, on a unique strict active branch; a branch boundary or ambiguous selection returns NONDIFFERENTIABLE through the initial call. The transpose is the real Euclidean transpose, not a complex adjoint.

Let $f:\mathrm{\Omega }\to \mathbb{R}$ be the output of a finite $C^1$ program on a fixed strict branch. For every admissible $x\in \mathrm{\Omega }$ and direction $v\in {\mathbb{R}}^n$, the forward-mode algorithm returns $Df(x)v$.

For a finite $C^1$ program with one scalar output $f$, on a fixed strict branch and at every admissible $x$, the reverse-mode algorithm returns $Df(x{)}^{T}1$, the gradient of $f$. More precisely, at any operation node $i$, if its value is temporarily treated as an independent variable and all later operations are recomputed from it, then the accumulated cotangent at $i$ is the derivative of the scalar output with respect to that independent node value.

For a finite $C^1$ graph on a fixed strict branch, fix a finite set of scalar/vector primitive types with at most $r$ parent slots per operation and bounded dimensions. Suppose each operation $j$ has primal work $w_j\ge 1$, its local vector-Jacobian product costs at most $c{w}_j$ operations, and accumulating each parent-slot contribution costs at most $a$ operations. Assume each invocation's retained local tape and peak pullback scratch use at most a fixed number of scalar entries. Let $S$ be the scalar storage in the primal tape and input-gradient buffer, counting all input and node-value coordinates, per-node and per-parent metadata, branch labels, and retained local-tape entries. Then the exact reverse-mode algorithm for a scalar output uses at most $(1+c+ar){\sum }_{j=1}^T{w}_j$ operations for the primal evaluation, reverse sweep, and parent accumulations, and stores $O(S)$ scalar entries. Opaque solver calls are excluded unless their primal and derivative costs satisfy the same hypotheses.

Baur–Strassen proves a separate nonscalar arithmetic-circuit complexity theorem over an infinite field. The local bound above is proved directly for a fixed smooth primitive set with explicit primal/pullback cost ratios; it does not extend the arithmetic-circuit theorem to arbitrary opaque procedures or claim that every differentiable primitive has a cheap derivative.

For the finite-dimensional $C^1$ transition sequences on a fixed strict branch defined in Uniform-block and binomial checkpoint schedules for reverse sweeps, provided every schedule replay remains in the declared domains, both schedules return the same terminal value and initial-state cotangent as an uncheckpointed reverse sweep. In uniform-block mode, if $T,m\ge 1$, $q=\lceil T\mathrm{/}m\rceil$, and the block lengths are $r_1,\dots ,r_s$, excluding the initial forward pass used to save checkpoints, the number of additional unrecorded forward evaluations is exactly ${\sum }_{\mathrm{\ell }=1}^s{r}_{\mathrm{\ell }}(r_{\mathrm{\ell }}-1)\mathrm{/}2$, at most $mq(q-1)\mathrm{/}2$. At most $m$ checkpoint states are saved, with one live replay state and one local step tape. In binomial mode, $C(d,t)=\left(\genfrac{}{}{0px}{}{d+t}{d}\right)$; any $T\le C(d,t)$ steps can be reversed with at most $d$ saved snapshots, one recorded forward evaluation and one reverse evaluation per step, at most $t$ additional unrecorded forward evaluations per step, total work at most $\widehat{W}+\bar{W}+tW$, and storage $G+(d+1)R_s$. Here $W$ is the total cost of one unrecorded full forward pass, $\widehat{W}$ the sum of recorded one-step forward costs, $\bar{W}$ the sum of local reverse costs, $R_s$ bounds scalar storage for one primal state, and $G$ bounds the largest one-step tape and local reverse scratch, the constant number of live cotangent/work vectors, the scalar output register, and scalar recursion-frame records, excluding saved states and one live primal state.

Let $p,m\ge 0$, let $\mathrm{\Theta }\subseteq {\mathbb{R}}^p$ be open with ${\theta }_0\in \mathrm{\Theta }$, and let $G:U\to {\mathbb{R}}^m$ be $C^2$ on an open neighborhood $U\subseteq {\mathbb{R}}^m\times \mathrm{\Theta }$ of $D\times \{{\theta }_0\}$. Suppose $D\subseteq {\mathbb{R}}^m$ is an open convex neighborhood of $z_{\ast }$ and $z_{\ast }=G(z_{\ast },{\theta }_0)$. Assume $G(D,{\theta }_0)\subseteq D$, $\mathrm{\parallel }{G}_z(z,{\theta }_0)\mathrm{\parallel }\le q<1$ on $D$, and $G_z,G_{\theta }$ are Lipschitz in $z$ with constants $L_z,L_{\theta }$. Let $z_0:\mathrm{\Theta }\to {\mathbb{R}}^m$ be $C^1$, with the iterates at ${\theta }_0$ lying in $D$. Write $s_{\ast }=D\varphi ({\theta }_0)$ for the local exact fixed-point branch (supplied by the implicit function theorem when $p,m\ge 1$), $e_k=D_{\theta }{z}_k({\theta }_0)$, ${\delta }_0=\mathrm{\parallel }{z}_0({\theta }_0)-z_{\ast }\mathrm{\parallel }$, $d_0=\mathrm{\parallel }{e}_0-s_{\ast }\mathrm{\parallel }$, and $C=L_z\mathrm{\parallel }{s}_{\ast }\mathrm{\parallel }+L_{\theta }$. For every integer $K\ge 1$, $\mathrm{\parallel }{z}_K({\theta }_0)-z_{\ast }\mathrm{\parallel }\le q^K{\delta }_0,\mathrm{\parallel }{e}_K-s_{\ast }\mathrm{\parallel }\le q^K{d}_0+CK{q}^{K-1}{\delta }_0,$ with $q^0=1$ when $q=0,K=1$. If $R(z,\theta )=z-G(z,\theta )$ and $r_K=R(z_K({\theta }_0),{\theta }_0)$, then $(1-q)\mathrm{\parallel }{z}_K-z_{\ast }\mathrm{\parallel }\le \mathrm{\parallel }{r}_K\mathrm{\parallel }$. The derivative error is not bounded by the residual alone: for $G(z,\theta )=qz+(1-q)\theta$, ${\theta }_0=0$, and $z_0(\theta )=0$, every finite $K$ has residual zero at ${\theta }_0$ but $e_K=1-q^K\mathrm{\ne }1=s_{\ast }$ when $0<q<1$.