{"id":"0621cea0-a270-41ec-bacc-e98df1e70700","arxiv_id":"2505.12627","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Hercules improves LLM-based heuristic generation by abstracting core components of elite heuristics into prompts, and Hercules-P reduces search cost by having the LLM predict heuristic fitness values instead of evaluating all candidates.","lead":"Researchers propose two prompting techniques, CAP and PPP, that make large language models better at automatically designing heuristics for combinatorial optimization problems. The methods improve heuristic quality and cut evaluation cost, but the theoretical argument rests on a tautological identity and several headline claims are weaker than the tables show.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The headline SOTA claim is not supported by the paper's own tables: Hercules loses to EoH or Random in several reported cells (e.g., Table 1 Llama3-70b n=200; Table 5 LEHD TSP n=1000), and most comparisons lack error bars, so 'outperforms SOTA across four tasks, five COPs, eight LLMs' is currently…","rationale":"The reader's own review already flags lack of error bars and inconsistent tables; my stress-test elevates that to the central load-bearing issue. The CAP information-gain proof (Eq. 1-4, Appendix A) is a standard entropy-decomposition identity and, by itself, proves only that conditioning on a partition reduces entropy; it does not establish that Hercules's particular abstraction yields better heuristics. That burden falls on the empirical tables, and those tables contain losses and ties. PPP calibration (Eq. 7) is a related secondary risk: with r=0.39 the acceptance of predicted fitness on the basis of phi_i could bias the population, and the w/o ConS ablation (-4.06 vs 7.46) shows ConS is doing real work. But even if PPP worked perfectly, the 'SOTA across all tasks' claim would still need the missing statistical support. I therefore recommend keeping the paper CONDITIONAL: the method is plausible, code is available, and several large improvements exist, but universal SOTA and on-par claims should be softened and supported by significance testing and sensitivity analysis, especially for the tuned hyperparameters λ=0.7 and δ=0.1.","tokens_in":21653,"tokens_out":9764,"duration_ms":103839,"concrete_test":"Re-run the main comparisons (Tables 1, 3, 4, 5, 10, 11) with at least 10 independent seeds per algorithm-task-LLM cell and report paired bootstrap or permutation test p-values for Hercules vs EoH, ReEvo, and Random. Count significant wins/losses/ties across all cells. If Hercules is not significantly better than the best baseline on a majority of task-LLM-scale cells, the abstract and Section 1 should be revised from 'outperforms SOTA across...' to 'is competitive on several tasks,' and 'on-par' for Hercules-P should be restricted to cells where the gap is statistically negligible.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Central claim: Hercules and Hercules-P are SOTA across four HG tasks, five COPs, and eight LLMs (Abstract, Section 1). The evidence in Tables 1-5 does not establish this. Table 1 (Llama3-70b, n=200): Hercules 3.42 vs EoH 5.82. Table 3: Hercules average 4.87 vs EoH 4.80, a tie. Table 5: LEHD TSP n=1000 Hercules 5.14 vs EoH 6.09; POMO TSP n=200 Hercules 2.49 vs EoH 2.19 and Random 3.05. Hercules-P is much worse than Hercules in many cells (e.g., POMO TSP n=200: -0.10 vs 2.49), so 'on-par gain' is not visible there. Most entries are means over three runs without standard deviations or tests; where std is given (Table 4), gaps like 2.19 vs 2.01 with std 0.20/0.34 are unlikely to be significant. Without a systematic win/loss count and significance testing, the universal SOTA assertion is load-bearing but unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two components for LLM-based heuristic generation. Core Abstraction Prompting (CAP) extracts core components from elite heuristics and feeds them into prompts so that LLM-generated search directions are more specific; a theoretical claim is made that CAP reduces unspecificity in the sense of information gain. The second component, Performance Prediction Prompting (PPP), uses a few-shot LLM prompt to predict fitness values of newly generated heuristics, together with an EXEMPLAR selection mechanism and a Confidence Stratification (ConS) acceptance rule, yielding a resource-efficient variant Hercules-P. The authors report extensive experiments across four heuristic-generation tasks, five combinatorial optimization problems, and eight LLMs, and claim state-of-the-art gains for Hercules and 7%--59% search-time reductions for Hercules-P at on-par quality.","tokens_in":21970,"tokens_out":3515,"duration_ms":37347,"significance":"If the empirical claims hold, the paper makes a useful practical contribution: CAP is a simple, zero-shot mechanism that plausibly improves the specificity of LLM search directions, and PPP is, to my knowledge, a novel use of LLMs as fitness predictors in heuristic generation. The manuscript is also strong in breadth: it covers multiple LLMs, seed algorithms, and problem types, and the authors release code and prompts. The ablation studies, especially the statistical comparison of EXEMPLAR variants in Figure 6, are a good-faith attempt to isolate design choices. However, the current evidence does not support the universal SOTA claim in the abstract and introduction, and the theoretical argument in Section 3.1/Appendix A is better described as a formalization of an assumption than a proof of CAP's benefit. These are load-bearing issues for the paper's central claims.","major_comments":[{"comment":"The proof of Proposition 1 is internally correct only after assuming the conditional-probability identity p_j * p(omega_i | Omega_j) = p(omega_i | Omega_t) for every subset j and every direction omega_i. This identity is not a consequence of probability calculus; it is an assumption that the abstraction partitions the direction space without loss. Furthermore, the claimed positivity range (0, log(k+1)] in Eq. (4) requires that no subset has probability 1, and this non-degeneracy is exactly the behavioral conclusion the theorem is supposed to establish. Please state these assumptions explicitly and either prove them from the CAP mechanism or reframe the result as a formalization of the intended effect rather than a proof of empirical benefit.","section":"Section 3.1 and Appendix A"},{"comment":"The headline claim that Hercules outperforms state-of-the-art LLM-based HG algorithms across four tasks, five COPs, and eight LLMs is not supported by the paper's own tables. Table 1 shows that with Llama3-70b at n=200, Hercules obtains gain 3.42 versus EoH's 5.82. Table 3 shows average gains of 4.87 for Hercules versus 4.80 for EoH, a near tie with no reported variance. In Table 5, POMO TSP n=200 gives Hercules 2.49 versus Random 3.05 and EoH 2.19, and LEHD TSP n=1000 gives Hercules 5.14 versus EoH 6.09. A systematic win/loss count across all cells and statistical significance tests are needed before the universal SOTA statement can be made.","section":"Section 1, Tables 1, 3, and 5"},{"comment":"The on-par performance claim for Hercules-P is not demonstrated. Table 5 contains several cells where Hercules-P is substantially worse than Hercules or even negative, e.g., POMO TSP n=200 (-0.10 vs 2.49) and POMO CVRP n=200 (-0.57 vs 1.53). Table 6 reports only search time, not quality, so the reported 7%--59% savings do not by themselves establish resource efficiency at on-par performance. In addition, the reliance of ConS on the LLM's self-reported confidence phi_i is weakly supported: the paper itself reports a Pearson correlation of only 0.39 between predicted and true fitness values (Section 4.5), and no calibration analysis for the confidence values is provided. The authors should report quality and time jointly, and provide evidence that the confidence threshold in Eq. (7) is well-calibrated.","section":"Tables 5 and 6, Section 4.5"},{"comment":"Most gain tables report only the mean over three independent runs, without standard deviations or tests, while the few reported standard deviations (Table 4) show overlapping intervals for several key comparisons, e.g., BPP n=1000 Hercules 2.19 +/- 0.20 versus ReEvo 2.01 +/- 0.34. Given that the universal SOTA claim rests on small numeric gaps, the paper should report per-cell standard deviations or confidence intervals and run paired significance tests (or a systematic win/loss summary) across all tasks and LLMs. Without this, the claim that Hercules outperforms SOTA is not verifiable from the presented data.","section":"Experimental methodology, Tables 1--5"}],"minor_comments":[{"comment":"The phrase \"we theoretically prove the effectiveness of CAP in reducing unspecificity\" overstates what Eq. (4) establishes; consider replacing it with \"formalize the intended reduction\" or similar.","section":"Abstract and Introduction"},{"comment":"There is a typo in \"real-wolrd case study\" that should be corrected to \"real-world\".","section":"Section 4.1"},{"comment":"The text notes that Random outperforms the other methods on some NCO tasks, but the discussion does not reconcile this with the universal SOTA claim; please add an explicit discussion of these counterexamples.","section":"Section 4.4, Table 5"},{"comment":"The figure label contains garbled text (\"w w/o w/o1\") and the figure is difficult to read; the axis labels and legend should be clarified.","section":"Section 4.5, Figure 6"},{"comment":"There is a typo \"repsectively\" that should be \"respectively\".","section":"Appendix G"},{"comment":"The paragraph after the proof argues that the one-to-one mapping assumption is reasonable, but the argument would be more convincing if it stated that the information-gain formula changes only by replacing k with k_c; the notation should be made explicit.","section":"Appendix A"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for the venue and contains a useful practical system, but the public claims are considerably stronger than the evidence. I would ask the authors to revise the SOTA statements to match the actual win/loss pattern, add statistical support, and reframe the theoretical section as a formalization rather than a proof of empirical benefit. The code release and breadth of experiments are commendable and give me confidence that the empirical gaps can be addressed with additional analysis rather than new experiments alone."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The interesting piece here is PPP: using an LLM to predict heuristic fitness from semantic similarity, with EXEMPLAR for example selection and ConS for confidence-based acceptance. That is a real step for heuristic generation, and the 7–59% search-time savings are believable. CAP is a reasonable zero-shot twist on step-back prompting, and the ablation studies are honest. Code is out, and the experimental span—four tasks, five COPs, eight LLMs—is more than most papers in this area bother with.\n\nThe soft spots are real, though. The theoretical claim in Section 3.1/Appendix A is just the identity IG = H - Σ p_j H_j = -Σ p_j log p_j, which is the definition of mutual information under a partition. The positivity conclusion requires p_j < 1 for every j; the paper waves this away with \"the diverse nature of LLM training corpora.\" That is an assumption, not a proof. Please soften the \"theoretically proven\" language to \"we motivate\" or \"we argue.\"\n\nMore importantly, the universal SOTA claim does not survive contact with the paper's own tables. Table 1 has EoH beating Hercules on Llama3-70b n=200 (5.82 vs 3.42). Table 3 is a near-tie (4.80 vs 4.87). Table 5 shows EoH ahead on POMO TSP n=200 (2.19 vs 2.49) and Random beating everyone on some NCO cells. Most tables lack error bars, so we cannot tell if the reported gaps are real, and Hercules-P is sometimes far worse than Hercules (Table 5 POMO TSP n=200: -0.10 vs 2.49), undercutting the \"on-par\" claim. The correlation between predicted and true fitness is only 0.39, so ConS is carrying a lot of weight on a weak predictor. Hyperparameters (lambda, delta, etc.) are tuned on one task and applied everywhere, with no sensitivity analysis across tasks.\n\nThe citation pattern looks fine, and the authors do acknowledge some negative results, which I appreciate. This is a useful paper for anyone working on LLM-based algorithm design or hyper-heuristics, but read the tables carefully.\n\nI would send this to serious peer review. The PPP idea is worth debating, and the empirical scope is substantial. I would ask the authors to (1) fix the theoretical overclaim, (2) report error bars and a win/loss count with significance tests, (3) substantiate the \"on-par\" claim for Hercules-P with the actual numbers, and (4) add a hyperparameter sensitivity analysis. With those changes, the paper would be solid.","headline":"The PPP performance predictor is a genuinely new and useful idea with broad experiments, but the universal SOTA claim overshoots the evidence and the 'proof' of CAP is an identity plus an assumption.","tokens_in":22495,"tokens_out":2964,"would_cite":true,"duration_ms":31416,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"By abstracting elite heuristics' core components as prompt prior knowledge, Hercules steers LLMs to specific search directions, and its confidence-gated fitness predictor cuts search time by up to 59%.","keywords":["large language models","heuristic generation","combinatorial optimization","core abstraction prompting","performance prediction","prompting","evolutionary computation","resource efficiency"],"falsifier":"Measure prediction error separately for heuristics that ConS trusts (confidence at least 1−δ) and for those it re-evaluates; if the trusted set's errors are not significantly smaller in absolute value than the untrusted set's, then the confidence signal carries no information and Hercules-P's speedup is not the reliable filtering the paper claims, so rerunning Hercules-P with shuffled confidence values should leave search time and gain essentially unchanged.","tokens_in":21425,"feed_emoji":"🤖","tokens_out":7515,"duration_ms":69912,"temperature":0.7,"pith_summary":"This paper claims that the main weakness of LLM-based heuristic discovery for combinatorial optimization is not the LLM's coding ability but the vagueness of the search directions it is prompted to give. To fix this, the authors introduce Hercules, a heuristic-generation loop whose Core Abstraction Prompting (CAP) first asks the LLM to extract the core components of the current elite heuristics and then uses those components as prior knowledge when asking for new directions. They prove, via an information-gain argument, that such abstraction reduces the entropy (unspecificity) of the produced directions. They also add Performance Prediction Prompting (PPP) to let the LLM estimate the fitness of new heuristics from semantic similarity to evaluated ones, with confidence-gated acceptance, yielding a variant, Hercules-P, that cuts search time by 7%–59% while matching Hercules's quality. If the claims hold, LLM-based heuristics become both stronger and much cheaper to produce.","feed_headline":"LLM heuristic generation: sharper directions, up to 59% faster search","feed_subtitle":"Prompted with elite heuristics' core components, Hercules predicts fitness to skip re-running similar code.","key_machinery":"The central object is the prompting pipeline wrapped around a generational loop. Core Abstraction Prompting (CAP) is a zero-shot prompt that summarizes the top-k heuristics' core components, e.g., 'normalize penalties relative to overall distance', and feeds them as prior knowledge for search directions. Performance Prediction Prompting (PPP) is a few-shot prompt that presents a set of previously evaluated heuristics with distinct fitness values and asks the LLM to predict the fitness of new code from semantic similarity, returning a confidence score. Two small mechanisms make PPP usable: EXEMPLAR selects the historical best/worst plus top parents with distinct fitness values as examples, and Confidence Stratification (ConS) decides per heuristic whether to accept the LLM's predicted fitness or pay for a real COP-instance evaluation, using the acceptance threshold schedule m_t = ⌊α·β^t·N_o⌋. Together they carry the paper's twin claims: CAP reduces unspecificity (with a proven entropy bound) and PPP reduces evaluation cost without degrading population quality.","core_discovery":"The paper's central claim is that feeding an LLM the abstracted core components of its best-so-far heuristics, rather than asking for reflections on performance, shifts the distribution of generated search directions toward actionable task-specific ideas, and that this shift can be quantified as an information gain. In formal terms, partitioning the space of possible directions by the k core components reduces entropy from H(Ω_t) to ∑ p_j H(Ω_j), giving IG = −∑ p_j log p_j in (0, log(k+1)]; the authors prove this identity and present it as the mechanism behind CAP's improvement. The companion claim is that an LLM can act as a fitness predictor: given a few well-chosen evaluated heuristics (best, worst, and top parents with distinct fitness values), the LLM predicts a new heuristic's performance from semantic similarity and outputs a confidence value; the ConS rule then decides which predictions to trust. Empirically, Hercules outperforms previous LLM-based heuristic generators across four tasks, five combinatorial optimization problems, and eight LLMs, while Hercules-P delivers similar gains in less compute.","pith_inferences":["If CAP's entropy-reduction argument applies as generally as stated, the same abstraction trick could be applied to other LLM-driven program synthesis tasks beyond combinatorial optimization, such as circuit design or scheduling policies, which the paper does not explore.","The paper documents that LLMs frequently produce semantically equivalent heuristics; this suggests an explicit deduplication step based on code embedding similarity could complement PPP and further cut evaluation counts, a step the authors do not take.","ConS currently thresholds confidence into three discrete bands; smoothing the acceptance probability as a continuous function of the confidence value could recover more of PPP's time savings while avoiding the bias-variance cliff at band boundaries.","A stress test for PPP would be to run it on a search space where semantic novelty is high; in such a regime the semantic-similarity signal may weaken, and the claimed 7%–59% speedup could shrink or require more real evaluations."],"forward_implications":["Hercules sets a new performance bar across four heuristic-generation tasks, five combinatorial optimization problems, and eight LLMs, so the specificity gain from CAP transfers across model families and problem types.","Hercules-P cuts search time by 7% to 59% while matching Hercules's gain, making LLM-driven heuristic design practical in settings with limited compute, such as near-real-time resource allocation.","The theoretical bound IG = −∑ p_j log p_j ∈ (0, log(k+1)] implies that any partitioning of the direction space by core components reduces entropy, so the benefit of CAP is structural rather than accidental to one model.","The rank-based selection mechanism and the early-iteration use of elite components accelerate convergence, as shown by the ablation where replacing rank-based selection with random selection drops gain from 11.10% to 8.49%.","PPP's EXEMPLAR mechanism improves predictive accuracy by 26% to 37% in median accuracy relative to using duplicate-fitness or random examples, indicating that example quality matters more than example quantity for LLM fitness prediction."],"supporting_citations":[{"why":"Supplies the Reflection Prompting (RP) baseline that Hercules extends, along with the crossover/mutation operators and experimental setups reused for fair comparison.","marker":"[53]"},{"why":"The Evolution of Heuristics (EoH) baseline, the main LLM-based evolutionary framework whose crossover/mutation prompting Hercules must beat on the same COP instances.","marker":"[22]"},{"why":"Defines the information-gain concept that the paper adapts to prove that abstracting core components reduces the unspecificity of LLM-produced search directions.","marker":"[13]"},{"why":"Shows that LLMs can act as performance predictors in neural architecture search, the direct inspiration for adapting the idea to heuristic generation as PPP.","marker":"[6]"},{"why":"Another LLM-based performance predictor that PPP contrasts with by relying on only a few high-quality examples rather than a larger set.","marker":"[15]"},{"why":"Provides the 18 TSPLIB benchmark instances used to evaluate the constructive heuristics derived in the generalization experiments.","marker":"[34]"},{"why":"Supplies the distance-aware attention reshaping seed function used to test Hercules and Hercules-P on neural combinatorial optimization solvers.","marker":"[40]"},{"why":"Supplies the human-designed KGLS seed function for the guided local search TSP experiments, the baseline against which gains are measured.","marker":"[1]"}],"fun_headline_variants":["LLM heuristics: learn from the best, predict the rest","Core abstractions + fitness prediction = leaner LLM heuristics","Skip the rerun: LLM predicts which heuristics will work","Hercules: elite patterns improve LLM heuristic generation","Faster COP solving: LLM uses core ideas and forecasts quality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Hercules-P's time savings rest on the assumption that the LLM's self-reported confidence in its fitness prediction reliably flags predictions worth trusting; the paper reports only a 0.39 correlation between predicted and true fitness, so a miscalibrated confidence could let poor heuristics slip through while the claimed on-par performance is not guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["LLM heuristics: learn from the best, predict the rest","Core abstractions + fitness prediction = leaner LLM heuristics","Skip the rerun: LLM predicts which heuristics will work","Hercules: elite patterns improve LLM heuristic generation","Faster COP solving: LLM uses core ideas and forecasts quality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000539,"raw_usage":{"total_tokens":2649,"prompt_tokens":1073,"completion_tokens":1576,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":689,"completion_tokens_details":{"reasoning_tokens":1488}},"tokens_in":689,"tokens_out":1576,"duration_ms":16715,"temperature":1.0,"reasoning_tokens":1488,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:30:33.168990+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure prediction error separately for heuristics that ConS trusts (confidence at least 1−δ) and for those it re-evaluates; if the trusted set's errors are not significantly smaller in absolute value than the untrusted set's, then the confidence signal carries no information and Hercules-P's speedup is not the reliable filtering the paper claims, so rerunning Hercules-P with shuffled confidence values should leave search time and gain essentially unchanged.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Reflection Prompting (RP) baseline that Hercules extends, along with the crossover/mutation operators and experimental setups reused for fair comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Evolution of Heuristics (EoH) baseline, the main LLM-based evolutionary framework whose crossover/mutation prompting Hercules must beat on the same COP instances."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the information-gain concept that the paper adapts to prove that abstracting core components reduces the unspecificity of LLM-produced search directions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Another LLM-based performance predictor that PPP contrasts with by relying on only a few high-quality examples rather than a larger set."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the 18 TSPLIB benchmark instances used to evaluate the constructive heuristics derived in the generalization experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the human-designed KGLS seed function for the guided local search TSP experiments, the baseline against which gains are measured."}],"review_version":1}