You need at least two attention heads to do XOR, and we will find that it is a surprisingly crisp result which uses only a few lines of algebra.

Introduction

A single attention head can already do Boolean operations like OR and AND on two input bits, but it cannot do XOR^[1]. We will show this using the setup outlined in the above figure: by checking if there exists a logistic regression probe on the internal activations of the query token = to predict^[2] .

Since the skip connection is constant across all , it can be absorbed into the threshold , so the probe logit depends only on the attention update :

If the probe correctly classifies XOR, then it must satisfy



More explicitly, the above equation can be written as:

The key fact is that in the single-head setting, for every choice of probe , there exist positive numbers such that

But this is impossible under the inequalities above: since each is positive, we would have

contradicting the equality. So a single attention head cannot linearly separate XOR.

However, two heads are enough. Conceptually, one head detects 0 and the other detects 1. On the mixed inputs 01 and 10, both heads contribute; on 00 and 11, only one of them does. A linear readout can then separate the mixed cases from the same-bit ones.

This means you need at least two attention heads to do XOR.^[3]

Setup

We work with sequences of length 3 over the vocabulary . On input , the model sees the sequence .

The = token's residual stream after the attention head has two parts: the skip connection (its original embedding) and the attention update (the new information it gathered by attending to and ):

Since doesn't depend on the input bits at all, any probe can fold it into its threshold . So the only thing that matters for classification is the attention update .

Let denote the value vector at position . The attention update is then a convex combination of these value vectors, weighted by the attention probabilities :

The attention probabilities are the softmax of the raw attention logits , which measure how strongly the = token's query matches each key:

resulting in the following attention weights:

So we can equivalently write the attention update directly in terms of the 's:

We now ask: can a hyperplane separate the four attention outputs into the XOR classes?

One attention head cannot do XOR

Here we are going to work towards a short proof why a single attention head cannot do XOR.

The key identities

In the setup section, we saw that the attention update takes the form



where and . Note that , since it will turn out useful later.

The key structural fact is that and each split into an -only term, a -only term, and a constant:

Because of this, summing over the main diagonal versus the off-diagonal yields identical totals — in both cases you collect exactly one copy each of the and contributions, and one copy each of the and contributions. This gives the key identities:

Proof by contradiction

Suppose there exists a probe that correctly classifies XOR. This means:

so the probe scores must satisfy the XOR sign pattern:

Let's define the denominator-weighted probe score :

Since , the XOR sign pattern on the probe scores carries over to :

Because is linear in and , the key identities pass straight through to :

But the XOR sign pattern forces and , which contradicts the equality above.

Conclusion. A single attention head with a linear readout cannot compute XOR.

Two heads can do XOR

Now we switch from one head to two parallel heads. For the existence proof, it is enough to write the residual update as the sum of the two head outputs:

where

The idea is simple:

• Head 0 softly detects token 0 and writes in one direction;
• Head 1 softly detects token 1 and writes in an orthogonal direction.

Then the mixed inputs 01 and 10 are exactly the cases where both heads contribute.

An explicit construction

Let's work in , with no positional embeddings, and choose the token embeddings as follows:

We choose the query, key, value and output matrices for each head as shown below, along with the resulting attention scores and weights from the = query position.

The construction is symmetric by design:

• Head 0 attends preferentially to token 0 and writes in the direction
• Head 1 attends preferentially to token 1 and writes in the direction

Each entry^[6] is the triplet of softmax attention weights that the = query assigns to positions respectively, for that head and input. The weights are non-negative and sum to 1.

We can now compute the attention update from each head across all four inputs.

The same-bit inputs and each activate only one head, while the mixed inputs and activate both heads equally. The mixed inputs therefore have a strictly larger total activation, which a linear readout can exploit.

Choosing , the probe score takes only two distinct values:

The mixed inputs score strictly higher, so any threshold together with correctly classifies XOR.

Conclusion. Two attention heads are sufficient to compute XOR with a linear readout.

Takeaway

The single-head impossibility comes down to a structural constraint. Once you weight the probe score by the attention denominator , the result

always decomposes as , an additive table with no interaction between and . Since , and the probe score share the same sign, so this additive structure is the true obstruction. XOR requires the checkerboard sign pattern, i.e. firing on the off-diagonal, not on the diagonal, which no additive table can realize.

Two heads fix this by providing two independent soft detectors. The mixed inputs and are the only cases where both detectors fire at once, creating a gap in the probe scores that a linear readout can exploit.

In a single-layer, attention-only model with a linear readout from the query position, we saw that

• 1 head is not enough for any choice of dimension, embeddings, positional embeddings, or linear readout.
• 2 heads are enough, via the explicit construction above.

Together, these establish that two attention heads are necessary and sufficient to compute XOR with a logistic regression probe.

1. ^{^}

   
   
   XOR is denoted by in equations.
   

2. ^{^}

   This is used to classify just four points. 00 and 11 map to 0 whereas 01 and 10 map to 1.

3. ^{^}

   Throughout this post, the model is attention-only: there are no MLPs, layer norms, or bias terms. Adding an MLP after the attention layer could solve XOR with a single head, since the MLP can implement the needed nonlinearity on its own.

4. ^{^}

   To clarify, it performs these operations independently (either OR or AND), not simultaneously

5. ^{^}

   For example, this can be done by using a value matrix that is "parallel" to e(1) and "orthogonal" to e(0).

6. ^{^}

   The entries involve because each attention score is either 0 or 1, so the softmax exponentiates to either or .