Balancing Feature Extraction Overhead in Adaptive Systems

69 concepts58 papers1 proposal

Standard machine learning models assume that features are freely available at inference time. However, in real-world adaptive systems—such as automated algorithm selection, dynamic video scheduling, or meta-learning—features carry a real computational cost. To select the optimal solver or configuration for a specific problem instance, a meta-decision module must first characterize that instance by extracting its features. If this characterization phase takes too long, the time saved by making the smart choice is completely wiped out. This tension creates a fundamental bottleneck: feature extraction overhead.

The Meta-Reasoning Paradox

The problem is most pronounced in automated algorithm selection for NP-hard problems. In frameworks like SATzilla: Portfolio-based Algorithm Selection for SAT, Frank Hutter et al. demonstrated that a portfolio of specialized solvers can vastly outperform any single standalone tool. But the system's net efficiency depends on a delicate balance: the time spent on feature extraction must be strictly less than the expected reduction in execution time.

When this balance fails, meta-optimization becomes counterproductive. As Pascal Kerschke et al. note in Automated Algorithm Selection: Survey and Perspectives, selection mechanisms result in a net loss of efficiency if the overhead of characterizing an instance exceeds the performance delta between solvers. This challenge spans diverse optimization domains, from the Traveling Thief Problem (Marius Lindauer et al. in A case study of algorithm selection for the traveling thief problem) to automated K-means algorithm selection (Sheng Wang et al. in On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection).

Even in black-box optimization, Josefine Asmus points out in Towards an FCA-based Recommender System for Black-Box Optimization that if estimating the features of an unknown function requires more evaluations than simply running a general-purpose algorithm, the meta-reasoning framework collapses under its own weight.

The Deep vs. Cheap Feature Dilemma

Why not simply extract better features to guarantee perfect decisions? The dilemma lies in the relationship between a feature's predictive power and its computational complexity.

Deep structural features—such as graph embeddings for distributed processing (Nikolai Merkel et al. in Partitioner Selection with EASE to Optimize Distributed Graph Processing) or lower-bounding properties for Bayesian networks (Brandon M. Malone et al. in Predicting the Hardness of Learning Bayesian Networks)—provide rich signals for meta-models but are notoriously slow to compute. In time-constrained classical planning, Mark Roberts notes in Harnessing Algorithm Bias in Classical Planning that deep topological analysis can improve selection accuracy, but the time spent on extraction directly reduces the remaining time available for the actual search.

Even "probing features"—where a solver is briefly executed to gather empirical performance data—introduce a severe trade-off. As Frank Hutter et al. explain in Algorithm Runtime Prediction: Methods and Evaluation (Extended Abstract), if the time spent probing and running model inference exceeds the runtime savings, the utility of the performance model is entirely diminished.

Manifestations Across Computing Domains

This overhead is not confined to discrete optimization; it reappears wherever systems attempt to adapt dynamically to data:

Engineering Strategies to Mitigate Overhead

To make adaptive systems viable, researchers have developed three primary architectural patterns to manage characterization costs:

1. Strict Time Caps and Fallbacks

Modern algorithm selectors explicitly treat feature extraction as part of the total time budget (Marius Lindauer et al. in Open Algorithm Selection Challenge 2017: Setup and Scenarios). In AutoFolio: An Automatically Configured Algorithm Selector, the authors incorporate mechanisms to automatically cap the time allocated for feature extraction. If an instance is too complex and triggers a timeout during this phase, the system immediately aborts characterization and defaults to a robust fallback solver, preventing the most challenging instances from stalling the pipeline (Zhengyang John Lu et al. in Btor2-Select: Machine Learning Based Algorithm Selection for Hardware Model Checking).

2. Tiered and Multi-Pass Extraction

Instead of extracting all features upfront, systems can compute them lazily or hierarchically. Wei Fan et al. demonstrated this in A Multiple Model Cost-Sensitive Approach for Intrusion Detection by using a hierarchy of models. The system processes cheap packet headers first and only escalates to resource-intensive connection-window features when an anomaly is suspected.

Similarly, in natural language processing, Alexander M Rush et al. use a fast, linear-time pruning pass in Vine Pruning for Efficient Multi-Pass Dependency Parsing to narrow the search space before computing expensive higher-order features, ensuring that feature computation costs do not become the dominant bottleneck.

3. Cost-Aware Feature Selection

When warm-starting optimization tasks, the meta-features used to measure dataset similarity must be cheap. Matthias Feurer in Using Meta-Learning to Initialize Bayesian Optimization of Hyperparameters and Rafael Gomes Mantovani et al. in A meta-learning recommender system for hyperparameter tuning: predicting when tuning improves SVM classifiers emphasize that identifying a minimal, high-impact set of meta-features is essential. By optimizing for the ratio of predictive power to extraction cost rather than maximizing information gain blindly, these systems ensure that task characterization does not eclipse the time saved during the optimization search phase.

Key Foundational Work

An Information-Theoretic Empirical Analysis of Dependency-Based Feature Types for Word Prediction Models (1999) — contributed 1 concept elements to this direction.
A Multiple Model Cost-Sensitive Approach for Intrusion Detection (2000) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_feature_extraction_overhead_fc075731,
  title = {feature extraction overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/feature-extraction-overhead/rdr_fc0757315f044f02ba1ea7b3a9be4abb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_feature_extraction_overhead_fc075731_v1,
  title = {feature extraction overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/feature-extraction-overhead/rdr_fc0757315f044f02ba1ea7b3a9be4abb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake