Simply typed reverse-mode automatic differentiation with variants: denotational correctness via idempotent completion (Preprint)

  <Reference List>
Type: Preprint
National /International: International
Title: Simply typed reverse-mode automatic differentiation with variants: denotational correctness via idempotent completion
Publication Date: 2026-07-16
Authors: - Fernando Lucatelli Nunes
- Diogo Simm
- Matthijs Vákár
Abstract:

Reverse-mode automatic differentiation can be derived denotationally as a structure-preserving interpretation of program syntax. In the usual simply typed model, each source type has one cotangent type. Variants break this representation because the valid cotangent space depends on the branch selected at run time; established correctness results therefore use primal-indexed families of cotangent spaces, whose direct internal language is dependent. We show that this dependence can instead be represented in an ordinary nondependent target. The cotangent fibres of each source type are placed inside a common ambient type, and a primal-indexed idempotent selects the valid fibre. For a category \( \mathcal C \) and a regular infinite cardinal \( k \), we prove that the constant-family inclusion extends to an equivalence \( \mathsf{Kar}({\mathsf{Copow}}_k(\mathcal C)) ≃ {\mathsf{Fam}}_k(\mathcal C) \) precisely when \( \mathcal C \) is Cauchy complete and every \( k \)-small family admits a common retract host. The same host condition yields explicit coproducts after Karoubi completion. We use this result to construct a bicartesian closed semantics for reverse-mode AD with variants whose ambient types, projectors, and backpropagators are ordinary nondependent target terms. Splitting the generated idempotents recovers the dependent semantics, and the two interpretations are naturally isomorphic. The ambient backpropagator is consequently the unique map that agrees with the transposed derivative on the valid cotangent fibres and respects their projectors.

Institution: DMUC 26-40
Online version: http://www.mat.uc.pt...prints/eng_2026.html
Download: Not available
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Financiado total ou parcialmente pela FCT, Fundação para a Ciência e a Tecnologia, I.P., sob o Financiamento de:
UID/00324/2025 Projeto Estratégico com a referência DOI https://doi.org/10.54499/UID/00324/2025.
https://doi.org/10.54499/UID/PRR/00324/2025     UID/PRR/00324/2025   https://doi.org/10.54499/UID/PRR2/00324/2025   UID/PRR2/00324/2025
Powered by: rdOnWeb v1.4 | technical support