Exponential Minimum Sampling
8 min read
A language model chooses its next token using both its predicted probabilities and some randomness. Usually that randomness is discarded. If the model provider keeps it, could it help the provider recognize the generated text later?
A watermark can use a secret key to supply the sampling randomness. The chosen token is then correlated with numbers that a verifier holding the key can reconstruct. The verifier can test that relationship even when the text alone gives no such evidence. For the exponential sampler, averaging over the random key gives exactly the model’s token probabilities. A fixed key supplies the additional information that detection uses.
Scott Aaronson proposed using shared sampling randomness for a watermark [Aaronson, ’22]. Kuditipudi, Thickstun, Hashimoto & Liang developed the EXP scheme and its detector [KTHL, TMLR ’24].
An Exact Sample from Shared Draws
The answer starts with an ordinary sampling question: how do we draw a token from \(p\) using random numbers we supply, so that someone holding the same numbers can later tell what we drew? Fix a distribution \(p\) over a vocabulary of \(n\) tokens \(\{1, \dots, n\}\) with positive probabilities \(p_1, \dots, p_n\) summing to one (tokens with zero probability can be omitted). Draw \(E_1, \dots, E_n\) independently from \(\mathrm{Exp}(1)\), one per token, and output
\[ \arg\min_{i} \; \frac{E_i}{p_i}. \]
Dividing by \(p_i\) shrinks the values of likely tokens, so they are more often the minimum, and the claim is that this happens with exactly the right frequency.
Claim: for independent \(E_1, \dots, E_n \sim \mathrm{Exp}(1)\) and any distribution \(p\) with positive entries, every token \(i\) satisfies
\[ \Pr\Big(\arg\min_j \frac{E_j}{p_j} = i\Big) = p_i. \]
Proof
An \(\mathrm{Exp}(\lambda)\) random variable has tail \(\Pr(E \ge s) = e^{-\lambda s}\) and mean \(1/\lambda\). Dividing an \(\mathrm{Exp}(1)\) draw by \(p_i\) changes its rate, which we read off from the tail:
\[ \Pr(E_i / p_i \ge s) = \Pr(E_i \ge p_i s) = e^{-p_i s}, \]
so \(E_i / p_i \sim \mathrm{Exp}(p_i)\), with density \(p_i\, e^{-p_i u}\) at \(u\). We prove the slightly stronger statement that for every token \(i\) and every \(s \ge 0\),
\[ \Pr\Big(\arg\min_j E_j/p_j = i \ \text{ and } \ \min_j E_j/p_j \ge s\Big) = p_i\, e^{-s}. \]
The event on the left holds exactly when \(E_i/p_i\) takes some value \(u \ge s\) and every other \(E_j/p_j\) exceeds \(u\), which happens with probability \(e^{-p_j u}\) each, independently. Integrating the density of \(E_i/p_i\) against those tail probabilities:
\[\begin{align} & \Pr\big(i \text{ is the argmin and the minimum is at least } s\big) \\ &= \int_s^\infty p_i\, e^{-p_i u} \prod_{j \ne i} e^{-p_j u} \, du \\ &= \int_s^\infty p_i\, e^{-p_i u}\, e^{-\sum_{j \ne i} p_j u} \, du \\ &= p_i \int_s^\infty e^{-\left(\sum_j p_j\right) u} \, du \\ &= p_i \int_s^\infty e^{-u} \, du \\ &= p_i\, e^{-s}, \end{align}\]
where we first collected the competitors’ exponents, then included token \(i\)’s rate so the sum runs over every \(j\), and finally used \(\sum_j p_j = 1\). Setting \(s = 0\) gives the claim.
The proof gave more than the claim. The joint probability \(p_i \cdot e^{-s}\) is a function of \(i\) times the \(\mathrm{Exp}(1)\) tail \(e^{-s}\), so the argmin and the minimum are independent, and the minimum \(\min_j E_j/p_j\) is \(\mathrm{Exp}(1)\) whatever \(p\) is. Detection will use both facts.
In the plot, one set of five draws \(E_a, \dots, E_e\) is divided by two different distributions over the same tokens. The same draws give different samples under \(p\) and \(q\), and each is an exact sample of the distribution it was divided by.
Randomness a Verifier Can Reproduce
A language model at step \(t\) produces a next-token distribution \(p_t\) over the vocabulary, conditioned on everything generated so far. Ordinary sampling draws fresh randomness at each step and throws it away. Instead, we need draws \(E_{t,1}, \dots, E_{t,n} \sim \mathrm{Exp}(1)\) for every step \(t\) that we can produce twice: once at generation time and once at detection time. Any pseudorandom generator seeded with a secret key does this; the generator expands the key into the \(E_{t,i}\) on demand, and whoever holds the key can regenerate them. Scott Aaronson described this scheme in a 2022 lecture, and Kuditipudi, Thickstun, Hashimoto & Liang [KTHL, TMLR ’24] analyzed the version where the key is a fixed sequence indexed by position.
Generation at step \(t\) is deterministic given the key:
\[ x_t = \arg\min_{i} \; \frac{E_{t,i}}{p_t(i)}. \]
Marginalized over the key, the \(E_{t,i}\) are independent \(\mathrm{Exp}(1)\) draws, so by the claim \(x_t\) is an exact sample from \(p_t\), and the generated text is equal in distribution to ordinary sampling. This is the distortion-free property (Theorem 2 in [KTHL, TMLR ’24]): watermarked and unwatermarked text have the same distribution, so the quality cost is exactly zero. Exactness holds as long as no draw \(E_{t,i}\) is reused, so the guarantee comes with a generation budget, the length of the key; a random starting offset into the key keeps repeated queries from replaying the same text.
Detection
A verifier holds the key and a text \(y_1, \dots, y_m\), with no model and no prompt, and asks whether the text was generated with the key. It cannot rerun generation, since that needs \(p_t\). What it can do is regenerate the draws and read off the one each token points to, \(E_{t, y_t}\). For text produced with the key, those draws are small.
Claim: if \(x = \arg\min_j E_j/p_j\) for independent \(E_1, \dots, E_n \sim \mathrm{Exp}(1)\), then
\[ \mathbb{E}\big[E_x \,\big|\, x\big] = p_x, \]
while an index \(i\) chosen without reference to the draws has \(\mathbb{E}[E_i] = 1\).
Proof
The argmin achieves the minimum, so \(E_x / p_x = \min_j E_j/p_j\), and multiplying through by \(p_x\),
\[ E_x = p_x \cdot \min_j \frac{E_j}{p_j}. \]
The minimum is \(\mathrm{Exp}(1)\) and independent of \(x\), so its mean given \(x\) is \(1\):
\[ \mathbb{E}\big[E_x \,\big|\, x\big] = p_x \cdot \mathbb{E}\Big[\min_j \tfrac{E_j}{p_j}\Big] = p_x \cdot 1 = p_x. \]
An index chosen without reference to the draws leaves \(E_i\) a plain \(\mathrm{Exp}(1)\) variable with mean \(1\).
Applied at every step, the mean of \(E_{t, y_t}\) over a watermarked text is about \(\frac{1}{m}\sum_t p_t(y_t)\), which is at most \(1\), while over text written without the key it is about \(1\). The detector computes the average draw and flags the text when it falls far enough below \(1\). The per-token evidence is the gap \(1 - p_t(y_t)\), so the signal comes from the model’s entropy. Where the model is uncertain the gap is wide; where it is confident, \(p_t(y_t)\) is near \(1\) and there is almost no signal. No distortion-free scheme can do better, because a deterministic model emits the same fixed string with or without a key. On Alpaca-7B, whose instruction responses are low-entropy, only about a quarter of responses of median length around 100 tokens are detectable at \(p\)-value \(0.01\).
In the plot below, a synthetic model draws each next-token distribution \(p_t\) as a softmax of Gaussian logits over a 50-token vocabulary, a choice that spreads the per-step entropy instead of fixing one confidence level. The average draw separates 35-token watermarked texts from unwatermarked ones at the one-percent threshold.
Real text does not arrive aligned with the key: the user crops the prompt, edits words, or splices the generation into their own writing, and then the verifier no longer knows which step \(t\) each token came from. [KTHL, TMLR ’24] score the text against every shift of the key and keep the best alignment, taking the \(p\)-value from a permutation test over fresh random keys; on OPT-1.3B and LLaMA-7B this still detects 35-token texts after 40 to 50 percent of the tokens are corrupted.
Aaronson’s lecture instead derives the step-\(t\) draws by hashing the previous few tokens together with the secret key. That makes detection alignment-free, since the verifier recomputes the draws straight from the text, but hashing reuses randomness: the same context always produces the same draws, which biases the text toward particular phrases ([KTHL, TMLR ’24] show sampled lists repeating themselves on prompts like “give me a list of 20 movies”), and editing any single token in a hash window destroys the signal for the token that follows it.
Where the Sample Appears
Aaronson’s variant was prototyped inside OpenAI by the engineer Hendrik Kirchner, and [KTHL, TMLR ’24] released code and an in-browser detector for the fixed-key scheme.
The argmin is the Gumbel-max trick after a change of variables: \(G_i = -\ln E_i\) has CDF \(\Pr(G_i \le g) = \Pr(E_i \ge e^{-g}) = e^{-e^{-g}}\), a standard Gumbel, and \(\arg\min_i E_i/p_i = \arg\max_i (\ln p_i + G_i)\). In that form it powers reparameterized discrete sampling, where a categorical draw becomes an argmax over noised log-probabilities that can be softened to let gradients through, and it resurfaces as a differential privacy mechanism. Maddison, Tarlow & Minka [MTM, NeurIPS ’14] push it to continuous spaces as A* sampling, which turns drawing from a continuous distribution into an optimization problem.