acceptodds
Under review as a conference paper at ICLR 2027

Checking Leakage Witnesses versus Certifying Bounded Non-Leakage

Abstract

When a language-model audit finds no leak, what is needed to certify non-leakage? We study guarantees over a declared prompt domain under an executable leakage criterion and decoding rule. For general bounded polynomial-time evaluators, a supplied leaking execution is polynomial-time checkable, while leak existence is \NP-complete and deterministic certification is \coNP-complete. Exact stochastic certification is \coNP^\PP-complete at every fixed rational cutoff in . Restricting the computation can change these bounds. For example, certification is in \coNP when all randomness is a terminal draw from an efficiently computed finite probability table. Attention models admit polynomial-time certification when local dependency windows of logarithmic length precede one global head, given deterministic decoding, fixed vocabulary, exact rational weighted means, a direct binary affine readout and finite-automaton prompt domains. A construction with two global layers instead makes certification \coNP-complete over template domains, with one head per layer, polynomial width, logarithmic precision and an inverse-polynomial logit margin. Planted-secret experiments measure what finite audits miss relative to complete references. Among 30 secret–model-state pairs that leak under greedy single-prompt execution on their secret's 4,096-prompt domain, uniformly selecting 256 recorded evaluations per pair misses every leak for an expected of these pairs. Batched and single-prompt checks disagree on one complete-domain decision among all 48 fine-tuned pairs, while a same-order repeat reproduces every single-prompt output. These results distinguish computational conditions for certification from the coverage and execution conditions needed to interpret a negative audit.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM safety, leakage certification, computational complexity, verification, transformers, decoding, red teaming, privacy auditing

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_udYpOpenReview ↗
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
  1. 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.

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

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

  4. 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.

  5. 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?
Reviewer_L3kxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper examines the difference between finding a prompt that leaks information and proving that leakage stays below a threshold for all prompts in a defined domain. It analyzes how the difficulty of this verification changes with different decoding methods and attention structures. Experiments with planted secrets investigate how limited prompt testing can miss leaks and how results may differ between batched and single-prompt execution.

Critical strengths
  • The paper clearly distinguishes detecting information leakage from certifying a leakage bound over all allowed prompts. It explains why an audit that finds no leak does not provide such a guarantee.

  • The paper shows that leakage certification can be easier or harder depending on the attention structure. It compares local attention followed by a global head with two global attention layers and explains how these structures affect the difficulty of certification.

Critical weaknesses
  • Most of the general complexity results build on existing work. Sections 4.2 and 4.3 provide more specific results on decoding and attention structures, but the experiments do not examine these settings. Instead, the experiments focus on missed leakage in finite prompt audits, leaving a weak connection between the main theoretical results and the experiments.

  • The complete-domain experiments use only two Qwen3 models, one SFT seed, fixed 16-character canaries, and a single set of 4,096 prompts. The reported 41.06% expected miss rate is based on the 30 targets with recorded leaks under this setting. The paper does not examine how the results change with canary length or different prompt sets.

Questions for authors
  • Can the authors provide experimental evidence related to the decoding and attention structures presented in Sections 4.2 and 4.3?

  • What are the eight choices for each of the four prompt components, and what exact template was used to generate the 4,096 prompts? How were these choices selected?

  • Why was the canary length fixed at 16 characters? How sensitive are the witness counts and miss rates to canary length?

Reviewer_qEr3OpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper investigates the theoretical and empirical conditions required to certify bounded non-leakage when language model safety audits fail to uncover secret disclosures. The theoretical portion formalizes language models, decoding routines, and leakage judges as explicit polynomial-time computational circuits or clocked machines, classifying the computational complexity of leakage existence (NP-complete), deterministic zero-threshold certification (co-NP-complete), and exact stochastic threshold certification (co-NP^PP-complete). It further establishes that certification is in co-NP under terminal probability table sampling, but returns to co-NP^PP-completeness when sampling occurs during autoregressive generation under a fixed nucleus rule. For attention architectures, it proves an exact dynamic programming certification algorithm in P for single-head global rational attention with logarithmic local windows, while proving that two-layer global attention with one head per layer makes certification co-NP-complete. The empirical portion introduces CanaryBench, which compares continued adaptive search against complete enumeration over a frozen 4,096-prompt grammar on Qwen3-8B and Qwen3-32B targets, measuring missed targets under budgeted selection (41.06% uniform miss at B=256) and noting evaluation discrepancies between batched and single-prompt executions.

Critical strengths
  • The paper formalizes a crucial conceptual distinction between observing absence of evidence in finite audits and certifying domain-wide non-leakage, explicitly identifying the gap between polynomial-time witness verification and the higher complexity of universal guarantees.
  • The theoretical treatment differentiates the complexity consequences of architectural features (local window radius versus global multi-layer context) and decoding mechanics (terminal sampling versus intermediate autoregressive token choices), supported by comprehensive complete-domain baseline maps that quantify the sparsity of leakage witnesses.
Critical weaknesses
  • The theoretical proofs and formal write-up exhibit pervasive synthetic, LLM-generated characteristics rather than genuine mathematical rigor. Across the 62 pages, lengthy sections of the appendices read as mechanical compilations of standardized complexity gadgets (such as routine Cook-Levin/Tseitin reductions and textbook Tseitin transformations) padded with excessive formalistic jargon that wraps straightforward observations without providing deeper insight into real neural network behavior. The manuscript explicitly acknowledges that generative AI tools were used extensively for literature searches, proof review and development, circuit constructions, fixed-threshold rescaling, and manuscript review. This heavy reliance on AI drafting manifests in superficial formalizations—such as wrapping standard SAT formulas in constant-depth circuit shells (Theorems 1–5)—that produce mathematically trivial variants of classical complexity theorems while failing to connect meaningfully to non-trivial neural representations.
  • There is a severe disconnect between the idealized complexity models and practical language model certification. The tractable result in Proposition 5 relies on extreme, unrealistic assumptions: a single global head, exact rational weighted means, a direct binary affine readout without subsequent feed-forward or normalization layers, and a logarithmic receptive field radius R = O(log N). Conversely, the empirical CanaryBench experiments evaluate standard pretrained autoregressive transformers under greedy decoding via black-box API queries, running none of the proposed theoretical certification algorithms nor validating the stochastic threshold bounds on real models. Furthermore, key experimental assets suffer from missing historical training hyperparameters (learning rates, LoRA ranks, and step counts in Appendix C.1), and Appendix C.6/C.7 needlessly consumes extensive space running off-the-shelf Glucose 3 SAT solvers on textbook pigeonhole and random 3-CNF instances to demonstrate that unfinished runs yield lower bounds, which adds no substantive value to neural language model auditing.
Questions for authors
  • Beyond standard textbook padding gadgets and Tseitin reductions, what is the core structural insight that distinguishes your general circuit reductions (Theorems 1–5) from classical satisfiability and majority-SAT results cited in Table 3 and Table 4?
  • Can you demonstrate an actual implementation of the local-to-global dynamic programming algorithm from Proposition 5 on a non-trivial neural network, and evaluate its tractability and tightness when real-world features like multi-head projections, Softmax approximations, or LayerNorm are introduced?
  • How do you address the missing experimental provenance in Appendix C.1 (the loss of historical LoRA ranks, optimizer steps, and learning rates), and can you ensure that SAFE targets represent genuine refusal learning rather than failed canary injection?
  • In Section 5.3, the interpretation of the R1 frozen record map selection as an online B-query audit explicitly assumes call-position invariance. Did you empirically verify whether outputs remain bitwise identical when prompts are evaluated out of order or as isolated individual calls without running the full 4,096-sequence sweep?
Reviewer_iGBmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

From my understanding, the paper derives complexity classifications for determistic and stochastic models through unifiedly formalizing leakage discovery and certification under bounded evaluators.

Critical strengths

The paper to my undersanding unifiedly formalizes leakage discovery and certification under bounded evaluators. The paper presents results across multiple models and seeds.

Critical weaknesses

The paper to my understanding has limited novelty in terms of theoretical contribution with respect to prior work and relies on highly restrictive assumptions that do not apply to modern autoregressive LLMs. Moreover, the evaluation is weak and largely disconnected from the theoretical results.

Questions for authors
  1. Could the authors clarify the novelty of the theoretical results with respect to established results in LLM complexity theory, SAT, counting, and probalistic verification?
  2. Can the authors demonstrate whether the results apply to any practical modern transformer architecture?
  3. Can the authors provide further experiments to more directly emperically evaluate the theoretical claims?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.