Algorithmic algorithm development with LLMs: A Case Study on LLM-Usage for Contraction Order Optimization in Tensor Networks

Technical Summary: Algorithmic Algorithm Development with LLMs

Problem Statement
The paper investigates the application of Large Language Models (LLMs) to the core scientific task of algorithm development and improvement, specifically focusing on contraction order optimization for tensor networks. Determining an optimal contraction sequence for a tensor network (TN) is an NP-hard problem where the goal is to minimize the number of floating-point operations (FLOPs) and intermediate memory requirements. While heuristics and meta-heuristics (e.g., greedy algorithms, simulated annealing) exist, the authors explore whether LLM-based evolutionary agents can discover superior algorithms without end-to-end automation of the research cycle. The study uses OpenEvolve, an open-source evolutionary coding agent, to evolve Python code that determines contraction orders.

Methodology
The authors employ a controlled experimental framework using OpenEvolve, which combines LLM-generated code mutations with island-based evolutionary search and a MAP-Elites-style quality-diversity archive. The setup involves:

• Initial State: A "very stupid" greedy baseline algorithm that contracts indices in descending order of size.
• Evaluation: An automated evaluator calculates the FLOP count for a given contraction order on a set of tensor networks (generated as scalar products of periodic Matrix Product States). The evaluation relies on theoretical FLOP counts rather than actual execution to ensure stability and reproducibility.
• Metrics: The primary optimization target is the log10 speedup relative to a "cotengra cheap" baseline (a standard heuristic). Secondary metrics include median, max, min speedup, and total FLOP reduction.
• Experimental Variables: The study systematically varies:
  1. LLM Choice: Testing various open-weight models (e.g., GPT-OSS-20B/120B, Qwen3.5, MiniMax, Gemma-4) with different reasoning efforts.
  2. Reproducibility: Running 20 independent trials with different random seeds to assess stochasticity.
  3. Optimization Metrics: Changing the objective function (e.g., optimizing for average vs. minimum speedup).
  4. Test Data: Training on different subsets of tensor networks ("small," "middle," "large") to observe generalization.

Key Results

• Model Sensitivity: The choice of LLM significantly impacts results. GPT-OSS-20B with "high" reasoning effort was the only model to consistently outperform the baseline on "small" tensor networks (achieving an average log10 speedup of +0.06, a ~1.15x reduction in FLOPs) and showed significant improvement on "middle" networks (+1.67, ~47x reduction). Larger models (e.g., GPT-OSS-120B) and other open models often failed to improve or performed worse than the baseline.
• Stochasticity: Evolution runs are highly stochastic. While individual runs vary widely, ensembles of runs show converging trends, particularly with higher reasoning efforts.
• Metric and Data Influence: The definition of the "combined score" and the selection of test cases are critical. Optimizing for "average" speedup performed better than optimizing for "minimum" or "total FLOP reduction." Furthermore, optimizing on "small" tensor networks yielded the best generalization across all network sizes, whereas optimizing on "middle" networks performed worst.
• Algorithmic Discovery: The "best" evolved algorithm (from GPT-OSS-20B) did not discover a fundamentally new paradigm but refined a known approach. It utilized a greedy min-fill strategy with explicit fill-in updates and local refinement (swapping adjacent positions). Notably, it introduced a non-standard surrogate weighting for prospective fill edges: penalizing by min(log dim a, log dim b) rather than the standard multiplicative (additive in log-space) measures. This heuristic yielded reasonable results despite lacking prior theoretical justification in the literature.
• Runtime Constraints: While the evolved algorithm reduced FLOPs significantly, its own runtime for determining the order was high. On "large" tensor networks, the algorithm's execution time exceeded reasonable limits, highlighting a trade-off between the quality of the contraction order and the time required to compute it.

Significance and Claims
The authors explicitly state that this work is not a "success story" claiming a breakthrough algorithmic discovery. Instead, the paper serves as a case study to analyze the factors contributing to the success or failure of LLM-based algorithm engineering.

• Human-in-the-Loop Necessity: The study emphasizes that while LLMs can generate code, the human scientist remains responsible for intentmaking (defining the problem, selecting metrics, and choosing test data) and sensemaking (interpreting, validating, and understanding the results). The design of the evaluation harness and the selection of the LLM are critical design decisions that heavily influence outcomes.
• Shift in Engineering Objects: The paper argues that in AI-assisted scientific software development, the engineering object extends beyond executable code to include "semi-executable artifacts" such as prompts, workflows, evaluation metrics, and organizational routines.
• Limitations: The authors acknowledge limitations, including the use of a single framework (OpenEvolve), reliance on internal LLM knowledge without external retrieval, and the use of open-weight models rather than frontier commercial models. They note that the rapid evolution of the field may render specific experimental setups quickly outdated.

In conclusion, the paper posits that LLM-based evolutionary agents are promising tools for scaling algorithm search, but their effective deployment requires rigorous human oversight in designing the search space and validating the resulting artifacts against domain-specific constraints.