How Automatic Differentiation Computes Exact Derivatives
This article explains how automatic differentiation computes exact derivatives of complex computer programs efficiently and accurately. It explores the fundamental limitations of traditional numerical finite-difference methods and symbolic differentiation, which suffer from precision errors and computational bloat, respectively. Finally, it breaks down how automatic differentiation bypasses these flaws by decomposing code into elementary operations and systematically applying the calculus chain rule in either forward or reverse mode.
The Flaws of Traditional Differentiation
Before understanding automatic differentiation (AD), it is necessary to see why traditional methods fail in large-scale computing.
Numerical Differentiation (Finite Differences) approximates derivatives by perturbing an input by a tiny step size (\(h\)) and measuring the change in output: \(\frac{f(x + h) - f(x)}{h}\).
- Truncation Error: Because \(h\) cannot be infinitely small, the formula is only an approximation.
- Round-off Error: As \(h\) becomes smaller to improve accuracy, computers lose floating-point precision when subtracting two nearly identical numbers (\(f(x+h)\) and \(f(x)\)).
- Poor Scaling: If a function has a million inputs, you must run the function a million times to find the gradient.
Symbolic Differentiation manipulates mathematical expressions algorithmically using rules like the product rule to output a new algebraic formula for the derivative.
- Expression Swell: The resulting derivative formulas frequently grow exponentially larger than the original function, consuming massive memory and computation time.
- Control Flow Limitations: Symbolic math struggles
with standard programming constructs like
if-elsebranching,whileloops, and recursion.
The Core Mechanism of Automatic Differentiation
Automatic differentiation is neither numerical nor symbolic. Instead, it relies on a simple truth: every computer program, no matter how complex, executes as a sequence of elementary arithmetic operations (addition, subtraction, multiplication, division) and elementary functions (sine, cosine, exponential, logarithm).
AD works by tracking these primitive operations at runtime. Because the exact analytical derivative rules for these basic building blocks are already known, AD calculates the numerical derivative of each tiny step and combines them using the chain rule of calculus.
It avoids numerical truncation errors because it uses exact derivative formulas at the elementary level rather than dividing by a tiny step size. It avoids symbolic expression swell because it immediately evaluates intermediate derivatives as concrete floating-point numbers, rather than building giant algebraic strings.
Forward Mode vs. Reverse Mode
AD applies the chain rule in one of two ways, depending on the shape of the program's inputs and outputs.
Forward Mode
In forward mode, the derivative is computed alongside the original program's execution. For every intermediate variable \(v\) in the code, the computer also calculates its derivative \(\dot{v}\) with respect to a specific input.
This is often implemented using dual numbers, which pair a variable's value with its derivative: \(x + \dot{x}\epsilon\), where \(\epsilon^2 = 0\). When the program adds or multiplies two dual numbers, the value and the exact derivative update simultaneously in a single pass. Forward mode is exceptionally fast when a program has few inputs and many outputs.
Reverse Mode
When a program has millions of inputs and a single output—such as a neural network calculating a loss function—forward mode becomes too slow because it requires a separate pass for each input. Reverse mode solves this in two phases:
- The Forward Pass: The program runs normally to compute the output. However, AD records all elementary operations and intermediate values in a data structure called a computational graph (or "Wengert list").
- The Backward Pass: Starting from the final output, AD traverses the graph backward to the inputs. It multiplies the local derivatives step-by-step using the chain rule to find how much each input contributed to the final output.
Reverse mode calculates the exact derivative of one output with respect to millions of inputs in just a single backward pass. The famous "backpropagation" algorithm in machine learning is simply a specialized form of reverse-mode automatic differentiation.
Handling Program Control Flow
Unlike symbolic differentiation, AD handles if
statements, loops, and dynamic branching effortlessly. Because AD
operates on actual numerical values at runtime, it only differentiates
the exact execution path that the program takes for a given input. A
while loop that runs five times is simply recorded and
differentiated as a sequence of five consecutive blocks of elementary
operations.