Abstract
Algorithm selection traditionally treats algorithms as "black boxes," focusing primarily on problem-specific features. This paper introduces AS-LLM, a framework that leverages Large Language Models (LLMs) to represent algorithms by extracting structural and semantic insights from their source code or documentation. By combining LLM embeddings with a dual-tower matching architecture and differentiable feature selection, AS-LLM transforms algorithm selection into a bidirectional matching problem. Experimental results on the ASlib benchmark demonstrate that AS-LLM significantly outperforms traditional state-of-the-art methods across diverse computational scenarios.
Introduction: Beyond the Black Box
In automated machine learning (AutoML), the principle of "performance complementarity" dictates that no single algorithm is universally superior. Algorithm selection aims to predict the most effective solver for a given problem instance. Historically, this has been a one-sided process: models map problem features (e.g., variables in a SAT formula) to performance labels, treating the algorithms themselves as anonymous entities.
AS-LLM addresses this missed opportunity. Algorithms possess rich internal logic and structural dependencies that influence their performance. By using LLMs to translate raw code or descriptions into high-dimensional "algorithm features," the authors enable a more nuanced understanding of the relationship between problems and solvers.
The AS-LLM Framework
The AS-LLM pipeline consists of several integrated stages designed to bridge the gap between problem characteristics and algorithmic logic.
1. Algorithm Representation
For each candidate algorithm, the system processes its source code or descriptive text through a pretrained LLM (such as CodeBERT). This step captures semantic meaning and logical flow that traditional macro-statistics often miss. As shown in the framework overview, this can include abstract syntax trees, library functions, and broader background knowledge.
2. Sequential Processing and Feature Selection
Because LLM outputs are sequential, an LSTM network compresses these embeddings into a fixed-length vector. To manage the high dimensionality of these embeddings, a Gumbel-softmax module performs differentiable feature selection, identifying the most predictive attributes while filtering out noise.
3. Dual-Tower Architecture
The model employs a "dual-tower" design where problem features and algorithm features are processed through separate Multi-Layer Perceptrons (MLPs). The final selection is based on the Cosine Similarity between these two representations. This approach treats selection as a matching problem—finding the algorithm whose logical "shape" best fits the problem's requirements.
Experimental Evaluation
The framework was evaluated using the ASlib Benchmark, covering 10 diverse scenarios including Boolean Satisfiability (SAT), Constraint Programming, and Traveling Salesman Problems.
Key Results
- Performance Dominance: AS-LLM achieved the best performance in 8 out of 10 scenarios compared to classic methods like SATzilla and SUNNY.
- Significant Gains: In the
BNSL-2016scenario, AS-LLM improved the PAR10 score by nearly 31% over the nearest competitor. - Generalization: The model demonstrates the potential to generalize to unseen algorithms by "reading" their documentation, provided the input quality is sufficient.
Insights and Future Directions
The success of AS-LLM highlights that code is a rich source of discriminative features. However, the model's performance is sensitive to the quality of algorithm descriptions; it struggled in scenarios where complete source code was unavailable. Future work may involve fine-tuning LLMs specifically for domain-specific code or exploring more advanced feature selection techniques to further refine the matching process.
Summary updated