Tokenization-Invariant Watermarking: A Byte-Local Method for LLM Text

Tung-Ling Li

cs.CROct 9, 2026

Tokenization-Invariant Watermarking: A Byte-Local Method for LLM Text

Authors: Tung-Ling Li

Organizations: Independent Researcher

Abstract

We introduce Tokenization-Invariant Watermarking (TI-WM), a method that embeds a watermark during token generation but keys and scores it on canonicalized UTF-8 bytes. The detector does not invoke the tokenizer. Canonicalizer-preserving edits leave its score unchanged; other localized canonical-byte edits affect a bounded number of scoring windows. Across three fixed keys and 128 prompts per key and model, a deterministic white-box attack at a 5% word-edit budget leaves mean attacked-AUC 0.530 on Qwen3-8B and 0.664 on Gemma 4 E4B, compared with 0.410 and 0.489 for Unigram with detection-side deletion. These operating points are not jointly matched on quality and clean detectability. Bias sweeps show model-dependent distortion costs, and shared-rule controls support a locality interpretation without establishing a unique advantage of bytes. Visible insertion outside the canonicalizer's deletion set defeats the default design. Alphabetic filtering closes that channel but does not resolve source shift or calibrated detection power. TI-WM thus provides a concrete construction with local scoring guarantees and measured attack-ranking gains, not a general robustness or low-false-positive-rate deployment guarantee.

Figures & tables

line	signal	main defense target
KGW/SynthID	token	statistical detectability
Unigram	token	token-edit robustness
WaterPool	token	quality/efficacy trade-off
SIR/PASA	semantic	paraphrase
rollback repair	token	tokenization mismatch

Table 1: Summary of nearby watermarking research lines.

scheme	base-AUC	PPL	AUC, 5% edits	AUC, 30% edits
KGW	0.857	1.049	0.237 [0.204,0.273]	0.000
KGW+DE	0.850	1.049	0.259 [0.224,0.296]	0.000
KGW+UN	0.857	1.049	0.274 [0.238,0.312]	0.000
Unigram	0.799	1.056	0.374 [0.332,0.417]	0.001
Unigram+DE	0.799	1.056	0.410 [0.366,0.454]	0.003
Unigram+UN	0.799	1.056	0.409 [0.366,0.453]	0.007

Table 2: Qwen3-8B, 128 prompts per key, three fixed keys, 200-token limit. Entries average per-key statistics. Brackets give 95% prompt-bootstrap intervals conditional on these keys. PPL is a ratio to unwatermarked output; settings are not matched on clean detectability.

Figure 1: First-key bias sweeps: 128 prompts per model, 5% deterministic attack. Shapes denote

\delta

; bars are pointwise 95% bootstrap intervals. PPL is relative to the unwatermarked mean. Axes are shared within rows; Gemma’s PPL axis is logarithmic. Equal PPL does not establish equal detectability or perceptual quality.

scheme	base-AUC	PPL	AUC, 5% edits	AUC, 30% edits
KGW	0.894	1.696	0.336 [0.297,0.376]	0.000
KGW+DE	0.892	1.696	0.362 [0.322,0.402]	0.000
KGW+UN	0.894	1.696	0.373 [0.334,0.414]	0.001
Unigram	0.857	1.192	0.461 [0.422,0.502]	0.005
Unigram+DE	0.856	1.192	0.489 [0.450,0.531]	0.006
Unigram+UN	0.857	1.192	0.495 [0.455,0.537]	0.011

Table 3: Gemma 4 E4B replication with the same 128 prompts, three keys, defenses, and uncertainty convention as Table 2 . Mean PPL is particularly sensitive to rare outputs in this model.

	Qwen		Gemma
unit	clean AUC	attacked AUC	clean AUC	attacked AUC
Token	0.809	0.205 [0.153,0.264]	0.886	0.331 [0.266,0.402]
Word	0.793	0.214 [0.160,0.268]	0.886	0.308 [0.245,0.369]
Code point	0.721	0.493 [0.421,0.569]	0.837	0.641 [0.573,0.708]
Byte	0.721	0.467 [0.394,0.542]	0.831	0.606 [0.539,0.673]
Code point, bounded	0.764	0.525 [0.453,0.597]	0.876	0.689 [0.624,0.751]

Table 4: Shared-rule locality controls, first key, 128 prompts, 200-token limit. Attack is the 5% deterministic GA; brackets give pointwise 95% document-bootstrap intervals. All binary variants use bias 1.

canonicalizer	base-AUC	attacked-AUC	exact
default	.732	.002	.000
alphabetic-only	.773	.773	1.000

Table 6: Adaptive visible-character insertion at a 30% word-boundary budget (

n=128

, earlier first-key Qwen diagnostic, not averaged over keys). Exact is the fraction whose score is unchanged.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

model	limit	mean tokens	TI-WM AUC [95% CI]	Unigram	$z>4$	radius
Qwen	100	99.6	0.496 [0.422,0.564]	0.370	10/128	0
Qwen	200	189.9	0.544 [0.472,0.612]	0.392	40/128	0
Qwen	400	336.0	0.597 [0.529,0.662]	0.469	80/128	6
Gemma	100	99.5	0.593 [0.519,0.659]	0.428	9/128	0
Gemma	200	195.3	0.680 [0.613,0.743]	0.466	45/128	0
Gemma	400	380.1	0.743 [0.679,0.800]	0.549	102/128	12

Appendix

Table 7: First-key length scaling (

n=128

per row). Observed tokens and radii refer to default TI-WM at

\delta=1.25

. Both attacked AUC columns use 5% word edits; Unigram uses DE and

\delta=1

. Radius is the median over all documents under the fixed-threshold canonical-substitution bound.

filter	cap	5% AUC	detected	max LOO FPR	visible drop
default	none	0.525–0.579	0/128	0.0088–0.0664	0.264–0.381
letters	none	0.522–0.578	0/128	0.0056–0.0744	0.000–0.000
letters	2	0.351–0.374	0/128	0.0088–0.0552	0.000–0.000
letters	4	0.384–0.490	0/128	0.0088–0.0560	0.000–0.000

Appendix

Table 8: Bounded code-point screen on Qwen, 128 prompts per variant, three keys. Ranges are observed minima/maxima across keys, not confidence intervals. TPR is clean detection at a human-calibrated nominal

10^{-3}

FPR; the count is zero separately for every key. Max LOO is each key’s worst held-out-source FPR. Visible drop is clean minus insertion-attacked AUC.

seed ( $n$ )	clean AUC	5% human AUC	gain [95% CI]	TPR	PPL ratio
003 (64)	.896/.944	.722/.797	.075 [.050,.101]	1/64, 2/64	1.258/1.265
004 (32)	.880/.962	.305/.452	.147 [.073,.223]	0/32, 0/32	1.221/1.174
005 (32)	.832/.899	.422/.599	.177 [.123,.235]	0/32, 0/32	1.201/1.164

Appendix

Table 9: Rank-aligned reward pilot. Clean AUC uses matched unwatermarked model outputs; attacked AUC uses held-out human text. Each paired entry is raw/rank. The gain column gives paired 95% intervals for the rank-minus-raw difference. TPR is measured after the attack; PPL is relative to unwatermarked text.

setting	before	after attack
5% compound	…$50 million in proposed transit funding, with proposals ranging from…	…$50 million in propo[U+0455]ed transit funding, with proposals ranging from…
Full-document score: $1.521\to 0.464$ .
30% compound	…City council members are currently debating how to allocate…	…City council mrmbers aer currently debating hwo to allocate…
Full-document score: $1.521\to-1.893$ .
Visible insertion	…City officials are currently locked in debate…	…City. officials are. currently. locked in debate….
Full-document score: $1.325\to 1.325$ .

Appendix

Table 10: Saved Qwen campaign examples at the first key and 200-token limit. The first two rows use default TI-WM; the last uses the bounded code-point variant with letters-only filtering and no repetition cap. Its unchanged score demonstrates invariance, not successful detection.

judge	PPL cap	consistent	attack/original/tie	position gap
Qwen3.8-27B	$1.25\times$	122	0 / 10 / 112	.000
	$1.5\times$	100	0 / 60 / 40	.008
	$2\times$	103	0 / 95 / 8	.032
Gemma 4 E4B	$1.25\times$	125	0 / 0 / 125	.000
	$1.5\times$	106	0 / 3 / 103	.008
	$2\times$	84	0 / 6 / 78	.008

Appendix

Table 11: Historical cross-family quality diagnostic on saved, quality-gated pairs using Qwen/Qwen3.8-27B and google/gemma-4-E4B-it [ 20 , 5 ] (128 scheme–document pairs per gate). Each pair is judged in both A/B orders; only decoded order-consistent pairs are counted. The selector retained the exact original in 110, 31, and 1 pairs at the three gates. Neither judge replaces human evaluation.

setting	mean PPL	char. similarity	word similarity
unwatermarked	6.00	–	–
KGW / Unigram	6.35 / 6.29	–	–
TI-WM $L=0$ / $L=1$	6.59 / 6.18	–	–
10%-edit GA (scheme range)	15.88–20.29	0.987–0.989	0.902–0.906
30%-edit GA (scheme range)	36.24–50.20	0.965–0.970	0.717–0.736

Appendix

Table 12: Local quality diagnostics on 32 prompts. PPL is scored by the same Qwen3-8B model; similarities compare the saved attacked text with its source. These automatic metrics motivate, but do not replace, human evaluation.

configuration	base-AUC	attacked-AUC
identity, $L=0$	0.615 [0.470,0.758]	0.213 [0.110,0.338]
default, $L=0$	0.641 [0.503,0.772]	0.242 [0.136,0.367]
UN-style, $L=0$	0.641 [0.503,0.772]	0.257 [0.148,0.384]
identity, $L=1$	0.672 [0.527,0.803]	0.163 [0.067,0.269]
default, $L=1$	0.708 [0.566,0.832]	0.078 [0.022,0.162]
UN-style, $L=1$	0.708 [0.566,0.832]	0.113 [0.039,0.215]

Appendix

Table 13: Matched-seed Qwen3-8B canonicalizer ablation on 32 64-token outputs. These are shorter generations than Table 2 , which explains the different default

L=1

base and attacked AUCs. The deterministic compound GA uses a 30% word-edit budget, population 40, and 30 generations. Default removes whitespace/format characters; UN-style also reverses the attack’s confusable map.

Explore similar work

ByteMark: A Unified Byte-Level Watermark for Detection Across Language Models
Oct 10, 2026Xiaopu Wang, Runze LiText Watermarking LLM Watermarking
TextSeal: A Localized LLM Watermark for Provenance & Distillation Protection
May 12, 2026Tom Sander, Hongyan Chang, Tomáš Souček +10Language Model Fingerprinting LLM Watermarking
FAIR, Meta Superintelligence Labs
Tracing Provenance and Detecting Tampering with Complementary LLM Watermarks
Aug 13, 2026Xiaoyan Feng, Yanjun Zhang, He Zhang +2Data Provenance LLM Watermarking
Griffith University

Oct 10, 2026J/K move · Enter open · S save

ByteMark: A Unified Byte-Level Watermark for Detection Across Language Models

Xiaopu Wang, Runze Li

Text Watermarking LLM Watermarking Robustness of Machine-Generated Text Detection

Open paper AskPDF arXiv

As watermarking of LLM-generated text enters deployment, users increasingly need to check text whose source is unknown. Existing detectors read the watermark through a specific tokenizer or embedding pipeline, and even if all providers adopted the same watermarking method, differences in these representations would leave their watermarks incompatible, and the text alone does not reveal which representation produced it. We propose ByteMark, a unified watermarking scheme that defines its signal on the UTF-8 bytes of published text. Models with different tokenizers embed this signal under one public specification and key, and a single detector verifies the text from the text and key alone. When the tokenizer or embedding model of a baseline detector is replaced, its detection degrades sharply, whereas ByteMark, which uses neither, retains its detection rate; ByteMark also remains detectable when participating models continue or rewrite the text.

Abstract

Explore similar work

ByteMark: A Unified Byte-Level Watermark for Detection Across Language Models

TextSeal: A Localized LLM Watermark for Provenance & Distillation Protection

Tracing Provenance and Detecting Tampering with Complementary LLM Watermarks