Automated prompt search tries hundreds of candidate instructions on a few hundred benchmark questions and reports the best one. Systems that use a language model as the optimizer, such as OPRO, have reported large gains this way. Two separate effects can inflate those reported scores. The first is the optimizer's curse: when you pick the best of many noisy scores, the winner's score is too high on average, because the search favours candidates that got lucky. The second is benchmark contamination: the scoring model may have seen the test questions during training, so a prompt can raise accuracy by helping the model recall memorized answers rather than by improving its reasoning. The two literatures have studied these effects apart. Prompt search over contaminated benchmarks is the setting where they meet most directly. There, the optimizer is free to hunt for whatever wording unlocks memorized items, and the noise it exploits is no longer zero-mean.
We propose a controlled experiment that splits a prompt-search gain into three additive parts: selection luck, memorization exploitation, and gain that transfers to unseen items. We plant contamination ourselves on a random half of each benchmark, so that contaminated and clean items come from exactly the same distribution. We also propose and test an estimator of the selection-luck component that needs no held-out data. The deliverable is a measured answer to how much of a prompt-search improvement survives on items the model never saw. It also tells us whether existing corrections for the optimizer's curse remove the memorization component, which we predict they do not.
Core Claim
Let $s(p, D)$ be the accuracy of prompt $p$ on item set $D$, and let $p^*$ be the winner of a search run on search set $S$, compared against a fixed baseline prompt $p_0$. Every item has two independent binary attributes. One says whether the item was used in the search; the other says whether it was planted into the scoring model's training data. Because both are assigned at random, the reported gain on contaminated search items splits exactly as follows:
$$ \underbrace{\Delta(S_{c})}_{\text{reported}} = \underbrace{\Delta(S_{c}) - \Delta(H_{c})}_{\text{selection luck}} + \underbrace{\Delta(H_{c}) - \Delta(H_{u})}_{\text{memorization exploitation}} + \underbrace{\Delta(H_{u})}_{\text{transferable}} $$
Here $\Delta(D) = s(p^*, D) - s(p_0, D)$. The labels $S_c$ and $H_c$ are contaminated search and held-out items, and $H_u$ is uncontaminated held-out items.
We make two predictions. First, the memorization term is substantially positive when the search runs on contaminated items: the optimizer finds wordings that trigger recall. Second, the term should be near zero when the same search runs on clean items. The second prediction is the falsifiable part. If memorization exploitation appears equally in both conditions, the effect is generic contamination inflation and has nothing to do with search.
We also claim that the luck term itself grows under contamination. Memorized items respond to wording in an all-or-nothing way, which gives candidate scores heavy tails. Pessimistic corrections that rely on empirical variance will under-penalize these items, because contaminated items show collapsed variance (On The Fragility of Benchmark Contamination Detection in Reasoning Models shows this collapse in log-probabilities).
Relation to Prior Work
Two papers come closest. The Capability Frontier is the nearest on the selection side. It measures selection bias when picking the best model or generation across 21 models and 16 benchmarks, finds naive oracle quality overestimated by 1.2% on average, and corrects this with bias-decay extrapolation and a latent-difficulty graphical model. It treats estimation errors as zero-mean and never separates contamination. We reuse its extrapolation idea as a baseline and test exactly the case it assumes away.
Large Language Models as Optimizers supplies the search procedure. It improved GSM8K from 71.8% with "Let's think step by step" to 80.2% with a discovered instruction, but it checked transfer only to similar public math sets. Our work does not argue that this particular result is spurious. It builds the instrument that would tell.
Several papers motivate the design. The Emperor's New Clothes in Benchmarking? shows that surface edits keep fidelity above 0.9 but give almost no resistance to memorization. It also shows that identical aggregate scores can hide disjoint sets of correctly answered questions. This is why we score per item and treat paraphrase-based decontamination as insufficient. DyCodeEval shows that a model deliberately fine-tuned on HumanEval rose from about 20% to about 80% on the static items yet fell to about 13% on rewritten variants. This confirms that planted contamination produces a large, measurable gap, and DyCodeEval's variants serve as our clean counterparts for code.
Other papers constrain the design. On The Fragility of Benchmark Contamination Detection shows that a single epoch of clean reinforcement learning pushes detectors toward 50–58% AUROC while keeping the inflated accuracy. Filtering by detector cannot be our safeguard, so we include a post-RL condition.
Two papers supply the correction methods we test. HAVER estimates the best arm's mean by averaging the candidates that cannot be statistically distinguished from a lower-confidence-bound pivot. Pessimistic Off-Policy Optimization for Learning to Rank selects by lower confidence bound. Unbiased Objective Estimation in Predictive Optimization shows that plain hold-out evaluation trades optimistic bias for pessimistic bias, and corrects by perturbing the estimates and extrapolating back to zero noise. All of these assume zero-mean, independent noise, and we measure what happens when that assumption breaks.
Research Program
We work with open scoring models at three scales drawn from the cited papers: Llama-3.2-1B, an 8B instruction model, and DeepSeek-R1-Distill-Llama-8B. The benchmarks are GSM8K and HumanEval/MBPP-Sanitized. RepliQA is a third benchmark; its fictional entities make it a near-certain clean reference.
For each benchmark we randomly split items into a contaminated half and a clean half. We fine-tune each scorer on the contaminated half, including solutions, at three doses: none, light (one epoch mixed into unrelated instruction data), and heavy. A control model is fine-tuned on an equal volume of unrelated math or code, so that fine-tuning itself is not mistaken for contamination. A fourth condition adds one epoch of clean reinforcement learning after contamination, following the fragility paper's recipe.
Each half is further split into search and held-out portions. We then run an OPRO-style search with a fixed optimizer model and a fixed budget, for example 200 candidate prompts. We run it once with the search set drawn from contaminated items and once with it drawn from clean items, using several seeds.
We log every candidate's per-item correctness, not just aggregates. This lets us compute all three terms of the decomposition and the normalized Hamming distance between correct-item sets. It also lets us estimate the luck term for any search budget by subsampling the candidate pool.
The analysis contribution is a held-out-free estimator of the luck term, and we evaluate it against the held-out ground truth. The estimator combines bootstrap resampling of search items with re-selection; this is the perturbation-and-extrapolate logic of the predictive-optimization paper applied to a discrete prompt pool. We compare it with HAVER-style head averaging and Capability-Frontier-style extrapolation over the number of candidates.
We then test whether any of these estimators, or selection by lower confidence bound, shrinks the memorization term. We predict they do not, since that term is a shift in the mean rather than noise. Finally, we take the best published-style prompts found on public GSM8K and evaluate them on LiveBench math and MMLU-CF items, as a natural, uncontrolled check on the planted-contamination findings.
Baselines
The naive reference point is the number a prompt-search paper would report: the winner's accuracy on the search set itself. The external anchor is OPRO's reported GSM8K result of 71.8% to 80.2% (Large Language Models as Optimizers). We do not expect to reproduce that figure with different scorers. We report our own naive gain under the same search loop. Any correction must move this number toward the held-out clean gain $\Delta(H_u)$.
The standard-practice baseline is evaluating the winner on a held-out split of the same public benchmark. With our planted design, this removes luck but keeps memorization whenever the held-out items share contamination status. We run it with the identical winner and items, so the only difference is which items are scored. Our claim is that it overstates $\Delta(H_u)$ whenever the search set was contaminated. It counts as beaten if our decomposition shows a significant memorization term across seeds.
The strongest existing correction for selection bias in language-model evaluation is the extrapolation method of The Capability Frontier. That paper reports a 1.2% average naive quality overestimate, not a per-method accuracy for this setting; we found no result on Lacuna for it applied to prompt search. We fit it to the same logged candidate pool with the same compute. Alongside it we run HAVER head averaging (HAVER), for which no reported result was found on Lacuna for language-model prompt selection, and lower-confidence-bound selection (Pessimistic Off-Policy Optimization). The confidence level for lower-confidence-bound selection is tuned on a separate seed only.
Our bootstrap estimator beats these baselines if it has lower mean squared error against the true luck term on clean search sets. The separate prediction is that every correction, ours included, leaves the memorization term intact on contaminated search sets.
The key ablation is a matched pair: the identical search budget and optimizer, run on clean versus contaminated search items for the same contaminated model. A second ablation scores random, unsearched candidate prompts, which gives a null distribution for pure prompt-to-prompt noise.
Why not just…?
Why not just evaluate the winning prompt on a held-out split? On a public benchmark, the held-out split is contaminated whenever the search split is. It therefore removes luck but not memorization exploitation (The Emperor's New Clothes in Benchmarking? notes that splitting a seen benchmark protects nothing). The same paper also shows that held-out evaluation becomes pessimistic as the candidate space grows. Our matched comparison of $H_c$ against $H_u$ measures exactly what this approach misses. If that gap is zero, this alternative wins and we will say so.
Why not just run the search on a contamination-free benchmark such as LiveBench or MMLU-CF? For new work this is the right remedy, and the proposal does not compete with it. It cannot, however, say how much of an existing gain was memorization. Comparing results across benchmarks also mixes contamination with differences in difficulty and topic: MMLU-CF changes question style along with leakage. Our random within-benchmark split removes that confound. We still run the LiveBench transfer check to see whether the controlled results predict the natural ones.
Why not just filter contaminated items or models with a detector first? Detectors fail exactly where this matters. After one epoch of clean reinforcement learning they fall to near chance (On The Fragility of Benchmark Contamination Detection). Our post-RL condition will show whether Min-K% filtering before search reduces the memorization term. We expect it to work only in the no-RL condition.
Why not just select by lower confidence bound? Lower confidence bounds penalize high variance. Memorized items are low-variance and high-mean, so they are left unpenalized. We test this directly. If lower-confidence-bound selection does shrink the memorization term, then our variance-collapse explanation is wrong and the cheaper fix suffices.
Decisive Checks
The central check is the sign and size of the memorization term, $\Delta(H_c) - \Delta(H_u)$. We measure it for searches run on contaminated items and compare it against the same quantity for searches run on clean items, with confidence intervals from seed and item bootstraps. A positive difference that grows with contamination dose supports the claim. A null difference refutes the search-specific mechanism.
The second check is whether the luck term is larger on contaminated search sets than on clean ones at a fixed budget. We also measure how the luck term scales with the number of candidates, which the subsampled pools make possible.
The third check is whether the bootstrap estimator recovers the true luck term within its stated intervals on clean data. On contaminated data, we test whether every estimator's residual error matches the memorization term, which would mark the boundary of what statistical correction can do.
The final check is at the item level. We ask whether the winning prompts' extra correct answers fall disproportionately on planted items, measured by normalized Hamming distance and the share of newly correct items that were contaminated. A plain shift in aggregate accuracy would not show this.
References
- On The Fragility of Benchmark Contamination Detection in Reasoning Models
- The Capability Frontier: Benchmarks Miss 82% of Model Performance
- Large Language Models as Optimizers
- The Emperor's New Clothes in Benchmarking? A Rigorous Examination of Mitigation Strategies for LLM Benchmark Data Contamination
- DyCodeEval: Dynamic Benchmarking of Reasoning Capabilities in Code Large Language Models Under Data Contamination
- HAVER: Instance-Dependent Error Bounds for Maximum Mean Estimation and Applications to Q-Learning and Monte Carlo Tree Search
- Pessimistic Off-Policy Optimization for Learning to Rank
- Unbiased Objective Estimation in Predictive Optimization
- MMLU-CF: A Contamination-free Multi-task Language Understanding Benchmark