BREW: Block-wise Reliable Embedding for Multi-bit Text Watermarking

Paper: Block-wise Codeword Embedding for Reliable Multi-bit Text Watermarking Authors: Joeun Kim, HoEun Kim, Dongsup Kim, Young-Sik Kim arXiv: 2605.00348 (2026-04-29)

The Problem: Embeddable but Unreliable Watermarks

Text watermarks serve to identify AI-generated content, prevent misuse, protect copyright, and enable content provenance. Existing approaches face a fundamental dilemma:

• High-capacity methods embed many bits but suffer poor reliability and conflate decoding with detection.
• ECC-based extractors suffer catastrophic false positive rates. Raising thresholds to suppress false alarms causes detection rates to collapse to random-guess levels.

The core issue: with multi-bit watermarks, a decoder cannot tell whether it is misreading an actual watermark or hallucinating a message from unwatermarked text.

The BREW Approach

BREW (Block-wise Reliable Embedding for Watermarking) shifts from "detect-then-decode on everything" to designated verification via a two-stage mechanism:

1. Stage 1 — Block-level detection: first confirm, with high reliability, that the text carries a watermark. 2. Stage 2 — Designated verification: decode message bits only on blocks confirmed as watermarked.

Supporting design elements:

• Block-wise embedding: the text is split into blocks; each block independently embeds and locally verifies information; results are aggregated globally.
• Separated detection and decoding: decoding never runs blind on arbitrary text.
• Reliability guarantee: low false positives, high detection rate, and multi-bit capacity are achieved simultaneously.

An analogy

• Traditional methods: like opening any letter and reading its hidden content — possibly "reading out" messages that don't exist (false positives).
• BREW: like first checking whether a letter contains invisible ink. If yes, read the message; if not, don't.

Why Designated Verification Beats Blind Decoding

Blind decoding conflates detection with decoding, producing messages from unwatermarked text and forcing an unwinnable threshold trade-off. Designated verification separates the questions "Is there a watermark?" from "What is the message?" — a classic signal-processing principle: detection ≠ decoding; confirm existence first, then extract content.

Takeaways for Practitioners

If you build watermarking or provenance systems, ask:

1. Does my system conflate detection with decoding? 2. Is the false positive rate acceptable? 3. Does multi-bit capacity sacrifice reliability? 4. Would a two-stage design improve reliability?

Key insight: a reliable watermark is not measured by how much information it can embed, but by how certain the detection is. When a watermark system learns to "confirm before decoding," it evolves from an information hider into a trusted content passport.