Text embeddings replace domain knowledge in algorithm selection across seven problem classes

A research team led by Stefan Szeider has proposed ZeroFolio, a domain-agnostic approach to algorithm selection that eliminates the need for hand-engineered features. Rather than extracting problem-specific characteristics, the method treats raw instance files as plain text, encodes them with pretrained embeddings, and applies weighted k-nearest neighbors for solver selection.

The core innovation rests on an empirical observation: pretrained language model embeddings capture structural distinctions between problem instances without explicit domain knowledge or task-specific fine-tuning. This permits the same three-step pipeline—serialize, embed, select—to work across unrelated problem classes.

The authors evaluated ZeroFolio on 11 scenarios spanning seven distinct combinatorial optimization domains: satisfiability, maximum satisfiability, quantified Boolean formulas, answer set programming, constraint satisfaction, mixed-integer programming, and graph problems. Against random forest classifiers built on conventional hand-crafted features, ZeroFolio outperformed baselines in 10 of 11 scenarios using a single fixed hyperparameter set, and in all 11 scenarios when ensemble voting with two random seeds was applied.

Ablation analysis identified three critical design decisions: inverse-distance weighting for neighbor contribution, random line shuffling during text preprocessing, and Manhattan distance as the similarity metric. On datasets where both approaches showed comparable performance, combining embeddings with traditional features through soft voting produced measurable gains.