# Checking Leakage Witnesses versus Certifying Bounded Non-Leakage

arXiv: https://arxiv.org/abs/2609.32134 · HTML: https://mlsanity.com/paper/2609.32134/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 56 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Builds on (most cited first, 12 of 12)

- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Universal and Transferable Adversarial Attacks on Aligned Language Models](https://mlsanity.com/paper/2307.15043/) (2023)
- [Jailbreaking Black Box Large Language Models in Twenty Queries](https://mlsanity.com/paper/2310.08419/) (2023)
- [Llama Guard: LLM-based Input-Output Safeguard for Human-AI Conversations](https://mlsanity.com/paper/2312.06674/) (2023)
- [AutoDAN: Generating Stealthy Jailbreak Prompts on Aligned Large Language Models](https://mlsanity.com/paper/2310.04451/) (2023)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [The Counting Power of Transformers](https://mlsanity.com/paper/2505.11199/) (2025)
- [Parameterized Hardness of Zonotope Containment and Neural Network Verification](https://mlsanity.com/paper/2509.22849/) (2025)
- [The Head Complexity of Boolean Functions in Single-Layer Attention](https://mlsanity.com/paper/2609.04046/) (2026)
- [The Complexity of Verifying Loop-Free Programs as Differentially Private](https://mlsanity.com/paper/1911.03272/) (2019)
- [MAJORITY-3SAT (and Related Problems) in Polynomial Time](https://mlsanity.com/paper/2107.02748/) (2021)

## Abstract (arXiv)

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 coNPPP-complete at every fixed rational cutoff in (0,1). 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 41.06% 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.