DS-1000 Skyline · Rollouts

The accuracy ceiling (skyline) and acceptance rate (Z) of the no-runtime-error potential (DS1000RuntimeNoErrorPotential) under exact posterior sampling, across 10 models and 6 temperatures (59 cells, ~3.8M rollouts). Measured with the literal potential (forkserver, 30 s timeout) scored in the DS-1000 repo environment (sklearn 1.4.0, numpy 1.26.4, …), matching how the dataset's passed labels were produced. Matplotlib excluded (image-graded).

Across ~3.8M rollouts the potential produced only 20 false-rejects (a correct solution it marked as erroring), "runs without error" is an almost lossless filter on correct code. Those 20 fall on just 10 problems (7 on one), almost all np.random-based or compute-heavy Sklearn/Numpy tasks: cases where the code's own runtime outcome varies between executions (random draw, 30 s timeout, memory), not a class of correct code the potential systematically rejects.
* Qwen2.5-Coder 7B, DeepSeek-Coder: externally ingested (# SOLUTION START/END convention).

Definitions

Constraint (validity potential). A sample y is valid iff its code runs to completion under DS1000RuntimeNoErrorPotential — no runtime/syntax error and no timeout:

φ(y) = 1[ y passes DS1000RuntimeNoErrorPotential ] ∈ {0, 1}

An answer that runs but returns the wrong value is still valid — the constraint is “does it run”, not “is it correct”.

Constrained-generation target. Let p₀(· | x) be the model’s sampling distribution for question x at the given temperature. Enforcing the constraint defines the target distribution

π(· | x) ∝ p₀(· | x) · φ(·)

Rejection sampling realises π exactly: draw from p₀, discard invalid samples, keep the valid ones. This is what we rejection-sample for — the validity-constrained distribution, not correctness.

Normalizing constant = validity rate. Estimated by simple Monte Carlo over the rollouts:

Z(x) = 𝔼_p₀(y|x)[ φ(y) ] = Pr( y valid | x ) ≈ (1/N) ∑_i φ(y_i)

where N is the total number of rollouts sampled for question x. Averaging over all tasks x gives the full Z:

Z = mean_x Z(x)

Correctness rate (single-sample accuracy). What we ultimately care about — how often the constrained generator is right — factorises as

Pr( y correct | x ) = Pr( y valid | x ) · Pr( y correct | y valid, x ) = Z(x) · skyline(x)

Averaged over problems, this single-sample accuracy is the pass@1 plotted on the DS-1000 page:

pass@1 = mean_x Pr( y correct | x )

Skyline over the benchmark. The second factor, skyline(x) = Pr( y correct | y valid, x ), is the accuracy within the valid set. To report one skyline for the whole benchmark we use the estimator

skyline = pass@1 / Z

equivalently, the fraction of all valid rollouts that are correct:

skyline = (∑_x ∑_y 1[y correct]) / (∑_x ∑_y 1[y valid]) = (∑_x Correct_x) / (∑_x Valid_x)

summing over the N rollouts y of each problem x — Valid_x the rollouts that pass φ, Correct_x the correct ones. Averaging the per-problem ratios instead — mean_x skyline(x) — would not give Pr( y correct | y valid): it weights every problem equally no matter how many valid samples it had, so the product no longer recovers pass@1. The pooled estimate weights every valid rollout equally.

Why “skyline”? It is the accuracy of ideal constrained generation: if you could sample exactly from π (enforce validity and nothing else) and ask how often the result is correct, this is the number you would get. The point is that it is a reference for evaluating approximate methods. In practice you rarely have exact access to π — sampling it (e.g. by rejection) is expensive — so an inference method approximates it with some π̃ (importance sampling, SMC, fine-tuning, …). To judge that method you look at the accuracy of samples from π̃ and compare it to this skyline: it tells you how close the approximation gets to the ideal constrained target. Strictly it is not an upper bound: a biased π̃ could exceed it if its bias systematically favours correct solutions (approximation error correlated with correctness) — very unlikely in practice, so we treat it as a skyline / reference rather than a hard ceiling.

For each model and temperature we report the pooled validity rate Z and skyline (DS-1000, Matplotlib excluded), so that pass@1 = Z × skyline holds on the plotted values. Shaded bands are 95% bootstrap confidence intervals (2000 resamples of the problem set).

posterior vs prior: what conditioning on validity buys

One dot per model at the selected temperature (optionally within one library). The diagonal is P(V) = 1; a dot’s height above it is what enforcing the constraint buys.

Conditioning on validity: the completion runs without a runtime or syntax error (an AssertionError still counts as valid) — the potential DS1000RuntimeNoErrorPotential

x is the prior P(C): the pass@1 rate as sampled. y is the posterior P(C|V): the pass rate after rejection-sampling to the first draw the validity notion above accepts. Height above the diagonal is the gain; error bars are 95% bootstrap CIs (2000 resamples of the problem set) on both axes. Hovering a dot also shows its two reference lines: the ray from the origin (slope 1/P(V), the cost) and the line through (1,1) (slope = the surviving-failure fraction).

skyline against temperature

skyline = (total correct) / (total valid), pooled over problems — the accuracy ideal constrained generation reaches. It falls with temperature as the target π dilutes.

skyline by model and temperature

Each cell is the pooled skyline for one (model, temperature), greedy t=0 first, then the sampled temperatures. Browse the underlying rollouts in the explorer.

Z, the acceptance rate (normalizing constant)

model	t=0.0	t=0.2	t=0.4	t=0.6	t=0.8	t=1.0
Llama-3 8B	0.465	0.447	0.427	0.390	0.341	0.309
Llama-3 8B Instruct	0.419	0.411	0.400	0.388	0.372	0.363
Llama-3.1 8B	0.405	0.399	0.385	0.354	0.316	0.279
Llama-3.1 8B Instruct	0.374	0.379	0.370	0.354	0.336	0.325
Llama-3.2 1B	0.128	0.114	0.101	0.088	0.067	0.050
Llama-3.2 1B Instruct	0.170	0.179	0.157	0.137	0.112	0.109
Qwen2.5-Coder 3B	0.452	0.432	0.403	0.362	0.318	0.295
Qwen2.5-Coder 3B Instruct	0.476	0.483	0.468	0.443	0.411	0.379
Qwen2.5-Coder 7B *	0.554	0.542	0.513	0.479	0.431	0.391
DeepSeek-Coder 6.7B *	0.426	0.431	0.419	0.392	0.350	0.295

Z is the pooled proportion of rollouts that obey the constraint (run without error), Z = mean_x Z(x) — the potential’s normalizing mass under the sampling distribution. With pooled estimators single-sample accuracy factorises as pass@1 = Z × skyline. Z collapses toward t=1.0 as more rollouts error out.

by library, choose a model

skyline and Z broken down by library for a single model. Use the selector to switch models; the two plots and the table below update together. Shaded bands are 95% bootstrap CIs (2000 resamples of that library’s problems).

library	metric	t=0.0	t=0.2	t=0.4	t=0.6	t=0.8	t=1.0
Numpy	skyline	0.519	0.500	0.466	0.430	0.388	0.363
Numpy	Z	0.700	0.700	0.683	0.616	0.501	0.328
Pandas	skyline	0.325	0.317	0.308	0.273	0.231	0.194
Pandas	Z	0.646	0.647	0.617	0.550	0.439	0.263
Pytorch	skyline	0.469	0.471	0.500	0.503	0.449	0.409
Pytorch	Z	0.471	0.502	0.474	0.421	0.336	0.183
Scipy	skyline	0.534	0.512	0.486	0.445	0.407	0.388
Scipy	Z	0.547	0.531	0.515	0.454	0.349	0.196
Sklearn	skyline	0.644	0.623	0.570	0.507	0.423	0.376
Sklearn	Z	0.391	0.404	0.380	0.331	0.237	0.105
Tensorflow	skyline	0.645	0.575	0.563	0.513	0.447	0.418
Tensorflow	Z	0.689	0.629	0.589	0.507	0.411	0.243

library	metric	t=0.0	t=0.2	t=0.4	t=0.6	t=0.8	t=1.0
Numpy	skyline	0.399	0.375	0.364	0.364	0.362	0.370
Numpy	Z	0.718	0.710	0.700	0.676	0.620	0.512
Pandas	skyline	0.304	0.314	0.314	0.302	0.284	0.273
Pandas	Z	0.701	0.694	0.669	0.628	0.568	0.447
Pytorch	skyline	0.750	0.733	0.698	0.661	0.617	0.602
Pytorch	Z	0.529	0.517	0.506	0.474	0.428	0.315
Scipy	skyline	0.460	0.424	0.403	0.370	0.355	0.359
Scipy	Z	0.472	0.493	0.474	0.439	0.383	0.284
Sklearn	skyline	0.683	0.638	0.601	0.575	0.541	0.487
Sklearn	Z	0.356	0.396	0.390	0.359	0.309	0.211
Tensorflow	skyline	0.483	0.508	0.517	0.528	0.538	0.547
Tensorflow	Z	0.644	0.617	0.568	0.510	0.443	0.345

library	metric	t=0.0	t=0.2	t=0.4	t=0.6	t=0.8	t=1.0
Numpy	skyline	0.487	0.470	0.447	0.415	0.376	0.349
Numpy	Z	0.718	0.716	0.697	0.632	0.524	0.343
Pandas	skyline	0.275	0.273	0.262	0.234	0.200	0.166
Pandas	Z	0.725	0.703	0.657	0.589	0.470	0.279
Pytorch	skyline	0.469	0.477	0.478	0.460	0.421	0.351
Pytorch	Z	0.471	0.456	0.433	0.382	0.296	0.163
Scipy	skyline	0.429	0.425	0.416	0.398	0.371	0.340
Scipy	Z	0.594	0.570	0.524	0.453	0.350	0.197
Sklearn	skyline	0.657	0.596	0.553	0.479	0.413	0.345
Sklearn	Z	0.304	0.354	0.344	0.296	0.206	0.088
Tensorflow	skyline	0.467	0.492	0.499	0.489	0.455	0.386
Tensorflow	Z	0.667	0.639	0.583	0.496	0.389	0.237

library	metric	t=0.0	t=0.2	t=0.4	t=0.6	t=0.8	t=1.0
Numpy	skyline	0.407	0.411	0.394	0.379	0.364	0.368
Numpy	Z	0.659	0.662	0.660	0.640	0.587	0.439
Pandas	skyline	0.251	0.266	0.263	0.254	0.237	0.224
Pandas	Z	0.711	0.699	0.676	0.639	0.566	0.400
Pytorch	skyline	0.559	0.576	0.565	0.550	0.511	0.494
Pytorch	Z	0.500	0.506	0.493	0.465	0.414	0.282
Scipy	skyline	0.333	0.372	0.368	0.346	0.335	0.332
Scipy	Z	0.594	0.540	0.505	0.475	0.400	0.249
Sklearn	skyline	0.691	0.548	0.515	0.486	0.453	0.407
Sklearn	Z	0.365	0.399	0.404	0.372	0.311	0.174
Tensorflow	skyline	0.500	0.530	0.533	0.515	0.499	0.482
Tensorflow	Z	0.622	0.620	0.600	0.549	0.465	0.331

library	metric	t=0.0	t=0.2	t=0.4	t=0.6	t=0.8	t=1.0
Numpy	skyline	0.171	0.132	0.108	0.103	0.088	0.070
Numpy	Z	0.186	0.213	0.206	0.176	0.123	0.052
Pandas	skyline	0.047	0.059	0.051	0.042	0.030	0.030
Pandas	Z	0.220	0.238	0.249	0.236	0.180	0.084
Pytorch	skyline	0.273	0.303	0.314	0.286	0.208	0.140
Pytorch	Z	0.162	0.170	0.164	0.139	0.098	0.034
Scipy	skyline	0.250	0.197	0.156	0.127	0.089	0.068
Scipy	Z	0.189	0.184	0.171	0.132	0.086	0.026
Sklearn	skyline	0.000	0.081	0.132	0.119	0.095	0.020
Sklearn	Z	0.078	0.088	0.079	0.066	0.040	0.013
Tensorflow	skyline	0.250	0.002	0.035	0.073	0.090	0.062
Tensorflow	Z	0.089	0.107	0.113	0.103	0.067	0.032

library	metric	t=0.0	t=0.2	t=0.4	t=0.6	t=0.8	t=1.0
Numpy	skyline	0.484	0.491	0.476	0.446	0.406	0.363
Numpy	Z	0.732	0.732	0.695	0.637	0.537	0.374
Pandas	skyline	0.321	0.317	0.302	0.269	0.231	0.181
Pandas	Z	0.653	0.654	0.625	0.579	0.501	0.345
Pytorch	skyline	0.293	0.342	0.405	0.440	0.429	0.395
Pytorch	Z	0.603	0.586	0.555	0.495	0.402	0.256
Scipy	skyline	0.466	0.467	0.453	0.420	0.384	0.330
Scipy	Z	0.547	0.544	0.526	0.484	0.391	0.249
Sklearn	skyline	0.621	0.619	0.589	0.561	0.502	0.396
Sklearn	Z	0.574	0.572	0.526	0.451	0.348	0.200
Tensorflow	skyline	0.476	0.482	0.454	0.444	0.419	0.369
Tensorflow	Z	0.467	0.503	0.501	0.463	0.370	0.250