Towards Robustness and Explainability of Automatic Algorithm Selection

Xingyu Wu, Jibin Wu, Yu Zhou, Liang Feng, Kc TanICML 2025 · OpenReview

Introduction

Researchers have developed DAG-AS, a novel framework for automatic algorithm selection that moves beyond simple correlations to embrace causal modeling. By utilizing Directed Acyclic Graphs (DAGs) to understand why a specific algorithm fits a particular problem, the system achieves state-of-the-art performance, remains robust against data bias, and provides "counterfactual" explanations for its decisions.

The Challenge of Algorithm Selection

In the realms of optimization and machine learning, there is no "one size fits all" algorithm. Algorithm Selection (AS) is the task of predicting which algorithm will perform best on a specific problem instance before actually executing it.

Traditionally, AS models operate as "black boxes" that search for statistical patterns—or correlations—between problem features (e.g., the size or density of a graph) and algorithm performance. However, this conventional approach suffers from two major flaws:

  1. Brittleness to Distribution Shifts: If the distribution of problems changes—for instance, moving from small-scale, tightly clustered training data to high-dimensional, scattered real-world data—these correlation-based models often fail catastrophically.
  2. Lack of Transparency: Traditional models cannot explain why they chose Algorithm A over Algorithm B in a manner that human engineers can interpret and use to improve their own algorithmic designs.
Illustration of distribution shift between training and testing data, a common cause of failure for traditional algorithm selection models.

The DAG-AS Framework

To address these limitations, the authors introduce DAG-AS (DAG-based Algorithm Selection). Instead of merely mapping problem features to a performance score, DAG-AS models the underlying mechanism using a Structural Causal Model (SCM).

  • Causal Learning Network: The core of the model is a neural network constrained to learn a Directed Acyclic Graph. It learns how specific problem features (PF) causally necessitate specific algorithm features (AF).
  • Feature Reconstruction: When presented with a new problem, the model reconstructs the "ideal" algorithm features required to solve it. It then compares these ideal features against the actual features of candidate algorithms to rank them effectively.

Multi-Level Explainability

A standout feature of DAG-AS is its ability to explain its reasoning at multiple levels:

  • Model-Level: By examining the learned DAG, researchers can identify which features are most influential using metrics like betweenness centrality.
  • Instance-Level: The model supports counterfactual reasoning. It can answer hypothetical questions, such as: "If this problem's dimensionality were slightly lower, would the model have chosen a different algorithm?" This is achieved through a three-step process: Abduction (inferring hidden noise), Intervention (modifying a feature), and Prediction.
Diagram illustrating model-level and instance-level explainability, showing how interventions on problem features can lead to a change in algorithm selection.

Key Insights and Performance

The authors evaluated their approach using the ASlib (Algorithm Selection Library) benchmark, focusing on ten diverse scenarios including Bayesian Network Structure Learning (BNSL-2016), Boolean Satisfiability (SAT11/SAT18), and the Traveling Salesman Problem (TSP-LION2015).

Core Findings

  • Causality Over Correlation: The fundamental insight is that algorithm selection is inherently a causal process. A problem's structure demands certain algorithmic properties. By modeling this directionality, DAG-AS ignores spurious correlations that typically lead to errors during distribution shifts.
  • Centrality of Algorithm Features: The study revealed that algorithm features (e.g., "cyclomatic complexity") often exhibit higher centrality in the causal graph than problem features, suggesting that understanding the tool is just as critical as understanding the task.
  • Robustness to Missing Algorithms: Because the model learns the underlying mechanism of what makes an algorithm effective, it remains highly accurate even when some candidate algorithms are removed during the training phase.

Empirical Results

  • Top Performance: DAG-AS achieved the lowest PAR10 score (a standard metric for algorithm running time) in 8 out of 10 benchmark datasets, outperforming established methods like SATzilla11 and SUNNY.
  • Distribution Shift Resilience: In tests where test data significantly differed from training data, DAG-AS demonstrated markedly lower performance degradation compared to competing models.
  • Actionable Explainability: The authors successfully triggered a "selection change" in 79 specific instances by making minimal, human-interpretable interventions (less than a 10% change) to problem features, proving the viability of their counterfactual reasoning engine.

Limitations and Future Directions

While highly effective, DAG-AS does face certain limitations. The model relies heavily on having a rich set of informative features; poor feature quality will degrade the causal discovery process. Additionally, solving the "Abduction" step for counterfactual explanations requires iterative numerical methods, which can be computationally expensive for very large models. Finally, the model assumes "causal sufficiency," meaning there are no hidden variables influencing both the problem and the algorithm performance.

Future work will aim to improve the computational efficiency of these counterfactual calculations and explore how these causal insights can be leveraged to automatically design entirely new algorithms, rather than simply selecting from existing ones.

Summary updated

Abstract

Algorithm selection aims to identify the optimal performing algorithm before execution. Existing techniques typically focus on the observed correlations between algorithm performance and meta-features. However, little research has explored the underlying mechanisms of algorithm selection, specifically what characteristics an algorithm must possess to effectively tackle problems with certain feature values. This gap not only limits the explainability but also makes existing models vulnerable to data bias and distribution shift. This paper introduces directed acyclic graph (DAG) to describe this mechanism, proposing a novel modeling paradigm that aligns more closely with the fundamental logic of algorithm selection. By leveraging DAG to characterize the algorithm feature distribution conditioned on problem features, our approach enhances robustness against marginal distribution changes and allows for finer-grained predictions through the reconstruction of optimal algorithm features, with the final decision relying on differences between reconstructed and rejected algorithm features. Furthermore, we demonstrate that, the learned DAG and the proposed counterfactual calculations offer our approach with both model-level and instance-level explainability.
BibTeX
@inproceedings{wu2025towards,
  author = {Xingyu Wu and Jibin Wu and Yu Zhou and Liang Feng and KC Tan},
  title = {{Towards Robustness and Explainability of Automatic Algorithm Selection}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=Gp7NfP7Erm},
}
Figure