{"id":"988d0412-4c49-4fad-b337-754a631c5812","arxiv_id":"2509.09707","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"An LLM-generated, per-instance bias vector improves a BRKGA on the NP-hard Longest Run Subsequence problem, with statistically significant gains on 15 of 35 instance groups, concentrated on complex instances.","lead":"This paper tests whether a large language model can act as a per-instance advisor to a genetic algorithm on the Longest Run Subsequence problem, and finds that the guided version beats the plain algorithm on the hardest instance classes. It is the first application of the authors' own LLM-as-heuristic-bias framework to a string-based problem, with modest but statistically supported gains.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Missing control: a fixed sensible static bias could match the LLM's gains, undermining the 'instance-driven' claim.","rationale":"The reader's verdict of CONDITIONAL is well supported. The paper is methodical, statistically rigorous, and honest about the 57.14% of groups without significant improvement. The ablation against random bias vectors (§4.7) shows the LLM output is not noise. However, the missing control for a fixed, sensible static bias is the most load-bearing gap because it directly targets the 'instance-driven' and 'tailored' language in the abstract and conclusion. Without it, the observed gains could be explained by the mere presence of a smooth bias, which would not require an LLM at all. This is not an internal inconsistency but an underdetermination of the central claim; hence CONDITIONAL is the right verdict. I agree with the reader's weakest_assumption. The prompt-metric inconsistency is a secondary issue: it affects interpretability but does not by itself overturn the performance results. The proposed static-bias test would settle the main concern: if a fixed bias does as well, the paper's central novelty ('instance-driven') collapses to 'any helpful bias', and the verdict should be revised downward; if the static bias performs clearly worse, the instance-driven claim is substantially validated. No change to the reader's verdict is needed at this stage.","tokens_in":35771,"tokens_out":4983,"duration_ms":50533,"concrete_test":"Run BRKGA+Llama-4-Maverick with its irace-tuned hyperparameters (ψ=17, πe=0.12, πm=0.30, ρe=0.69) on the same 1,050 instances, but replace the per-instance LLM alpha/beta with a fixed static bias for every instance—e.g., L_i = ML(R_i), or the consensus α=(0.4,0.3,0.2,0.1), β=(1.0,1.0,1.0,0.5). If the average solution quality is within ~0.3 of 313.07 (or above), the instance-driven component is unsupported; if it drops below 312, the instance-specific LLM analysis is doing real work. A complementary check: shuffle the LLM-generated bias vectors across instances of the same (length, alphabet) group; if shuffled biases perform equally well, the 'tailored' aspect is void.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (abstract; §6) is that 'instance-driven' and 'tailored' LLM bias improves BRKGA. The only ablation for this is §4.7/Table 6, which compares the LLM-generated bias vector against uniform random vectors (static and dynamic). This controls for noise but not for instance-specificity: it does not exclude the possibility that any smooth, sensible bias—e.g., setting L_i to normalized run length, or using the consensus alpha/beta values visible in Figure 8—would produce the same ~313 average. If a fixed static bias matches or beats 313.07, the improvement is due to 'a non-random bias helps BRKGA', not to the LLM's instance analysis. The paper provides no such control, so the 'instance-driven' component is unsupported. Additionally, the Phase 3 prompt (§3.3.1) mis-describes Normalized_length as 'Length of the run divided by the total string length' (formal definition §3.2: ML = l_i/l_max) and Opportunity as '1/(1+gap)' (formal: MO = |Σ_{>i}|/|Σ|). While this does not invalidate the measured performance, it weakens the interpretability analysis (§4.9) and complicates the claim of a clean co-designed metric set.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a framework that uses an LLM to analyze a per-instance table of four run metrics for the Longest Run Subsequence (LRS) problem and to output eight coefficients (four alpha weights, four beta ideals). These coefficients define a fixed bias vector L that multiplies the random keys in a BRKGA decoder, biasing the construction order before evolution begins. Four LLM variants are compared against a standard BRKGA on 1,050 uniformly random instances with lengths 100-5000 and alphabets 2-32. Each variant is tuned separately with irace. The best variant, BRKGA+Llama-4-Maverick, achieves an average score of 313.07 versus 311.85 for the baseline, with statistically significant superiority in 15 of 35 instance groups, concentrated in large-alphabet instances. Ablation studies with random bias vectors and with alternative metric sets, STN behavioral analysis, parameter-distribution analysis, and cost/latency analysis are also reported.","tokens_in":1494,"tokens_out":1471,"duration_ms":74545,"significance":"If the result holds, the paper provides evidence for a cheap, zero-shot way to inject instance-specific structure into BRKGA and extends the authors' earlier OptiPattern paradigm to a string-based combinatorial problem. The empirical apparatus is careful: per-variant irace tuning, honest disclosure that 20 of 35 instance groups show no significant improvement, a random-bias control showing the LLM signal is informative, and a behavioral analysis. The paper ships code and the experiments are reproducible. However, the central 'instance-driven' claim is not fully separated from a generic 'non-random bias helps BRKGA' effect, and the prompt used in Phase 3 describes two metrics in a way that conflicts with their formal definitions. These issues do not invalidate the measured performance but do require additional controls and clarification before the paper's main claims are fully supported.","major_comments":[{"comment":"The only ablation isolating the LLM's contribution is §4.7/Table 6, which compares the LLM-generated bias vector against uniform random vectors. This controls for 'non-random' but not for 'instance-driven': it does not exclude the possibility that any fixed, sensible bias--e.g., using the consensus alpha/beta values visible in Figure 8, or setting L_i proportional to the normalized run length--yields the same ~313 average. If a static bias matches or beats 313.07, the improvement is due to adding a smooth bias to BRKGA, not to the LLM's per-instance analysis. Please add a static-bias control (e.g., median alpha/beta from Figure 8, or a hand-coded L_i = ML_i) and report the comparison.","section":"§4.7, Table 6; §4.9, Figure 8"},{"comment":"The Phase 3 prompt's [BEGIN EVALUATION SEQUENCE] describes Normalized_length as 'Length of the run divided by the total string length' and Opportunity as '1/(1+gap)', whereas §3.2 defines ML(R_i)=l_i/l_max and MO(R_i)=|Σ_{>i}|/|Σ|. The table inserted in the prompt uses the formal definitions, so the LLM sees values whose column labels have incorrect semantics. This does not necessarily invalidate the empirical gains, but it undermines the interpretability analysis of §4.9 and the claim of a cleanly co-designed metric set. Correct the prompt descriptions (or the formal definitions), or explicitly document the mismatch and its possible effect on the LLM's outputs.","section":"§3.3.1 vs §3.2"},{"comment":"The benchmark consists exclusively of iid uniform random strings. The introduction and Section 2.2 motivate the work by string-based bioinformatics problems, but no structured, non-uniform, or biological strings are tested. The generalization in Section 6 and the abstract's 'complex optimization domains' is therefore an extrapolation. Add a small set of structured/biological instances (or clearly delimit the claims to uniform random strings).","section":"§4.2"},{"comment":"The random 4-metric set achieves an average of 312.94, essentially tied with the curated set's 313.07. Thus the human-LLM curation is shown to matter only through pre-computation cost (Figure 6), not solution quality. The authors acknowledge this honestly, but Section 1.1 presents the co-design process as a contribution without noting this quality-neutrality. Please adjust the framing so that the claimed contribution of the human-LLM metric co-design is stated as computational feasibility, not improved solution quality.","section":"§4.6, Table 5 (Case 2)"}],"minor_comments":[{"comment":"The text says 'with a budget of 3000 runs over 70 instances' but the preceding description defines 42 tuning instances (35 + 7). Correct the count.","section":"§4.4"},{"comment":"The header uses [0,1]^n for the random-key vector and [0,1]^m for L, but n should be m (the number of runs) for consistency with Algorithm 1 and Section 2.4.","section":"Algorithm 2"},{"comment":"The lightning-bolt icon appears as '/bol◎' in several places; this is likely a LaTeX/PDF rendering artifact and should be fixed.","section":"Tables 2, 5, 6"},{"comment":"The parenthetical 'e.g., an LRS sequence with 'length=5000'' is oddly placed; consider rephrasing.","section":"§3.3.3"},{"comment":"The caption says '1050 instances' but the subplots show distributions for 30 instances per configuration. Clarify the aggregate.","section":"Figure 8 caption"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The manuscript is carefully executed and the authors are transparent about negative results. The main risk is the missing static-bias control for the 'instance-driven' claim; I would require it before publication. The prompt/formal-definition mismatch is also easy to fix but damages interpretability if left. The paper is largely an empirical extension of the authors' own OptiPattern framework, so the novelty is incremental but acceptable for the target venue if the requested controls are added."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The first thing you should know: this is the first real test of the instance-driven LLM bias paradigm on a string problem, and the empirics are a cut above the usual for this subfield. Every variant is irace-tuned, they report significance per instance group, and the random-bias ablation in Table 6 genuinely shows the LLM output carries signal, not just noise. The best hybrid, BRKGA+Llama-4-Maverick, beats the baseline by about 1.2 points on average, with the gains concentrated in the large-alphabet groups. That is a modest effect, but it looks real.\n\nWhat's genuinely new is the transfer to the LRS problem and the human-LLM metric co-design process. The co-design result is refreshingly honest: a randomly selected metric set achieves nearly the same solution quality (312.94 vs 313.07) but at 17x the pre-computation cost. So the human contribution is mostly computational triage, not magical feature selection. The authors basically say this themselves.\n\nThe biggest soft spot is the one the stress-test flags: there is no control with a fixed, sensible static bias. They compare against uniform random vectors, which rules out noise, but it does not rule out the possibility that any smooth non-random bias (say, L_i proportional to run length, or just the consensus alpha/beta values from Figure 8) would do the same. Without that control, the \"instance-driven\" component of the claim is not fully supported. The improvement could simply be that a non-random bias helps BRKGA. That is a real gap, and it weakens the central title claim.\n\nThere are also textual issues. The Phase 3 prompt misdescribes Normalized_length as length divided by total string length instead of l_i/l_max, and Opportunity as 1/(1+gap) instead of the fraction of the alphabet after the run. The data fed to the LLM uses the formal definitions, so it doesn't invalidate the performance numbers, but it complicates the interpretability analysis in Section 4.9. You'd want this cleaned up before publication.\n\nFinally, everything is in-house: synthetic uniform random strings, their own BRKGA baseline, their own STNWeb tool. There is no external benchmark or optimality gap, so the magnitude of the gains is uncalibrated. The authors do disclose that 57% of instance groups show no significant improvement, which is good practice.\n\nOverall, this is a serious paper. The methodology is careful and the claims in the abstract are mostly scoped to what the tables show. The missing static-bias control is the one thing I would push the authors to add before accepting the \"instance-driven\" label. It deserves a proper peer review, and I'd send it to a competent referee with a request for that experiment and a cleanup pass.","headline":"A careful, honest transfer of the OptiPattern idea to a string problem, with modest but real gains on complex instances; the 'instance-driven' part is less proven than the abstract claims because a simple static bias baseline is missing.","tokens_in":36615,"tokens_out":2504,"would_cite":true,"duration_ms":28388,"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":"An LLM that reads four per-run statistics can output a bias vector that improves a Biased Random-Key Genetic Algorithm on the Longest Run Subsequence problem, with the strongest gains on the most complex, large-alphabet instances.","keywords":["Large Language Models","Metaheuristics","Biased Random-Key Genetic Algorithm","Longest Run Subsequence","Instance-Driven Heuristic Bias","Combinatorial Optimization","Alpha-Beta Parameters"],"falsifier":"Run the exact pipeline but replace the LLM's alpha/beta output with a fixed consensus vector, such as high alpha on normalized length and opportunity with beta ideals at the medians reported for the top model, across the same 1,050 instances; if the fixed vector matches the LLM's solution quality, the instance-driven component is unsupported. Separately, rerun the benchmark on non-uniform, structured strings meant to mimic biological sequences; a disappearance of the gains would show the uniform random benchmark was carrying the effect.","tokens_in":35485,"feed_emoji":"🧬","tokens_out":7718,"duration_ms":77882,"temperature":0.7,"pith_summary":"The paper tries to show that a large language model can act as a cheap, one-shot advisor for a genetic algorithm on an NP-hard string problem. Instead of generating code, the LLM reads a small table of instance-derived statistics and returns eight numbers that bias the search before it starts. On 1,050 synthetic instances of the Longest Run Subsequence problem, the best hybrid beats the plain BRKGA on the hardest groups, and the paper argues the gain is not random noise because randomized bias vectors actually hurt. The practical payoff would be a zero-training way to inject instance awareness into metaheuristics.","feed_headline":"One LLM prompt steers a genetic solver past its baseline","feed_subtitle":"A single pre-search read of four metrics beats the baseline on the hardest large-alphabet instances","key_machinery":"The alpha-beta mechanism: four alpha weights (summing to one) and four beta ideals are fed into the prompt's sigmoid influence formula, producing a per-run desirability vector L. The modified decoder sorts runs by the product of random key and desirability, v_i · L_i, before greedy construction, so the LLM's reading of the feature matrix steers which runs come early. The four co-designed metrics form the feature matrix F the LLM analyzes; their extraction is deliberately separated from the LLM because direct LLM computation of features proved unreliable.","core_discovery":"The paper's central claim is that a single LLM call can turn four cheap per-run statistics — normalized length, opportunity, distance to the next same-character run, and global character frequency — into an instance-specific bias vector that improves BRKGA's final solution quality on the Longest Run Subsequence problem. The LLM is asked to set four alpha weights and four beta ideals in a sigmoid influence equation; converting those into a desirability per run and multiplying it into the random keys reorders the greedy decoder so promising runs are considered earlier. In the authors' experiments all four LLM hybrids beat the baseline overall, the top-performing open-weight hybrid ranks first","pith_inferences":["If the gain comes mainly from a smooth non-random bias rather than from instance-specific reading, a fixed hand-coded alpha/beta vector might match the LLM's result; the paper's ablation, which pits the LLM only against uniform random vectors, does not settle this.","The benchmark is uniform i.i.d. strings, so the stated bioinformatics motivation is untested; real DNA or protein strings have biased alphabets and long-range structure, where instance-driven bias could behave differently.","Because the top model's alpha/beta distributions for secondary metrics shift with instance scale, a cheap distilled model trained on its outputs might reproduce much of the benefit without per-instance API calls.","The multiplicative-key mechanism should transfer to other BRKGA-applied string problems with run-like structure, such as longest common subsequence variants, as long as the same static pre-analysis applies."],"forward_implications":["On the 1,050-instance benchmark, all four BRKGA+LLM hybrids rank above the plain BRKGA on average solution quality, and the top hybrid wins the global Friedman/Nemenyi comparison.","The top hybrid beats the baseline with statistical significance in 15 of 35 length-by-alphabet groups (42.86%), and the significant groups are mostly large-alphabet instances.","Random bias vectors — static or refreshed every generation — score below the standard BRKGA, so the LLM's fixed bias is doing more than adding noise.","Curated metrics precompute in about 8 seconds at n=5000 while a randomly chosen LLM-suggested set took about 300 seconds, with similar solution quality, making human curation a computational-efficiency filter.","Token usage grows super-linearly with instance length, from about 1.9k tokens at n=100 to 90k at n=5000, so API cost and latency scale with the feature-table size; the free small model remains viable but slower."],"supporting_citations":[{"why":"Foundational instance-driven heuristic bias framework; supplies the alpha-beta mechanism and the BRKGA-LLM integration that this paper adapts to LRS.","marker":"[35]"},{"why":"Provides the BRKGA decoder and baseline for the Longest Run Subsequence problem that the hybrid modifies.","marker":"[5]"},{"why":"Introduces the LRS problem and establishes its complexity, motivating a metaheuristic approach.","marker":"[15]"},{"why":"The irace tool used to tune all five algorithm variants, underwriting the fair-comparison claim.","marker":"[24]"},{"why":"Empirical evidence that LLMs cannot reliably compute optimization-feature values, justifying the paper's separation of metric extraction from LLM analysis.","marker":"[13]"},{"why":"STNWeb visualization tool used to obtain the behavioral evidence of exploration versus premature convergence.","marker":"[9]"},{"why":"Search trajectory network methodology that supports the behavioral interpretation of how the LLM changes search dynamics.","marker":"[29]"}],"fun_headline_variants":["LLM-crafted bias boosts genetic solver on hardest instances","One LLM read of four stats reorders search, beats baseline","LLM sets instance bias, BRKGA wins on complex cases","Instance-aware LLM heuristic beats classic genetic algorithm","Four cheap metrics, one LLM call, better LRSP solutions"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The central claim depends on an LLM being able to read a small table of per-run statistics and output alpha/beta weights that capture genuine instance structure; the paper's only control is uniform random bias, so the possibility that any fixed sensible bias would work just as well is left open.","fun_headline_variants_meta":{"raw":{"variants":["LLM-crafted bias boosts genetic solver on hardest instances","One LLM read of four stats reorders search, beats baseline","LLM sets instance bias, BRKGA wins on complex cases","Instance-aware LLM heuristic beats classic genetic algorithm","Four cheap metrics, one LLM call, better LRSP solutions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000485,"raw_usage":{"total_tokens":2237,"prompt_tokens":757,"completion_tokens":1480,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":501,"completion_tokens_details":{"reasoning_tokens":1409}},"tokens_in":501,"tokens_out":1480,"duration_ms":11470,"temperature":1.0,"reasoning_tokens":1409,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T05:25:45.786914+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the exact pipeline but replace the LLM's alpha/beta output with a fixed consensus vector, such as high alpha on normalized length and opportunity with beta ideals at the medians reported for the top model, across the same 1,050 instances; if the fixed vector matches the LLM's solution quality, the instance-driven component is unsupported. Separately, rerun the benchmark on non-uniform, structured strings meant to mimic biological sequences; a disappearance of the gains would show the uniform random benchmark was carrying the effect.","supporting_citations":[{"cited_title":"Metaheuristics and large language models join forces: Toward an integrated optimization approach","cited_arxiv_id":null,"evidence_quote":"Foundational instance-driven heuristic bias framework; supplies the alpha-beta mechanism and the BRKGA-LLM integration that this paper adapts to LRS."},{"cited_title":"A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem","cited_arxiv_id":"2508.14020","evidence_quote":"Provides the BRKGA decoder and baseline for the Longest Run Subsequence problem that the hybrid modifies."},{"cited_title":"The Longest Run Subsequence Problem: Further Complexity Results","cited_arxiv_id":null,"evidence_quote":"Introduces the LRS problem and establishes its complexity, motivating a metaheuristic approach."},{"cited_title":"The irace package: Iterated racing for automatic algorithm configuration","cited_arxiv_id":null,"evidence_quote":"The irace tool used to tune all five algorithm variants, underwriting the fair-comparison claim."},{"cited_title":"Probing LLMs on Optimization Problems: Can They Recall and Interpret Problem Features? In Pablo García-Sánchez, Emma Hart, and Sarah L","cited_arxiv_id":null,"evidence_quote":"Empirical evidence that LLMs cannot reliably compute optimization-feature values, justifying the paper's separation of metric extraction from LLM analysis."},{"cited_title":"STNWeb: A new visualization tool for analyzing op- timization algorithms","cited_arxiv_id":null,"evidence_quote":"STNWeb visualization tool used to obtain the behavioral evidence of exploration versus premature convergence."},{"cited_title":"Malan, and Christian Blum","cited_arxiv_id":null,"evidence_quote":"Search trajectory network methodology that supports the behavioral interpretation of how the LLM changes search dynamics."}],"review_version":1}