- Rating
- 2(+1)
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies what it takes to certify that a model does not leak a secret over a fixed prompt domain, as opposed to simply failing to find a leak. Leakage is defined by an arbitrary efficiently computable judge on the output. For general evaluators the authors classify leak existence and certification (NP-complete and co-NP-complete in the deterministic case, co-NP^PP-complete with stochastic decoding), and then look at restricted settings. Certification becomes easier when all randomness is a final draw from an explicit table, and polynomial-time when local layers are followed by a single global attention head. It becomes hard again with two global layers. The experiments implant fake secrets into Qwen3 models, enumerate a 4,096-prompt domain, and use this as ground truth to measure what budget-limited audits miss.
Critical strengths
The paper is careful. Each result states its assumptions precisely, and the limitations section is honest about what the experiments do and do not test. I found the complete-enumeration setup useful, since it gives a ground truth against which partial audits can be evaluated. The finding in Section 5.4 that batched and single-prompt execution change one target's decision is small, but it is the kind of detail that matters when someone claims a model was "fully audited".
Critical weaknesses
-
My main concern is novelty. Theorems 1 to 5 are standard reductions from SAT, E-MAJSAT and Σ2-SAT, and Table 4 labels most of them as instantiations. The judge is an arbitrary output predicate, so nothing in the formulation is specific to leakage. I could not see what these results tell us about LLM auditing beyond what is already known from software testing and neural network verification.
-
The tractable cases in Propositions 3 and 5 assume one global head, no feed-forward or normalization layer after pooling, and exact rational arithmetic. No deployed LLM satisfies this. The hardness results, on the other hand, are worst-case and say nothing about whether a given trained model is hard to certify. So neither side of the boundary applies to the models used in the experiments.
-
The experiments do not test the theory. Decoding is greedy throughout, so the stochastic-threshold results are not exercised, and the architectural results are not examined at all.
-
Several empirical findings are what one would expect. The uniform miss rate is just the hypergeometric formula, and more search recovering more secrets is not surprising. The setup is also small (two models, one SFT seed), and the leakage check only looks for the full 16-character string plus one base64 decode.
-
The paper is hard to read. The main text tries to cover too many results, and with appendices it runs past 60 pages. I would suggest focusing the main text on one clear message.
Questions for authors
- Is there any model that is used in practice, such as a safety classifier or a monitoring probe, that falls into the tractable class of Proposition 5? Does the polynomial-time result survive if a feed-forward layer is placed after the final pooling layer?
- Regarding the disagreement between batched and single-prompt execution in Section 5.4, do the authors know what causes the differing outputs (for example, padding or numerical nondeterminism)? In a real audit, which execution condition should a certification claim refer to?