Many applications of language models rely on the expectation of a test functional rather than on individual generated samples. Directly estimating this expectation often requires extensive sampling, leading to high computational cost. This paper shows how to exploit the next‑token conditional probabilities that are naturally produced during sampling by introducing potentials—real‑valued functions defined on prefixes—that decompose the test functional additively, enabling a more efficient estimator.
We first define a potential $\phi$ such that the original functional $f$ can be expressed as $f(x)=\sum_{t}\phi(x_{\le t})$. This decomposition yields an unbiased estimator whose variance depends on the chosen potential. Sufficient conditions under which a potential reduces variance are derived, namely
$$\mathrm{Var}[\hat{\mu}_{\phi}] \le \mathrm{Var}[\hat{\mu}_{\text{baseline}}]$$
Based on this theory, we construct practical potentials for various estimands—including sequence probability, expected BLEU, confidence scores, etc.—using linear potentials based on prefix probabilities and adaptive potentials derived from gradients. Experiments on several benchmark datasets compare the variance of different potentials against baseline sampling. Results demonstrate that, under equal computational budget, well‑designed potentials achieve several‑fold to ten‑fold variance reductions, substantially improving estimation accuracy.
Review: By cleverly leveraging conditional probabilities already available during sampling, the paper introduces potentials to control variance in expectation estimation, providing both theoretical insight and practical implementations. This framework offers a significant step forward for efficient evaluation of large autoregressive language models.