{"id":"14c40f51-e924-484e-805b-db6a3dec2084","arxiv_id":"2412.17330","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"EcoSearch is a best-first bottom-up search algorithm that, assuming integer costs, has constant delay between output programs, and it outperforms Heap Search and Bee Search in two classic synthesis domains.","lead":"EcoSearch is a new algorithm for program synthesis that produces candidate programs at a constant rate, without slowing down as the search proceeds. It matters because enumerating candidate programs is a main bottleneck in many synthesis tools, so a constant-delay search could make them faster on larger problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 10 can return an uncomputed GeneratedX set: line 28 writes a peeked cost into Index2CostXi before that cost is generated, so line 6 later returns an undefined bucket on a simple grammar.","rationale":"The reader's weakest assumption was that EcoSearch enumerates in non-decreasing cost order without proof. My stress test found a sharper, concrete violation: as printed, Algorithm 10 can return from line 7 before the corresponding GeneratedX bucket is initialized, because line 28 writes Index2CostXi as a prediction. This is not a cosmetic issue; the pseudocode is the specification of the algorithm, and the central theorem is about this algorithm. The bug is localized and likely fixable, for example by keeping a separate prediction map or by checking GeneratedX membership before the early return, so a conditional accept remains appropriate. The verdict therefore stays conditional, matching the reader, but the stated condition should explicitly require correcting Algorithm 10 and proving the queue invariant. I partially agree with the reader because the order invariant is indeed unproven, yet the more urgent problem is that the algorithm's own data structures are inconsistent.","tokens_in":16596,"tokens_out":17111,"duration_ms":177362,"concrete_test":"Implement Algorithm 10 exactly as printed in Section C and run it on the grammar S -> f(A), A -> a | b | g(A) with the integer costs above; observe the KeyError when Output(S,1) calls Output(A,1). As a broader check, for random small CFGs with integer costs, compare the entire output stream of Algorithm 10 against brute-force cost-sorted enumeration up to a fixed cost bound; any missing, duplicate, or out-of-order program refutes the best-first/constant-delay claim. Also inspect the released implementation to see whether it adds a guard such as 'Index2CostX[ℓ] in GeneratedX' before the early return at line 7.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section C, Algorithm 10 violates its own data-structure invariant. Index2CostX is defined as the list of costs of generated programs, but line 28 assigns Index2CostXi[n'i] <- cost(peek(QueueXi)) as a predicted next cost, without adding any program of that cost to GeneratedXi. Line 6 then tests only 'Index2CostX[ℓ] is defined' and returns GeneratedX[Index2CostX[ℓ]], which may not exist. Concretely, take the grammar S -> f(A) with cost 1, A -> a with cost 1, A -> b with cost 100, A -> g(A) with cost 1. After Output(S,0), the update at line 28 predicts Index2CostA[1] = 2, the cost of g(a), but GeneratedA[2] has not been created. When Output(S,1) calls Output(A,1), line 6 returns GeneratedA[2], producing a KeyError. Thus the published algorithm is not a well-defined enumerator; the best-first-order invariant and Theorem 1 are unsupported as stated. This is an internal inconsistency, not merely a missing proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces EcoSearch, a bottom-up best-first search algorithm for cost-guided program synthesis with pre-generation cost functions. The main theoretical contribution is a proof (Theorem 1) that, under integer costs, EcoSearch has constant delay: the time between generating two programs is bounded by a constant. The algorithm builds on the cost-tuple representation of Bee Search and the per-non-terminal structure of Heap Search, adds a frugal expansion rule, and uses bucket queues to achieve constant-time priority operations. The paper reports experiments on FlashFill and DeepCoder DSLs in which EcoSearch outperforms Heap Search and Bee Search, including a variant without bucketing. The appendix contains the full pseudocode and proofs of two lemmas bounding the cost gap between a program and its successor.","tokens_in":16889,"tokens_out":13303,"duration_ms":108146,"significance":"If the constant-delay result is correct, it is a significant theoretical improvement over prior best-first search algorithms for this setting, which have logarithmic delay. The bucketing technique and the per-non-terminal data structures are natural and potentially useful beyond program synthesis. The experimental results, if reproducible, suggest practical gains. However, the significance is conditional: the algorithm as published contains a correctness bug (see Major Comment 1), the proof of Theorem 1 depends on an unproven imported lemma, and the best-first ordering invariant is not established. These issues must be resolved before the contribution can be assessed.","major_comments":[{"comment":"The algorithm violates its own data-structure invariant. Index2CostX is defined in Section 3.2 as the list of costs of generated programs, but line 28 assigns Index2CostXi[n'i] <- cost(peek(QueueXi)) before any program of that cost has been generated. A later call to Output(Xi, ℓ) with ℓ equal to that index will see the index defined and return GeneratedX[Index2CostX[ℓ]], which may not exist. Concretely, for the grammar S -> f(A) (cost 1), A -> a (cost 1), A -> b (cost 100), A -> g(A) (cost 1), after Output(S,0) the algorithm sets Index2CostA[1] = 2 (the cost of g(a)) but GeneratedA[2] is never created. Then Output(S,1) calls Output(A,1), which at line 6 returns GeneratedA[2], producing a KeyError. Thus EcoSearch as published is not a well-defined enumerator; the constant-delay theorem (Theorem 1) is unsupported.","section":"Section C, Algorithm 10, lines 27–28"},{"comment":"The proof of Theorem 1 depends on the frugal expansion property, which bounds the number of recursive calls per output by the number of non-terminals. This property is imported from the authors' own prior work (Fijalkow et al. 2022, arXiv appendix) and is not stated or proved here; the text explicitly says 'we only give an overview.' Since this is a load-bearing step in the constant-delay argument, the paper is not self-contained. The authors must state the property as a lemma and provide a complete proof or a precise reference to a published version that includes it.","section":"Section 3.3"},{"comment":"The best-first enumeration order invariant is asserted but not proven. The paper never proves that Output(X,ℓ) returns exactly the programs of the ℓ-smallest cost for X, nor that the queue update in Algorithm 10 lines 23–30 preserves the correctness of cost tuples after the predicted-cost assignment of line 28. The worked example in Section C, step 6, actually contradicts the pseudocode: it describes Output(I,1) as popping (r6,∅) and generating 1, but under Algorithm 10 line 6 would immediately return GeneratedI[3.3], which does not exist, because Index2CostI[1] was already set to 3.3 in step 5. The delay analysis has no meaning if the output order is not the cost order.","section":"Section 3 and Section C, worked example"},{"comment":"The proof of Lemma 1 is not rigorous. The construction of the finite set F and the step 'as long as condition (*) is not satisfied, there is always a child with a successor because there is a duplicated non-terminal on some path, ensuring that the process is sound' needs a formal argument; it is unclear why the process always finds a node n whose subprogram is in F. Lemma 2's proof is also too terse: it does not handle the moment when queues are initialized, nor does it account for the predicted-cost entries introduced by line 28, which can insert incorrect costs into the queues, as demonstrated in Major Comment 1.","section":"Appendix A, Lemmas 1 and 2"},{"comment":"The experimental claims are hard to verify from the text. The figures are not included in the manuscript, and the abstract's statement that EcoSearch 'solves twice as many tasks in the same amount of time' is not supported by any numeric comparison in the body. Also, the theoretical result assumes integer costs, but the experiments discretize real-valued costs (log-space discretization to 10^-5 and bucket size 20); the paper does not explain how the constant-delay guarantee degrades under this discretization.","section":"Section 4"}],"minor_comments":[{"comment":"Step 3 of the worked example calls ComputeSuccessor(W, I), but W is a string program generated by S, not an integer program; this appears to be a typo for ComputeSuccessor(W, S).","section":"Section B.2, Heap Search example"},{"comment":"The definition of pre-generation cost functions allows arbitrary positive real costs, while Theorem 1 assumes integer costs; the paper should clarify whether the constant-delay result extends to arbitrary real costs or requires rounding.","section":"Section 2.3 and Theorem 1"},{"comment":"The reference for the frugal expansion analysis is to an arXiv version of Fijalkow et al. (2022) (Section C.2 Lemma 2); the published AAAI version may not include that appendix. Please provide a stable citation or a self-contained proof.","section":"Section 3.3, reference"},{"comment":"The paper uses both 'Eco Search' and 'EcoSearch' inconsistently; the title and abstract use 'EcoSearch' while the body often writes 'Eco Search'. Please standardize.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The correctness bug in Algorithm 10 is the most serious issue and should be the primary focus of the revision. The authors should also be aware that the constant-delay claim may require a more careful treatment of predicted-cost entries; a separate data structure for predicted costs might restore the invariant. Given the paper's experimental promise, I recommend major revision rather than reject, but the revised version must include a corrected algorithm, a self-contained proof of Theorem 1, and a rigorous treatment of the best-first ordering invariant."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about this one. The constant-delay result, if it held, would be a real step forward for cost-guided program synthesis; prior best-first algorithms had logarithmic delay. But as written, Theorem 1 is not supported: Algorithm 10 in Appendix C has a concrete bug. Line 28 assigns a predicted next cost to Index2CostXi[n'i] before any program of that cost has been generated. Line 6 later checks only whether Index2CostX[ℓ] is defined and then reads GeneratedX at that cost, which may not exist. The stress-test example (S -> f(A), with A -> a, b, g(A)) triggers a KeyError on the second call to Output(S,1). That is not a missing proof; the algorithm as printed is not a well-defined enumerator.\n\nThe core ideas are not bad. Combining cost tuples from Bee Search with per-nonterminal structures from Heap Search is natural, and the bucketing analysis (Lemma 1) is proven. The experiments on FlashFill and DeepCoder show EcoSearch consistently ahead of Bee Search, by about 1.3x to 1.8x in time-to-same-task-count, and the code and seeds are public. The abstract's \"twice as many tasks\" overstates what the figures show, but the empirical work is honest in its setup.\n\nThe other soft spots are real but secondary. The frugal expansion lemma is imported from Fijalkow et al. 2022 without proof, so the constant-delay argument rests on an unverified citation. The paper asserts, but does not prove, that programs are output in non-decreasing cost order; if that invariant fails, the 'best-first' and delay claims lose their meaning. And the theoretical result needs integer costs; the discretization is an extra parameter.\n\nMy take: a promising draft, not a valid paper. The bug looks fixable — separate the 'expected next cost' from the list of generated costs, or create the Generated bucket at prediction time — but that changes the invariant and the proof. The right move for a venue is to send it to referees anyway, because the question is important and the approach is plausible, but the expected outcome should be major revision, not acceptance. For my own work, I would not cite the constant-delay claim yet.","headline":"The constant-delay claim is not supported as written—Algorithm 10 has a concrete bug where predicted costs are written into Index2Cost before programs of that cost exist—but the underlying idea is promising and worth a serious revision.","tokens_in":17382,"tokens_out":5426,"would_cite":false,"duration_ms":48791,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"EcoSearch claims the first constant-delay best-first search for program synthesis: under integer costs, the time between consecutive output programs stays bounded, and the algorithm solves more benchmark synthesis tasks in the same time…","keywords":["program synthesis","best-first search","constant delay","cost-guided combinatorial search","pre-generation cost function","bottom-up enumeration","bucket queue","DeepCoder"],"falsifier":"Run EcoSearch on a finite DSL with integer costs and record the CPU time between consecutive generated programs; if the average or worst-case inter-output gap grows as the number of outputs increases, instead of staying bounded, the constant-delay theorem is false. A cheaper check is to inspect the output sequence for any program emitted after a higher-cost program but carrying a lower cost, which would show the best-first invariant is violated.","tokens_in":16407,"feed_emoji":"⚡","tokens_out":7350,"duration_ms":62564,"temperature":0.7,"pith_summary":"Program-synthesis tools that search by a learned or probabilistic cost function have a scalability problem: best-first search correctly enumerates programs, but every existing algorithm slows down as it goes because its frontier of candidate programs grows. EcoSearch claims to remove that slowdown. It is, the paper argues, the first constant-delay best-first search algorithm for pre-generation cost functions: the compute needed between one output program and the next is bounded by a constant rather than growing logarithmically. Under integer costs the paper proves this bound, and experiments on string and integer-list synthesis show EcoSearch solving more tasks in the same wall-clock time than its predecessors. If the bound holds, cost-guided enumerative synthesis becomes genuinely scalable in the number of programs examined.","feed_headline":"First constant-delay search for program synthesis","feed_subtitle":"EcoSearch bounds the compute between generated programs, solving more synthesis tasks in less time.","key_machinery":"The engine is the cost tuple: a pair $(r, \\mathbf n)$ where $r$ is a grammar rule $X \\to f(X_1, \\dots, X_k)$ and $\\mathbf n$ says to take, for each argument, the program at position $n_i$ in the cost-ordered list of programs already generated for $X_i$. Such a tuple lazily stands for a whole set of programs. EcoSearch keeps one cost-ordered index and one bucket queue per non-terminal, the per-non-terminal data structure, and it uses frugal expansion so that an output call triggers recursive uncached work for at most one index per non-terminal. Two lemmas bound, by a constant $M$, the gap between the minimal and maximal costs living in any queue at any time; this is what licenses replacing a general priority queue with a bucket queue, an array of $M$ lists plus a rotating pointer, giving $O(1)$ push and pop operations. With integer costs, that yields the constant-delay theorem.","core_discovery":"EcoSearch is claimed to be the first best-first search algorithm with constant delay for pre-generation cost functions. For integer costs, the amount of compute between outputting successive programs is bounded by a constant independent of how many programs have already been emitted, in contrast with the logarithmic delay of previous best-first algorithms. The algorithm is bottom-up, so it retains compatibility with observational equivalence pruning, and on FlashFill string tasks and DeepCoder integer-list tasks it solves more tasks than previous best-first algorithms within the same time budget.","pith_inferences":["Editorial inference: if the constant-delay guarantee survives non-integer or rounded costs, best-first search becomes a viable anytime algorithm for interactive synthesis, where per-query latency matters as much as total throughput.","Editorial inference: the bounded-gap lemmas rely on finitely many irreducible programs, so grammars with many non-terminals or deep recursion could make the practical constant $M$ large even though the asymptotic claim holds.","Editorial inference: EcoSearch's low per-output overhead could make it attractive as the enumeration backend for LLM-guided synthesis, since more programs could be explored per LLM call or per refinement loop."],"forward_implications":["Generating the first $n$ programs under a pre-generation cost function now costs $O(n)$ total work instead of $O(n \\log n)$, for integer costs; the per-output cost does not compound.","Because delay no longer grows, EcoSearch can keep enumerating indefinitely without the frontier slowdown that makes previous best-first algorithms impractical on large grammars.","Bottom-up synthesis techniques such as observational equivalence carry over unchanged, so the constant-delay guarantee composes with standard pruning.","On the two benchmark domains, string manipulation and integer list manipulation, EcoSearch solves more tasks within a fixed time than its predecessors, including roughly twice as many tasks in the same wall-clock time."],"supporting_citations":[{"why":"introduced the cost tuple representation and the Bee Search algorithm that EcoSearch builds on and compares against.","marker":"Ameen and Lelis (2023)"},{"why":"introduced Heap Search, per-non-terminal data structures, and the frugal-expansion cost analysis EcoSearch inherits.","marker":"Fijalkow et al. (2022)"},{"why":"provides the bucket-queue data structure that turns priority-queue operations into constant time.","marker":"Thorup (2000)"},{"why":"supplies the DeepCoder integer-list domain and the neural cost model used in the experiments.","marker":"Balog et al. (2017)"},{"why":"supplies the FlashFill string-manipulation tasks used as the second benchmark domain.","marker":"Gulwani (2011)"},{"why":"introduced A* best-first search for synthesis and the delay notion that EcoSearch improves upon.","marker":"Alur et al. (2017)"}],"fun_headline_variants":["Constant-delay search cracks synthesis faster","EcoSearch: best-first with no delay creep","Best-first synthesis now with constant delay","EcoSearch: constant compute between programs","EcoSearch solves more synthesis tasks in less time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire constant-delay result depends on the claim, asserted rather than fully proven in the paper, that EcoSearch's queues always emit programs in non-decreasing cost order; if that invariant ever fails, the output is not best-first and the delay bound loses its meaning.","fun_headline_variants_meta":{"raw":{"variants":["Constant-delay search cracks synthesis faster","EcoSearch: best-first with no delay creep","Best-first synthesis now with constant delay","EcoSearch: constant compute between programs","EcoSearch solves more synthesis tasks in less time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000187,"raw_usage":{"total_tokens":1237,"prompt_tokens":760,"completion_tokens":477,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":376,"completion_tokens_details":{"reasoning_tokens":409}},"tokens_in":376,"tokens_out":477,"duration_ms":4288,"temperature":1.0,"reasoning_tokens":409,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:35:28.183846+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run EcoSearch on a finite DSL with integer costs and record the CPU time between consecutive generated programs; if the average or worst-case inter-output gap grows as the number of outputs increases, instead of staying bounded, the constant-delay theorem is false. A cheaper check is to inspect the output sequence for any program emitted after a higher-cost program but carrying a lower cost, which would show the best-first invariant is violated.","supporting_citations":[],"review_version":1}