Today, for each output token the LLM produces a probability for each possible output, then a 'sampler' makes a probability-weighted random choice. If the next-token probabilities are 90% for foo, 9% for bar and 1% for baz then the sampler chooses a random number between 0 and 1, if it's <0.9 it outputs foo, 0.9-0.99 it outputs bar, 0.99-1 it outputs baz.
But what if instead of using random numbers, you had a source of evenly distributed random numbers that was deterministic, based on some secret key?
Each candidate token would remain just as likely as it was before - there would still be a 90% chance of foo being chosen. So the output shouldn't degrade in quality.
And sure, some tokens will have 99.999% probability and their selection doesn't tell you much. But in most real-world use multiple wordings are possible and so on. So across a large enough sample of the output, you could detect whether the sampler was following your secret deterministic pattern.
Of course the downside is you've got to check on exactly the same LLM, and only people with the secret key can perform the check. And it's only applicable to closed-source LLMs.
I'm also not quite sure if it works when you don't know the exact prompt - so maybe my understanding of the paper is all wrong?