Watermarking runif | Minimally Sufficient
We’re currently getting to a point where it’s very hard to tell if the<br>content you’re consuming is AI-generated.
This is in the news lately as the EU’s AI Act requires that users must<br>be informed when content is AI-generated. In particular “providers of<br>generative AI systems —1 producing<br>text, images, audio, video — must mark outputs in a machine-readable<br>format and ensure they are detectable as artificially generated or<br>manipulated.”
This is basically watermarking: embedding a signal into the output<br>that identifies2 the model that created it. It’s straightforward<br>to naively achieve this for images: this is the realm of steganography<br>with hiding information in the lowest value pixels. Text however would<br>seem to be a much harder challenge due to its discreteness: there<br>aren’t any low value bits to manipulate (or so it would seem).
There’s a number of approaches3<br>out there but I prefer thinking of watermarking as a form of<br>statistical test. And to make it clear what’s happening though I’ll<br>work with a familiar process for a statistician: a series of draws<br>from a Uniform(0, 1) distribution.
Basics of Watermarking#
For our purposes we’ll define four desiderata in escalating order of<br>difficulty:
Detection probability<br>Can we even recover the fact that we<br>generated this sequence? We’ll use a fixed length of 100<br>observations though we’ll later investigate exactly how much data we<br>need for reasonable detection probabilities.<br>Adversarial detection probability<br>Suppose our sequence is going<br>to be modified after the fact. Can we still detect that the original<br>sequence was generated? We’ll use a weak version: you get random<br>edits on a subset of the data. The stronger version: where your<br>adversary gets access to the detector itself is mostly hopeless.<br>Multi-shot distribution<br>Suppose we prompt it multiple times: is<br>it indistinguishable from an unaltered distribution?<br>Low false positive rate<br>We’ve been caring about \(P(\text{detect}<br>\mid \text{watermarked})\) but we also need to consider<br>\(P(\text{detect} \mid \text{unwatermarked})\). This is the standard<br>type I error and we’ll want to be able to control it at a fairly low<br>rate4 (\(\alpha=0.001\))
We’ll also take as table stakes that the unconditioned distribution of<br>the sequence must be unaltered. There’s two versions marginal equality<br>(each value has the right distribution) and joint equality (the<br>sequence has the right distribution). This is actually a rather hard<br>constraint: “distortion-free” methods are not always practical and<br>thus some papers accept controlled level of distortion in order to<br>boost detectability.
We can evaluate these desiderata with the following code
using Random, Statistics, Distributions
# Randomly perturb a subset of elements to mimic "editing"<br>function adversarial_manipulation(seq, resample_rate = 0.1)<br>new_seq = copy(seq)<br>for ii in eachindex(seq)<br>if rand() resample_rate<br>new_seq[ii] = mod(new_seq[ii] + 0.02 * (rand() - 0.5), 1)<br>end<br>end<br>return new_seq<br>end
# Two-sided one-sample Kolmogorov–Smirnov test against Uniform(0, 1).<br>function ks_uniform_pvalue(x)<br>n = length(x)<br>xs = sort(x)<br>dplus = maximum((1:n) ./ n .- xs)<br>dminus = maximum(xs .- (0:n-1) ./ n)<br>D = max(dplus, dminus)<br>return ccdf(Kolmogorov(), sqrt(n) * D)<br>end
# Joint uniformity: consecutive draws should fill the unit square evenly.<br>function joint_uniform_pvalue(x; grid = 5)<br>counts = zeros(Int, grid, grid)<br>for i in 1:length(x)-1<br>a = clamp(floor(Int, grid * x[i]) + 1, 1, grid)<br>b = clamp(floor(Int, grid * x[i+1]) + 1, 1, grid)<br>counts[a, b] += 1<br>end<br>e = (length(x) - 1) / grid^2<br>return ccdf(Chisq(grid^2 - 1), sum((counts .- e) .^ 2 ./ e))<br>end
function run_suite(gen, n_samples = 100, n_trials = 1000; α = 0.001, resample_rate = 0.1, pool = 25, seed = 0)<br>Random.seed!(seed)<br>watermarked = [runif(gen, n_samples) for _ in 1:n_trials]<br>unmarked = [rand(n_samples) for _ in 1:n_trials]
detection_prob = mean(detect(gen, w; α) for w in watermarked)<br>adversarial_prob = mean(detect(gen, adversarial_manipulation(w, resample_rate); α) for w in watermarked)<br>false_positive = mean(detect(gen, u; α) for u in unmarked)
marginal_reject = mean(ks_uniform_pvalue(w) α for w in watermarked)<br>nblocks = fld(n_trials, pool)<br>pooled(b) = reduce(vcat, watermarked[(b-1)*pool+1:b*pool])<br>multishot_reject = mean(ks_uniform_pvalue(pooled(b)) α for b in 1:nblocks)<br>joint_reject = mean(joint_uniform_pvalue(pooled(b)) α for b in 1:nblocks)
return (; detection_prob, adversarial_prob, false_positive, marginal_reject, multishot_reject, joint_reject)<br>end
Seeded Generators#
The first obvious solution is using a seed. If you can generate the<br>same sequence using a fixed seed it’s extremely strong evidence that<br>it was generated by your process.
struct SeededWatermark<br>seed::Int<br>end
function runif(gen::SeededWatermark, n)<br>return...