Source-linked AI summary
Data-Driven Dynamic Algorithm Dispatch with Large Language Models
Rushil Shah, Emmanuel Lujan, Rabab Alomairy, Alan Edelman
TL;DR
Manual dispatch becomes difficult as matrix structures and solver designs diversify. The paper combines prompt engineering with performance data to generate dynamic heuristics, and an LU case study successfully rediscovers the desired strategy while revealing variability and prompt-size constraints.
Problem
Increasing matrix-structure and solver diversity makes manually engineered dispatch heuristics increasingly difficult.
Method
The approach uses prompt engineering and a SmartSolve.jl performance database to have an LLM generate dynamic algorithm dispatch heuristics.
Results
The LLM-driven approach successfully rediscovers the desired LU dispatch heuristic using Pareto-optimal choices from benchmark data.
Takeaways & Limitations
The study provides evidence that LLMs can generate dynamic algorithmic dispatch heuristics for linear algebra.
Takeaways & Limitations
The approach is limited by probabilistic output variability and prompt-size constraints, often requiring iterative refinement.
Abstract
from arXiv · showhide
We introduce a large language model (LLM)-driven approach for generating dynamic algorithmic dispatch heuristics in high-performance linear algebra. By combining prompt engineering with LLaMA 3 and a curated performance database, the model learns to synthesize selection heuristics that exploit structural patterns to identify fast algorithmic choices. A case study on LU factorization demonstrates the model's ability to replicate expert-designed strategies. This work, developed as part of the DARPA-MIT SmartSolve project, highlights the promise of LLMs for algorithmic discovery and the development of more adaptive, fast linear algebra software.
I. INTRODUCTION
The paper motivates LLM-driven dynamic dispatch by the difficulty of manually handling diverse matrix structures and presents SmartSolve’s data-driven approach, with an LU case study using LLaMA 3.
- Specialized LU variants exploit sparsity and block patterns to improve performance and reduce memory use over general-purpose approaches.
- Growing diversity in matrix structures and solver designs makes manually engineered dispatch heuristics increasingly difficult to maintain.
- SmartSolve benchmarks algorithms across matrix patterns, data formats, precision strategies, and architectures, aggregating features and performance metrics into a database.
- Pareto analysis identifies speed–precision trade-offs, and the resulting database trains a model to select algorithmic and architectural choices from input-matrix features.
- The paper contributes an LLM-driven method for generating dynamic dispatch heuristics and an LLaMA 3 LU case study that rediscovers a heuristic across MatrixMarket.jl matrices.
II. METHODS
The method uses prompt engineering and SmartSolve.jl benchmark data to make an LLM generate dispatch logic that maps matrix features to an efficient available algorithm.
- Prompt engineering instructs the LLM to generate dynamic algorithm dispatch heuristics for linear algebra.
- The prompt supplies the model with a domain role and SmartSolve.jl performance data covering alternative algorithms and input features.
- The generated heuristic maps input-matrix features to the most efficient available algorithm for integration into systems such as LinearSolve.jl.
III. RESULTS AND DISCUSSION
The LU case study uses Pareto-optimal benchmark choices to guide LLM-generated dispatch logic and successfully rediscovers the desired heuristic, while exposing variability and prompt-size constraints.
- SmartSolve benchmarks dense, sparse, and banded LU strategies on structurally diverse matrices and applies Pareto analysis to runtime–accuracy trade-offs.
- Pareto-optimal choices guide the LLM in generating LU dispatch heuristics, with the reported results obtained using double-precision computations.
- The case study uses a Julia notebook with 7B Mistral v0.3 through Ollama v0.9.4, and its code is publicly available in SmartSolve.jl.
- The approach successfully rediscovers the desired LU dispatch heuristic, providing evidence for LLM viability in generating dynamic algorithmic dispatch heuristics.
- Statistical output variability can require prompt rephrasing or multiple generation rounds, while limited prompt input space constrains use of large performance databases.