acceptodds
Under review as a conference paper at ICLR 2027

Discovering Practical Algorithms for Least Squares using Language Models

Abstract

Least squares is a central problem in scientific computing with applications across many domains such as the natural and social sciences. The design and implementation of state-of-the-art algorithms for solving least squares are often based on worst-case theoretical analysis and tailored to provide numerically stable solutions. These principles are often too conservative in real-world settings, incurring severe runtime slowdowns. Manually designing per-use-case algorithm implementations, on the other hand, requires domain knowledge and tedious trial-and-error. In this work, we leverage recent progress in large language model-guided automated discovery to automate the design of practical algorithms for numerical linear algebra applications. More specifically, our methodology frames the search for practical least squares algorithms as a meta-discovery problem: given a family of downstream solver tasks, we combine language model-guided algorithm evolution with robust meta-evaluation accounting for runtime and solver accuracy. We demonstrate the effectiveness and flexibility of our framework by discovering faster practical algorithms across an extensive list of synthetic and real-world least squares tasks. The discovered algorithms are faster than optimized baselines on large kernel regression tasks from the SUSY dataset for high-energy particle physics classification with up to one million rows. Additionally, we analyze the algorithms discovered by our framework and decompose the runtime improvements across algorithmic changes, hyperparameter optimization, and code engineering.

Primary area:
optimization
Keywords:
Numerical Linear Algebra, Least Squares, LLMs, Scientific Discovery

Reviews

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

Please concisely summarize the paper, contributions, and validation as you understand them to be. The paper shows a LLM guided evoultion to automatically tune dense least-squares solvers to a fixed workload. They find that the evolved solvers faster than the best baseline, by recombing and retuning known techniques that plain hyperparameter search largely recovers.

Critical strengths

The paper's main strength is as a methodology template for LLM runtime optimization under an accuracy constraint.

Critical weaknesses
  1. The baselines are from authors' own Python with conservative stopping rules that over-solve about 100x.
  2. Genuine novelty is limited; the gains come from re-selecting and retuning known components
  3. Lack of proper statistics like the standard error of mean
Questions for authors

N/A

1 comment
AuthorsOpenReview ↗

Kind reminder: updated manuscript addressing the Reviews

Dear reviewer 9Fb6,

We again thank you for your time and feedback. Given that the ICLR discussion period will come to an end on November 18th, we kindly want to ask whether you could assess our rebuttal?

Furthermore, we want to again highlight the extensive revision of the paper and the accompanying additional experiments we did to address your review comments. We hope that these additions have addressed your concerns with respect to our paper.

Please let us know if any further questions may have come up, we would be happy to answer them.

Have a good week, The authors.

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

The paper proposes using LLM-guided evolutionary program search to discover least-squares solvers tailored to a specific workload, arguing for a shift from worst-case to “practical-case” algorithm design. Since production LS solvers are built for numerical stability on all inputs, they are often slow on the narrower instance distributions ones actually face.

A task is defined as sets of instances with reference solutions, a target accuracy, and a natural-language description. Result sections show the discovered program achieve faster converge or performance saturation compared with the best baseline. On SUSY kernel regression trained on 100k-row, and evaluated on three disjoint 1M-row instances with QR’s solution as the reference), the discovered algorithms are 2.00× faster at ε=10⁻⁴ and 1.52× at ε=10⁻¹². The limitations section concedes that discoveries are largely recombinations of expert-known techniques and lack provable guarantees.

Critical strengths

The paper provides a very clear derivation for practical LS algorithms, this is a very interesting point to read and understand the problem to have such design space with language model-guided algorithm and meta-evaluation evolution. The scoring function is designed with tailored aim, and it is the part of this paper I would expect to outlive the specific application. Wall-clock runtime is a bad optimization target like contention, thermal state, cache. In the LLM-search papers, often one either ignore this or report raw timings and hope. Most of the objective is built against the failure mode with reasonable motivation.

The analysis on the paper is interpretable for a “discovery” paper, which makes the modest claims trustworthy. It gives the evaluation metrics in few direction to provide good evidence to support the argument made from the paper, either from designed score and test accuracy. The comparison against hyperparameter optimization concedes that TPE refinement on top of the discovered program yields around 10-20% improvement.

Critical weaknesses

Accuracy is measured only as the relative residual ratio, never as forward or backward error, the study chose SUSY dataset in the high-energy physics regime, whereas there should have much more concerns about other aspects for this task. The final performance for data analysis or kernel regression would be potentially biased if solely rely on the accuracy metric. The paper does acknowledge that discovered algorithms “lack provable guarantees beyond their success on task instances, so they should be carefully inspected”. But inspection is not a substitute for measurement, and no empirical substitute is offered.

Throughout the paper, there is several place where the evolution-vs-TPE comparisons all appear to be single runs per configuration of a stochastic search procedure, with the chosen default setting selected on the training score that Appendix C itself reports “ranks differently” from validation and k=1 is precisely the regime that uses no validation set. The instance distribution is benign in exactly the dimension that would break the discovered algorithms, and the synthetic train/test split cannot detect it.

Questions for authors

Clarifications that could materially change my assessment:

  1. Can you report relative forward error ‖x̂−x‖/‖x‖ (and ideally a backward-error measure) for every discovered program and baseline in Tables 1 and Figures 2, 3, and 5?

  2. What are the condition number and leverage/coherence profile of the SUSY kernel feature matrices?

  3. Were the search-strategy comparisons (evolution vs best-of-N, the k-restart sweep, evolution vs TPE) run more than once per configuration?

  4. Is that possible to find more metrics to see the improvement from other angles, instead of only relying on few metrics listed here. Can you add a Δ-decomposition for the SUSY tasks?

  5. Can you give a break-even analysis? With ~3 h and ~$10 of discovery plus 2RK solves per candidate across 200 generations, how many downstream solves are needed before the discovered program pays for its discovery, per task?

1 comment
AuthorsOpenReview ↗

Kind reminder: updated manuscript addressing the Reviews

Dear reviewer cnxF,

We again thank you for your time and feedback. Given that the ICLR discussion period will come to an end on November 18th, we kindly want to ask whether you could assess our rebuttal?

Furthermore, we want to again highlight the extensive revision of the paper and the accompanying additional experiments we did to address your review comments. We hope that these additions have addressed your concerns with respect to our paper.

Please let us know if any further questions may have come up, we would be happy to answer them.

Have a good week, The authors.

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

The paper addresses the problem of designing fast, task-specific least-squares solvers, since standard algorithms can be unnecessarily conservative and computationally expensive. It proposes an LLM-guided evolutionary framework that automatically optimizes solver implementations, including sketching, preconditioning, and stopping criteria, while satisfying accuracy constraints. Experiments on synthetic least-squares problems and real-world kernel regression tasks from the SUSY dataset demonstrate runtime improvements of up to 2× over optimized baselines.

Critical strengths

The paper addresses an important problem, as developing efficient algorithms for numerical linear algebra is fundamental to many scientific and machine learning applications. I particularly appreciate the use of LLM-guided algorithmic discovery to automate a process that traditionally requires substantial expert knowledge and manual tuning. I believe this is a promising research direction from which the broader machine learning and scientific computing communities could significantly benefit.

Critical weaknesses

I find the paper interesting and the empirical results promising. However, I would appreciate comparisons with additional state-of-the-art least-squares solvers and existing autotuning methods to better assess the significance of the reported speedups. Such comparisons would strengthen the experimental evaluation and increase my confidence in the paper's contributions.

Questions for authors

Could the authors compare their approach with additional black-box optimization methods, including neural network-based surrogate optimization and other learning-based algorithm configuration techniques? How consistent are the discovered algorithms across independent runs of the LLM-guided evolutionary search? Is there significant variance in the final runtime improvements? How well do the discovered algorithms generalize to different matrix distributions, particularly those with different spectral properties or conditioning ? Could the authors compare against additional modern randomized least-squares solvers to better establish the performance advantages of their approach? How sensitive is the discovery process to the choice of the initial algorithm and the LLM used for evolution? Could the authors provide a more detailed analysis of the computational cost of discovery relative to the runtime savings achieved on downstream tasks?

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

The paper uses ShinkaEvolve to search for task-specific least-squares (LS) solvers under residual-accuracy constraints. It reports speedups on synthetic LS tasks and SUSY kernel regression, and analyzes changes to sketching, preconditioning, stopping criteria, and implementation. However, I have substantial concerns about novelty and the evidence supporting its performance and practicality claims.

Critical strengths
  1. Relevant practical motivation. The paper addresses a meaningful performance challenge in numerical linear algebra: general-purpose least-squares solvers can be unnecessarily conservative for workloads with known accuracy requirements. Automating task-specific solver optimization is a potentially useful direction.
  2. Empirical evidence of speedups on the evaluated workloads. The authors report measurable runtime improvements on several dense synthetic least-squares configurations and on large kernel-regression instances from the SUSY dataset. The use of held-out instances for evaluating the final discovered solvers is a positive aspect of the experimental design.
  3. Useful inspection of the discovered implementations. The paper goes beyond reporting aggregate speedups by examining changes in sketching, preconditioning, stopping criteria, and low-level implementation. This analysis provides some insight into which practical choices contribute to faster solvers, even if the underlying techniques are largely established.
Critical weaknesses

W1. Outdated baselines. The main algorithmic baselines are classical QR/Cholesky, Blendenpik, and sparse-sketch LSQR, with core methods dating back to 2013 or earlier. The paper omits recent solvers it cites [1–3] and a closely related surrogate-based LS autotuning method [4]. These comparisons are needed to establish competitiveness with current solvers and LS-specific tuning approaches. W2. Unconvincing advantage over TPE. Figure 4 shows only a modest final gain over TPE, without explicit held-out test results or variation across independent searches; Appendix C also notes that training and validation rankings can differ. Moreover, LLM evolution can change code implementations whereas TPE searches a fixed implementation. A controlled test-set comparison is needed to isolate the benefit of LLM search itself. W3. Missing end-to-end cost evaluation. The search process for each task requires substantial time, along with LLM API fees and considerable CPU computation, yet the comparison focuses on the final solver runtime. Equal evaluation counts do not mean equal search time or compute budgets. Please compare LLM evolution and conventional tuning by wall-clock/compute budget and quantify how many downstream solves are needed to amortize discovery. W4. Unclear novelty and limited LS-specific adaptation. Is the main novelty simply applying the existing ShinkaEvolve framework [5] to LS? Beyond an LS runtime/accuracy evaluator, an existing solver seed, and basic task statistics, I do not see a substantive LS-specific modification to candidate generation or the search procedure. Most discovered changes recombine established numerical techniques. The authors should clearly identify and justify the methodological contribution beyond this application. W5. Narrow data distribution and limited OOD evaluation. Synthetic tasks vary size, conditioning, and accuracy but use the same generator: exponentially decaying singular values, normalized inputs, and fixed optimal residual norm (0.01). Figure 5 primarily tests other parameter settings within this generator, not genuinely different matrix distributions; one real-world dataset is insufficient to establish broad generalization. Please test different spectra, residual scales, and data distributions. References [1] Fast and forward stable randomized algorithms for linear least-squares problems. [2] Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers. [3] Adaptive LSQR preconditioning from one small sketch. [4] Surrogate-based autotuning for randomized sketching algorithms in regression problems. [5] ShinkaEvolve: Towards open-ended and sample-efficient program evolution.

Questions for authors

Q1. How reliable are the randomized solvers? Table 1 uses only three held-out SUSY test instances, too few to characterize variability or rare failures. Could the authors add substantially more independent instances and seeds, reporting maximum/per-instance residual error, accuracy-violation rates, and runtime quantiles rather than only averages? Q2. Is the speedup partly due to less conservative stopping? At ε = 10⁻⁴ on SUSY, the discovered solver takes 20.7 s with residual error 2.4 × 10⁻⁵, whereas LSQRsparse takes 41.4 s but reaches 9.4 × 10⁻⁷. Both meet the target, but the baseline solves more accurately. Could the authors report accuracy–runtime Pareto curves or retune baseline stopping thresholds to the target accuracy? Q3. Is the discovery process reproducible? The reported 1–3% runtime variation concerns selected solvers, not independent end-to-end evolution runs. Appendix C's restart comparisons do not replace repeated runs of the same configuration. Could the authors report the distribution of final held-out speedups across independent searches (mean, variance, and success rate)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.