Algorithm Selection with Zero Domain Knowledge via Text Embeddings

arXiv:2604.19753 · cs.AI, cs.CL, cs.LG · Submitted 2026-03-20 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Algorithm Selection with Zero Domain Knowledge via Text Embeddings".

Jane: ZeroFolio proposes a feature-free approach to algorithm selection by utilizing pretrained text embeddings instead of hand-crafted instance features,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: Welcome back to the show, everyone! Today we have a paper that is really interesting because it tackles algorithm selection in a way we haven't seen before. We're talking about "Algorithm Selection with Zero Domain Knowledge via Text Embeddings." Jane, you ready to break this down for us?

Jane: I am absolutely ready, Tom; it sounds like they're proposing a method that bypasses the need for any domain-specific knowledge when choosing an algorithm. The core idea seems to be using text embeddings instead of those traditional instance features that people usually have to manually design themselves.

Lu: It’s fascinating because it suggests that representations learned from general text can capture the underlying structure of completely different problem types, which is a huge concept for AI research. I'm curious how they manage that generalization without any task-specific training or feature engineering.

Meng: From an engineering standpoint, my main question is about the practical application; if this works across diverse domains, does it mean we can just plug in any new problem format and get a decent selection result immediately? I need to know how robust this pipeline actually is in the real world.

Lalam: If we look at this from a cultural perspective, Lalam sees this as an evolution in how AI systems learn to make decisions; it suggests that complex reasoning doesn't always require specific domain training if the input structure is rich enough. It opens up possibilities for truly versatile problem-solving tools across many industries.

Tom: Exactly, and that's what the paper claims: pretrained embeddings can distinguish problem instances without any domain knowledge or task-specific training <ref:2604.19753#pg0>. So, essentially, the thesis is that you can use a fixed three-step pipeline—read text, embed it, and select an algorithm using weighted k-nearest neighbors—and that this works across SAT, MaxSAT, QBF, ASP, CSP-M models <ref:2604.19753#pg1>, and even graph problems.

Jane: That's a powerful claim because it addresses the common limitation where features designed for one domain simply don't work well in another domain <ref:2604.19753#pg1>. They suggest that relying on hand-crafted features means accepting weaker selection performance if you switch domains, which this approach tries to avoid entirely.

Paper summary: Lu: The way they handle the input, treating the raw file as plain text without parsing or feature extraction is a clever move for generalization <ref:2604.19753#pg1>. And their technique of line shuffling before truncation to manage token limits seems critical for ensuring different parts of the instance are seen by the embedding model <ref:2604.19753#pg0>.

Meng: I'm thinking about that line shuffling; from an engineering perspective, ensuring the model gets a good overview of a complex file structure without processing it as structured data is a neat trick to keep things simple for deployment. But what about the embedding model itself? They rely on something like Gemini-embedding-two which brings up concerns about reliance on specific proprietary models <ref:2604.19753#pg2>.

Lalam: I think that reliance is a point we should discuss; if we can move toward selection methods that are less dependent on a single large model's specific architecture, the cultural impact could be far more widespread and less centralized. It speaks to democratizing complex problem-solving capabilities.

Tom: Right, so the paper moves from just saying embeddings *might* work to showing that with the right choices—specifically inverse-distance weighting and line shuffling—it actually performs well <ref:2604.19753#pg2>. The results showed ZeroFolio outperformed a random forest trained on hand-crafted features in nine of eleven scenarios <ref:2604.19753#pg0>.

Jane: It’s also worth mentioning the performance metrics they reported; for example, the inverse-distance weighting was highlighted as having "the greatest impact on the results," and switching from uniform weighting could reduce PAR10 by thirty-three percent <ref:2604.19753#pg2>. That shows that optimizing the selection mechanism itself is just as important as the embedding source.

Lu: The finding that Manhattan distance shows a "smaller but consistent advantage over cosine" distance on SAT12-ALL, showing a +three point four percent improvement <ref:2604.19753#pg2>, gives us concrete guidance on which geometric approach to use for the k-NN selection step. It’s not just theoretical; it's actionable advice for implementation.

Meng: Actionable advice is good, but let's talk about the limitations they brought up in the paper itself. They mentioned that this method relies on proprietary embedding models like Gemini or OpenAI, which brings up a real concern about vendor lock-in and costs <ref:2604.19753#pg2>. Also, they noted that training these baseline models requires labeled runtime data per scenario <ref:2604.19753#pg2>.

Paper summary: Lalam: That's a fair critique; if the power relies on external, paid services, it limits accessibility for smaller groups or those with strict privacy requirements. However, the fact that ZeroFolio still wins eight of eleven scenarios against per-scenario tuned random forests suggests that the core representation idea has significant inherent value even with those practical constraints.

Tom: It’s clear the paper is demonstrating that these text representations capture instance structure relevant for solver choice, which they argue goes beyond just surface n-gram frequencies <ref:2604.19753#pg2>. So, the main implication here is that we might be able to adopt a much simpler, more general framework for algorithm selection in many AI tasks without needing deep domain expertise upfront.

Jane: If this holds up across those eleven ASlib scenarios spanning seven domains <ref:2604.19753#pg0>, it means we can potentially skip the arduous process of feature engineering for many new problems, just by getting their text format and running it through a standard embedding pipeline.

Lu: The implication is that the complexity shifts from domain specialists spending time on feature design to researchers focusing on optimizing the embedding choice and the selection metric itself <ref:2604.19753#pg1>. This opens up a whole new space for applying large-scale language models to solve computationally hard problems across disparate fields.

Meng: So, for practical implementation, it seems we need to prioritize finding robust open-source embedding alternatives if we want widespread adoption beyond the proprietary ones they tested <ref:2604.19753#pg2>. The engineering challenge will be scaling this pipeline efficiently for massive problem instances.

Lalam: I see a future where AI systems don't just solve problems based on explicit rules but learn to navigate the *structure* of problems themselves through rich textual representations, which is a significant step toward more intuitive and adaptable intelligence.

Tom: That's what we were talking about—the shift from brittle, domain-specific feature sets to flexible, structure-aware representations derived directly from the input text. We’ll keep digging into how they optimized those weighting schemes next.

Conclusion: Tom: So, to wrap up this discussion on "Algorithm Selection with Zero Domain Knowledge via Text Embeddings," we've seen how this approach uses text embeddings instead of manual feature design to choose the best algorithm for a problem. Jane, what do you think about that title and who wrote it?

Jane: I think the title is very descriptive because it immediately tells us that they aren't using any specific knowledge about the problem domain to make their choice. The authors clearly want to highlight this zero-domain-knowledge aspect of their method.

Lu: It's a really interesting framing, Jane, because it suggests that we might be able to generalize algorithm selection across many different fields simply by treating the problem description as raw text. I think the authors are positioning this as a way to make AI solvers much more versatile than they currently are.

Meng: From my side, I'm focused on the practical implication of that generality; if it truly works across diverse domains, it means we could potentially deploy selection pipelines with far less domain-specific tuning for new applications. But I have to wonder how robust this generalization actually holds up in real-world deployment scenarios.

Lalam: I see a vision where this capability fundamentally improves how we interact with complex systems; if an AI can navigate the structure of a problem without us having to manually define every possible feature, it democratizes high-level reasoning across all industries. It suggests that culture itself can be better served by tools that adapt so flexibly.

Tom: That's a big picture point, Lalam; the idea of adaptive reasoning is compelling. Jane, when you think about the authors' main conclusion, what do you pull from their summary?

Jane: They conclude that pretrained text embeddings can capture instance structure relevant for choosing a solver without needing domain expertise or specific training. It’s essentially saying that the inherent meaning in the raw text format is enough to guide the AI to pick the right tool.

Lu: That speaks to how much richer language models are becoming; they aren't just predicting words anymore, they're capturing relationships between concepts that might be relevant for problem-solving choices. This moves us beyond simple pattern matching into understanding problem semantics at a deeper level.

Meng: I have to circle back to the practical reality of that structure capture; if the embedding isn't perfectly capturing the critical decision points, then we still end up with a sub-optimal choice, no matter how good the embedding model is. That's where my engineering caution comes in about implementation fidelity.

Lalam: That fidelity issue is important; if the captured structure is noisy, it translates into poor choices for the AI system. But even with those limitations, I believe this work pushes us toward a more intuitive form of AI that learns to navigate complexity on its own terms.

Tom: It sounds like the core message is that we can simplify the selection process by leveraging powerful language representations instead of spending tons of time designing custom feature sets for every new problem. Jane, what's your final thought on how this affects the broader research landscape?

Jane: I think it shifts the focus from building better feature engineering pipelines to focusing on creating more effective ways to represent problems as text that are immediately useful for downstream selection tasks. It’s a valuable direction for current AI research.

Lu: And I see massive future work in exploring how different types of embeddings—not just text-based ones—might interact with this k-NN selection mechanism to find even smarter choices. The possibilities for combining these ideas are vast, and I'm eager to see what comes next.

TU Wien

cs.AI, cs.CL, cs.LG

Submitted: 2026-03-20

Updated: 2026-10-05

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 90/100

The gist: ZeroFolio proposes a feature-free approach to algorithm selection by utilizing pretrained text embeddings instead of hand-crafted instance features, demonstrating that these representations can

Key concepts

Zero Domain Knowledge Serialization: This step treats any problem file (like CNF formulas) as plain text without complex parsing or feature extraction. To help embedding models handle long files, lines are randomly shuffled before truncation, ensuring different parts of the instance are visible to the model.
Pretrained Text Embeddings: These are fixed-dimensional vectors generated by large language models (like Gemini). The core idea is that these embeddings capture the underlying structure of a problem instance in a way that allows them to distinguish between different types of problems across various domains, even without prior training on those specific tasks.
Weighted k-Nearest Neighbors: This is the algorithm selection mechanism. It finds the 'k' most similar instances (neighbors) in the embedding space and selects an algorithm based on a weighted score derived from its predicted runtime performance on those neighbors, favoring algorithms that perform well in similar problem contexts.

Terminology

Embeddings — 33× in this paper · explained in 2 episodes
Ablation — 14× in this paper · explained in 1 episode
Benchmark — 10× in this paper · explained in 2 episodes
Ablation study — 8× in this paper · explained in 1 episode
Feature Engineering — 7× in this paper · explained in 3 episodes
Core — 4× in this paper · explained in 2 episodes
Feature Extraction — 4× in this paper · explained in 2 episodes
Fine-Tuning — 3× in this paper · explained in 5 episodes
Generalization — 3× in this paper · explained in 13 episodes
Fidelity — 2× in this paper · explained in 2 episodes
Frozen model — 2× in this paper · explained in 2 episodes
Transformer — 2× in this paper · explained in 2 episodes
Ablation Studies — 1× in this paper · explained in 1 episode
Adaptation — 1× in this paper · explained in 1 episode
Adaptive Reasoning — 1× in this paper · explained in 2 episodes
Combinatorial Optimization — 1× in this paper · explained in 2 episodes
Domain Adaptation — 1× in this paper · explained in 5 episodes
Failure Modes — 1× in this paper · explained in 3 episodes
Robustness — 1× in this paper · explained in 5 episodes

Summary

ZeroFolio proposes a feature-free approach to algorithm selection by utilizing pretrained text embeddings instead of hand-crafted instance features, demonstrating that these representations can effectively distinguish problem instances across diverse domains without requiring any domain knowledge or task-specific training.

How it works

The ZeroFolio method proceeds in three distinct steps: first, it reads the raw instance file as plain text; second, it embeds this text using a pretrained embedding model; and third, it selects an algorithm via weighted k-nearest neighbors. The core premise is that pretrained embeddings can distinguish problem instances without any domain knowledge or task-specific training, allowing the same pipeline to be applied across various problem domains with text-based instance formats.

Zero Domain Knowledge Serialization

The first step involves treating the raw instance file as plain text without parsing, preprocessing, or feature extraction, which handles formats such as CNF formulas, WCNF (MaxSAT), QDIMACS (QBF), and MiniZinc models. To manage the token limit of embedding models, the file is truncated to a character budget of 10,000 characters. Crucially, to ensure different parts of the instance are seen by the model, We address this with line shuffling. We randomly permute the lines of the file before truncation, which exposes different parts of the instance to the embedding model.

Embedding and Algorithm Selection

The serialized text is passed to a pretrained embedding model, such as Gemini-embedding-2, to obtain a fixed-dimensional vector. The algorithm selection is then performed using weighted k-NN based on Manhattan distance. The score for an algorithm 'a' is calculated as:

score(a) = Xk i=1 wi · ti,a where wi = 1/δ(e, ei), with δ denoting Manhattan distance and ti,a being the PAR10 runtime of algorithm a on that neighbor. The goal is to select the algorithm with the lowest weighted score.

Key Design Choices and Results

The performance of ZeroFolio is highly dependent on specific design choices identified through ablation studies:

Inverse-distance weighting is highlighted as having the greatest impact on the results, as switching to uniform weighting can reduce PAR10 by 33%.
Line shuffling is the second most important factor, improving PAR10 by 11% compared to fixed sequential order.
Manhattan distance shows a smaller but consistent advantage over cosine distance (e.g., +3.4% on SAT12-ALL).

Experiments on 11 ASlib scenarios across 7 domains show that ZeroFolio outperforms a random forest trained on hand-crafted features in 9 of 11 scenarios, and it still wins 8 of 11 against a per-scenario-tuned random forest. Furthermore, on the three scenarios with published AutoFolio results, ZeroFolio remains competitive without any per-scenario configuration tuning. The method is robust across serialization seeds, with the mean PAR10 reported over seeds.

Model and Selector Analysis

The study compared several embedding models, finding that Gemini 2 outperformed other models and the RF baseline on 9 of 11 scenarios. The selector employs a non-parametric k-NN approach because it exploits the global geometry of the embedding space, whereas tree ensembles degrade on dense, high-dimensional representations. The paper concludes that pretrained embeddings capture instance structure relevant for solver choice, and that Surface n-gram frequencies are thus not enough to achieve superior performance compared to these representations. The method is applicable to any problem domain with text-based instance formats without requiring any domain expertise.

Limitations

The primary limitations noted are the reliance on proprietary embedding models (Gemini, OpenAI) and the associated API costs. Additionally, SAT12-ALL represents a scenario where the feature-based approach is genuinely stronger; however, ZeroFolio still maintains an advantage over both AutoFolio and a tuned random forest in this case. The approach also requires labeled runtime data per scenario for training the baseline models.

The gist

Pretrained text embeddings can effectively distinguish problem instances across diverse domains without requiring any domain knowledge or task-specific training. ZeroFolio, a feature-free framework using serialization, embedding, and weighted k-NN selection, outperforms hand-crafted feature baselines in 9 of 11 scenarios while remaining competitive with AutoFolio on three key benchmarks without per-scenario tuning.

Figure 2: The ZeroFolio pipeline:

Raw Instance -> File Serialize (with line shuffle) -> Embed (frozen model) -> k-NN Select Algorithm.

Improvements for AI systems

As a fastidious and diligent AI researcher, I have analyzed the ZeroFolio paper. The core innovation lies in replacing domain-specific feature engineering with general-purpose, pre-trained text embeddings and selecting an algorithm via k-Nearest Neighbors (k-NN).

Here are the specific improvements this method enables for AI systems:

Replacement of Domain Expertise with General Embeddings:
Generalization Across Diverse Problem Domains:
Robustness to Serialization Variations (Instance Format Flexibility):
Reduced Computational Cost for Feature Engineering:
Superior Performance in Feature-Scarce Scenarios (Feature-Free Advantage):

Here is what the improved AI system can do specifically:

The system can select the optimal solver from a massive portfolio of solvers (e.g., SAT, MIP, CSP) for an arbitrary problem instance without requiring any prior knowledge or training data specific to that problem type.
It can effectively handle entirely new or niche combinatorial optimization problems by simply providing the raw instance file as text, leveraging the structural understanding captured by large language model embeddings (like Gemini).
Unlike traditional feature-based systems that require manual feature design (e.g., clause-variable ratios for SAT), this system applies a fixed serialize, embed, select pipeline universally across formats like DIMACS CNF, MiniZinc models (.mzn), and MPS files.
It maintains high performance by utilizing the global geometric properties of the embedding space via k-NN selection, which is shown to be more effective than training complex random forests on hand-crafted features in many scenarios.
The system provides a robust baseline for algorithm selection where domain knowledge is scarce or expensive to acquire, outperforming hand-crafted feature models across 9 out of 11 tested scenarios while remaining competitive with state-of-the-art automated systems like AutoFolio without requiring complex per-scenario tuning.