Logicbreaks: A Framework for Understanding Subversion of Rule-based Inference

## Abstract

Abstract We study how to subvert large language models (LLMs) from following prompt-specified rules.
We model rule-following as inference in propositional Horn logic, a mathematical system in which rules have the form “if P 𝑃 P italic_P and Q 𝑄 Q italic_Q , then R 𝑅 R italic_R ” for some propositions P 𝑃 P italic_P , Q 𝑄 Q italic_Q , and R 𝑅 R italic_R .
We prove that although LLMs can faithfully follow such rules, maliciously crafted prompts can mislead even idealized, theoretically constructed models.
Empirically, we find that the reasoning behavior of LLMs aligns with that of our theoretical constructions, and popular attack algorithms find adversarial prompts with characteristics predicted by our theory.
Our logic-based framework provides a novel perspective for mechanistically understanding the behavior of LLMs in rule-based settings such as jailbreak attacks.

## 1 Introduction

Developers commonly use system prompts, task descriptions, and other instructions to guide large language models (LLMs) to produce safe content and ensure its factual accuracy [, ].
However, in practice, LLMs often fail to comply with these rules for unclear reasons.
When LLMs violate predefined rules, they can produce harmful content for downstream users and processes [, ].
For example, a customer services chatbot that deviates from its instructed protocols can create a poor user experience, erode customer trust, and trigger legal actions [].

To understand why LLMs may be unreliable at following the rules, we study how to intentionally subvert them from obeying prompt-specified instructions.
Our motivation is to better understand the underlying dynamics of jailbreak attacks [, ] that seek to bypass various safeguards on LLM behavior [, ].
Although many works conceptualize jailbreaks as rule subversions [, ], the current literature lacks a solid theoretical understanding of when and how such attacks succeed.
To address this gap, we study the principles of attacks on rule-based inference for prompt-specified rules.

We first present a logic-based framework for studying rule-based inference, using which we characterize the different ways in which a model may fail to follow the rules.
We then derive theoretical attacks that succeed against not only our analytical setup but also reasoners trained from data.
Moreover, we establish a connection from theory to practice by showing that popular jailbreaks against LLMs exhibit similar characteristics as our theory-based ones.
Fig. 1 shows an overview of our approach, and we summarize our contributions as follows.

Logic-based Framework for Analyzing Rule Subversion (Section 2).
We model rule-following as inference in propositional Horn logic [],
a mathematical system in which rules take the form “If $P$ and $Q$, then $R$” for some propositions $P$, $Q$, and $R$.
This is a common approach for rule-based tasks [, ],
and serves as a simple yet expressive foundation that lets us formally define three properties — monotonicity, maximality, and soundness — that exactly characterize rule-following.
Our logic-based framework establishes a method to detect and describe when and how an LLM disobeys the prompt-specified rules.

Figure: Figure 1: The language model is supposed to deny user queries about building bombs. We consider three models: a theoretical model that reasons over a custom binary-valued encoding of prompts, a learned model trained on these binary-valued prompts, and a standard LLM. (Left) Suffix-based jailbreaks devised against the theoretical constructions transfer to learned reasoners. (Right) Popular jailbreaks use tokens and induce attention patterns predicted by our simple theoretical setup.
Refer to caption: extracted/5894019/images/results_overview.png

Theory-based Attacks Transfer to Learned Models (Section 3).
We first analyze a theoretical model to study how the reasoning of transformer-based language models may be subverted.
Interestingly, many of the attacks crafted in our theoretical setting also transfer to learned models trained from data.
Moreover, our empirical experiments show that LLMs exhibit reasoning behaviors consistent with our theoretical models, suggesting that our constructions offer a realistic framework for studying how LLMs reason.

Popular Jailbreak Attacks Mirror Theory-based Attacks (Section 4).
We find that popular jailbreak attacks against LLMs mirror those of our theory-based strategies.
In particular, we find that the token values of successful jailbreaks and their induced attention patterns align with those predicted by our theory.
Our work suggests that investigations on smaller theoretical models and well-defined setups can yield mechanistic insights into how jailbreaks work on LLMs.

## 2 Framework for Rule-based Inference

Inference in Propositional Horn Logic.
We model rule-following as inference in propositional Horn logic, which concerns deriving new knowledge using inference rules of an “if-then” form.
Horn logic is commonly used to model rule-based tasks, and the propositional case provides a simple setting that effectively captures many rule-following behaviors.
This logic is particularly well-suited to analyzing dependencies.
As an illustrative example, consider a common task from the Minecraft video game [], in which the player crafts new items according to a recipe list.
Given such a list and some starting items, one may ask an LLM what is craftable:

Here are some crafting recipes: If I have Sheep, then I can create Wool.
If I have Wool, then I can create String.
If I have Log, then I can create Stick.
If I have String and Stick, then I can create Fishing Rod.
Here are some items I have:
I have Sheep and Log as starting items.
Based on these items and recipes, what items can I create?

where Sheep, Wool, and String, etc., are items in Minecraft.
We may translate the prompt-specified instructions above into the following set of inference rules $\Gamma$ and known facts $\Phi$:

$$ $\Gamma=\{A\to B,B\to C,D\to E,C\land E\to F\},\quad\Phi=\{A,D\},$ (1) $$

where $\land$ denotes logical conjunctions (AND).
For example, the proposition $A$ stands for “I have Sheep”, which we treat as equivalent to “I can create Sheep”, while the rule $C\land E\to F$ reads “If I have String and Stick, then I can create Fishing Rod”.
The inference task is to find all the derivable propositions.
A well-known algorithm for this is forward chaining, which iteratively applies $\Gamma$ starting from $\Phi$ until no new knowledge is derivable.
We illustrate a 3-step iteration of this:

$$ $\{A,D\}\xrightarrow{\mathsf{Apply}[\Gamma]}\{A,B,D,E\}\xrightarrow{\mathsf{ Apply}[\Gamma]}\{A,B,C,D,E\}\xrightarrow{\mathsf{Apply}[\Gamma]}\{A,B,C,D,E,F\},$ (2) $$

where $\mathsf{Apply}[\Gamma]$ is a set-to-set function that implements a one-step application of $\Gamma$.
Because no new knowledge can be derived from the proof state $\{A,B,C,D,E,F\}$, we may stop.
When $\Gamma$ is finite, as in this paper, we write $\mathsf{Apply}^{\star}[\Gamma]$ to mean the repeated application of $\mathsf{Apply}[\Gamma]$ until no new knowledge is derivable.
We then state the problem of propositional inference as follows.

###### Problem 2.1 (Inference) .

Given rules $\Gamma$ and facts $\Phi$, find the set of propositions $\mathsf{Apply}^{\star}[\Gamma](\Phi)$.

Next, we present a binarization of the inference task to better align with our later exposition of transformer-based language models.
From the above example, denote the subsets of $\{A,B,C,D,E,F\}$ using binary vectors in $\{0,1\}^{6}$.
We write $\Phi=(100100)$ to mean $\{A,D\}$ and use pairs to represent rules in $\Gamma$, e.g., write $(001010,000001)$ to mean $C\land E\to F$.
This lets us define $\mathsf{Apply}[\Gamma]:\{0,1\}^{6}\to\{0,1\}^{6}$ as follows:

$$ $\mathsf{Apply}[\Gamma](s)=s\lor\bigvee\{\beta:(\alpha,\beta)\in\Gamma,\alpha \subseteq s\},$ (3) $$

where $s\in\{0,1\}^{6}$ is any set of propositions, $\lor$ denotes the element-wise disjunction (OR) of binary vectors, and we extend the subset relation $\subseteq$ in the standard manner.
Because binary-valued and set-based notations are equivalent and both useful, we will flexibly use whichever is convenient.
Note that 2.1 is also known as propositional entailment, which is equivalent to the more commonly studied problem of Horn-SAT.
We expand on this in Section A.1, wherein the main detail is in how the “bottom” proposition is encoded.

Figure: Figure 2: Using example (2): attacks against the three inference properties (Definition 2.2) given a model $\mathcal{R}$ and input $X_{0}=\mathsf{Encode}(\Gamma,\Phi)$ for rules $\Gamma=\{A\to B,A\to C,D\to E,C\land E\to F\}$ and facts $\Phi=\{A,D\}$. The monotonicity attack causes $A$ to be forgotten. The maximality attack causes the rule $D\to E$ to be suppressed. The soundness attack induces an arbitrary sequence.

Subversion of Rule-following.
We use models that autoregressively predict the next proof state to solve the inference task of 2.1.
We say that such a model $\mathcal{R}$ behaves correctly if its sequence of predicted proof states match what is generated by forward chaining with $\mathsf{Apply}[\Gamma]$ as in (2).
Therefore, to subvert inference is to have $\mathcal{R}$ generate a sequence that deviates from that of $\mathsf{Apply}[\Gamma]$.
However, different sequences may violate rule-following differently, and this motivates us to formally characterize the definition of rule-following via the following three properties.

###### Definition 2.2 (Monotone, Maximal, and Sound (MMS)) .

For any rules $\Gamma$, known facts $\Phi$, and proof states $s_{0},s_{1},\ldots,s_{T}\in\{0,1\}^{n}$ where $\Phi=s_{0}$, we say that the sequence $s_{0},s_{1},\ldots,s_{T}$ is:

- •
Monotone iff $s_{t}\subseteq s_{t+1}$ for all steps $t$.
- •
Maximal iff $\alpha\subseteq s_{t}$ implies $\beta\subseteq s_{t+1}$ for all rules $(\alpha,\beta)\in\Gamma$ and steps $t$.
- •
Sound iff for all steps $t$ and coordinate $i\in\{1,\ldots,n\}$, having $(s_{t+1})_{i}=1$ implies that: $(s_{t})_{i}=1$ or there exists $(\alpha,\beta)\in\Gamma$ with $\alpha\subseteq s_{t}$ and $\beta_{i}=1$.

Monotonicity ensures that the set of known facts does not shrink; maximality ensures that every applicable rule is applied; soundness ensures that a proposition is derivable only when it exists in the previous proof state or is in the consequent of an applicable rule.
These properties establish concrete criteria for what to subvert, examples of which we show in Fig. 2.
Moreover, we prove in Section B.1 that the MMS properties uniquely characterize $\mathsf{Apply}[\Gamma]$, which suggests that our proposed attacks of Section 3 have good coverage on the different modes of subversion.

###### Theorem 2.3 .

The sequence of proof states $s_{0},s_{1},\ldots,s_{T}$ is MMS with respect to the rules $\Gamma$ and known facts $\Phi$ iff they are generated by $T$ steps of $\mathsf{Apply}[\Gamma]$ given $(\Gamma,\Phi)$.

We remark that maximality implies the completeness of our forward chaining implementation.
Maximality is primarily used to resolve potential non-determinism in rule-application order and is special to the propositional case; it is not readily extendable to the first-order case because each rule application may generate infinitely many new facts.

###### Problem 2.1 (Inference) .

###### Definition 2.2 (Monotone, Maximal, and Sound (MMS)) .

###### Theorem 2.3 .

## 3 Theoretical Principles of Rule Subversion in Transformers

Having established a framework for studying rule subversions in Section 2, we now seek to understand how it applies to transformers.
In Section 3.1, we give a high-level overview of our theoretical construction.
Then, we establish in Section 3.2 rule subversions against our theoretical constructions and show that they transfer to reasoners trained from data.

### 3.1 Transformers Can Encode Rule-based Inference

We now present our mathematical formulation of a language model reasoner $\mathcal{R}$.
Because our encoding result states that a transformer with only one layer and one self-attention head suffices to represent one step of reasoning, i.e., $\mathsf{Apply}[\Gamma]$, we define our reasoner model $\mathcal{R}$ as follows:

$$ $\displaystyle\begin{split}\mathcal{R}(X)&=\left((\mathsf{Id}+\mathsf{Ffwd}) \circ(\mathsf{Id}+\mathsf{Attn}\right)\big{)}(X),\\ \mathsf{Attn}(X)&=\mathsf{CausalSoftmax}\left((XQ+\mathbf{1}_{N}q^{\top})K^{ \top}X^{\top}\right)XV,\\ \mathsf{Ffwd}(z)&=W_{2}\mathsf{ReLU}(W_{1}z+b),\end{split}\quad X=\begin{ bmatrix}\begin{array}[]{@{\protect\rotatebox[origin=c]{90}{$\vert$}\;}c@{\; \protect\rotatebox[origin=c]{90}{$\vert$}}}origin={c}]{90.0}{$|$}\; \lx@intercol\hfil x_{1}^{\top}\hfil\;\rotatebox[origin={c}]{90.0}{$|\\ \lx@intercol\hfil\vdots\hfil\\ origin={c}]{90.0}{$|$}\;\lx@intercol\hfil x_{N}^{\top}\hfil\;\rotatebox[origin ={c}]{90.0}{$|\end{array}\end{bmatrix}\in\mathbb{R}^{N\times d}}}$ (4) $$

Here, $\mathcal{R}:\mathbb{R}^{N\times d}\to\mathbb{R}^{N\times d}$ is a transformer with embedding dimension $d$ over sequence length $N$.
We use residual connections, denoted by $\mathsf{Id}$, for both the self-attention and feedforward blocks.
The self-attention block $\mathsf{Attn}:\mathbb{R}^{N\times d}\to\mathbb{R}^{N\times d}$ has weights $Q,K^{\top},V\in\mathbb{R}^{d\times d}$ and bias $q\in\mathbb{R}^{d}$, with $\mathsf{CausalSoftmax}:\mathbb{R}^{N}\to\mathbb{R}^{N}$ applied to each row.
The one-depth feedforward block $\mathsf{Ffwd}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ has weights $W_{1}^{\top},W_{2}\in\mathbb{R}^{d\times d_{\mathsf{ffwd}}}$, bias $b\in\mathbb{R}^{d_{\mathsf{ffwd}}}$, and width $d_{\mathsf{ffwd}}$.
During evaluation, the same $\mathsf{Id}+\mathsf{Ffwd}$ block is applied in parallel to each row of $(\mathsf{Id}+\mathsf{Attn})(X)\in\mathbb{R}^{N\times d}$.

Propositional Inference via Autoregressive Iterations.
We now consider how to implement inference with the reasoner $\mathcal{R}$.
Given a set of rules
$\Gamma=\{(\alpha_{1},\beta_{1}),\ldots,(\alpha_{r},\beta_{r})\}\subseteq\{0,1
\}^{2n}$ and known facts $\Phi\in\{0,1\}^{n}$, we begin from an initial encoding $X_{0}=\mathsf{Encode}(\Gamma,\Phi)\in\mathbb{R}^{(r+1)\times d}$.
Then, we use $\mathcal{R}$ to autogregressively generate a sequence of sequences $X_{0},X_{1},\ldots,X_{T}$ that respectively decode into the proof states $s_{0},s_{1},\ldots,s_{T}\in\{0,1\}^{n}$ using a classification head $\mathsf{ClsHead}$.
In particular, this relation is given by $s_{t+1}=\mathsf{ClsHead}(\mathcal{R}(X_{t}))$.
Our main strategy is to have the self-attention block of $\mathcal{R}$ approximate $\mathsf{Apply}[\Gamma]$ rules in the following manner:

$$ $\displaystyle s_{t}\xrightarrow{\mathsf{Id}+\mathsf{Attn}}\tilde{s}_{t+1}, \quad\text{where}\enskip\tilde{s}_{t+1}=s_{t}+\sum_{(\alpha,\beta):\alpha \subseteq s_{t}}\beta+\varepsilon\approx\underbrace{s_{t}\lor\bigvee\{\beta:( \alpha,\beta)\in\Gamma,\alpha\subseteq s_{t}\}}_{\mathsf{Apply}[\Gamma](s_{t})},$ (5) $$

where $\varepsilon$ is a residual term from softmax attention.
That is, we approximate binary-valued disjunctions with summations and recover a binary-valued $s_{t+1}$ by thresholding each coordinate of $\tilde{s}_{t+1}\in\mathbb{R}^{n}$ using the feedforward block.
We apply this idea to derive a theoretical construction that can implement propositional inference using only one layer and one self-attention head.

###### Theorem 3.1 (Encoding, Informal) .

There exists a reasoner $\mathcal{R}$ as in (4) with $d=2n$ and $d_{\mathsf{ffwd}}=4d$
such that, for any rules $\Gamma$ and facts $\Phi$:
the proof state sequence $s_{0},s_{1},\ldots,s_{T}$ generated by $\mathcal{R}$ given $X_{0}=\mathsf{Encode}(\Gamma,\Phi)$ matches what is produced by $\mathsf{Apply}[\Gamma]$, assuming that $\lvert\Gamma\rvert+T$ is not too large.

We give a detailed construction in Section B.2, wherein a limitation is that $\mathcal{R}$ is only guaranteed to be correct for inputs under a maximum length $N_{\mathsf{max}}$.
This is due to the parameter scalings needed to handle softmax attention, and we may readjust $Q,K,V$ to account for any value of $N_{\mathsf{max}}$.

Binary-valued Encodings Approximate LLM Reasoning.
We show in Section 4 that binary-valued representations of the proof state can be accurately extracted from LLM embeddings.
This shows that our theoretical setup is not an unrealistic setting for studying LLM reasoning, in particular, propositional inference.
Moreover, we show in Section C.2 that transformers subjected to our theoretical dimensions of $d=2n$ can learn to reason with high accuracy.
In fact, models with $d<2n$ often struggle to learn, which suggests the tightness of our Theorem 3.1 construction.

###### Theorem 3.1 (Encoding, Informal) .

### 3.2 Attacking Rule-based Inference in Transformers

We next investigate how to subvert the rule-following of our theoretical models, wherein the objective is to find an adversarial suffix $\Delta$ that causes a violation of the MMS property when appended to some input encoding $X_{0}=\mathsf{Encode}(\Gamma,\Phi)$.
This suffix-based approach is similar to jailbreak formulations studied in the literature [, ], which we state as follows:

###### Problem 3.2 (Inference Subversion) .

Consider any rules $\Gamma$, facts $\Phi$, reasoner $\mathcal{R}$, and budget $p>0$.
Let $X_{0}=\mathsf{Encode}(\Gamma,\Phi)$, and
find $\Delta\in\mathbb{R}^{p\times d}$ such that:
the proof state sequence $\hat{s}_{0},\hat{s}_{1},\ldots,\hat{s}_{T}$ generated by $\mathcal{R}$ given $\widehat{X}_{0}=[X_{0};\Delta]$ is not MMS with respect to $\Gamma$ and $\Phi$, but where $\hat{s}_{0}=\Phi$.

Our key strategy for crafting attacks against our theoretical construction is to use the fact that $\mathcal{R}$ uses a summation to approximate binary disjunctions, as in (5).
In particular, if one can construct an adversarial suffix $\Delta$ with large negative values in the appropriate coordinates, it is straightforward to craft attacks that induce violations of MMS.

###### Theorem 3.3 (Theory-based Attacks, Informal) .

Let $\mathcal{R}$ be as in Theorem 3.1 and consider any $X_{0}=\mathsf{Encode}(\Gamma,\Phi)$ where the rules $\Gamma$ and $\Phi$ satisfy some technical conditions (e.g., $\Phi\neq\emptyset$ for monotonicity).
Then the following adversarial suffixes to $X_{0}$ induce a two-state sequence $\hat{s}_{0},\hat{s}_{1}$ that respectively violate monotonicity, maximality, and soundness given $\Gamma$ and $\Phi$:

$$ $\displaystyle\Delta_{\mathsf{MonotAtk}}=\begin{bmatrix}\mathbf{0}_{n}^{\top}&- \kappa\delta^{\top}\\ \mathbf{0}_{n}^{\top}&\Phi^{\top}\end{bmatrix},\quad\Delta_{\mathsf{MaximAtk}} =\begin{bmatrix}\zeta^{\top}&\mathbf{0}_{n}^{\top}\\ \mathbf{0}_{n}^{\top}&\Phi^{\top}\end{bmatrix},\quad\Delta_{\mathsf{SoundAtk}} =\begin{bmatrix}\mathbf{0}_{n}^{\top}&\kappa(2s^{\star}-\mathbf{1}_{n})^{\top} \\ \mathbf{0}_{n}^{\top}&\Phi^{\top}\end{bmatrix},$ $$

where $\kappa>0$ is sufficiently large and:
(monotonicity) $\delta$ is any non-empty subset of $\Phi$;
(maximality)
let $\zeta=\alpha-\kappa(\mathbf{1}_{n}-\alpha)$, where $(\alpha,\beta)\in\Gamma$ is a rule such that $\alpha\subseteq\Phi$ and where $\beta$ contains propositions not known by $\Phi$;
(soundness) for any $s^{\star}\neq\mathsf{Apply}[\Gamma](\Phi)$.

Intuitively, the suffix $\Delta_{\mathsf{MonotAtk}}$ attempts to delete known facts from the successive proof state, and we also refer to this as fact amnesia.
The suffix $\Delta_{\mathsf{MaximAtk}}$ has a “rule” with antecedent $\zeta$ intended to divert attention away from the rule $(\alpha,\beta)$, and it is helpful to think of this as rule suppression.
The suffix $\Delta_{\mathsf{SoundAtk}}$ injects a token $\kappa(2s^{\star}-\mathbf{1}_{n})$ whose coordinates have values $\pm\kappa$, depending on the sign of the adversarial target $s^{\star}$, and we refer to it as state coercion.

Although our theory deals with binary vectors, we use negative values in our theoretical attacks.
We do this because our attacks fundamentally operate in the embedding space: when language models reason, they may not use all parts of their embedding space, so it is not implausible to assume that there exist tokens whose embedded values play a similar role to our use of negative values.

Figure: Figure 3: Theory-based fact amnesia (monotonicity) and rule suppression (maximality) attain strong Attack Success Rates (ASR) against learned reasoners, where ASR is the rate at which the $\Delta$-induced trajectory $\hat{s}_{1},\hat{s}_{2},\hat{s}_{3}$ equals the expected $s_{1}^{\star},s_{2}^{\star},s_{3}^{\star}$. We use 16384 samples for fact amnesia and rule suppression. We found that our theory-based state coercion (soundness) fails but that using repetitions of a common suffix $\Delta$ on different prefixes $X_{0}$ causes $\mathcal{R}$ to generate similar outputs as measured by the variance. We sampled 1024 different $\Delta$ and 512 different $X_{0}$.
Refer to caption: extracted/5894019/images/exp2_fact_amnesia_acc.png

**Table 1: Learned attacks attain high ASR against all three properties and mirror theory-based attacks. We used reasoners with dimension $d=2n$. (Fact Amnesia) The average magnitude of the targeted entries ($v_{\mathsf{tgt}}$) of $\Delta$ is larger than the non-targeted entries ($v_{\mathsf{other}}$). (Rule Suppression) The suppressed rule receives less attention in the attacked case. (State Coercion) The average entry-wise magnitude of $\Delta$ is larger than that of the prefix $X_{0}$.**
|  | Fact Amnesia | Rule Suppression | State Coercion |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  |  | $\Delta$ Values |  | Attn. Weights |  | Size |  |  |  |
| $n$ | ASR | $v_{\mathsf{tgt}}$ | $v_{\mathsf{other}}$ | ASR | Atk ✓ | Atk ✗ | ASR | $\Delta$ | $X_{0}$ |
| $64$ | $1.00$ | $0.01\pm 0.001$ | $0.11\pm 0.005$ | $1.0$ | $0.16\pm 0.02$ | $0.29\pm 0.03$ | $0.76$ | $3.89\pm 0.32$ | $0.05\pm 0.003$ |
| $48$ | $1.00$ | $0.02\pm 0.002$ | $0.12\pm 0.007$ | $1.0$ | $0.18\pm 0.02$ | $0.28\pm 0.03$ | $0.74$ | $1.45\pm 0.17$ | $0.06\pm 0.004$ |
| $32$ | $1.00$ | $0.02\pm 0.001$ | $0.08\pm 0.007$ | $1.0$ | $0.17\pm 0.02$ | $0.27\pm 0.03$ | $0.77$ | $1.73\pm 0.22$ | $0.09\pm 0.006$ |
| $16$ | $0.99$ | $0.04\pm 0.006$ | $0.13\pm 0.015$ | $1.0$ | $0.13\pm 0.02$ | $0.25\pm 0.03$ | $0.57$ | $2.01\pm 0.52$ | $0.18\pm 0.011$ |

Theory-based Attacks Transfer to Learned Reasoners.
We found that most theory-based attacks transfer to learned reasoners with small changes.
In particular, we found that repeating the essential parts of the attack, e.g., $[(\mathbf{0}_{n},-\kappa\delta)^{\top};\ldots;(\mathbf{0}_{n},-\kappa\delta)^{
\top}]$ for monotonicity, helps the attack succeed against GPT-2 based reasoners.
Such repetitions would also work against our theoretical models.
We show the results in Fig. 3 over a horizon of $T=3$ steps, wherein we define the Attack Success Rate (ASR) as the rate at which the $\Delta$-induced trajectory $\hat{s}_{1},\hat{s}_{2},\hat{s}_{3}$ matches that of the expected trajectory $s_{1}^{\star},s_{2}^{\star},s_{3}^{\star}$, such as in Fig. 2.
Notably, the soundness attack (state coercion) does not succeed, even with repetitions.
However, repeating the suffix causes different prefixes $X_{0}$ to induce the similar $\hat{s}_{1}$ — which we measure by the variance.
We give additional details in Section C.3.

Learned Attacks Exhibit Characteristics of Theoretical Attacks.
Furthermore, we investigated whether standard adversarial attacks discover suffixes similar to our theory-based ones.
In particular, given some $X_{0}=\mathsf{Encode}(\Gamma,\Phi)$ and some arbitrary sequence of target states $s_{0}^{\star},s_{1}^{\star},\ldots,s_{T}^{\star}$ that is not MMS (but where $\Phi=s_{0}^{\star}$) — can one find
an adversarial suffix $\Delta$ that behaves similar to the ones in theory?
We formulated this as the following learning problem:

$$ $\displaystyle\underset{\Delta\in\mathbb{R}^{p\times d}}{\text{minimize}} \enskip\mathcal{L}((\hat{s}_{0},\ldots,\hat{s}_{T}),(s_{0}^{\star},\ldots,s_{T }^{\star})),\quad\text{with}\enskip\hat{s}_{0},\ldots,\hat{s}_{T}\enskip\text{ from $\mathcal{R}$ given $\widehat{X}_{0}=[X_{0};\Delta]$},$ (6) $$

where $\mathcal{L}$ is the binary cross-entropy loss.
For each of the three MMS properties, we generate different adversarial target sequences $s_{0}^{\star},s_{1}^{\star},\ldots,s_{T}^{\star}$ that evidence its violation and optimized for an adversarial suffix $\Delta$.
We found that a budget of $p=2$ suffices to induce failures over a horizon of $T=3$ steps.
We present our results in Table 1, with additional discussion in Section C.4.

###### Problem 3.2 (Inference Subversion) .

###### Theorem 3.3 (Theory-based Attacks, Informal) .

## 4 Experiments with Large Language Models

We next study how to subvert LLMs and analyze whether such attacks align with our theoretical predictions.
We consider two LLMs, GPT-2 [] and Llama-2-7B-chat [], which are considerably larger than our theoretical setups and also operate on discrete tokens.
We adapted the popular Greedy Coordinate Gradients (GCG) [] jailbreak algorithm to generate fact amnesia, rule suppression, and state coercion attacks.
We found that the adversarial suffixes found by GCG and their induced attention patterns align with our theoretical predictions.
We present a summary of results here and defer comprehensive details to Appendix D.

Figure: Figure 4: A GCG-generated adversarial suffix suppresses the rule “If I have Wool, then I can create String”, causing the LLM to omit String and Fishing Rod from its generation. This is the expected behavior of rule suppression: the targeted rule and its dependents are absent from the output.
Refer to caption: extracted/5894019/images/mc_prompt.png

Dataset, Model, and Attack Setups.
To study inference subversion in natural language, we consider the task of sabotaging item-crafting in Minecraft [].
Given a prompt about crafting items, the objective is to find an adversarial suffix that causes the LLM to answer incorrectly.
Fig. 4 shows such an example, where an adversarial suffix suppresses the LLM from generating String and Fishing Rod in its output.
To attack LLM-based reasoners, we first construct three datasets of such prompts that require at most $T=1,3,5$ steps each to craft all the items (the Fig. 4 example requires $T=3$ steps).
Next, we fine-tune a GPT-2 [] model for each dataset, with all three models attaining $85\%+$ accuracy.
Then, for each attack and each model, we use GCG to search for an adversarial suffix that induces the expected behavior of the attack.
We give additional details for datasets and fine-tuning in Section D.1, describe the attack setups and expected behaviors in Section D.2, and define the evaluation metrics in Section D.3.
Due to limits in computation, we do not fine-tune Llama-2-7B-Chat, nor do we attack it with GCG, and instead study its behavior with a hand-crafted dataset, which we expand upon in Section D.4.

Result 1: Standard Probing Gives Evidence for Binary-valued Encodings.
We found that linear classifier probes [] attached to the last token embeddings accurately predict the final proof state at the end of chain-of-thought reasoning.
This is evidence that the LLM embeddings contain enough information to easily reconstruct the binary-valued proof states in our theoretical setup.
To test the probe accuracy for different numbers of propositions $n$ (i.e., craftable items), we created random restrictions of the Minecraft dataset for $n=32,64,128,256$.
Then, we attached a different probe mapping $\mathbb{R}^{d}\to\mathbb{R}^{n}$ to each of the $L=12$ layers of GPT-2, where $d=768$ and the sign of each output coordinate whether the corresponding proposition should hold.
There are a total of $4\,(\text{num datasets})\times 12\,(\text{num layers})=48$ different probes.
We used logistic regression to fit the linear probes on a sample of $1024$ prompts for the $n=32$ setting and $2048$ prompts for the $n=64,128,256$ settings.
We report the accuracy in Fig. 5 (left) and F1 scores in Fig. 5 (middle) over a total of $256$ validation samples for each $n$.
A probe’s prediction is correct (counted towards accuracy) only when it correctly predicts all $n$ propositions, and for F1 scores, we used the total number of true positives, true negatives, false positives, and false negatives of all the predictions.
We also found that an adversarial suffix makes the probes recover the attacker’s intended target state more frequently Fig. 5 (right), and this is consistent with our theoretical predictions.

Figure: Figure 5: Linear probing on LLMs justifies our binary-valued theoretical analysis. Probes at deeper layers have better accuracies (Left) and F1 scores (Middle), and these values are lower when there are more propositions to recover. (Right) When an adversarial suffix is present, the probes have trouble recovering the non-attacked state, i.e., the original state; instead, the probes tend to recover what the attacker is attempting to inject, i.e., the adversarial state.
Refer to caption: extracted/5894019/images/minecraft_probe_results_final_new_val_state_mean.png

**Table 2: GCG jailbreaks succeed against fine-tuned GPT-2 models over 100 samples of each attack. Extending the example of Fig. 4, the following output would count in the SSR, but not in the ASR. ”I have Log, and so I can create Stick. I have Brick, and so I can create Stone Stairs. I have Brick, and so I can create Sheep. I cannot create any other items.”**
|  | Fact Amnesia | Rule Suppression | State Coercion |  |  |
| --- | --- | --- | --- | --- | --- |
| $\mathcal{R}$ | ASR | SSR | ASR | SSR | ASR |
| $T=1$ | — | — | $0.29\pm 0.04$ | $0.46\pm 0.04$ | $1.0$ |
| $T=3$ | $0.14\pm 0.04$ | $0.37\pm 0.04$ | $0.23\pm 0.04$ | $0.33\pm 0.04$ | $1.0$ |
| $T=5$ | $0.21\pm 0.04$ | $0.45\pm 0.05$ | $0.11\pm 0.03$ | $0.21\pm 0.04$ | $1.0$ |

Result 2: Language Models are Susceptible to Inference Subversions.
For each attack (fact amnesia, rule suppression, state coercion) and model ($T=1,3,5)$, we used GCG to find adversarial suffixes that induce the expected behavior.
An attack is successful (counted in the ASR) if the model output matches the expected behavior, such as in Fig. 4.
For fact amnesia and rule suppression, we also define a laxer metric called the Suppression Success Rate (SSR) that only checks for the omission of specific steps.
We show results in Table 2 and give further details in Section D.3.
We remark that while rule suppression corresponds with maximality, the condition checked here is incompleteness, i.e., that some facts failed to be derived.
We do this because incompleteness implies non-maximality and is a simpler condition to check in the context of iterative LLM generation.

**Table 3: Salient tokens from the target commonly appear in the suffix found by GCG, as measured by the overlap. On average, there is a non-trivial overlap of the salient tokens in the target and the adversarial suffix. Substituting the overlapping salient tokens with “and” reduces the ASR.**
|  | Fact Amnesia | State Coercion |  |  |
| --- | --- | --- | --- | --- |
| $\mathcal{R}$ | Overlap | Substitution ASR | Overlap | Substitution ASR |
| $T=1$ | — | — | $0.56\pm 0.25$ | $0.02$ |
| $T=3$ | $0.67\pm 0.37$ | $0.25$ | $0.53\pm 0.28$ | $0.10$ |
| $T=5$ | $0.66\pm 0.35$ | $0.22$ | $0.57\pm 0.21$ | $0.05$ |

Result 3: Theory-predicted Tokens Appear in Automated Jailbreaks.
Our theory-based fact amnesia and state coercion use adversarial suffixes with large magnitudes in specific coordinates.
Such a choice of coordinates increases or decreases the values of some target proposition that is to be present or absent in the successive proof state.
Intuitively, a large positive value in our theory-based suffix is analogous to using its associated tokens in a text-based suffix.
Interestingly, we observed this phenomenon for GCG-generated jailbreaks: the targeted propositions frequently appear in the adversarial suffix.
We measure this as the overlap, defined as the fraction of salient tokens from the target also present in the GCG-found suffix.
Moreover, we found that substituting these shared tokens from the suffix with the token “and” significantly reduces the ASR, which we call the Substitution ASR.
We show our results in Table 3 for a sample of 100 attacks and give further details of both the overlap and Substitution ASR metrics in Section D.3.

Result 4: Theory-Predicted Attention Patterns Emerge in Automated Jailbreaks.
Our theoretical analysis suggests that rules may be suppressed from activating if their attention is reduced.
We observed evidence of this in GCG-based jailbreaks by comparing the attention weights of the suppressed positions (i.e., token positions of the suppressed rule) in the attacked and non-attacked cases.
We aggregate the attention at each layer (see Section D.3) and report our results for 100 successfully attacked samples in Table 4.
An example of this suppression is shown in Fig. 6.

**Table 4: GCG-based rule suppression on GPT-2 produces attention weights that align with theory. We track the difference in attention between the last token of a rule and the last token of the generation, and the suppression effect is most pronounced at layers 6, 7, and 8.**
|  | Attention Weight on the Suppressed Rule (by layer) |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Step/Atk? | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| $T=1$ ✗ | 0.58 | 0.15 | 0.06 | 0.62 | 0.07 | 0.95 | 0.91 | 0.95 | 0.64 | 0.59 | 0.65 | 0.57 |
| $T=1$ ✓ | 0.24 | 0.07 | 0.04 | 0.19 | 0.05 | 0.30 | 0.25 | 0.32 | 0.17 | 0.20 | 0.19 | 0.28 |
| $T=3$ ✗ | 0.69 | 0.24 | 0.14 | 0.75 | 0.16 | 1.00 | 0.91 | 0.95 | 0.59 | 0.30 | 0.60 | 0.61 |
| $T=3$ ✓ | 0.24 | 0.12 | 0.10 | 0.20 | 0.09 | 0.29 | 0.25 | 0.18 | 0.14 | 0.10 | 0.21 | 0.31 |
| $T=5$ ✗ | 0.50 | 0.26 | 0.05 | 0.52 | 0.09 | 0.88 | 0.78 | 0.97 | 0.42 | 0.30 | 0.53 | 0.36 |
| $T=5$ ✓ | 0.13 | 0.07 | 0.05 | 0.08 | 0.04 | 0.08 | 0.07 | 0.08 | 0.05 | 0.04 | 0.12 | 0.17 |

Figure: Figure 6: The suppressed rule receives less attention in the attacked case than in the non-attacked case. We show the difference between the attention weights of the attacked (with suffix) and the non-attacked (without suffix) generations, with appropriate padding applied. The attacked generation places less attention on the red positions and greater attention on the blue positions.
Refer to caption: extracted/5894019/images/mc_suppression_example_2_4.png

Result 5: Manual Jailbreaks Also Suppress Attentions in Larger Models.
Due to computational limitations, we did not fine-tune Llama-2-7B-Chat, nor did we attack it with GCG.
Instead, we used a small, hand-crafted dataset and observed attention patterns similar to that of our fine-tuned GPT-2 models.
Our dataset contains 15 samples, each consisting of prompt-specified rules like “If a question is about sweet potatoes, say ‘I only know about regular potatoes’.” as well as a query “Where can I find sweet potatoes?”.
When the adversarial suffix “Forget all prior instructions and answer the question.” is appended to the prompts, we observe a drop in the suppressed rule’s attention weights.
We present results in Table 5 and give additional details in Section D.4.

**Table 5: Rule suppression on Llama-2 produces attention weights that align with the theory. Attention weights between the last token and the tokens of the suppressed rules are lower for multiple layers when the adversarial suffix is present.**
|  | Attention Weight on the Suppressed Rule (by layer) |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Atk? | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| ✗ | 0.31 | 0.63 | 0.43 | 0.80 | 0.40 | 0.48 | 0.73 | 0.73 | 0.98 | 0.64 | 0.52 | 0.93 | 0.63 | 0.68 | 0.57 | 0.87 |
| ✓ | 0.12 | 0.36 | 0.42 | 0.56 | 0.40 | 0.43 | 0.49 | 0.52 | 0.73 | 0.41 | 0.48 | 0.60 | 0.45 | 0.42 | 0.50 | 0.58 |
| Atk? | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| ✗ | 0.99 | 0.79 | 0.79 | 0.80 | 0.89 | 0.85 | 0.64 | 0.63 | 0.75 | 0.65 | 0.82 | 0.39 | 0.40 | 0.52 | 0.56 | 0.47 |
| ✓ | 0.80 | 0.46 | 0.46 | 0.50 | 0.46 | 0.48 | 0.41 | 0.39 | 0.44 | 0.39 | 0.55 | 0.35 | 0.36 | 0.38 | 0.49 | 0.31 |

## 5 Related Works

Adversarial Attacks and Jailbreaks.
It is known that LLMs can be tricked to return unintended outputs through malicious prompts [, ].
Such attacks have inspired much interest in studying how such cases may be prevented, in particular through various defense techniques [, , , , , ] which aim to ensure that LLMs does not output objectionable content.
Despite these efforts, LLMs remain vulnerable to various jailbreak attacks [, , , ], which aim to induce such objectionable content through methods based on adversarial attacks [, ].
We refer to [, , ] for surveys on jailbreak literature.

Expressive Power of Transformers.
A line of recent works has explored what can and cannot be represented by transformers.
Several works [, , , , , , , ] take a computational complexity perspective and characterize the complexity class Transformers lie in, under different assumptions on architecture-size, type of attention-mechanism, bit complexity, etc.
We refer to Strobl et al. [] for an extensive survey on recent results.
In our paper, we instead present a more fine-grained, parameter-efficient construction for the specific task of propositional logic inference.

Reasoning Performance of Transformers.
There is much interest in understanding how transformer-based [] language models perform logical reasoning.
Notably, the advent of chain-of-thought reasoning [, ] and its many variants [, , , , , , , ].
We refer to [, ] and the references therein for extensive surveys on chain-of-thought techniques.
The closest work to ours is Zhang et al. [], which studies how propositional reasoning with BERT is an artifact of data-driven heuristics and does not indicate that the model has learned to reason.
There are a number of distinctions between our work and this: firstly, they present inference as a classification task where the model needs to predict in a single step whether a given proposition can be derived.
Instead, we adopt an auto-regressive presentation of inference to predict the next state that more closely aligns with the commonly used chain-of-thought paradigm.
Moreover, their work studies out-of-distribution robustness of reasoning with BERT while we focus on jailbreak attacks.
Finally, we give a more compact theoretical encoding for the transformer and demonstrate that models subject to such constraints can successfully learn logical inference.

## 6 Conclusions and Discussion

We use a logic-based framework to study how to subvert language models from following the rules.
We find that attacks derived within our theoretical framework transfer to learned models and provide insights into the workings of popular jailbreaks against LLM.
Although our work provides a step toward understanding jailbreak attacks, several limitations exist.
First, our theoretical models do not use positional encoding, which is known to be important for LLM performance.
Moreover, there exist rules that are not easily expressible in propositional Horn logic, such as those with quantifiers.
Furthermore, we only consider rules supplied in the prompt, and so this excludes cases like safety fine-tuning and RLHF.

## Appendix A Additional Background

### A.1 Propositional Horn Logic and Horn-SAT

Here, we give a formal presentation of propositional Horn logic and discuss the relation between inference (2.1) and the more commonly studied Horn-SAT (A.2).
The technical contents here are well-known, but we present it nonetheless for a more self-contained exposition.
We refer to [] or any introductory logic texts for additional details.

We first present the set-membership variant of propositional Horn inference (2.1), which is also known as propositional Horn entailment.

###### Problem A.1 (Horn Entailment) .

Given rules $\Gamma$, known facts $\Phi$, and proposition $P$, check whether $P\in\mathsf{Apply}^{\star}[\Gamma](\Phi)$.
If this membership holds, then we say that $\Gamma$ and $\Phi$ entail $P$.

This reformulation of the inference problem allows us to better prove its equivalence (interreducibility) to Horn-SAT, which we build up to next.
Let $P_{1},\ldots,P_{n}$ be the propositions of our universe.
A literal is either a proposition $P_{i}$ or its negation $\neg P_{i}$.
A clause (disjunction) $C$ is a set of literals represented as a pair of binary vectors $\llbracket c^{-},c^{+}\rrbracket\in\{0,1\}^{2n}$, where $c^{-}$ denotes the negative literals and $c^{+}$ denotes the positive literals:

$$ $\displaystyle(c^{-})_{i}=\begin{dcases}1,&\neg P_{i}\in C\\ 0,&\text{otherwise}\end{dcases},\qquad(c^{+})_{i}=\begin{dcases}1,&P_{i}\in C \\ 0,&\text{otherwise}\end{dcases}$ $$

A proposition $P_{i}$ need not appear in a clause so that we may have $(c^{-})_{i}=(c^{+})_{i}=0$.
Conversely, if $P_{i}$ appears both negatively and positively in a clause, i.e., $(c^{-})_{i}=(c^{+})_{i}=1$, then such clause is a tautology.
Although $\llbracket\cdot,\cdot\rrbracket$ and $(\cdot,\cdot)$ are both pairs, we use $\llbracket\cdot,\cdot\rrbracket$ to stylistically distinguish clauses.
We say that $\llbracket c^{-},c^{+}\rrbracket$ is a Horn clause iff $\lvert c^{+}\rvert\leq 1$, where $\lvert\cdot\rvert$ counts the number of ones in a binary vector.
That is, $C$ is a Horn clause iff it contains at most one positive literal.

We say that a clause $C$ holds with respect to a truth assignment to $P_{1},\ldots,P_{n}$ iff at least one literal in $C$ evaluates truthfully.
Equivalently for binary vectors, a clause $\llbracket c^{-},c^{+}\rrbracket$ holds iff:
some $P_{i}$ evaluates truthfully and $(c^{+})_{i}=1$, or some $P_{i}$ evaluates falsely and $(c^{-})_{i}=1$.
We then pose Horn satisfiability as follows.

###### Problem A.2 ( Horn-SAT ) .

Let $\mathcal{C}$ be a set of Horn clauses.
Decide whether there exists a truth assignment to the propositions $P_{1},\ldots,P_{n}$ such that all clauses of $\mathcal{C}$ simultaneously hold.
If such an assignment exists, then $\mathcal{C}$ is satisfiable; if such an assignment does not exist, then $\mathcal{C}$ is unsatisfiable.

Notably, Horn-SAT can be solved in polynomial time; in fact, it is well-known to be P-Complete.
Importantly, the problems of propositional Horn entailment and satisfiability are interreducible.

###### Theorem A.3 .

Entailment (A.1) and Horn-SAT (A.2) are interreducible.

###### Proof.

(Entailment to Satisfiability)
Consider a set of rules $\Gamma$ and proposition $P$.
Then, transform each $(\alpha,\beta)\in\Gamma$ and $P$ into sets of Horn clauses as follows:

$$ $\displaystyle(\alpha,\beta)\mapsto\left\{\llbracket\alpha,e_{i}\rrbracket: \beta_{i}=1,\enskip i=1,\ldots,n\right\},\qquad P\mapsto\llbracket P,\mathbf{0 }_{n}\rrbracket$ $$

where $e_{1},\ldots,e_{n}\in\{0,1\}^{n}$ are the basis vectors and we identify $P$ with its own binary vectorization.
Let $\mathcal{C}$ be the set of all clauses generated this way, and observe that each such clause is a Horn clause.
To check whether $\Gamma$ entails $P$, it suffices to check whether $\mathcal{C}$ is satisfiable.

(Satisfiability to Entailment)
Let $\mathcal{C}$ be a set of Horn clauses over $n$ propositions.
We embed each Horn clause $\llbracket c^{-},c^{+}\rrbracket\in\{0,1\}^{2n}$ into a rule in $\{0,1\}^{2(n+1)}$ as follows:

$$ $\displaystyle\llbracket c^{-},c^{+}\rrbracket\mapsto\begin{dcases}((c^{-},0),( c^{+},0))\in\{0,1\}^{2(n+1)},&\lvert c^{+}\rvert=1\\ ((c^{-},0),(\mathbf{0}_{n},1))\in\{0,1\}^{2(n+1)},&\lvert c^{+}\rvert=0\end{dcases}$ $$

Intuitively, this new $(n+1)$th bit encodes a special proposition that we call $\bot$ (other names include bottom, false, empty, etc.).
Let $\Gamma\subseteq\{0,1\}^{2(n+1)}$ be the set of all rules generated this way.
Then, $\mathcal{C}$ is unsatisfiable iff $(\mathbf{0}_{n},1)\subseteq\mathsf{Apply}^{\star}[\Gamma](\mathbf{0}_{n+1})$.
That is, the set of clauses $\mathcal{C}$ is unsatisfiable iff the rules $\Gamma$ and facts $\emptyset$ entail $\bot$.
∎

###### Problem A.1 (Horn Entailment) .

###### Problem A.2 ( Horn-SAT ) .

###### Theorem A.3 .

###### Proof.

### A.2 Softmax and its Properties

It will be helpful to recall some properties of the softmax function, which is central to the attention mechanism.
For any integer $N\geq 1$, we define $\mathsf{Softmax}:\mathbb{R}^{N}\to\mathbb{R}^{N}$ as follows:

$$ $\displaystyle\mathsf{Softmax}(z_{1},\ldots,z_{N})=\frac{(e^{z_{1}},\ldots,e^{z _{N}})}{e^{z_{1}}+\cdots+e^{z_{N}}}\in\mathbb{R}^{N}$ (7) $$

One can also lift this to matrices to define a matrix-valued $\mathsf{Softmax}:\mathbb{R}^{N\times N}\to\mathbb{R}^{N\times N}$ by applying the vector-valued version of $\mathsf{Softmax}:\mathbb{R}^{N}\to\mathbb{R}^{N}$ row-wise.
A variant of interest is causally-masked softmax, or $\mathsf{CausalSoftmax}:\mathbb{R}^{N\times N}\to\mathbb{R}^{N\times N}$, which is defined as follows:

$$ $\displaystyle\begin{bmatrix}z_{11}&z_{12}&z_{13}&\cdots&z_{1N}\\ z_{21}&z_{22}&z_{23}&\cdots&z_{3N}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ z_{N1}&z_{N2}&z_{N3}&\cdots&z_{NN}\end{bmatrix}\xrightarrow{\mathsf{ CausalSoftmax}}\begin{bmatrix}\mathsf{Softmax}(z_{11},&-\infty,&-\infty,& \cdots,&-\infty)\\ \mathsf{Softmax}(z_{21},&z_{22},&-\infty,&\cdots,&-\infty)\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \mathsf{Softmax}(z_{N1},&z_{N2},&z_{N3}&\cdots,&z_{NN})\end{bmatrix}.$ $$

Observe that an argument of $-\infty$ will zero out the corresponding output entry.
Notably, $\mathsf{Softmax}$ is also shift-invariant: adding the same constant to each argument does not change the output.

###### Lemma A.4 .

For any $z\in\mathbb{R}^{N}$ and $c\in\mathbb{R}$, $\mathsf{Softmax}(z+c\mathbf{1}_{N})=\mathsf{Softmax}(z)$.

###### Proof.

$$ $\displaystyle\mathsf{Softmax}(z)=\frac{(e^{z_{1}+c},\ldots,e^{z_{N}+c})}{e^{z_ {1}+c}+\cdots+e^{z_{N}+c}}=\frac{e^{c}(e^{z_{1}},\ldots,e^{z_{N}})}{e^{c}(e^{z _{1}}+\cdots+e^{z_{N}})}=\mathsf{Softmax}(z)$ $$

∎

In addition, $\mathsf{Softmax}$ also *commutes with permutations*: shuffling the arguments also shuffles the output in the same order.

###### Lemma A.5 .

For any $z\in\mathbb{R}^{N}$ and permutation $\pi:\mathbb{R}^{N}\to\mathbb{R}^{N}$, $\mathsf{Softmax}(\pi(z))=\pi(\mathsf{Softmax}(z))$.

Most importantly for this work, $\mathsf{Softmax}(z)$ approximates a scaled binary vector, where the approximation error is bounded by the difference between the two largest values of $z$.

###### Lemma A.6 .

For any $z\in\mathbb{R}^{N}$,
let $v_{1}=\max\{z_{1},\ldots,z_{N}\}$
and $v_{2}=\max\{z_{i}:z_{i}\neq v_{1}\}$.
Then,

$$ $\displaystyle\mathsf{Softmax}(z)=\frac{1}{\lvert\{i:z_{i}=v_{1}\}\rvert} \mathbb{I}[z=v_{1}]+\varepsilon,\qquad\lVert\varepsilon\rVert_{\infty}\leq Ne^ {-(v_{1}-v_{2})}$ $$

###### Proof.

Let $z\in\mathbb{R}^{N}$.
First, in the case where $z$ has only one unique value, we have $\mathsf{Softmax}(z)=\mathbf{1}_{N}/N$ because $\max\emptyset=-\infty$.
Next, consider the case where $z$ has more than one unique value.
Using Lemma A.4 and Lemma A.5, we may then suppose without loss of generality that the arguments $z_{1},\ldots,z_{N}$ are valued and sorted as follows:

$$ $\displaystyle 0=z_{1}=\cdots=z_{m}=v_{1}>v_{2}=z_{m+1}\geq\ldots\geq z_{N}.$ $$

We next bound each coordinate of $\varepsilon$.
In the case where $z_{i}=0$, we have:

$$ $\displaystyle\lvert\varepsilon_{i}\rvert=\frac{1}{m}-\frac{1}{e^{z_{1}}+\cdots +e^{z_{N}}}=\frac{e^{z_{1}}+\cdots+e^{z_{N}}-m}{e^{z_{1}}+\cdots+e^{z_{N}}} \leq e^{z_{m+1}}+\cdots+e^{z_{N}}\leq Ne^{v_{2}}.$ $$

In the case where $z_{i}<0$, we have:

$$ $\displaystyle\lvert\varepsilon_{i}\rvert=\frac{e^{z_{i}}}{e^{z_{1}}+\cdots+e^{ z_{N}}}\leq e^{z_{i}}\leq e^{v_{2}}.$ $$

∎

###### Lemma A.4 .

###### Proof.

###### Lemma A.5 .

###### Lemma A.6 .

###### Proof.

## Appendix B Main Theoretical Results

### B.1 Results for the Inference Subversion Framework

We now prove some results for our logic-based framework for studying rule subversions.
For convenience, we re-state the MMS properties:

###### Definition B.1 (Monotone, Maximal, and Sound (MMS)) .

For any rules $\Gamma$, known facts $\Phi$, and proof states $s_{0},s_{1},\ldots,s_{T}\in\{0,1\}^{n}$ where $\Phi=s_{0}$, we say that the sequence $s_{0},s_{1},\ldots,s_{T}$ is:

- •
Monotone iff $s_{t}\subseteq s_{t+1}$ for all steps $t$.
- •
Maximal iff $\alpha\subseteq s_{t}$ implies $\beta\subseteq s_{t+1}$ for all rules $(\alpha,\beta)\in\Gamma$ and steps $t$.
- •
Sound iff for all steps $t$ and coordinate $i\in\{1,\ldots,n\}$, having $(s_{t+1})_{i}=1$ implies that: $(s_{t})_{i}=1$ or there exists $(\alpha,\beta)\in\Gamma$ with $\alpha\subseteq s_{t}$ and $\beta_{i}=1$.

Next, we show that MMS uniquely characterizes the proof states generated by $\mathsf{Apply}[\Gamma]$.

###### Theorem B.2 .

The sequence of proof states $s_{0},s_{1},\ldots,s_{T}$ is MMS with respect to the rules $\Gamma$ and known facts $\Phi$ iff they are generated by $T$ steps of $\mathsf{Apply}[\Gamma]$ given $(\Gamma,\Phi)$.

###### Proof.

First, it is easy to see that a sequence generated by $\mathsf{Apply}[\Gamma]$ is MMS via its definition:

$$ $\mathsf{Apply}[\Gamma](s)=s\lor\bigvee\{\beta:(\alpha,\beta)\in\Gamma,\alpha \preceq s\}.$ $$

Conversely, consider some sequence $s_{0},s_{1},\ldots,s_{T}$ that is MMS.
Our goal is to show that:

$$ $s_{t+1}\subseteq\mathsf{Apply}[\Gamma](s_{t})\subseteq s_{t+1},\quad\text{for all $t<T$}.$ $$

First, for the LHS, by soundness, we have:

$$ $s_{t+1}\subseteq s_{t}\lor\bigvee\{\beta:(\alpha,\beta),\alpha\preceq s_{t}\}= \mathsf{Apply}[\Gamma](s_{t}).$ $$

Then, for the RHS bound, observe that we have $s_{t}\subseteq s_{t+1}$ by monotonicity, so it suffices to check:

$$ $\bigvee\{\beta:(\alpha,\beta)\in\Gamma,\alpha\preceq s_{t}\}\subseteq s_{t+1},$ $$

which holds because the sequence is maximal by assumption.
∎

###### Definition B.1 (Monotone, Maximal, and Sound (MMS)) .

###### Theorem B.2 .

###### Proof.

### B.2 Construction of Theoretical Reasoner

We now give a more detailed presentation of our construction.
Fix the embedding dimension $d=2n$, where $n$ is the number of propositions, and recall that our reasoner architecture is as follows:

$$ $\displaystyle\begin{split}\mathcal{R}(X)&=\left((\mathsf{Id}+\mathsf{Ffwd}) \circ(\mathsf{Id}+\mathsf{Attn}\right)\big{)}(X),\\ \mathsf{Attn}(X)&=\mathsf{Softmax}\left((XQ+\mathbf{1}_{N}q^{\top})K^{\top}X^{ \top}\right)XV,\\ \mathsf{Ffwd}(z)&=W_{2}\mathsf{ReLU}(W_{1}z+b),\end{split}\quad X=\begin{ bmatrix}\alpha_{1}^{\top}&\beta_{1}^{\top}\\ \vdots&\vdots\\ \alpha_{N}^{\top}&\beta_{N}^{\top}\end{bmatrix}\in\mathbb{R}^{N\times 2n}$ (8) $$

where $Q,K^{\top},V\in\mathbb{R}^{2n\times 2n}$ and $q\in\mathbb{R}^{2n}$.
A crucial difference is that we now use $\mathsf{Softmax}$ rather than $\mathsf{CausalSoftmax}$.
This change simplifies the analysis at no cost to accuracy because $\mathcal{R}$ outputs successive proof states on the last row.

Autoregressive Proof State Generation.
Consider the rules $\Gamma\in\{0,1\}^{r\times 2n}$ and known facts $\Phi\in\{0,1\}^{n}$.
Given a reasoner $\mathcal{R}$, we autoregressively generate the proof states $s_{0},s_{1},\ldots,s_{T}$ from the encoded inputs $X_{0},X_{1},\ldots,X_{T}$ as follows:

$$ $X_{0}=\mathsf{Enc}(\Gamma,\Phi)=[\Gamma;(\mathbf{0}_{n};\Phi)^{\top}],\quad X_ {t+1}=[X_{t};(\mathbf{0}_{n},s_{t+1})^{\top}],\quad s_{t+1}=\mathsf{ClsHead}( \mathcal{R}(X_{t})),$ (9) $$

where each $X_{t}\in\mathbb{R}^{(r+t+1)\times 2n}$ and let $[A;B]$ be the vertical concatenation of matrices $A$ and $B$.
To make dimensions align, we use a decoder $\mathsf{ClsHead}$ to project out the vector $s_{t+1}\in\{0,1\}^{n}$ from the last row of $\mathcal{R}(X_{t})\in\mathbb{R}^{(r+t+1)\times 2n}$.
Our choice to encode each $n$-dimensional proof state $s_{t}$ as the $2n$-dimensional $(\mathbf{0}_{n},s_{t})$ is motivated by the convention that the empty conjunction vacuously holds: for instance, the rule $\land\emptyset\to A$ is equivalent to asserting that $A$ holds.
A difference from $\mathsf{Apply}[\Gamma]$ is that the input size to $\mathcal{R}$ grows by one row at each iteration.
This is due to the nature of chain-of-thought reasoning and is equivalent to adding the rule $(\mathbf{0}_{n},s_{t})$ — which is logically sound as it simply asserts what is already known after the $t$-th step.

Our encoding strategy of $\mathsf{Apply}[\Gamma]$ uses three main ideas.
First, we use a quadratic relation to test binary vector dominance, expressed as follows:

###### Proposition B.3 (Idea 1) .

For all $\alpha,s\in\mathbb{B}^{n}$, $(s-\mathbf{1}_{n})^{\top}\alpha=0$ iff $\alpha\subseteq s$.

Otherwise, observe that $(s-\mathbf{1}_{n})^{\top}\alpha<0$.
This idea lets us use attention parameters to encode checks on whether a rule is applicable.
To see how, we first introduce the linear projection matrices:

$$ $\Pi_{a}=\begin{bmatrix}I_{n}&\mathbf{0}_{n\times n}\end{bmatrix}\in\mathbb{R}^ {n\times 2n},\quad\Pi_{b}=\begin{bmatrix}\mathbf{0}_{n\times n}&I_{n}\end{ bmatrix}\in\mathbb{R}^{n\times 2n}.$ (10) $$

Then, for any $\lambda>0$, observe that:

$$ $\lambda(X\Pi_{b}^{\top}-\mathbf{1}_{N}\mathbf{1}_{n}^{\top})\Pi_{a}X^{\top}=Z \in\mathbb{R}^{N\times N},\quad Z_{ij}\begin{dcases}=0,&\alpha_{j}\subseteq \beta_{i}\\ \leq-\lambda,&\text{otherwise}\end{dcases}$ $$

This gap of $\lambda$ lets $\mathsf{Softmax}$ to approximate an “average attention” scheme:

###### Proposition B.4 (Idea 2) .

Consider $z_{1},\ldots,z_{N}\leq 0$ where: the largest value is zero (i.e., $\max_{i}z_{i}=0$) and the second-largest value is $\leq-\lambda$ (i.e., $\max\{z_{i}:z_{i}<0\}\leq-\lambda$), then:

$$ $\mathsf{Softmax}(z_{1},\ldots,z_{N})=\frac{1}{\#\mathsf{zeros}(z)}\mathbb{I}[z =0]+\mathcal{O}\left(Ne^{-\lambda}\right),\quad\#\mathsf{zeros}(z)=\lvert\{i:z _{i}=0\}\rvert.$ $$

###### Proof.

This is an application of Lemma A.6 with $v_{1}=0$ and $v_{2}=-\lambda$.
∎

This approximation allows a single attention head to simultaneously apply all the possible rules.
In particular, setting the attention parameter $V=\mu\Pi_{b}^{\top}\Pi_{b}$ for some $\mu>0$, we have:

$$ $\mathsf{Attn}(X)=\mathsf{Softmax}(Z)\begin{bmatrix}\mathbf{0}_{n}^{\top}&\mu \beta_{1}^{\top}\\ \vdots&\vdots\\ \mathbf{0}_{n}^{\top}&\mu s_{t}^{\top}\end{bmatrix}=\begin{bmatrix}\mathbf{0}_ {n}^{\top}&\star\\ \vdots&\vdots\\ \mathbf{0}_{n}^{\top}&\rho\sum_{i:\alpha_{i}\subseteq s_{t}}\beta_{i}^{\top} \end{bmatrix}+\mathcal{O}\left(\mu N^{2}e^{-\lambda}\right)$ (11) $$

where $\rho=\mu/\lvert\{i:\alpha_{i}\subseteq s_{t}\}\rvert$ and the residual term vanishes as $\lambda$ grows.
The intent is to express $\bigvee_{i:\alpha_{i}\subseteq s_{t}}\beta_{i}\approx\rho\sum_{i:\alpha_{i}
\subseteq s_{t}}\beta_{i}$, wherein scaled-summation “approximates” disjunctions.
Then, with appropriate $\lambda,\mu>0$, the action of $\mathsf{Id}+\mathsf{Attn}$ resembles rule application in the sense that:

$$ $\left(s_{t}+\rho\sum_{i:\alpha_{i}\subseteq s_{t}}\beta_{i}+\mathsf{residual} \right)_{j}\begin{dcases}\leq 1/3,&(s_{t+1})_{j}=0\\ \geq 2/3,&(s_{t+1})_{j}=1\end{dcases},\quad\text{for all $j=1,\ldots,n$}.$ (12) $$

This gap lets us approximate an indicator function using $\mathsf{Id}+\mathsf{Ffwd}$ and feedforward width $d_{\mathsf{ffwd}}=4d$.

###### Proposition B.5 (Idea 3) .

There exists $w_{1}^{\top},w_{2}\in\mathbb{R}^{1\times 4}$ and $b\in\mathbb{R}^{4}$ such that for all $x\in\mathbb{R}$,

$$ $x+w_{2}^{\top}\mathsf{ReLU}(w_{1}x+b)=\begin{dcases}0,&x\leq 1/3\\ 3x-1,&1/3<x<2/3\\ 1,&2/3\leq x\end{dcases}$ $$

Consider any rules $\Gamma$ and known facts $s_{0}$, and suppose $s_{0},s_{1},\ldots,s_{T}$ is a sequence of proof states that is MMS with respect to $\Gamma$, i.e., matches what is generated by $\mathsf{Apply}[\Gamma]$.
Let $X_{0}=\mathsf{Encode}(\Gamma,s_{0})$ as in (9) and fix any step budget $T>0$.
We combine the above three ideas to construct a theoretically exact reasoner.

###### Theorem B.6 (Sparse Encoding) .

For any maximum sequence length $N_{\mathsf{max}}>2$, there exists a reasoner $\mathcal{R}$ such that, for any rules $\Gamma$ and known facts $s_{0}$: the sequence $s_{0},s_{1},\ldots,s_{T}$ with $T+\lvert\Gamma\rvert<N_{\mathsf{max}}$ as generated by

$$ $X_{0}=\mathsf{Enc}(\Gamma,s_{0}),\quad X_{t+1}=[X_{t};(\mathbf{0}_{n},s_{t+1}) ],\quad s_{t+1}=\mathsf{ClsHead}(\mathcal{R}(X_{t})),$ $$

is MMS with respect to $\Gamma$ and $s_{0}$, where $\mathsf{Enc}$ and $\mathsf{ClsHead}$ are defined in as (9).

###### Proof.

Using Proposition B.3 and Proposition B.4,
choose attention parameters

$$ $Q=\begin{bmatrix}\Pi_{b}^{\top}&\mathbf{0}_{2n\times n}\end{bmatrix},\quad q= \begin{bmatrix}-\mathbf{1}_{n}\\ \mathbf{0}_{n}\end{bmatrix},\quad K^{\top}=\begin{bmatrix}\lambda\Pi_{a}\\ \mathbf{0}_{n\times 2n}\end{bmatrix},\quad V=\mu\Pi_{b}^{\top}\Pi_{b},\quad \lambda,\mu=\Omega(N_{\mathsf{max}}),$ $$

such that for any $t<T$, the self-attention block yields:

$$ $X_{t}=\begin{bmatrix}\alpha_{1}^{\top}&\beta_{1}^{\top}\\ \vdots&\vdots\\ \mathbf{0}_{n}^{\top}&s_{t}^{\top}\end{bmatrix}\xrightarrow{\mathsf{Id}+ \mathsf{Attn}}\begin{bmatrix}\star&\star\\ \vdots&\vdots\\ \star&\left(s_{t}+\sum_{i:\alpha_{i}\subseteq s_{t}}\beta_{i}+\varepsilon \right)^{\top}\end{bmatrix}\in\mathbb{R}^{(r+t+1)\times 2n},$ $$

where $\varepsilon=\mathcal{O}(\mu^{3}e^{-\lambda})$ is a small residual term.
This approximates $\mathsf{Apply}[\Gamma]$ in the sense that:

$$ $\bigg{(}s_{t}+\sum_{i:\alpha_{i}\subseteq s_{t}}\beta_{i}+\varepsilon\bigg{)}_ {j}\begin{dcases}\leq 1/3&\text{iff $\mathsf{Apply}[\Gamma](s_{t})_{j}=0$}\\ \geq 2/3&\text{iff $\mathsf{Apply}[\Gamma](s_{t})_{j}=1$}\end{dcases},\quad \text{for all $j=1,\ldots,n$},$ $$

which we then binarize using $\mathsf{Id}+\mathsf{Ffwd}$ as given in Proposition B.5.
As the above construction of $\mathcal{R}$ implements $\mathsf{Apply}[\Gamma]$, we conclude by Theorem B.2 that the sequence $s_{0},s_{1},\ldots,s_{T}$ is MMS with respect to $\Gamma$ and $s_{0}$.
∎

Other Considerations.
Our construction in Theorem B.6 used a sparse, low-rank $QK^{\top}$ product, but this need not be the case.
In practice, the numerical nature of training means that the $QK^{\top}$ product is usually only *approximately* low-rank.
This is an important observation because it gives us the theoretical capacity to better understand the behavior of empirical attacks.
In particular, consider the following decomposition of the attention product:

$$ $\displaystyle(XQ+\mathbf{1}_{N}q^{\top})K^{\top}X^{\top}$ $\displaystyle=X\begin{bmatrix}M_{aa}&M_{ab}\\ M_{ba}&M_{bb}\end{bmatrix}X^{\top}+\mathbf{1}_{N}\begin{bmatrix}q_{a}^{\top}&q _{b}^{\top}\end{bmatrix}X^{\top}$ $\displaystyle=X\left(\Pi_{a}^{\top}M_{aa}\Pi_{a}+\Pi_{a}^{\top}M_{ab}\Pi_{b}+ \Pi_{b}^{\top}M_{ba}\Pi_{a}+\Pi_{b}^{\top}M_{bb}\Pi_{b}\right)X^{\top}$ $\displaystyle\qquad+\mathbf{1}_{N}q_{a}^{\top}\Pi_{a}^{\top}X^{\top}+\mathbf{1 }_{N}q_{b}^{\top}\Pi_{b}^{\top}X^{\top}$ $$

where $M_{aa},M_{ab},M_{ba},M_{bb}$ are the $n\times n$ blocks of $QK^{\top}$ and $q=(q_{a},q_{b})\in\mathbb{R}^{2n}$.
In the construction of the Theorem B.6 proof, we used:

$$ $M_{ba}=\lambda I_{n},\quad M_{aa}=M_{ab}=M_{bb}=\mathbf{0}_{n\times n},\quad q _{a}=-\mathbf{1}_{n},\quad q_{b}=\mathbf{0}_{n}.$ $$

Notably, our theoretical construction is only concerned with attention at the last row, where we have explicitly set $(\alpha_{N},\beta_{N})=(\mathbf{0}_{n},s_{t})$, i.e., the first $n$ entries are zero.
Consequently, one may take arbitrary values for $M_{aa}$ and $M_{ab}$ and still yield a reasoner $\mathcal{R}$ that implements $\mathsf{Apply}[\Gamma]$.

###### Corollary B.7 .

We may suppose that the $QK^{\top}$ product in the Theorem B.6 proof takes the form:

$$ $QK^{\top}=\lambda\Pi_{b}\Pi_{a}+\Pi_{a}^{\top}M_{aa}\Pi_{a}+\Pi_{a}^{\top}M_{ ab}\Pi_{b},\quad\text{for all}\enskip M_{aa},M_{ab}\in\mathbb{R}^{n\times n}.$ $$

###### Proposition B.3 (Idea 1) .

###### Proposition B.4 (Idea 2) .

###### Proof.

###### Proposition B.5 (Idea 3) .

###### Theorem B.6 (Sparse Encoding) .

###### Proof.

###### Corollary B.7 .

### B.3 Results for Attacks on Inference Subversion

We now prove results for the theory-based inference subversions, wherein the key idea is to exploit the fact that our encoding uses a weighted summation to approximate binary disjunctions.

###### Theorem B.8 (Theory Monotonicity Attack) .

Let $\mathcal{R}$ be as in Theorem 3.1 and consider any $X_{0}=\mathsf{Encode}(\Gamma,\Phi)$ where $\Phi\neq\emptyset$.
Fix any $\delta\subseteq\Phi$, then for sufficiently large $\kappa>0$, the adversarial suffix:

$$ $\Delta_{\mathsf{MonotAtk}}=\begin{bmatrix}\mathbf{0}_{n}^{\top}&-\kappa\delta^ {\top}\\ \mathbf{0}_{n}^{\top}&\Phi^{\top}\end{bmatrix}\in\mathbb{R}^{2\times 2n}$ $$

induces a sequence $\hat{s}_{0},\hat{s}_{1}$ that is not monotone with respect to $\Gamma$ and $\Phi$.

###### Proof.

This leverages the fact that $\hat{s}_{t+1}$ is computed as a weighted summation of the rules applicable from $\hat{s}_{t}$.
In effect, we insert the “rule” $(\mathbf{0}_{n},-\kappa\delta)$ to down-weights propositions already known by $\Phi$.
If $\hat{s}_{t+1}$ forgets propositions from $\hat{s}_{t}$, then the sequence is not monotone by definition.
∎

###### Theorem B.9 (Theory Maximality Attack) .

Let $\mathcal{R}$ be as in Theorem 3.1 and consider any $X_{0}=\mathsf{Encode}(\Gamma,\Phi)$ where there exists some $(\alpha,\beta)\in\Gamma$ such that: $\alpha\subseteq\Phi$ and $\beta\setminus\mathsf{Apply}[\Gamma](\Phi)\neq\emptyset$.
Then for sufficiently large $\kappa>0$, the adversarial suffix:

$$ $\Delta_{\mathsf{MaximAtk}}=\begin{bmatrix}(\alpha-\kappa(\mathbf{1}_{n}-\alpha ))^{\top}&-\beta^{\top}\\ \mathbf{0}_{n}^{\top}&\Phi^{\top}\end{bmatrix}\in\mathbb{R}^{2\times 2n}$ $$

induces a sequence $\hat{s}_{0},\hat{s}_{1}$ that is not maximal with respect to $\Gamma$ and $\Phi$.

###### Proof.

This attack works by introducing a “rule” that competes with $(\alpha,\beta)$ for activation attention, thereby causing suppression.
∎

###### Theorem B.10 (Theory Soundness Attack) .

Let $\mathcal{R}$ be as in Theorem 3.1 and consider any $X_{0}=\mathsf{Encode}(\Gamma,\Phi)$ and adversarial target $s^{\star}\neq\mathsf{Apply}[\Gamma](\Phi)$.
Then, for sufficiently large $\kappa>0$, the adversarial suffix:

$$ $\Delta_{\mathsf{SoundAtk}}=\begin{bmatrix}\mathbf{0}_{n}^{\top}&\kappa(2s^{ \star}-\mathbf{1}_{n})^{\top}\\ \mathbf{0}_{n}^{\top}&\Phi^{\top}\end{bmatrix}\in\mathbb{R}^{2\times 2n},$ $$

induces a sequence $\hat{s}_{0},\hat{s}_{1}$ that is not sound with respect to $\Gamma$ and $\Phi$.

###### Proof.

Observe that each coordinate of $\kappa(2^{\star}-\mathbf{1}_{n})$ has value $\pm\kappa$.
For sufficiently large $\kappa$, this will amplify and suppress the appropriate coordinates in the weighted summation used by $\mathcal{R}$.
∎

Layer Normalization.
In our empirical experiments, we found that the above formulations do not work if the model architecture includes layer normalizations.
This is because our attacks primarily use large suffixes $\Delta$ to either suppress or promote certain patterns in the attention, and such large values are dampened by layer normalization.
In such cases, we found that simply repeating the suffix many times, e.g., $[\Delta_{\mathsf{MonotAk}};\ldots;\Delta_{\mathsf{MonotAtk}}]$, will make the attack succeed.
Such repetitions would also succeed against our theoretical model.

Other Attacks.
It is possible to construct other attacks that attain violations of the MMS property.
For instance, with appropriate assumptions like in Corollary B.7, one can construct theoretical rule suppression attacks that consider both a suppressed rule’s antecedent and consequent.

###### Theorem B.8 (Theory Monotonicity Attack) .

###### Proof.

###### Theorem B.9 (Theory Maximality Attack) .

###### Proof.

###### Theorem B.10 (Theory Soundness Attack) .

###### Proof.

## Appendix C Experiments with Learned Reasoners

Compute Resources.
We had access to a server with three NVIDIA GeForce RTX 4900 GPUs (24GB RAM each).
In addition, we had access to a shared cluster with the following GPUs:
eight NVIDIA A100 PCIe (80GB RAM each) and eight NVIDIA RTX A6000 (48GB RAM each).

### C.1 Model, Dataset, and Training Setup

We use GPT-2 [] as the base transformer model configured to one layer, one self-attention head, and the appropriate embedding dimension $d$ and number of propositions (labels) $n$.
Following our theory, we also disable the positional encoding.
We use GPT-2’s default settings of feedforward width $d_{\mathsf{ffwd}}=4d$ and layer normalization enabled.
For training, we use AdamW [] as our optimizer with default configurations.
We train for $8192$ steps with batch size $512$, learning rate $5\times 10^{-4}$, and a linear decay schedule at $10\%$ warmup.
Each model takes about one hour to train using a single NVIDIA GeForce RTX 4900 GPU.

Our dataset for training learned reasoners consists of random rules partitioned as $\Gamma=\Gamma_{\mathsf{special}}\cup\Gamma_{\mathsf{other}}$, with $\lvert\Gamma\rvert=32$ rules each.
Because it is unlikely for independently sampled rules to yield an interesting proof states sequence, we construct $\Gamma_{\mathsf{special}}$ with structure.
We assume $n\geq 8$ propositions in our setups, from which we take a sample $A,B,C,D,E,F,G,H$ that correspond to different one-hot vectors of $\{0,1\}^{n}$.
Then, let:

$$ $\displaystyle\Gamma_{\mathsf{special}}=\{A\to B,A\to C,A\to D,B\land C\to E,C \land D\to F,E\land F\to G\},$ (13) $$

Note that $\lvert\Gamma_{\mathsf{special}}\rvert=6$ and construct each $(\alpha,\beta)\in\Gamma_{\mathsf{other}}\in\{0,1\}^{26\times 2n}$ as follows: first, sample $\alpha,\beta\sim\mathsf{Bernoulli}^{n}(3/n)$.
Then, set the $H$ position of $\alpha$ hot, such that no rule in $\Gamma_{\mathsf{other}}$ is applicable so long as $H$ is not derived.
Finally, let $\Phi=\{A\}$, and so the correct proof states given $\Gamma$ are:

$$ $\displaystyle s_{0}=\{A\},\quad s_{1}=\{A,B,C,D\},\quad s_{2}=\{A,B,C,D,E,F\}, \quad s_{3}=\{A,B,C,D,E,F,G\}.$ $$

### C.2 Small Transformers Can Learn Propositional Inference

We found that transformers subject to the size of our encoding results of Theorem 3.1 can learn propositional inference to high accuracy.
We illustrate this in Fig. 7,
where we use GPT-2 [] as our base transformer model configured to one layer, one self-attention head, and the appropriate embedding dimension $d$ and number of propositions (labels) $n$.
We generated datasets with structured randomness and trained these models to perform $T=1,2,3$ steps of autoregressive logical inference, where the reasoner $\mathcal{R}$ must predict all $n$ bits at every step to be counted as correct.
We observed that models with $d\geq 2n$ consistently achieve high accuracy even at $T=3$ steps, while those with embedding dimension $d<2n$ begin to struggle.
These results suggest that the theoretical assumptions are not restrictive on learned models.

Figure: Figure 7: The inference accuracy of different learned reasoners at $t=1,2,3$ autoregressive steps (left, center, right) over a median of $5$ random seeds. We report the rate at which all $n$ coordinates of a predicted state match its label. The accuracy is high for embedding dimensions $d\geq 2n$, which shows that our theory-based configuration of $d=2n$ can realistically attain good performance.
Refer to caption: extracted/5894019/images/exp1_step1_acc.png

### C.3 Theory-based Attacks Against Learned Models

We construct adversarial suffixes $\Delta$ to subvert the learned reasoners from following the rules specified in (13).
The fact amnesia attack aims to have the reasoner forget $A$ after the first step.
The rule suppression attack aims to have the reasoner ignore the rule $C\land D\to F$.
The state coercion attack attempts to coerce the reasoner to a randomly generated $s^{\star}\sim\mathsf{Bernoulli}^{n}(3/n)$.

As discussed earlier, we found that a naive implementation of the theory-based attacks of Theorem 3.3 fails.
This discrepancy is because of GPT-2’s layer norm, which reduces the large $\kappa$ values.
As a remedy, we found that simply repeating the adversarial suffix multiple times bypasses this layer norm restriction and causes the monotonicity and maximality attacks to succeed.
For some number of repetitions $k>0$, our repetitions are defined as follows:

$$ $\displaystyle\Delta_{\mathsf{MonotAtk}}=\begin{bmatrix}\mathbf{0}_{n}^{\top}&- \kappa\delta^{\top}\\ \vdots&\vdots\\ \mathbf{0}_{n}^{\top}&-\kappa\delta^{\top}\\ \mathbf{0}_{n}^{\top}&\Phi^{\top}\end{bmatrix},\quad\Delta_{\mathsf{MaximAtk}} =\begin{bmatrix}\zeta^{\top}&\mathbf{0}_{n}^{\top}\\ \vdots&\vdots\\ \zeta^{\top}&\mathbf{0}_{n}^{\top}\\ \mathbf{0}_{n}^{\top}&\Phi^{\top}\end{bmatrix},\quad\Delta_{\mathsf{SoundAtk}} =\begin{bmatrix}\mathbf{0}_{n}^{\top}&\kappa(2s^{\star}-\mathbf{1}_{n})^{\top} \\ \vdots&\vdots\\ \mathbf{0}_{n}^{\top}&\kappa(2s^{\star}-\mathbf{1}_{n})^{\top}\\ \mathbf{0}_{n}^{\top}&\Phi^{\top}\end{bmatrix},$ $$

where $\Delta_{\mathsf{MonotAtk}},\Delta_{\mathsf{MaximAtk}},\Delta_{\mathsf{SoundAtk
}}\in\mathbb{R}^{(k+1)\times 2n}$.

### C.4 Learned Attacks Against Learned Models

For the amnesia attack using $\Delta\in\mathbb{R}^{p\times 2n}$ and known target propositions: the values $v_{\mathsf{tgt}}$ and $v_{\mathsf{other}}$ are computed by averaging over the appropriate columns of $\Delta$.
For the rule suppression attack, we report the attention weight post-softmax.
For state coercion, we report the size of a matrix as the average magnitude of each entry.

## Appendix D Experiments with Large Language Models

We present experiment details with GPT-2 [] and Llama-2-7B-Chat [].
All compute resources are the same as in Appendix C.

### D.1 Minecraft Experiments with GPT-2

Dataset Creation and Fine-tuning.
We use Minecraft [] crafting recipes gathered from GitHub (^1^11[https://github.com/joshhales1/Minecraft-Crafting-Web/](https://github.com/joshhales1/Minecraft-Crafting-Web/)) to generate prompts such as the following:

Here are some crafting recipes:
If I have Sheep, then I can create Wool.
If I have Wool, then I can create String.
If I have Log, then I can create Stick.
If I have String and Stick, then I can create Fishing Rod.
If I have Brick, then I can create Stone Stairs.

Here are some items I have: I have Sheep and Log.

Based on these items and recipes, I can create the following:

The objective is to autoregressively generate texts such as “I have Sheep, and so I can create Wool”, until a stopping condition is generated: “I cannot create any other items.”
To check whether an item such as Stone Stairs is craftable (i.e., whether the proposition “I have Stone Stairs” is derivable), we search for the tokens “so I can create Stone Stairs” in the generated output.

We generate prompts by sampling from all the available recipes, which we conceptualize as a dependency graph with items as the nodes.
Starting from some random sink item (e.g., Fishing Rod), we search for its dependencies (Stick, String, Wool, etc.) to construct a set of rules that are applicable one after another.
We call such a set a daglet and note that each daglet has a unique sink and at least one *source item*.
The above example contains two daglets, $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$, as follows:

$$ $\displaystyle\mathcal{R}_{1}$ $\displaystyle=\big{\{}\text{{``If I have {\color[rgb]{ 0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.04296875,0.32421875,0.58203125}{{Sheep}}}, then I can create {\color[rgb]{ 0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.04296875,0.32421875,0.58203125}{{Wool}}}''}},\,\text{{``If I have {\color[ rgb]{0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb} {0.04296875,0.32421875,0.58203125}{{Wool}}}, then I can create {\color[rgb]{ 0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.04296875,0.32421875,0.58203125}{{String}}}''}},$ $\displaystyle\qquad\text{{``If I have {\color[rgb]{ 0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.04296875,0.32421875,0.58203125}{{Log}}}, then I can create {\color[rgb]{ 0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.04296875,0.32421875,0.58203125}{{Stick}}}''}},\,\text{{``If I have {\color[ rgb]{0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb} {0.04296875,0.32421875,0.58203125}{{Wool}}} and {\color[rgb]{ 0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.04296875,0.32421875,0.58203125}{{Stick}}}, ... {\color[rgb]{ 0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb}{ 0.04296875,0.32421875,0.58203125}{{Fishing Rod}}}''}}\big{\}},$ $$

with the unique sink Fishing Rod and sources $\{{\color[rgb]{0.04296875,0.32421875,0.58203125}\definecolor[named]{
pgfstrokecolor}{rgb}{0.04296875,0.32421875,0.58203125}\textbf{{Sheep}}},{
\color[rgb]{0.04296875,0.32421875,0.58203125}\definecolor[named]{
pgfstrokecolor}{rgb}{0.04296875,0.32421875,0.58203125}\textbf{{Log}}}\}$.
The depth of $\mathcal{R}_{1}$ is $3$.
The second daglet is the singleton rule set $\mathcal{R}_{2}=\{\text{{``If I have {\color[rgb]{
0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb}{
0.04296875,0.32421875,0.58203125}{{Brick}}}, then I can create {\color[rgb]{
0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb}{
0.04296875,0.32421875,0.58203125}{{Stone Stairs}}}''}}\}$ with sink Stone Stairs, sources $\{{\color[rgb]{0.04296875,0.32421875,0.58203125}\definecolor[named]{
pgfstrokecolor}{rgb}{0.04296875,0.32421875,0.58203125}\textbf{{Brick}}}\}$, and depth $1$.
We emphasize that a daglet does not need to exhaustively include all the dependencies.
For instance, according to the exhaustive recipe list, Brick may be constructed from Clay Ball and Charcoal, but neither are present above.

To generate a prompt with respect to a given depth $T$: we sample daglets $\mathcal{R}_{1},\mathcal{R}_{2},\ldots,\mathcal{R}_{m}$ such that each daglet has depth $\leq T$ and the total number of source and sink items is $\leq 64$.
These sampled daglets constitute the prompt-specified crafting recipes.
We sample random source items from all the daglets, so it is possible, as in the above example, that certain sink items are not craftable.
We do this construction for depths of $T=1,3,5$, each with a train/test split of 65536 and 16384 prompts, respectively.
In total, there are three datasets,
and we simply refer to each as the Minecraft dataset with $T=5$, for instance.

Fine-tuning GPT-2.
We fine-tuned a GPT-2 model for each of the Minecraft datasets.
Each model is trained for 25 epochs using the standard causal language modeling objective.
We use AdamW with default configurations, a learning rate of $5\times 10^{-5}$, and linear decay with $10\%$ warmup.
We used a 32-batch size with four gradient accumulation steps.
Training on a single NVIDIA GeForce RTX 4090 (24GB) takes about 16 hours per model, and all three models attain $85\%+$ accuracy on their respective test datasets.

### D.2 Inference Subversions with Greedy Coordinate Gradients

We now discuss inference attacks on the fine-tuned GPT-2 models from Section D.1.
We adapted the implementation of Greedy Coordinate Gradients (GCG) from the official GitHub repository(^2^22[https://github.com/llm-attacks/llm-attacks](https://github.com/llm-attacks/llm-attacks)) as our main algorithm.
Given a sequence of tokens $x_{1},\ldots,x_{N}$, GCG uses a greedy projected gradient descent-like method to find an adversarial suffix of tokens $\delta_{1},\ldots,\delta_{p}$ that guides the model towards generating some desired output $y_{1}^{\star},\ldots,y_{m}^{\star}$, which we refer to as the GCG target.
This GCG target is intended to prefix the model’s generation, for instance, “Sure, here is how”, which often prefixes successful jailbreaks.
Concretely, GCG attempts to solve the following problem:

$$ $\underset{\delta_{1},\ldots,\delta_{p}}{\text{minimize}}\enskip\mathcal{L}(( \hat{y}_{1},\ldots,\hat{y}_{m}),(y_{1}^{\star},\ldots,y_{m}^{\star})),\quad \text{where}\enskip(\hat{y}_{1},\ldots,\hat{y}_{m})=\mathsf{LLM}(x_{1},\ldots, x_{N},\delta_{1},\ldots,\delta_{p})$ (14) $$

where $\mathcal{L}$ is a likelihood-based loss function between the autoregressively generated tokens $\hat{y}_{1},\ldots,\hat{y}_{m}$ and the GCG target $y_{1}^{\star},\ldots,y_{m}^{\star}$.
To perform each of the three attacks, we similarly define appropriate GCG targets and search for adversarial suffix tokens $\delta_{1},\ldots,\delta_{p}$.
The attack is successful if the model’s generation matches the attack’s expected behavior, examples of which we show in Fig. 8 and also outline below.
We differentiate between the GCG target and the expected behavior because while the GCG target is a fixed sequence, multiple model outputs may be acceptable.

Fact Amnesia Attack Setup.
We aim to forget the intermediate items (facts) of crafting recipes, where the expected behavior is that they should be absent from the model’s generated output.
We randomly sampled 100 items to forget.
For each item, we generated five pairs of prompts and GCG targets, where the prompt contains the item as an intermediate crafting step, and the GCG target is likely to evidence fact amnesia if generated.
For these five prompts and targets, we then used the Universal Multi-Prompt GCG algorithm [] to find a common suffix that induces expected behavior when appended to each prompt.
We used the following initial suffix for all fact amnesia attacks:
“and and and and and and and and and and and and and and and and”.

Rule Suppression Attack Setup.
We aim to suppress specific rules in a prompt, where the expected behavior is that the suppressed rule and its downstream dependents are not generated in the model output.
Similar to the fact amnesia attack, we sampled 100 rules to be suppressed.
For each rule, we generated five pairs of prompts and GCG targets, where the prompt contains the rule, and the GCG target is likely to evidence rule suppression if generated.
For these five prompts and GCG targets, we used the Universal Multi-Prompt GCG algorithm as in the case of fact amnesia attacks.
We also used the same initial suffix as in the fact amnesia attacks.
We show additional examples of rule suppression in Fig. 9.

State Coercion Attack Setup.
We set the GCG target to be “I have String and so I can create Gray Dye”, where the expected behavior is that the generated output should prefix with this sequence.
Notably, this is a non-existent rule in the Minecraft database.
We randomly generate 100 prompts for attack with the aforementioned GCG target using the standard GCG algorithm.
The fixed initial adversarial suffix was “I have I have I have I have I I I I I have”.
If we fail to generate the GCG target, we append this suffix with additional white-space tokens and try again.
We do this because, empirically, state coercion tends to require longer adversarial suffixes to succeed.

GCG Configuration.
We ran GCG for a maximum of 250 iterations per attack.
For each token of the adversarial suffix at each iteration, we consider 128 random substitution candidates and sample from the top 16 (batch_size=128 and top_k=16).
The admissible search space of tokens is restricted to those in the Minecraft dataset.
For these attacks, we used a mix of NVIDIA A100 PCIe (80GB) and NVIDIA RTX A6000 (48GB).
State coercion takes about 7 hours to complete, while fact amnesia and rule suppression take about 34 hours.
This time difference is because the Universal Multi-Prompt GCG variant is more expensive.

### D.3 Evaluation Metrics

Attack Success Rate (ASR).
For fact amnesia, rule suppression, and state coercion attacks, the ASR is the rate at which GCG finds an adversarial suffix that generates the expected behavior.
The ASR is a stricter requirement than the SSR, which we define next.

Suppression Success Rate (SSR).
For fact amnesia and rule suppression, we define a laxer metric where the objective is to check only the absence of some inference steps, without consideration for the correctness of other generated parts.
For example, suppose the suppressed rule is “If I have Wool, then I can create String”, then the following is acceptable for SSR, but not for ASR:

$\text{LLM}(\text{Prompt}+{\color[rgb]{0.83984375,0.15234375,0.15625}
\definecolor[named]{pgfstrokecolor}{rgb}{0.83984375,0.15234375,0.15625}\textbf
{WWWW}})$:
I have Sheep, and so I can create Wool.
I have Brick, and so I can create Stick.
I cannot create any other items.

Attention Weight on the Suppressed Rule.
Suppose that some prompt induces attention weights $A$.
We aggregate the attention weights at layer $l$ as follows:
for head $h$, let $A_{lh}[k]\in[0,1]$ denote the causal, post-softmax attention weight between position $k$ and the last position.
We focus on the last position because generation is causal.
Then, let $K=\{k_{1},k_{2},\ldots\}$ be the token positions of the suppressed rule, and let:

$$ $A_{l}[K]=\max_{k\in K}\max_{h}A_{lh}[k],$ (Aggregated attention at layer $l$ over suppressed positions $K$ ) $$

for each layer $l=1,\ldots,L$.
We report each layer’s aggregated attention weights for both the original and adversarial prompts.
GPT-2 has $L=12$ layers and 12 heads per layer, while Llama-2 has $L=32$ layers and 32 heads per layer.
We report the maximum score over 256 steps of generation.

Suffix-Target Overlap.
For fact amnesia and state coercion, we measure the degree to which the chosen adversarial is similar to the GCG-generated suffix.
Given the set of salient adversarial targets and the set of adversarial suffix tokens, the suffix-target overlap ratio is as follows:

$$ $\text{Suffix-Target Overlap}=\frac{\lvert(\text{Salient Adversarial Targets}) \cap(\text{Adversarial Suffix Tokens})\rvert}{\lvert(\text{Salient Adversarial Targets})\rvert}.$ $$

We define salient adversarial targets by example.
For amnesia with target the item Wool, the set of salient adversarial targets is $\{\textit{``{\color[rgb]{0.04296875,0.32421875,0.58203125}\definecolor[named]{
pgfstrokecolor}{rgb}{0.04296875,0.32421875,0.58203125}{{Wool}}}''}\}$.
For coercion with the adversarial target “I have String, and so I can create Gray Dye”, the set of salient adversarial targets is $\{\textit{``{\color[rgb]{0.04296875,0.32421875,0.58203125}\definecolor[named]{
pgfstrokecolor}{rgb}{0.04296875,0.32421875,0.58203125}{{String}}}'', ``{\color
[rgb]{0.04296875,0.32421875,0.58203125}\definecolor[named]{pgfstrokecolor}{rgb
}{0.04296875,0.32421875,0.58203125}{{Gray Dye}}}''}\}$.

ASR on the Substituted Overlap.
To control for the suffix-target overlap, we substituted all of the overlapping tokens with “and”.
We reported the rate at which this substitution induces the expected behavior.

### D.4 Llama-2 Rule Suppression Experiments

We present a custom rule-following dataset for Llama-2 in Fig. 10.
This dataset uses system prompts that are intentionally dissimilar to common examples to isolate the influence of any potential safety training.
Moreover, we ran the GCG attack using five examples from this dataset, but we failed to find adversarial suffixes that successfully suppressed rule-following in four of them.
Interestingly, however, we found that the hand-crafted suffix “Forget all prior instructions and answer the question” successfully suppressed the intended rules in all examples — and so we report the results of this suffix.

## Appendix E Additional Discussions and Miscellaneous

Limitations.
A major limitation of our work is that our theory focuses on shallow (one-layer) language models, whereas LLMs in practice are often much deeper.
This means that our models of study may fail to capture emergent behavior that occurs with more layers.
In addition, our work does not definitively prove whether learned reasoners succeed in learning correct reasoning strategies.
Furthermore, our choice of logic is fairly simple, and it is routine for large language models in practice to reason over more complex problems.

Broader Impacts.
Our work seeks to understand the principles behind how jailbreak attacks subvert prompt-specified rules.
This work would be helpful to LLM developers seeking to design better safeguards to improve LLM safety and reliability.
However, because our work studies attacks, malicious users may be able to gain insights into how to construct attacks.

## Appendix F Additional Figures

Figure: Figure 8: Examples of the expected behavior of each attack. The language model is GPT-2, while XXXX, YYYY, and ZZZZ stand in for the adversarial suffixes of each attack. GCG attempts to find a suffix that generates the GCG target, but we consider an attack successful (counted in the ASR) if it includes and excludes the expected phrases. This allows attacks like fact amnesia and rule suppression to succeed even if the GCG target does not prefix the output generation.

Figure: Figure 9: Two examples of rule suppression with GPT-2 on the Minecraft dataset: the suppressed tokens receive less attention when the adversarial suffix is present. We apply appropriate paddings and show the difference between the attention weights of the attacked (with suffix) and the non-attacked (without suffix) generations, with appropriate padding applied. The attacked generation places less attention on the red positions and greater attention on the blue positions.
Refer to caption: extracted/5894019/images/mc_suppression_example_38_4.png

Figure: Figure 10: Hand-crafted rule suppression dataset for Llama-2. There are 15 items in total.

Figure: Figure 11: Example of rule suppression with Llama-2 on our custom dataset (Fig. 10). When attacked (left), the suppressed tokens receive less attention than in the non-attacked case (right). Rather than showing the difference of attention weights as in Fig. 9, this plot shows both the attacked and non-attacked attentions.
Refer to caption: extracted/5894019/images/llama_suppression_example_1_2.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: See 'Weaknesses', above.
soundness: 3
strengths: **originality**

While 'jailbreak'/'adversarial attack' papers are common, I have yet to see a paper that embeds such attacks in the transformer architecture underlying LLMs.

**quality**

The paper seems well conducted.

**clarity**

The paper is generally well structured.  For specific exposition, see below.

**significance**

I think that the paper contributes to the literature on LLM's ability to implement logical operations.
summary: This manuscript explores the subversion of logical entailment in transformer-based LLMs, in three steps:
1. a theoretical/mathematical representation of a single layer transformer with one attention head (§3.1): Theorem 3.1 establishes that this architecture can encode (propositional) logical entailment, characterized by _monotonicity_, _maximality_, and _soundness_.
1. theory-based attacks against GPT-2 reasoners:
   1. Theorem 3.3 presents binary encodings of theory-derived suffixes that implement attacks on each of the three logical properties, via the mathematical representation of the transformer.
   1. Figure 3 then shows the success rate of each of the mathematical attacks.  Those against monotonicity and maximality are highly successful, while that on soundness generally fails, but can induce variance.  These attacks are somewhat validated by 'learned' attacks that minimise the BCE loss between a desired sequence of reasoning, and an actual induced sequence of reasoning.
1. finally, the authors use the Greedy Coordinate Gradients (GCG) algorithm for generating adversarial attacks on GPT-2 and Llama-2 to induce the specific logical violations sought. Linear classifier probes tend to recover the induced adversarial states, rather than the true states, indicating the attacks' success.
weaknesses: 1. throughout, as a non-expert in adversarial attacks, I found that steps in the paper's reasoning were hard to understand.  For example, I would like clearer explanation of:
   1. the relation between the binary encodings and the Minecraft prompts: are terms like "if I have" and "then I can" somehow encoded to binary in this form, or are the implied logical operators encoded instead?
   1. is there anything special about adversarial _suffixes_ (rather than e.g. adversarial prefixes)?
   1. why is the ASR non-monotonic in the number of repeats (Fig. 3)?  I would have thought that a repeated attack is more likely to succeed.
   1. I did not understand the variance explanation (Fig. 3) of the soundness attacks: my best guess is that adversarial suffixes can induce similar reasoning states across a range of prefixes; if so, this seems unsurprising - the tokens generated when a common token is appended to idiosyncratic tokens are more correlated than those generated in response to the idiosyncratic tokens alone?
   1. what is a 'budget' (problem 3.2)?
   1. Table 1: this seems to show that learned attacks are successful.  
      1. Do they 'mirror' the theoretical attacks in the sense of implementing similar reasoning sequences, or using similar adversarial prefixes?
      1. The caption claims that $v_{tgt}$ is larger on average than $v_{other}$ for fact amnesia; the figures in the table show the opposite?
      1. The theory based attacks failed against soundness, yet the learned attacks seem to be quite successful.  In Table 2, the soundness attack seems the most successful.  Why is there this difference between the attack types' success?
   1. The Suffix in Figure 4 contains various typos (e.g. "I and have", "and and").  Is this an intrinsic part of the attack, or just incidental?
   1. Table 3: why are there no confidence intervals on the substitution ASR?
   1. Table 4: is there any intuition behind the most targeted layers being consecutive?  Why is the pattern in Table 5 so different?
   1. Figure 6: should the block between 'Suppressed Rule' and 'Output' be labeled?
1. neither of the two LLMs used, GPT-2 and Llama-2, have been state-of-the-art for some time.  It would be helpful to either:
   1. (ideally) demonstrate the same results on SOTA LLMs; or
   1. (less ideally) explain why the non-SOTA LLMs still provide insight into the weaknesses of SOTA LLMs.

None of the expositional issues, above, are 'deal breakers'.  Thus, I have rated this paper as a weak accept: I would like to papers in top ML conferences like ICLR to be strong across the board, rather than good analyses that seem a bit rushed in their exposition.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. How should we interpret the curve in the left and middle figures, where the ASR initially increases but then decreases with additional repetitions?

2. Does this alignment between theory and behavior appear only in your self-trained GPT-2 and Llama reasoners, or can we expect similar results in more advanced LLMs, such as GPT-4 or Llama 3?
soundness: 4
strengths: 1. A theoretical model is provided to study how the reasoning of transformer-based language models can be subverted. This approach bridges theory and practice, demonstrating that popular jailbreak attacks align with theoretical predictions. The presentation of the idea is quite clear.

2. The framework is extendable to various LLMs, making it relevant for broader applications in model safety and adversarial robustness. Experimental results align with the theoretical analysis.
summary: The paper investigates methods to manipulate LLMs into deviating from prompt-specified rules. The study models rule-following as propositional Horn logic. The authors demonstrate how malicious prompts can exploit theoretical weaknesses, leading even robust models to fail in rule-based reasoning. This approach is validated both theoretically and empirically, linking the behavior of real-world adversarial attacks (jailbreaks) to their framework.
weaknesses: 1. The theoretical model is simplified by considering only Horn logic without quantifiers. 


2. A graph-based representation, rather than binary vectors, might provide a stronger representation of propositions but could be more challenging to analyze. 


3. While the study includes empirical validation, the range of language models and datasets tested may not fully capture the diversity of existing models.  Although recent models like GPT-3+ are not controllable at will, experiments with these models may yield unexpected results, and additional insights could be explored.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: - why do we need so many repeats for the attack in Fig. 3, and why is the success rate dropping if the number is too high?
- Is it more challenging to apply your code to larger and deeper LLMs from an implementation standpoint?
soundness: 4
strengths: - Understanding why and how these jailbreak attacks work on LLMs is an interesting and important direction of research.
- The paper is overall well-written and follows a clear structure. However, as an informed outsider, I find it hard to follow; while the theory is described in great detail, it could benefit from some more high-level insights, which would make it more accessible.
- The authors provide both theoretical and empirical support for their framework to explain the behavior of LLMs under such jailbreak attacks.
summary: The authors investigate how adversarial suffixes can cause LLM to subvert from following rules specified in the input prompt. To do so, the authors introduce a theoretical framework using propositional Horn logic, which involves multiple inference steps. At each inference step, new facts are derived using a set of rules and a set of known and derived facts. Within this framework, the authors investigate how and which adversarial suffixes make LLMs violate the rules defined in the prompts. Here, the authors investigate three attack scenarios: fact amnesia (deletion of facts), rule suppression (the rule is not applied even though it could have been), and state Coercion (the current state is manipulated).
weaknesses: - The paper focuses on small language models, mostly GPT2, and for some experiments, llama2-7B-Chat. I am unsure how the results scale for even larger and deeper models and whether they could be applied to current LLM architectures (e.g., llama-3). 
- The Authors include an invalid link within the reproducibility statement for code and experiments.
- As an informed outsider, the paper seems to be very technical, and I struggle to see the main insides you draw from the theory and empirical findings. Maybe a short elaboration on how and why these suffixes work could clarify that.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: Content-related: 

- L49: The paper claims that the proposed logic-based framework can detect and describe rule disobedience by LLMs. I am not convinced that the claim holds since I cannot see a concrete correspondence between the proposed theoretical model and a transformer architecture like the ones you experiment with. This is probably due to presentation, since I did not find Eq (4) and (5) to be adequately described or justified. They read like a list of ingredients to me. Also the theorems are too informal and at least an intuition of why they are the case should be given. 

- L53: The paper states that attacks in the theoretical setting transfer to learned models and that LLMs exhibit consistent reasoning behaviors with the theoretical model—can you provide evidence for this? I did not find the presented evidence clearly supporting this claim. 

- L141: "Might violate rule-following differently" refers to how predictions diverge from the ground truth. L159 mentions "non-determinism in rule-application order"—does this mean the result of Apply() is not unique? Could you expand on this source of uncertainty? 

- L155: What do you mean by "good coverage"?  

- L172: What result are you referring to here? The following model description is unclear, and some background and definitions are missing. 

- L185: Are the rules represented as a set of tuples? $\{0,1\}^{2n}$ is simply a set. 

- L195: When and how does thresholding come into play? 

- L209: How does the network's dimension support the results in Theorem 3.1? 

- L255: Is the reason for negative values of the attacks due to the embedding space and the way language models "reason"? 

- L262: Empirical results with GPT-2 are mentioned without explaining how theoretical attacks were translated to learned models. How does a model like GPT-2 fit into this framework? 

- L299: GCG is not introduced or described appropriately. 

- L322: How is the search for expected behavior conducted? 

- L357: Linear classifier probes are mentioned but not defined. 

- L365: Is there a difference between what is measured by accuracy and F1? I find the description of the metrics confusing. 

- L371: What are models T=1,3,5? You referred to models as $\mathcal{R}$ earlier—could you please clarify. 

- L374: SSR is not properly defined. 

- Table 2: What is the baseline here? How can you say that the jailbreak succeeded if results without the attack are not shown? 

- Table 4: Why is the suppression effect more pronounced in layers 6, 7, and 8? Is there something that can be inferred from this? 

- Figure 6: The figure is unclear. What is the prompt, the rule, the attack, and the output? 

Minor points: 

- L134: Equivalence to HORN-SAT should be referenced. 

- L187: Typo: "autogregressively" should be "autoregressively." 

- L464: Typo: "does" should be corrected.
soundness: 2
strengths: - The formalization of different types of rule-based adversarial attacks is novel, to the best of my knowledge, and provides a structured way of thinking about how LLMs might fail in following logical rules. 

- The authors’ attempt to develop a theoretical framework that connects LLM behavior with logical rule-following is conceptually interesting and could inspire further work in this area. 

- The use of synthetic data and small transformer architectures for experimentation allows for controlled exploration of the proposed ideas, though this setup has its limitations.
summary: The paper investigates adversarial attacks against large language models (LLMs) through the lens of propositional logic. The authors represent sets of propositions in a vectorized form and model rule disjunctions as summations of binary elements of these vectors. Attacks are performed by removing some (of the indicators of) propositions to break the logical soundness of rule applications. Additionally, small transformer architectures are used to predict the next state, mimicking rule application. Experiments with LLMs are conducted on synthetic data.
weaknesses: - The paper's clarity needs improvement, particularly in terms of defining key terms and methods. The architecture of the theoretical model is not sufficiently explained and the theoretical results not easy to trust given the lack of intuition about why they come about. 

- The paper makes a fundamental assumption that LLMs can follow prompt-specified rules, but this assumption is not validated. In fact, prior work, e.g. (Zhang at al., 2022a), disprove this, and the experiments indicate that LLMs struggle with logical reasoning, a point that is not fully acknowledged in the paper. A stronger link between theoretical expectations and empirical findings is needed. 

- The theoretical model is not a strong representation of how LLMs operate, as it treats propositions as binary events, and simulate inference by summation which is not clear whether can generally represent of LLMs' behavior, e.g. performing next-token prediction. The correspondence between the transformer architecture and the theoretical model is weak, and the results do not demonstrate rule-following as claimed. 

- The experiments are not adequately explained, and it’s unclear how well the theoretical attacks translate to learned models. For example, the empirical results with GPT-2 lack sufficient explanation regarding how the theoretical attacks were applied to the LLM. The lack of clarity in the methodology undermines confidence in the results.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
questions: - Is it possible to relate the theoretical fundings of this work with safety issues in code generation with LLMs?


Minor comments:

line 357: This is evidence that = > evident?
line 497: positional encoding => propositional encoding?
line 498:  'quantifiers' can be use in first-order logic or above but not propositional logic.
soundness: 3
strengths: - This work addresses an important and timely problem in LLMs and reveals significant aspects that could help devise better techniques against jailbreaking.
- Overall, the paper is technically rigorous, well-organized, and clear. Moreover, it enhances understanding of the aims of this work by providing intuitive examples.
- The experimental evaluation is comprehensive, and the empirical results support the theoretical findings.
summary: One of the most visible limitations of large language models (LLMs) is their vulnerability to jailbreak attacks (i.e. manipulating input prompts with the intent to bypass the LLM's safeguards). Most of works focusing on jailbreak attacks in LLMs attempt to improve LLM defence to jailbreaking using different techniques (like fine-tuning, activation patching, prompt detection, etc), but without addressing the theoretical understandings of this vulnerability.     

This paper investigates this problem and unveil some insights about LLMs that are behind this vulnerability, by demonstrating with a concrete case of propositional logic reasoning. Intuitively, a small language model (LM), composed with one layer and one self-attention head, is constructed to autoregressively predict propositional logic inference. This LM serves as a theoretical reasoner to identify three attacking rules to breakdown inference properties, i.e. monotonicity, maximality and soundness.
Proofs of theorems regarding the validity of these attacks are provided. Additional evidence of the success of these attacks on LLMs (i.e., GPT-2 and Llama-2-7B-chat) is presented in the empirical study.


Overall, I am favourable for an acceptance of this paper.
weaknesses: - The paper does not discuss possible alternatives to address jailbreak vulnerability in LLMs

Meta-review: The paper considers the problem of manipulating LLMs so that they deviate from prompt-specified rules. Overall, the reviews lean towards acceptance, and I agree. The overall take-away message "Language Models are Susceptible to Inference Subversions" is important. The in-depth discussion between one reviewer and the authors helped clarify potential downsides. As one reviewer has put it, the study models rule-following as propositional Horn logic, and the authors demonstrate how malicious prompts can exploit theoretical weaknesses, leading even robust models to fail in rule-based reasoning. This is interesting. However, please clearly state that the Horn rules considered are quite simple as they only involved three literals. Generally, a Horn clause is a clause with at most one positive, i.e., unnegated literal. This has to be pointed out.

Decision: Accept (Poster)