Code Generation & Verification: theory

Checking generated code with tests and static analysis, running candidates in a sandbox, AST checks for unsafe code, test generation and repair loops.

Code is the one kind of model output that can be checked mechanically: run it and see. That makes code generation the cleanest playground for verification, and also a risky one, because code that runs can also delete files or leak data. This page covers:

how generated code is evaluated;
how candidates are filtered and selected by executing them;
how generated tests find the bugs that hand-written ones miss;
how static analysis catches dangerous code before it runs.

Measuring correctness: pass@k

Code benchmarks such as HumanEval (164 hand-written Python problems, Chen et al., 2021) and MBPP (Austin et al., 2021) check functional correctness: a completion counts only if it passes the problem's unit tests. pass@k is the probability that at least one of $k$ samples passes.

Estimating it from exactly $k$ samples is noisy, so Chen et al. draw $n \ge k$ samples, count the $c$ that pass, and use the unbiased estimator

\text{pass@}k = 1 - \frac{\binom{n - c}{k}}{\binom{n}{k}}

where $\binom{n}{k}$ (" $n$ choose $k$ ") is the number of ways to pick $k$ items out of $n$ . In words: the probability that a random subset of $k$ of the $n$ samples contains at least one correct one is 1 minus the probability that all $k$ are wrong, and the fraction counts the subsets of $k$ that are all wrong over all subsets.

Example. $n = 10$ samples, of which $c = 3$ pass.

$k = 1$ : the fraction of wrong subsets is $\binom{7}{1} / \binom{10}{1} = 7/10$ , so pass@1 $= 0.3$ : just the share of correct samples.

$k = 5$ : $\binom{7}{5} = 21$ ways to pick 5 wrong samples out of 7, and $\binom{10}{5} = 252$ ways to pick 5 samples out of 10. pass@5 $= 1 - 21/252 = 0.917$ .

If $n - c < k$ (here, $c = 8$ , $k = 5$ : only 2 wrong samples), no subset of 5 can be all wrong: pass@5 $= 1$ .

The binomials overflow quickly for large $n$ , so the estimator is computed as a product: $1 - \prod_{i = n - c + 1}^{n} \left(1 - k/i\right)$ . The tempting shortcut $1 - (1 - \hat p)^k$ , with $\hat p = c/n$ , is biased.

Example. $n = 2$ samples, one correct, $k = 2$ . The true pass@2 is 1: both samples are drawn, so one is correct. The shortcut gives $1 - (1 - 0.5)^2 = 0.75$ : it underestimates. The product form gives $1 - (1 - 2/2) = 1$ (here $n - c = 1 < k = 2$ ).

Running candidates

To use tests at generation time, every candidate must be executed. Two practical points:

Isolation. Generated code must run in a sandbox: a separate process or container with no network, a read-only filesystem, and limits on time and memory. Running it inside the evaluating program (as the exercises do, with a restricted set of builtins) is only acceptable for code you trust; a Python namespace with no builtins is not a security boundary.
Every failure is information. A test can fail by a wrong answer, an exception, or a timeout. Self-Debugging (Chen et al., 2023) feeds the execution results back to the model, which explains its code and repairs it.

Example. Five candidates for add(a, b) are run on three tests, add(1, 2) = 3, add(0, 0) = 0, add(-1, 1) = 0:

candidate result

return a + b 3 of 3 passed

return a - b 1 of 3: test 0: wrong answer -1, test 2: wrong answer -2

missing colon after the def line 0: load: SyntaxError: ...: it does not even load

uses an undefined name 0: test 0: NameError: ... for every test

defines plus instead of add 0: load: KeyError: 'add'

Ranking by tests passed: candidate 0 first, then 1, then the others. The error messages are what a repair step would give back to the model.

candidate	result
`return a + b`	3 of 3 passed
`return a - b`	1 of 3: `test 0: wrong answer -1`, `test 2: wrong answer -2`
missing colon after the `def` line	0: `load: SyntaxError: ...`: it does not even load
uses an undefined name	0: `test 0: NameError: ...` for every test
defines `plus` instead of `add`	0: `load: KeyError: 'add'`

Selecting among samples by behaviour

With many samples and few tests, how do you pick what to submit? AlphaCode (Li et al., 2022) filtered its samples with the example tests, then ran the survivors on extra generated inputs and clustered programs that produce the same outputs. Selecting one program from each cluster, largest first, worked best: there are many ways to be wrong, but correct programs tend to agree, so they form large clusters. CodeT (Chen et al., 2022) applies the same idea with test cases generated by the model itself: a solution is trusted if it agrees with many tests and many other solutions agree with it.

Example. Five programs meant to compute the absolute value, run on the inputs $-2$ , $0$ and $3$ :

program outputs

abs $2, 0, 3$

an if x >= 0 else -x version $2, 0, 3$

lambda x: x (wrong for negatives) $-2, 0, 3$

$\sqrt{x^2}$ $2.0, 0.0, 3.0$ (equal to $2, 0, 3$ )

$1 // x$ (crashes at 0) $-1$ , error, $0$

Clusters: $\{0, 1, 3\}$ (3 programs that agree), $\{2\}$ , $\{4\}$ . The biggest cluster is most likely right. With a budget of 2 submissions, take one program from the biggest cluster and one from the next.

program	outputs
`abs`	$2, 0, 3$
an `if x >= 0 else -x` version	$2, 0, 3$
`lambda x: x` (wrong for negatives)	$-2, 0, 3$
$\sqrt{x^2}$	$2.0, 0.0, 3.0$ (equal to $2, 0, 3$ )
$1 // x$ (crashes at 0)	$-1$ , error, $0$

Generated tests and property-based testing

Hand-written tests check a few examples. Property-based testing, introduced by QuickCheck (Claessen and Hughes, 2000), states a property ("sorting returns a permutation in non-decreasing order", "the fast version matches the slow reference") and checks it on hundreds of random inputs. Modern property-based testing tools also shrink a failing input to a minimal counterexample, which is what a developer, or a model, needs to fix the bug. Differential testing compares a candidate against a trusted but slow reference on random inputs: ideal for generated optimizations.

Example. The reference sorts a list; a generated "optimized" candidate returns sorted(set(xs)), which silently drops duplicates. A random test finds, in its first trial, the failing input [2, 0, -3, -2, -5, -5, -5]: seven numbers, hard to read. Shrinking removes one element at a time while the failure persists, and ends at [3, 3] for the input [3, -1, 4, 0, 5, 3]: two equal numbers, and the bug is obvious. (Replacing a nonzero value by 0 is also tried, so that a failing input may simplify to zeros when the values do not matter.)

Static analysis

Some problems are visible without running the code. Python's ast module parses source into an abstract syntax tree (the structure of the program, as a tree) that a program can walk: imports of os, subprocess or socket, calls to eval, exec or open, and access to attributes such as __subclasses__ (a classic way to escape a restricted namespace) can all be flagged before execution. This is the idea behind linters and security scanners such as Bandit, a tool designed to find common security issues in Python code. The need is real: Pearce et al. (2022) generated 1,689 programs with GitHub Copilot for security-relevant scenarios and found about 40% vulnerable.

Example. Scanning this source:
import os
x = eval(input())
y = ().__class__
from subprocess import run
finds, by line: 1: import os, 2: call eval, 3: dunder __class__, 4: import subprocess. The code is never run.

Static checks are fast and catch obvious cases, but they cannot prove code safe (getattr(__builtins__, "ev" + "al") is easy to write); they complement the sandbox, never replace it.

Beyond single functions

Real software work means repositories, not functions. SWE-bench (Jimenez et al., 2024) collects real GitHub issues from popular Python projects; a model must edit the repository so that the project's own tests, including the ones added by the real fix, pass. Agents (section 16) attack it with the loop of this section: read, edit, run the tests, read the failures, edit again.

References

M. Chen et al., Evaluating Large Language Models Trained on Code, arXiv, 2021. Codex, HumanEval and the unbiased pass@k estimator (Figure 3).
J. Austin et al., Program Synthesis with Large Language Models, arXiv, 2021. MBPP.
X. Chen, M. Lin, N. Schärli, D. Zhou, Teaching Large Language Models to Self-Debug, arXiv, 2023.
Y. Li et al., Competition-level code generation with AlphaCode, Science 378, 1092–1097, 2022. Section 4.6 of the arXiv version: clustering by behaviour.
B. Chen et al., CodeT: Code Generation with Generated Tests, arXiv, 2022.
K. Claessen, J. Hughes, QuickCheck: a lightweight tool for random testing of Haskell programs, ICFP, 268–279, 2000.
H. Pearce et al., Asleep at the Keyboard? Assessing the Security of GitHub Copilot's Code Contributions, IEEE Symposium on Security and Privacy, 2022.
C. E. Jimenez et al., SWE-bench: Can Language Models Resolve Real-World GitHub Issues?, ICLR, 2024.
Python documentation, ast — Abstract Syntax Trees.

Code Generation & Verification