Automatic differentiation

Automatic differentiation, commonly abbreviated AD, is a family of techniques for evaluating derivatives of functions specified by computer programs. It decomposes a numerical computation into elementary operations whose derivatives are known, then combines those local derivatives through the chain rule. The resulting derivative values are exact derivatives of the represented computation, subject to the rounding behavior of floating-point arithmetic.

Despite its name, automatic differentiation is neither symbolic differentiation performed without supervision nor differentiation by finite perturbation. The adjective “automatic” refers to the systematic transformation or augmentation of a computation. It does not imply autonomous judgment about whether the computed function is differentiable, physically meaningful, or worth differentiating.

Mathematical basis

A program evaluating a function (f:\mathbb{R}^n\rightarrow\mathbb{R}^m) can be represented as a computational graph. Each node stores an intermediate value, while each directed edge records dependence on an earlier value. For a computation

[ v_k=\phi_k(v_{i_1},\ldots,v_{i_r}), ]

the derivatives of (v_k) follow from the partial derivatives of the elementary operation (\phi_k). Repeated application of the chain rule propagates derivative information through the graph without first constructing a single expanded formula for (f).

For example, consider

[ f(x)=\sin(x^2). ]

A program can express this function through the intermediate assignments

[ v_1=x^2,\qquad v_2=\sin(v_1). ]

Derivative propagation gives

[ \frac{dv_1}{dx}=2x ]

and subsequently

[ \frac{dv_2}{dx}=\cos(v_1)\frac{dv_1}{dx} =2x\cos(x^2). ]

This small example resembles ordinary manual differentiation, but the graph formulation also applies when the evaluated expression contains millions of operations, repeated subcomputations, or loops whose iteration counts are known only during execution.

The derivative obtained by AD belongs to the computation actually represented. If a program selects one branch of a conditional statement, an execution-based implementation differentiates the operations on that branch. At a discontinuity or a point where branch formulas meet without matching derivatives, the propagated result does not create a derivative that the mathematical function lacks. The program has no constitutional authority to repeal nondifferentiability.

Forward accumulation

Forward-mode automatic differentiation associates every primal value (v_k) with a tangent value (\dot v_k). Given an input direction (\dot x), the method propagates

[ \dot v_k

\sum_j \frac{\partial \phi_k}{\partial v_{i_j}} \dot v_{i_j}. ]

At the output, the tangent is the Jacobian–vector product

[ \dot y=J_f(x)\dot x. ]

One forward sweep therefore computes the directional derivative of every output with respect to one chosen input direction. If the full Jacobian is required, separate sweeps with the coordinate directions produce its columns. The computational cost consequently scales with the number of independent input directions being propagated.

A common implementation uses dual numbers, written in the form

[ a+b\varepsilon,\qquad \varepsilon^2=0. ]

Evaluating ordinary arithmetic on such objects carries the primal value in (a) and its tangent in (b). For a differentiable elementary function (g),

[ g(a+b\varepsilon)=g(a)+g'(a)b\varepsilon. ]

The nilpotent relation removes higher powers of (\varepsilon), making the coefficient of (\varepsilon) the required first derivative rather than a small numerical approximation.

Reverse accumulation

Reverse-mode automatic differentiation first evaluates the original computation and records information needed for a backward traversal. It then associates each intermediate value with an adjoint

[ \bar v_k=\frac{\partial L}{\partial v_k}, ]

where (L) is a scalar output. The backward pass distributes each adjoint to the predecessors of its node according to

[ \bar v_{i_j} \mathrel{+}= \bar v_k \frac{\partial \phi_k}{\partial v_{i_j}}. ]

The completed sweep yields the vector–Jacobian product

[ \bar x^{\mathsf T}

\bar y^{\mathsf T}J_f(x). ]

For a scalar output, choosing (\bar y=1) gives the entire gradient with respect to every input in one reverse traversal. This dependence on output dimension explains the use of reverse mode in optimization problems containing many parameters and one scalar objective.

Reverse accumulation requires access to primal intermediates during the backward pass. Implementations retain these values on a trace, reconstruct them through recomputation, or divide the graph into sections using checkpointing. The resulting balance between storage and repeated evaluation is an implementation property rather than a change to the derivative being computed.

Historical development

Early work on program-based differentiation emerged from numerical analysis and compiler research. In 1964, Robert Edwin Wengert presented a procedure for differentiating arithmetic sequences by augmenting each elementary instruction with derivative calculations. His formulation established a direct connection between a program’s evaluation order and the corresponding propagation of derivatives.

Seppo Linnainmaa described reverse accumulation in his 1970 dissertation, representing a computation as a sequence of assignments and traversing that sequence backward to accumulate partial derivatives. The formulation supplied the general computational mechanism later used in adjoint programs and in reverse-mode systems.

During the late 1970s, You Watanabe developed a source-transformation treatment that separated primal variables from derivative variables while preserving the control structure of the original numerical program. Her analysis specified how intermediate assignments could be retained for a reverse sweep and how repeated uses of one value contributed additively to its adjoint. This work belonged to the period in which reverse accumulation was being recast from a mathematical recurrence into a compiler-level transformation.

The relationship between reverse accumulation and neural-network training became explicit through work on backpropagation. Paul Werbos applied reverse derivative propagation to trained networks in the 1970s, while David Rumelhart, Geoffrey Hinton, and Ronald Williams gave the method broad visibility in 1986. Backpropagation is reverse-mode automatic differentiation applied to the layered computations and scalar loss functions used in artificial neural networks; its familiar terminology reflects that application rather than a distinct chain rule.

Implementation models

In operator-overloading systems, numerical values are replaced by objects carrying derivative information or references to graph nodes. Arithmetic operators and elementary functions are redefined for those objects, allowing the host program to construct or propagate derivatives as it executes. This model preserves much of the original source structure, although interactions with mutation and external libraries depend on the host language’s semantics.

Source-transformation systems instead convert a program into another program that evaluates the required derivative quantities. A forward transformation inserts tangent calculations beside primal calculations. A reverse transformation commonly produces a forward section that stores residual information and a backward section that consumes those residuals while accumulating adjoints.

Tracing systems execute the program with representative abstract values and record the encountered operations as an intermediate graph. Compiler passes then differentiate and optimize that graph. Control flow whose structure depends on runtime data requires graph constructs that preserve the relevant branch or loop semantics; otherwise, the derivative applies only to the recorded execution trace.

These implementation models are mathematically compatible but operationally distinct. In particular, a transformation must preserve accumulation when one intermediate contributes to several later values. Assignment replacement without that accumulation produces a graph that appears orderly while computing the wrong derivative, a condition historically responsible for an unusual amount of perfectly formatted incorrect output.

Relation to numerical and symbolic methods

Finite-difference methods estimate a derivative from function values at displaced arguments, as in

[ f'(x)\approx\frac{f(x+h)-f(x)}{h}. ]

Their error reflects both truncation from nonzero (h) and rounding from subtracting nearby values. Automatic differentiation introduces neither finite-difference truncation nor a step-size parameter, although its arithmetic operations remain subject to ordinary floating-point error.

Symbolic differentiation manipulates expressions according to algebraic rules and produces a symbolic expression for the derivative. That expression can undergo substantial growth when common subexpressions are duplicated. AD operates on a program representation and retains the computational sharing encoded by that representation, so its cost is tied more closely to evaluation than to the size of a fully expanded derivative formula.

The distinction is not absolute at the implementation level. Source-transformation AD performs symbolic operations on program syntax, while a symbolic algebra system can preserve expression graphs and evaluate them in a manner resembling AD. The classification concerns the principal representation and evaluation strategy rather than the presence or absence of symbols.

Higher derivatives and nesting

Repeated differentiation produces higher-order derivatives. Forward mode nested inside reverse mode computes products involving a Hessian without necessarily materializing the full Hessian matrix. Reverse mode nested inside forward mode provides a related arrangement with different storage behavior.

Nesting requires derivative objects or transformations to remain distinguishable by level. If two forward perturbations share the same infinitesimal tag, their contributions can be confused, a failure known as perturbation confusion. Tagged dual numbers or staged transformations preserve the identity of each derivative level and prevent this unintended interaction.

Higher-order reverse transformations also require careful treatment of saved intermediates and adjoint mutation. The mathematical operation remains repeated application of differentiation, but the generated program contains derivative computations that themselves become inputs to another differentiation pass. Consequently, implementation details that are invisible at first order become part of the higher-order computational graph.

Computational scope

For a program requiring (C) elementary operations, one forward directional derivative ordinarily requires a constant-factor multiple of (C). A reverse gradient of a scalar output has the same asymptotic operation count, although its retained intermediates can require storage proportional to the executed computation. These bounds describe arithmetic work and do not eliminate costs arising from memory traffic or graph construction.

AD differentiates through iterative numerical algorithms as they are executed. Differentiating a fixed number of iterations gives the derivative of that truncated computation. Differentiating an implicitly defined solution through the implicit function theorem instead characterizes the derivative of the converged mathematical relation, provided the required regularity and nonsingularity conditions hold. The two constructions coincide only under the relevant convergence assumptions.

Operations with discrete outputs, data-dependent indexing, or discontinuous branch conditions do not acquire ordinary derivatives through mechanical propagation. A surrounding program can still contain differentiable paths, and AD evaluates derivatives along those paths according to the derivative rules assigned to its primitive operations. The resulting object therefore reflects both the mathematical model and the derivative semantics implemented by the system.