DS-1000, rejection-sampling skyline & Z

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) = 𝔼_p0(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.