acceptodds
Under review as a conference paper at ICLR 2027

RouterMAS: Value-Preserving Watermarking for Multi-Agent Routing

Abstract

Multi-agent systems derive capability from how they delegate work, yet embedding an ownership signal into delegation can alter every decision that follows. Exist- ing behavioral and expert-routing watermarks provide signature carriers without characterizing the routing freedom left by a system’s required continuation utility and cost. We propose RouterMAS, a value-preserving watermarking framework for multi-agent routing. Our key insight is that fixing task values need not fix the routing distribution: Bellman recursion converts prefix-wise preservation into local conservation equations, exposing an admissible space of probability redistributions. RouterMAS first constructs this space from continuation values, then encodes a secret key through a minimum-information-change routing law, and finally verifies the signature using evidence induced by the same law. An error budget connects value estimation and deployed-policy approximation to accumulated return drift. Controlled finite-state experiments validate conservation, sequential verification, and algebraically inert controls. Across reasoning, code generation, and environ- ment interaction, RouterMAS preserves task performance and operating cost while maintaining reliable detection. Its usable signature space expands with routing alter- natives and contracts as additional task values are protected, connecting watermark strength to the structure of multi-agent orchestration.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
watermark, Multi-Agent System

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 4 reviews, above 27% of the others.
Reviewer_ULZROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduces RouterMAS, a watermarking scheme for multi-agent systems that embeds signals into task delegation distributions. Recognizing that routing choices propagate to downstream reasoning, retries, and execution costs, the authors enforce history-wise preservation of expected continuation utility and invocation cost rather than mere single-step plausibility or marginal average performance.

Critical strengths
  • Beyond characterizing the feasible subspace, the paper analyzes when no valid watermarking direction exists, when to fall back to the original router, and how value estimation errors and controller approximation errors accumulate into overall return drift.

  • Controlled finite-state experiments allow exact calculation of continuation values to cleanly isolate the effects of full value constraints, myopic value constraints, full-rank constraints, and invalid keys.

Critical weaknesses
  • Constrained cost only captures modeled runtime agent calls. The total end-to-end cost of value estimation and controller training, and how it is amortized, is not reported.

  • Confounded comparison between key-directed selection and random feasible perturbation. In Appendix Table 8, the full-constraint method induces a mean KL of 0.0929 versus just 0.0065 for random feasible perturbation. Since expected per-step LLR evidence equals conditional KL, perturbation KL must be matched to tell whether the TPR gain comes from directional selection or simply a much larger distributional shift.

Questions for authors
  • How is value preservation concretely verified on real tasks? What are the confidence level and simultaneous coverage method for the value-estimation error bound, and how many independent continuation rollouts (along with confidence intervals) are used to estimate DU,95D_{U,95}? Additionally, how are the exact continuation values obtained for the Exact-QQ ablation labeled as GSM8K in Table 1? Are they computed exactly on the real system, or via an oracle within a finite proxy model?

  • What is the total end-to-end deployment cost? Please report the costs of counterfactual rollout collection, value-estimator training, controller training, online routing, and verification. When encountering unseen execution histories at test time, does the system require fresh rollouts, or does it rely solely on the trained estimator—and how do cost and value drift compare between the two?

  • Does key-directed encoding still outperform random feasible directions under a matched realized KL? Could you scale the random feasible perturbation to match the empirical KL of RouterMAS, pair it with the likelihood-ratio detector corresponding to its own perturbed routing distribution, and evaluate the isolated gain of key-directed optimization?

  • What is the cost-utility trade-off of function-preserving erasure attacks? Could you plot the trade-off curve among attack training budget, detection rate, and task utility loss, and evaluate prefix-level value drift after the attack rather than only aggregate success rate? Finally, can increasing the number of verification decisions recover detection power against erased and behavior-cloned routers?

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

RouterMAS watermarks a multi-agent routing policy by changing delegation probabilities within constraints on expected continuation returns. With a fixed executor and exact values, these constraints preserve the protected returns at every execution prefix. A keyed KL objective selects the marked law, and a sequential likelihood-ratio test compares it with a retained reference router. The paper extends the construction to estimated values and compiled controllers. Finite-state checks and four real-task evaluations report small utility changes and high clean-copy detection, with weaker detection after several modifications.

Critical strengths
  1. The value constraints identify which routing changes preserve protected returns at every prefix under a fixed executor. The paper uses these changes to encode a key and construct a matching sequential detector.
  2. The finite-state controls distinguish continuation-value preservation from immediate-value matching and test cases with no usable marking direction. They support the need for continuation values and check that the method returns the reference router when marking is infeasible.
Critical weaknesses
  1. Key-blind reoptimization substantially weakens detection while leaving measured utility almost unchanged. At the same 256-decision budget, detection falls from 95.2% to 32.2%, success changes from 94.1% to 94.0%, and normalized cost from 1.009 to 1.010. This limits the demonstrated protection against modified copies.
  2. The bound on return drift relies on valid value-estimation error bounds at histories reached by the deployed policy. The paper reports independent recalibration but does not specify how these bounds are constructed or their confidence level. The reported 95th-percentile value drift measures differences between policy values and does not establish the required prediction-error coverage.
Questions for authors
  1. After key-blind reoptimization, does likelihood-ratio evidence still accumulate with longer traces? If so, what decision budget is needed for reliable detection at the same threshold?
  2. How are the continuation-value error bounds constructed and calibrated? Do they hold simultaneously over histories reached by the deployed or compiled policy, and with what confidence?
Reviewer_uKG6OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates how to embed watermarks into multi-agent systems (MAS) by perturbing routing probabilities while preserving downstream task utility and execution cost (RouterMAS). Using Bellman recursion, the authors formulate continuation value preservation at each execution prefix as local linear constraints, apply KL-regularized key encoding within the resulting feasible subspace, and perform sequential detection via conditional likelihood ratios.

Critical strengths
  • Formulating utility preservation at the level of each execution prefix's continuation value is stricter and better motivated than merely maintaining global average task success, as it prevents positive and negative utility drifts from canceling out across different states.
  • The feasible subspace, watermark encoder, and sequential detector are cohesively unified under the same routing distribution framework. Under the idealized assumptions of a finite horizon and fixed downstream executors, the theoretical derivation (Proposition 1) is sound, and the finite-state ablation studies effectively probe the proposed components.
Critical weaknesses
  • There is a substantial gap between exact theoretical value preservation, ownership attribution claims, and practical deployment guarantees. First, Proposition 1 requires exact continuation values, whereas Eq. (1) relies on a calibrated error envelope whose construction, confidence level, and robustness to watermark-induced distribution shifts are omitted in Appendix E.2. Reporting only the 95th percentile of estimated drift (DU,95D_{U,95} in Table 3) obscures the worst 5% tail behavior and lacks uncertainty quantification. Second, the false-positive guarantee in Section 4.5 only tests against a single fixed reference router pp; rejecting pp does not rule out independently trained, unwatermarked routers. Moreover, in Table 5, key-free blind erasure drops detection from 95.2% to 32.2% while task utility remains intact (94.1% vs. 94.0%), undermining practical robustness claims.
  • The evaluation suffers from incomplete cost accounting, confounded baseline comparisons, and missing experimental details. Table 4 reports a ~3 ms overhead by counting only solver time while excluding counterfactual rollouts and LLM inference; yet Appendix E.2 implies 196,608 full continuations (256 prefixes x 6 actions x 128 rollouts) for auditing alone. Furthermore, the comparison between random feasible perturbations and Exact-Q in Appendix F is confounded by a massive mismatch in perturbation strength (Mean KL of 0.0065 vs. 0.0929), and it is unclear how "Exact-Q" is even defined or computed for an open-ended LLM benchmark like GSM8K in Table 1.
Questions for authors
  • How is the error envelope in Eq. (1) and Appendix E.2 formally constructed, and how do you guarantee simultaneous coverage when the watermarked policy alters the prefix visitation distribution? Please also report the worst-case tail drift (beyond the 95th percentile), the scaling factor ρ\rho, and the fallback rate to the original router.
  • What is the false-positive rate of the detector when evaluated against independently trained, unwatermarked routers (e.g., varying random seeds, temperatures, or training subsets) rather than the exact reference router pp used in the likelihood ratio?
  • What is the total end-to-end computational cost (in wall-clock time, token usage, and LLM calls) of offline auditing/rollouts versus online routing in Table 3, and how exactly is "Exact-Q" obtained for GSM8K in Table 1?
  • Does the detection advantage of key-aligned perturbations over random feasible perturbations still hold when both methods are strictly matched on trajectory/conditional KL divergence? Additionally, how was AgentMark-F adapted to ensure a fair comparison regarding key conditioning vs. marginal distribution preservation?
Reviewer_74hEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes RouterMAS, a value-preserving watermarking framework for multi-agent routing policies. The authors characterize admissible probability redistributions using Bellman continuation-value constraints, encode a secret-key signal through KL-regularized optimization, and verify the resulting watermark using sequential likelihood-ratio testing. Experiments on GSM8K, HumanEval, MBPP, and ALFWorld show high watermark detection rates with relatively small changes in task success and operating cost.

Critical strengths

Principled mathematical formulation. The characterization of prefix-wise continuation-value preservation as local linear constraints is a meaningful contribution. It provides a systematic way to identify routing freedom without altering the protected expected returns.

Coherent embedding and verification framework. The connection between KL-regularized encoding, feasible probability geometry, and sequential likelihood-ratio verification is well motivated. The experiments demonstrate promising detection-performance tradeoffs.

Critical weaknesses

Limited practical preservation guarantees and scalability analysis. Exact preservation depends on true continuation values at every relevant history, whereas the implementation relies on estimated values and a compiled controller. The paper does not sufficiently establish the statistical coverage of these approximations over unseen histories. The reported solver latency also excludes the potentially expensive counterfactual audits.

Security assumptions and robustness remain insufficiently established. The key-dependent score construction and verification access requirements need clarification. Moreover, the watermark can be substantially weakened through policy modification while retaining similar task performance, raising concerns about its effectiveness against adaptive removal.

Questions for authors

How are the continuation-value error bounds calibrated, and what statistical guarantees apply to previously unseen histories visited by the marked policy?

What is the total end-to-end computational cost of watermark construction, including counterfactual rollouts and controller training?

How is the secret-key-dependent score constructed, and what access does an attacker require to forge or remove the watermark?

Can the authors reconcile the AI-use statements on page 10 and in Appendix H, particularly regarding experiment planning?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.