Linguistic steganography hides a secret bitstream inside ordinary-looking text, so that an observer sees only a plausible message. The field has a well-known trade-off: schemes that hide bits in word-by-word choices deliver low capacity, are caught by statistical detectors, and are destroyed the moment someone paraphrases the text; schemes that hide bits in high-level semantic choices — such as which entity a sentence mentions — survive paraphrasing and carry far more data, but have only ever been demonstrated one sentence at a time. Meanwhile, story-generation systems can now hold a plot together for thousands of words, and no one has asked them to carry a hidden payload. This proposal builds a system that writes a coherent multi-thousand-word story while hiding hundreds of bits in its narrative choices, and — the part no prior work touches — does so when the external knowledge graph that sender and receiver share is incomplete, as real graphs always are.
The core observation that makes this more than a mash-up: steganography inverts the standard failure mode of incomplete knowledge graphs. In knowledge-graph question answering, a missing edge is a catastrophe because the answer is fixed and the graph must contain it — a constrained decoder is physically blocked from saying the true thing. In steganography, the payload is an arbitrary bitstream, so if one path through the graph is blocked, the encoder can simply choose another. Incompleteness stops being a blocker and becomes a rate parameter: a fraction of the hiding opportunities are lost, which is exactly the situation erasure coding was designed for. That reframing yields a measurable, theory-backed question — how much payload survives as a function of graph completeness — that no existing work poses.
Core Claim
A long-form narrative can carry a high-capacity, paraphrase-robust steganographic payload if three things are done together: bits are encoded at narrative anchor points (scene-level choices of which entities, settings, and events from a shared knowledge graph the story brings up), the payload is spread across anchors with a fountain code so that lost or corrupted anchors are erasures rather than synchronization failures, and generation is decomposed so that payload planning, narrative planning, drafting, and verification are handled by separate cooperating agents that negotiate over which codeword options also make narrative sense. I claim this delivers payload rates comparable to the best sentence-level semantic steganography while keeping story quality near non-steganographic long-form baselines, and that it degrades gracefully — rather than catastrophically — as edges are deleted from the shared graph.
Prior Work and What It Leaves Open
Two systems already hide bits in knowledge-structure choices, and both stop at the sentence. Graph-Stega encodes secret bits in paths through a knowledge graph (up to 2.49 bits per word on an automobile-review corpus, with steganalysis detector accuracy of 0.720) using a single GRU–LSTM pipeline, and it strictly requires a fully pre-shared, static graph with no recovery when a relation is missing Graph-Stega. The ontology-tree system of Semantic Steganography maps bits to paths in a concept hierarchy with arithmetic coding, uses a three-agent generate–check–extract loop, and reaches roughly 28 bits per sentence (versus 2–4 bits for token-level methods), a GPT-4 semantic-rationality score of 7.36 out of 10, and 77–93% decoding success under noise — but again only on isolated sentences, over a static, complete taxonomy. My proposal differs on all three axes: story-length cover text with global plot and character consistency, an incomplete and drifting graph handled by an erasure-aware codec, and a decomposition in which the narrative planner is a first-class participant in codeword selection rather than a post-hoc sentence checker.
On the coherence side, Re3 generates 2,000–7,500-word stories through a modular plan–draft–rewrite–edit pipeline, with a 14% absolute increase in stories judged to have a coherent overarching plot and a 20% increase in premise relevance over rolling-window GPT-3, and evaluators mistaking its stories for human writing in up to 83% of tests Re3. Re3 supplies the narrative machinery I adapt — outlines, distilled reprompting, a character attribute dictionary — but has no notion of a payload, and its attribute dictionary is an ad-hoc internal structure rather than an external graph. Its blueprint stages are exactly where anchor decisions belong. DiscoDVT makes the same point at the discourse level, showing that a high-level blueprint prevents wandering in long form text Maintaining Global Coherence in Long Form Text Generation.
Two results from the adversarial side motivate the design rather than constrain it. The CASE evaluation shows that even GPT-4, asked zero-shot, succeeds in only 26% of sandboxed group-steganography runs — covert channels do not emerge from a single prompted model Secret Collusion. And the Hand-and-Brain defense shows that bits encoded in strategic choices are immune to paraphrasers (paraphrasing preserves meaning, hence preserves the bits) but can be stripped by a trusted small model that seizes control at decision forks, cutting capacity from 2.13 to 0.08 bits per decision point on MATH Level-5 while keeping 96% task accuracy Hand and Brain. The first result pushes toward explicit architecture; the second defines the strongest attack I will test against.
From the knowledge-graph side, GCR compiles subgraphs into a prefix tree and constrains autoregressive decoding to valid paths, achieving 100% faithful reasoning (versus 48–62% unconstrained) and 92.6 Hit on WebQSP over Freebase, while acknowledging that any missing node physically blocks the correct output Graph-constrained Reasoning. Its public codebase for building KG-Trie indexes over Freebase subgraphs is the infrastructure I reuse graph-constrained-reasoning. My encoder is in the opposite position: it chooses among graph branches rather than being forced down one, so gaps re-route instead of block.
Research Program
The system has four components, each mapping to one research question.
The codec. Both parties share a snapshot of a knowledge graph (Freebase subgraphs in experiments). The story outline defines $n$ anchor points — one per scene or major plot beat. At anchor $i$, the story must commit to one of $m_i$ mutually available successor entities along a graph branch, and that choice encodes roughly $\log_2 m_i$ bits via arithmetic coding over the branch's canonical ordering. The payload is protected by a fountain code with per-block checksums, so an anchor whose branch is missing on either side, or whose extraction fails the checksum, is simply an erasure. Under a simple independence assumption — anchor $i$ survives with probability $\rho_i$ that its branch is present in both snapshots — the expected delivered payload is
$$\mathbb{E}[\text{payload}] \;=\; \sum_{i=1}^{n} \rho_i \log_2 m_i,$$
which makes the capacity-versus-completeness curve an experimentally testable prediction rather than a slogan. A second research question is what happens when the two snapshots disagree silently (the receiver decodes an anchor the sender never chose): the checksum converts this from a desynchronization into an erasure, and I will measure how much of the 77–93% decode-robustness budget reported for sentence-level semantic hiding Semantic Steganography survives at story scale.
The agent decomposition. Four roles, following the evidence that separating planning from execution cuts cascading errors — MACM's Thinker–Judge–Executor split lifted GPT-4 Turbo from 54.68% to 76.73% on Level-5 MATH precisely because a monolithic model fails when it must plan and generate at once MACM. A Payload Planner converts the fountain-coded stream into ranked candidate codewords per anchor, restricted to branches verifiable in both snapshots. A Narrative Architect builds a Re3-style outline — premise, characters, settings, scene beats — and slots codewords into scenes, choosing among codec-equivalent options the one that best fits the plot, and generalizing Re3's attribute dictionary into a Story Graph: a small dynamic graph of characters, locations, and timeline facts that both guides drafting and gives the Critic something checkable. A Drafter writes each scene from the outline plus its anchor entities, obliged to surface each entity unambiguously (the extraction requirement from Semantic Steganography). A Critic runs two independent checks — Story-Graph consistency (LEGO-style iterative feedback, which raised explanation quality to 0.666 F1 on WIKIWHY over GPT-3.5's 0.615, provides the template LEGO) and statistical imperceptibility. The negotiation between Payload Planner and Narrative Architect — where the codec offers a set of valid options and the architect picks within it — is the key ingredient, and it is what the main ablation removes.
The coherence question. Uncoordinated entity injection is exactly what breaks long stories: token-level forcing accumulates drift, and Relatively-Secure LLM-Based Steganography via Constrained Markov Decision Processes shows that greedy local edits ignore future states and trip detectors. Whether semantic anchoring at the scene level avoids this is an open empirical question, and the Re3 human-evaluation protocol is the yardstick.
The theory. The CMDP analysis in Relatively-Secure LLM-Based Steganography via Constrained Markov Decision Processes proves water-filling policies only in a two-state toy model; I will formulate the anchor-selection problem as a constrained program over outline states and graph nodes and check whether the erasure-aware setting admits a closed-form or provably near-optimal greedy policy. This is the weakest part of the program and I treat it as secondary to the empirical claims.
Baselines
The naive reference point is a single-pass prompted frontier model told to write a multi-thousand-word story that works in a given list of entities. This is the "do nothing" comparator and, per CASE, GPT-4 succeeds in only 26% of zero-shot group-steganography runs, so the bar it sets is low on payload reliability; it will be run with the same backbone model, premises, and graph on our data, and any condition that fails to beat it is disqualified outright.
The strongest existing competitor is the ontology-tree system of Semantic Steganography, which reported roughly 28 bits per sentence, a 7.36/10 GPT-4 semantic-rationality score, and 77–93% decoding success under word insertion, deletion, replacement, and paraphrasing on LCCC. I will run its generate–check loop sentence-by-sentence over the same target story lengths, same backbone LLM, same Freebase-derived entity pool (its taxonomy instantiated over our subgraphs), and same tuning budget, then stitch its sentences into a continuous story with no global planner. Beating it means matching its bits-per-sentence and clean-channel decode rate while scoring substantially higher on Re3-protocol story coherence — its per-sentence design should break character and plot consistency over thousands of words, and that gap is the thing being measured.
The second serious competitor is token-level arithmetic coding applied directly to the long story's token stream, in the lineage of Neural Linguistic Steganography with distribution shaping from OD-Stega, which reported near-random 49.8% detector accuracy at a zero divergence budget and a 20% capacity gain over unshaped coding. It gets the same backbone model and is tuned to a comparable bits-per-word rate; beating it means parity on clean decode but a decisive margin under paraphrase and steganalysis, since Semantic Steganography reports symbolic decoding success dropping to near zero under those perturbations. Graph-Stega Graph-Stega is run as a fourth comparator on its native automobile-review corpus and adapted to our Freebase setting; its reported 2.49 bits per word with detector accuracy 0.720 is the reference point for KG-anchored hiding, and it has no mechanism for graph gaps, so it doubles as the hard-failure baseline in the deletion sweep.
Two ablations isolate the proposal's ingredients. Removing the Payload-Planner–Architect negotiation (random valid codeword slotting, drafter forced to include whatever arrives) isolates the coherence contribution of joint selection. Removing the fountain/erasure layer (plain arithmetic coding over branches) isolates the gap-robustness contribution; under edge deletion this ablation should collapse while the full system degrades smoothly, and that contrast is the cleanest evidence the mechanism works.
Why not just…?
Why not just prompt a frontier model to do the whole thing in one pass? The evidence against this is consistent across three of the four source literatures: GPT-4 succeeds in only 26% of zero-shot group-steganography runs in the CASE evaluation Secret Collusion; a monolithic model mixing planning and execution scores 54.68% on Level-5 MATH where a decomposed one scores 76.73% MACM; and flat autoregressive prompting loses 14% coherent-plot and 20% relevance relative to a modular pipeline at story length Re3. Still, this alternative costs nothing to run, so it is baseline one rather than something argued away.
Why not just run token-level arithmetic coding on the long story? This is a real threat in the clean-channel setting: token-level coding needs no knowledge graph, no agents, and on a high-entropy backbone it can match or exceed our raw bits-per-word, since semantic hiding is bounded by $\log_2 m_i$ per anchor. Two cited results say where it falls short: output entropy of modern LLMs caps symbolic capacity at 2–4 bits per sentence Semantic Steganography, and its decode success drops to near zero under paraphrase while semantic hiding holds 77–93%. The head-to-head baseline will make the trade explicit — I expect token-level coding to win on clean-channel capacity and lose badly on paraphrased channels and detector accuracy, and if it wins on those too, the proposal is wrong.
Why not just use ordinary retrieval instead of graph-structured encoding? Retrieval-augmented drafting can certainly surface relevant entities, but it provides no codebook: there is no canonical ordering over a retrieved bag of passages, so entity mentions carry no defined bits, and extraction ambiguity is unbounded. The graph-constrained line shows what structure buys — unconstrained and retrieval-style paths are only 48–62% faithful with roughly 33% invalid, versus 100% under trie constraints Graph-constrained Reasoning, and search-augmented baselines underperform structured decomposition on WIKIWHY (ReAct 0.631 F1 versus LEGO's 0.666) LEGO. To be fair, a RAG drafter told to include a canonically ordered retrieved list verbatim would be a near-variant of our system, so I will run it as an additional baseline and treat a win for it as a win for the proposal's codec with a simpler front end.
Why not just pre-share a complete pruned subgraph and assume away incompleteness? Graph-Stega effectively does this with its 36,373-triple graph Graph-Stega. If sender and receiver can freely exchange a canonical artifact, the incompleteness problem dissolves — but the artifact itself is evidence: an unusual shared subgraph is metadata an overseer can see, and dynamic graphs drift out from under any pre-share. The honest answer is that this is a legitimate deployment regime, and the deletion-sweep experiment will simply report the capacity cost of refusing it, so a reader can decide whether the robustness is worth it.
Why not just defend against the whole scheme with Hand and Brain? This is the most serious objection, because our anchor decisions are exactly the strategic forks that protocol attacks: it cut capacity from 2.13 to 0.08 bits per decision point on MATH Level-5 at 96% task accuracy Hand and Brain. The counter-argument is architectural: Hand and Brain needs a trusted model to identify forks and force neutral prefixes, and in open-ended narrative every scene offers dozens of legitimate entity choices with no neutral default, so neutralizing all of them should degrade the story. I will run an adapted Hand-and-Brain overseer as an explicit attack, and if it strips our channel at acceptable story cost, that is a publishable negative result for the attack side of this agenda.
Proposed Experiments
The main evaluation generates 2,000–5,000-word stories from WritingPrompts premises (the corpus Re3 used, with its reported +14% coherent-plot and +20% relevance over rolling-window GPT-3 as calibration) over Freebase subgraphs indexed with the GCR codebase graph-constrained-reasoning. Four metric families: total delivered payload and bits per anchor; decode success clean and under the LCCC noise protocol (word insertion, deletion, replacement, paraphrase) with Semantic Steganography's 77–93% as the reference band; story quality by Re3's human protocol (coherent plot, premise relevance, mistaken-for-human rate against its 83%); and steganalysis detector accuracy, where Graph-Stega's 0.720 and OD-Stega's 49.8% at zero divergence budget OD-Stega set the competitive range and 0.5 is the target.
The decisive check is the incompleteness sweep: delete edges from the shared Freebase subgraphs at controlled rates (5%, 10%, 25%, 50%) and plot delivered payload and decode rate against deletion rate for the full system, the no-erasure ablation, and Graph-Stega. The prediction from the capacity equation is a smooth decay roughly proportional to surviving-branch mass; the baselines should fail hard, since neither has any gap mechanism — though I note that no reported result found on Lacuna for any steganographic system's behavior under graph-edge deletion, so the baseline collapse is a hypothesis this experiment establishes, not one I can cite. A final block measures cost: token overhead and wall-clock latency per story against single-pass prompting and the sentence-level generate–check loops, since multi-agent iteration overhead is the acknowledged tax on this entire line of work, and a system that cannot report its own price is not a finished result.
References
- Graph-Stega: Semantic Controllable Steganographic Text Generation Guided by Knowledge Graph
- Semantic Steganography: A Framework for Robust and High-Capacity Information Hiding using Large Language Models
- Re3: Generating Longer Stories With Recursive Reprompting and Revision
- Secret Collusion among AI Agents: Multi-Agent Deception via Steganography
- Hand and Brain: Defenses against Agentic Steganography in Language Models
- Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
- MACM: Utilizing a Multi-Agent System for Condition Mining in Solving Complex Mathematical Problems
- LEGO: A Multi-agent Collaborative Framework with Role-playing and Iterative Feedback for Causality Explanation Generation
- Relatively-Secure LLM-Based Steganography via Constrained Markov Decision Processes
- Neural Linguistic Steganography
- OD-Stega: LLM-Based Near-Imperceptible Steganography via Optimized Distributions