Addressing Tokenization Inconsistency in Steganography and Watermarking Based on Large Language Models

• Tokenization inconsistency arises when Alice’s generated tokens and Bob’s retokenized tokens differ, potentially causing errors in steganography extraction or watermark detection.Alice’s source inconsistent tokens (SITs) can correspond to consequential inconsistent tokens (CITs) after retokenization.Source: §1 · p. 1, Figure 1 · p. 2
• The investigation identifies infrequency and temporariness as two key characteristics of inconsistent tokens.Source: §1 · p. 2
• The paper proposes stepwise verification for steganography, using token infrequency to maintain 100% correct extraction.Source: §1 · p. 2
• For watermarking, post-hoc rollback uses infrequency and temporariness to address tokenization inconsistency.Source: §1 · p. 2
• Compared with the best baseline in each group, stepwise verification lowers perplexity by 14.12%, KL divergence by 47.86%, and steganalysis accuracy by 3.53%; watermark rollback improves detectability and robustness over TI-unaware watermarking.Source: §1 · p. 2

2 Investigation: Inconsistent Tokens in Generation by Language Models

• The authors define SITs and CITs by whether token character spans in Alice’s generated list and Bob’s retokenized list match.SITs are indexed in Alice’s list and CITs in Bob’s.Source: §2 · p. 2
• Below 0.5%, token-level inconsistency rates are typical, even as text-level TI becomes more common with longer generations.The tables report text-level rates across models and generation lengths and token-level rates as the ratio of SITs and CITs to generated and retokenized tokens.Source: Table 1 · p. 3, Table 2 · p. 3, §2 · p. 3
• A candidate-level inconsistency rate measures candidate tokens that can cause TI relative to all tokens in the generative-step candidate pools.The investigation uses a one-step detokenization-retokenization check to identify candidate-level inconsistent tokens.Source: §2 · p. 3
• Candidate-level inconsistent tokens are infrequent in candidate pools, including among the 64 highest-probability tokens considered.The reported number and probability ratios indicate that low candidate-level inconsistency rates in each pool primarily account for this infrequency.Source: §2 · p. 4, Table 3 · p. 4
• Candidate-level inconsistencies can be temporary: a token may cause TI immediately after output, then generation can recover consistency.Figure 2 illustrates this with the token “put.”Source: Figure 2 · p. 3, §2 · p. 4
• Llama-2-7b has a significantly lower temporary inconsistency rate than the other models, indicating its potential SITs are more stable in affecting final tokenization.The passage also notes that Swallow-7b and Qwen2.5-7b output partial UTF-8 tokens.Source: §2 · p. 4, Table 4 · p. 4

3 Methods

• The methods target different application needs, using infrequency for steganography and both infrequency and temporariness for watermarking.Watermarking permits greater relaxation because its detector does not need candidate-pool details at every step; the method is described as lightweight, with nearly negligible imperceptibility effects expected from infrequent output inconsistencies.Source: §3 · pp. 4–5

3.1 A Stepwise Verification Method for Steganography

• For steganography, stepwise verification removes candidate-level inconsistent tokens at each generation step, making their absence sufficient to eliminate final tokenization inconsistency.Because candidate tokens are tied to codewords, the method checks each candidate with the tokenizer; its complexity is linear, compared with at least O(n^2) for earlier disambiguation algorithms.Source: §3 · pp. 4–5
• Removing infrequent candidate-level inconsistencies keeps the KL divergence between original and modified candidate pools small, reducing the negative impact on imperceptibility.The method preemptively removes candidate-level inconsistent tokens to achieve extraction accuracy.Source: §3 · p. 5

3.2 A Post-Hoc Rollback Method for Watermarking

• For watermarking, post-hoc rollback waits to see whether tokenization inconsistency persists, then returns generation to the state before it occurred.A temporary inconsistency is observed for the next q tokens; if consistency recovers, generation continues, but persistent inconsistency triggers resampling without the candidate that caused it.Source: §3 · p. 5, Figure 4 · p. 5, §3.2 · p. 6

3.1 A Stepwise Verification Method for Steganography

• Alice and Bob verify candidate pools between sampling and encoding, then encode from the same filtered pools to support accurate extraction.The approach simulates detokenization and retokenization during transmission and removes candidates that could interfere with Bob’s extraction.Source: §3.1 · pp. 5–6, Figure 3 · p. 5

4.1 Experiments on Steganography

• Steganography experiments use 128-bit messages, compare Basic, MWIS, SyncPool, and the proposed method, and vary top-k across 11 values with 500 samples per setting.The experiments use arithmetic coding and multilingual prompts and models described for Llama-2-7b, Swallow-7b, and Qwen2.5-7b.Source: §4.1 · p. 6, §4 · p. 6

4.1.1 Metrics

• Steganography evaluation uses BPT for embedding capacity, PPL for text quality and fluency, KLD for imperceptibility, ACC for steganalysis, and time for embedding efficiency.Steganalysis accuracy is evaluated with a fine-tuned discriminator.Source: §4.1.1 · p. 6

4.1.2 Results

• Reported negligible extraction error rates were about 10% for Llama-2-7b, about 5% for Swallow-7b, and about 7% for Qwen2.5-7b, illustrating the necessity of stepwise verification or disambiguation.Source: §4.1.2 · p. 6
• 14.12% lower PPL, 47.86% lower KLD, and 3.53% lower ACC were achieved on average than the best steganography baseline for each metric, model, and embedding-capacity interval.The comparisons cover Llama-2-7b, Swallow-7b, and Qwen2.5-7b; the tables report results for their English, Japanese, and Chinese contexts, respectively.Source: Table 5 · p. 7, Table 6 · p. 7, Table 7 · p. 7

4.2 Experiments on Watermarking

• Watermarking tests the rollback method with logit-based and sampling-based schemes, using q=2 for Llama-2-7b and q=10 for Swallow-7b and Qwen2.5-7b.Each condition generates 200 tokens, with 500 samples per watermarking method and model.Source: §4.2 · pp. 7–8

4.2.1 Attacking Watermarks

• Watermark attacks replace selected tokens by inference and resampling with the original generating model; GPT-4o paraphrasing results are reported in the appendix.The original model was chosen as the replacement model in consideration of attacking-model scale, fairness, and availability.Source: §4.2.1 · p. 8

4.2.2 Metrics

• Watermark strength is a relative detectability score that is not comparable across watermarking types; AUROC simulates real-world detectability, and PPL assesses text quality.Each AUROC group evaluates 500 watermarked and 500 unwatermarked texts.Source: §4.2.2 · p. 8

4.2.3 Results

• Watermark strength increased with rollback, with gains limited by infrequent inconsistent tokens; under attacks, rollback showed some superiority in watermark strength and AUROC.The authors interpret the attack results as indicating greater detectability and robustness, or anti-modification capability, after addressing TI.Source: §4.2.3 · p. 8, Table 8 · p. 8

5 Conclusion

• Across language models, stepwise verification outperforms traditional steganographic disambiguation across embedding-capacity intervals, while rollback improves watermark detectability and robustness against adversarial modifications with lower perplexity.The steganography method also improves text quality, imperceptibility, and anti-steganalysis capacity.Source: §5 · p. 9
• The investigation finds that inconsistent tokens in steganography and watermarking are infrequent and temporary.The proposed methods are stepwise verification for steganography and post-hoc rollback for watermarking.Source: §5 · p. 9
• The authors state that the methods may generalize to a wide range of steganographic algorithms and watermarking schemes.This is presented as potential generalizability.Source: §5 · p. 9

Limitations

• The 100% correct-extraction guarantee assumes no active attacker modifies stegotexts.The authors say the guarantee would not be ensured otherwise.Source: Limitations · p. 9
• For watermarking, rollback’s superiority over TI-unaware schemes is limited because inconsistent tokens are infrequent, making metric improvements relatively minor.The supplied text further notes that watermarking inconsistencies affect detection scores at inconsistency positions and positions whose contexts contain them.Source: Limitations · p. 9
• The proposed methods rest on empirical investigation, while a rigorous theoretical account of how inconsistent tokens arise remains lacking.The authors identify this as a direction for future research.Source: Limitations · p. 9

Ethical Considerations

• Steganography has intended uses such as embedding copyright information and countering censorship, but can also support harmful covert communication, disinformation, or censorship bypass.The passage identifies monitoring, regulation, and steganalysis as relevant research directions.Source: Ethical Considerations · p. 9

A.1 Language Model Basics

• An LLM predicts the next token from prompt and generated-token history, converts logits into a probability distribution, and samples a token from it.The language model’s vocabulary consists of words or word fragments called tokens.Source: §A.1 · p. 12

A.2 Steganography based on Language Models

• Language-model steganography embeds a secret message in a cover text using agreed embedding and extraction functions, with both parties accessing the same model.Generative approaches can encode through candidate pools formed by sampling and coding token probabilities.Source: §A.2 · pp. 12–13

A.2.1 Segmentation Ambiguity

• Segmentation ambiguity occurs when the same detokenized text can represent multiple token sequences, leaving the receiver unable to determine which candidate carried the message.The example contrasts “_no” plus “body” with the independent token “_nobody.”Source: §A.2.1 · p. 13

A.2.2 Disambiguation Algorithms

• Prior disambiguation methods remove ambiguous candidates or group and sample them, but prefix-based extraction bypasses sender-receiver TI and can compromise imperceptibility or embedding capacity.The described approaches include basic filtering, MWIS-based processing, and SyncPool.Source: §A.2.2 · p. 13

A.2.3 Imperceptibility of LM-based Steganography

• Statistical imperceptibility is framed as similarity between the monitored-channel model and the steganographic model, with total variation distance used to measure it.The passage says linguistic steganography focuses on the distance between the original model and its steganographic counterpart and may minimize stepwise KL divergence.Source: §A.2.3 · p. 13

A.3 Watermarks for Language Models

• Language-model watermarking uses embedding and detection functions; inference-time approaches may modify logits or guide sampling using a watermark message.Sampling-based detection can assess alignment between text tokens and pseudorandom values.Source: §A.3 · pp. 13–14

A.4 Related Work on Abnormal Tokens

• Related work covers glitch tokens, unreachable tokens, TI, and adversarial tokenizer challenges, while noting that consistency matters in text transmission because precise transmission preserves information integrity.Glitch tokens can trigger unexpected behavior; unreachable tokens are never produced by tokenizing text, and prior unreachable-token testing considered tokens without contexts.Source: §A.4.1 · p. 14, §A.4.2 · p. 14, §A.4.3 · pp. 14–15

B Analysis of Inconsistent Tokens and Tokenization Inconsistency (TI)

• TI requires outputting candidate-level inconsistent tokens, but it can occur without source inconsistent tokens; a sufficient condition is the presence of source or consequential inconsistent tokens.The section notes that a candidate-level inconsistent token need not become a source inconsistent token.Source: B Analysis of Inconsistent Tokens and… · p. 15

C.1 Stepwise Verification

• Stepwise verification filters candidate-level inconsistent tokens at each generation step; their absence is sufficient to prevent inconsistent tokens in the final output.Embedding and extraction process candidate pools consistently, with a fallback token if filtering leaves the pool empty.Source: §C.1 · p. 15

C.2 Post-Hoc Rollback

• Post-hoc rollback tracks sustained inconsistency and deletes the latest q + 1 tokens once the observation period reaches q.The counter resets when tokenization consistency returns; rollback removes tokens back to before the stable inconsistent token.Source: §C.2 · p. 16, §C.1 · p. 16

D.1 Overall Setups

• Experiments use multilingual C4 contexts, temperature 1.0, model-specific initial contexts, and default tokenizer settings except skip_special_tokens=True during detokenization.The supplied setup also reports Python, Torch, CPU, and GPU configurations.Source: §D.1 · p. 16

D.2 Steganalysis

• Steganalysis uses base-sized BERT discriminators trained on stegotexts and non-steganographic text, with testing organized by embedding-capacity intervals.The experiments collect samples across 11 top-k values, four methods, and each language model; insufficient interval samples are excluded.Source: §D.2 · pp. 16–17

D.3 Original Error Rates

• For every language model, k = 4 gives the lowest BPT and highest extraction error rate among the tested top-k values.The table reports BPT and extraction error rates for each language model and top-k value, with 500 samples per combination.Source: §D.3 · p. 17

D.4 The Limitation of SyncPool in Embedding Capacity

• As original candidate pools grow, SyncPool’s ambiguous pools can grow faster, reducing their average number and potentially lowering embedding capacity.Figure 5 presents average embedding capacities across disambiguation methods and top-k values.Source: Figure 5 · p. 17, §D.4 · p. 18
• SyncPool’s reported KL divergence of 0 uses top-k reference pools; these experiments instead use original candidate pools to compare the original and steganographic models.The comparison is described for Tables 5, 6, and 7.Source: §D.4 · p. 18

D.5 Watermarking Schemes

• LeftHash and SelfHash hash the preceding h tokens into a seed at each generation step, while Unigram uses a global seed to create green/red token vectors.The decoder samples from softmax(logit(t) + δ * Vec(t)); the schemes are identified as logit-based watermarking methods [Kirchenbauer et al., 2023; Kirchenbauer et al., 2024; Zhao et al., 2024].Source: §D.5 · p. 18
• Gumbel softmax watermarking hashes the previous h tokens at each step to seed a vector whose elements are sampled uniformly from (0, 1).The described scheme is attributed to Aaronson and Kirchner (2023).Source: §D.5 · p. 18

D.6 Perplexities of Attacked Watermarked Texts

• Addressing TI improves perplexity in attacked watermarked texts, as well as in unattacked scenarios, across the reported evaluations.Tables 11–13 report attacked-text perplexities for Llama-2-7b, Swallow-7b, and Qwen2.5-7b.Source: §D.6 · p. 18, Table 11 · p. 19, Table 12 · p. 19

E.1 Samples of Stegotexts

• The stepwise-verification examples embed a 128-bit random secret and stop generation once the message is embedded.The examples are listed in Table 16.Source: §E.1 · p. 19

E.2 Samples of Watermarked Texts

• The watermarked-text examples contain 200 generated tokens each; complete texts are omitted because of space limits.The examples are listed in Table 17.Source: §E.2 · p. 19

• Consequential inconsistent tokens generally have lower predicted probabilities than stable tokens, and only the former are accessed by perplexity calculation.Perplexity is calculated over the retokenized token list, so lower probabilities for consequential inconsistent tokens raise it relative to calculation on the original generated list.Source: §E.3 · p. 19

F Determine Observation Period (q)

• In Swallow-7b and Qwen2.5-7b, most temporary inconsistencies disappear after two subsequent tokens, while most in Llama-2-7b persist.The passages attribute the contrast to partial UTF-8 tokens in the first two models and special tokens in Llama-2-7b; over 90% of temporary inconsistencies do not disappear in Llama-2-7b.Source: F Determine Observation Period (q) · p. 19
• The experiments set q = 10 for Swallow-7b and Qwen2.5-7b to avoid most temporary inconsistencies, and q = 2 for Llama-2-7b to fix persistent inconsistencies sooner.The text recommends q greater than 2 for the first two models and permits a smaller value for Llama-2-7b.Source: F Determine Observation Period (q) · p. 19

G Efficiency of the Post-Hoc Rollback Method for Watermarking

• Runtime differences between original watermarking schemes and post-hoc rollback are generally under 5% across the tested language models.The runtime comparison uses 500 samples of 200 tokens each.Source: G Efficiency of the Post-Hoc Rollback… · pp. 20–21

H Attacking Watermarks with GPT-4o Paraphrasing

• Post-hoc rollback overall improves watermark robustness against GPT-4o paraphrasing attacks across the reported language models.The attack uses GPT-4o paraphrasing at temperature 1 with max_completion_tokens = 2048; Table 21 reports quantitative comparisons.Source: H Attacking Watermarks with GPT-4o… · pp. 21–22, Table 21 · p. 23