acceptodds
Under review as a conference paper at ICLR 2027

DiffDog: Formally Verified Automatic Differentiation at Billion-Parameter Scale

Abstract

As AI training runs grow in scale, cost, and complexity, software errors become increasingly consequential. Yet mainstream automatic differentiation (AD) libraries at the heart of these training runs rely on Python-centered stacks that are unable to provide machine-checkable correctness guarantees. We present \DiffDog, a formally verified AD system in Lean that supports arbitrarily nested forward- and reverse-mode AD, automatic vectorization, and compilation to GPU and TPU executables, with machine-checked correctness proofs for its tracing, differentiation, and vectorization transformations. Programs written against \DiffDog's abstract array interface can be instantiated over mathematical value types for direct reasoning and over traceable array types for compilation to accelerators. This dual interpretation provides an extensible foundation for developing verified models, numerical algorithms, and program transformations without relinquishing high-performance accelerated execution. We exhibit \DiffDog's expressiveness and utility by training a language model with verified gradients, introducing the first accelerator-executable SGD optimizer with verified convergence, and demonstrating that \DiffDog automatically synthesizes a counterexample to Adam's original convergence claim, independently exposing the failure identified by DBLP:conf/iclr/ReddiKK18. Finally, \DiffDog's training and inference throughput is competitive with optimized JAX and PyTorch implementations on leading open-weight models, including Qwen 3.8-27B and Gemma 4.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
automatic differentiation, machine learning compiler

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ir4LOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper presents DiffDog, a numerical tensor library in Lean that provides tensor shape verification, automatic differentiation correctness, and "cheap gradients" verification. Furthermore, the paper verifies optimizer convergence guarantees and automatically rediscovers counterexamples to known issues in Adam convergence claims. DiffDog includes a verified tracing mechanism for vectorization (vmap), for its automatic differentiation (grad) and for just-in-time compilation through the StableHLO → XLA pipeline, by compiling their internal intermediate representation to StableHLO. The authors demonstrate the usefulness of DiffDog for real applications by training (and fine-tuning) a 125M-parameter GPT-2 model and by LoRA fine-tuning, prefilling, and running 27B-parameter LLMs. They show differentiation performance surpassing that of Python's JAX and PyTorch, and on-par runtime performance. DiffDog enables users to "mathematically reason" about and execute the same program, allowing for formal verification of parts of the technology stack without sacrificing performance.

Critical strengths

DiffDog can be seen as JAX in Lean and it shows interesting and promising results in both the formal verification aspects and the practicality by fine-tunning big models. The authors must have put significant efforts into this project, providing a Lean-based framework, using it for verification themselves, verifing the tracing step, adding a high-efficient XLA compilation route, and successfully fine-tune billion-parameter-scale models. Also it shows faster automatic differentiation (and thus tracing) than both PyTorch and JAX – a significant achievement given that these libraries are maintained by teams over years. DiffDog is a significant step towords a formal verified deep learning stack to partially verified application, reducing the trust we must put into systems.

There is overlap with existing work like TorchLean, but there is enough novelty in showing successful application at scale (billions of parameters) paired with some formalizations (e.g., optimizer convergence).

Critical weaknesses

The main text is difficult to read and does not give justice to the great work done. The title overclaims, contributions are not stated clearly, and multiple statements are contradictory, confusing, or even wrong. I think these issues can be addressed during the rebuttal phase or in the camera-ready version:

  • The title overclaims: The billion-parameter-scale path is not verified (e.g., the XLA compiler). This work verifies tensor programs on top of a partly verified technical stack that supports the billion-parameter scale.

  • The introduction fails to lay out the contributions clearly (e.g., by listing them), making it unnecessarily difficult for readers to understand the paper’s contributions.

  • Section 3.1 is confusing: Section 3.1 could be easier to understand if the introduction, related work, and background did a better job of explaining the “standard” functional AD methods and DiffDog’s contribution. The following parts of this section are particularly confusing:

    • The referential-transparency problem is “solved” by relying on withPtrEq, which undermines the narrative developed over multiple paragraphs about why it is difficult or impossible in Lean. The final method (withPtrEq) is then in line with existing functional AD methods. In my view, the method’s novelty lies in verifying the tracing and allowing AD/tracing without requiring an abstraction such as a state monad (e.g., TorchLean).

    • “Care is taken to preserve topological ordering” is non-technical and must be clarified. Do you preserve a partial dependency order rather than a total execution order, similar to ScalaGrad?

    • Finally, the IR is motivated by the need to manipulate a program as “data”; however, the traced DAG can already be viewed as data. It is unclear why a separate IR is necessary.

  • Other missing, contradictory, confusing, or incorrect statements:

    • L35: “Software stack […] remains largely unchanged” is incorrect. The period in question saw new tensor libraries (JAX), JIT-compilation-based frameworks, mixed- and low-precision training, new fused kernels (FlashAttention), and new distributed-training capabilities.

    • L170: “Are not representable in Lean” seems factually incorrect. For example, TorchLean does this through a state monad. It is a matter of trade-offs.

    • L485: “Autonomous research agents” is unrelated to anything demonstrated in the paper and does not fit its conclusion.

    • L493: The AI-use statement contains sentence fragments that begin mid-sentence.

Minor flaws that should be addressed

  • Footnote 1: Something is claimed to have been “found […] to be ill-suited” without any explanation. Please explain why.

  • The abbreviation IR is used several times before being introduced in L156.

  • Section 3.4: loss_fast should be d_loss_fast. Rename it for clarity.

  • L481: “Still” appears twice.

  • Several formulations are odd or unclear: “fresh,” “à la,” “hard-liners,” “footholds,” “blessed,” and “AD system.”

Questions for authors

Section 3.3: It is unclear to me why nested AD does not work out of the box. AD takes a function f and returns a function df. Applying AD to the resulting df should result in a new function ddf. Confusion can only occur if you rely on a shared resource (e.g., a global state), which should be impossible in functional Lean?

Footnote 2: Why cubic in the worst case? I’d expect exponential. The main text states it this way for residual connections.

3 comments

Thank you for your detailed review and feedback!

The title overclaims: The billion-parameter-scale path is not verified (e.g., the XLA compiler). This work verifies tensor programs on top of a partly verified technical stack that supports the billion-parameter scale.

Apologies for the confusion. Our viewpoint is that we are providing an AD framework with a verified core that also supports running models at billion-parameter scale. Although formally verifying XLA would be interesting, it is not clear whether this is sufficient either: other parts of the runtime remain, including CUDA, device drivers, and the hardware itself.

Footnote 1: Something is claimed to have been “found […] to be ill-suited” without any explanation. Please explain why.

Edited, and explanation added

The abbreviation IR is used several times before being introduced in L156.

We introduce "IR" on L080. Perhaps there is somewhere else that is confusing?

Section 3.4: loss_fast should be d_loss_fast. Rename it for clarity.

Done!

L481: “Still” appears twice.

Thank you, fixed!

Section 3.3: It is unclear to me why nested AD does not work out of the box. AD takes a function f and returns a function df. Applying AD to the resulting df should result in a new function ddf. Confusion can only occur if you rely on a shared resource (e.g., a global state), which should be impossible in functional Lean?

Good question! This is the "perturbation confusion" trap. You are correct in a certain sense, but the devil is in the details when symbolic values from different differentiation stages interact. See eg https://mural.maynoothuniversity.ie/id/eprint/566/1/Perturbation.pdf for example.

Footnote 2: Why cubic in the worst case? I’d expect exponential. The main text states it this way for residual connections.

Good catch. Indeed the naive solution results in exponential time reverse mode AD, but with a bit of cleverness we are able to get tracing down to cubic time. Specifically, in each symbolic value we track its "store," the list of instructions that cover its provenance, like an immutable Wengert tape. Then at operations like a + b, we construct a new symbolic value by merging the stores of a and b. This merge operation is quadratic: for every entry in storeA, we must walk storeB to find a corresponding entry if it exists. Finally, in the worst case every node of our computation graph requires merging stores, meaning that we incur this quadratic cost a linear number of times.

It may be possible to speed up this method, eg by using a hashmap to accelerate the linear search, but this is not something we explored since it would still not achieve linear time.

I thank the authors for answering my questions. In particular, the explanation of the cubic time was very interesting.

My main critique remains that the main text is difficult to understand and could be improved significantly, which is why I maintain my score, although I appreciate the underlying work! Some points raised in my review were also not addressed or commented on (e.g., L170, L485).

To move to an "accept" score, the main text would need to be clearer, which requires more fundamental revisions that I believe are out of scope for the rebuttal. I state them here in case of resubmission: clarify the paper's story between verification and scaling; clarify advantages over related work like TorchLean (e.g., vmap and scaling); and describe the method at a high level, explaining how you achieved tracing without any extra mechanism (e.g., a state monad) compared with others: tracing the partial order of dependencies vs. tracing the (total) execution order. This needs more than rewording: the paper has to articulate precisely what the core technical contribution is, why it works, and how it differs from related work. I think that requires the authors to first work this positioning out in more depth, so that it is stated explicitly in the paper rather than left for the reader to reconstruct.

Thank you for your feedback on the paper and its clarity. We always strive to present as clearly as possible, and we appreciate your feedback.

In the short-term, we address these comments,

L485: “Autonomous research agents” is unrelated to anything demonstrated in the paper and does not fit its conclusion.

Removed

L493: The AI-use statement contains sentence fragments that begin mid-sentence.

We attempted to follow the provided template (https://iclr.cc/Conferences/2027/AIPolicyForAuthors) as closely as possible. If ACs/PCs can confirm that it is ok to deviate from the template, we would be keen to edit for clarity.

L170: “Are not representable in Lean” seems factually incorrect. For example, TorchLean does this through a state monad. It is a matter of trade-offs.

Edited for clarity. In a language like Python a DAG can be represented with nodes containing pointers to their children. The graph may be constructed with mutation and sharing (a node with multiple parents) in this data structure is accomplished via pointer aliasing. Because Lean is referentially transparent it would be appear to Lean code as a tree with all sharing replaced with duplicated subtrees. In the case of resnets this results in an exponential blowup.

Reviewer_iydwOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

An AD system with arrays is implemented in Lean, and its correctness verified for code that has only one level of differentiation (no nesting). The system supports nested AD operators, both forward and reverse. It also admits to an aggressive GPU-enabled implementation whose performance is competitive with JAX and PyTorch. Formal verification of an optimizer fails, revealing a (known) bug, which is addressed to yield an end-to-end formally-verified stochastic gradient optimizer with verified O(1/√t) convergence.

Critical strengths

Construction of verified high-performance AD system suitable for deep learning is a lovely connection between AI coding agents (that actually generate these proofs) and the substrate they're built upon. It is a sort of tying of the knot, perhaps even a step in the direction of using these systems to establish verifiable safety properties for these very systems.

Critical weaknesses

There are a few technical issues I'd like to bring up.

  1. The language used for writing the functions being differentiated is quite weak: it supports only a single static dataflow graph (given the input type), without conditionals or loops.

  2. Although the language claims to admit to nested derivative operators, the correctness of nesting is not verified for technical reasons. Perturbation confusion is prevented (maybe) by "branding" as in the Haskell ad package https://hackage.haskell.org/package/ad but, particularly given the discovery of higher-order perturbation confusion (Manzyuk et al, 2019, DOI: 10.1017/S095679681900008X), a proof would be nice. Basically, the proof of correctness restricts itself to the easiest case: no nesting, at a nice obviously differentiable point. Proofs should give us confidence about the tricky situations!

  3. This is a minor issue, but the system uses "tracing" for reverse mode, with a trick to handle structure sharing. This is the same as the Haskell ad package, which calls the operation reifyGraph. This deserves a pointer.

  4. The RegularAt idea sounds nice in principle (can't calculate the derivative at a point where the function ain't differentiable) but, due to the geometry of the situation, optimization often seeks precisely points where the non-linearity hits a hinge, so such points are far from measure zero in the distribution of points encountered in practice. There are various tricks to deal with this issue, but a formalization of saying "who cares" at least deserves some justification, if only to defer a proper solution to future work.

  5. The O∂yssée Fortran preprocessor AD system (Faure, 2005, "An automatic differentiation platform: Odyssée", DOI: 10.1016/j.future.2004.11.006), which has both forward and reverse accumulation mode automatic differentiation, was proven correct in Coq (Mayero, 2002, "Using Theorem Proving for Numerical Analysis: Correctness Proof of an Automatic Differentiation Algorithm", DOI: 10.1007/3-540-45685-6_17). That system appears to anticipate the present proof: it has a stronger language (Fortran includes loops and conditionals) and I believe establishes the same properties as the present manuscript: correct forward and reverse AD without nesting. AD is a meta-operator instead of being in-language, but with nesting precluded this is a much smaller difference than it might appear at first blush.

  6. It is claimed that nesting is supported, but not verified. In the examples in the code, a manual ⇧ is inserted to indicate closed-over variables. But this ⇧ appears, in actuality, to be the proverbial camel's nose in the tent. I tried to write some code involving nesting.

    diffdog-nesting.lean

    /-
    Nesting in DiffDog: what one wants to write, and what one has to write.
    
    Each "have to write" is checked by DiffDog's own compiled code (`native_decide`). It keeps
    only the annotations Lean cannot infer: removing any one of them makes it fail to elaborate.
    Each "want to write" is rejected, with the error shown.
    -/
    import ADSystem2.F32Sig
    import ADSystem2.VerifyTrace
    import ADSystem2.ADable.Arithmetic
    
    open scoped F32Backend
    set_option synthInstance.maxSize 1024
    
    abbrev C := LeanArray DDFloat32
    
    /-! ## A function used at two levels: d/dx (x·x + x) at 5 = 11
    
    What I want to write:
    
        ∂ (fun x =>
            let f y := x * y
            f x + ∂ f x)
          5
    
    Rejected at `∂ f`: `f` has type `S✝¹ [] → S✝¹ []`, but `∂` needs a function of every
    inner carrier. -/
    
    -- What I have to write:
    example : (∂ (fun {R} _ [Interpretable F32Sig R] [R ⊒ C] x =>
        let f {S} [Interpretable F32Sig S] [S ⊒ R] (y : S []) := ⇧x * y
        @f _ _ ⟨fun a => a⟩ x + ∂ f x)
      5).unscalar = 11 := by native_decide
    
    /-! ## A function of functions, nested three deep: 75
    
    `f (f (fun z => z * x))` is `y ↦ x³ y + x⁴`, its derivative in `y` is `x³`, and
    d/dx x³ at 5 is 75.
    
    What I want to write:
    
        ∂ (fun x =>
            let f g y := x * g y + (x * x / 2) * ∂ g y
            ∂ (f (f (fun z => z * x))) x)
          5
    
    Rejected at `∂ g`: `g` is inferred as a function of one carrier, but `∂` needs a function of
    every inner carrier. -/
    
    -- What I have to write:
    example : (∂ (fun {R} _ [Interpretable F32Sig R] [R ⊒ C] x =>
        let f (g : ∀ {T} [Carrier F32Sig T] [Interpretable F32Sig T] [T ⊒ R], T [] → T [])
            {T} [Carrier F32Sig T] [Interpretable F32Sig T] [T ⊒ R] (y : T []) : T [] :=
          ⇧x * g y + (⇧x * ⇧x / 2) * ∂ (fun {V} _ _ _ z => @g V _ _ ⟨fun a => ⇧(⇧a : T _)⟩ z) y
        ∂ (f (f fun {T} _ _ _ z => z * (⇧x : T []))) x)
      5).unscalar = 75 := by native_decide
    

    The necessary type annotations were inserted by an AI coding agent; I, and it seems reasonable to speculate most working programmers, would have found them quite difficult to formulate correctly without such assistance.

Questions for authors
  1. Verification aside, nesting is expressible in the language as given. However it is not clear to me whether the system is sufficiently expressive to allow higher-order perturbation confusion. As shown above (W.6) nesting requires extremely elaborate type annotations, with the implementation level leaking through. I'm not sure if this is necessary, or alternatively whether it would be possible to build an AD subsystem in lean which has the correct type for the derivative-taking operators thus avoiding exposing programmer to such elaborate type filagree.

  2. I'm a bit confused about the motivation here. There is a lot going on. It seems a mash-up of six topics:

    (1) an AD language similar to R6RD-AD, PyTorch, or JAX (albeit a bit more restricted, and typed) embedded in Lean instead of Scheme or Python.

    (2) a partial (since it does not handle nesting) machine proof similar to the Coq proof for O∂yssée.

    (3) a compiler from floating-point computation graphs produced by tracing to GPU/TPU code using XLA and MLIR. This is the same as PyTorch and JAX.

    (4) branding to prevent first-order perturbation confusion; this is the same as Haskell ad.

    (5) the machine rediscovery of a bug in the convergence proof for Adam and fix thereof.

    (6) a reimplementation of GPT-2 and Qwen, to provide benchmarks.

    It's all nice, and uses modern clean substrates, and the high performance using less scruffy tools is great to see. But each one seems a bit shallow as presented, due perhaps to length restrictions on the manuscript. Perhaps it would make sense break this up into coherent subsets and go a bit deeper?

6 comments
AuthorsOpenReview ↗

Nested AD ergonomics are a weakness, but our goal is a formally verified alternative to JAX and PyTorch (1/2)

Thank you for your detailed feedback, responses, and attention to the code! We have taken some time to address your concerns as thoroughly as possible.

The language used for writing the functions being differentiated is quite weak: it supports only a single static dataflow graph (given the input type), without conditionals or loops.

Support for loops and conditionals was considered, but turned out to be unnecessary in the implementation of any of the models we studied. We touch on this briefly in the "Instructions and straight-line bodies" paragraph of Appendix A.2.

Our planned path towards adding them is to convert Instr into an inductive, with separate constructors for primitive ops, conditionals, and loops. The primitive op version would look exactly as it does today. Conditional and loop constructors would take ANFFuns for their sub-blocks.

We felt that this complexity would be more confusing than helpful in this initial presentation of the project and we did not find a need for them in our experiments, but we agree that supporting them is a relevant follow up.

This is a minor issue, but the system uses "tracing" for reverse mode, with a trick to handle structure sharing. This is the same as the Haskell ad package, which calls the operation reifyGraph. This deserves a pointer.

Thanks for the reference! We have added a citation for ad to the paper.

As we mention in another comment as well, the ad package has two reverse mode implementations. Its "Reverse" implementation uses a mutable tape. Its "Kahn" implementation is the closest in spirit to our approach but relies on StableName (https://downloads.haskell.org/~ghc/5.04.2/docs/html/base/System.Mem.StableName.html) and unsafePerformIO which provide heap identities. Their counterpart in Lean, ptrAddrUnsafe, is not compatible with Lean's proof system (you can use it to prove False). One interpretation of our tracing implementation is that it is an adaptation of the "Kahn" method to work within Lean's pure, proof-friendly type system.

We invite you to read our full comparison in the Extended Related Works section.

The RegularAt idea sounds nice in principle (can't calculate the derivative at a point where the function ain't differentiable) but, due to the geometry of the situation, optimization often seeks precisely points where the non-linearity hits a hinge, so such points are far from measure zero in the distribution of points encountered in practice. There are various tricks to deal with this issue, but a formalization of saying "who cares" at least deserves some justification, if only to defer a proper solution to future work.

Agreed, handling points of non-differentiability is inherently challenging. As you note, we opted to handle this via RegularAt which asserts the differentiable domain of each operation, and we discuss limitations and possibility for extension in Footnote 4. Our decision making here is based on a few points,

  1. RegularAt is defined inductively per-op, and individual op regularity conditions are straightforward to compare with mathematical reality.
  2. The composition of RegularAt constructions for whole programs is automatic and proof-carrying, so it is machine-checked and trustworthy.
  3. We believe RegularAt is the appropriate abstraction to build additional constraints on in future work. We did not make this a focus in this paper, but we agree that hardening the regularity conditions could be an interesting avenue for future work.

Out of curiosity, what is the argument that optimization seeks points of non-differentiability? In neural networks, they constitute a measure zero set, so it would be somewhat surprising for the optimizer to happen upon them.

The O∂yssée Fortran preprocessor AD system (Faure, 2005, "An automatic differentiation platform: Odyssée", DOI: 10.1016/j.future.2004.11.006), which has both forward and reverse accumulation mode automatic differentiation, was proven correct in Coq (Mayero, 2002, "Using Theorem Proving for Numerical Analysis: Correctness Proof of an Automatic Differentiation Algorithm", DOI: 10.1007/3-540-45685-6_17). That system appears to anticipate the present proof: it has a stronger language (Fortran includes loops and conditionals) and I believe establishes the same properties as the present manuscript: correct forward and reverse AD without nesting. AD is a meta-operator instead of being in-language, but with nesting precluded this is a much smaller difference than it might appear at first blush.

Thank you for these references! We have added them to the Related Works.

We would like to emphasize that although O∂yssée includes support for loops and conditionals, Mayero's correctness proof is limited to straight-line programs and does not cover control flow.

With regards to being in-language vs not: Mayero translates the O∂yssée algorithm into Coq and verifies this translated version. Bugs are still possible in the translation. In any case, we contend that being in-language in Lean does offer benefits beyond the proofs as well, including connection to mathlib, user ergonomics, static array shape checking, and so on.

Re nested AD and the expressibility of AD in Lean:

Thanks for taking a look at the code! Indeed, the ergonomics of nested AD fall short of our mathematical ideal. As to whether the formality is necessary, DiffDog is our attempt at the simplest and most elegant solution possible within Lean. We are confident that we have gotten close to the essence of things with the core of DiffDog and its IR. However, presenting a user-friendly frontend on top of that core is another challenge, esp. when it comes to nested AD. We are happy to have arrived at a usable interface for non-nested AD code, but as you note the nested AD case is unwieldy.

Nested AD in particular presents some friction because a certain amount of pedantry is required to distinguish separate tracing and differentiation levels, and secondly nested AD has not been a focus for us thus far because it is relatively uncommon in deep learning.

We have thus far eschewed metaprogramming in the frontend, but alas Lean's type inference and elaboration only goes so far, and it stands to reason that a touch of metaprogramming may be appropriate in the frontend. Regarding the code you sent, we found that with a bit of metaprogramming in ∂ your first test case becomes

   example :
       (∂ (fun x =>
           let f y := x * y
           f x + ∂ f x)
         5).unscalar = 11 := by native_decide

Unfortunately your second test case uses higher-order functions, something that we do not officially support, and alas we were unable to find a nice metaprogramming solution in time for this rebuttal period. Code: https://paste.rs/Ktug1 and https://paste.rs/8ZaHl.

But we are eager to explore ways to improve this, and are always open to simplifications. It may be interesting to explore what modifications to Lean would be necessary to unlock natural AD, including its full generality: higher-order functions, nested AD, native loops+conditionals, and so on. Modifying Lean was not something we considered in this work, but we would be curious to better understand what this might look like in the future!

Reviewer_iydwOpenReview ↗

Optimization seeking non-differentiable points

Out of curiosity, what is the argument that optimization seeks points of non-differentiability? In neural networks, they constitute a measure zero set, so it would be somewhat surprising for the optimizer to happen upon them.

Not to get off on too much of a tangent, but there's a reason they call min⁡wE(w)+λ∥w∥1\min_{\mathbf{w}} E(\mathbf{w})+\lambda\lVert \mathbf{w} \rVert_1 “ridge regression”. Consider a 1D example with λ=1\lambda=1 and no data, min⁡w∣w∣\min_w |w|, the optimum is at w=0w=0 which is precisely where ∣w∣|w| is non-differentiable. In general in constrained optimization problems the optimum often has multiple active constraints. E.g., in linear programming the optimum is at a vertex of the feasible polytope, where each facet of the polytope is defined by a linear ≥ constraint.

Reviewer_fR4LOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

DiffDog is a Lean-based automatic differentiation framework combining formal correctness guarantees with accelerator execution. It supports user-defined array operations, differentiation and vectorization transformations, optimizer verification examples, and competitive throughput on large language-model workloads.

Critical strengths
  • Connecting mathematical reasoning with accelerator execution is a valuable contribution toward more reliable machine-learning software.

  • The introduced design connects mathematical reasoning with executable programs and allows users to add operations with their own correctness proofs.

  • The optimizer convergence proofs, gradient bound, and language-model experiments demonstrate complementary uses of the system. The experimental reporting documents the hardware and software configurations, timing protocol, and modifications made to the baseline implementations in sufficient detail.

Critical weaknesses
  • The connection between the correctness results and the demonstrated models needs clarification. Section 3.3 describes tracing certificates and correctness proofs for individual operations, but it does not clearly identify which of these cover the experimental models or under what exact assumptions gradient correctness are guaranteed.

  • The performance results demonstrate competitiveness only on one GPU in float32, with billion-parameter training limited to LoRA updates. Section 4.3.2 acknowledges some of these restrictions. However, the implications of the changes made to the JAX baselines and the slower PyTorch implementation used for Gemma in float32, discussed in Appendix A.8, deserve greater emphasis when presenting the performance conclusions.

Questions for authors
  • For each model used in the experiments, which tracing certificates and proofs of individual derivative rules were checked, and under what exact assumptions is gradient correctness guaranteed?

  • Section 3.3 explains that nested AD relies on metatheoretic reasoning rather than internal Lean correctness theorems. Could the authors state the precise correctness claim and the assumptions supporting that reasoning?

5 comments

Thank you for your feedback!

The connection between the correctness results and the demonstrated models needs clarification. Section 3.3 describes tracing certificates and correctness proofs for individual operations, but it does not clearly identify which of these cover the experimental models or under what exact assumptions gradient correctness are guaranteed.

For each model used in the experiments, which tracing certificates and proofs of individual derivative rules were checked, and under what exact assumptions is gradient correctness guaranteed?

Yes, these experimental models enjoy full proof coverage: verified correct gradients, and so on. We have updated Section 4.3.2 to clarify!

The performance results demonstrate competitiveness only on one GPU in float32, with billion-parameter training limited to LoRA updates. Section 4.3.2 acknowledges some of these restrictions. However, the implications of the changes made to the JAX baselines and the slower PyTorch implementation used for Gemma in float32, discussed in Appendix A.8, deserve greater emphasis when presenting the performance conclusions.

Thank you for raising this. To address your concerns we added results for full fine-tuning and added an explicit statement of these limitations inside 4.3.2 to clarify before the limitations discussed in the conclusion.

Section 3.3 explains that nested AD relies on metatheoretic reasoning rather than internal Lean correctness theorems. Could the authors state the precise correctness claim and the assumptions supporting that reasoning?

Good question! We rely on rank-2 types (aka branding) to distinguish values from different differentiation levels. In essence, at each call site grad f x, we mint a rank-2 type, say \alpha, and tag tracer values with it. Then inside f, another call to grad would mint its own, separate rank-2 type \beta, and Lean's type system refuses to unify rank-2 types \alpha and \beta, preventing the user from accidentally mixing tracers across incompatible grad levels. (OTOH Lean will happily unify \alpha with \alpha and \beta with \beta.)

Because this depends on the behavior of Lean's type system around rank-2 types instead of operating at the level of Lean values, this behavior falls outside the scope of statements that can be formalized and proved within Lean itself, hence the metatheory comment.

Nevertheless, the argument for its correctness can be made inductively: Consider a finite nesting of AD operators and begin from the innermost AD invocation. In this context, all external values must enter the context via explicit lifting because of Lean's refusal to unify disparate rank-2 types. The explicit lifting operation clears these values of their external derivative context and freshly anoints them as constants within the inner context, matching the mathematical definition of nested derivatives.

Then, the inner grad produces the mathematically correct function, and this function is then interpreted into the outer context during tracing. And from here the process repeats, covering any finite nesting of AD operators by induction.

In this context, all external values must enter the context via explicit lifting because of Lean's refusal to unify disparate rank-2 types.

This is an intuitive argument, and sounds plausible. But it breaks down for derivatives of higher-order functions (Manzyuk et al, 2019, DOI: 10.1017/S095679681900008X) and it is not entirely clear to me that it holds even in the first-order case in the presence of higher-order functions used internally: perhaps defined at one level but closed over in other levels. This is the kind of subtle thing that we need actual proofs for. (I think it still goes through, but ... famous last words.)

Indeed, DiffDog does not officially support AD with higher-order functions. Supporting AD of higher-order functions would be exciting, but it is not currently clear to us how this could be done in Lean in a satisfactory way. One could go the language-in-a-language route: define a small language in Lean possibly including higher order functions, then define AD semantics on that language and prove its correctness in Lean. But then you end up with a language-in-a-language staging type thing like TensorFlow or Theano that have proven less convenient and less popular than the tracing, define-by-run style tools like JAX and PyTorch.

Comments on the paper

4 comments
~Jeffrey_Mark_Siskind1OpenReview ↗

novelty

Tracing a program with overloaded primitives to produce a floating-point computation graph for AD is neither particularly novel nor complicated. It has been done by many systems in many programming languages, including Fortran (e.g., ADOL-F), C++ (e.g., ADOL-C, FADBAD++, CppAD), Scheme (e.g., R6RS-AD), ML (e.g., Siskind & Pearlmutter, AD2016), Haskell (e.g., Kmett's ad package), Julia (e.g., ReverseDiff.jl), and Python (e.g., HIPS Autograd), among many others, going back three decades or more. R6RS-AD is only 462 lines. It has been taught in university courses for at least six years (49 lines; https://github.com/qobi/ece59500cv, https://github.com/qobi/ece49595cv, https://github.com/qobi/ece59500nl). A rewrite in Lean seems straightforward.

Using rank-2 polymorphism to brand perturbations and thereby prevent perturbation confusion is also not particularly novel. It is based on Haskell's runST (Launchbury & Peyton Jones, PLDI 1994) and was applied to perturbation confusion in AD by Chung-chieh Shan (https://conway.rutgers.edu/~ccshan/wiki/blog/posts/Differentiation/) and subsequently in the Haskell fad package (https://hackage.haskell.org/package/fad) and Kmett's ad package.

Compiling a floating-point computation graph to GPU code with tools like XLA is also not particularly novel. JAX and PyTorch do this routinely. Jeff Dean previewed this direction at the NIPS 2016 autodiff workshop ("TensorFlow: Future Directions for Simplifying Large-Scale Machine Learning"; https://autodiff-workshop.github.io/2016.html). Before XLA, Theano did this (Bergstra et al., SciPy 2010).

Machine-checked proofs of the correctness of AD are also not particularly novel, e.g., Reid & Gamboa (ITP 2011, ACL2), Selsam, Liang & Dill (ICML 2017, Lean), Chin Jen Sem (MSc thesis, Utrecht, 2020, Coq), and de Vilhena & Pottier (LMCS 2023, a machine-checked proof of a define-by-run reverse-mode AD library). See also Huot, Staton & Vakar (FoSSaCS 2020) for semantic correctness proofs.

The scale of the experiments (billion-parameter models) and the performance achieved appear to be attributable to XLA rather than to any contribution of this submission.

Our goal is to develop a formally verified alternative to JAX and PyTorch. We believe that this is best served by building the simplest, cleanest system possible, and using best-of-breed techniques and ideas from the AD and MLSys literature in the process. Alas, some innovations were still required, e.g. in implementing a non-monadic tracing implementation that is amenable to Lean's proof system, and in the development of a dependently typed core IR for array computations.

Certainly, AD has been studied for over 60 years, and much has happened in research and teaching including your courses as you point out. We humbly attempt to pay tribute to the existing literature in our treatment of the Related Works and Extended Related Works sections.

Re tracing: Alas none of the existing tracing implementations, including the ones you cite, are admissible within pure, sorry-free, non-monadic Lean:

  • ADOL-C uses a mutable Wengert-style tape
  • FADBAD++, CppAD, and R6RS-AD, ReverseDiff.jl, use mutable bookkeeping for primals, cotangents, and node relationships
  • Kmett's ad package includes two implementations. Its "Reverse" implementation uses a mutable tape and relies on IORef, unsafePerfromIO, and unsafeCoerce. Its "Kahn" implementation is the closest in spirit to our approach but relies on StableName (https://downloads.haskell.org/~ghc/5.04.2/docs/html/base/System.Mem.StableName.html) and unsafePerformIO which provide heap identities. Their counterpart in Lean, ptrAddrUnsafe, is not compatible with Lean's proof system (you can use it to prove False). We have added a paragraph on ad in the Extended Related Works.
  • HIPS autograd's forward graph construction is pure, but its reverse mode implementation uses heap identities to avoid repeatedly traversing shared computations.

Re the existing machine-checked proofs in AD:

  • Reid & Gamboa (2011) implemented symbolic differentiation, not AD.
  • We already cite Selsam, Liang & Dill (2017) as the first formally verified AD system in Lean. However, they rely on an axiomatization of calculus, whereas we integrate directly with mathlib's Frechet derivative. Also they focus on stochastic backpropagation whereas we focus on general AD.
  • Chin Jen Sem (2020) does not implement a formally verified reverse mode (https://github.com/crtschin/thesis/blob/master/thesis/conclusion.tex).
  • de Vilhena & Pottier (2023) supports a very small language including only constants 0, 1, addition, and multiplication.
  • Huot, Staton & Vákár (2020) provide a pen-and-paper proof of AD correctness, no machine-checked implementation. Also they focus on forward mode AD, and they acknowledge their reverse mode AD does not run in the usual linear time.
AuthorsOpenReview ↗

Synopsis of the discussion

Hello Reviewers, ACs, Senior ACs, and PCs,

For your convenience, we thought it prudent to bring the main points of the discussion together in one place.

To recap: DiffDog is a formally verified alternative to JAX and PyTorch. This paper introduces DiffDog, and evaluates the utility of such a formally verified AD framework in real-world deep learning practice. Our goal is to deliver a new, practically-relevant tool to the deep learning community.

We identify a few key themes in the discussion period so far.

  1. Comment "novelty" (here) and reviewer iydw mentioned related papers in the tracing-based AD lineage and requested clarification on the novelty of the tracing implementation in DiffDog. In response, we have added a discussion of Kmett's ad library, and clarified that none of the referenced prior methods translate to proof-friendly Lean due to their use of purity escape hatches like unsafePerformIO. We also emphasize that our intended contribution is the DiffDog system itself and tracing, though it presented a substantial technical hurdle, is a means towards that end.
  2. Reviewers fR4L and ir4L asked how the proofs apply to the models in Table 1. In response we have edited the paper to clarify that all experiments enjoy the full correctness guarantees of the system.
  3. Reviewer iydw supplied example programs and expressed surprise that loops, conditionals, and higher-order AD were unsupported, and that nested AD involved additional syntax. In response, we identified small syntax/metaprogramming changes that bring their nested AD test case in line with mathematical notation (here). Loops, conditionals, and higher-order AD are explicitly out of scope for us, as our focus is on mainstream deep learning use cases. We discuss the extensibility of DiffDog to potentially cover these features as future work here.

We feel two results in particular make the case for DiffDog.

  1. Users can prove properties of the training algorithms they run. We use the same array interface to implement an accelerator-executable SGD optimizer and prove its O(1/T)O(1/\sqrt{T}) convergence rate. Applying the same machinery to Adam automatically produces a counterexample to its original convergence claim, independently recovering the failure identified by Reddi et al. These examples show what a user gains from having AD inside the proof assistant.
  2. DiffDog's verified AD implementation works at the scale of current open-weight models. In response to fR4L, we added full fine-tuning alongside LoRA. On a single B300 in float32, DiffDog and JAX achieve 359 and 360 tokens/s respectively on Qwen 3.8-27B, and 1,234 and 1,216 tokens/s on Gemma 4 26B-A4B (Table 1). To isolate the work done by the AD frontend itself, Fig. 4 separately measures construction of the backward program before compilation. On the 32-layer GPT-2 benchmark, DiffDog is 6x faster than JAX and 101x faster than PyTorch. Unlike prior verified AD work, DiffDog offers performance that makes it usable for real work with large models.

Thank you to the Reviewers for reading the paper and trying the code, and to the ACs for your consideration of the paper and discussion! We hope this synopsis helps.

All the best,

The DiffDog Authors

Reviewer_iydwOpenReview ↗

Still Thin

I appreciate the synopsis, so I feel I should explain my perspective that leads to my low rating.

  • The AD system is not fully amenable to proofs: nesting is a problem, but so is the tracing mechanism. When you get down to it, an equivalent first-order expression (unfolding) is constructed for a functional program with a first-order signature. Proving correctness of a derivative of a first-order expression is not a big advance, and that is what is actually verified.

  • The ADAM counterexample etc is not really related to the AD engine. You could just assume correct gradients, the same way we assume correct arithmetic or linear algebraic operations. It is a machine proof/rediscovery of a known result.

  • The performance is entirely due to translating a first-order expression (with structure sharing) into XLA and feeding that into the appropriate execution engine. The "billion parameters" is due to treating arrays as atomic objects, and is not a testimony to DiffDog itself.

  • It is unclear to me that the system, including all its tracing machinations, achieves the complexity guarantees expected of reverse mode AD. Certainly this is not verified, due to issues with the tracing mechanism and the proof system. Even if this complexity property holds, that is not exactly a major accomplishment: it is replicating in lean4 the same thing that has been done for many decades in many other languages.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.