PaperlayerView exact revision on arXiv

Source-linked AI summary

HiMark: Hierarchical and Controllable Multi-bit Watermarking for Large Language Models

Ke Zhu, Yanli Chen, Ling Xiong, Gejian Zhao, Hanzhou Wu

arXiv:2610.30601v1cs.CR

TL;DR

Multi-bit watermarking faces sparse per-bit evidence, especially in short texts, and a trade-off between extraction accuracy and text quality. HiMark controls candidate tokens during embedding and aggregates token evidence during model-agnostic extraction; experiments report higher extraction accuracy while maintaining text quality and robustness against paraphrasing.

  • Problem

    Multi-bit watermarking can leave fragile, sparse evidence for each bit, particularly as messages lengthen or texts shorten, while stronger interventions can degrade text quality.

    Source: §I · p. 1, B. Multi-bit Watermarking · p. 2

  • Method

    HiMark uses hierarchical candidate control to embed bits and model-agnostic aggregation of multilayer token evidence to extract them.

    Source: §I · p. 1, §III · p. 2

  • Results

    HiMark achieves higher watermark extraction accuracy while maintaining text quality and robustness against paraphrasing attacks.

    Source: §V · p. 6

  • Takeaways & Limitations

    Reliable extraction of embedded multi-bit information supports intellectual-property protection.

    Source: §I · p. 1

Abstract

from arXiv · show

With the rapid adoption of large language models (LLMs) in text generation applications, it has become increasingly difficult to trace generated content and assign responsibility for its use, raising concerns about provenance, copyright protection, and accountability. Multi-bit watermarking addresses these issues by embedding multi-bit provenance information into generated text, but reliable extraction remains difficult due to sparse per-bit evidence and the trade-off between watermark-extraction accuracy and text quality. To deal with these challenges, we propose HiMark, a hierarchical and controllable multi-bit watermarking framework for LLM-generated text. During watermark embedding, HiMark uses a hierarchical candidate-control mechanism, including initial candidate sampling, layer-wise tournament elimination, support-based refinement, and support-threshold filtering. During watermark detection, a model-agnostic evidence aggregation mechanism computes multi-layer support evidence for each observed token, and then accumulates these token-level votes into the corresponding information for robust watermark extraction. Experiments show that HiMark improves watermark extraction accuracy while maintaining text quality, e.g., the watermark extraction accuracy is 90.01% under the paraphrasing attack when 32 bits were embedded within a text containing 300 tokens, demonstrating its effectiveness for provenance tracking.

I. INTRODUCTION

Multi-bit watermarking can carry provenance information beyond watermark-presence checks, but sparse per-bit evidence and intervention-related quality trade-offs make extraction challenging. HiMark controls local token candidates for embedding and aggregates token-level support for extraction.

I. INTRODUCTION

  • Sparse per-bit evidence makes multi-bit extraction less stable in short texts, while stronger interventions can improve precision but degrade generated-text quality.Weaker interventions preserve fluency but may weaken extraction performance.Source: §I · p. 1
  • HiMark embeds and extracts multi-bit watermarks without altering the LLM, with claimed robustness across short-text, long-message, and textual-perturbation scenarios.The framework is presented for provenance and intellectual-property protection.Source: §I · p. 1
  • Embedding shifts from global probability intervention to local candidate selection through tournament elimination, support-based refinement, and support-threshold filtering.These stages guide candidate tokens to carry their corresponding bits.Source: §I · p. 1
  • Model-agnostic extraction evaluates multilayer support for each bit and accumulates token evidence in a voting matrix.The paper presents this aggregation as improving robustness to textual perturbations.Source: §I · p. 1

II. RELATED WORKS

  • Post-hoc watermarking edits generated text, whereas inference-time watermarking embeds during generation by intervening in sampling or decoding.Post-hoc editing can affect semantic consistency or text quality, and later editing or paraphrasing can weaken its embedded information.Source: §II · p. 2

A. Zero-bit Watermarking

Zero-bit watermarking detects a hidden pattern, while multi-bit methods encode message information but face extraction constraints across message length and text conditions. The section reviews these approaches and highlights sparse per-bit evidence as a challenge for position-allocation methods.

A. Zero-bit Watermarking

  • Probability-biased zero-bit watermarking increases green-list token probabilities, but this can raise rare-token likelihood and reduce generated-text naturalness.The passage also distinguishes unbiased and sampling-based approaches.Source: A. Zero-bit Watermarking · p. 2
  • Unbiased zero-bit methods can reduce extraction accuracy by restricting intervention strength and leaving weaker statistical evidence for detection.The cited examples include inverse sampling with γ-reweighting and a later improvement to γ-reweighting.Source: A. Zero-bit Watermarking · p. 2
  • SynthID-Text uses tournament sampling for zero-bit detection, while HiMark extends tournament-based token selection to multi-bit watermarking with bit-specific evidence and filtering.HiMark adds message-index assignment, support-based refinement, and threshold filtering.Source: A. Zero-bit Watermarking · p. 2

B. Multi-bit Watermarking

  • Message-coupled extraction cost grows exponentially with message length, while segment-based extraction depends on sufficiently long, well-aligned text segments.Short texts or substantial removals can make segment alignment difficult and message extraction unstable.Source: B. Multi-bit Watermarking · p. 2
  • Position-allocation methods give each bit evidence from only a subset of tokens, making robust extraction harder as messages lengthen or texts shorten.The passage gives MPAC and BiMark as examples of this method family.Source: B. Multi-bit Watermarking · p. 2

III. PROPOSED METHOD

HiMark embeds assigned message bits by selecting tokens through hierarchical candidate control, then extracts the message by aggregating token evidence. Its embedding process maps each generation step to a bit and progressively filters sampled candidates for support of that bit.

III. PROPOSED METHOD

  • HiMark combines hierarchical candidate selection during embedding with two-stage evidence aggregation during extraction.The extraction process reconstructs the message-position mapping and accumulates evidence into the corresponding bit positions.Source: §III · p. 2

A. Hierarchical and Controllable Watermark Embedding

  • At each generation step, the prefix context and secret key determine a message-bit position, and the corresponding message bit becomes the target.The paper states that longer messages require more effective tokens, while longer texts improve extraction reliability.Source: A. Hierarchical and Controllable… · pp. 2–3
  • HiMark samples initial candidates from the LLM distribution and uses a context-seeded binary mapping to assess candidate support for the target bit.A candidate supports the target bit at a layer when its mapping equals that bit.Source: A. Hierarchical and Controllable… · p. 3
  • Layer-wise tournament elimination pairs candidates in sampled order, advancing a target-supporting candidate and choosing randomly when both candidates have the same support status.Elimination stops when the set reaches Kkeep.Source: A. Hierarchical and Controllable… · p. 3
  • HiMark refines retained candidates by support score, keeps the top Krefine, filters scores below τs, and samples from the remaining set using the original LLM logits.Discarded candidates are masked by setting their logits to −∞.Source: A. Hierarchical and Controllable… · p. 3

B. Two-Stage Evidence Aggregation for Watermark Extraction

HiMark extracts the binary message without access to the original LLM by reconstructing each observed token’s message position and aggregating its support evidence. Token-level votes are weighted by support differences and combined at each bit position.

B. Two-Stage Evidence Aggregation for Watermark Extraction

  • The detector extracts the message from observed text without accessing the original LLM, using multi-layer token support computation followed by bit-wise evidence aggregation.The accumulated evidence is stored in a voting matrix and used to extract the binary message.Source: B. Two-Stage Evidence Aggregation for… · p. 4
  • For each observed token, the detector reconstructs its context-dependent seed and message index, then evaluates the token with the same context-seeded binary function used during embedding.The reconstructed index identifies the message-bit position associated with that token.Source: B. Two-Stage Evidence Aggregation for… · p. 4
  • The larger of the token’s support counts determines its vote direction, while the absolute support difference determines its evidence strength.Each token contributes its evidence to the row for its reconstructed message-bit position.Source: B. Two-Stage Evidence Aggregation for… · p. 4
  • After processing all tokens, the detector extracts each message bit by selecting the value with greater accumulated evidence in that bit’s voting-matrix row.The support difference is accumulated as the evidence weight in the column for the voted bit.Source: B. Two-Stage Evidence Aggregation for… · p. 4

IV. EXPERIMENTAL RESULTS AND ANALYSIS

Experiments use Llama-3.1-8B with prompts from C4, compare watermarking methods across message and text lengths, and assess text quality using perplexity.

  • Llama-3.1-8B generates text from prompts sampled from C4, using random binary strings as the secret messages.Source: §IV · p. 4
  • Text quality is measured by perplexity on generated tokens, with prompt tokens excluded; lower PPL indicates more fluent text.Source: §IV · p. 4
  • Multi-bit extraction is compared with MPAC and BiMark, while Table I reports extraction accuracy and PPL across message and text lengths.Source: §IV · p. 4, Table I · p. 4
  • Unless otherwise specified, experiments embed an 8-bit random string and average results over 1,000 generated samples.Source: §IV · p. 4

A. Watermark Extraction Accuracy and Text Quality

HiMark achieves the highest extraction accuracy across the reported settings while maintaining better text quality than the compared methods.

B. Generalization across LLMs and Datasets

HiMark is evaluated across multiple LLM backbones and datasets, with reported high extraction accuracy across those settings.

C. Computational Overhead

HiMark incurs greater computational cost than BiMark but less than MPAC, and its extraction remains robust to synonym substitution, copy-paste, insertion, and deletion attacks.

C. Computational Overhead

1) Synonym Substitution Attack:

2) Copy-Paste Attack:

  • HiMark remains robust to copy-paste attacks because weighted evidence from unchanged watermarked regions supports bit-wise voting despite watermark dilution.Source: 2) Copy-Paste Attack · p. 5

3) Robustness against Insertion and Deletion Attacks:

4) Spoofing/Forgery and Scrubbing Attacks:

HiMark retains extraction accuracy under paraphrasing and scrubbing, while zero-bit detection leads across tested text lengths. Ablations expose trade-offs between extraction strength and text quality for several sampling controls.

4) Spoofing/Forgery and Scrubbing Attacks:

  • 50.63% bit accuracy under spoofing/forgery, while HiMark retains 86.88% extraction accuracy after manual scrubbing of 300 texts.For spoofing/forgery, attackers used independently chosen keys while decoding used the legitimate key; scrubbing aimed to remove the watermark while preserving meaning.Source: 4) Spoofing/Forgery and Scrubbing… · p. 5

5) Paraphrasing Attack:

  • 90.01% accuracy under paraphrasing, versus 52.38% for BiMark, 49.79% for MPAC(1), and 52.92% for MPAC(1.5), with 32 bits in 300-token texts.The attack used DIPPER paraphraser-xxl with lexical and order diversity both set to 10.Source: 5) Paraphrasing Attack · p. 5

E. Zero-bit Detection Performance

F. Ablation Study

  • Increasing τs improves extraction accuracy but increases PPL; τs = 5 balances the two.A higher threshold removes weak-support candidates and strengthens watermark evidence, but narrows the sampling space.Source: F. Ablation Study · p. 5
  • Increasing tournament depth m from 9 to 12 decreases both extraction accuracy and PPL; m = 11 balances extraction performance and PPL.A larger m provides more candidates and improves fluency, but weakens watermark selection pressure under fixed refinement and filtering.Source: F. Ablation Study · p. 5
  • A smaller Krefine improves extraction accuracy but increases PPL; Krefine = 10 balances extraction strength and text quality.Fewer candidates strengthen bit-level evidence but reduce fluency.Source: F. Ablation Study · pp. 5–6
  • A larger Kkeep improves extraction by retaining more candidates for refinement, but may increase PPL by selecting tokens less preferred by the LLM; Kkeep = 32 balances robustness and quality.Source: F. Ablation Study · p. 6

V. CONCLUSION

HiMark embeds and extracts multi-bit watermarks without altering the LLM, using hierarchical candidate control and model-agnostic aggregation of token evidence. The paper reports higher extraction accuracy while maintaining text quality and robustness against paraphrasing.

  • HiMark embeds a binary string through hierarchical candidate control and extracts it by aggregating multi-layer token evidence in a voting matrix.Source: §V · p. 6
  • The framework performs multi-bit watermark embedding and extraction without altering the LLM.Source: §V · p. 6
  • Experiments show higher watermark extraction accuracy while maintaining text quality and robustness against paraphrasing attacks.Source: §V · p. 6

Related papers

Loading 2610.30601v1…