acceptodds
Under review as a conference paper at ICLR 2027

Beyond Surface Tokens: Watermarking Language Models through Private Solution Choices

13 views

Abstract

Watermarking provides evidence of model ownership, but signals carried by wording and code patterns are exposed to rewriting and normalization. We introduce, to our knowledge, the first watermark carried by which valid solution a model returns to a constraint problem, rather than by how the answer is worded. A private key selects one of two verified solutions, and joint fine-tuning combines these protected targets with ordinary problem-solving examples. Verification compares parsed solutions through the model's input-output interface, so rewriting that preserves the solution preserves the mark. Removing the mark while keeping answers correct requires another valid solution, which links removal to the Another Solution Problem (ASP), NP-complete in the worst case for the domains we use. Across X3C, Kakuro, and graph coloring, joint training raises accuracy on 1,536 unseen problems from 16.21% to 42.45%, while producing the exact owner solution on all 96 protected problems used in training. General benchmark performance remains close to the base model. Given WM's valid answers, five commercial reasoning models find different valid solutions on 0% to 20.83% of the problems under the reported inference budgets. Ordinary continued fine-tuning retains nearly all owner matches, whereas targeted interventions reduce owner matches only together with unseen-problem accuracy, a cost that general benchmark scores alone do not reveal.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
large language models, model watermarking, behavioral watermarking, Another Solution Problem, combinatorial reasoning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_CvNCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces a watermark for model ownership carried by which valid solution a model returns to a constraint problem, rather than by how the answer is worded.

Critical strengths

(1) The carrier resists correctness-checking, correctness-driven fine-tuning, and answer-only extraction.

Because the designated reply must be a correct answer chosen among verified alternatives, correctness-checking does not expose the mark and correctness-driven fine-tuning does not overwrite it, with 98.96% to 100% of owner matches retained. Because the verifier reads the parsed solution rather than the wording, answer-only extraction leaves the mark intact, and under that attack this method keeps 99.8% balanced accuracy while all six text watermarks fall to chance at 50.0%.

(2) The paper defines mark removal precisely, as finding another valid solution.

Resistance to removal is usually argued informally, by showing that a rewriter or a paraphrase model fails to strip the mark, which does not say what an attacker would have to do instead. Requiring another valid solution does say it, and turns an open-ended claim into one that a single experiment can settle. That is a contribution to how subsequent work can argue about removal.

Critical weaknesses

(1) The security claim is not established, because no exact solver is ever run on the protected problems.

A. The five commercial reasoning models of Table 1 stand in for the solver that removal route (i) requires, since Section 3.1 defines that route as re-solving "with a key-independent solver", yet no exact solver for X3C, Kakuro or anchored graph coloring is run anywhere in the paper. Those five models reach at most 35/96 validity, so the experiment measures whether an LLM can solve the problems from scratch, not whether an exact solver can find another solution.

B.The screening was performed by two models that the paper does not identify. Appendix A kept later candidates "only if neither of two external reasoning models found a different valid solution", but neither their identity, their settings nor their budget is reported, and the fixed screening budget of Section 3.2 is also unreported. The hardness of the catalog is defined relative to those models, so the filter cannot be reproduced or checked.

(2) The paper's own results contradict its stated conclusions.

A. Table 4 reports owner match, validity and MMLU under model modification but not the acceptance probability. "SVA, related checkpoints" leaves 56/96 owner matches, which by Equation 7 gives acceptance probabilities of 3.61%, 4.50% and 3.09%, so the owner would accept this model with only 3% to 4.5% probability, while it stays valid on 93.75% of the protected problems with MMLU unchanged at 77.27. That meets the attacker-success definition of Section 3.1, yet Section 4.6 counts every row as a failed removal.

B. The abstract's invariance claim is stated without its scope. It reads "rewriting that preserves the solution preserves the mark", yet Table 5 gives an owner match of 100.00% under the canonical trained prompt, 95.83% under four new prefixes, 40.63% under full Chinese, 4.17% under structured JSON, and 0 of 192 valid outputs under two isomorphic views per problem. In the last three conditions validity falls by exactly the same amount as the owner match, so the model stops producing valid answers rather than returning a different solution, and the claim should be scoped to rewriting of the answer rather than of the problem statement or the output format.

Questions for authors
  1. Related to Weakness 1. Was an exact solver for X3C, Kakuro or anchored graph coloring ever run on the protected problems with the stored solution blocked, and if so, what time and node budget does it need?

  2. Related to Weakness 1. Which two models screened the protected candidates, with what settings and budget, and what is the fixed screening budget of Section 3.2?

  3. Related to Weakness 2. "SVA, related checkpoints" fails verification at 3.61% to 4.50% acceptance while staying 93.75% valid, so does the paper consider this a successful removal under its own Section 3.1 definition, and does the Section 4.6 conclusion still hold?

  4. Related to Weakness 2. To which class of rewriting does the invariance claim apply, given that owner match falls to 40.63% under full Chinese and 4.17% under structured JSON while validity falls by exactly the same amount?

Reviewer_HN8KOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper embeds a model ownership watermark in the choice of a valid solution to a constraint problem, rather than in the answer's wording. The owner stores two distinct valid solutions for each protected problem, uses a private random bit to select the training target, and verifies provenance through exact solution matches in black-box queries. The authors derive a binomial-tail false-acceptance bound for key-independent models and connect correctness-preserving answer replacement to the Another Solution Problem (ASP). Across three task domains using Qwen3-8B, the watermarked model reproduces the owner solutions on all 96 protected problems while retaining most of the solving gains on unseen problems. Experiments also examine rewriting, continued fine-tuning, and targeted removal.

Critical strengths
  1. The choice of carrier is meaningful. Encoding among valid solutions neither requires incorrect answers nor depends on retaining explanatory text; verification directly checks the mathematical object. This grounds the watermark more directly in task semantics than merely improving robustness at the wording level.
  2. The control effectively separates correctness from matching a private choice. WM and Control both solve all protected problems, but their owner-match rates are 100% and 55.21%, respectively, while their unseen-problem accuracies are also close. This shows that the detection signal comes from the private targets rather than being a by-product of solving accuracy.
Critical weaknesses
  1. Worst-case ASP hardness has not been translated into a practical removal cost. The authors acknowledge that average-case hardness is unproved, and the protected problems are screened using reasoning models. The attacks in Table 1 disallow tools and verifier feedback, so they primarily measure restricted search by particular LLMs, rather than the SAT/CSP solvers and local repair available to a white-box adversary. More importantly, Appendix C reports a WM match rate of only 4.17% under structured JSON inputs and zero under both isomorphic presentations. This suggests that an adversary might evade detection through input normalization rather than solving ASP. The effect of the same wrapper on ordinary tasks must be measured to determine whether this is a low-cost removal route.
  2. The observed loss of solving ability under removal may reflect general forgetting rather than an inseparable link between capability and watermark. Protected problems are repeatedly trained on and are substantially harder than unseen problems. All models score zero on the 384 stress problems, and the authors themselves attribute success on protected problems to reproducing trained choices (§4.5). Memorizing private answers to large problems and generalizing to smaller problems are therefore distinguishable behaviors. The interventions in Table 4 damage both, but do not rule out more selective forgetting. A training control using only ordinary reasoning data, together with removal experiments targeting protected-problem memory, is missing from this central interpretation.
Questions for authors

These are clarification or evidence requests that could change my assessment, rather than suggestions for future work:

  1. Under the same input-normalization/relabeling wrapper, how do verification acceptance on protected problems and accuracy on the 1,536 unseen problems change? Do the zero matches in the appendix primarily reflect solving failures, parsing failures, or loss of the private solution preference?
  2. Could you report the cost of ASP attacks with dedicated solvers and verifier feedback, and provide either an ordinary-reasoning-only training control or a selective-forgetting control to distinguish task generalization from watermark memory? Please also clarify whether the screening models overlap with the evaluated attack models.
Reviewer_QEwoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a model ownership watermark based on which valid solution a model returns to a constraint problem. Each protected problem has two verified solutions, and a private bit selects the training target. Verification checks the parsed solution rather than its wording. The method is evaluated on X3C, Kakuro, and anchored graph coloring using Qwen3-8B. The watermarked model reproduces all 96 protected owner solutions and retains most of a matched control's improvement on 1,536 unseen problems. The paper also evaluates output rewriting, answer replacement by external language models, and several model interventions. It connects valid answer replacement to the Another Solution Problem and gives a false-acceptance bound for key-independent outputs.

Critical strengths
  1. Putting the mark in the chosen solution is a neat idea. If the parsed solution stays the same, changing the wording or the order of the answer cannot remove the mark. Both validity and an owner match can be checked from the output, without access to model weights or logits.

  2. The Control model makes the experiment more informative. It sees the same protected prompts and task supervision, but its target choices are independent of the owner's key. It solves all protected problems and matches the owner on 55.21%, compared with 100% for WM. This is a useful check that the model learns the private choices. Measuring unseen constraint-solving accuracy also catches utility losses that MMLU misses.

Critical weaknesses
  1. The missing solver attack is my main concern. These are explicit constraint problems, yet the replacement attacks use language models without tools or verifier feedback. Some protected instances were even selected because two reasoning models failed on them. Why not test a constraint solver with the supplied solution excluded? The attacker in Section 3.1 is allowed to do this. The authors correctly note that worst-case ASP hardness does not establish hardness of their instances, but the current experiments leave exactly that question open. If a solver finds alternatives cheaply, much of the motivation for this construction falls away.

  2. Table 5 raises another concern about how easily verification can be disrupted. Owner matches fall to 40.63% with Chinese inputs and 4.17% with structured-JSON inputs; the tested isomorphic views produce no valid answers. These input changes do not disprove the output-rewriting claim. Still, they suggest a simple attack worth testing: apply a fixed transformation to incoming prompts before passing them to the model. Would this defeat verification while keeping ordinary task performance? The protected problems are much harder than the ordinary unseen set, and all models fail the larger stress set. I therefore do not think the tested weight interventions are enough to conclude that removing the mark must cost ordinary solving ability.

Questions for authors
  1. What are the success rates and runtimes of standard constraint solvers when given a protected instance and the WM solution, with that solution explicitly excluded? Please report results by domain and include the cost of verifying a replacement.

  2. If a fixed input-normalization or relabeling wrapper is applied without knowing the private catalog, what happens to both verification acceptance and unseen-problem utility? Table 5 already suggests that this test could change the robustness assessment.

  3. Which two models screened the later protected problems, and which reported attackers were independent of that screening? Please separate the results for the inherited and later catalogs. This would help interpret the reported replacement rates.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.