When Is Interpretability Free? Sample-Size Laws for Algorithm Selectors

Hard computational problems such as satisfiability (SAT), constraint satisfaction, and integer programming are solved in practice by a portfolio of solvers. No single solver wins everywhere, so a learned "algorithm selector" looks at cheap features of each instance and picks which solver to run. The selectors that win benchmarks are random forests and heavily auto-configured pipelines. Nobody can read their routing logic, and nobody can correct it when it sends an instance to a solver that times out. Practitioners usually assume that a readable selector, such as a short decision tree or a scoring rule over a handful of named instance properties, must cost speed. We think that assumption has never been tested at the sample sizes where selectors are actually trained, which range from a few hundred to a few thousand instances per scenario.

This note proposes to measure the accuracy–interpretability trade-off for algorithm selection as a function of training-set size, and to predict it from dimension-dependent generalization bounds. The core claim is that the "price of interpretability" is mostly an estimation-error effect. A flexible selector earns a real advantage only after the number of training instances passes a crossover point. That point is set by the gap in effective capacity between the two selector classes, and we expect it to follow the intrinsic dimension of the instance-feature cloud rather than the raw feature count. If this holds, a practitioner can tell before training whether a readable, correctable selector will match a black-box one on their data. If it fails, we will know the trade-off is real and structural.

Core Claim

Generalization in Portfolio-Based Algorithm Selection proves that the gap between training and test cost of a learned selector is at most of order $H\sqrt{(\bar d + \kappa \log t)/N}$. Here $H$ is the maximum runtime cost, $\bar d$ is the capacity of the selector class (its pseudo-dimension, a combinatorial count of how many patterns the class can fit), $\kappa$ is the portfolio size, $t$ counts the constant pieces in each solver's performance surface, and $N$ is the number of training instances. That paper treats $\bar d$ as an opaque constant and uses the bound to explain why large portfolios overfit. We use the same bound for a different job: comparing two selector classes on the same portfolio.

Call the readable class $\mathcal{F}_I$ and the black-box class $\mathcal{F}_B$. Let $A$ be the best-case test-cost advantage of $\mathcal{F}_B$ over $\mathcal{F}_I$ given infinite data, which is the approximation gap. Let $D_B$ and $D_I$ be their effective capacities. The expected price of interpretability at sample size $N$ then behaves roughly like

$$P(N) \approx A - cH\left(\sqrt{D_B/N} - \sqrt{D_I/N}\right),$$

where $c$ is a constant we calibrate across scenarios. Setting $P(N)=0$ gives a crossover sample size $N^* \approx c^2 H^2(\sqrt{D_B}-\sqrt{D_I})^2/A^2$. Below $N^*$ the readable selector should match or beat the black box.

The claim has two testable halves. First, $P(N)$ shrinks toward zero or goes negative at small $N$ in a way this functional form fits. Second, the crossover follows an intrinsic-dimension estimate of $D_B$ better than the ambient feature count, which is 113 features in SAT12-RAND. The second half is the dimension-dependent part. It mirrors the move in Provable Robust Overfitting Mitigation in Wasserstein Distributionally Robust Optimization, which replaces ambient dimension with the data's intrinsic dimension in a generalization certificate. We reuse that idea as a predictor; we do not reuse its method.

The motivating evidence comes from ASlib: A Benchmark Library for Algorithm Selection. That benchmark found random regression forests best on 13 of 17 scenarios. It also found that in SAT12-RAND, features could be pruned from 113 to 3 and solvers from 31 to 2 "with minimal impact" on penalized runtime. Both facts were observed at full data size, and neither was explained. Our claim says both are the same phenomenon seen at one point on the $P(N)$ curve.

Research Program

The readable selector class is a concept-bottleneck selector in the sense of Concept Bottleneck Models. That paper factors prediction into a map from input to a few human-named concepts, followed by a transparent predictor on those concepts. It also shows that humans can fix wrong concept values at test time and so correct the output. In our setting the input is ASlib's precomputed instance features. The concepts are $k$ named structural quantities, such as clause-to-variable ratio, constraint-graph density, and solver probing statistics. Some are taken directly from the features. Others are small named aggregates of feature groups that ASlib already defines.

On top of the concepts sits a pairwise cost-sensitive linear scorer or a depth-limited tree. A user can therefore read why solver $s_i$ was preferred to $s_j$, and can overwrite a concept value, for example when a feature computation timed out, and watch the decision change. We deliberately avoid deep concept extractors. On tabular selector features, extra extraction capacity would reintroduce the hidden information channels that weaken concept bottlenecks.

The black-box classes are ASlib-style random regression forests, the full AutoFolio pipeline, and a multilayer perceptron selector trained by gradient descent. The perceptron is included because The Dimension Strikes Back with Gradients shows that gradient descent can need on the order of $\sqrt{d}$ samples to avoid memorizing its training set. That lower bound comes from a worst-case convex construction. Whether it predicts anything on natural selector data is open, and the perceptron arm tests that directly.

The analysis has three parts. First, we compute capacity estimates for each class. For the readable class these are pseudo-dimension bounds in $k$ and tree depth. For the black boxes we use effective dimension from several sources: the feature covariance spectrum, nearest-neighbour intrinsic-dimension estimators on the instance cloud, and, for forests, the number of distinct leaves actually used. Second, we fit $A$ and $c$ on half the scenarios and predict $N^*$ on the held-out half. Third, we repeat the curve while varying portfolio size $\kappa$. Following the Balcan et al. finding that test cost degrades as portfolios grow, we expect larger $\kappa$ to shift $N^*$ upward for black boxes faster than for readable selectors.

Baselines

The naive reference points are the single best solver (SBS) and the virtual best solver (VBS). The SBS is the one solver with the best average penalized runtime, run on every instance. The VBS is an oracle that always picks the instance's fastest solver. We report every selector as the fraction of the SBS-to-VBS gap it closes in PAR10, which is penalized average runtime with timeouts counted as ten times the cutoff. This normalization is standard on ASlib and makes scenarios comparable.

The strongest existing method is AutoFolio. It uses sequential model-based configuration to search over feature selection, preprocessing, schedules, and learner type. Its authors report average speedup factors of 1.3 to 15.4 over the SBS, nearly 4x faster than SATzilla'11 on SAT12-RAND, and new best results on 7 of 13 scenarios. It needs about 2 CPU days of training per scenario. We found no per-scenario PAR10 values for AutoFolio on Lacuna, so we will rerun it ourselves rather than quote figures.

For fairness, every selector, readable or black-box, sees identical training subsamples and is scored on an identical untouched outer test split. AutoFolio gets its published 2-CPU-day budget at full $N$, scaled down proportionally at smaller $N$. The readable selector gets the same wall-clock budget for choosing $k$ and depth. The random-forest regression selector from ASlib is the second strong baseline because it was the most consistent winner, and it gets nested cross-validated hyperparameters.

Beating these baselines does not mean beating AutoFolio at full data. It means one of two things. Either the readable selector closes at least as much of the gap as AutoFolio, within a paired bootstrap confidence interval, for all $N$ below a predicted $N^*$. Or the predicted $N^*$ matches the empirically observed crossover within a factor of two on held-out scenarios.

Two ablations isolate the key ingredients. The first keeps the readable architecture but feeds it $k$ random features instead of named concepts. This tests whether naming and grouping matter, or only small $k$ does. The second replaces the intrinsic-dimension capacity estimate with the raw feature count in the crossover prediction. This tests whether the dimension-dependent part of the theory carries the predictive weight.

Why not just…?

Why not just use the random forest everywhere, since ASlib says it wins? That ASlib result is aggregated at full training size, so it says nothing about the small-$N$ regime that most new scenarios start in. It is the main threat to our claim. If forests close more of the gap than readable selectors at every subsample size on most scenarios, the trade-off is structural and our crossover theory is wrong. The subsampling experiment is designed to show exactly this, and we will report it either way.

Why not just tune the number of features by nested cross-validation and skip the theory? This is a real competitor for picking $k$ on a given scenario. We expect it to roughly match any bound-based choice once enough data exists. We do not claim a better tuning rule. The contribution is a prediction made before training on a new scenario of whether a readable selector will be competitive, which cross-validation can only answer after fitting every candidate. There is a second issue at small $N$. The Limits of Post-Selection Generalization shows that reusing the same data for many adaptive choices needs sample size growing like the square root of the number of choices. That result predicts that heavily searched cross-validation scores will be optimistic. We measure that optimism directly as the gap between inner cross-validation PAR10 and outer test PAR10, for both AutoFolio and nested-CV pruning.

Why not just fit a shallow decision tree or Lasso on all features? These are readable and have known capacity, so they are included as additional readable classes rather than dismissed. ASlib's comparison suggests linear models lose to forests, but again only at full $N$. The concept-bottleneck variant differs because its inputs are named, grouped quantities a user can overwrite. The random-feature ablation shows whether that adds anything beyond sparsity. If a plain sparse tree matches it, we will report that the bottleneck structure is unnecessary for accuracy and matters only for correctability.

Why not explain the forest after the fact with attribution methods? Post-hoc attributions describe a model but give no way to change its decision. The case for intervention comes from the concept-bottleneck work, where correcting two concepts on knee X-rays cut task error from over 0.4 to about 0.3. We test the analogue here. On instances whose feature computation was capped or failed, we substitute the true concept values and measure how much PAR10 recovers. No equivalent action exists for an attributed forest.

Proposed Experiments

The main experiment runs all 17 ASlib scenarios. For each scenario we subsample the training instances to 10, 20, 40, 70, and 100 percent of the available pool, with ten random draws per fraction and a fixed outer test split. We plot the SBS-to-VBS gap closed against $N$ for the readable selector, random forest, AutoFolio, and the perceptron.

The first decisive check is the sign of $P(N)$ at the smallest fractions. Our claim predicts that the readable selector is statistically tied with or ahead of the black boxes there on a majority of scenarios. The second decisive check is out-of-scenario prediction of the crossover. With $c$ and $A$ calibrated on half the scenarios, does the intrinsic-dimension version of $N^*$ predict the other half better than the raw-feature-count version? We use rank correlation between predicted and observed crossover as the primary statistic.

The third check is a portfolio-size sweep, pruning solvers greedily from the full pool down to two, on the SAT scenarios. A secondary sweep uses the CATS integer-programming instances from Balcan et al. if their CPLEX runtimes are obtainable. We test whether $N^*$ grows with $\kappa$ faster for black boxes, as the $\kappa \log t$ term predicts.

The fourth check tests whether the perceptron's small-$N$ deficit relative to forests scales with its parameter count, as the $\sqrt{d}$ lower bound would suggest, or with the instance cloud's intrinsic dimension. This gives a natural-data probe of a worst-case result.

As an out-of-domain sanity check, we apply the same subsampling protocol to the routing-solver setting of Neural Solver Selection for Combinatorial Optimization. That work reduced the synthetic TSP optimality gap from 2.33 percent for the best single solver to 1.51 percent, and the CVRP gap from 6.82 to 4.81 percent, with a graph-encoder selector trained on 10,000 instances. If its own reported numbers can be reproduced, we ask whether a concept-bottleneck selector over named graph statistics recovers most of that improvement at 10 to 20 percent of the training data.

The outcome that would most clearly refute the proposal is a uniformly positive $P(N)$ with no fitted crossover on held-out scenarios. We would report that as evidence that the interpretability price in algorithm selection is real at every practical sample size.