{"id":"4443e990-3aa2-4d31-bc82-5035c865d5a1","arxiv_id":"2504.14367","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"CFG plus MAP-Elites produces structurally diverse high-performing prompts and shows task-specific effects, with zero-shot prompts winning on logic tasks.","lead":"This paper combines a grammar-based prompt generator with the MAP-Elites evolutionary algorithm to map how prompt structure affects LLM performance. It reports that this method finds more diverse high-scoring prompts than random search, and that simple zero-shot prompts beat few-shot prompts on logic-heavy tasks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 21-vs-6 coverage advantage may be an artifact of MAP-Elites selecting on noisy 50-sample fitness scores; without repeated runs or a matched best-of-k random control, the headline claim is not yet supported.","rationale":"The paper is a transparent, well-scoped empirical study, and the reader's CONDITIONAL verdict is appropriate. The central claim, however, rests on a quantitative comparison whose main possible failure mode is exactly the reader's weakest assumption: 50-instance fitness is noisy, and MAP-Elites archives are built by maximizing that noisy fitness. I sharpen this into a concrete selection-bias mechanism: archive members are maxima of noisy estimates, so the high-performer coverage advantage over Random Search can be inflated even if the true quality distributions are identical. The paper acknowledges resource limitations in Section VI.A and promises code/data, but it does not report repeated runs or variance, and the only significant chi-square results appear in two of seven tasks. The proposed concrete test (larger evaluation sets plus a best-of-k random control) would settle whether the improvement is real. This does not move the verdict; it remains CONDITIONAL pending that evidence.","tokens_in":13010,"tokens_out":7283,"duration_ms":70244,"concrete_test":"Re-run the SSB+LLaMA-3-1 and Winowhy+Starling conditions with: (1) the same MAP-Elites algorithm but with num evaluations increased to 500 (or 5 repeated runs of 50, aggregating coverage), and (2) a matched 'best-of-k random' control that randomly samples genotypes, assigns them to bins, and keeps only the best observed fitness per bin (no mutation or selection across generations). If the MAP-Elites coverage advantage over this control shrinks or vanishes with larger num evaluations, the headline result is driven by noise-maximization; if it persists, the claim is supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is that the headline coverage advantage may be an artifact of selecting on a noisy fitness estimate. In Algorithm 1 and Eq. (1), fitness is the proportion correct on only 50 randomly drawn task instances (num evaluations=50, Section IV.C). Each archive bin keeps the individual with the highest observed fitness ('Add or replace ... if it improves fitness'), so archive members are maxima of noisy estimates. If true accuracy is 0.5, a single 50-trial evaluation has probability about 0.24 of exceeding the 55% high-performer threshold; if a bin has seen k candidates, the chance that at least one crosses 0.55 is 1-(1-0.24)^k, which is about 0.94 for k=10. Random Search has no equivalent optimization-driven selection, so Table I's '21 of 28 runs' vs '6 of 28 runs' comparison could reflect selection bias rather than genuine quality-diversity search. The paper reports no repeated runs or variance for these coverage counts, and the only claimed statistical significance is in two tasks (SSB and Winowhy). Without controlling for selection-on-noise, the central claim that MAP-Elites 'significantly outperforms' random generation is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes combining a context-free grammar (CFG) with the MAP-Elites quality-diversity algorithm to explore the prompt space of LLMs. Genotypes are CFG expansion paths that control phenotypic traits such as number of examples, reasoning depth, and role context; fitness is the proportion of correct answers on 50 task instances per prompt. The authors evaluate the method on seven BigBench Lite tasks with four sub-10B instruction-tuned LLMs, comparing MAP-Elites against random search in terms of phenotypic coverage, correlation between prompt features and accuracy, and the distribution of features among high-performing prompts. The central claim is that MAP-Elites 'consistently outperformed Random Search' in coverage, with statistical significance in two tasks and high-performer coverage above 60% in 21 of 28 runs versus 6 of 28 for Random Search (Section V.A, Table I). The conclusion states that the method 'effectively enhances prompt diversity, significantly outperforming random generation.' Public code and data are provided via Zenodo.","tokens_in":13258,"tokens_out":4489,"duration_ms":41119,"significance":"If the central claim were fully established, the paper would make a useful contribution to automated prompt engineering by showing that a quality-diversity search over a grammar-defined prompt space yields both higher coverage of the phenotypic space and actionable insights about which prompt structures help which tasks. The paper is honest in listing resource-driven limitations, and the public reproduction artifacts are a real strength. However, the headline claim currently rests on a small number of runs, noisy fitness estimates, and statistical comparisons that are partly circular. The observed effect is plausible, but the evidence as reported does not yet support the strong conclusion in the abstract and Section VI.","major_comments":[{"comment":"The archive's keep-best-in-bin rule, combined with fitness estimated from only 50 task instances, makes the headline coverage advantage vulnerable to selection on noise. Each prompt's fitness is the proportion correct on 50 random instances, and the archive stores the individual with the highest observed fitness per bin. If true accuracy is near 0.5, a single 50-trial evaluation has probability about 0.24 of exceeding the 55% high-performer threshold, and with several candidates per bin the chance that at least one crosses the threshold is large. Random Search, as described, has no equivalent selection pressure, so the 21-of-28 versus 6-of-28 coverage counts in Table I may reflect the number of noisy draws per bin rather than a genuine quality-diversity advantage. The paper reports no repeated runs and no confidence intervals for these counts. Please add repeated runs or a matched best-of-k random baseline, and report variance or confidence bounds for the coverage statistics.","section":"Section IV.C, Algorithm 1, Eq. (1)"},{"comment":"The random-search baseline is underspecified. The text says only that 'we used random sampling as a baseline for diversity' and gives no details on the number of individuals sampled, whether the same evaluation budget (500 evaluations) is used, or whether any best-of-k selection is applied. Without this information, the coverage comparison in Table I may conflate search effectiveness with evaluation budget. The authors should specify the random-search protocol precisely, including the number of samples, the allocation of fitness evaluations, and whether the same 55% threshold is applied to the same set of evaluated prompts.","section":"Section IV.C"},{"comment":"The z-tests for feature over-representation compare the high-performer subset to the overall population of 500 individuals from which those high performers were drawn. This is not an independent comparison: any subset defined by a fitness threshold will tend to differ from the full population on features correlated with fitness, and since the archive keeps only the best individual per bin, the 'high performers' are also the survivors of within-bin selection. The dagger significances in Table III are therefore partly definitional and do not establish that MAP-Elites preferentially explores those structures. A valid test would compare the archive's high performers against an independently sampled random population, or against the complete set of evaluated genotypes with an appropriate multiple-testing correction.","section":"Section V.C, Table III"},{"comment":"The statement that 'MAP-Elites consistently outperformed Random Search' is not supported by the reported statistics. Only SSB and Winowhy reach p < 0.05, multiple comparisons across the 28 runs are not accounted for, and in several rows Random Search reports higher coverage (e.g., PDSD/LLaMA-3-1 high-performer coverage of 80% vs. 72%). The conclusion in Section VI that the method 'significantly outperforming random generation' is an overstatement relative to the evidence. The authors should either temper the claim to the tasks where significance holds or provide a proper multi-run analysis with variance estimates.","section":"Section V.A, Table I"}],"minor_comments":[{"comment":"There is a typo in the sentence 'improve the fitness os such solutions' which should read 'improve the fitness of such solutions.'","section":"Section III.B"},{"comment":"The pseudocode would benefit from an explicit description of the mutation operators and the archive replacement rule, rather than only a textual description; this would make the 'Add or replace' step unambiguous.","section":"Section III.B, Algorithm 1"},{"comment":"The heatmap in Figure 2 is referenced but not visible in the manuscript text; please ensure it is legible and that all correlation values and significance markers are readable in the published version.","section":"Section V.B, Figure 2"},{"comment":"The paper states that LLM temperature was set to 0, but does not discuss whether API-side nondeterminism was otherwise controlled; a brief note on this would strengthen reproducibility.","section":"Section IV.C"},{"comment":"The description of the statistical tests (Chi-Square, p-value, Cramer's V) is brief; please state the contingency table structure and the sample size underlying each test, since the table reports only percentages.","section":"Section V.A"}],"recommendation":"major_revision","confidential_remarks":"This is a borderline case. The methodology is reasonable, the public artifacts are a genuine strength, and the limitations section is candid. However, the central claim of significant improvement over random search is not yet supported: the evidence is based on a small number of runs, fitness is noisy, the random baseline is underspecified, and the high-performer z-tests are partly circular. I think the paper can be made publishable if the authors add repeated runs or a matched best-of-k baseline, report variance, and revise the conclusion to match the statistical evidence. The current version overstates the results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuine but modest step. Combining a CFG genotype with MAP-Elites to map prompt structure space is new, and the write-up is honest about weak correlations and resource limits. The problem is the headline claim — “significantly outperforming random generation” — rests on a comparison that selection on noisy fitness could explain.\n\nWhat’s new: prior work used evolutionary sampling or grammar prompting separately; here the CFG gives controlled variation over shots, reasoning depth, and context, and MAP-Elites bins by those phenotypes. That is a reasonable way to ask which prompt structures matter per task. The paper ships code and data (Zenodo), reports 56 runs, and openly lists limitations in Section VI.A. The per-task findings — zero-shot best for LD3 and SQA, examples helpful for Winowhy and SSB — are plausible and consistent with the broader in-context learning literature.\n\nWhere it is soft: The 21/28 vs 6/28 coverage count is the empirical core, but fitness is measured on 50 random instances, and the archive keeps the max of noisy estimates. Random search has no optimizer pushing candidates across the threshold, so the gap could be selection bias rather than richer exploration. The high-performer z-tests in Section V.C compare against the archive population itself, which is not independent, so the significance is inflated. Only two of seven tasks reach statistical significance on coverage, effect sizes are mostly small to medium, and the correlations are near zero — the authors themselves admit large-sample significance is likely. No repeated runs, no variance, no confidence intervals. These are addressable, but they mean the central quantitative claim is not yet established.\n\nVerdict: this deserves a serious referee, not a desk reject. The method is worth engaging, and the questions are the right ones. I would send it back for major revision: add repeated runs or variance estimates, add a matched best-of-k random baseline to control for selection-on-noise, and redo the z-tests against an independent sample or otherwise account for archive dependency. If those checks hold, this becomes a solid contribution. As is, I treat the qualitative trends as suggestive rather than demonstrated.","headline":"Novel CFG-plus-MAP-Elites prompt mapping, but the headline coverage claim is not yet supported because noisy 50-shot fitness plus archive selection can explain the gap.","tokens_in":13787,"tokens_out":1324,"would_cite":false,"duration_ms":12750,"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":"A grammar-guided MAP-Elites search produces more diverse, high-performing prompts than random search, and the resulting maps expose task-specific prompt rules.","keywords":["prompt engineering","MAP-Elites","quality-diversity search","context-free grammar","large language models","prompt diversity","BigBench Lite"],"falsifier":"Run the full 56-run protocol several times with different random seeds, then take every archived prompt and score it on the complete task set; if coverage counts or which features look significant change across seeds or against full-set scores, the reported diversity advantage and feature correlations are not stable.","tokens_in":12790,"feed_emoji":"🧬","tokens_out":4896,"duration_ms":42006,"temperature":0.7,"pith_summary":"This paper claims that prompt diversity for large language models can be systematically generated and studied by combining a context-free grammar with the MAP-Elites search algorithm. The authors argue that MAP-Elites covers more of the prompt-feature space with high-quality prompts than random search, and that the resulting archive reveals task-dependent relationships between prompt structure and model accuracy. The value is practical: instead of hand-tuning prompts, a practitioner could use this approach to map which prompt designs work for which task types, and the maps suggest that no single prompt style wins everywhere.","feed_headline":"MAP-Elites finds more diverse, high-performing prompts than random search","feed_subtitle":"A grammar-based evolutionary search maps which prompt structures work for which LLM tasks.","key_machinery":"The mechanism is a context-free grammar whose expansion path acts as the genotype: production choices decide whether a prompt includes a context-role, how many examples it uses (zero-shot, few-shot, or many-shot), and its reasoning depth (no chain-of-thought, one step, or multiple steps), along with task-specific entries, requests, instructions, and examples. MAP-Elites then evolves a population of these genotypes, scoring each prompt by accuracy on 50 task instances, binning individuals by number of examples, prompt length, and reasoning depth, and keeping only the best occupant per bin. The structured archive is what carries the argument: coverage of bins by high-accuracy individuals is the measure of diversity with quality, and the bin distribution is what supports the task-specific correlations.","core_discovery":"The paper's central claim is that structuring prompt generation with a context-free grammar and evolving prompts with MAP-Elites produces a broader archive of high-performing, phenotypically varied prompts than random sampling. Across seven BigBench Lite tasks and four instruction-tuned models, MAP-Elites covers over 60% of the feature space with individuals above 55% accuracy in 21 of 28 runs, versus 6 for random search, with statistically significant differences on two tasks. The archive analysis shows task-specific patterns: zero-shot prompts dominate for logical-deduction and knowledge-heavy tasks like LD3 and KU, while few-shot and many-shot prompts help contextual tasks like PDSD and Winowhy; context-role and chain-of-thought depth show little measurable effect. The authors conclude that exploring the prompt space in this way is a method for both optimization and characterization of how prompt structure affects LLM behavior.","pith_inferences":["Inference: because each prompt is scored on only 50 task instances without repeated runs, evaluation noise could be inflating or deflating the coverage gap; rerunning with fixed seeds would test this.","Inference: the same grammar-plus-archive recipe could be applied to larger models, and the zero-shot dominance on reasoning tasks may shrink or reverse if larger models exploit demonstrations differently.","Inference: the null context-role result may be an artifact of static templates; task-conditioned or dynamically generated roles could reveal a real effect."],"forward_implications":["Prompt search can be cast as a quality-diversity problem: the archive itself is a deliverable, not just the best prompt.","Zero-shot prompts are not a compromise for reasoning-heavy tasks; on LD3, SQA, and KU they outperform few-shot prompts, so simple designs should be part of any search.","Few-shot and many-shot prompts carry the top performers on contextual pattern-recognition tasks like PDSD, SSB, and Winowhy, consistent with in-context learning effects.","Static context-role templates and chain-of-thought depth had negligible measured impact, meaning those features should not be the primary lever in prompt optimization.","Reported correlations between prompt features and accuracy are generally weak, so the method is more useful for mapping task-specific regions than for deriving global prompt-design rules."],"supporting_citations":[{"why":"Supplies the MAP-Elites algorithm that carries the quality-diversity search.","marker":"[6]"},{"why":"Prior evolutionary prompt-space sampling that this work extends and contrasts with.","marker":"[7]"},{"why":"Defines the BigBench Lite task collection used for evaluation.","marker":"[8]"},{"why":"Provides the in-context learning account used to explain why examples help certain tasks.","marker":"[18]"},{"why":"Chain-of-thought prompting is the source of the reasoning-depth trait varied in the grammar.","marker":"[19]"},{"why":"Context-free grammar formalism is the representational backbone for prompt genotypes.","marker":"[31]"},{"why":"BigBench Lite's parent benchmark, providing the task suite and scope.","marker":"[32]"}],"fun_headline_variants":["Evolving prompts: MAP-Elites beats random search","Grammar-guided evolution finds diverse, top prompts","Evolutionary search illuminates prompt design space","MAP-Elites maps prompt space for better LLM prompts","Prompt evolution: quality and diversity via MAP-Elites"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that a prompt's fitness measured on 50 randomly drawn task instances is stable enough to decide which prompts fill the archive and which features appear correlated with performance.","fun_headline_variants_meta":{"raw":{"variants":["Evolving prompts: MAP-Elites beats random search","Grammar-guided evolution finds diverse, top prompts","Evolutionary search illuminates prompt design space","MAP-Elites maps prompt space for better LLM prompts","Prompt evolution: quality and diversity via MAP-Elites"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000168,"raw_usage":{"total_tokens":1217,"prompt_tokens":855,"completion_tokens":362,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":286}},"tokens_in":471,"tokens_out":362,"duration_ms":3684,"temperature":1.0,"reasoning_tokens":286,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:49:47.277731+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the full 56-run protocol several times with different random seeds, then take every archived prompt and score it on the complete task set; if coverage counts or which features look significant change across seeds or against full-set scores, the reported diversity advantage and feature correlations are not stable.","supporting_citations":[{"cited_title":"Exploring the prompt space of large language models through evolutionary sampling,","cited_arxiv_id":null,"evidence_quote":"Prior evolutionary prompt-space sampling that this work extends and contrasts with."},{"cited_title":"Big-bench lite,","cited_arxiv_id":null,"evidence_quote":"Defines the BigBench Lite task collection used for evaluation."},{"cited_title":"Chomsky, Aspects of the Theory of Syntax","cited_arxiv_id":null,"evidence_quote":"Context-free grammar formalism is the representational backbone for prompt genotypes."}],"review_version":1}