Algorithm Selection with Zero Domain Knowledge via Text Embeddings

Abstract

We propose ZeroFolio, a feature-free approach to algorithm selection that uses pretrained text embeddings instead of hand-crafted instance features. It reads the raw instance file as plain text, embeds it with a pretrained embedding model, and selects an algorithm via weighted k-nearest neighbors. Our approach is based on the observation that pretrained embeddings can distinguish problem instances without any domain knowledge or task-specific training. ZeroFolio applies to any problem domain with text-based instance formats. We evaluate our approach on 11 ASlib scenarios spanning 7 domains (SAT, MaxSAT, QBF, ASP, CSP, MIP, and graph problems). ZeroFolio outperforms a random forest trained on hand-crafted features in 9 of 11 scenarios, often substantially, and in 8 of them with every serialization seed. It wins 8 of 11 scenarios against a per-scenario-tuned random forest. On the three scenarios with published AutoFolio results from the 2015 ICON Challenge, ZeroFolio comes within a small margin of AutoFolio without any per-scenario tuning. Our ablation study on SAT12-ALL shows that inverse-distance weighting and line shuffling improve performance. We further analyze the sensitivity of our approach to the serialization seed. On the SAT12-ALL scenario, where the random forest is stronger, both methods can be combined via soft voting to achieve further improvements.