{"id":"22edd690-3615-4539-a216-3db0c87533b3","arxiv_id":"2605.28703","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":5.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Baldwinian and Lamarckian evolution outperform Darwinian evolution empirically on Max Independent Set and Max Cut tasks and show better asymptotic runtime on the extended Deceptive Leading Block benchmark.","lead":"The paper compares Lamarckian and Baldwinian evolution against standard Darwinian evolution in evolutionary algorithms using experiments on graph optimization problems and theoretical runtime analysis on an extended benchmark. Smart generalists might read it to see whether adding local search steps can make evolutionary methods competitive with specialized solvers on hard combinatorial tasks.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"The local-search cost model is the load-bearing assumption for the 'Baldwinian fastest when cost included' claim","rationale":"The reader's weakest_assumption exactly isolates the step that converts the fitness-evaluation ordering into a practical-runtime claim; everything else in the abstract (empirical outperformance on GraphBench, parameter recommendations) is independent of this modeling choice. Because the paper itself flags that the ordering 'depends on the implementation,' the cost-model assumption is the single point whose failure would falsify the headline theoretical conclusion.","tokens_in":1751,"tokens_out":360,"duration_ms":18588,"concrete_test":"Re-derive the expected-runtime bounds for block length k=3 under two explicit cost models: (1) local search costs O(k) fitness evaluations per individual, (2) local search costs O(2^k) (exhaustive). Check whether the Baldwinian upper bound remains asymptotically smaller than the Lamarckian bound in both models.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The theoretical analysis first derives an ordering (Baldwinian < Lamarckian < Darwinian) purely from the number of fitness evaluations on the extended Deceptive Leading Blocks function. It then states that 'when accounting for the cost of the local search procedure ... the ordering depends on the implementation' yet still concludes Baldwinian remains fastest from small block lengths. No explicit cost function (e.g., number of neighborhood evaluations per local-search step, dependence on block length k, or whether Lamarckian updates change the per-step cost) is supplied in the abstract, so the second claim rests on an unstated modeling choice that could reverse the ordering for plausible implementations such as exhaustive search inside each block or fixed-iteration hill-climbing.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper empirically evaluates Baldwinian, Lamarckian, and Darwinian evolutionary algorithms on Maximum Independent Set and Maximum Cut instances from six GraphBench datasets, reporting consistent outperformance of the local-search-augmented variants over plain Darwinian evolution and often over deep learning baselines, while also supplying a recommended generalist parameter set. Theoretically, it extends the Deceptive Leading Blocks function to arbitrary block length k and derives asymptotic runtime bounds showing that, for k>2, Baldwinian evolution is fastest, followed by Lamarckian, then Darwinian when counting only fitness evaluations; when local-search costs are included the ordering is stated to depend on implementation details yet Baldwinian remains fastest from small k onward.","tokens_in":1922,"tokens_out":571,"duration_ms":20473,"significance":"If the empirical protocol is fully reproducible and the local-search cost model is made explicit, the work would supply both practical guidance (generalist parameters) and the first rigorous asymptotic comparison of the three evolutionary regimes on an extended benchmark, strengthening the case for hybrid local-search EAs. The use of modern runtime-analysis tools to obtain matching upper and lower bounds is a methodological strength.","major_comments":[{"comment":"Theoretical analysis (paragraph immediately after the fitness-evaluation-only bounds): the claim that 'Baldwinian evolution staying fastest from small block lengths onwards' when local-search cost is included rests on an unstated cost model; no explicit function is supplied that defines the per-step cost of local search (e.g., as a function of block length k, neighborhood size, or whether Lamarckian inheritance alters the cost), so it is impossible to verify whether the reported ordering survives plausible implementations such as exhaustive enumeration inside each block.","section":"Theoretical analysis"},{"comment":"Empirical evaluation section: the abstract asserts 'consistent outperformance' and 'in the great majority of cases' superiority over deep-learning baselines, yet the manuscript provides neither the precise data-exclusion rules, the statistical test used for 'consistent', nor the full experimental protocol (random seeds, termination criteria, how ties are broken), rendering the central empirical claim difficult to assess for robustness.","section":"Empirical evaluation"}],"minor_comments":[{"comment":"Notation: the extended Deceptive Leading Blocks function is introduced without an explicit equation number or definition of the fitness function for arbitrary k; adding a displayed equation would improve readability.","section":"Theoretical analysis"},{"comment":"Table/figure captions: several result tables lack explicit indication of whether reported runtimes include or exclude local-search overhead, which is directly relevant to the cost-model discussion.","section":null}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the constructive comments on our manuscript. We address each major point below and will revise the paper accordingly to improve clarity and reproducibility.","responses":[{"response":"We agree that an explicit cost model was not provided. In the revised manuscript we will introduce a concrete cost function for local search (e.g., linear in block length k for exhaustive enumeration within each block, with an additional constant factor for Lamarckian inheritance of the improved genotype). We will then restate the asymptotic comparison under this model and show that the claimed ordering (Baldwinian fastest from small k onward) holds for the standard implementation we have in mind. The fitness-evaluation-only bounds remain unchanged.","revision_made":"yes","referee_comment":"[Theoretical analysis] Theoretical analysis (paragraph immediately after the fitness-evaluation-only bounds): the claim that 'Baldwinian evolution staying fastest from small block lengths onwards' when local-search cost is included rests on an unstated cost model; no explicit function is supplied that defines the per-step cost of local search (e.g., as a function of block length k, neighborhood size, or whether Lamarckian inheritance alters the cost), so it is impossible to verify whether the reported ordering survives plausible implementations such as exhaustive enumeration inside each block."},{"response":"We acknowledge the lack of protocol detail. The revision will add a dedicated experimental-setup subsection that specifies: (i) the exact statistical test and significance threshold used to support 'consistent outperformance', (ii) random seeds and number of independent runs, (iii) termination criteria, (iv) tie-breaking rule, and (v) any data-exclusion criteria. We will also make the full result tables and code repository reference explicit so that the claims can be verified.","revision_made":"yes","referee_comment":"[Empirical evaluation] Empirical evaluation section: the abstract asserts 'consistent outperformance' and 'in the great majority of cases' superiority over deep-learning baselines, yet the manuscript provides neither the precise data-exclusion rules, the statistical test used for 'consistent', nor the full experimental protocol (random seeds, termination criteria, how ties are broken), rendering the central empirical claim difficult to assess for robustness."}],"tokens_in":1497,"tokens_out":479,"duration_ms":18065,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that this paper runs a large empirical comparison on Maximum Independent Set and Maximum Cut from GraphBench across six datasets and finds that Baldwinian and Lamarckian evolution beat plain Darwinian evolution, often beat recent deep learning baselines, and get close to specialized solvers. They also extend the Deceptive Leading Blocks function to arbitrary block lengths and prove runtime bounds showing Baldwinian faster than Lamarckian faster than Darwinian for lengths greater than two.\n\nWhat is actually new is the arbitrary-length extension of that benchmark together with the new upper and lower bounds, plus the scale of the graph experiments and the reported generalist parameter sets. The experiments appear broad enough to be useful for practitioners looking for concrete settings.\n\nThe soft spot is the handling of local search cost in the theory. The abstract derives the evaluation ordering first, then states that including local search cost makes the ordering implementation-dependent yet still concludes Baldwinian remains fastest from small block lengths onward. No explicit cost function (neighborhood size, dependence on block length, or how Lamarckian updates affect per-step cost) appears in the abstract, so the final claim depends on an unstated modeling choice that could flip for plausible implementations such as exhaustive search inside blocks. The stress-test note correctly flags this as load-bearing.\n\nThis work is for people in evolutionary computation who care about hybrid local-search EAs on combinatorial graphs or runtime analysis on deceptive functions. A reader who wants empirical parameter guidance or asymptotic comparisons on the extended benchmark would get value from it. It deserves a serious referee because the empirical breadth is real and the theory-practice link is worth checking in detail, even if the cost model needs tightening.","headline":"The empirical comparison on GraphBench is the solid part here, but the theoretical claim that Baldwinian stays fastest once local search cost is included rests on an underspecified cost model.","tokens_in":2403,"tokens_out":416,"would_cite":false,"duration_ms":21637,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Baldwinian evolution is asymptotically faster than Lamarckian which is faster than Darwinian for block lengths greater than two.","keywords":["evolutionary algorithms","Lamarckian evolution","Baldwin effect","runtime analysis","maximum independent set","maximum cut","local search","graph optimization"],"falsifier":"An empirical runtime measurement on the extended Deceptive Leading Block problem with block length four in which the average number of fitness evaluations required by Darwinian evolution is smaller than that required by Baldwinian evolution.","tokens_in":2660,"feed_emoji":"","tokens_out":759,"duration_ms":22684,"temperature":0.7,"pith_summary":"The paper compares three styles of evolutionary algorithms on both graph problems and a theoretical benchmark. It demonstrates that versions using local search outperform plain Darwinian evolution in experiments on Maximum Independent Set and Maximum Cut across six datasets, often beating deep learning baselines. On the theoretical side the authors extend the Deceptive Leading Block problem to arbitrary block lengths and prove runtime bounds showing Baldwinian evolution requires fewer fitness evaluations than Lamarckian, which in turn beats Darwinian, once blocks exceed length two. When the cost of local search is folded into the fitness count the ordering can shift, yet Baldwinian stays fastest from small blocks onward in the cost models examined. These results matter because they quantify when and why hybrid local-global search improves efficiency on hard combinatorial tasks.","feed_headline":"Baldwinian evolution asymptotically fastest for blocks longer than two","feed_subtitle":"Runtime bounds on the extended Deceptive Leading Block problem place it ahead of Lamarckian and Darwinian; empirical tests on graphs confirm","key_machinery":"The Deceptive Leading Block benchmark extended to arbitrary block lengths, together with upper and lower bounds on expected runtime derived from modern theoretical runtime analysis.","core_discovery":"On the Deceptive Leading Block benchmark extended to arbitrary block length, for block lengths greater than two Baldwinian evolution is asymptotically faster than Lamarckian which is asymptotically faster than Darwinian evolution. When the cost of the local search procedure is included in the fitness evaluation count, Baldwinian evolution remains the fastest from small block lengths onwards. Empirically, on graphs drawn from six datasets, Baldwinian and Lamarckian variants consistently outperform Darwinian evolution, exceed recent deep learning baselines in most cases, and approach the performance of specialised heuristics and exact solvers.","pith_inferences":["The Baldwinian advantage may arise because learned local improvements guide the population without locking the genotype into a local optimum that must be inherited.","The reported generalist parameters could serve as a practical starting point for applying these hybrids to other combinatorial problems where local search is cheap relative to global search.","The runtime ordering may change on landscapes whose deception structure differs from the leading-block pattern, suggesting targeted experiments on other benchmark families."],"forward_implications":["Baldwinian and Lamarckian evolution outperform Darwinian evolution on the great majority of Maximum Independent Set and Maximum Cut instances tested.","All three evolutionary algorithm variants exceed recent deep learning baselines in most cases examined.","A single set of generalist parameters works well across Darwinian, Lamarckian and Baldwinian evolution on the studied graph problems.","Baldwinian evolution retains the best asymptotic runtime even after local search cost is included, for the cost models considered."],"fun_headline_variants":["Baldwinian evolution fastest for blocks longer than two","Lamarckian beats Darwinian on extended Deceptive Leading Block","Local search variants outperform Darwinian on six graph datasets","Baldwinian stays fastest when counting local search cost"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The cost of the local search procedure used inside the Baldwinian and Lamarckian variants can be assigned to fitness evaluations without changing the runtime ordering obtained from the number of evaluations alone.","fun_headline_variants_meta":{"raw":{"variants":["Baldwinian evolution fastest for blocks longer than two","Lamarckian beats Darwinian on extended Deceptive Leading Block","Local search variants outperform Darwinian on six graph datasets","Baldwinian stays fastest when counting local search cost"]},"model":"grok-4.3","cost_usd":0.006232,"raw_usage":{"total_tokens":2972,"prompt_tokens":743,"num_sources_used":0,"completion_tokens":64,"cost_in_usd_ticks":62324500,"prompt_tokens_details":{"text_tokens":743,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2165,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":743,"tokens_out":64,"duration_ms":20231,"temperature":1.0,"reasoning_tokens":2165,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-29T09:06:15.234695+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An empirical runtime measurement on the extended Deceptive Leading Block problem with block length four in which the average number of fitness evaluations required by Darwinian evolution is smaller than that required by Baldwinian evolution.","supporting_citations":[],"review_version":1}