acceptodds
Under review as a conference paper at ICLR 2027

Theoretical Possibilities and Limits of Efficient Corruption Detection in Multi-Agents

Abstract

This work initiates a theoretical study of the query and communication complexity of detecting a corrupted matrix via queries in the form of linear probes. This is inspired by corruption detection in multi-agents, since reliable multi-agent systems need to detect changes in worker behavior without exchanging complete models or exhaustive output tables. We establish matching upper and lower bounds for query and total communication bits using deterministic and private randomized protocols, both for verifying a single worker and for identifying a corrupted worker in a complete network. These results confirm the possibility of detection with efficient query and communication. In particular, we show that randomization can yield an exponential improvement over deterministic ones and thus achieve efficient query bounds. Our results provide a theoretical foundation for verification mechanisms in multi-agent systems.

Primary area:
learning theory
Keywords:
Communication Complexity, Matrix Difference, Multiple Agents

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_rXAwOpenReview ↗
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
  1. The paper presents a well-defined theoretical framework for corruption detection through matrix difference testing.

  2. 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
  1. 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?

  2. How would the proposed framework handle corrupted workers that deliberately manipulate their responses to verification queries, rather than faithfully executing the probing protocol?

  3. 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?

1 comment

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 ζ\zeta 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ζ\nu\le 2\zeta where ζ\zeta is the noise level and ν\nu is the difference between the corrupted and reference), the inexact replies can conceal corruption. Theorems 6.1–6.2 show that when ν>2ζ\nu> 2\zeta 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\beta=1/4, ν=1/8\nu=1/8, ζ=1/32\zeta=1/32, and target error ϵ=1/16\epsilon=1/16. The honest and corrupted single-worker results are shown separately. This brief summary demonstrates the success of the protocols.

Protocol and (Nin,Nout)(N_{\mathrm{in}},N_{\mathrm{out}})ErrorsMean worker probesSamples per probe kkMean transmitted bits
Single worker, (214,210)(2^{14},2^{10})0/256 honest, 0/256 corrupted732.02340,591156,359 honest, 45,997 corrupted
Single worker, (222,216)(2^{22},2^{16})0/64 honest, 0/64 corrupted747.9517,370,722171,683 honest, 49,359 corrupted
8 workers, (214,210)(2^{14},2^{10})0/1925,831.48348,8831,037,541
4 workers, (222,216)(2^{22},2^{16})0/642,515.7217,405,743435,943

Here we simulated the replies according to the practical scenario: for query qq to model PP, sample input indices from qq and use the multinomial counts q^\hat{q} to get the output distribution z=Pq^z = P \hat{q}, and then sample the reply from zz to get the sampled version z^\hat{z} and use z^\hat{z} as the noisy reply. With large enough samples, z^\hat{z} will not violate the TV-distance budget ζ\zeta. No TV-budget violations occurred in these configurations. At the larger defaults, the mean output-draw counts are about 1.30×10101.30\times10^{10} and 4.38×10104.38\times10^{10}, respectively. The larger dimension sweeps (J.4/K.4, Figures 2 and 4) reach 2242^{24} inputs and 2182^{18} outputs. Across a 16×16\times increase in output dimension, the calibrated sample count rises about 15×15\times, 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.

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

This paper models multi-agent corruption detection through linear matrix queries and derives query and communication bounds for discrete and probabilistic models. Under its assumptions, randomization and hashing reduce verification costs, while complete worker networks provide no asymptotic advantage over stars in total queries and communicated bits.

Critical strengths
  1. The paper studies both query and communication costs, providing a unified framework for understanding efficient corruption detection across multiple agents.

  2. Matching bounds characterize resource requirements within the stated regimes, while carefully designed probes enable verification with one query and finite communication.

Critical weaknesses
  • W1: Insufficient novelty positioning. The paper omits Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra, whose Theorem 18(2)–(3) overlaps with specific probe and collision arguments in Lemmas B.5–B.6. A direct comparison is needed to assess the additional contribution of the adaptive verification, finite-bit protocols, and network identification results.
  • W2: Limited practical relevance. The model assumes an exact reference, faithful controllers, and complete, exact distribution-valued responses. Although disclosed, these assumptions place reference construction, trust enforcement, and distribution estimation outside the analysis. Their implications for practical LLM verification remain unclear without a concrete connection to implementable access.
Questions for authors
  • Q1 — Related to W1: Which adaptive, finite-bit, or network arguments require techniques beyond the mentioned reference?
  • Q2 — Related to W2: What concrete verification setting supports the assumed reference, faithful controllers, and exact responses?
  • Q3: Theorem 5.1 establishes bounds for the one-query result, but leaves unrestricted local computation and preprocessing uncharged. How do uncharged local computation and preprocessing costs affect the one-query protocol’s practical efficiency?
3 comments
AuthorsOpenReview ↗

Response 1/2

Thank you for identifying the overlap with related work and for asking us to clarify the model setting.

W1/Q1. Relation to matrix-vector query complexity

We have updated the draft adding the references. The revised related-work paragraph and Lemmas B.5–B.6 explicitly credit Theorem 18(2)–(3) of [1]. Part (3) supplies the scalar finite-alphabet random-probe bound, and part (2) supplies the pair-collision argument underlying our fixed prior. Lemma B.5 also gives the rank-dependent and nonzero-query variants. We credit the unrestricted continuous zero-test argument separately in Appendix E.2.

Here we clarify additional techniques in our analysis. Our analysis concerns verification and identification under the stated communication convention. The honest-path characterization in Lemma B.4 represents adaptive verifiers by distributions over schedules on the reference execution and gives the exact two-sided error βm(A)/(1+βm(A))\beta_m(A)/(1+\beta_m(A)). The B.6 prior embeds collisions as legal bounded-integer corruptions, with a distribution fixed before the protocol coins. The finite-bit protocols transmit the privately chosen schedule and fingerprint indices and charge every binary message. In a network, the query analysis accounts for an unprobed worker identified by elimination. The bit lower bounds simulate each worker cut and apply private equality bounds to its charged traffic, allowing arbitrary peer messages. In the probability model, the rational grid and quantitative separation in Appendix E.2 make finite response labels possible.

[1] Meyer, Raphael A., William Swartworth, and David P. Woodruff. "Understanding the Kronecker matrix-vector complexity of linear algebra." International Conference on Machine Learning, 2025.

W2/Q2. What access can look like

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.

Here we describe a concrete example. Consider a learned routing policy with finitely many actions and a fixed input catalog. An approved snapshot provides the supervisor's reference. A separately protected evaluator can compute a requested mixture from a deployed probability table or sample its deployed policy on selected inputs. The model treats changes to the policy as corruption and assumes the evaluator follows the protocol. If an evaluator can fabricate reference replies, it can conceal a changed policy.

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 ζ\zeta 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 show that when the noise level is higher than the model difference (i.e., ν≤2ζ\nu\le 2\zeta where ζ\zeta is the noise level and ν\nu is the difference between the corrupted and reference), the inexact replies can conceal corruption. Theorems 6.1–6.2 show that when ν>2ζ\nu> 2\zeta then the query/communication bounds are similar to those in previous discretized/probabilistic settings.

AuthorsOpenReview ↗

Response 2/2

Q3. Cost of the exact one-query result

Theorem 5.1 counts calls to the matrix-vector oracle and transmitted bits. Forming its dense mixture can involve every input in the catalog. The finite grid in Appendix E.2 uses local quantization precision O(log⁡2(Nout/ν)+Ninlog⁡2(Nin/ϵ))O(\log_2(N_{\rm out}/\nu)+N_{\rm in}\log_2(N_{\rm in}/\epsilon)) bits per output coordinate for Nin≥2N_{\rm in}\ge2, and finite hash tables may incur substantial preprocessing and storage. On the other hand, our study mainly focuses on the query and communication bits required. The local process budget is not the focus.

Preliminary experiments on synthetic data

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. Below is a brief summary, which demonstrates the success of the protocols.

Synthetic taskObserved errorsMean probesMean transmitted bitsOutput draws per probe
Verify one honest worker0/64747.95171,68317,370,722
Verify one corrupted worker0/64747.9549,35917,370,722
Identify one corrupted worker among four0/642,515.72435,94317,405,743

Here we simulated the replies according to the practical scenario: for query qq to model PP, sample input indices from qq and use the multinomial counts q^\hat{q} to get the output distribution z=Pq^z = P \hat{q}, and then sample the reply from zz to get the sampled version z^\hat{z} and use z^\hat{z} as the noisy reply. In the experiments, the upper endpoint of a two-sided 95% exact binomial interval for each 0/64 result is 0.0560. These measurements characterize the tested synthetic ensembles and the implemented procedural tables.

I appreciate your rebuttal to my concerns, but I have decided to remain my original rating of 2 (weak reject) as my final decision, and here are the reasons. Your first response clarifies how your work differs from Meyer's; however, it also highlights a gap in the original manuscript, or even your work, of closely related work. Your second response explains why the idealized setting is worth studying and establishes a modest extension, but the overall contribution is still limited. Considering the overall quality, I believe the paper still falls a little from the bar for acceptance at ICLR.

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

The paper develops a study in terms of computational complexity bounds of detecting failure in matrix representation. In as far as I can see the paper does not deal with byzantine failure at agent level or any distributed failure detection. I see nothing wrong with this and the authors are clearly experts in the subject matter, but as such I really do not see the relevance to ICLR, nor did i see the case being made that it is.

Specifically, no agent failure neither benign nor adversarial is considered as far as I can see, nor any of the failures of the standard distributed systems community (crash, omission, etc) is analysed.

As such, I do not see how the paper fits ICLR CFP. I recommend the paper being submitted to a more relevant conference.

Critical strengths

The paper puts forward what seems to be a rigorous analysis to detecting corrpuption in matrixes in one-to-one interactions.

Critical weaknesses

As stated above, irrespective of the results, I do not see the relevance of this to ICLR in this form.

Even considering agent failures which is something that the paper does not consider, I'd have thought this is solidly in theoretical distributed systems territory but purely on matrix representation, this seems to me to be a TCS paper on a data/HW problem.

Questions for authors
  1. Can you argue for relevance of this result to the ML community (beside I guess that ML uses matrices?)
  2. What is new relative to detecting matrices, matrix–vector query complexity, Freivalds-style verification?
  3. Why is a faithful controller justified? Which concrete setup supports this?
1 comment

Thank you for asking us to clarify the connection to ML and the scope of the fault model. We agree that the paper does not analyze crash/omission failures, Byzantine consensus, or controllers that fabricate replies. The intended task is more specific to the deployment of AI models: detecting a fixed change in the behavior of a deployed learned model relative to an approved ground-truth reference. Our presentation will make this distinction more prominent.

Relevance to ML and a concrete setting

Our formulation formalizes the conditional input–output behavior of AI models as a matrix. A concrete example is a learned finite-action policy or an LLM evaluated on prompts. An approved checkpoint supplies the ground-truth reference, while deployed workers respond to given inputs. A version mismatch or changed deployment can then change the represented behavior, even when there are no crash/Byzantine/fabricate controllers. Our formulation focuses on detecting such model differences.

The information question is whether the detection must transfer the entire behavior table, and whether extra peer links reduce its total verification cost. Theorems 3.1–4.2 characterize these costs in the discretized model, while Section 5 addresses normalized probability tables. The conclusions concern observations and transmitted bits once the reference and access interface are supplied.

Relation to matrix testing and Freivalds-style verification

Random probing and fingerprinting are established ideas. We will explicitly credit that lineage, e.g., the matrix-vector query framework of [1], and the overlapping probe/collision primitives in [2]. Our contribution should not be read as inventing random-projection detection.

Our contributions are the resource characterizations in the specified distributed model: the finite-game formulation for adaptive, two-sided verification; protocols attaining the stated query and bit orders while paying for private seeds; and network lower bounds permitting adaptive worker selection and worker-to-worker communication. The latter require controlling traffic across worker cuts under the charged communication convention. In the probability setting, the proof also turns exact local separation into finite binary communication through a quantitative separation threshold and quantization. We will distinguish these results from the classical ingredients more clearly.

Why a faithful controller?

We focus on detecting the model difference. Even without adversarial controllers, model differences already lead to behavior differences, and we would like to study whether access to behaviors via queries can efficiently detect the difference. The controller is thus outside our modeled corruption boundary: the deployed behavioral model may change while the evaluator continues to execute the prescribed operation. This is a meaningful assumption for a separately protected evaluation service.

We agree that adversarial controllers are classic topics in distributed settings. However, our focus is on the new specific setting where undesired behaviors come from model difference. Model difference combined with adversarial controllers will be an interesting topic, but that requires first understanding the question of detecting the model difference alone.

Finally, we note that addressing fabricated controllers needs a different setting. In our current setting, if arbitrary fabricated responses are allowed, a corrupted worker can emulate the reference on every verification query, producing an indistinguishable transcript. Our paper does not solve that problem.

We will therefore present the work as a theoretical resource benchmark for reference-based verification of learned behavior under explicit access assumptions, rather than as a general solution to multi-agent failures. We recognize that this is a specific contributioin to ML reliability, rather than solving multi-agent failures completely.

[1] Sun, Xiaoming, David P. Woodruff, Guang Yang, and Jialin Zhang. "Querying a matrix through matrix-vector products." ACM Transactions on Algorithms (TALG) 17, no. 4 (2021): 1-19.

[2] Meyer, Raphael A., William Swartworth, and David P. Woodruff. "Understanding the Kronecker matrix-vector complexity of linear algebra." International Conference on Machine Learning, 2025.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.