If a language model can be coaxed into hiding bits inside its word choices, token ordering, or punctuation patterns, the text it generates stops being output and starts being a channel. A March 2026 preprint on arXiv now gives defenders a theoretical foothold: any steganographic embedding that preserves meaning must inflate text complexity by a measurable amount, and that inflation is detectable with a perplexity-based proxy. The catch is that detection and evasion are adversarial. The result raises the cost of naive smuggling; it does not close the channel.
What the theorem actually says
The paper proves a lower bound rooted in Kolmogorov complexity, the information-theoretic measure of the shortest program that can produce a given string. Formally: for any lossless, semantic-preserving steganographic encoding, the complexity of the stegotext must satisfy K(stegotext) ≥ K(covertext) + K(payload) − O(log n), where n is the combined length of covertext and payload.
The intuition is straightforward. Hiding information inside otherwise-normal text requires the text to encode two things at once: the original meaning and the hidden payload. Any scheme that does this without distorting the surface meaning still has to find room for those extra bits somewhere, and that somewhere is the compressibility of the output itself. A corollary makes this sharper: for any non-trivial payload where K(P) is much larger than log n, the stegotext is strictly more complex than the covertext, no matter how clever the encoder is about distributing the signal.
This is an impossibility result, not a heuristic. Future encoders can try to minimize the complexity penalty, but they cannot make it vanish for non-trivial payloads.
Why perplexity works as a detector proxy
Kolmogorov complexity is uncomputable; you cannot evaluate it directly on arbitrary strings. The paper’s practical contribution is arguing that language model perplexity serves the same structural role as compression length does in classical Kolmogorov estimation. If stegotext is more complex than clean text, a language model should assign it higher perplexity on average, because the model’s training objective is to minimize surprise on natural text, and steganographic perturbations are, by the theorem, surprising.
This reframes steganalysis as a variant of the already well-studied problem of detecting machine-generated text, except the signal is weaker and the adversarial stakes are higher.
Binoculars perplexity-ratio as a detection proxy
To test the complexity proxy, the authors propose the Binoculars perplexity-ratio score. The detector computes this score on suspected stegotext and compares it against a baseline distribution for clean text from the same model, asking whether the text carries more complexity than its surface meaning requires.
The approach requires no access to the steganographic encoder, no knowledge of the encoding scheme, and no labeled examples of stegotext. It is a zero-shot detector in the strict sense.
The 300-sample validation and its limits
The authors test the Binoculars perplexity-ratio proxy against a color-based LLM steganographic scheme across 300 samples. A paired t-test yields t = 5.11 with p < 10⁻⁶, confirming that the perplexity distribution of stegotext is statistically distinguishable from that of clean text. The result validates the theoretical prediction: the complexity increase imposed by the theorem is real and measurable.
The limitations are significant. A color-based scheme is among the simpler encoding strategies. More sophisticated encoders can distribute bits across longer-range dependencies, use syntactic reordering, or encode information in whitespace and punctuation patterns that have smaller effects on perplexity. The paper does not report false-positive rates on idiosyncratic but clean human text. A detector that flags verbose or unusual writing as steganographic would be unusable in production.
The 300-sample size is adequate for establishing statistical significance of the effect but says little about detection robustness across encoding families, model sizes, or domains.
The adversarial framing: cost vs. closure
The paper is explicit about what it does not prove. It does not claim that steganography is detectable in general. The defense problem is adversarial: as models grow more capable, the bandwidth and subtlety of steganographic channels increase, and an encoder that knows the detector’s proxy can optimize against it. The authors frame their contribution as establishing a fundamental lower bound that any encoder must contend with, and providing a practical detector that catches naive implementations.
This is the correct framing. A static detector raises the floor. It forces the encoder to spend more of the complexity budget on evading detection, which means less bandwidth for the payload, which means the steganographic channel is slower and noisier. But a determined adversary with a strong model and knowledge of the detector can likely find encodings that stay below the perplexity threshold for short payloads. The channel is degraded, not eliminated.
The broader landscape of LLM output-channel security
The steganography question sits inside a larger problem: LLM outputs are increasingly treated as trusted inputs to downstream systems, and the security assumptions around that trust are weak.
The iSeal paper, presented as a poster at AAAI 2026, illustrates the adjacent problem of model fingerprinting. iSeal shows that traditional LLM fingerprinting methods achieve near-0% verification success under end-to-end attacks using collusion-based unlearning and response manipulation. The implication is that even if you can detect that something is wrong with a model’s output, proving which model produced it, or that it was the model you intended, is a separate and largely unsolved challenge.
Related work on security operations, such as OpenSOC-AI, focuses on using LLMs to analyze logs rather than on securing the LLM output channel itself. The gap between “using LLMs for security” and “securing LLM outputs” is where the steganography detection work lands. Most deployment security assumes the threat comes from the prompt. The steganography literature reminds practitioners that the threat can also come from the response.
What changes for pipeline builders
For engineering teams piping LLM output into RAG systems, agentic workflows, or automated decision pipelines, the practical implications are specific.
First, any system that passes generated text to a downstream parser, database, or agent without validation is exposed to a channel that can carry hidden payloads. The payloads could be instructions to downstream agents (prompt injection via the output channel), exfiltrated data encoded in word choices, or coordination signals between compromised model instances.
Second, the Kolmogorov bound means this channel cannot be made invisible. If you monitor complexity, you can catch the low-effort versions. Perplexity-based detectors like the Binoculars proxy are computationally cheap to run alongside existing output pipelines; they require only perplexity scoring, not a full re-encoding of the output.
Third, the adversarial nature of the problem means detection is an ongoing cost, not a one-time fix. As encoders adapt, detectors need to adapt with them. The theoretical lower bound is permanent; the practical detection threshold is not.
The honest summary: the Kolmogorov-complexity result gives defenders something they did not have before, which is a proof that the steganography problem is detectable in principle and a proxy that works against simple encoders in practice. The gap between “detectable in principle” and “detectable in production against motivated adversaries” remains wide. Closing it will require more than one paper.
Frequently Asked Questions
What compute does the Binoculars proxy need to run against live LLM output?
The Quadroculars detector runs two model passes per checked output: Falcon-7B computes scoring perplexity and Falcon-7B-Instruct computes reference perplexity, then the ratio is compared against a clean-text baseline. Teams already serving 7B-class models can add this as a sidecar scoring step with roughly 2x the inference cost of a single forward pass per output.
What kinds of clean text risk false positives under perplexity-based steganalysis?
The paper does not report false-positive rates, a notable gap. Text with high lexical diversity, frequent code-switching between languages, domain jargon the scoring models have not seen, or deliberately creative prose would all register higher perplexity. The Binoculars score inherits the same false-positive surface documented in AI-text detection work: any text that surprises the scoring model looks suspicious, and not all surprising text is steganographic.
How does this detection approach differ from model fingerprinting methods like iSeal?
Fingerprinting asks which model produced an output; the Kolmogorov approach asks whether an output carries hidden data. They are separate problems and both are contested. iSeal’s AAAI 2026 results show traditional fingerprinting collapses to near-0% verification under collusion-based unlearning and response manipulation attacks. Steganography detection does not require identifying the source model, which makes it a narrower but potentially more robust signal.
Does the complexity bound still hold if the encoder hides bits in whitespace or Unicode homoglyphs rather than word choices?
The Kolmogorov theorem applies to any lossless semantic-preserving encoding regardless of channel, so the bound holds. The perplexity proxy, however, becomes a weaker detector for non-lexical channels. Whitespace padding and Unicode homoglyph substitution do not shift token-level perplexity the way word-choice perturbations do, so a comprehensive detector would need supplementary checks beyond perplexity scoring to catch those encodings.