{"id":"c2bc04c1-be98-48f4-a861-b07e7b797100","arxiv_id":"2505.21991","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"LGP fitness expectations can be studied through fitness supremums that grow linearly with instruction editing distance, which explains bloat and supports larger freemut mutation steps.","lead":"A theoretical study of linear genetic programming models fitness through a worst-case 'fitness supremum' tied to instruction editing distance, and uses the model to explain program bloat and mutation step-size choices. The core inequality is simple and correct, but the proof chain from supremums to expected fitness rests on an unproven distribution-similarity assumption.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The bridge from fitness supremum to expected fitness is unproven: Eq. (5) is never verified, and Theorem 4's inference from 'similar probabilities plus larger support' to a larger expectation does not follow logically.","rationale":"The reader's weakest_assumption correctly identifies the unproven similarity of fitness distributions, specifically Eq. (5) and the unsupported assertion in Theorem 3. I agree that this is the load-bearing gap. My read goes slightly further: even if Eq. (5) and Theorem 3 were fully proved, the paper's step from 'similar probabilities' and 'larger support' to 'expectation increases' is not a valid mathematical inference. For example, a distribution with most probability mass shifting to δ=0 while a tiny amount appears at a larger maximum δ would satisfy a qualitative similarity bound yet have a smaller mean. Theorem 4's proof uses exactly this unsupported move, so the bloat and hitting-time conclusions inherit the gap. That said, Theorem 1 is a clean Lipschitz-style bound, and the empirical trends in Sections 3.2, 4.3, and 5.1 are consistent with the qualitative direction of the claims. The paper is therefore not a rejection candidate; it is a plausible framework that needs either a proof of Eq. (5) under stated assumptions, a direct proof of stochastic dominance of fitness with distance, or empirical validation of the monotonicity E[f | δ=d] itself. The existing CONDITIONAL verdict remains appropriate, which is why I recommend no change.","tokens_in":24984,"tokens_out":7211,"duration_ms":82831,"concrete_test":"Perform exhaustive enumeration for a minimal LGP instance (e.g., γ=2 registers, γ_out=1, |I|=n=8 instructions, target program of length m*=2, max length L=6) and compute the exact quantities in Eq. (5), Theorem 2's Eq. (6), Theorem 3's normalized counts ||P^{δ=d}_m||/n^m, and E[f | δ=d] as well as E[δ | P_m]. If Eq. (5) fails for some d, or E[f | δ=d] is non-monotone in d, or E[δ | P_{m+1}] ≤ E[δ | P_m] for any m, the central bridge is falsified. Independently, construct two toy distributions satisfying Theorem 3's similarity bound with E[δ | m+1] < E[δ | m]; such a pair would show the inference in Theorem 4 is invalid even before enumeration.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central chain is: Theorem 1 gives an upper bound |f(ρ)−f(ρ*)| ≤ B(δ); assuming inf f = 0, Eq. (4) labels B(δ) the fitness supremum and notes that B increases with δ. To infer that E[f] increases with δ, the paper inserts Theorem 2. Two things are missing. First, Eq. (5) is an assumption, not a proved property: it constrains how the conditional probability of each fitness value changes when the ball of radius d grows to d+1. The paper never verifies Eq. (5) for any concrete LGP search space and fitness function, and the remark that individual v-probabilities are 'small enough' does not imply the ratio inequality in Eq. (5). Theorem 3 concerns the distribution of δ*, not the distribution of fitness values; its proof is a recurrence plus an assertion that α1 and α2 are negligible because n is combinatorial, but the recurrence is not derived from the operator definitions and the bound is not established for all d. Second, even granting Eq. (5) and Theorem 3, the conclusion of Theorem 4 does not follow. Eq. (9) compares sums of d·(||P^{δ=d}_m||/n^m). 'More possible d' in layer m+1 and 'similar' normalized probabilities do not imply the new expectation is larger: additional mass at large d can be arbitrarily small, and mass at small d can increase. A single distribution pair satisfying the stated similarity bound with decreasing mean is a counterexample to the proof step. Since Theorem 4, Corollary 4.1, and the bloat explanation all rest on this unproven inference, the paper's central claim—that fitness expectation increases with editing distance and program size—is not established by the given mathematics.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a theoretical link between fitness values and LGP search spaces via a 'fitness supremum' defined as an upper bound on the fitness gap, claimed to be linear in the instruction editing distance from an optimal program. Theorems 1–4 aim to show that smaller editing distance implies smaller fitness supremum and that similar fitness distributions across editing distances imply that expected fitness increases with editing distance and program size; these conclusions are then used to explain bloat and the minimum hitting time of freemut. The empirical sections compare instruction sets, program sizes, and variation step sizes on symbolic regression benchmarks. The main result that is cleanly supported is Theorem 1, a Lipschitz-style bound. The rest of the theoretical chain, however, rests on unverified assumptions and an invalid inference from similar distributions to monotone expectations.","tokens_in":25471,"tokens_out":4213,"duration_ms":46208,"significance":"If the full chain of claims were established, the proposed framework would be a valuable alternative to problem-specific runtime analyses of GP: it would connect fitness to genotype structure through a parameter-free bound and would yield explanations of bloat and hitting time without constructing special fitness functions. The paper also has the virtue of stating a concrete, falsifiable bound in Theorem 1 and of performing external empirical checks rather than fitting constants to data. Those strengths are real but conditional. The central bridge from the supremum bound to expected fitness is not proven: the similarity condition in Eq. (5) is assumed and never verified for any concrete LGP search space, and Theorem 4's inference from 'more possible d' and 'similar normalized probabilities' to a larger expectation is logically invalid. Consequently, the bloat and hitting-time explanations rest on an unsupported step. The paper's contribution as it stands is therefore a potentially useful framework with a substantial gap between what is stated in the abstract and what is proved.","major_comments":[{"comment":"Eq. (4) defines the 'fitness supremum' sup f(ρ) as the upper bound from Theorem 1, not as the actual supremum of the fitness function over programs at a given editing distance. Since the bound is written as a linear function of δ*(ρ), the sentence 'a smaller (larger) editing distance from the optimal program implies a smaller (larger) fitness supremum' is a restatement of the bound, not an independent property. The real claim, that the expectation of fitness increases with editing distance, does not follow from Eq. (4) alone; it requires the distributional similarity asserted later.","section":"Section 3.1, Eq. (4) and subsequent paragraph"},{"comment":"Eq. (5) is an assumption, not a proved condition, and the manuscript never verifies it for any concrete LGP search space, instruction set, or fitness function. The remark that individual probabilities Pr(f(ρ)=v | δ≤d) are 'small enough' does not imply the ratio inequality in Eq. (5). Moreover, Theorem 2's conclusion is only a bound on the difference of conditional probabilities; it says nothing about the ordering of expectations. Since the paper uses Theorem 2 to bridge from 'supremum grows with δ' to 'expected fitness grows with δ', this gap is load-bearing.","section":"Theorem 2, Eq. (5)"},{"comment":"The recurrence ||P^{δ=d}_{m+1}|| = ||P^{δ=d}_m||Ω(m,m+1) + ||P^{δ=d±1}_m||Λ(m,m+1) is stated without derivation from the definitions of P^{δ=d}_m, Ω, and Λ. The notation δ=d±1 conflates two different contributions, and the coefficients α1 and α2 in the subsequent line are not defined. The claim that |α1||P^{δ=d}_m|| + α2||P^{δ=d±1}_m|| is 'much smaller than n^m' because n is combinatorial is not quantified and is not shown to hold for all d and m. Thus the theorem's conclusion of ϵ-similarity is not established, and Theorem 4 relies directly on it.","section":"Theorem 3 and its proof"},{"comment":"The proof infers E[δ*|ρ∈P_{m+1}] − E[δ*|ρ∈P_m] > 0 from two facts: the support of δ* widens for larger m and the normalized probabilities ||P^{δ*=d}_m||/n^m and ||P^{δ*=d}_{m+1}||/n^{m+1} are 'similar'. This inference is invalid. A growing support does not force a larger mean if probability mass moves toward smaller d, and the similarity bound stated in Theorem 3 does not impose a lower bound on the mass at the new largest d. There exist two distributions on {1,...,k} and {1,...,k+1} with arbitrarily close normalized probabilities on the common support yet with the second distribution having a strictly smaller mean. Hence Eq. (9) does not prove the claim, and Corollary 4.1 and the bloat explanation inherit this gap.","section":"Theorem 4, Eq. (9) and proof"},{"comment":"The proof of Theorem 5 substitutes upper bounds on offspring counts from Lemmas 5 and 6 into Eq. (11) and divides by the total number of offspring. An upper bound on the numerator combined with the true denominator does not yield an upper bound on the expectation; one would need the same normalization in the bound or a separate argument. The truncation remark after Theorem 5 adjusts the formula ad hoc and is not derived. Additionally, Lemma 6 states ||P^{Δδ*=i}(ρ,o−u)|| ≤ (|ρ| choose u), which is the total number of deletion offspring regardless of i, so it cannot by itself bound the constructive moving rate. These issues affect the minimum hitting time conclusions.","section":"Section 5, Theorem 5 and Lemmas 5–6"}],"minor_comments":[{"comment":"The definition of Δf(Ψ) uses a ratio with ||s−s*|| in the denominator; the case of identical semantics should be handled explicitly to avoid division by zero.","section":"Section 2.4, Definition 5"},{"comment":"The text lists the benchmark problem 'CCN' while Table 3 uses 'CNN'; the naming should be made consistent.","section":"Section 3.2, Table 3"},{"comment":"The symbol δ* is introduced as distance to an optimal program, but Theorem 1 and Definition 6 use δρ,ρ* relative to a single ρ*; the paper should clarify whether the bound applies to the closest optimal program or to an arbitrary fixed one.","section":"Notation throughout"},{"comment":"The empirical results in Figures 4, 5, and 9 show correlations consistent with the claims, but they do not measure the distributions P^{δ*=d}_m or verify the similarity condition Eq. (5), so they are not a test of the proposed mechanism itself.","section":"Section 4.3 and Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The paper's abstract and conclusions state the bridge as established, but the proof chain is incomplete: Eq. (5) is an unverified assumption, Theorem 3 is not derived, and Theorem 4's inference is invalid. The empirical sections are suggestive but do not test the theoretical mechanism directly. I recommend major revision, with the expectation that the authors either prove the similarity conditions for concrete search spaces or substantially weaken the claims to clearly conditional statements. If the missing inference cannot be repaired, the paper should be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this paper has one solid theorem, a genuinely new way to look at LGP fitness landscapes, and a central bridge that is not actually built. The fitness-supremum perspective is the real contribution. Theorem 1 is a clean Lipschitz-style bound showing that the fitness gap to the optimum is bounded by a linear function of instruction editing distance. The paper also does well to connect this to the 'exploding lasagna' counting model and to test the qualitative predictions empirically. The experiments on instruction sets and freemut step size are consistent with the model's weak form, and the practical recommendations—start small, mutate a handful of instructions—are sensible and supported by the data.\n\nThe soft spot is exactly where the title says the bridge is: the step from fitness supremum to expected fitness. Theorem 2's Eq. (5) is an assumption, not a proved property; the remark that probabilities are 'small enough' does not imply the ratio inequality. Theorem 3's proof is a recurrence plus an assertion that the alpha terms are negligible because n is combinatorial. That is not a derivation, and the bound is not established for all d. The decisive problem is Theorem 4: even granting Eq. (5) and Theorem 3, 'more possible d values plus similar normalized probabilities' does not imply a larger expectation. Additional mass at large d can be arbitrarily small, and mass at small d can grow. The proof step is logically invalid, and since Theorem 4, Corollary 4.1, and the bloat explanation all rest on it, the central claim is not established by the given mathematics.\n\nThe authors are transparent about the assumptions—Eq. (5) is stated, and the remark concedes it only holds for some fitness functions—but they never verify it for any concrete LGP setting. That is a load-bearing gap, not a cosmetic one.\n\nWho is this for? Researchers in GP theory who want a new way to think about genotype-fitness maps. They will find the supremum idea worth engaging with, but they should not treat the expectation results as proven. I would send it to a serious referee with a clear request to focus on Theorem 4 and the verification of Eq. (5). With that fixed, the paper could be publishable; as it stands, the headline conclusions are conditional on an unproven premise.","headline":"A fresh and testable fitness-supremum framework for LGP, undermined by an unproven step from supremum to expected fitness.","tokens_in":25879,"tokens_out":2552,"would_cite":false,"duration_ms":24448,"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":"In linear genetic programming, the worst-case fitness gap to an optimal program grows linearly with the number of instructions that differ from it, and that link explains bloat and guides mutation sizing.","keywords":["genetic programming","linear genetic programming","fitness supremum","instruction editing distance","bloat effect","minimum hitting time","freemut"],"falsifier":"Enumerate a small LGP instance—say two registers, a handful of instructions, and a simple regression target—and compute, for every editing distance $d$, the empirical fitness distribution. If the supremum increases with $d$ but the mean fitness does not, or if the conditional distributions violate equation (5), the central bridge between Theorem 1 and Theorem 4 is falsified; this check can be done exactly for small instruction sets.","tokens_in":24759,"feed_emoji":"🧬","tokens_out":7597,"duration_ms":59761,"temperature":0.7,"pith_summary":"Linear genetic programming (LGP) is hard to analyze theoretically because fitness depends on program execution in a way that resists simple genotype-to-fitness maps. This paper proposes an upper-bound bridge: the fitness supremum of a program—the largest possible fitness gap to an optimal program—is a linear function of its instruction editing distance from that optimal program. Assuming the distribution of fitness values is similar across editing distances, this linear supremum makes expected fitness monotone in editing distance, and hence in program size. The paper uses that to explain why LGP programs grow beyond what is needed (bloat) and to estimate the minimum hitting time of the freemut operator, predicting that small programs and multi-instruction mutations improve search. The value, if the step from supremum to expectation holds, is a problem-independent way to connect LGP fitness values with search-space geometry.","feed_headline":"Editing distance predicts fitness in LGP","feed_subtitle":"A linear fitness-supremum bound explains why programs bloat and why larger mutations can improve search.","key_machinery":"The central object is the fitness supremum identity of equation (4), $\\sup f(\\rho)=\\Delta_f(\\Psi)\\min\\{(\\Delta(\\mathcal{I}_2,\\Psi)-\\Delta(\\mathcal{I}^*,\\Psi))\\delta^*(\\rho)+\\Delta(\\mathcal{I}^*,\\Psi)L,\\Delta_\\Psi\\}$, which turns the weak causality between genotype and fitness into a linear relationship with a single combinatorial quantity, the instruction editing distance $\\delta^*(\\rho)$. The supporting 'exploding lasagna model' organizes the search space into layers of constant program size $m$, each holding $n^m$ programs, with the neutral and non-neutral bloating factors $\\Omega(m_1,m_2)$ and $\\Lambda(m_1,m_2)$ bounding how adding or removing instructions multiplies the number of programs at a given editing distance. The bridge from supremum to expectation is the assumption that the fraction of programs with $\\delta^*=d$ is nearly independent of size $m$ (Theorem 3), which lets the linear supremum bound control the expected fitness.","core_discovery":"The paper's central claim is Theorem 1: in an LGP search space with instruction set $\\mathcal{I}$, maximum program length $L$, optimal program set $\\mathcal{P}^*$, and fitness function $f$, the fitness gap between any program $\\rho$ and any optimal program $\\rho^*$ satisfies $$|f(\\rho)-f(\\rho^*)|<= \\Delta_f(\\Psi)\\min\\{(\\$\\Delta$(\\mathcal{I}_2,\\Psi)-\\$\\Delta$(\\mathcal{I}^*,\\Psi))\\delta^*(\\rho)+\\$\\Delta$(\\mathcal{I}^*,\\Psi)L,\\ \\Delta_\\Psi\\},$$ where $\\delta^*(\\rho)$ is the instruction editing distance from $\\rho$ to the nearest optimal program. Setting the fitness infimum to $f(\\rho^*)=0$ turns this into equation (4), the fitness supremum $\\sup f(\\rho)$, which is linear in $\\delta^*(\\rho)$ because $\\Delta(\\mathcal{I}_2,\\Psi)\\ge\\Delta(\\mathcal{I}^*,\\Psi)$. Theorems 2 and 3 then argue that fitness probabilities are similar across editing distances, so the growth of the supremum implies growth of the expected fitness; Theorem 4 states this expectation increases with program size, Corollary 4.1 derives the bloat effect, and Theorem 5 gives an upper bound on the constructive moving rate of freemut that favors larger variation step sizes.","pith_inferences":["If the supremum-to-expectation step is valid, the same editing-distance analysis may extend to other GP representations where a suitable distance metric exists (for example, tree edit distance), not just linear programs.","The theory suggests a testable prediction: on a fixed regression problem, the empirical distribution of fitness at a given editing distance should be roughly independent of that distance; if it is not, the bloat explanation would need revision.","The recommendation of large variation step sizes is bounded by a truncation effect: once the constructive-moving-rate bound saturates, further increases in step size no longer help, which the experiments already hint at for $u>10$.","One could derive a direct estimator of expected fitness from the supremum formula and compare it against random program sampling as a stronger validation than the mean-fitness curves."],"forward_implications":["Smaller instruction editing distance to an optimal program implies a smaller fitness supremum, so search can be guided by editing distance rather than by problem-specific fitness functions.","Expected fitness increases with program size, theoretically justifying the common practice of initializing LGP with small programs.","Bloat occurs because, at a fixed editing distance, adding instructions is more likely than removing them to reduce or maintain distance to an optimal program.","For freemut, the upper bound on constructive moving rate increases with variation step size $u$ within a small range, so mutating multiple instructions per generation can improve the minimum hitting time.","The minimum hitting time to reach an $\\epsilon$-neighborhood of the optimal program is shorter when the program size is kept small."],"supporting_citations":[{"why":"Supplies the LGP representation, intron/exon structure, register-based instructions, and the freemut operator that the theory models.","marker":"Brameier and Banzhaf (2007)"},{"why":"Establishes freemut as the standard simple operator for studying LGP evolution, which the minimum-hitting-time analysis relies on.","marker":"Hu and Banzhaf (2018)"},{"why":"Provides the combinatorics of neutral spaces that Lemma 3's bloating factor bounds build on.","marker":"Banzhaf et al. (2024)"},{"why":"The prior quantitative bloat model whose restrictive assumptions this paper's bloat explanation extends.","marker":"Freitag McPhee and Poli (2001)"},{"why":"Representative problem-specific runtime analysis (ORDER/MAJORITY) that motivates the need for a problem-independent fitness model.","marker":"Durrett et al. (2011)"},{"why":"Provides the LGP parameter settings used in the paper's empirical verification experiments.","marker":"Huang et al. (2022a)"}],"fun_headline_variants":["Fitness supremum scales with edit distance in LGP","LGP bloat explained by linear fitness bound","Edit distance predicts LGP fitness and bloat","Why larger mutations speed up LGP search","Fitness ceiling grows with edit distance in LGP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the distribution of fitness values is similar across different editing distances (and that the fraction of programs at a given editing distance is roughly independent of program size), so that a larger fitness supremum guarantees a larger expected fitness; if this similarity fails, the supremum bound does not transfer to expectations.","fun_headline_variants_meta":{"raw":{"variants":["Fitness supremum scales with edit distance in LGP","LGP bloat explained by linear fitness bound","Edit distance predicts LGP fitness and bloat","Why larger mutations speed up LGP search","Fitness ceiling grows with edit distance in LGP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000241,"raw_usage":{"total_tokens":1568,"prompt_tokens":1038,"completion_tokens":530,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":654,"completion_tokens_details":{"reasoning_tokens":457}},"tokens_in":654,"tokens_out":530,"duration_ms":4973,"temperature":1.0,"reasoning_tokens":457,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:19:05.410862+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate a small LGP instance—say two registers, a handful of instructions, and a simple regression target—and compute, for every editing distance $d$, the empirical fitness distribution. If the supremum increases with $d$ but the mean fitness does not, or if the conditional distributions violate equation (5), the central bridge between Theorem 1 and Theorem 4 is falsified; this check can be done exactly for small instruction sets.","supporting_citations":[{"cited_title":"and Banzhaf, W","cited_arxiv_id":null,"evidence_quote":"Supplies the LGP representation, intron/exon structure, register-based instructions, and the freemut operator that the theory models."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the combinatorics of neutral spaces that Lemma 3's bloating factor bounds build on."},{"cited_title":"and Poli, R","cited_arxiv_id":null,"evidence_quote":"The prior quantitative bloat model whose restrictive assumptions this paper's bloat explanation extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Representative problem-specific runtime analysis (ORDER/MAJORITY) that motivates the need for a problem-independent fitness model."}],"review_version":1}