acceptodds
Under review as a conference paper at ICLR 2027

The Mode of Null-A: Compositional Computation of a Generalized Inverse

Abstract

We present a novel algorithm for calculating the preimage of an affine space through a product of matrices of special form: finding the largest input space such that implies , where is a given output affine space. These special matrices arise in AD, where the Jacobians describing the linearized computation have precisely this structure: the product of a series of linearized primitive numeric operations. This allows us to use the new algorithm to formulate Null-A mode preimage AD, which finds the affine preimage through the Jacobian or Jacobian transpose of a numeric computation. This is a generalization of the inverse AD problem of solving or . The key is to represent affine spaces in a fashion which lends itself to efficient preimage calculation, in a compositional and *quasi-local* fashion, through a succession of matrices . Unlike previous methods, Null-A preimage mode AD allows the matrices to be non-square, corresponding to a computer program whose number of active variables swells and shrinks during the computation. When is square and the initial affine space is a single point, this finds the conventional inverse. But in the more general case, having the entire affine space provides freedom which can be leveraged in a problem-specific manner. We apply the method to small problems on-CPU where the are linearized scalar unary or binary numeric functions; and to larger problems on-GPU where the are linearized aggregate array operations like convolution and attention.

Primary area:
optimization
Keywords:
Automatic Differentiation, Preimage Calculation, Affine Spaces, Optimization, Linear Computations, Pseudoinverse, Array Operations

Reviews

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

This paper proposes Null-A, which propagates affine solution sets through a program's Jacobian or its transpose, including when stepwise Jacobians aren't invertible. It reports speedups over CG on small transformer models.

Critical strengths

The method handles rectangular and singular stepwise Jacobians, so inverse AD no longer requires the number of live variable to stay constant. Affine space slices with deferred updates give a concrete implementation of this. Returning the full affine solution set lets users choose a solution by another criterion, e.g. sparsity, which point solvers like CG cannot.

Critical weaknesses
  1. The only GPU baseline is CG on JJ⊤JJ^\top. The authors attribute the largest gains to ill-conditioning, but no condition numbers are reported. Table 1-3 report no residuals for the Null-A's origin or basis while Table 1 reports CG residuals. CG's tolerance and iteration cap are also not specified, so it's unclear whether the methods produce equally accurate results. Comparisons with LSQR/LSMR and a direct QR/SVD method that also returns the affine solution set would help.
  2. The paper doesn't show when the full preimage is worth the cost. The GPU experiments form dense block Jacobians and use small models. In the GPT-2 width sweep, Null-A's advantage shrinks (42x faster at width 8, 2x faster at width 32, but actually 2.25x slower than CG at width 40). No memory usage or timing breakdown (e.g. Jacobian vs. preimage computation) is reported. The prompt-editing example also doesn't compare against solving the sparse problem directly without forming the preimage.
Questions for authors
  1. For each setting in Table 1-3, what are the relative residuals of Null-A's returned origins and basis? What stopping tolerance and iteration cap did CG use?
  2. For the largest GPT-2 case (width 40), what's the peak memory usage? How is the runtime split between constructing the block Jacobians and computing the preimage?
1 comment
AuthorsOpenReview ↗

Final Thoughts

We thank the reviewers and AC for engaging and their insightful comments. The focus on benchmark comparisons with existing methods, however, has allowed the conversation to drift far away from the truly novel contribtion of our submission, stated clearly in the title and abstract. The Null-A method computes the full preimage, and does so in a compositional fashion that operates by a single overloaded execution of the program.

CG, LSQR, and LSMR are point solvers and do not compute the full preimage. They are incomparable, as they do not yield the same result. QR and SVD are not compositional, and not matrix-free. They require explicit computation and representation of the full Jacobian for the entire program, which is infeasible for large programs because it grows as O(mn)O(mn) space for programs ℜn→ℜm\Re^n\rightarrow\Re^m. Null-A is a novel method, we hope even the first instance of a new class of affine-space-based methods, and should be evaluated as such rather than in a benchmark comparison framework.

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

The paper tackles the tough problem of inverse automatic differentiation by proposing a technique to compute to handle non-square Jacobians.

Critical strengths

I should preface my comments by admitting that I am not an expert in this area. My comments are therefore more generic and not about the specific technique itself.

With the caveat that I am not familiar with the mathematical background works involved (which, by the way, seems old, especially by today's standard), I think it is nice that the problem of non-square Jacobian has been solved by the work.

Critical weaknesses

My main concerns here are more generic.

  1. How does the method compare to the current practices? Since extremely large LLMs with tensors of different shapes do can trained successfully via backpropagation, how will the paper's work affect the overall system performance? Will it result in better accuracy? Or faster convergence?

  2. The tests conducted seem limited. It is done on MLPs only and not on entire models. Also (as in Question 1), how do the results compare with compare with the current backpropagation approach of just taking the transpose?

  3. The result seems mixed at best. By the authors' own admission: "Null-A mode preimage AD is faster on ill-conditioned, wide-output, small-to-moderate problems. CG is faster on well-conditioned, narrow-output, large ones." This seems to limit the practice impact of the method.

In summary: seems nice as a mathematical curiosity, but unclear on the overal practical impact.

Questions for authors

See above.

1 comment
AuthorsOpenReview ↗

Final Thoughts

We thank the reviewers and AC for engaging and their insightful comments. The focus on benchmark comparisons with existing methods, however, has allowed the conversation to drift far away from the truly novel contribtion of our submission, stated clearly in the title and abstract. The Null-A method computes the full preimage, and does so in a compositional fashion that operates by a single overloaded execution of the program.

CG, LSQR, and LSMR are point solvers and do not compute the full preimage. They are incomparable, as they do not yield the same result. QR and SVD are not compositional, and not matrix-free. They require explicit computation and representation of the full Jacobian for the entire program, which is infeasible for large programs because it grows as O(mn)O(mn) space for programs ℜn→ℜm\Re^n\rightarrow\Re^m. Null-A is a novel method, we hope even the first instance of a new class of affine-space-based methods, and should be evaluated as such rather than in a benchmark comparison framework.

Reviewer_VgAQOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper generalizes inverse automatic differentiation — solving linear systems through the Jacobian or its transpose of a program — to computing the preimage of an affine space, removing the constant-width restriction of prior inverse-AD work and handling programs whose number of active values changes during execution. The key mechanism is an affine-space-slice data structure with lazily applied updates, which makes preimage propagation through the primitive linear maps of a computation graph compositional and quasi-local. The framework nests, giving inverse-Hessian-vector products and Newton steps. Validation includes a scalar CPU implementation verified to give exact answers and to match the predicted complexity, and a GPU implementation with block primitives for layers and transformer blocks, benchmarked against a conjugate-gradient baseline on small MLPs and GPT-2 configurations, where the proposed method is faster except at the largest sizes and the baseline sometimes fails outright. A demonstration selects a sparse prompt edit inside the returned preimage, which point solvers cannot do.

Critical strengths
  1. The generalization from point inverses to affine-set preimages is conceptually novel and clean, and the slice representation with delayed updates is a genuinely new mechanism for exploiting the near-identity structure of stepwise Jacobians. The symmetric four-mode presentation is instructive, and the comparison against conjugate gradients is honest about where each side wins and fails.
  2. Returning a full preimage rather than a single point enables post-hoc selection inside the solution space. The token-edit demonstration is a small but convincing proof of concept that this capability matters in practice, not merely in form.
Critical weaknesses
  1. The validation is far below the scale of the motivating workloads. The GPU experiments use very small MLPs and toy GPT-2 configurations, the only baseline is conjugate gradients, and the growth of the preimage dimension with depth, sequence length, and batch which decides whether the cost, quadratic in program length, is practical — is neither analyzed nor measured.
  2. Much of the substance lives in a very long appendix dominated by code listings, so the main-text benchmark claims cannot be assessed without heavy cross-reading, and the numerical-stability discussion is brief given that rank decisions drive correctness.
Questions for authors
  1. How does the preimage dimension grow with depth, sequence length, and batch in your experiments, and what is the observed scaling on one configuration approaching a realistic model, even if the method is slower there?
  2. Why is conjugate gradient the only baseline? A comparison with prior constant-width inverse-AD methods, and with a dense solve at small scale, would position the contribution better.
  3. What is the measured numerical error of the returned spaces on the GPT-2 sweeps as the conditioning worsens?
  4. The running header required by the submission template is absent from all pages, which suggests a modified style file. I am raising this with the AC separately; it does not affect my assessment.
1 comment
AuthorsOpenReview ↗

Final Thoughts

We thank the reviewers and AC for engaging and their insightful comments. The focus on benchmark comparisons with existing methods, however, has allowed the conversation to drift far away from the truly novel contribtion of our submission, stated clearly in the title and abstract. The Null-A method computes the full preimage, and does so in a compositional fashion that operates by a single overloaded execution of the program.

CG, LSQR, and LSMR are point solvers and do not compute the full preimage. They are incomparable, as they do not yield the same result. QR and SVD are not compositional, and not matrix-free. They require explicit computation and representation of the full Jacobian for the entire program, which is infeasible for large programs because it grows as O(mn)O(mn) space for programs ℜn→ℜm\Re^n\rightarrow\Re^m. Null-A is a novel method, we hope even the first instance of a new class of affine-space-based methods, and should be evaluated as such rather than in a benchmark comparison framework.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Answered all questions, addressed all weaknesses

Please note that we have answered all the reviewers' questions and addressed all critical weaknesses. This involved considerable effort and substantial computational resources. We have not yet heard back from the reviewers acknowledging our response to the reviews, and are a bit concerned that the reviewers may have simply disappeared.

We have conducted new experiments in response to reviews which demonstrate that Null-A can indeed run on the largest open-source LLM currently available, namely Apertus v1.5, a 70×10⁹-parameter model.

  • On one 80GB H100 in double precision, Null-A computes the full preimage at the inputs of that model (24,576 input variables, 42 constraints) in 17 minutes, with residuals of 4×10⁻¹² for the origin and 4×10⁻¹³ for the basis, while matrix-free CG takes 5.7 hours to return a single point with residual 4×10⁻⁹.

  • On one 128GB DGX Spark in single precision, Null-A computes the same preimage in 2.0 hours using 33 GiB, with the dimension exact and residuals of 2×10⁻³ for the origin and 4×10⁻⁴ for the basis.

These results should ameliorate any concerns about numeric stability.

AuthorsOpenReview ↗

Final Thoughts

We thank the reviewers and AC for engaging and their insightful comments. The focus on benchmark comparisons with existing methods, however, has allowed the conversation to drift far away from the truly novel contribtion of our submission, stated clearly in the title and abstract. The Null-A method computes the full preimage, and does so in a compositional fashion that operates by a single overloaded execution of the program.

CG, LSQR, and LSMR are point solvers and do not compute the full preimage. They are incomparable, as they do not yield the same result. QR and SVD are not compositional, and not matrix-free. They require explicit computation and representation of the full Jacobian for the entire program, which is infeasible for large programs because it grows as O(mn)O(mn) space for programs ℜn→ℜm\Re^n\rightarrow\Re^m. Null-A is a novel method, we hope even the first instance of a new class of affine-space-based methods, and should be evaluated as such rather than in a benchmark comparison framework.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.