For every $\varepsilon>0$ and positive integer $k$, and all sufficiently large $s$ and then $w$, each purported long code $A$ has a set $S$ of at most $2^{\varepsilon s}$ words such that the CNA test, except with probability $2^{-ks}$, either rejects or agrees with evaluation at a word in $S$. This is Theorem 4.2 of Håstad's paper.

The stronger Theorem 4.17 uses the same quantifiers and a set $S$ chosen independently of the side condition $h$. For every $h$, except with the same probability, the extended test rejects or agrees with evaluation at some $x\in S$ satisfying $h(x)$.

The probability is uniform over the $s$ independently chosen Boolean functions. The thresholds for $s$ depend only on $\varepsilon,k$; the threshold for $w$ may additionally depend on $s$. Both statements concern arbitrary tables, without assuming they are genuine long codes.