- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper investigates the query and communication complexity of corruption detection in multi-agent systems. By modeling agent behaviors as input-output matrices, the authors formulate corruption detection as a matrix difference testing problem. They establish matching upper and lower bounds for deterministic and randomized protocols in both single-worker and multi-worker settings. The results suggest that randomized linear probing and hashing can substantially reduce detection costs, while communication among workers provides no asymptotic improvement over a star topology.
Critical strengths
-
The paper presents a well-defined theoretical framework for corruption detection through matrix difference testing.
-
The paper establishes matching upper and lower bounds for query and communication complexity across multiple settings.
Critical weaknesses
Unrealistic Oracle Assumption The framework assumes exact access to (Pq) for arbitrary input distributions, which is generally unavailable in real-world LLM agents. This assumption substantially limits the practical relevance of the results.
Oversimplified Threat Model The framework assumes a trusted reference, faithful controllers, and a single corrupted worker, overlooking realistic adversarial behaviors and dynamic agent interactions.
Lack of Empirical Validation The paper provides no experiments with actual LLM agents or multi-agent systems, leaving the applicability of its theoretical findings unsubstantiated.
Questions for authors
-
How can the assumed linear-probing oracle, which returns the exact distribution (Pq), be implemented in practical LLM-based agents? Would the theoretical guarantees still hold if only sampled outputs were available?
-
How would the proposed framework handle corrupted workers that deliberately manipulate their responses to verification queries, rather than faithfully executing the probing protocol?
-
Could the authors provide a practical example or preliminary experiment demonstrating how the proposed framework could be applied to an actual LLM-based multi-agent system?
Thank you for raising the oracle, threat-model, and empirical questions. The revised paper adds a noisy setting with inexact replies for queries (§6, Theorems 6.1–6.2), and preliminary experiments on synthetic data with inexact replies (Appendices J–K, Figures 1–4).
From sampled outputs to noisy probes
Our formulation of the theoretical setting focuses on detecting model differences from behavior access, since this issue comes up even in the presence of the assumed reference, faithful controllers, and exact responses. The formulation then abstracts the issue from other factors like adversarial controllers or inexact responses, allowing in-depth investigation and paving the road for more complex settings.
We can extend the analysis to more complex settings. In particular, Section 6 now includes results for the noisy setting with inexact responses to queries, i.e., the reply is only known to be in TV-distance ζ from the exact reply. Theorems 6.1–6.2 give query and communication bounds for single worker and multiple workers, with proofs in Appendices G–I. The analysis in Appendix G.3 shows that when the noise level is higher than the model difference (i.e., ν≤2ζ where ζ is the noise level and ν is the difference between the corrupted and reference), the inexact replies can conceal corruption. Theorems 6.1–6.2 show that when ν>2ζ then the query/communication bounds are similar to those in previous discretized/probabilistic settings.
Concrete deployment and trust boundary
Consider a supervisor that delegates to tool-routing workers. A finite catalog fixes the input templates and context, and each response is mapped to a finite set of tool choices, including refusal and invalid output. The reference can be the categorical policy of a pinned, approved version exposed to the supervisor. A gateway outside the worker's control can issue the probes, draw from the deployed worker under a fixed decoding policy, map outputs to the action catalog, and run the prescribed encoding. An API that supplies only samples from the approved version leaves reference-estimation error to account for.
If a worker can replace the gateway's replies with reference replies, its transcript can match that of an honest worker even when its deployment behavior differs. Our guarantees therefore consider trusted probe execution and cover deviations in observed behavior within that trust boundary. Handling fabricated replies or selective behavior that differs between verification and deployment requires additional assumptions, which is left for future work.
Preliminary experiments
We added synthetic single-worker verification and multi-worker identification. The experiments are for the single-worker or multiple workers + random protocols in the noisy setting, and the detailed setup and results are in Appendix J and K.
The table below gives calibrated defaults from Appendix J.2/J.4 (single worker) and K.2/K.4 (multiple workers), with β=1/4, ν=1/8, ζ=1/32, and target error ϵ=1/16. The honest and corrupted single-worker results are shown separately. This brief summary demonstrates the success of the protocols.
Here we simulated the replies according to the practical scenario: for query q to model P, sample input indices from q and use the multinomial counts q^ to get the output distribution z=Pq^, and then sample the reply from z to get the sampled version z^ and use z^ as the noisy reply. With large enough samples, z^ will not violate the TV-distance budget ζ. No TV-budget violations occurred in these configurations. At the larger defaults, the mean output-draw counts are about 1.30×1010 and 4.38×1010, respectively. The larger dimension sweeps (J.4/K.4, Figures 2 and 4) reach 224 inputs and 218 outputs. Across a 16× increase in output dimension, the calibrated sample count rises about 15×, while mean communication changes by only a few percent within each worker state. At $N_{ m out}=2^{16}$, using about $k_{ m safe}/16$ gave 16 false alarms in 16 honest single-worker trials (Appendix J.4). The experiments measure the implemented procedural tables on synthetic ensembles. The worst-case bounds use the finite tables in the proofs. An end-to-end evaluation with real model calls and a trusted gateway remains open.