To optimize complex systems, we often rely on a simple premise: if we can predict how a process will behave before it runs, we can make smarter decisions. We build auxiliary models—ranging from lightweight static analysis to deep neural networks—to forecast transaction conflicts, estimate execution times, or select the best optimization algorithm from a portfolio.
But prediction is not free. It consumes the exact same computational resources (CPU cycles, memory, and wall-clock time) that it aims to conserve. This introduces a fundamental trade-off: prediction overhead. If the time spent predicting a system's behavior exceeds the time saved by the resulting optimization, the meta-model degrades the overall system performance rather than improving it.
The Amortization Fallacy in Dynamic Environments
In theoretical computer science, the cost of generating a prediction is frequently swept under the rug. Algorithms are often analyzed under the assumption that prediction costs are either zero or fully amortized over an infinite sequence of problem instances. However, as Antonios Antoniadis et al. demonstrate in Approximation algorithms for combinatorial optimization with predictions, this assumption completely breaks down when dealing with dynamic or rapidly changing data distributions. When a distribution shifts, the system must continuously train or update its predictive models on the fly.
This high-frequency training cost can quickly become catastrophic. For instance, in Neural Networks in Evolutionary Dynamic Constrained Optimization: Computational Cost and Benefits, Maryam Hasani-Shoreh et al. evaluate the real-world wall-clock cost of using neural networks to predict moving optima in dynamic environments. They show that the time spent training the neural network directly reduces the number of iterations available to the primary evolutionary search algorithm. If the environment changes quickly, the predictor consumes so much of the total time budget that the search algorithm is starved of execution time, leading to a net performance loss and a vicious cycle where poor search results provide low-quality training data.
The "Thinking Time" Bottleneck in Algorithm Selection
A similar bottleneck occurs in meta-algorithm control and algorithm portfolios, where a system must decide which solver to deploy based on early execution data. In Low-Knowledge Algorithm Control, Tom Carchrae et al. highlight that the initial phase used to observe and predict which algorithm will perform best can consume a disproportionate amount of a strict time budget.
When the underlying solvers execute quickly, the overhead of the prediction mechanism can completely swallow any potential optimization gains. As Jürgen Schmidhuber et al. observe in Dynamic Algorithm Portfolios, the computational cost of updating predictive models and calculating resource allocations limits the practical use of dynamic portfolios to computationally expensive solvers. If the solvers are low-latency, the meta-model's "thinking time" becomes the primary bottleneck.
This trade-off is explicitly quantified by Thomas Weise et al. in An Improved Generic Bet-and-Run Strategy with Performance Prediction for Stochastic Local Search. The authors note that if the time spent analyzing early run data to make an informed selection is too substantial, simpler strategies—such as blindly continuing the current best run without any predictive analysis—prove to be more efficient in practice.
Micro-Latency and Static Analysis Bottlenecks
This tension is not confined to machine learning models; it manifests even in deterministic, lightweight prediction methods like static analysis and statistical profiling.
Consider database transaction scheduling. Gianni Mainetto et al. explored this in Data Sharing Analysis for a Database Programming Lanaguage via Abstract Interpretation, using formal static analysis to predict transaction readsets and writesets to prevent deadlocks. They found that the computational overhead of performing this static analysis prior to execution could easily exceed the actual runtime of the transaction itself, rendering the optimization counterproductive.
A parallel issue appears in modern software engineering. In Lazy Testing of Machine-Learning Models, Anastasia Isychev et al. introduce a framework that uses static analysis to skip redundant machine learning model invocations. While highly effective for expensive models, the authors caution that the static analysis phase itself becomes a bottleneck when the target model invocations are extremely fast.
When integrated into low-latency environments like operating systems or real-time AI systems, even microseconds of prediction latency matter. Ruhi Sarikaya et al. note in Program behavior prediction using a statistical metric model that the computational cost of existing program behavior predictors often makes them prohibitive for real-time OS integration. As Franz Barachini et al. emphasize in Run-Time Prediction for Production Systems, any prediction mechanism designed for real-time systems must explicitly account for its own execution cost within the system's strict timing constraints, lest it violate the very real-time guarantees it is trying to provide.
Designing Budget-Aware Predictors
To successfully navigate this trade-off, system designers cannot treat performance predictors as isolated, cost-free components. Instead, the choice of a predictor must be tightly coupled to the available time budget.
In How Powerful are Performance Predictors in Neural Architecture Search?, Colin White et al. systematically evaluated dozens of performance predictors across various search spaces. The authors revealed that there is no single "best" predictor; rather, the optimal choice depends entirely on the time budget allocated for the initialization and query phases. Complex, heavy predictors (like gradient-boosted trees) yield highly accurate forecasts but require a massive initialization budget to pre-train. When rapid, real-time evaluation is required without prior data collection, simpler or zero-shot prediction strategies become necessary.
Ultimately, the success of predictive optimization hinges on a holistic accounting of wall-clock time: a predictor's utility is determined not just by its accuracy, but by whether its accuracy can compensate for the time it steals from the primary task.
Key Foundational Work
Data Sharing Analysis for a Database Programming Lanaguage via Abstract Interpretation (1993) — contributed 2 concept elements to this direction.
Run-Time Prediction for Production Systems (1992) — contributed 1 concept elements to this direction.