Exponential Minimum Sampling
11 min read
Attach an exponential clock to every token in a vocabulary, speed each clock up in proportion to its token’s probability, and the token whose clock rings first is an exact sample from the distribution. In a November 2022 lecture at UT Austin, Scott Aaronson [Aaronson, ’22] proposed running language model sampling this way, with the clocks derived pseudorandomly from a secret key, so a model provider could later recognize its own text. Every other watermark I knew of degrades text quality somewhere to become detectable. Kuditipudi, Thickstun, Hashimoto & Liang [KTHL, TMLR ’24] turned that proposal into the EXP watermark: they fixed the key, added an alignment-based detector, and proved the result is distortion-free, meaning watermarking costs exactly zero quality. There is no catch.
The Race
That claim needs a proof: the clocks are drawn with no reference to each other, so it is not obvious why the winner comes out distributed exactly as \(p\) rather than merely favoring likely tokens. Fix a distribution \(p\) over a vocabulary of \(n\) tokens \(\{1, \dots, n\}\), with probabilities \(p_1, \dots, p_n\) summing to one. Recall that an \(\mathrm{Exp}(\lambda)\) random variable has tail \(\Pr(E \ge s) = e^{-\lambda s}\) and mean \(1/\lambda\); think of it as a clock that rings at rate \(\lambda\). Draw \(E_1, \dots, E_n\) independently from \(\mathrm{Exp}(1)\), one clock per token, and race the scaled clocks \(E_i / p_i\).
Dividing a clock by its probability speeds it up, and we can read off the new rate from its tail:
\[ \Pr(E_i / p_i \ge s) = \Pr(E_i \ge p_i s) = e^{-p_i s}. \]
That is the tail of an exponential with rate \(p_i\):
\[ E_i / p_i \sim \mathrm{Exp}(p_i). \]
A likely token has a large \(p_i\), so it runs a fast clock.
The race is a classic in disguise: competing exponential clocks ring in proportion to their rates, and we chose the rates to be the probabilities themselves. With two tokens, token 1’s clock runs at rate \(p_1\) against token 2’s at rate \(p_2\), so it rings first with probability equal to its share of the total rate, \(p_1/(p_1 + p_2)\). The rates sum to one, so token 1 wins with probability exactly \(p_1\). The claim below is the same statement for any number of lanes, proved from scratch, with the finish time pinned down as well.
Claim: the token whose clock rings first is distributed exactly as \(p\). More precisely, for every token \(i\) and every time \(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 left side asks for two things at once: token \(i\) wins, and no clock rings before time \(s\). Both hold exactly when token \(i\)’s clock rings at some \(u \ge s\) while every other clock is still running, so condition on that ring time \(u\). Token \(i\)’s clock \(E_i/p_i \sim \mathrm{Exp}(p_i)\) has density \(p_i\, e^{-p_i u}\), and each competitor \(j\) is still running with probability \(\Pr(E_j/p_j \ge u) = e^{-p_j u}\). Multiplying the winner’s density by the competitors’ independent survival probabilities and integrating over \(u\):
\[\begin{align} & \Pr\big(i \text{ wins, no earlier than } 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 into a single exponential, then folded in token \(i\)’s own rate so the sum runs over every \(j\), and finally used \(\sum_j p_j = 1\), so the whole field of clocks decays at the single combined rate of one. Setting \(s = 0\) leaves the sampling claim on its own:
\[ \Pr\big(\arg\min_j E_j/p_j = i\big) = p_i, \]
so token \(i\) wins with probability exactly \(p_i\), for any distribution \(p\).
In the plot, one draw of five clocks is raced under \(p\) and again under a second distribution \(q\) over the same tokens: a lane’s length is its finish time, and its thickness is that token’s probability in the race shown. The same draws produce different winners under \(p\) and \(q\), yet each winner (teal) is an exact sample of the distribution it faces.
(The same race 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)\). It resurfaces as a differential privacy mechanism, and Maddison, Tarlow & Minka [MTM, NeurIPS ’14] push it to continuous spaces as A* sampling.)
Come back to the claim. It says more than which token wins: the right-hand side is a function of \(i\) times a function of \(s\), and each factor is a probability we have already met:
\[ \Pr\Big(\arg\min_j E_j/p_j = i \ \text{ and } \ \min_j E_j/p_j \ge s\Big) = \underbrace{p_i}_{\Pr(\text{winner}=i)} \cdot \underbrace{e^{-s}}_{\Pr(\min \ge s)}. \]
A joint probability that splits into the product of its marginals means the two are independent: the winner’s identity and the winning time tell you nothing about each other. The second factor \(e^{-s}\) does not mention \(p\), so the race always finishes in an \(\mathrm{Exp}(1)\) time however the probability is split across the lanes. This independence is the whole case for the detector below.
The Watermark
The race is a sampler, and a sampler proves nothing: handed the text, a verifier sees a draw from \(p\) and cannot tell which model produced it. 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. The EXP scheme keeps that randomness instead, and shares it with the verifier in advance.
The watermark key is a pseudorandom sequence \(\xi_1, \xi_2, \dots\), with each \(\xi_t\) uniform on \([0,1]^n\) and expanded from a short secret seed the verifier also holds; the sequence itself runs much longer than anything you plan to generate. A uniform coordinate becomes an exponential clock under a negative log, again read off from the tail:
\[ \Pr(-\ln \xi_{t,i} \ge s) = \Pr(\xi_{t,i} \le e^{-s}) = e^{-s}, \]
so \(-\ln \xi_{t,i} \sim \mathrm{Exp}(1)\). At step \(t\), decode deterministically by running the race on the \(t\)-th key vector:
\[ x_t = \arg\min_{i} \; \frac{-\ln \xi_{t,i}}{p_t(i)}. \]
Read this decode rule two ways, depending on whether the key is random or fixed.
Marginalized over the key, step \(t\) is exactly the race of the previous section, with \(-\ln \xi_{t,i} \sim \mathrm{Exp}(1)\) playing the role of \(E_i\). So \(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 guarantee (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 key coordinate is reused, so the guarantee comes with a generation budget, the key’s length; a random starting offset into the key keeps repeated queries from replaying the same text.)
Conditioned on the key, the same text is conspicuous. The winner \(x_t\) is the token that achieves the minimum, so its own scaled clock is that minimum:
\[ \frac{-\ln \xi_{t,x_t}}{p_t(x_t)} = \min_i \frac{-\ln \xi_{t,i}}{p_t(i)}. \]
Multiplying through by \(p_t(x_t)\) rewrites the winner’s raw coordinate as its probability times the winning time:
\[ -\ln \xi_{t,x_t} = p_t(x_t) \cdot \min_i \frac{-\ln \xi_{t,i}}{p_t(i)}. \]
Now take the expectation given which token won. By the factorization the winning time is \(\mathrm{Exp}(1)\) independent of the winner, so its conditional mean is just \(1\):
\[ \mathbb{E}\big[-\ln \xi_{t,x_t} \,\big|\, x_t\big] = p_t(x_t) \cdot \mathbb{E}\Big[\min_i \tfrac{-\ln \xi_{t,i}}{p_t(i)}\Big] = p_t(x_t) \cdot 1 = p_t(x_t). \]
A coordinate picked without reference to the key is just a fresh uniform draw, and \(-\ln \xi_{t,i}\) averages \(1\) instead. So the winning coordinate is pulled below that baseline by exactly the factor \(p_t(x_t) \le 1\); equivalently \(\xi_{t,x_t}\) itself sits close to \(1\).
The per-token evidence is the size of that gap, \(1 - p_t(x_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(x_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. (This shows up in practice: 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\).) Detection has to add those gaps across a document, without the model.
Detection Without the Model
The gap \(1 - p_t(x_t)\) is the evidence, and the verifier cannot compute a single term of it: holding the key and a text of \(m\) tokens \(y_1, \dots, y_m\), with no model and no prompt, it never sees any \(p_t\). What it can read is the key coordinate each token points to. The natural score sums them, the alignment cost:
\[ \mathrm{cost}(y) = \sum_{t=1}^{m} -\ln \xi_{t, y_t}. \]
The previous section computed each term’s mean under the two competing hypotheses:
\[ \mathbb{E}\big[-\ln \xi_{t, y_t}\big] = \begin{cases} p_t(y_t) \le 1 & \text{if } y \text{ is watermarked},\\ 1 & \text{if } y \text{ is independent of the key}. \end{cases} \]
So watermarked text has a systematically smaller alignment cost, and the detector flags any text whose cost falls far enough below \(m\). (In practice [KTHL, TMLR ’24] follow Aaronson and score \(\ln(1 - \xi_{t,y_t})\) instead, which rewards coordinates near one more aggressively; the logic is identical.) 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 per-token alignment cost cleanly separates 35-token watermarked documents from unwatermarked ones.
Real text does not arrive aligned: the user crops the prompt, swaps words, splices the generation into their own writing. So the detector never assumes the text positions line up with the key positions. It compares every block of the text against every shift of the key and keeps the best alignment. The strongest variant, EXP-edit, scores each candidate alignment with an edit-distance dynamic program that charges a penalty for every insertion or deletion, so the statistic survives substitutions, insertions, deletions, and cropping. The search costs time quadratic in the block size and linear in both the text and the key length.
Significance comes from a permutation test: recompute the same best-alignment score against fresh random keys, and report the true key’s rank as the \(p\)-value. By symmetry this \(p\)-value is valid whatever statistic you choose, so the race math only affects the test’s power, never its validity. The result is robust: on OPT-1.3B and LLaMA-7B, watermarked text is reliably detected (\(p \le 0.01\)) from 35 tokens even after randomly corrupting 40–50% of them, and stays detectable from 50 tokens after round-trip machine translation through French. Translating through Russian instead is the harder attack: no variant other than EXP-edit reliably reaches \(p < 0.05\) there, however long the text.
Why a fixed key rather than Aaronson’s original proposal? His scheme derives \(\xi_t\) by hashing the previous few tokens together with the secret key. That makes detection alignment-free: the verifier recomputes each \(\xi_t\) straight from the text. The catch is that hashing reuses randomness. The same context always produces the same clocks, and that biases the text toward particular phrases ([KTHL, TMLR ’24] show the bias plainly on prompts like “give me a list of 20 movies”, where sampled lists repeat themselves). Editing any single token in a hash window also destroys the signal for the token that follows it. The fixed key and the alignment search recover both missing properties, distortion-freeness and robustness. That leaves a paradox: the detector works, and the text it flags is distributed exactly like text written with no key.
The Sample and the Signature
The resolution is that the watermark was never in the text. Distortion-freeness means watermarked text is equal in distribution to ordinary samples, so a detector that reads the text alone has nothing to find. What detection checks is a correlation between the text and a secret the verifier already holds. It is a statement about that pair rather than about the prose.
Concretely, Aaronson’s variant was prototyped inside OpenAI by the engineer Hendrik Kirchner [Aaronson, ’22], and [KTHL, TMLR ’24] released code and an in-browser detector for the fixed-key scheme. The race shows up well outside watermarking. As the Gumbel-max trick it powers reparameterized discrete sampling, where a categorical draw becomes an argmax over noised log-probabilities that can be softened to let gradients through. As A* sampling it turns drawing from a continuous distribution into an optimization problem. The general lesson: a sample and a signature can be the same draw, as long as you keep the randomness that produced it.