Coverage-Guided Sampling: Allocate More Code Samples Where Behavior Remains Unseen

The pattern is conventional_core_atypical_pairing: a conventional core (best-of-N + test filtering + execution clustering) paired with an unconventional species-estimation tool. If reviewers remember it, this will be because of a testable diagnostic conclusion: whether coverage statistics can distinguish 'being trapped in an incorrect attractor' from 'not yet explored,' while retaining predictive power after controlling for public-test status. Even if the end-to-end improvement is only approximately 2 percentage points, this diagnostic could merit citation; if it does not hold, the result is a clear negative finding. At present, this is only a hypothesis, not an established conclusion.

In code generation using best-of-N plus test filtering, budget allocation usually relies on answer agreement or difficulty proxies, which cannot distinguish 'agreement because the problem has been solved,' 'being trapped in a single incorrect attractor,' and 'a flat, insufficiently explored distribution.' We treat sampling as capture events for program behavior: execute each sample on approximately 20 inputs generated by the same LLM, then hash its output signature to obtain a behavioral cluster. Good-Turing missing mass M_t (singleton-cluster count/t) and Chao1 abundance are used to estimate the probability that 'the next sample reveals new behavior.' Combined with the proportion of observed clusters that pass public example tests (with a Beta prior), these estimate the probability that 'an unseen cluster that passes the tests will appear.' Each batch of 8 samples is then greedily allocated to the problem with the largest marginal gain. For 'incorrect attractor' problems with M_t≈0 and no passing cluster, trigger forced diversification by increasing temperature or changing the prompt. We deliberately do not assume that this method outperforms simple baselines: 'stop at the first public-test pass + round-robin sampling of unsolved problems' is a strong baseline that must be beaten. We also conduct conditional analysis, comparing the predictive power of M_t, leader margin, and difficulty probes for subsequent gains only on problems with no passing cluster yet. LiveCodeBench evaluation uses Pareto curves and rank correlation; abandon the method if M_t adds no value. There is currently no experimental evidence; all of the above are hypotheses to be tested.

The brief notes that uniform allocation of test-time compute wastes resources on easy problems while hard problems receive insufficient attention. Existing adaptive self-consistency inherits the voting-based stopping rule of 'whether the leader is stable.' In coding settings with partial verifiers, however, additional samples have value only when they can expose behavior not previously seen. Code execution signatures provide exact, inexpensive semantic clustering unavailable in mathematical answer clustering. Qwen3-32B and DeepSeek-R1 distill, combined with vLLM, make 64–256 samples per problem feasible, and LiveCodeBench provides temporally split data designed to resist contamination. We must be candid, however: this motivation depends on M_t providing information beyond public-test status, which has not yet been demonstrated.

The convention in the field is to use agreement as a stopping/allocation signal. Treating samples as 'capture events' for behavior and borrowing unseen-species estimators from ecology/linguistics is uncommon. Candidly, however, an expert could reasonably expect 'public-test pass status' to explain most gains, while unseen mass on difficult problems largely consists of junk singletons (crashes, timeouts, and anomalous outputs). The non-obviousness of the approach has therefore not yet been established; this is precisely what the experiments must test.

1. Construct behavioral clusters: for each problem, have the same LLM generate approximately 20 inputs in one batch (filtered through differential testing). Execute each sample program to obtain an output-signature hash. Collapse crashes, timeouts, and exceptions into a single 'invalid' cluster to prevent contamination by junk singletons (addressing the red team's junk-singleton criticism), and treat this choice as a sensitivity variable.
2. Coverage statistics: maintain cluster counts n_k. After t samples, compute Good-Turing missing mass M_t = singleton-cluster count / t over valid clusters only, and calculate the Chao1 abundance estimate.
3. Partial-verifier signal: measure the proportion of observed clusters that pass public example tests, and use a Beta prior to obtain the posterior probability P_pass that 'an unseen cluster can pass the tests.'
4. Allocation policy: under a global budget B, assign the next batch of 8 samples each round to the problem with the largest M_t·P_pass. Freeze problems that already have a passing cluster whose count exceeds a Chao-based confidence lower bound.
5. Final answer: select the cluster with the highest count among those passing public tests; also report CodeT-style dual-consistency ranking as a comparison.
6. Forced diversification (by default, an independent module that can be switched on or off; initially excluded from the primary method): switch temperature or prompt for problems with M_t≈0 and no passing cluster. To preserve exchangeability, restart counts separately for each sampling configuration and treat configurations as strata, avoiding pooled counts across configurations.
7. Required baselines and diagnostics: implement 'stop at the first public-test pass + round-robin sampling of unsolved problems' and Thompson/UCB allocation based on each problem's public-test pass rate. Conduct conditional analysis: on problems with no passing cluster, compare the rank correlations of M_t, leader margin, and difficulty probes with the actual gain from the next k samples. Then separately analyze problems with a passing cluster that nevertheless fails hidden tests (weak public tests).
8. Offline replay framework: cache all samples and the execution matrix, then replay each allocation policy over random orderings, making ablations and multi-seed confidence intervals almost cost-free.

Use Qwen3-8B for the primary experiments, extending to Qwen3-32B and another model family (such as DeepSeek-R1 distill). Cache 128–256 samples per problem and their execution matrices on generated inputs and public/hidden tests. Replay all policies offline on the cache, repeating with random orderings. Compare all methods at the same total generation-token cost, including probe overhead. Use at least 3 sampling seeds and bootstrap confidence intervals (the post-cutoff LiveCodeBench split contains only a few hundred problems, so differences of 2–4 percentage points require caution).

• datasets: LiveCodeBench (post-cutoff split, easy/medium/hard); HumanEval+/MBPP+ (easy-problem controls); optional extension: mathematical datasets with answer-equivalence clustering (such as MATH-500) to test generalization
• baselines: uniform N per problem + test filtering; stop at the first public-test pass + round-robin sampling of unsolved problems (the strongest trivial baseline, which must be beaten); Thompson/UCB allocation based on public-test pass rates; adaptive early-stopping self-consistency based on solution agreement (in the style of Aggarwal et al.); bandit allocation based on per-problem difficulty prediction/probe samples (in the style of Damani et al.); CodeT-style dual-consistency ranking (uniform N); oracle allocation based on actual pass rates (upper bound)
• metrics: pass@1 versus total generation tokens as a Pareto curve (including probe overhead); proportion of samples saved at equal accuracy; Spearman correlation between M_t and actual subsequent gain (strata: no passing cluster / a passing cluster that fails hidden tests); budget allocation proportions between hard and easy problems
• ablations: replace Good-Turing with leader margin; remove the Beta prior on the passing proportion; replace execution signatures with code-text/embedding clustering; use 5/20/50 generated inputs; whether to collapse crashes/timeouts into an invalid cluster; remove forced diversification, or count separately by configuration versus pooling counts; separate P_pass-only (without M_t) and M_t-only (without P_pass) variants to isolate the incremental contribution of M_t
• expected: the original hypothesis is an improvement of at least 3 absolute percentage points (LiveCodeBench hard) over agreement-based adaptive stopping and uniform allocation at the same total sample count, or savings of ≥40% of samples at equal accuracy; M_t should have a higher rank correlation with gain from the next 32 samples than leader margin. Based on red-team feedback, my conservative expectation is that most savings will come from the trivial 'stop at the first pass' baseline. The incremental value of M_t on moderately difficult problems with 'no passing cluster' may be small (approximately +1–2 percentage points or 10–20% additional savings), and polarization of pass rates under strong reasoning models may further compress the gains. These are all expectations, not results.
• falsification criteria: abandon the method if, in conditional analysis controlling for public-test status, M_t's rank correlation with subsequent gain is no higher than that of leader margin plus difficulty probes, or if its Pareto curve does not achieve an improvement at p<0.05 over the 'stop at the first pass + round-robin' and Thompson/UCB baselines across 3 seeds. Coverage diagnostics could instead support a short analytical paper, but only if the diagnostics themselves hold.

1. Days 1–2: use vLLM to sample 128 solutions per problem from Qwen3-8B on 200 post-cutoff LiveCodeBench problems (approximately 25k generations, less than 1 day on 1–2 A100 GPUs), caching all outputs.
2. Days 2–3: have the same LLM generate approximately 20 inputs per problem and filter them through differential testing. Execute in a sandbox on CPUs to obtain signature matrices and public/hidden-test pass matrices; label crash/timeout clusters.
3. Day 4: first implement the strongest trivial baseline (stop at the first pass + round-robin), uniform allocation, and Thompson/UCB, then verify that they behave reasonably in the replay framework.
4. Days 5–6: implement M_t, Chao1, P_pass, and greedy allocation; replay on random orderings while also calculating leader-margin and difficulty-probe signals.
5. Day 7: perform the core conditional analysis—on problems with no passing cluster, compare each signal's Spearman correlation with the actual gain from the next k samples. Also examine the proportion of junk singletons and the difference before and after collapsing invalid clusters.
6. Days 8–10: assess success/failure signals (success: M_t's correlation exceeds agreement margin by ≥0.1, and the replay Pareto comparison saves ≥20% relative to strong baselines). Also conduct a supplementary 2–3-hour literature search to confirm that no existing 2025–26 paper uses Good-Turing for sampling budgets; decide whether to continue on this basis.

• M_t has no incremental value beyond public-test status, and trivial baselines capture most of the gains (the potentially fatal issue reviewers are most likely to identify). → Use the trivial baseline and the P_pass-only variant as the main controls; perform conditional analysis first, and terminate according to the kill criterion if the premise does not hold.
• Singleton clusters on hard/hopeless problems are mostly junk (crashes, timeouts, and differences on boundary cases), inflating M_t and wasting the budget. → Collapse invalid clusters, weight singletons by validity, adjust the number of probe inputs, and report sensitivity; check whether generated inputs split programs on underspecified boundaries.
• Forced diversification (changing temperature/prompt) violates exchangeability, invalidating the Good-Turing estimate. → Exclude this module from the primary method; include it as an independent ablation and restart counts separately by configuration.
• Execution signatures on model-generated inputs split correct programs (underspecified boundaries), or public tests are so weak that 'passing' is uninformative. → Compare text/embedding clustering and different input counts; analyze weak-public-test problems separately; if necessary, add hidden-test consistency as a diagnostic (for evaluation only).
• Strong reasoning models polarize pass rates (either solved or hopeless), leaving little gain; applicability is limited to code, restricting generalization. → Test across model scales and report by pass-rate strata; optionally extend to mathematical tasks with answer-equivalence clustering; if gains remain small, reposition the contribution as analytical.
• LiveCodeBench's small problem count produces substantial noise; related work is crowded, creating a risk of being scooped; the literature coverage is incomplete. → Use multiple seeds + bootstrap CIs; conduct the supplementary literature search early and release a preprint promptly.

• Q: A trivial rule such as 'stop at the first public-test pass + round-robin sampling of unsolved problems' already performs most of the reallocation. Your gains may come solely from using the verifier. A: This is valid, and the original plan did indeed omit that baseline. In the revised plan it is the main control, alongside Thompson/UCB and a P_pass-only ablation to isolate M_t's incremental contribution. If M_t's predictive power on problems with no passing cluster does not exceed round-robin or difficulty probes, the method will be abandoned according to the kill criterion. I do not assume it will win.
• Q: Missing mass over output-signature clusters is dominated by junk singletons and will incorrectly indicate that hard or hopeless problems 'still need budget.' A: This is a real risk. Mitigations include collapsing crashes/timeouts/exceptions, weighting singletons by validity, reporting sensitivity to input counts and the decision to collapse clusters, and directly measuring the proportion of invalid outputs among singletons. However, these measures cannot fully eliminate the problem of diverse outputs that are 'semantically incorrect but valid'; experiments must determine the outcome.
• Q: Forced diversification violates the exchangeability required by Good-Turing, making the method inconsistent. A: Agreed. The primary method excludes this switch; when it is used as a separate ablation, counts are restarted and stratified by sampling configuration, treating each configuration as a different 'community.' If stratification still yields no gains, remove the module; this does not affect the claim about the core estimator.
• Q: The scope is narrow (code only, requiring executable outputs), and the connection to the brief's mathematics/PRM/step-level guidance is weak. A: It indeed covers only the brief's 'adaptive budget' component and provides no step-level signal. The optional extension to mathematical answer-equivalence clustering can partly address this, but mathematical clustering is coarser and effectiveness is not guaranteed. The paper should be positioned as a study of allocation and diagnostics in partial-verifier settings, rather than a general replacement for PRMs.
• Q: Novelty is limited: execution clustering, missing mass, and adaptive allocation each have precedents, and this merely combines them. A: Agreed that the distinction is moderate. The related papers I supplied do not provide full coverage, and the latest 2025–26 work has not yet been verified. The value depends primarily on whether the conditional diagnostic can distinguish 'stuck' from 'unexplored.' If it cannot, I would not recommend submitting it as a main-conference methods paper.

The test-time-compute tracks of NeurIPS/ICLR are suitable, provided the paper centers on principled analysis: coverage statistics as diagnostic and allocation signals, with strong baselines and conditional analysis. If M_t adds only 1–2 percentage points, a workshop or analytical paper would be more appropriate; the fit with ACL is weaker. The overall assessment is borderline: feasibility is high (offline replay and a go/no-go decision in approximately 8 days), but significance and generalizability are moderately low. A two-week pilot is recommended before deciding whether to invest several months.