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

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "HiMark: Hierarchical and Controllable Multi-bit Watermarking for Large Language Models".

Elias: Here's the gist of the paper. The gist The proposed HiMark framework introduces a hierarchical and controllable multi-bit watermarking system designed to embed provenance information into LLM-generated text without requiring model training, while ensuring robust extraction against various attacks.

Nadia: Large language models have introduced risks such as copyright infringement, misinformation dissemination, malicious content generation, and synthetic data contamination; "The widespread deployment of LLMs, however, has also introduced a series of risks such as copyright infringement, misinformation dissemination, malicious content generation and synthetic data contamination." Model watermarking addresses these issues by embedding multi-bit provenance information into generated text but faces challenges 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." Proposed Framework Components HiMark operates through a hierarchical candidate selection mechanism during embedding and a two-stage evidence aggregation strategy during extraction; "HiMark does not require LLM training, fine-tuning, and other internal interventions." During watermark embedding, the process involves: 1.

Elias: Determining the message bit assigned to the current token using a context-dependent seed st = PRF(pt, kt), where pt = (xt−w, xt−w+1, …, xt−1) is the prefix context and kt is a secret key; "At token generation step t > 0, HiMark collects the prefix context by pt = (xt−w, xt−w+1, …, xt−1), where xt denotes the token to be generated at step t and w is the context window-size." 2.

Nadia: Sampling initial candidate tokens C(0)t containing 2m tokens from the LLM distribution; "HiMark samples an initial candidate set C(0)t containing 2m tokens from this distribution, where m denotes the tournament depth." 3.

Paper summary: Nadia: The core problem they're tackling is that with large language models generating text so fast, it gets really hard to track where the content came from or who is responsible for it. This paper says multi-bit watermarking is a way to put some kind of provenance information right into the generated text itself.

Elias: But they acknowledge that extracting this embedded information reliably has been pretty tricky before because there's not much clear evidence for each individual bit, and you always have to choose between getting an accurate watermark extraction and keeping the generated text looking good.

Priya: From my side, I'm wondering what kind of data these claims are based on. When they talk about embedding information, how do we know if it actually sticks through the model's process? Does it really survive paraphrasing attacks or something similar?

Nadia: Exactly that's the question. They propose a framework called HiMark, which is designed to handle those issues by being hierarchical and controllable during both the embedding and extraction phases.

Elias: During embedding, they use this hierarchical candidate-control mechanism involving initial sampling, layer-wise tournament elimination, support-based refinement, and support-threshold filtering to select the right token at each step.

Priya: That sounds complex from an engineering standpoint. What does that hierarchy actually do for the quality of the text versus how much provenance information you manage to hide?

Nadia: They claim that during extraction, they use a two-stage evidence aggregation strategy to reconstruct the message without needing access to the original LLM itself.

Elias: In the first stage, they compute multi-layer token support evidence for every observed token using a function called gl(xt, st) equals Hash(xt, st, l) mod two across different layers l <ref:2610.30601#pg1>.

Priya: So you're looking at how many times each potential word in the text supports a specific bit at different levels of the process. How does that translate into a usable message?

Nadia: Then in the second stage, they do bitwise evidence aggregation by initializing a voting matrix C and accumulating evidence weights based on which support count, n(zero)t or n(one)t, is larger for each token <ref:2610.30601#pg3>.

Elias: Specifically, the larger one between those two counts determines the voted bit and the absolute difference between them is accumulated as an evidence weight in the column of that voted bit. Finally, they select the full message by choosing the bit value with the largest accumulated evidence in each position j equals arg max d∈one C

j, d: <ref:2610.30601#pg1>.

Priya: So if I understand this right, you're taking these token-level votes and stacking them up into a final binary string? That seems like a lot of information to process for a single generated text.

Paper summary: Nadia: It is a lot of information, but they argue it makes the extraction robust against various attacks. Their experiments show that HiMark improves extraction accuracy while keeping the text quality pretty high.

Elias: They specifically report that under a paraphrasing attack, HiMark gets ninety point zero one percent accuracy when thirty-two bits are embedded in a text of three hundred tokens, which is compared to much lower numbers for other methods they tested.

Priya: A hundred percent isn't really possible, but ninety percent accuracy on a paraphrase is pretty strong if we're talking about practical security. What about the limitations? What can't this framework do?

Nadia: The paper states that longer messages require more effective tokens and longer texts improve watermark extraction reliability, which is because the probability that no evidence is given to a bit is L minus one over L times n, so that total probabilities of all bits receiving no evidence is less than or equal to Le minus n over L.

Elias: That probability formula suggests that for a message of length L, you need at least n greater than or equal to L times the natural logarithm of l divided by delta to cover all bits with probability at least one minus delta.

Priya: So if I'm just listening to this show and I see a text with a watermark, am I going to be able to reliably pull out that embedded information? The paper says it's better than other methods like MPAC and BiMark in their tests.

Nadia: They do claim it achieves the highest extraction accuracy across all settings by selecting tokens with stronger bit-level evidence for aggregation, and they also show lower perplexity than MPAC configurations.

Elias: And they've tested its robustness against a few different attacks, like synonym substitution, copy-paste attacks, and paraphrasing attacks. The results show it stays pretty stable under those kinds of challenges.

Priya: So the big implication for us is that if we use this kind of watermarking technique in LLM generation for things like intellectual property protection or provenance tracking, HiMark seems to offer a way to make that information more extractable than before.

Nadia: Right, it's about making sure the embedded multi-bit information is actually accessible for practical use without destroying the text quality too much. That's where this framework fits into what we're trying to do in applied security.

Elias: And for us cryptographers, it shows how a hierarchical structure can help manage the trade-off between embedding strength and extraction feasibility when dealing with these complex signal problems.

Priya: It just feels like a step forward in making watermarking for large models something that's actually usable and not just theoretical proof on paper.

Conclusion: Nadia: So we're wrapping up this discussion on HiMark, which is titled "HiMark: Hierarchical and Controllable Multi-bit Watermarking for Large Language Models."

Elias: Yeah, it’s basically a framework that lets you put provenance information into text without the AI having to be retrained.

Nadia: Right. The authors are working on this practical application of watermarking for things like tracking where generated content comes from.

Elias: They focused on making the embedding and extraction controllable, which is key because before, extracting those bits was really unreliable due to sparse evidence.

Nadia: So they built a system with these hierarchical candidate controls during embedding to select the right tokens at each step.

Elias: And then for extraction, they used this two-stage voting matrix approach where you aggregate token support counts across different layers.

Nadia: Priya, from what you’re seeing in terms of the results, what does this mean for someone who just uses an LLM to write something?

Priya: Well, the experiments show it keeps the text quality high while still getting decent extraction accuracy even when people try to paraphrase the text.

Elias: That ninety point zero one percent accuracy they hit under a paraphrasing attack is pretty notable when you compare it to other methods they tested.

Nadia: It shows that this approach actually manages to preserve enough bit-level evidence so you can pull out the hidden message without totally ruining the text flow.

Elias: That's what they’re claiming: you get reliable extraction for intellectual property protection while maintaining good output quality.

Priya: The caveat is that it still needs a certain amount of text length and bits embedded to be really effective, which is something to keep in mind when planning your use case.

Nadia: Right. So this framework seems like a solid step toward making watermarking more useful for actually tracking generated content in the real world.