covert communication · llm agents
Feedback coding embeds hidden payloads in agentic dialogue at ≈0.2 bits/token and <0.3% message error — distortion-free, provably secure, and requiring no shared model or prompt.
Running example: two agents play a full game of chess through the covert channel beneath an ordinary chat.
the gap
Our algorithm Burnashev Adaptive Posterior Matching (BAM) Steganography closes that gap on three fronts at once: reliability, security, and rate. The BAM algorithm is designed for conversational steganography, not watermarking application, but our algorithm outperforms current multi-bit watermark on the same setting by a wide margin.
At a matched embedding budget, BAM drives message-error probability roughly an order of magnitude below every baseline, and it keeps falling toward zero as a few more tokens become available — while fixed-budget watermarking schemes plateau at high error on short, low-entropy conversational turns. The gain is consistent across Llama-3.1-8B, Qwen3.5-9B-Base, and Mistral-7B.
references
prior work vs. this work
Embedding signal in LLM output isn't new. Doing it on ordinary, variable-length conversation — where the receiver shares no model or prompt and reads only text — is where existing schemes fall short. As shown before, most inference-time schemes were designed as watermarks — a signal stamped onto generated text. Ours is designed as a channel: a variable-length feedback code that carries a message reliably over whatever the conversation happens to produce.
the setting
In the absence of editting, both parties see the same channel outputs. That makes the conversation a channel with perfect feedback — which is the source of embedding gain. The walkthrough below shows the whole scheme end to end; the full formalism is in the paper.
method — detail
No shared model or prompt, low-entropy text, LLM generation with unpredictable length, distortion-free and undetectablility. Here is each obstacle in the order the protocol resolves it — and the mechanism that does the work.
The receiver has no token probabilities, no prompt, and no model in hand. It must read back the transmitted symbol using shared transcript and the seed
Following ArcMarkiArcMark: tokens and symbols placed on a unit circle, sampling biased by angular distance., every token and every message symbol sits on a unit circle: the seed assigns each token an angle, and the target symbol defines a target angle. To transmit it, the encoder solves an optimal-transport couplingiConstrained coupling, solved via Sinkhorn: nudges toward the target angle while preserving the base marginal. that picks a token whose angle lands near the target while preserving the model's own word statistics. The receiver re-derives that angle from the token and seed — no model in the loop. That same statistics-preserving property is what buys security in Challenge 04.
A real LLM generated conversational have arbitrary generation length (we don't assume any form of prompt tuning). A fixed codeword with a preset budget breaks both ways — it fails when the turn stops short and can't exploit one that keeps going.
Instead of a codebook fixed in advance, the encoder builds online codebook: at each step it maps the message to the next symbol against the decoder's current belief, and both parties update that belief token by token. The belief is shared there's no preset budget — the protocol simply keeps generating while uncertain and stops the moment the belief is confident enough. That variable stopping time is the sequentiality gain.
Posterior matching localizes the message, but it does not improve the decoding error exponent by itself. The leading candidate can be confident and wrong. Embedding rate alone doesn't characterize a scheme: error exponent characterize the rate at which decoding error decays asymptotically.
Once one candidate dominates, BAM stops localizing and starts verifying: it treats confirmation as a simple binary hypothesis test and re-transmits confirmation symbols before committing. This adaptivity gain is what classical feedback coding uses to push decoding error down at a given rates.
Every one of those biased tokens must leave no statistical trace — nothing a passive monitor could learn to catch, and nothing an adaptive API adversary could distinguish from ordinary generation.
The coupling from Challenge 01 preserves the base model's next-token distribution exactly, so averaged over the secret key the observable text carries precisely the model's own word statistics — no distortion for a monitor to latch onto. A keyed, nonce based pseudorandom function, supplies the per-token side information, and a cryptographic reduction makes the whole transcript provably indistinguishable from ordinary generation for any polynomial-time adversary.
The upshot: no efficient test on the visible text does better than a coin flip. The full theorem and proof are in the paper.
does it work
Far more reliable. Across three language models our algorithm offers about 98% drop in error rate at same embedding rate, compared to current baselines.
Provably secure. The transcript is computationally indistinguishable from ordinary generation for any polynomial-time adversary — the guarantee and its proof are in the paper.
Information-theoretically motivated. Our algorithm is inspired by information-theoretic optimal feedback coding schemes.
New security threat. Our strong embedding performance over conversational text without model or prompt sharing means that AI mediated text can now carry high information undetectably.
Full numbers, baselines, and ablations are in the paper.
what this means
We build this to make a blind spot concrete: if coordinating agents want a channel hidden in plain conversation, transcript monitoring alone won't find it — the visible text is provably ordinary. Defenses have to look elsewhere: at the generation process, at the entropy available to agents, at the coordination itself rather than the payload. We regard that as the central open problem this work raises.
try it live
Make a chess move and enter a prompt to emit an AI mediated message.
The agents chat naturally while the payload rides along underneath.
See the hidden message recovered from the text alone, turn by turn.
authors
Information theory, covert communication, machine learning security.
[One line on research focus.]
[One line on research focus.]
[One line on research focus.]
[One line on research focus.]
[One line on research focus.]