- 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_fastshould bed_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
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.
Thank you for your detailed review and feedback!
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.
Edited, and explanation added
We introduce "IR" on L080. Perhaps there is somewhere else that is confusing?
Done!
Thank you, fixed!
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.
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 ofaandb. This merge operation is quadratic: for every entry instoreA, we must walkstoreBto 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.