Time-Fair Benchmarking for Metaheuristics: A Restart-Fair Protocol for Fixed-Time Comparisons

Junbo Jacob Lian

REVIEW 4 major objections 5 minor 12 references

Time-Fair Benchmarking for Metaheuristics: A Restart-Fair Protocol for Fixed-Time Comparisons

T0 review · 4 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Metaheuristic benchmarks should be budgeted by wall-clock time, not function-evaluation counts, and a restart-fair fixed-time protocol is the way to do it.

desk verdict A clear, well-written position piece on time-fair benchmarking, but its fairness claim is undercut by permitting unrestricted parallelism; deserves peer review with heavy revision. read the letter →

arxiv 2509.08986 v1 pith:T3IU56HG submitted 2025-09-10 cs.NE cs.PFstat.CO

Junbo Jacob Lian This is my paper

classification cs.NEcs.PFstat.CO

keywords metaheuristicsbenchmarkingwall-clocktimerestartfairnessexpectedrunningperformanceprofilesanytimeoptimizationchecklist

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that comparing metaheuristics by equal function evaluations (FEs) is inherently unfair, because algorithms can hide heavy per-iteration work, preprocessing, or tuning behind the same FE count. The authors propose that benchmarkers award every algorithm the same wall-clock time budget per problem instance, and then let each algorithm use that budget however it likes—restarts, early stopping, adaptive mechanisms. They formalize this as a fixed-time, restart-fair protocol, with anytime performance curves, expected running time to target, and time-based performance profiles as the recommended metrics. A concrete PSO example shows a time-fair comparison can invert the ranking an FE-equivalent comparison produces. The upshot is that benchmarking becomes aligned with real deployment decisions, where users care about solution quality within a given clock time.

What carries the argument

The restart-fair fixed-time protocol. It consists of three definitions: a fixed-time budget T per instance; restart-fairness, which lets an algorithm with single-run duration τ execute k = ⌊T/τ⌋ independent runs and keep the best result; and a time-to-target ERT metric that counts the time to reach a quality threshold across successful runs and reports infinity with empirical success rate if no run reaches it. These are combined with anytime performance curves and time-cost performance profiles, plus a reporting checklist covering budget, restarts, targets, statistical rigor, environment, tuning overhead, and artifacts. This machinery directly converts FE-equivalent comparisons into time-fai

What would settle it

Run a fixed set of algorithms under an identical wall-clock budget T on a single machine, repeat the experiment 30 times, and check whether the performance-profile ranking stays stable; if ranking reversals are common due to timing noise alone, then wall-clock time is not a reproducible cost measure and the protocol's central premise fails.

Watch

Extended reading notes

Core claim

The central claim is that wall-clock time, not function evaluations, should be the principal budgetary constraint for metaheuristic comparison. Under the protocol, each algorithm receives an identical wall-clock budget T per instance; it may run multiple independent restarts (at most floor(T/τ) for average run duration τ), use any internal adaptive strategy, and is evaluated on the best solution found within T. Performance is summarized through anytime curves, ERT to predefined quality targets, and performance profiles whose cost metric is time. The paper further requires explicit reporting of tuning and ancillary costs and hardware/software details, so that hidden computational burdens are

Load-bearing premise

The protocol assumes that wall-clock time, measured on a given hardware and software stack, is a fair and sufficiently reproducible measure of algorithmic cost so that equal time budgets yield meaningful comparisons.

Editorial extensions

If this is right

Algorithms with lower per-run overhead are incentivized to exploit multiple restarts, which can escape local optima and improve best-found quality within the fixed budget.
A time-fair comparison can reverse the ranking that a function-evaluation comparison produces, as the PSO example in the paper shows.
Hidden computational costs—preprocessing, surrogate modeling, hyperparameter tuning, library overhead—are forced into the open when wall-clock time is the budget.
Benchmark results become directly interpretable by practitioners who care about solution quality within a given clock time, rather than about abstract evaluation counts.
Adoption of the accompanying reporting checklist would make benchmarks more reproducible and more comparable across studies.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The protocol could be extended to multi-objective or dynamic optimization by substituting a time-based attainment function for the single-objective anytime curve, though the paper leaves this to future work.
In settings where function evaluations are extremely expensive, FE budgets may still be the appropriate primary constraint, but the paper's insistence on also reporting wall-clock time would still expose differences in per-evaluation overhead.
A natural stress test is to re-run existing benchmark suites under a fixed-time restart-fair budget and check whether published superiority claims survive the switch to time costs; the paper suggests this would frequently invert results.
The reproducibility of wall-clock time as a measure is itself an empirical question: if OS noise, CPU frequency scaling, or library differences make time budgets unstable across otherwise identical runs, the protocol's premise would need a hardened measurement layer (e.g., multiple repetitions and median times).

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

You should know two things about this paper. First, it is a clearly written position piece arguing that wall-clock time should replace function evaluations as the main budget in metaheuristic benchmarking, and it offers a restart-fair protocol to do that. Second, the central fairness claim has a structural gap: the protocol explicitly permits unrestricted internal parallelism within the fixed time budget, so equal wall-clock time does not mean equal computational resources. A 32-core algorithm can do far more work in the same T than a single-threaded baseline, and the paper never fixes cores/threads or CPU-hours. That undercuts the 'equitable comparisons' promise.

What is actually new: not much. The protocol synthesizes Dolan-More performance profiles, COCO/BBOB's ERT and anytime ECDFs, IOHprofiler workflows, and restart strategies from Kadioglu, Friedrich, Weise. The checklist is a reasonable distillation of existing best practices. The paper is honest that the illustrative PSO example is fictional and that figures are placeholders. It engages the literature properly.

Where it is soft: the parallelism hole is the big one, and it is not minor. Definition 1 invites it, Algorithm 1 measures only wall-clock time, and the checklist only asks to list hardware—not to fix a per-algorithm core budget. The motivating example and Algorithm 2 assume single-threaded runs, so the formalization does not cover a regime the paper itself allows. Also, there is zero empirical validation. Proposition 1 is asserted, not proved, and the example's numbers are invented—fine for illustration, but they do not demonstrate anything. The claim that faster-per-iteration algorithms benefit from restarts follows almost directly from Definition 2, so the example is somewhat circular. None of this is fatal for a position piece, but it means the protocol remains a proposal, not a result.

The paper is for anyone who benchmarks metaheuristics and is tired of FE-only claims that hide per-iteration overhead. It is a useful discussion document and could mature into a practical guide with two fixes: a per-algorithm resource budget (cores or CPU time) and at least one real benchmark run on BBOB or IOHprofiler.

I would send it to peer review—not desk reject—because the question is important and the protocol is close to being usable. But I would expect heavy revision and push hard on the parallelism issue. My verdict: conditional, and the condition is non-trivial.

Referee Report

4 major / 5 minor

Summary. The manuscript proposes a fixed-time, restart-fair benchmarking protocol for metaheuristics, arguing that wall-clock time rather than function evaluations (FEs) should be the principal budgetary constraint. It formalizes this via three definitions (fixed-time budget, restart-fairness, time-to-target/ERT), a two-algorithm evaluation procedure, a reporting checklist, and an illustrative PSO example. The stated goal is to make algorithmic comparisons more equitable and practically relevant by permitting restarts, early stopping, adaptive mechanisms, and by exposing hidden overheads such as tuning and preprocessing costs.

Significance. The paper addresses a real and widely acknowledged problem: FE-only comparisons can conceal per-iteration computational overhead, leading to inflated performance claims. The proposed protocol, if adopted, could reorient benchmarking around deployment constraints that practitioners actually face. The definitions are mostly transparent, the ERT formula in Eq. (1) is the standard expression, and the reporting checklist is practical and actionable. However, the manuscript is a proposal rather than a validated study: it contains no empirical data, the figures are explicitly placeholders, and the illustrative example uses invented numbers. The central 'equitable comparisons' claim is also weakened by the protocol's failure to control computational resources and by an implementation gap in Algorithm 1. These issues are fixable, but they are load-bearing for the paper's central contribution.

major comments (4)

[Definitions 1-2; §4, checklist item 6] Definition 1 permits 'internal parallelism' within a fixed wall-clock budget T, but the protocol never fixes a core/thread budget per algorithm. Definition 2's k=⌊T/τ⌋ treats τ as a single-run wall-clock duration and implicitly assumes serial execution; with 32 cores versus 1 core, a parallel algorithm can perform roughly 32 times more work in the same T. The paper's 'equitable comparisons' therefore fail unless a per-algorithm core/thread count is fixed, or CPU time is reported as a secondary budget. Checklist item 6 only asks to enumerate hardware, not to hold it fixed across algorithms.
[Algorithm 1] Algorithm 1's while loop checks time_used only before starting a run. There is no per-run hard deadline; if an algorithm does not terminate or early-stop before the remaining budget is exhausted, the run overshoots T, violating Definition 1. The protocol needs an explicit timeout mechanism (e.g., halt at T - time_used, or check elapsed time inside the run).
[§2, Proposition 1] Proposition 1 is asserted without proof. As stated, it is largely a restatement of Definition 2: once restarts are allowed, an algorithm with smaller τ can run more k=⌊T/τ⌋ runs. If it is intended as a substantive claim—that more restarts improve solution quality—it needs a proof or direct empirical evidence; the cited restart-strategy literature is only indirectly related. The proposition should either be proven or demoted to a remark.
[§3 and §5] The illustrative PSO example uses entirely invented numbers and the figures are explicitly placeholders. The text claims 'This inversion underscores how time-fairness reveals practical efficacies obscured by FE equivalence' (Section 3), but a constructed example cannot underscore an empirical advantage. The paper should either provide real benchmark results (e.g., BBOB/IOHprofiler) in place of the placeholders, or clearly label the example as purely schematic and temper the wording accordingly.

minor comments (5)

[§3, ERT arithmetic] The ERT values in the illustrative example are inconsistent with Eq. (1) and T=50. For PSO (95% success, 18 s average time-to-target), ERT = (19·18 + 50)/19 ≈ 20.6 s, not 20.5 s. For APSO (85% success, 22 s), ERT = (17·22 + 3·50)/17 ≈ 30.8 s, not 25.9 s. Please correct the arithmetic or clarify the assumptions.
[Algorithm 1, line 4] The instruction 'execute A once with independent seed until termination or early success' should specify what happens if a run would exceed T - time_used. Add an explicit deadline or a check within the run.
[Reproducibility Statement] The reproducibility statement promises scripts and utilities, but no artifacts are included with the manuscript. Please provide a repository link or an appendix with at least the evaluation and plotting code.
[Section 7, Limitations and Scope] The scope limitation is useful, but the abstract and introduction claim broad applicability. State early on that the protocol targets settings where algorithmic overhead is non-negligible relative to evaluation times, and that FE-based budgets may remain appropriate for evaluation-dominated problems.
[Figures 1 and 2] The placeholders should be replaced by real plots in the final version. Add axis labels, legends, and captions that describe the hypothetical data generation if retained as schematic.

Circularity Check

0 steps flagged · score 2.0 of 10

No substantive circularity; only a minor non-load-bearing self-citation to the author's IECO paper.

full rationale

This paper is a normative methodological proposal rather than an empirical derivation chain. The central claim—that wall-clock time should be the principal budget for metaheuristic benchmarking—is argued from practical deployment constraints and supported by external surveys (Bartz-Beielstein et al., Sala and Müller) and standard tools (Dolan–Moré profiles, COCO, IOHprofiler). No parameter is fitted to data and then relabeled as a prediction; the illustrative PSO example is explicitly fictional, and the figures are placeholders. The only self-citation is to Tang et al. 2025 (IECO), which appears as related work / 'practical inspiration' for restart mechanisms, not as the load-bearing justification for the protocol, so it does not make the central claim circular. Proposition 1 does restate the immediate consequence of Definition 2 (k = floor(T/tau) implies lower per-run overhead yields more restarts), but this is an explicit definitional observation, not a hidden reduction of an empirical result to its inputs. The skeptic's concern about internal parallelism and core counts is a scope/assumption limitation, not circularity. Accordingly, the paper is largely self-contained and honest; the score reflects only the minor, non-load-bearing self-citation.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper contributes no fitted free parameters and introduces no new entities. Its load-bearing assumptions are mostly domain assumptions about the fairness and stability of wall-clock time as a benchmark resource, plus the effectiveness of restarts. The fictional APSO in Section 3 is explicitly labeled as illustrative, not a proposed real algorithm.

assumptions (5)

domain assumption Wall-clock time should be the principal budget for fair comparison.
The paper's normative premise, stated in the abstract and Section 1.
domain assumption Restart strategies can improve solution quality.
Relied on by Proposition 1 and supported only by citations (Kadioglu et al., Weise et al.).
domain assumption Benchmark hardware/software can be specified precisely enough for reproducibility.
Section 4, item 6 requires hardware and library details; the protocol assumes this suffices for time-based comparisons.
domain assumption Measured wall-clock time is repeatable across runs on the same hardware.
Implicit in Definitions 1 and 3; OS noise and CPU frequency scaling are not discussed as threats.
domain assumption The problem setting is single-objective black-box optimization.
Explicitly scoped in Section 7; the protocol is not claimed for multi-objective or dynamic problems.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Time-Fair Benchmarking for Metaheuristics: A Restart-Fair Protocol for Fixed-Time Comparisons." pith.science (2026). https://pith.science/paper/T3IU56HG

@misc{pith2026250908986,
  author       = {Pith},
  title        = {Pith review of: Time-Fair Benchmarking for Metaheuristics: A Restart-Fair Protocol for Fixed-Time Comparisons},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T3IU56HG}},
  note         = {Machine review of arXiv:2509.08986}
}

read the original abstract

Numerous purportedly improved metaheuristics claim superior performance based on equivalent function evaluations (FEs), yet often conceal additional computational burdens in more intensive iterations, preprocessing stages, or hyperparameter tuning. This paper posits that wall-clock time, rather than solely FEs, should serve as the principal budgetary constraint for equitable comparisons. We formalize a fixed-time, restart-fair benchmarking protocol wherein each algorithm is allotted an identical wall-clock time budget per problem instance, permitting unrestricted utilization of restarts, early termination criteria, and internal adaptive mechanisms. We advocate for the adoption of anytime performance curves, expected running time (ERT) metrics, and performance profiles that employ time as the cost measure, all aimed at predefined targets. Furthermore, we introduce a concise, reproducible checklist to standardize reporting practices and mitigate undisclosed computational overheads. This approach fosters more credible and practically relevant evaluations of metaheuristic algorithms.

Figures

Figures reproduced from arXiv: 2509.08986 by the authors.

**Figure 2.** Performance profiles utilizing time (e.g., ERT or time-to-target) as the underlying cost metric. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

12 extracted references · 4 canonical work pages

[1]

Malan, Jason H

Thomas Bartz-Beielstein, Carola Doerr, Daan van den Berg, Jakob Bossek, Sowmya Chandrasekaran, Tome Eftimov, Andreas Fischbach, Pascal Kerschke, William La Cava, Manuel L \'o pez-Ib \'a \ n ez, Katherine M. Malan, Jason H. Moore, Boris Naujoks, Patryk Orzechowski, Vanessa Volz, Markus Wagner, and Thomas Weise. Benchmarking in optimization: Best practice a...

arXiv 2007
[2]

Iohprofiler: A benchmarking and profiling tool for iterative optimization heuristics

Carola Doerr, Hao Wang, Furong Ye, Sander van Rijn, and Thomas B \"a ck. Iohprofiler: A benchmarking and profiling tool for iterative optimization heuristics. arXiv preprint arXiv:1810.05281, 2018

arXiv 2018
[3]

Dolan and Jorge J

Elizabeth D. Dolan and Jorge J. Mor \'e . Benchmarking optimization software with performance profiles. Mathematical Programming, 91 0 (2): 0 201--213, 2002

2002
[4]

A generic bet-and-run strategy for speeding up stochastic local search

Tobias Friedrich, Timo K \"o tzing, and Markus Wagner. A generic bet-and-run strategy for speeding up stochastic local search. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-17), pages 801--807, 2017

2017
[5]

Real-parameter black-box optimization benchmarking 2010: Experimental setup

Nikolaus Hansen, Anne Auger, Steffen Finck, and Raymond Ros. Real-parameter black-box optimization benchmarking 2010: Experimental setup. Technical Report RR-7215, INRIA, France, 2010. URL https://hal.inria.fr/inria-00502412

2010
[6]

Hoos, and Kevin Leyton-Brown

Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. Algorithm configuration. In Handbook of Heuristics, pages 141--173. Springer, 2019. doi:10.1007/978-3-319-07124-4_8-1

work page doi:10.1007/978-3-319-07124-4_8-1 2019
[7]

Learning a reactive restart strategy to improve stochastic search

Serdar Kadioglu, Meinolf Sellmann, and Markus Wagner. Learning a reactive restart strategy to improve stochastic search. In Learning and Intelligent Optimization (LION 11), LNCS 10556, pages 109--123. Springer, 2017. doi:10.1007/978-3-319-69404-7_9

work page doi:10.1007/978-3-319-69404-7_9 2017
[8]

Exploratory analysis of stochastic local search algorithms in biobjective optimization

Manuel L \'o pez-Ib \'a \ n ez, Lu \' s Paquete, and Thomas St \"u tzle. Exploratory analysis of stochastic local search algorithms in biobjective optimization. In Thomas Bartz-Beielstein, Marco Chiarandini, Lu \' s Paquete, and Mike Preuss, editors, Experimental Methods for the Analysis of Optimization Algorithms, pages 209--222. Springer, Berlin, German...

work page doi:10.1007/978-3-642-02538-9_9 2010

Show all 12 references

[9]

Benchmarking for metaheuristic black-box optimization: Perspectives and open challenges

Ramses Sala and Ralf M \"u ller. Benchmarking for metaheuristic black-box optimization: Perspectives and open challenges. In 2020 IEEE Congress on Evolutionary Computation (CEC), 2020. doi:10.1109/CEC48606.2020.9185724

2020
[10]

Performance measure and tool for benchmarking metaheuristic optimization algorithms

Fran c ois Schott, Dominique Chamoret, Thomas Baron, S \'e bastien Salmon, and Yann Meyer. Performance measure and tool for benchmarking metaheuristic optimization algorithms. Journal of Applied and Computational Mechanics, 7 0 (3): 0 1803--1813, 2021. doi:10.22055/JACM.2021.3...

2021
[11]

Ieco: an improved educational competition optimizer for state-of-the-art engineering optimization

Xiaojie Tang, Junbo Jacob Lian, and et al. Ieco: an improved educational competition optimizer for state-of-the-art engineering optimization. Journal of Big Data, 12 0 (1): 0 200, 2025. doi:10.1186/s40537-025-01260-0

2025 doi
[12]

An improved generic bet-and-run strategy for speeding up stochastic local search

Thomas Weise, Zijun Wu, and Markus Wagner. An improved generic bet-and-run strategy for speeding up stochastic local search. arXiv preprint arXiv:1806.08984, 2018

2018 arXiv

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

Malan, Jason H

Thomas Bartz-Beielstein, Carola Doerr, Daan van den Berg, Jakob Bossek, Sowmya Chandrasekaran, Tome Eftimov, Andreas Fischbach, Pascal Kerschke, William La Cava, Manuel L \'o pez-Ib \'a \ n ez, Katherine M. Malan, Jason H. Moore, Boris Naujoks, Patryk Orzechowski, Vanessa Volz, Markus Wagner, and Thomas Weise. Benchmarking in optimization: Best practice a...

arXiv 2007

[2] [2]

Iohprofiler: A benchmarking and profiling tool for iterative optimization heuristics

Carola Doerr, Hao Wang, Furong Ye, Sander van Rijn, and Thomas B \"a ck. Iohprofiler: A benchmarking and profiling tool for iterative optimization heuristics. arXiv preprint arXiv:1810.05281, 2018

arXiv 2018

[3] [3]

Dolan and Jorge J

Elizabeth D. Dolan and Jorge J. Mor \'e . Benchmarking optimization software with performance profiles. Mathematical Programming, 91 0 (2): 0 201--213, 2002

2002

[4] [4]

A generic bet-and-run strategy for speeding up stochastic local search

Tobias Friedrich, Timo K \"o tzing, and Markus Wagner. A generic bet-and-run strategy for speeding up stochastic local search. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-17), pages 801--807, 2017

2017

[5] [5]

Real-parameter black-box optimization benchmarking 2010: Experimental setup

Nikolaus Hansen, Anne Auger, Steffen Finck, and Raymond Ros. Real-parameter black-box optimization benchmarking 2010: Experimental setup. Technical Report RR-7215, INRIA, France, 2010. URL https://hal.inria.fr/inria-00502412

2010

[6] [6]

Hoos, and Kevin Leyton-Brown

Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. Algorithm configuration. In Handbook of Heuristics, pages 141--173. Springer, 2019. doi:10.1007/978-3-319-07124-4_8-1

work page doi:10.1007/978-3-319-07124-4_8-1 2019

[7] [7]

Learning a reactive restart strategy to improve stochastic search

Serdar Kadioglu, Meinolf Sellmann, and Markus Wagner. Learning a reactive restart strategy to improve stochastic search. In Learning and Intelligent Optimization (LION 11), LNCS 10556, pages 109--123. Springer, 2017. doi:10.1007/978-3-319-69404-7_9

work page doi:10.1007/978-3-319-69404-7_9 2017

[8] [8]

Exploratory analysis of stochastic local search algorithms in biobjective optimization

Manuel L \'o pez-Ib \'a \ n ez, Lu \' s Paquete, and Thomas St \"u tzle. Exploratory analysis of stochastic local search algorithms in biobjective optimization. In Thomas Bartz-Beielstein, Marco Chiarandini, Lu \' s Paquete, and Mike Preuss, editors, Experimental Methods for the Analysis of Optimization Algorithms, pages 209--222. Springer, Berlin, German...

work page doi:10.1007/978-3-642-02538-9_9 2010