Linear Transformers Implicitly Discover Unified Numerical Algorithms

We thank the reviewer for their positive feedback on our paper's core idea and for recognizing its novelty. We appreciate the thoughtful questions regarding the choice of a linear transformer and the path to extending our work. We are happy to provide additional details and context.

On the Methodological Framework (Linear Transformer & Task Scope)

The reviewer's main concern is that our focus on a single task with a linear transformer limits the contribution. We would like to clarify that these were deliberate methodological choices aimed at making the discovery of the transformer's implicit algorithm tractable and interpretable.

• The simple architecture was a result of principled simplification, not a starting assumption. Our goal was to isolate the computational essence of the learned algorithm. To do this, we performed a systematic simplification process, as described in the Algorithm extraction section (p. 4) and Appendix B.5 (p. 22). For example, we found that performance was maintained even after pruning the model from eight attention heads down to a single head per layer. The resulting "linear, attention-only" model is therefore not an arbitrary limitation, but rather the outcome of a principled approach to uncover the fundamental algorithm learned by the transformer.

• The transformer learns a simple, structured hyperparameter scheme. A crucial part of algorithm discovery is identifying the hyperparameters. A surprising result of our work is that the transformer simplifies this process immensely. [cite_start]After the simplification procedure, we found that the learned weights revealed a clear, interpretable rule for the step-size parameters of EAGLE. As shown in Section 4 ("Rationale for Weights", p. 5) and Figure 5 (p. 7), the learned weights correspond to fixed constants ($\eta,\gamma$) combined with an automatic normalization based on the data's spectral norm ($\\|A\_\ell\\|\_{2}^{-2}$). This discovery transforms a potentially complex hyperparameter tuning problem into a simple, parameter-free update rule, providing strong evidence that the transformer is uncovering a robust and elegant numerical method.

• A "linear transformer" is not a linear model. This is a critical point of clarification. A "linear transformer" is not a linear function of its input data. The attention update is fundamentally non-linear—specifically, it is cubic in the data activations $Z$. This is shown explicitly in the derivation in Appendix C.3 (Eq. 4). The term 'linear' simply refers to the absence of an additional, point-wise non-linear activation (like a ReLU), which our simplification process found to be unnecessary for this task.

On Generalizing the "EAGLE Method" and Future Work

We agree with the reviewer that extending this work is an exciting direction. We believe reviewer comments may stem from a potential ambiguity in the term "EAGLE method," which can refer to either the specific algorithm or our discovery process.

• The EAGLE algorithm is task-specific. The specific two-line update rule we call EAGLE is the algorithm the transformer discovered for the Nyström-type matrix completion problem. It is a powerful second-order solver for this task, but we would not expect it to solve a different problem like sparse regression.

• The discovery process is highly general. The core transferable contribution of our work is the methodology for discovering the implicit algorithm. We demonstrate this concretely in Appendix D (p. 25), where we apply this same process to a related but distinct parameter estimation task, revealing a slightly modified, highly efficient version of EAGLE. This shows the process is not a one-off trick. We are actively applying this framework to other domains like sparse regression and high-dimensional classification.

Answers to Specific Questions

• Why a linear transformer? How to extend to the non-linear regime? As explained above, the choice was a result of a principled simplification to enable algorithm discovery. The model is already non-linear in its data dependence. Our ongoing work on other tasks (e.g., classification) shows that this same discovery process reveals algorithms where non-linear activation functions (like ReLU or GeLU) are kept, as they are essential for those tasks.

• What real-world tasks can EAGLE be implemented for? The specific EAGLE algorithm is a second-order solver for least-squares problems based on Nyström approximation. It is therefore well-suited for real-world scenarios that rely on this technique, such as large-scale kernel methods, recommender systems, and statistical inference.

• How numerically stable is the algorithm? Do you find places where it diverges? Practically, our method is stable. As we mention in the paper (lines 87, 188, 248 and appx C), the inner loop of EAGLE is closely related to the classical Newton-Schulz method for positive definite matrices. As such, we expect numerical stability similar to Newton-Schulz. Theoretically, this can get problematic when condition numbers start approaching 1/floating-point-precision, but empirically we expect stable behavior. This is demonstrated well in the Sparse-Suite Matrix Completion experiments (see response to reviewer rz5S), where we see very good performance.

• Do you plan to open-source your code? Yes, we plan to release our code upon publication to encourage further research in this area.

We sincerely thank the reviewer for their thoughtful feedback and their interest in our work. We appreciate the concerns raised about scalability and generalizability, and we are grateful for the opportunity to clarify these points and the central contributions of our paper. Thanks also for suggesting experiments on the SuiteSparse Matrix Collection, which we have done below. We hope this response will clearly illuminate the key aspects of our submission.

The primary discovery of our paper is that a transformer, trained simply on a matrix completion task, can implicitly learn a single, sophisticated numerical algorithm (EAGLE) and automatically adapt its execution strategy for centralized, distributed, and computation-limited hardware regimes. The emergence of this unified, resource-adaptive solver is, we believe, a surprising and powerful demonstration of in-context learning. While we show that EAGLE itself is a strong algorithm, our core focus is on the transformer's emergent ability to derive and unify it.

---

Weaknesses

1. Scalability: The experiments primarily use small, fixed-size matrices. The lack of scalability analysis raises concerns about performance and the applicability of EAGLE to large-scale, real-world problems...

We respectfully point out that our work provides both strong theoretical and empirical evidence for EAGLE's scalability.

• Theoretical Guarantees: Our main theoretical contributions, Theorems 1, 2, and 3, provide explicit convergence guarantees that hold for matrices of any size and under any distribution (i.e., result is data independent). The convergence rates depend on fundamental matrix properties like condition number ($\\kappa$) and data diversity ($\\alpha$), not on the matrix dimensions or the distribution themselves. Specifically, EAGLE's logarithmic dependence on condition number ($O(\\log \\kappa)$) makes it theoretically well-suited for large, ill-conditioned problems where first-order methods struggle.

• Existing Large-Scale Experiments: While the main text reports experiments on matrices up to $240 \\times 240$ to clearly illustrate the dynamics, we provide further scalability analysis in the appendix. Figure 19 (p. 28) explicitly tests EAGLE on problems up to size $1920 \\times 1920$, and Figure 7(h) (p. 9) demonstrates its robustness on matrices with a condition number of $\\kappa = 100,000$. These results confirm the favorable scaling predicted by our theory.

2. Synthetic Data: The reliance on synthetic data, with controlled noise and parameters, limits the generalizability of the findings.

We argue that the use of synthetic data is a methodological strength for our study's goals, and our theory ensures the findings generalize.

• Controlled Stress-Testing: Our primary goal is to understand the mechanism by which the transformer adapts its learned algorithm. Synthetic data allows us to precisely control the parameters that our theory identifies as critical performance drivers—such as condition number and data structure—enabling a rigorous validation and stress-testing of the emergent algorithm in ways that would be infeasible with uncontrolled real-world data.

• Distribution-Agnostic Theory: Crucially, our theoretical guarantees are distribution-agnostic. The convergence of EAGLE depends on the spectral properties of the data matrix, not on the underlying distribution of its entries. To demonstrate this robustness empirically, Figure 18 (p. 28) shows that EAGLE performs consistently across six different data distributions, including heavy-tailed (Student-t), correlated, and sparse factors.

• New Real-World Benchmarks: Nevertheless, we agree that evaluation on real-world data is valuable. Following your suggestion, we have benchmarked EAGLE on several matrices from the SuiteSparse Matrix Collection. The results, presented at the end of this response, confirm EAGLE's strong performance.

---

Questions

1. How does EAGLE's performance scale with increasing matrix size, different data distributions..., and what are its limitations?

   As discussed above, our paper analyzes this from two perspectives:

   • Computational Performance (Speed): Our theory and experiments show that EAGLE's iteration count scales logarithmically with the condition number ($O(\\log \\kappa)$) and polynomially with data diversity ($\\alpha^{-1}$) or sketch size ($n/r$). This is a significant advantage over first-order methods like Gradient Descent, whose complexity scales with $\\kappa$ or $\\kappa^2$. This makes EAGLE particularly effective for the high-dimensional, ill-conditioned problems often found in practice.

   • Statistical Performance (Accuracy): EAGLE is proven to converge to the optimal Nyström approximation. The suitability of this solution depends on the task; for problems with different underlying structures (e.g., entry-wise sparsity), a different learning target would be needed. Our work's novel contribution is to fix the statistical task to isolate how a transformer adapts its computational strategy to different hardware regimes —a fundamentally different axis of investigation from prior work that studies adaptation to different statistical tasks.

2. How does EAGLE compare to optimized parallel implementations... and what is its potential for parallelization?

   EAGLE is very well parallelizable,

   • High-Level Parallelism: The distributed version of EAGLE is itself a parallel algorithm designed for multi-worker systems. As detailed in Sections 3 and 5.2, it performs computation-intensive work locally on each worker and requires only lightweight communication of the partial results for the shared columns ($O((d+d')n')$ floats per round), making it naturally suited for modern parallel hardware.

   • Low-Level Parallelism: The core operations within EAGLE's update rule are matrix-matrix products. These operations are highly parallelizable and have been extensively optimized in standard libraries (e.g., BLAS/LAPACK).

   A direct performance comparison with a library like ScaLAPACK would require an equally optimized C++/CUDA implementation of EAGLE, which we believe is an exciting piece of future engineering work but is beyond the scope of this paper's focus on the transformer-based discovery of the algorithm.

3. Is there any chance to evaluate EAGLE on... the SuiteSparse Matrix Collection?

   Yes, this is an excellent suggestion. We have run these experiments.

---

Experiments on SparseSuite Matrix Collection (SSMC)

We benchmark EAGLE against several baselines on matrices from the SSMC. These were chosen from diverse domains, and chosen to be big and sparse, to handle both the concerns raised in the review. Their condition numbers also vary a lot. In line with the paper's setting, we take these low rank matrices, and generate a matrix completion task in the $A,B,C,D$ format from the paper. We then hide $D$ and run each solver.

For iterative methods, we say an iterative method converges when the update norm satisfies $\|D_{t+1}-D_t\|\le10^{-6}$ within a maximum wall-clock time of 20 min. We implement EAGLE, CG, GD, QR/SVD, and also stochastic EAGLE ($r = n/5$) and SGD for small batch experiments. Implementation details for each baseline are in Section E.1 (p. 26).

Relative Convergence Times Because convergence times and errors vary greatly across tasks, we report all results relative to NumPy’s native np.linalg.lstsq implementation (which internally uses SVD/QR). So the SVD/QR time is set to $1$ in each row. Each solver is run three times with different random seeds, and we report the median runtime. We write DNC for "did not converge." In these cases, errors were all large. Otherwise, errors all fell below 1 and below $10^{-4}$ for EAGLE, stochastic EAGLE and SVD/QR methods.

Summary of New Results:

• EAGLE is robustly accurate and efficient on these SuiteSparse matrix tasks.
  • Further, it converges even on problems where CG/GD fail to converge.
• For large ill-conditioned systems, EAGLE's iterative approach is compelling, and gets both speed and accuracy, validating its practical potential.
• Stochastic EAGLE improves upon SGD in large ill-conditioned problems. It is also more robust.

We will add the above experiments to the paper.

We sincerely thank the reviewer for their exceptionally positive and insightful feedback. We are thrilled that they found our work to be insightful, original, and of high potential impact, and we appreciate their careful reading of our paper.

To answer your excellent question regarding the number of transformer layers: you are precisely correct.

The transformer was indeed trained with a small number of layers (typically L=4), as shown in the layer-wise performance plots like Figure 2. This corresponds to the model performing only 4 "in-context" iterations of the learned algorithm.

Your observation that the distilled algorithm, EAGLE, can then be unrolled and iterated for hundreds of iterations at inference time—far beyond what the transformer observed during training—is a key result that highlights the true generalization power of the discovered algorithm.

Thank you for pointing out that this is an impressive aspect of our work. Following your suggestion, we will be sure to emphasize this point more clearly in the final version of the paper. We are very grateful for your careful review and encouraging assessment.