Bits Leaked per Query: Information-Theoretic Bounds for Adversarial Attacks on LLMs

• The proposed lower bound has limited practical implication. Although the bound could in principle inform safe query limits, its right-hand side depends on the specific attack’s mutual information term . As a result, (1) each attack yields a different threshold and (2) the defender must already know the attack to compute it—undermining real-world applicability.
  • Thank you for raising this concern.
  • First, the ability to place a theoretical lower bound on existing defence methods is valuable because it introduces a mathematical safety guarantee into LLM-security evaluations that often rely on heuristics, and it lets us compare multiple defences on a common scale. Assuming existing attacks, therefore, does not diminish the usefulness of our work.
  • Second, the real issue is whether the bound is robust to unknown attacks; the mere fact that it is derived with respect to known ones should not, in itself, be problematic.
  • To test generalization, we ran an additional experiment: we estimated $I$ and measured the actual value using different attack methods (GCG and PAIR), then counted how often the resulting bound was violated.
  • Using the same three tasks and seven LLMs as in the main study, we found that no instance fell below the bound, confirming its robustness, just as in Figure 1. We also bootstrap-tested the differences between bounds computed with the two attacks ($p=0.05$) and observed no significant variation in any setting. We will include this experiment and its discussion in the appendix in the camera-ready version.
• The independent assumption is usually invalid for realistic attacks (which are adaptive in nature). The theoretical bound assumes are independent given , but adaptive attackers choose each query based on prior outputs, so those responses are correlated. This dependency contradicts the bound’s premise and calls into question the results shown in Figure 1(a).
  • Thank you for highlighting this issue. The i.i.d. assumption was introduced only to streamline the original proof; it is not required for the theory itself. We have already verified that the theorem still holds without assuming i.i.d., as we prove below. Consequently, our theory also covers fully adaptive attack settings and multi-turn conversation settings.
  • In the camera-ready version, we will replace the current statement under the i.i.d. assumption and proof with the independence-free version in Section 2.

Theorem 1 (Information‑theoretic lower bound for adaptive attacks without the i.i.d. assumption)

Let

• $T\in\mathcal{T}$ be the target property with an arbitrary prior (finite, countable, or continuous);
• an attacker issue $N$ sequential queries, where the $n$‑th input $X_n$ is any measurable function of the past outputs $Z_{1:n-1}$ (i.e., the attack is adaptive);
• the model reply is $Z_n = g\bigl(X_n,T,U_n\bigr),$ where $U_n$ is internal randomness independent of $T$ and of all previous $(X_i,Z_i)_{i<n}$.

Define the per‑query leakage

For any tolerated error probability $0<\varepsilon<1$, every adaptive strategy must issue at least

Proof

1. Fano’s inequality.

Let the attacker’s estimate be $\widehat{T}=f(Z_{1:N})$ with error probability $P_{\mathrm{err}}:=\Pr[\widehat{T}\neq T].$ The $K$‑ary (or differential) Fano inequality gives $H_{\mathcal{T}}\bigl(P_{\mathrm{err}}\bigr) \ge H(T)-I(Z_{1:N};T).$

2. Chain rule without independence.

Always $I(Z_{1:N};T)=\sum_{n=1}^{N} I \bigl(Z_n; T \mid Z_{1:n-1}\bigr).$ Each term is upper‑bounded by $I_{\max}$ by definition, so $I(Z_{1:N};T) \le N I_{\max}.$

3. Combine the bounds.

For $P_{\mathrm{err}}\le\varepsilon$, entropy satisfies $H_{\mathcal{T}} \bigl(P_{\mathrm{err}}\bigr)<\log_2(1/\varepsilon)$, hence

4. Rearrange.

$N \ge \frac{\log_2(1/\varepsilon)}{I_{\max}},$ establishing the claimed lower bound.

∎

Interpretation.

The i.i.d. assumption in prior work is only used to equalise the mutual‑information terms. Replacing that with a uniform upper bound $I_{\max}$ suffices because the chain rule already accounts for correlations between successive replies. Thus, the result holds for fully adaptive, stateful attacks.

• Some slight notation issues persist. The symbol denotes the attack outcome in Theorem 1, yet in Section 4 it is reused for “temperature.” Additionally, maybe “” in theorem1 is a typo?
  • Thank you for catching the notation clash. We will keep $T:=g(Y)$, rename the temperature to $\tau$, and correct the typo. These edits clarify the notation without affecting any results.

• Regarding usefulness in the decision-making phase
  • Thank you for the insightful comment. Our lower bound enables several concrete actions for practitioners, such as:
    1. Compute a safe query budget: By measuring the average information leaked per query $I(Z; T)$, we can instantly derive $N_{\max}$ (the safe limit on “suspicious” queries). If we want to expose top-$k$ logits while keeping attack risk below 1 %, we can set a rate limit that automatically stops serving logits once a user exceeds $N_{\max}$.
    2. Rate-limit suspicious traffic: Estimate $I(Z;T)$ once; flag or throttle when a user’s suspicious queries exceed N_\max.
    3. Benchmark red-team efficiency: Using the gap between the empirical query count $N$ attack $N_{\rm attack}$ and the theoretical lower bound N_\max as a metric lets us quantify how close an attack is to the information-theoretic limit and how much room for improvement remains.
  • As you suggested, a more modern MI estimator might further shrink the gap between the theoretical and empirical lower bounds. To test this, we replaced our original estimator with the one you recommended, SMILE [1], and compared the ratio between the theoretical lower bound N_\min^{\rm th} and the empirical lower bound N_\min^{\rm emp}, N_\min^{\rm th} / N_\min^{\rm emp}, under both estimators. In the following table, values near zero mean the gap did not close with SMILE, and asterisks in the table indicate bootstrap significance at $p = 0.05$.
  • As a result, we found almost no change in that ratio. These results suggest the gap stems mainly from attack inefficiency, not MI under-estimation. We will add the table and a brief discussion to the appendix.

• Clarification on experimental results
  • Thank you for catching the confusion in Figure 1. The horizontal axis should have been $\log I(Z; T)$, not “inverse leaked bits.”
  • We will (1) relabel the axis, (2) plot the theoretical line with the correct slope -1, and (3) horizontally flip the data so higher leakage (Tok + TP + logit) lies to the right and lower, exactly matching intuition.
  • These fixes are purely cosmetic; the data, statistics, and conclusions remain unchanged. In the correct figure, the “Tok” points move to the upper left and the “Tok + TP + logit” points to the lower right, fully matching the intuition that exposing more information lowers the required number of queries. This resolves your concerns.

[1]: Understanding the Limitations of Variational Mutual Information Estimators, Song et al 2020

• Certain aspects of the theoretical setting are unclear: as highlighted in the questions below, at first glance, it seems that requiring that pairs be i.i.d. might restrict the class of attacks under consideration, excluding attacks that alter subsequent queries depending on prior outputs. Also, it is not clear to what extent trying to recover an attack success indicator corresponds to model jailbreaking, as the former task relates to verifying attack success, while the latter task consists of producing an attack success, which a priori can be considered to be harder.
  • Thank you for highlighting this issue. Firstly, the i.i.d. assumption was introduced only to streamline the original proof; it is not required for the theory itself. We have already verified that the theorem still holds without assuming i.i.d., as we prove below. Consequently, our theory also covers fully adaptive attack settings and multi-turn conversation settings.
  • In the camera-ready version, we will replace the current statement under the i.i.d. assumption and proof with the independence-free version in Section 2.
  • Second, regarding the distinction between verification (detecting that a prompt has already succeeded) and generation (finding such a prompt), the two are information-theoretically equivalent. Consequently, the query lower bound $N_{\min}(\varepsilon)$ that we derive for verification applies unchanged to generation. This means an adversary that cannot verify success within $N_{\min}(\varepsilon)$ queries also cannot generate a successful prompt in fewer than $N_{\min}(\varepsilon)$ queries.

Theorem 1 (Information‑theoretic lower bound for adaptive attacks without the i.i.d. assumption)

Let

• $T\in\mathcal{T}$ be the target property with an arbitrary prior (finite, countable, or continuous);
• an attacker issue $N$ sequential queries, where the $n$‑th input $X_n$ is any measurable function of the past outputs $Z_{1:n-1}$ (i.e., the attack is adaptive);
• the model reply is $Z_n = g\bigl(X_n,T,U_n\bigr),$ where $U_n$ is internal randomness independent of $T$ and of all previous $(X_i,Z_i)_{i<n}$.

Define the per‑query leakage

For any tolerated error probability $0<\varepsilon<1$, every adaptive strategy must issue at least

Proof

1. Fano’s inequality.

Let the attacker’s estimate be $\widehat{T}=f(Z_{1:N})$ with error probability $P_{\mathrm{err}}:=\Pr[\widehat{T}\neq T].$ The $K$‑ary (or differential) Fano inequality gives $H_{\mathcal{T}}\bigl(P_{\mathrm{err}}\bigr) \ge H(T)-I(Z_{1:N};T).$

2. Chain rule without independence.

Always $I(Z_{1:N};T)=\sum_{n=1}^{N} I \bigl(Z_n; T \mid Z_{1:n-1}\bigr).$ Each term is upper‑bounded by $I_{\max}$ by definition, so $I(Z_{1:N};T) \le N I_{\max}.$

3. Combine the bounds.

For $P_{\mathrm{err}}\le\varepsilon$, entropy satisfies $H_{\mathcal{T}} \bigl(P_{\mathrm{err}}\bigr)<\log_2(1/\varepsilon)$, hence

4. Rearrange.

$N \ge \frac{\log_2(1/\varepsilon)}{I_{\max}},$ establishing the claimed lower bound.

∎

Interpretation.

The i.i.d. assumption in prior work is only used to equalise the mutual‑information terms. Replacing that with a uniform upper bound $I_{\max}$ suffices because the chain rule already accounts for correlations between successive replies. Thus, the result holds for fully adaptive, stateful attacks.

• In theorem 1, is my understanding correct that, since is an indicator of attack success, the attacker aims not to produce a prompt that jailbreaks the model, but rather to determine, for a given query, whether the model is jailbroken on it? If this is the case, then the setting does not reflect an attack trying to steer the model past its guardrails (line 30), but rather only detect whether the model is violating its guardrails (which is a very different and generally easier problem).
  • Thank you for your comment. Our framework covers the generation of a jailbreak prompt, not merely the detection of an attack.
  • We suspect there may be a misunderstanding, so allow us to clarify the role of $T$.
  • For every candidate query $q_i$, there is an unknown latent indicator $T(q_i)∈{0,1}$ that tells whether that query will bypass the guardrails. An attacker therefore proceeds in the following “generate-and-verify” loop:
    1. Generate a candidate query $q_i$
    2. Query the model with $q_i$ and observe the response $Z_i$.
    3. Infer $T_i$ from $Z_i$
    4. Terminate or iterate: If $T_i=1$, the jailbreak succeeds; otherwise, the attacker constructs a new prompt $q_{i+1}$ and returns to Step 1.
• Regarding the queries (prompts) in scope
  • Thank you for the question. Theorem 1 places no constraints on the queries: each $q_i$ can be any finite string, chosen adaptively from past outputs. Consequently, our framework accommodates both repeated prompts and different prompts at each round.
• In the SPRT attack, how does the attacker compute the likelihood ratio, concretely? Does the theoretical analysis assume access to the ground truth conditional distributions ? If so, how would your query complexity bound change if the attacker instead needs to estimate these distributions?
  • Thank you for the insightful question. Our lower-bound analysis adopts a worst-case model in which the attacker is granted oracle access to the true conditional distributions and can therefore compute the likelihood ratio exactly.
  • If, in reality, the attacker must first estimate these distributions, the required number of queries can grow. Consequently, our bound remains valid, and in practice becomes even more protective.

• While the paper emphasizes how more leakage accelerates attacks, it gives little actionable guidance on how to mitigate leakage besides reducing output diversity.
  • Thank you for raising this point. We respectfully point out that adjusting output diversity is only one facet of our proposed method. In Section 3 and again in the experimental result (Figure 1), we introduce and validate a theory that restricts the public signal can reduce the leakage effectively.
• Discussion Without the Independence Assumption
  • Thank you for highlighting this issue. The i.i.d. assumption was introduced only to streamline the original proof; it is not required for the theory itself. We have already verified that the theorem still holds without assuming i.i.d., as we prove below. Consequently, our theory also covers fully adaptive attack settings and multi-turn conversation settings.
  • In the camera-ready version, we will replace the current statement under the i.i.d. assumption and proof with the independence-free version in Section 2.

Theorem 1 (Information‑theoretic lower bound for adaptive attacks without the i.i.d. assumption)

Let

• $T\in\mathcal{T}$ be the target property with an arbitrary prior (finite, countable, or continuous);
• an attacker issue $N$ sequential queries, where the $n$‑th input $X_n$ is any measurable function of the past outputs $Z_{1:n-1}$ (i.e., the attack is adaptive);
• the model reply is $Z_n = g\bigl(X_n,T,U_n\bigr),$ where $U_n$ is internal randomness independent of $T$ and of all previous $(X_i,Z_i)_{i<n}$.

Define the per‑query leakage

For any tolerated error probability $0<\varepsilon<1$, every adaptive strategy must issue at least

Proof

1. Fano’s inequality.

Let the attacker’s estimate be $\widehat{T}=f(Z_{1:N})$ with error probability $P_{\mathrm{err}}:=\Pr[\widehat{T}\neq T].$ The $K$‑ary (or differential) Fano inequality gives $H_{\mathcal{T}}\bigl(P_{\mathrm{err}}\bigr) \ge H(T)-I(Z_{1:N};T).$

2. Chain rule without independence.

Always $I(Z_{1:N};T)=\sum_{n=1}^{N} I \bigl(Z_n; T \mid Z_{1:n-1}\bigr).$ Each term is upper‑bounded by $I_{\max}$ by definition, so $I(Z_{1:N};T) \le N I_{\max}.$

3. Combine the bounds.

For $P_{\mathrm{err}}\le\varepsilon$, entropy satisfies $H_{\mathcal{T}} \bigl(P_{\mathrm{err}}\bigr)<\log_2(1/\varepsilon)$, hence

4. Rearrange.

$N \ge \frac{\log_2(1/\varepsilon)}{I_{\max}},$ establishing the claimed lower bound.

∎

Interpretation.

The i.i.d. assumption in prior work is only used to equalise the mutual‑information terms. Replacing that with a uniform upper bound $I_{\max}$ suffices because the chain rule already accounts for correlations between successive replies. Thus, the result holds for fully adaptive, stateful attacks.

• Regarding the MI estimators

  • Thank you for the observation. Using a stronger encoder or a tighter estimator would indeed bring the estimated value closer to the true mutual information. However, Figure 1 shows that our MINE/NWJ/InfoNCE-based method never exceeds the lower bound of mutual information, so it serves as a valid lower bound.
  • We therefore conclude that the present MI estimators already measure leakage with adequate fidelity for the purposes of this work.

• Regarding the use of the LLM API

  • Thank you for the suggestion. To bridge theory with live systems, we have already included an LLM API, OpenAI GPT-4, in our evaluation. The experimental results in Section 3 provide direct evidence that our theoretical findings hold under practical safety filters and deployment quirks.

• Potential misuse of this framework

  • Thank you for raising this concern. We acknowledge that, in principle, signals with higher leakage could be exploited to create stronger jailbreak attacks. At the same time, the same analysis equips defenders to pinpoint which signals leak the most information and to withhold those signals for users who exhibit potentially malicious behavior.
  • We will clarify this dual-use aspect and outline concrete defensive deployments in the camera-ready version.

• How are signals like logits and chain-of-thought combined? Is there evidence of synergy or redundancy in the leakage they offer?

  • Thank you for your question. In Appendix B, we concatenate the final-layer RoBERTa representations and logits for the output tokens and TP into a single feature vector $Z=[z_{\text{tok}};z_{\text{logit}};z_{\text{TP}}]$ which is then passed to the classifier that estimates mutual information. Figure 1 reports different lower bounds for the four settings (Tok + TP + logit, Tok + logit, Tok + TP, and Tok alone), indicating that logits and TP contribute synergistically to information leakage.

• Beyond lowering temperature or hiding logits, do you recommend any defense techniques (e.g., randomized decoding, response perturbation) based on your findings?

  • Thank you for the suggestion. To raise the attack cost by reducing the mutual information $I$, the most straightforward way is to deliberately lower the determinacy of what the attacker can observe; thus, injecting randomness into every stage, such as model outputs, guardrail processing, and the choice of models in an ensemble, is effective.

• Could your framework also inform differential privacy-style bounds on allowable leakage for LLMs trained with user-sensitive data?

  • We didn’t quite understand the purpose of this question, so could you please explain it in a bit more detail?

• Do your bounds generalize to multi-turn conversations where leakage may accumulate or be reinforced across rounds?

  • As noted in another response, we have proved that our theory holds even without assuming i.i.d. between attacks, so it should remain valid in multi-turn settings. We state in the conclusion that extending the experiments to this is future work.

• Could your mutual information formulation be extended to LLMs with vision (e.g., GPT-4V)? What are the additional challenges?

  • Because $Z$ is defined as any attacker-observable signal, such as output tokens, chain-of-thought, image embeddings. Therefore, our theorems extend to multimodal LLMs by simply replacing it with the concatenated vector $Z=[z_{\text{text}};z_{\text{image}}]$. The only additional requirement is to estimate $I(Z;T)$ with a multimodal MI estimator. We will note this extension as future work in the camera-ready version.