Choosing Which Instances to Label for Algorithm Selection by Transfer Regret

Algorithm selection means picking, for each new problem instance, the solver most likely to handle it fastest from a fixed set of candidate solvers, called a portfolio. It works well for SAT, constraint and answer-set problems, but it is expensive to train. Every training instance has to be run on every solver, often up to a timeout, before a selector can learn anything. This proposal asks a narrower question than "how should we select?": which few instances should we pay to run, so that a selector trained on them performs nearly as well as one trained on all of them?

We borrow the answer from case-based reasoning, the AI tradition of solving new problems by retrieving and adapting old solutions. That field learned the hard way that two problems that look alike can be expensive to adapt between. Its fix was to measure similarity by adaptation cost, and to build compact case libraries that cover the problem space under that measure. Our analogue of adaptation cost is transfer regret: how much slower an instance gets solved if we reuse the solver that was best for some other instance. We propose to learn this regret, define each labeled instance's "neighborhood" as the instances its best solver serves well, and choose instances to label greedily so that these neighborhoods cover the unlabeled pool. The claim is that, at the same labeling CPU budget, covering under regret-based neighborhoods closes more of the gap to the full-data selector than covering under feature-space distance, random subsampling, or uncertainty-based active learning.

Core Claim and Where It Comes From

Two results from case-based reasoning motivate the claim. Case-Based Similarity Assessment: Estimating Adaptability from Experience introduces RCR, which estimates adaptation cost by retrieving stored records of past adaptations and scaling their recorded effort. In the DIAL disaster-planning system it cut average adaptation effort from 65 to 36 primitive memory operations compared with surface semantic similarity. This is evidence that surface similarity misjudges what transfers. Earlier, CHEF: A Model of Case-Based Planning documented the same failure: cases that matched on most features broke during adaptation because of hidden goal interactions.

A Case‐Addition Policy for Case‐Base Maintenance supplies the method we reuse. It defines a case's coverage as the set of problems solvable from it within an adaptation-effort bound. It then builds libraries by greedily adding the case with the largest marginal coverage, which carries the standard guarantee of at least 63% of optimal coverage for a given library size. On Towers of Hanoi it reached full competence with 58 cases, where 200 random cases did not.

The algorithm-selection side supplies the problem and the constraint. SATzilla: Portfolio-based Algorithm Selection for SAT and ASlib: A Benchmark Library for Algorithm Selection both describe training data that requires running dozens of solvers over thousands of instances. AutoFolio: An Automatically Configured Algorithm Selector reports about 2 CPU days per scenario just to configure the selector, on top of that data. None of the selection work in the file asks how to reduce the labeling bill. The CBR maintenance work, for its part, has never been applied to choosing which instances to label for a learned selector.

Our proposal does not change how selection is done at test time. The final selector is a standard random-forest runtime regressor. What changes is which rows of the runtime matrix it is trained on.

Research Program

We define transfer regret for an ordered pair of instances. Let $s^*(i)$ be the best solver on instance $i$, and let $t_k(j)$ be the penalized runtime (PAR10) of solver $k$ on instance $j$. Then

$$ r(i \to j) = \log t_{s^*(i)}(j) - \log t_{s^*(j)}(j), $$

the log-slowdown on $j$ from reusing $i$'s best solver. This quantity is zero when the choice transfers perfectly. It is asymmetric, which matches the CBR notion that adapting A to B differs from adapting B to A.

The functional neighborhood of $i$ is the set of pool instances $j$ with $r(i \to j) \le \epsilon$, for a tolerance $\epsilon$ such as $\log 1.5$. Because the true regret needs labels on both ends, we learn a predictor $\hat r$ from features of the pair. We use gradient-boosted trees on the concatenated feature vectors and their difference, trained on all ordered pairs among the instances labeled so far.

This predictor plays the role of RCR's library of past adaptations. Each labeled pair is a record of how well one instance's solution transferred to another. The predictor generalizes those records to unlabeled pairs, and it does not need a surface-similarity pre-filter, which removes the bottleneck RCR acknowledges.

Labeling then proceeds in rounds:

  1. Label a small random seed set.
  2. Fit $\hat r$ on all ordered pairs among the labeled instances.
  3. Greedily add the unlabeled instances that maximize marginal predicted coverage of the pool, using the case-addition rule.
  4. Pay to run the portfolio on the chosen instances, refit $\hat r$, and repeat.

Because hard instances cost far more to label, many solvers hitting the timeout, we also study a cost-weighted variant. It ranks candidates by coverage gain per predicted labeling cost, using a cheap runtime predictor.

We will be explicit about what the guarantee does and does not mean. The 63% bound holds for coverage under predicted neighborhoods. Whether predicted coverage tracks realized selector quality is an empirical question, and measuring that link is part of the program.

Baselines

The naive reference is the single best solver (SBS): the one solver with the best average on training data, used for every instance. The ceiling is the virtual best solver (VBS), an oracle that always picks the fastest solver per instance. Results are reported as the fraction of the SBS-to-VBS PAR10 gap that is closed.

The full-data selector is a random-forest regressor trained on the entire training split. It is the upper reference rather than a competitor. ASlib reports that random regression forests were best on 13 of 17 ASlib 2.0 scenarios, and AutoFolio reports speedups of 1.3x to 15.4x over the single best algorithm across the 13 ASlib 1.0 scenarios. The question is how much of that performance survives at 5%, 10% and 20% of the labeling budget. On selectors trained under a labeling budget, there is no reported result found on Lacuna, so the budgeted comparisons below are new measurements.

The random-subset baseline labels a uniformly random subset of the same CPU cost and trains the same forest. It is the strongest naive competitor, because random forests are robust and random samples are representative.

The feature-space coverage baseline chooses instances by greedy k-center on standardized static features. It is the direct analogue of surface-similarity retrieval in CBR, and it doubles as the key ablation. It keeps the greedy coverage machinery and swaps only the notion of distance. If regret neighborhoods do not beat it, the adaptation-cost idea contributes nothing here.

The uncertainty-sampling baseline labels the instances where the forest's per-solver runtime predictions disagree most across trees. It is standard active learning and the most serious methodological competitor.

Every method receives the same seed set, the same CPU labeling budget (computed exactly from ASlib's stored runtimes), the same feature set, and the same downstream forest with fixed hyperparameters, so differences come only from which rows were labeled. A method "beats" a baseline if it closes more of the SBS–VBS gap at equal budget. The test is a paired comparison over ASlib's cross-validation folds and over 10 seed draws, with a Wilcoxon signed-rank test across scenarios.

Why not just…?

Why not just label a random subset? This is the real threat. If the runtime matrix is low-rank and instances are well mixed, random sampling may already be near-optimal, and the Towers of Hanoi contrast in the case-addition paper comes from a domain with far sharper structure than ASlib. The budget-curve experiment settles it directly. We expect gains mainly in scenarios with rare but important instance families, where random sampling under-represents the instances on which the VBS beats the SBS. If no such advantage appears, we will report that as a finding about ASlib.

Why not just cover the feature space with k-center or clustering? The RCR result (65 versus 36 operations) and the CHEF failures say that surface proximity misjudges what transfers. The ASlib pruning result points the same way: on SAT12-RAND, forward selection kept only 3 of 113 features with minimal impact on PAR10. That suggests most feature-space distance is noise with respect to solver choice. Covering in raw feature space spends labels separating instances that the same solver handles equally well. The k-center ablation tests this exactly.

Why not just use uncertainty-based active learning? Uncertainty sampling targets instances where the model is unsure of runtimes. Many of those are hard instances on which all solvers time out, so they are expensive to label and irrelevant to the choice of solver. Regret coverage asks a different question: whether the decision transfers, not whether the runtime is predictable. We will report the fraction of each method's budget spent on instances where every solver times out, as a diagnostic of this failure mode.

Why not just shrink the portfolio instead of the instance set? ASlib shows that forward selection cut SAT12-RAND from 31 solvers to 2 with little PAR10 loss. That reduces labeling cost along the other axis. The two approaches are complementary rather than competing, but if solver pruning alone gives the same budget savings, our method adds little. We therefore include solver pruning followed by full instance labeling at matched CPU cost, and the combination of solver pruning with regret coverage.

Proposed Experiments

The main experiment runs on all 17 ASlib 2.0 scenarios (ASlib: A Benchmark Library for Algorithm Selection). The stored runtime matrices make every labeling decision exactly replayable without running solvers. We plot SBS–VBS gap closed against labeling CPU budget for each method.

A secondary experiment tests whether regret predictors transfer across related scenarios, in the spirit of the warmstarting results in Warmstarting of Model-Based Algorithm Configuration. That work transferred past performance models to cut configuration time by 4.3x on geometric average. We pretrain $\hat r$ on pairs from the SAT12 scenarios, which share SATzilla-style features, and use it to choose labels on a held-out SAT12 scenario from step zero, removing the random seed set.

Three checks are decisive:

  1. Does the core idea work? Regret coverage must beat feature-space k-center at equal budget on a majority of scenarios. Otherwise the core idea fails.
  2. Does the guarantee mean anything in practice? Predicted coverage at each round must correlate with realized gap closure across rounds and scenarios. Otherwise the 63% guarantee is vacuous here.
  3. Where does it help? Gains over random sampling should concentrate in scenarios where few instances account for most of the SBS–VBS gap. We predict this from the structure of the method and will test it with a per-scenario regression of gain on the concentration of that gap.