Zoom, Don’t Wander: Why Regional Search Outperforms Pareto Reasoning and Global Optimization in Budget-Constrained SBSE
arXiv:2605.09658v1 [cs.SE] 10 May 2026
Kishan Kumar Ganguly and Tim Menzies North Carolina State University, Raleigh NC, USA [email protected], [email protected]
Abstract. Traditional Search-Based Software Engineering (SBSE) assumes global search and full Pareto exploration are essential. We offer the following negative result based on a study of over 100 Software Engineering (SE) optimization tasks: “zooming” into promising regions is far more effective than Pareto and global exploration under constrained evaluation budgets. Our minimal greedy zoom method, EZR, runs three orders of magnitude faster than Pareto and global Bayesian methods, achieving higher statistical ranks and winning or tying in 84-89% of datasets on equal budget. Even at one-fifth the evaluation budget, EZR wins or ties in 79-81% of datasets. Surprisingly, despite never explicitly seeking a frontier, EZR matches or outperforms Pareto methods on their own coverage metrics (IGD, HV) at equal budgets. The explanation for this widespread failure is structural: across the datasets studied, Pareto-optimal solutions form a tiny, tight island concentrated in a compact region of decision space. Methods that wander waste their budgets outside this island. Beyond efficiency, zooming yields small, interpretable models, thus addressing concerns about black-box AI. By replacing global wandering with greedy zooming, we make SBSE much faster, more explicable, and hence accessible to a wider audience. SBSE practitioners and researchers should zoom, not wander.
Keywords: Multi-objective optimization, Pareto frontier, SBSE
1
Introduction
Software engineering optimization is inherently multi-objective: release planning trades customer value against delivery cost [1], test suites balance coverage against execution time [2], defect prediction simultaneously minimizes false alarms and missed faults [3], and process simulation models jointly optimize risk, cost, and schedule deviation [4]. The Search-Based Software Engineering (SBSE) community’s dominant response to these problems is Pareto-based evolutionary search [5–8]: run a multi-objective optimizer (e.g., NSGA-II [9] or SPEA2 [10]), obtain a frontier of trade-off options, and let the practitioner choose. For large and complex configuration spaces, surrogate-assisted global Bayesian optimization is a natural recourse from the broader optimization literature [11, 12] .
2
K. K. Ganguly and T. Menzies
Both are expensive. Our landscape analysis shows that Pareto solutions are rare (≈0.6% of configurations), concentrated in decision space (85% of datasets), and clustered near the low-distance-to-ideal region of objective space (88% of datasets). This raises a natural question: RQ0: Is expensive frontier exploration and global coverage worth their evaluation cost under realistic SE budgets? To answer RQ0, this paper compares three search strategies across 100+ tasks from MOOT [4]: (1) EZR [13, 14], a minimal contrastive method; (2) SMAC [11], a global Bayesian optimizer; and (3) NSGA-II/SPEA2 [9, 10], Pareto-diversity algorithms. This leads to the following negative result: Negative Result: Under realistic SE budgets, Pareto exploration and global Bayesian search do not justify their costs. While this is a negative results paper, we assert that it is very good news for users and researchers of SBSE algorithms for two reasons. Firstly, there is the issue of efficiency. As shown below, greedy search is orders of magnitude faster than algorithms seeking global coverage. Since it performs as well as these expensive alternatives, our results mean that SBSE methods can be explored and deployed much faster to a much wider audience. Secondly, Interpretability is another key issue. Our greedy search produces small and interpretable models. Figure 1 shows the efficacy of models (blue) built from 100+ MOOT data sets, using a few variables (red) from data sets with 3-1000 variables (yellow). Note that efficacy often remains near the maximum (100) and Fig. 1. Red= #variables used in model; almost unaffected by how few vari- yellow= #variables in dataset features; blue= model efficacy (defined in §4.2, so ables we use. Hence, at least for the larger numbers are better). For an example data used in this study, tiny models of one of these models, see Figure 4. are enough to explain complex optimization problems. This addresses a major concern raised by Rudin [15], who argues that simple, interpretable models are required for high-stakes decisions. Overall, this study makes the following contributions: 1. We show the relative efficacy of focused regional search with EZR versus Pareto methods and global Bayesian Optimization. On constrained budget, EZR wins/ties both in 84–89% of cases, obtaining best solutions in 75% cases (vs 61-68%) and beats Pareto methods on their own frontier metrics. 2. Even when given 5× more budget, Pareto and Global Bayesian search ties/loses to EZR (79% of cases), which runs 2–3 orders of magnitude faster. 3. Pareto solutions are rare (≈ 0.6%) and cluster in both decision (85% of datasets) and objective space near the ideal values (low D2H, 88% of datasets). 4. Replication package: https://github.com/kkganguly/ParetoMyth.
Zoom, Don’t Wander
2
3
Background
The efficacy and interpretability benefits boasted above are somewhat irrelevant if greedy search does not match the solution quality of established Pareto methods. This section argues that it can, by showing that (a) When seeking one best solution, standard Pareto metrics measure the wrong thing for budgetconstrained practitioners, and (b) the structure of SE objective spaces favors zoom methods over frontier-wide exploration. 2.1
The Evaluation Bottleneck
Both Pareto exploration and global search share the same fundamental strategy: wander the space broadly. The standard justification is that Pareto methods promise trade-off options spanning all preference weights and global methods promise escape from local optima. Both assumptions embed the same implicit cost that deserves scrutiny: that evaluation budgets are realistically large enough to make broad exploration worthwhile. In practice, the bottleneck is candidate evaluation cost, not the optimizer [14, 16]. For example, compiler flag selection requires 35–135 minutes per evaluation [16], and Nair et al. explicitly note that “exploring more than a handful of configurations is usually infeasible due to long benchmarking time” [16]; similarly, expert elicitation yields roughly ten labels per session [17, 18]. In such settings, overnight runs or quarterly efforts cap realistic budgets well below 1,000 evaluations (e.g. 100-200 evaluations). Yet, SBSE methods such as NSGA-II routinely assume populations of 100 across hundreds of generations [7, 9]. The right question is therefore not which optimizer wins given unlimited budget, but which wins within what practitioners can actually afford. 2.2
The Practitioner Selection Problem
Pareto Metrics vs D2H Pareto methods present practitioners with GD: convergence to true front; igtrade-off options; at the end, one solution is nores spread. selected. The key question is therefore: under Spread: diversity along front; ignores convergence. a constrained budget, which optimizer proIGD: captures both, but duces the best selectable outcome? weights all preference regions Without stated preferences, equal-weight equally—including extreme tradeoffs no practitioner selects. aggregation is the theoretically grounded deHV: dominated objective-space volfault, and the recommended first point to inume; rewards covering regions a practitioner would never choose. spect is the solution closest to the ideal [19, 20]. Standard indicators IGD and HV cannot measure the quality of a single best outcome, they reward coverage across all preference regions [21]. We therefore use Distance-to-Heaven (D2H), the normalized Euclidean distance to the ideal, as our primary measure. Readers concerned this ignores coverage will find it addressed in RQ3. Under this criterion, exploration is costly. Every evaluation spent on Pareto diversity or global surrogate fitting is one fewer spent improving the best solution, which is a diversity tax that constrained budgets cannot absorb. Since the practitioner selects one solution and the budget is constrained, broad coverage is wasteful by construction.
4
K. K. Ganguly and T. Menzies
It may be argued that reasonably increasing the budget may narrow the gap, but as we show next, it does not change the underlying structure of the problem, which is that Pareto-optimal solutions are concentrated in a small compact region close to the ideal solution. This suggests that a method zooming there should remain competitive regardless of budget, while global methods continue paying an exploration tax on every additional evaluation. 2.3
Zoom Search Trajectories Cover the Pareto Front in SE Data
A natural objection to zoom methods is that they return a single good solution rather than a set of trade-off options. We address this by characterizing where the true Pareto front sits across our SE datasets. In multi-objective optimization this structure is not guaranteed: Pareto fronts can span the entire objective space, with solutions spread across extreme regions [19, 20]. We extract the true Pareto front from each of our 100+ SE datasets via exhaustive non-domination and compute D2H for every configuration. To test whether Pareto solutions occupy a distinct low-D2H region, we compare their D2H distribution against non-Pareto solutions using a Mann-Whitney U test, which is a non-parametric rank test that requires no distributional assumptions and report effect size as rank-biserial correlation (rb), where rb <0 means Pareto solutions rank lower in D2H. We apply the same test to pairwise decision-space distances to check whether Pareto solutions are also spatially clustered: Median Pareto fraction of configurations 0.6% configurations Pareto D2H < non-Pareto D2H (rb < 0) 94% datasets Pareto D2H < non-Pareto D2H (significant, p<0.05, rb < 0, median rb = −0.89) 88% datasets Pareto tighter in decision space (significant, p<0.05, rb < 0) 85% datasets
This is consistent with a structure not previously documented for SE configuration problems: across all 100+ datasets, Pareto solutions are not only rare but doubly concentrated. They occupy a tight cluster in decision space while simultaneously sitting in the near-ideal region of objective space, rather than being dispersed across it as multi-objective theory permits [19, 20]. Implication. A zoom method searching for low-D2H solutions will naturally accumulate near-Pareto solutions along its trajectory. Non-domination filtering over that trajectory should therefore yield practical trade-off coverage without any explicit diversity mechanism. RQ3 tests this prediction: does EZR’s search trajectory provide reasonably good trade-off coverage compared to methods explicitly designed for frontier exploration?
3
Methodology
The previous section justified our central question: at realistic constrained budgets (50-200 evaluations in our study), does pareto and global exploration provide sufficient benefit to justify its use?
Zoom, Don’t Wander
3.1
5
Research Questions
– RQ1 (Solution Quality): Under constrained evaluation budgets, do Pareto methods or global Bayesian search outperform a minimal zoom method in solution quality, at equal or 5 times higher budget, enough to justify their runtime cost? – RQ2 (Budget Sensitivity): Do Pareto methods and global Bayesian search converge to better solutions as budget increases, or do they plateau early while EZR maintains its advantage? – RQ3 (Trade-off Coverage): Can a zoom method’s search trajectory provide useful trade-off options, and how does the resulting frontier compare to that of methods explicitly designed for Pareto exploration? 3.2
Algorithms Algorithm Taxonomy
Pareto Frontier Methods: NSGAII [9] is the one of the most widely cited multi-objective evolutionary algorithm in SBSE [5]. As per Colanzi et al., it is the second most widely used optimizers in SBSE over the past decade [22]. SPEA2 [10] provides an archive-based alternative with strength fitness and k-NN density estimation. Including both ensures results are not artifacts of NSGAII’s specific crowding-distance mechanism. Both are run at 200 (equalbudget comparison) and 1000 evaluations (5× advantage).
Category Algo. Greedy Global Pareto
Baseline
Description
EZR
Greedy exploitation of local promising regions SMAC Bayesian search via Random Forest surrogate NSGA-II Non-dominated sorting with crowding distance SPEA2 Archive-based strength Pareto evolution Random Uniform random exploration; zero learning
EZR SMAC NSGA-II SPEA2
Greedy Global
Random
Baseline
Pareto
50
100
200
1000
Fig. 2. Algorithm Budgets and Taxonomy
Global Bayesian Search: SMAC [11] fits a Random Forest surrogate over the decision space and uses Expected Improvement to select evaluations, optimising D2H directly. It is included because it represents the mainstream alternative to Pareto methods for practitioners seeking a single good balanced solution rather than a frontier. A prior study on the same MOOT benchmark [14] found it competitive with or better than TPE [23] and DEHB [24], making it a reasonable choice among global Bayesian methods for this comparison. Random Sampling Baseline: Random sampling serves as an essential baseline representing zero algorithmic sophistication and pure uniform exploration without learning or adaptation. Arcuri and Briand [25] demonstrated that random search often provides surprisingly competitive performance in SBSE, making it an essential baseline for any optimization comparison. We include Random at two budgets (200 and 1000 evaluations) to baseline with other optimizers’ at similar budgets.
6
K. K. Ganguly and T. Menzies
Regional Search: We use √ a minimal contrastive regional search, EZR [13, 14]. It maintains a Best set ( N solutions with lowest D2H found so far) and a Rest set (near-good solutions displaced from Best as better ones are discovered). At each step, EZR randomly samples 128 candidates from the unlabeled pool and returns the first candidate closer to Best’s decision-space centroid than to Rest’s centroid: xnext = first x ∈ U[128] s.t. dX (x, µB ) < dX (x, µR ) (1) where dX is normalized Euclidean distance over X-columns, and µB , µR are the centroids of Best and Rest respectively. EZR’s sampling of 128 candidates occurs entirely in the unlabelled decision space. Evaluating the x-distance of 128 candidates is computationally trivial and consumes zero objective-function evaluation budget. Only the single selected candidate xnext is actually evaluated to find its y-consequences, meaning EZR strictly consumes exactly one budget unit per iteration. √ Crucially, Best is bounded at N solutions; when a new solution enters, the worst incumbent is demoted to Rest. The combined Best+Rest set therefore captures the full search trajectory: Best holds the current best solutions and Rest accumulates near-good solutions from earlier iterations when the search was exploring slightly different parts of the good region. At termination, a frontier can be constructed by non-domination over Best+Rest, which we utilize in RQ3. We evaluate EZR at four budgets (50, 100, 200, and 1000 evaluations) to assess how quickly regional search converges relative to wandering methods, and to establish the minimum budget at which EZR’s advantage over Pareto and global methods becomes apparent. Why EZR: Among zooming methods (LITE [14], SWAY [26], etc.), EZR is an ideal representative because its simplicity isolates zooming as the sole driver. It has no surrogate, no Pareto reasoning, no complex structures, and its success despite minimal sophistication strengthens our negative result.
4
Experimental Design
4.1
Datasets: The MOOT Benchmark Repository
We evaluate on MOOT (Multi-Objective Optimization Testing) [4], a repository consolidating over 100 SE optimization tasks drawn from dozens of peer-reviewed publications across multiple years of community research. Rather than selecting benchmarks to favor any particular method, MOOT aggregates what the SE community has actually studied. Hence, its diversity is inherited from the literature, not engineered for this evaluation. Tasks span multiple SE domains such as: software configuration (e.g., system performance tuning across 25 software systems and 12 PromiseTune tasks [27]); project health prediction (GitHub health forecasting across closed issues, PRs, and commits); software process models (effort and risk estimation including POM3 and XOMO variants); feature models (Scrum and FM constraint satisfaction problems), software testing tasks and cross-domain analytics (spanning behavioral, financial, and health). Each dataset provides
Zoom, Don’t Wander
7
Table 1. Summary of MOOT datasets. “Features” = number of input variables. Rows
Cited
37 Config Tun- SS-A to SS-X, billing10k, 7z, ing BDBC, HSQLDB, LLVM, PostgreSQL, dconvert, deeparch, exastencils, javagc, redis, storm, x264
# Type
Datasets
System & Performance 3–88 optimisation
Objective
197–167k
[13, 27–34]
1 Cloud 1 Cloud 1 Cloud 1 Cloud 7 Cloud
HSMGP num Apache AllMeasurements SQL AllMeasurements X264 AllMeasurements (rs–sol–wc)*
Hazardous SW Server performance DB tuning Video encoding Misc config
14 9 39 16 3–6
3,457 192 4,654 1,153 196– 3,840
[13, 28, 30, 34] [13, 28, 30, 34] [13, 28, 30] [13, 28, 30] [13, 28, 30–32]
35 Project Health
Health-ClosedIssues,-PRs,Commits
Health prediction
5
10,001
[13, 28, 30, 31, 35]
3 Scrum 8 Feature Models
Scrum1k,10k,100k FFM-*,FM-*
Feature model config Variables/constraints
124 1k–100k 128–1044 10,001
1 SW Process nasa93dem 1 SW Process coc1000 1 SW Process pom3d 3 Behavioral 2 Financial 2 Health 2 RL 5 Sales 3 Misc
Features
Effort/defects/LOC 24 Risk/effort/experience 20 Idle/completion/cost 9
student dropout, HR-attrition, Behavioral patterns player stats home data, Telco-Churn Financial prediction Life Expectancy, hospital Readmissions A2C Acrobot, A2C CartPole accessories, dress-up, Marketing, socks, wallpaper auto93, Car price, Wine quality
93 1,001 501–20k
[13, 28, 29, 31] [13, 28, 29, 31] [28, 30, 31, 35] [13, 28, 30, 35, 36] [28–31, 35]
26–55
82–17k
[37–39]
19–77
1,460– 20k 2,938– 25k 224–318 247– 2,206 205– 1,600
[40, 41]
Health prediction
20–64
RL tasks Sales prediction
9–11 14–31
Miscellaneous
5–38
[42, 43] [44–46] [13, 28, 30, 31, 35]
114 Total
input configurations x and objective values y, with +/- notation indicating maximize/minimize directives. Full dataset details appear in Table 1. 4.2
Evaluation Metrics
D2H (primary, RQ1–RQ2) is the normalized Euclidean distance to the ideal point where all objectives are simultaneously optimal: v u M u 1 X 2 D2H(y) = t (ŷi − hi ) (2) M i=1 Lower is better; the mean formulation ensures comparability across datasets with different numbers of objectives. Validation Regret (RQ2) measures the relative gap to the best achievable solution at evaluation t: regret(t) =
D2Hbest (t) − D2H∗ D2H∗
(3)
where D2H∗ is the minimum D2H over the exhaustively labeled dataset, making regret comparable across datasets with different absolute D2H scales. Frontier coverage metrics (RQ3): True IGD, True GD, HV, and Spacing, computed against the exhaustive true Pareto front. These metrics are appropriate for RQ3 because it asks a different question from RQ1-RQ2: not which method finds the best balanced solution, but whether EZR’s frontier covers all
8
K. K. Ganguly and T. Menzies
Table 2. Scott-Knott summary across 114 SE datasets. Green = best per row per zone. Win/Tie/Loss: reference is always the cheaper method; W+T ≥ 50% means it holds its own or better. Practical Zone (200 evals)
5× Budget Zone (1000 evals)
EZR EZR EZR SMAC NSGA-II SPEA2 Rand EZR SMAC NSGA-II SPEA2 Rand 50 100 200 200 200 200 200 1k 1k 1k 1k 1k Tier 1 (%) Tier 1–2 (%) Tier 3+ (%) Runtime (s)
26 69 31 1.1
50 89 11 2.1
75 98 2 5.2
68 94 6 5060
61 89 11 1396
63 89 11 1420
46 82 18 0.3
98 100 0 0.25
86 98 2 36229
92 99 1 7800
88 96 4 8100
81 97 3 2.1
Evals
50
100
200
200
200
200
200
1k
1k
1k
1k
1k
Ref
Practical Zone (200 evals) Opponent W T L W+T vs L Ref
EZR-200 NSGA-II-200 36 61 17 97 vs 17 (85%) EZR-200 SPEA2-200 33 63 18 96 vs 18 (84%) EZR-200 SMAC-200 22 79 13 101 vs 13 (89%) EZR-200 Rand-200 44 67 3 111 vs 3 (97%) Rand-200 NSGA-II-200 14 67 33 81 vs 33 (71%) Rand-200 SPEA2-200 14 63 37 77 vs 37 (68%) Rand-200 SMAC-200 4 74 36 78 vs 36 (68%)
5× Budget Zone Opponent W T L
W+T vs L
EZR-200 NSGA-II-1000 6 78 22 84 vs 22 (79%) EZR-200 SPEA2-1000 9 76 22 85 vs 22 (79%) EZR-200 SMAC-1000 9 81 21 90 vs 21 (81%) EZR-200 Rand-1000 16 75 23 91 vs 23 (80%) Rand-1000 NSGA-II-1000 5 86 15 91 vs 15 (86%) Rand-1000 SPEA2-1000 7 88 12 95 vs 12 (89%) Rand-1000 SMAC-1000 11 84 16 95 vs 16 (86%)
trade-off positions that a practitioner with any preference weight could want. True IGD and HV penalize any method that misses any region of the true front regardless of preference weight, providing the strongest possible test of the diversity objection. Critically, all metrics are computed against the true front extracted by exhaustive non-domination over the fully labeled dataset, so scores reflect coverage of wherever the SE front actually lies rather than penalizing methods for not covering synthetic uniform distributions. We perform statistical comparisons via Scott-Knott recursive bi-clustering method [47]. It clusters optimizers per dataset by recursively splitting ranked distributions only where bootstrap significance and Cliff’s Delta effect size both confirm a meaningful difference, accounting for both central tendency and variance. Tier 1 denotes the best group, Tier-2 second best etc. In our experiments, each algorithm runs 20 independent trials.
5
Results
5.1
RQ1: Solution Quality
Table 2 reports Scott-Knott tier counts and Win/Tie/Loss comparisons. Win/Tie/Loss counts follow the pairwise practice recommended by Demšar [48]: the cheaper method is the reference, so a Win means EZR-200 reached a better Scott-Knott tier on that dataset, a Tie means both share the same tier, and a Loss means the opponent reached a higher tier. This perspective is intentional: we ask whether the cheaper method holds its own, not the reverse. Equal constrained budget: At 200 evaluations, EZR wins or ties NSGAII in 85% of datasets and SPEA2 in 84%, reaching Tier 1 in 75% of datasets versus 61% and 63% respectively, while being about two orders of magnitude faster. EZR also wins or ties SMAC in 89% of the datasets while being three orders of magnitude faster. The random baseline makes the structural failure
Zoom, Don’t Wander
9
of diversity maintenance explicit: uniform sampling with zero algorithmic machinery wins or ties NSGA-II-200 in 71% of datasets and SPEA2-200 in 68%, and holds its own against SMAC-200 in 68%. A method that does nothing but sample randomly outperforms methods that deliberately maintain diversity and fit surrogates, at the same budget. At constrained budgets, the evaluations consumed by these mechanisms actively seek global coverage, hence displacing evaluations that would otherwise find better solutions, consistent with the landscape structure established earlier. EZR wins or ties Random-200 in 97% of datasets, confirming that directed contrastive search adds value beyond mere sampling. 5× budget disadvantage: EZR at 200 evaluations wins or ties 79% against NSGA-II-1000, 79% against SPEA2-1000, and 81% against SMAC-1000, at three to four orders of magnitude lower runtime than its opponents. The key diagnostic is the EZR-200 versus Random-1000 comparison: EZR at 200 evaluations holds its own against Random at 1000 evaluations in 80% of datasets. Since Random1000 in turn matches NSGA-II-1000 in 86% of datasets and SPEA2-1000 in 89%, the improvement Pareto methods show at high budget is fully explained by additional evaluations reaching the good region through coverage, not by the diversity mechanism becoming useful. Any method given enough evaluations will encounter the good region. Despite budget disadvantage, EZR arrives there in many datasets at one-fifth the cost and orders of magnitude faster. EZR at 1000 evaluations: EZR-1000 reaches Tier 1 in 98% of datasets, the strongest result in the table, confirming that EZR’s contrastive search is not inherently limited by design. The practical recommendation remains EZR-200: the gain from 200 to 1000 evaluations is real but small relative to the 5× cost increase. RQ1. At equal budget, EZR wins or ties Pareto methods in 84–85% of datasets and SMAC in 89%, at orders of magnitude lower runtime. Random sampling alone matches these in 68–71%, confirming that diversity maintenance and surrogate fitting displace useful evaluations. At 5× disadvantage, EZR-200 holds its own in 79–81% against all opponents, proving high-budget gains reflect coverage not search mechanism, neither advantage justifies the runtime cost.
5.2
RQ2: Budget Sensitivity Analysis
RQ1 established that EZR matches or beats Pareto methods and SMAC at equal budget, and holds its own even at a 5× disadvantage. RQ2 asks why: does EZR converge faster, do wandering methods improve steadily with budget, and does additional budget eventually close the gap? Figure 3 shows validation regret (Eq. 3), which is the normalized gap to the best achievable D2H, versus evaluation budget for EZR, NSGA-II, SPEA2, and SMAC.. EZR drops steeply in the first 50-100 evaluations and reaches a stable operating level by evaluation 150-200, confirming that its practical-zone quality is achieved early. Beyond 200 evaluations EZR continues to improve, with a pronounced secondary drop between evaluations 400-600 of several orders of
10
K. K. Ganguly and T. Menzies
magnitude in median regret. This reflects EZR’s search progressively locating near-optimal solutions on more datasets as it zooms into the good region. NSGA-II and SPEA2 improve through the practical zone but require approximately 3.3-3.4× more evaluations to reach the regret level EZR achieves at 200 evaluations. Beyond that crossover both curves continue to decline slowly and exhibit a sharp secondary drop at about 800 evaluation which flattens almost immediately. In Fig. 3. Validation regret (log scale). Pareto spite of this drop, both remain sevmethods need 3.3–3.4× budget vs EZR-200 eral orders of magnitude above EZR’s to match it; SMAC needs > 5×. regret by evaluation 1000. SMAC is the slowest to converge. Its Random Forest surrogate requires broad decision-space coverage before Expected Improvement becomes informative. This makes early evaluations exploratory by design. As shown in Figure 3, SMAC does not reach EZR’s 200-evaluation regret until beyond 5× the budget. This cold-start cost is structural: global Bayesian search cannot exploit the concentrated good region in SE landscapes until it has explored enough to trust its surrogate, by which point EZR has converged. RQ2. EZR reaches a stable operating level by 150–200 evaluations. Pareto methods need 3.3–3.4× more to match it and SMAC needs 5× due to cold-start overhead. No wandering method approaches EZR’s regret trajectory within practical SE budget.
5.3 RQ3: Frontier Quality and the Trade-off Options Objection RQ1 shows that diversity maintenance actively hurts at equal budget and RQ2 confirms that additional budget buys coverage rather than better search. The remaining objection is: Pareto methods offer diverse trade-off options spanning all preferences, which D2H cannot capture. RQ3 addresses this using the standard Pareto coverage metrics. EZR is a single-solution method, but at termination we apply non-domination filtering over the combined Best+Rest trajectory to extract a frontier at no additional evaluation cost. Because Best holds the current low-D2H region and Rest captures near-good solutions from earlier iterations, the resulting non-dominated set spans low D2H region of the true front naturally, reaching near the Pareto front as per landscape argument. Table 3 summarizes frontier coverage. Equal budget: EZR achieves true IGD 0.04 versus 0.09 for NSGA-II-200 and 0.066 for SPEA2-200, and reaches Tier 1 on IGD in 65% of datasets versus 20% and 26%. This is the starkest form of the negative result: at equal budget, diversity maintenance does not build frontier coverage, it prevents it. Every evaluation spent on diversity maintenance is one fewer evaluation finding solutions near the true front, as predicted by the landscape structure.
Zoom, Don’t Wander
11
Table 3. Frontier coverage across 114 datasets. True IGD and True GD: lower is better. HV: higher is better. SK%T1 = fraction of datasets in the best Scott-Knott tier. Bold = best within each budget block. Method
T.IGD
T.GD
HV
Fr. sz
SK%T1 (IGD)
SK%T1 (HV)
Equal budget (200 evals) EZR-200 0.04 NSGA-II-200 0.09 SPEA2-200 0.07
0.04 0.05 0.04
1.03 0.99 0.99
7.0 6.0 6.0
65% 20% 26%
60% 26% 29%
5× budget (1000 evals) EZR-1000 0.03 NSGA-II-1000 0.03 SPEA2-1000 0.04
0.01 0.01 0.02
1.06 1.06 1.05
8.1 8.0 7.8
90% 91% 88%
87% 88% 83%
At 5× budget, Pareto recovers but not through diversity: NSGA-II1000 achieves IGD 0.030 and Tier 1 on 91% of datasets. EZR-1000 matches this exactly (IGD 0.031, Tier 1 on 90%), confirming that the improvement is additional coverage reaching the good region, not the diversity mechanism becoming useful, consistent with the RQ2 finding. The frontier is not degenerate: All methods produce a median of 5.0 nonextreme balanced solutions. Hence, EZR delivers actionable trade-off options similar to Pareto methods at 1000 evaluations, at one-fifth the cost. RQ3. At equal budget EZR beats Pareto methods on their own metrics (IGD 0.040 vs. 0.085/0.066; Tier 1 IGD 65% vs. 20%/26%), delivering the same 5.0 median trade-off options at one-fifth the cost. Under this specific landscape, diversity mechanisms do not build coverage under constrained budgets.
6
Discussion
6.1
A Unified Structural Explanation
All three research questions share one explanation. SE Pareto fronts are rare and doubly concentrated being tight in decision space and clustered near the low-D2H region. Hence, diversity mechanisms waste evaluations on sparse extremes, and as a result, random sampling already beats Pareto methods in 68-71% of datasets (RQ1). EZR reaches a stable operating level by evaluation 150-200, while Pareto methods need 3.3 − 3.4× and SMAC needs 5× that budget just to match it (RQ2). Because EZR’s trajectory naturally accumulates in this same region, it also beats Pareto methods on their own frontier metrics at equal budget (RQ3). The root cause is simple: methods that wander spend most of their budget outside where the good solutions are. The random baseline’s competitive performance (68–71% W+T against Pareto methods) does not suggest MOOT tasks are intrinsically easy. Rather, it confirms the landscape structure: when the Pareto region is a tight 0.6% island, any method, even an uninformed one, has a reasonable chance of landing near it with 200 evaluations. Diversity mechanisms actively reduce this chance by directing evaluations away from the concentrated good region toward sparse extremes. EZR’s directed search (97% W+T over Random) shows that the tasks are not trivial; they do reward informed exploitation, just not frontier-wide diversity.
12
6.2
K. K. Ganguly and T. Menzies
Actionable Trade-off Navigation via Decision Trees
A Pareto frontier shows which outcome trade-offs win are achievable, and the underlying archive records === .67 baseline the configurations that produce them. However, the .63 KLOC <= 227.23 | KLOC <= 93.52 archive alone does not identify which parameters mat- .59 .54 | | RELY > 2.51 ter most or within what bounds to reliably stay in the .62 | | RELY <= 2.51 | | | PCAP <= 4.46 good region. A decision tree trained on Best versus .60 .67 | | | PCAP > 4.46 Rest fills this gap at no additional evaluation cost, it .67 | KLOC > 93.52 | | KLOC <= 212.88 identifies the few master variables and bounds that .63 .58 | | | ACAP <= 4.38 produce low-D2H solutions [14, 27]. .69 | | | ACAP > 4.38 | | KLOC > 212.88 For example, Figure 4, shows the very small tree .74 .72 KLOC > 227.23 learned from the XOMO OSP. Here, our methods se- .68 | RESL > 3.82 | | RELY > 2.42 lected parts of the x space where, compared to the .64 .71 | | RELY <= 2.42 baseline, defects reduced by 5917 ≈ 470% and the de.76 | RESL <= 3.82 1258 .70 | | RUSE <= 4.37 velopment effect by 656 ≈ 329%. 199 .66 | | | PLEx <= 3.19 The data set used to generate Figure 4 has 26 x .76 | | | PLEx > 3.19 attributes. Yet, this tree only used 7. This pattern re- .82 | | RUSE > 4.37 peats across all our data sets: i.e. as seen in Figure 1, Fig. 4. EZR tree on our methods never build trees with more than 10 vari- XOMO OSP. win = perables. Such small trees can be manually browsed and formance gain. As shown used to discover how little we need to change the in- at top, before optimizaput in order to nudge a result into another leaf. We tion, the win=67. Best argue that this answers Rudin’s call [15] for using in- wins were achieved with reducing lines of code and terpretable models in high-stakes decisions. Note that, in principle, our trees could be trained improving reliability. on any Pareto front, but that requires expensive frontier search first. EZR’s Best set delivers equivalent guidance (in the form of very small trees) much faster. 6.3 Practical Recommendations Start with EZR at 200 evaluations: it matches or beats Pareto methods in 84– 85% of tasks, and its search trajectory already outperforms NSGA-II and SPEA2 on IGD and HV at equal budget. The complementary decision tree identifies which parameters to adjust and within what bounds - guidance no Pareto frontier can provide. If more objective-space coverage is needed, escalate to EZR at 1000 evaluations, which matches NSGA-II-1000 on frontier coverage (IGD 0.031 vs 0.030) at orders of magnitude lower runtime. Pareto methods remain a reasonable choice when practitioners have strongly asymmetric preferences or prior domain knowledge suggests a genuinely multimodal front.
7
Threats to Validity
Internal validity. Stochastic comparisons across many datasets risk false positives. Twenty independent replicates and Scott-Knott address this. The random baseline provides a further check: if diversity maintenance helped, random sampling would not match Pareto methods at equal budget.
Zoom, Don’t Wander
13
External validity. All datasets are tabular and pre-labeled, excluding online optimization and corresponding combinatorial constraints similar to many other optimization studies on tabular data [7,13]. Consistency across all five domains reduces domain-specific risk, though generalization beyond these settings requires further study. EZR’s pool-based design requires a pre-labeled or exhaustively enumerable candidate set, which excludes purely online settings (e.g., compiler flag tuning where each configuration must be physically built and run). In such settings, the unlabeled pool can be replaced by a random pre-sample; the centroid-based selection still applies, but initial diversity of that pre-sample becomes important. Extending EZR to true online optimization is future work. Construct validity. D2H assumes equal-weight aggregation as the default when preferences are unknown [19, 20]. This is appropriate given that Pareto solutions lie tightly closer to the ideal than non-Pareto ones across 94% datasets in our case. IGD and HV results further confirm this landscape structure. Algorithm configuration. The algorithm parameters may not represent their best performance. For NSGA-II and SPEA2, population sizes of 10 and 20 for 200 and 1000 evaluation budgets were used respectively, following evidence that smaller populations with more generations improve performance [49], giving Pareto methods advantage. EZR’s parameters are equally untuned, so Pareto methods are if anything advantaged in this study. SMAC uses default surrogate, found strongest among other global optimizers on MOOT [14], making its failure a conservative result. NSGA-II and SPEA2 were selected as the most widely used Pareto methods in SBSE [7], reflecting standard community practice.
8
Related Work
Pareto-based SBSE: Pareto-based search is a dominant SBSE paradigm [5], applied across release planning [1], hyperparameter optimization [3], configuration tuning [7], and process modeling [36], with NSGA-II [9] and SPEA2 [10] as the standard algorithms and NSGA-III [50] and MOEA/D [51] extending this to many-objective and decomposition-based settings. Li et al. [21] provide standard evaluation guidance using IGD and HV, which our RQ3 follows. Chen and Li [7] showed Pareto search wins given sufficient convergence budget. We complement this by analysing where and why Pareto methods fail across 100+ SE datasets under sub-convergence budgets, analyzing the objective-space structure that makes diversity maintenance wasteful in expensive SE settings. Lightweight optimizers: Lightweight and sampling-based optimizers have shown competitive performance in SE at small budgets. SWAY [26] showed hyperplane-based sampling competes with Pareto methods; FLASH [16] found near-optimal configurations in far fewer evaluations than model-based methods; and LITE [14] demonstrated contrastive active learning suffices for SE analytics. PromiseTune [27] suggests why: few master variables govern SE solution quality. Menzies and Ganguly [14] further show that SE problems collapse into surprisingly few occupied regions. These results were limited to single-objective, nonPareto or small-scale settings. We extend the question to 100+ multi-objective tasks, with a comparison against Pareto methods and global Bayesian search under realistic evaluation budgets, showing how, when and why these fail.
14
K. K. Ganguly and T. Menzies
Global Bayesian optimization and explainability: Global Bayesian optimization methods, including SMAC [11], TPE [23], and DEHB [24], use surrogate models to balance exploration and exploitation across the decision space. SMAC is included as stronger than two other methods TPE an DEHB, recently benchmarked on MOOT [14], making its failure here a conservative result. The decision-tree explainability step builds on Rayegan and Menzies [13], which show that shallow Best-vs.-Rest trees produce actionable configuration guidance connecting directly to the levers practitioners can turn [14, 27].
9
Conclusion
Across over 100 SE optimization tasks, Pareto frontier exploration and global Bayesian search fail to justify their cost under realistic evaluation budgets. Diversity maintenance does not merely fail to help - it actively displaces useful evaluations: random sampling beats Pareto methods in 68–71% of datasets, and EZR wins or ties in 84–85% while running orders of magnitude faster and outperforming both NSGA-II and SPEA2 on their own frontier coverage metrics (IGD, HV). The cause is structural: SE Pareto fronts live in a tiny concentrated region aligned with lower D2H, so a method that zooms toward the best-vs-rest boundary finds them naturally without frontier mapping or global exploration. These results do not make Pareto methods obsolete. They remain the right choice when practitioners have strongly asymmetric preferences or when domain knowledge suggests a genuinely multimodal front - the 15–16% of datasets where EZR does not win or tie signals that such cases exist. The most pressing open problem is a cheap pre-screening test to identify these cases in advance, enabling principled algorithm selection without paying the Pareto cost to find out. Extending this evaluation to online optimization, hard combinatorial problems, and many-objective settings where diversity may be harder to avoid, are the natural next steps. Until then, SE practitioners should zoom, not wander.
References 1. Anthony J. Bagnall, Victor J. Rayward-Smith, and Ian M Whittley. The next release problem. Inf. Soft. Tech., 43(14):883–890, 2001. 2. Gordon Fraser and Andrea Arcuri. Evosuite: automatic test suite generation for object-oriented software. In Proc. Found. Soft. Eng., pages 416–419, 2011. 3. Chakkrit Tantithamthavorn, Shane McIntosh, Ahmed E Hassan, and Kenichi Matsumoto. Automated parameter optimization of classification techniques for defect prediction models. In Proc. ICSE, pages 321–332. ACM, 2016. 4. Tim Menzies, Tao Chen, Yulong Ye, Kishan Kumar Ganguly, Amirali Rayegan, Srinath Srinivasan, and Andre Lustosa. Moot: a repository of many multi-objective optimization tasks. arXiv preprint arXiv:2511.16882, 2025. 5. Mark Harman, S Afshin Mansouri, and Yuanyuan Zhang. Search-based software engineering: Trends, techniques and applications. ACM Computing Surveys (CSUR), 45(1):11, 2012. 6. Lev Sorokin, Damir Safin, and Shiva Nejati. Can search-based testing with pareto optimization effectively cover failure-revealing test inputs? Empirical Software Engineering, 30(1):26, 2025. 7. J. Chen and M. Li. The weights can be harmful: Pareto search versus weighted search in multiobjective search-based software engineering. ACM Trans. Soft. Eng. Methodol., 32:1–40, 2023. 8. M. Li, T. Chen, and X. Yao. How to evaluate solutions in pareto-based search-based software engineering: A critical review and methodological guidance. IEEE TSE, 48(5):1771–1799, 2022. 9. Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Trans. Evo. Comp., 6(2):182–197, 2002. 10. Eckart Zitzler, Marco Laumanns, and Lothar Thiele. SPEA2: Improving the strength Pareto evolutionary algorithm. Technical Report TIK-Report 103, ETH Zurich, 2001. 11. Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. Sequential model-based optimization for general algorithm configuration. In Proc. LION, pages 507–523. Springer, 2011.
Zoom, Don’t Wander
15
12. B. Bischl, M. Binder, M. Lang, et al. Hyperparameter optimization: Foundations, algorithms, best practices, and open challenges. WIREs Data Mining Knowl. Discov., 13(2):e1484, 2023. 13. Amirali Rayegan and Tim Menzies. Minimal data, maximum clarity: A heuristic for explaining optimization. arXiv preprint arXiv:2509.08667, 2025. 14. Tim Menzies and Kishan Kumar Ganguly. How low can you go? The data-light SE challenge. In Arxiv, 2026. 15. Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 1(5):206–215, 2019. 16. Vivek Nair, Zhe Yu, Tim Menzies, Norbert Siegmund, and Sven Apel. Finding faster configurations using FLASH. IEEE Transactions on Software Engineering, 46(7):794–811, 2020. 17. Ricardo Valerdi. Heuristics for systems engineering cost estimation. IEEE Sys. J., 2010. 18. Mark Easterby-Smith. The design, analysis and interpretation of repertory grids. International Journal of Man-Machine Studies, 13(1):3–24, 1980. 19. Ching-Lai Hwang and Kwangsun Yoon. Multiple attribute decision making: methods and applications a state-of-the-art survey. Springer Science & Business Media, 2012. 20. Milan Zeleny. Multiple Criteria Decision Making. McGraw-Hill, New York, 1982. 21. Miqing Li, Tao Chen, and Xin Yao. How to evaluate solutions in pareto-based search-based software engineering? a critical review and methodological guidance. IEEE TSE, 2020. 22. T. E. Colanzi, W. K. G. Assunção, S. R. Vergilio, P. R. Farah, G. Guizzo, et al. The symposium on search-based software engineering: Past, present and future. Information and Software Technology, 127:106372, 2020. 23. J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl. Algorithms for hyper-parameter optimization. In NIPS, 2011. 24. Noor H. Awad, Neeratyoy Mallik, and Frank Hutter. DEHB: evolutionary hyberband for scalable, robust and efficient hyperparameter optimization. CoRR, abs/2105.09821, 2021. 25. Andrea Arcuri and Lionel Briand. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In Int. Conf. Soft. Eng., pages 1–10. IEEE, 2011. 26. Jianfeng Chen, Vivek Nair, Rahul Krishna, and Tim Menzies. “sampling” as a baseline optimizer for search-based software engineering. IEEE Trans. Soft. Eng., 45(6):597–614, 2018. 27. Pengzhou Chen and Tao Chen. Promisetune: Unveiling causally promising and explainable configuration tuning. In Proc. of the 48th IEEE/ACM Int. Conf. Softw. Eng., 2026. 28. Tim Menzies. The case for compact ai. Commun. ACM, 68(8):6–7, 2025. 29. Andre Lustosa and Tim Menzies. isneak: Partial ordering as heuristics for model- based reasoning in software engineering. IEEE Access, 12:142915–142929, 2024. 30. Lohith Senthilkumar and Tim Menzies. Can large language models improve se active learning via warm-starts? arXiv preprint arXiv:2501.00125, 2024. 31. Andre Lustosa and Tim Menzies. Less noise, more signal: Drr for better optimizations of se tasks. arXiv preprint arXiv:2503.21086, 2025. 32. V. Nair, A. Agrawal, J. Chen, W. Fu, G. Mathew, T. Menzies, L. L. Minku, M. Wagner, and Z. Yu. Data-driven search-based software engineering. In MSR, 2018. 33. Vivek Nair, Tim Menzies, Norbert Siegmund, and Sven Apel. Using bad learners to find good configurations. In Proc. Found. Soft. Eng., pages 257–267, 2017. 34. Pengzhou Chen, Jingzhi Gong, and Tao Chen. Accuracy can lie: On the impact of surrogate model in configuration tuning. IEEE Trans. Softw. Eng., 51(2):548–580, 2025. 35. Andre Lustosa and Tim Menzies. Learning from very little data: On the value of landscape analysis for predicting software project health. ACM Trans. Soft. Eng. Methodol., 33(3), 2024. 36. Jianfeng Chen, Vivek Nair, and Tim Menzies. Beyond evolutionary algorithms for search-based software engineering. Information and Software Technology, 95:281–294, 2018. 37. Abdullah0a. Student dropout analysis and prediction dataset, 2025. Kaggle. 38. die9origephit. Fifa world cup 2022: Complete dataset, 2025. Kaggle. 39. Pavansubhasht. Ibm hr analytics employee attrition & performance, 2025. Kaggle. 40. blastchar. Telco customer churn, 2025. Kaggle. 41. dansbecker. Home data for ml course, 2025. Kaggle. 42. dansbecker. Medical data and hospital readmissions, 2025. Kaggle. 43. Kumar A. Rajarshi. Life expectancy (who) dataset, 2025. Kaggle. 44. jessicali9530. Animal crossing new horizons: Nookplaza dataset, 2021. Kaggle. 45. Jack Daoud. Marketing analytics – marketing data, 2022. Kaggle. 46. syedfaizanalii. Car price dataset – cleaned, 2025. Kaggle. 47. A. J. Scott and M. Knott. A cluster analysis method for grouping means in the analysis of variance. Biometrics, 30:507–512, 1974. 48. Janez Demšar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine learning research, 7(Jan):1–30, 2006. 49. Max Hort and Federica Sarro. The effect of offspring population size on NSGA-II: A preliminary study. In Proc. GECCO, pages 1–2. ACM, 2021. 50. Kalyanmoy Deb and Himanshu Jain. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach. IEEE TSE, 18(4):577–601, 2014. 51. Qingfu Zhang and Hui Li. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6):712–731, 2007.