Lune

POPL2024Top-tier venue

Efficient CHAD

Tom Smeding, Matthijs Vákár

Abstract

We show how the basic Combinatory Homomorphic Automatic Differentiation (CHAD) algorithm can be optimised, using well-known methods, to yield a simple, composable, and generally applicable reverse-mode automatic differentiation (AD) technique that has the correct computational complexity that we would expect of reverse-mode AD. Specifically, we show that the standard optimisations of sparse vectors and state-passing style code (as well as defunctionalisation/closure conversion, for higher-order languages) give us a purely functional algorithm that is most of the way to the correct complexity, with (functional) mutable updates taking care of the final log-factors. We provide an Agda formalisation of our complexity proof. Finally, we discuss how the techniques apply to differentiating parallel functional array programs: the key observations are 1) that all required mutability is (commutative, associative) accumulation, which lets us preserve task-parallelism and 2) that we can write down data-parallel derivatives for most data-parallel array primitives.

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.

3 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

  • You Only Linearize Once: Tangents Transpose to Gradients cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • JAX Autodiff from a Linear Logic Perspective cites You Only Linearize Once: Tangents Transpose to Gradients
  • JAX Autodiff from a Linear Logic Perspective cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • JAX Autodiff from a Linear Logic Perspective cites δ is for Dialectica
  • JAX Autodiff from a Linear Logic Perspective cites Efficient Dual-Numbers Reverse AD via Well-Known Program Transformations
  • δ is for Dialectica cites You Only Linearize Once: Tangents Transpose to Gradients
  • Efficient Dual-Numbers Reverse AD via Well-Known Program Transformations cites AD for an Array Language with Nested Parallelism
  • Efficient Dual-Numbers Reverse AD via Well-Known Program Transformations 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 papers3

  1. Efficient Dual-Numbers Reverse AD via Well-Known Program TransformationsTom Smeding, Matthijs VákárPOPL 2023 · 10 citations
  2. JAX Autodiff from a Linear Logic PerspectiveGiulia Giusti, Michele PaganiPOPL 2026
  3. DeCo: A Core Calculus for Incremental Functional Programming with Generic Data TypesTimon Böhler, Tobias Reinhard, David Richter, Mira MeziniOOPSLA 2026

Builds on5

  1. Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiationFaustyna Krawiec, Simon Peyton Jones, Neel Krishnaswami, Tom Ellis et al.POPL 2022 · 27 citations
  2. You Only Linearize Once: Tangents Transpose to GradientsAlexey Radul, Adam Paszke, Roy Frostig, Matthew J. Johnson et al.POPL 2023 · 13 citations
  3. AD for an Array Language with Nested ParallelismRobert Schenck, Ola Rønning, Troels Henriksen, Cosmin E. OanceaSC 2022 · 11 citations
  4. Efficient Dual-Numbers Reverse AD via Well-Known Program TransformationsTom Smeding, Matthijs VákárPOPL 2023 · 10 citations
  5. δ is for DialecticaMarie Morgane Kerjean, Pierre-Marie PédrotLICS 2024 · 1 citation

Related papers

  1. A simple differentiable programming languageMartín Abadi, Gordon D. PlotkinPOPL 2020 · 49 citations
  2. Aδ: autodiff for discontinuous programs - applied to shadersYuting Yang, Connelly Barnes, Andrew Adams, Adam FinkelsteinSIGGRAPH 2022 · 17 citations
  3. ParDiff: Efficiently Parallelizing Reverse-Mode Automatic Differentiation with Direct IndexingShuhong Huang, Shizhi Tang, Yuan Wen, Huanqi Cao et al.PPoPP 2026
  4. Backpropagation in the simply typed lambda-calculus with linear negationAloïs Brunel, Damiano Mazza, Michele PaganiPOPL 2020 · 24 citations
  5. Automatic differentiation in PCFDamiano Mazza, Michele PaganiPOPL 2021 · 47 citations
Dusk over the sea between two cliffs drawn in fine vertical lines