Lune

POPL2023Top-tier venue

You Only Linearize Once: Tangents Transpose to Gradients

Alexey Radul, Adam Paszke, Roy Frostig, Matthew J. Johnson, Dougal Maclaurin

Abstract

Automatic differentiation (AD) is conventionally understood as a family of distinct algorithms, rooted in two "modes"-forward and reverse-which are typically presented (and implemented) separately. Can there be only one? Following up on the AD systems developed in the JAX and Dex projects, we formalize a decomposition of reverse-mode AD into (i) forward-mode AD followed by (ii) unzipping the linear and non-linear parts and then (iii) transposition of the linear part.

To that end, we define a (substructurally) linear type system that can prove a class of functions are (algebraically) linear. Our main results are that forward-mode AD produces such linear functions, and that we can unzip and transpose any such linear function, conserving cost, size, and linearity. Composing these three transformations recovers reverse-mode AD. This decomposition also sheds light on checkpointing, which emerges naturally from a free choice in unzipping let expressions. As a corollary, checkpointing techniques are applicable to general-purpose partial evaluation, not just AD.

We hope that our formalization will lead to a deeper understanding of automatic differentiation and that it will simplify implementations, by separating the concerns of differentiation proper from the concerns of gaining efficiency (namely, separating the derivative computation from the act of running it backward).

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

8 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites Automatic differentiation in PCF
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites Backpropagation in the simply typed lambda-calculus with linear negation
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites A simple differentiable programming language
  • Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation cites Automatic differentiation in PCF
  • Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation cites Backpropagation in the simply typed lambda-calculus with linear negation
  • Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation cites A simple differentiable programming language
  • Automatic differentiation in PCF cites Backpropagation in the simply typed lambda-calculus with linear negation
  • Automatic differentiation in PCF cites A simple differentiable programming language
  • Efficient CHAD cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers8

  1. Fast Finite Width Neural Tangent KernelRoman Novak, Jascha Sohl-Dickstein, Samuel S. SchoenholzICML 2022 · 72 citations
  2. Probabilistic Programming with Programmable Variational InferenceMcCoy R. Becker, Alexander K. Lew, Xiaoyan Wang, Matin Ghavami et al.PLDI 2024 · 8 citations
  3. On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable ParametersWonyeol Lee, Sejun Park, Alex AikenICML 2023 · 6 citations
  4. Efficient CHADTom Smeding, Matthijs VákárPOPL 2024 · 6 citations
  5. Automatic Functional Differentiation in JAXMin LinICLR 2024 · 5 citations

Builds on4

  1. A simple differentiable programming languageMartín Abadi, Gordon D. PlotkinPOPL 2020 · 49 citations
  2. Automatic differentiation in PCFDamiano Mazza, Michele PaganiPOPL 2021 · 47 citations
  3. Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiationFaustyna Krawiec, Simon Peyton Jones, Neel Krishnaswami, Tom Ellis et al.POPL 2022 · 27 citations
  4. Backpropagation in the simply typed lambda-calculus with linear negationAloïs Brunel, Damiano Mazza, Michele PaganiPOPL 2020 · 24 citations

Related papers

  1. JAX Autodiff from a Linear Logic PerspectiveGiulia Giusti, Michele PaganiPOPL 2026
  2. Efficient Dual-Numbers Reverse AD via Well-Known Program TransformationsTom Smeding, Matthijs VákárPOPL 2023 · 10 citations
  3. AD for an Array Language with Nested ParallelismRobert Schenck, Ola Rønning, Troels Henriksen, Cosmin E. OanceaSC 2022 · 11 citations
  4. Collapsing Taylor Mode Automatic DifferentiationFelix Dangel, Tim Siebert, Marius Zeinhofer, Andrea WaltherNeurIPS 2025 · 1 citation
  5. What does automatic differentiation compute for neural networks?Sejun Park, Sanghyuk Chun, Wonyeol LeeICLR 2024
Dusk over the sea between two cliffs drawn in fine vertical lines