Preisach Attention: A Hysteretic Model of Sequential Memory

Piotr Frydrych
The Metrology and Biomedical Engineering Institute
Faculty of Mechatronics, Warsaw University of Technology
piotr.frydrych@pw.edu.pl

Abstract

We introduce the Preisach Attention Layer (PAL), a novel sequence modelling architecture grounded in the classical Preisach hysteresis operator from mathematical physics. PAL replaces the softmax attention mechanism with a binary relay operator $\hat{\gamma}_{\alpha\beta}$ parameterised by learned activation and deactivation thresholds $(\alpha,\beta)$ , maintaining a stack of local extrema as its internal state. A single-layer PAL-Transformer with $O(1)$ depth is Turing-complete under arbitrary precision arithmetic, achievable through simulation of a two-stack pushdown automaton — in contrast to the $O(\log n)$ depth required by standard hard-attention transformers (Pérez et al., 2021). Second, we prove that the function classes computable by PAL and by the transformer are incomparable: PAL computes historical range statistics in $O(1)$ layers that require $O(\log n)$ layers for transformers, while transformers support random-access retrieval that PAL cannot perform without auxiliary state. The separating property is rate-independence — PAL responds only to the sequence of local extrema, not to absolute token positions or temporal spacing. Third, we show that the extremum stack constitutes a minimal sufficient statistic of the input history for all rate-independent functionals, providing a formal analogue of the wiping property in classical hysteresis theory. PAL is thus an efficient architecture for tasks with long episodic memory and weak positional dependence, with $O(n\log n)$ total inference cost versus $O(n^{2})$ for standard attention.

Keywords: Preisach operator, hysteresis, attention mechanism, Turing completeness, expressiveness, sequence modelling, long-range dependence, rate-independence.

1 Introduction

The transformer architecture (Vaswani et al., 2017) and its attention mechanism have become the dominant paradigm for sequence modelling. Theoretical analysis of transformer expressiveness has established that hard-attention transformers are Turing-complete (Pérez et al., 2021), that softmax attention corresponds to specific fragments of first-order logic (Hahn, 2020; Barceló et al., 2020), and that practical transformers implement approximate versions of classical algorithms (Akyürek et al., 2023; von Oswald et al., 2023).

A parallel body of work has studied alternative sequence models — recurrent networks (Siegelmann and Sontag, 1995), state space models (Gu and Dao, 2023), and mixture-of-experts architectures (Shazeer et al., 2017) — seeking more efficient representations of long-range dependence. These efforts share a common limitation: their memory mechanisms are either temporal (decaying by distance) or positional (indexed by token location), with no mechanism for value-based memory that persists based on the significance of past inputs rather than their recency.

This paper.

We propose a fundamentally different memory mechanism inspired by the Preisach hysteresis operator (Preisach, 1935), a classical model from mathematical physics used to describe ferromagnetic materials, elastoplastic systems, and — more recently — agent-based financial markets (Frydrych and Szewczyk, 2014; Frydrych, 2019). The Preisach operator aggregates the outputs of binary relays $\hat{\gamma}_{\alpha\beta}$ , each characterised by an activation threshold $\alpha$ and a deactivation threshold $\beta$ , weighted by a learned measure $\mu(\alpha,\beta)$ over the threshold plane.

The key structural properties of the Preisach operator that motivate its use in sequence modelling are:

1.

Rate-independence: the output depends only on the sequence of local extrema of the input, not on temporal spacing or absolute position.
2.

Wiping property: a new extremum erases all previous extrema of smaller magnitude, providing a natural forgetting mechanism based on significance rather than recency.
3.

Extremum stack sufficiency: the stack of alternating local maxima and minima is a minimal sufficient statistic of input history for all rate-independent functionals.
4.

Universal approximation: the class of Preisach operators with $\mu\in L^{2}(\mathcal{T})$ is dense in the space of all continuous, causal, rate-independent functionals (Mayergoyz, 1991).

Main contributions.

1.

We define the Preisach Attention Layer (PAL) and its multi-head variant (MPAL), giving exact computational definitions and connecting them to the classical Preisach operator (section˜3).
2.

We prove that a single-layer PAL-Transformer is Turing-complete (section˜4), establishing Turing completeness at depth $O(1)$ — lower than the $O(\log n)$ depth of Pérez et al. (2021).
3.

We prove a formal expressiveness separation between PAL and transformer attention (section˜5), identifying rate-independence as the separating property.
4.

We characterise the function class of PAL through its connection to rate-independent operators and provide a logical characterisation analogous to Barceló et al. (2020) (section˜6).
5.

We outline computational complexity advantages of PAL and identify task classes where PAL is predicted to outperform standard attention (section˜7).

Section˜2 reviews background; section˜3 defines PAL; section˜4–6 contain the main proofs; section˜7 analyses computational complexity; sections˜8 and 10 discuss related work and conclude.

2 Background

2.1 The Preisach Hysteresis Operator

The Preisach operator (Preisach, 1935) was introduced to model magnetic hysteresis in ferromagnetic materials. Let $\mathcal{T}=\{(\alpha,\beta)\in\mathbb{R}^{2}:\alpha\geq\beta\}$ be the Preisach half-plane.

Definition 2.1 (Elementary relay).

For $(\alpha,\beta)\in\mathcal{T}$ and input sequence $u=(u_{0},u_{1},\ldots)\in\mathbb{R}^{\mathbb{N}}$ , the elementary relay $\hat{\gamma}_{\alpha\beta}[u]:\mathbb{N}\to\{0,1\}$ is defined by:

\hat{\gamma}_{\alpha\beta}[u](n)=\begin{cases}1&\text{if }u_{n}\geq\alpha,\\ 0&\text{if }u_{n}\leq\beta,\\ \hat{\gamma}_{\alpha\beta}[u](n-1)&\text{otherwise.}\end{cases}

(1)

The interval $(\beta,\alpha)$ is the dead band of the relay.

Definition 2.2 (Preisach operator).

Let $\mu\in L^{1}(\mathcal{T})$ be a signed measure on $\mathcal{T}$ . The Preisach operator $\mathcal{P}_{\mu}:\mathbb{R}^{\mathbb{N}}\to\mathbb{R}^{\mathbb{N}}$ is:

\mathcal{P}_{\mu}[u](n)=\iint_{\mathcal{T}}\hat{\gamma}_{\alpha\beta}[u](n)\;\mu(\alpha,\beta)\,d\alpha\,d\beta.

(2)

The Preisach operator has three properties central to this paper.

Proposition 2.3 (Rate-independence (Brokate and Sprekels, 1996)).

For any non-decreasing bijection $\phi:[0,T]\to[0,T]$ , $\mathcal{P}_{\mu}[u\circ\phi]=\mathcal{P}_{\mu}[u]\circ\phi$ .

Proposition 2.4 (Wiping property (Mayergoyz, 1991)).

Let $M_{i}>m_{i}>M_{i+1}>m_{i+1}>\ldots$ be the alternating local maxima and minima of $u$ . If $M_{i+1}>M_{i}$ , then the relay state induced by $M_{i}$ is erased — the output $\mathcal{P}_{\mu}[u]$ after $M_{i+1}$ is identical to what it would be had $M_{i}$ not occurred.

Proposition 2.5 (Universal approximation (Mayergoyz, 1991)).

The set $\{\mathcal{P}_{\mu}:\mu\in L^{2}(\mathcal{T})\}$ is dense in the space of all continuous, causal, rate-independent functionals on $C([0,T])$ under the uniform topology.

2.2 The Extremum Stack

A fundamental algorithmic consequence of the wiping property is that the Preisach output depends only on the current extremum stack:

Definition 2.6 (Extremum stack).

The extremum stack of $u_{0:n}$ is the sequence:

\Pi_{n}=[(M_{1},m_{1}),(M_{2},m_{2}),\ldots,(M_{k},m_{k})]

(3)

of alternating local maxima $M_{1}>M_{2}>\ldots>M_{k}$ and local minima $m_{1}>m_{2}>\ldots>m_{k}$ , stored in decreasing order, where the pair $(M_{i},m_{i})$ records the $i$ -th local maximum and its subsequent local minimum.

Proposition 2.7 (Stack sufficiency).

$\mathcal{P}_{\mu}[u](n)$ is a measurable function of $\Pi_{n}$ alone. In particular, two sequences $u$ and $v$ with identical extremum stacks $\Pi_{n}^{u}=\Pi_{n}^{v}$ satisfy $\mathcal{P}_{\mu}[u](n)=\mathcal{P}_{\mu}[v](n)$ for all $\mu$ .

Algorithm 1 Extremum Stack Update

1:Current stack

\Pi_{n}

, new observation

u_{n+1}

, previous observation

u_{n}

2:Updated stack

\Pi_{n+1}

3:if

u_{n+1}>u_{n}

then

\triangleright

Input rises: update maxima

4: while

\Pi_{n}\neq\emptyset

and

M_{\mathrm{top}}<u_{n+1}

m_{\mathrm{last}}\leftarrow m_{\mathrm{top}}

\triangleright

Save last minimum before popping

\mathrm{pop}(\Pi_{n})

\triangleright

Wiping

7: end while

\mathrm{push}(\Pi_{n},(u_{n+1},m_{\mathrm{last}}))

\triangleright

New maximum with last surviving minimum

9:else if

u_{n+1}<u_{n}

then

\triangleright

Input falls: update minima

10: while

\Pi_{n}\neq\emptyset

and

m_{\mathrm{top}}>u_{n+1}

11:

M_{\mathrm{last}}\leftarrow M_{\mathrm{top}}

\triangleright

Save last maximum before popping

12:

\mathrm{pop}(\Pi_{n})

\triangleright

Wiping

13: end while

14:

\mathrm{push}(\Pi_{n},(M_{\mathrm{last}},u_{n+1}))

\triangleright

New minimum with last surviving maximum

15:end if

16:return

\Pi_{n+1}\leftarrow\Pi_{n}

Proposition 2.8 (Stack update complexity).

Algorithm˜1 runs in amortised $O(1)$ time per step — each element is pushed and popped at most once — and requires $O(k)$ space where $k\leq n$ is the current stack depth. The relay state $\hat{\gamma}_{\alpha\beta}[u](n)$ can be read from $\Pi_{n}$ in $O(\log k)$ time by binary search.

2.3 Transformer Attention

For completeness we recall standard definitions. Given query $q\in\mathbb{R}^{d}$ , keys $K\in\mathbb{R}^{n\times d}$ and values $V\in\mathbb{R}^{n\times d}$ , scaled dot-product attention is:

\operatorname{Attn}(q,K,V)=\mathrm{softmax}\!\left(\frac{qK^{\top}}{\sqrt{d}}\right)V.

(4)

Hard attention replaces softmax with argmax: $a_{j}=\mathbf{1}[j=\operatorname*{arg\,max}_{i}q\cdot k_{i}]$ .

We use the transformer model of Pérez et al. (2021): an $L$ -layer encoder-decoder with hard attention, sinusoidal position encoding, layer normalisation, and residual connections.

3 Preisach Attention Layer

3.1 Definition

Definition 3.1 (Preisach Attention Layer).

Let $u_{0:n}\in\mathbb{R}^{n+1}$ be a scalar input sequence and $\mu=\{\mu_{ij}\}_{i\geq j}\in\mathbb{R}^{L\times L}$ a discretised measure on the grid $\mathcal{G}_{L}=\{(\alpha_{i},\beta_{j}):i\geq j,\,i,j\in\{1,\ldots,L\}\}$ with $\alpha_{i}=i\Delta$ , $\beta_{j}=j\Delta$ . The Preisach Attention Layer is:

\operatorname{PAL}_{\mu}(u_{0:n})=\sum_{i\geq j}\mu_{ij}\cdot\hat{\gamma}_{\alpha_{i}\beta_{j}}[u](n)\in\mathbb{R}.

(5)

Definition 3.2 (Multi-head PAL).

Let $x_{0:n}\in\mathbb{R}^{(n+1)\times d}$ be a vector-valued sequence. Multi-head PAL with $H$ heads is:

\operatorname{MPAL}(x_{0:n})=\sum_{h=1}^{H}W_{O}^{(h)}\cdot\operatorname{PAL}_{\mu^{(h)}}\!\left(W_{I}^{(h)}x_{0:n}\right)\in\mathbb{R}^{d},

(6)

where $W_{I}^{(h)}\in\mathbb{R}^{1\times d}$ projects to a scalar signal and $W_{O}^{(h)}\in\mathbb{R}^{d}$ projects back to the model dimension. The scalar projection is a simplifying assumption of the present work; Section 10 discusses the vector extension (vPAL) where $W_{I}^{(h)}\in\mathbb{R}^{2\times d}$ and the measure $\mu$ is defined over the three-dimensional space $(\alpha,\beta,\theta)$ following Frydrych (2019).

Definition 3.3 (PAL-Transformer).

An $L$ -layer PAL-Transformer is defined by:

$\displaystyle z_{n}^{(0)}$	$\displaystyle=x_{n}+\mathrm{PE}(n),$	(7)
$\displaystyle z_{n}^{(l)}$	$\displaystyle=\mathrm{LN}\!\left(z_{n}^{(l-1)}+\operatorname{MPAL}^{(l)}(z_{0:n}^{(l-1)})\right),$	(8)
$\displaystyle z_{n}^{(l)}$	$\displaystyle=\mathrm{LN}\!\left(z_{n}^{(l)}+\mathrm{MLP}^{(l)}(z_{n}^{(l)})\right),$	(9)

where $\mathrm{PE}$ is sinusoidal position encoding, $\mathrm{LN}$ is layer normalisation, and $\mathrm{MLP}^{(l)}$ is a two-layer network with ReLU.

3.2 Connection to Classical Preisach Operator

Proposition 3.4 (PAL as discretised Preisach).

$\operatorname{PAL}_{\mu}(u_{0:n})$ is the discretised Preisach operator $\mathcal{P}_{\mu_{\Delta}}[u](n)$ where $\mu_{\Delta}=\sum_{i\geq j}\mu_{ij}\delta_{(\alpha_{i},\beta_{j})}$ is an atomic measure concentrated on the grid $\mathcal{G}_{L}$ . As $L\to\infty$ and $\Delta\to 0$ with $L\Delta=C$ fixed, $\operatorname{PAL}_{\mu}\to\mathcal{P}_{\mu}$ uniformly on $C([0,C])$ by proposition˜2.5.

3.3 Relationship to Standard Attention

Proposition 3.5 (Attention as continuous relaxation of PAL).

Standard softmax attention (4) is a continuous relaxation of PAL in which:

1.

The binary relay $\hat{\gamma}_{\alpha\beta}[u](n)\in\{0,1\}$ is replaced by the soft weight $a_{j}=\mathrm{softmax}(q\cdot k_{j}/\sqrt{d})\in(0,1)$ ,
2.

The measure $\mu(\alpha,\beta)$ is replaced by the value matrix $V$ ,
3.

Rate-independence is broken: attention depends on absolute position through $q\cdot k_{j}$ , while PAL depends only on the sequence of extrema.

4 Turing Completeness

We prove that a single-layer PAL-Transformer is Turing-complete by showing it can simulate an arbitrary two-stack pushdown automaton (2-PDA), which is known to be equivalent to a Turing machine (Hopcroft and Ullman, 1979).

4.1 Encoding Alphabet Symbols in the Extremum Stack

Definition 4.1 (Cantor-depth encoding).

Let $\Gamma=\{a_{1},\ldots,a_{k}\}$ be a stack alphabet, $D_{\max}$ a depth bound, $\Delta>0$ a resolution parameter, and $C_{\max}=D_{\max}(k+1)\Delta$ . The Cantor-depth encoding is:

\mathrm{code}^{*}(a_{i},d)=C_{\max}-[d(k+1)+i]\Delta,\quad i\in\{1,\ldots,k\},\;d\in\{0,\ldots,D_{\max}\}.

(10)

Lemma 4.2 (Strict monotonicity).

For all $i,i^{\prime}\in\{1,\ldots,k\}$ and $d\geq 0$ : $\mathrm{code}^{*}(a_{i^{\prime}},d+1)<\mathrm{code}^{*}(a_{i},d)$ .

Proof.

$\mathrm{code}^{*}(a_{i},d)-\mathrm{code}^{*}(a_{i^{\prime}},d+1)=[(d+1)(k+1)+i^{\prime}-d(k+1)-i]\Delta=[(k+1)+i^{\prime}-i]\Delta\geq[(k+1)-k]\Delta=\Delta>0$ . ∎

Lemma 4.3 (Stack operations via signal generation).

Under encoding (10), the three stack operations are realised by the following signal emissions, without triggering the wiping property erroneously:

$\displaystyle\mathrm{PUSH}(a_{i})\colon\quad$	$\displaystyle u_{n+1}=\mathrm{code}^{}(a_{i},d+1)+\varepsilon,\quad u_{n+2}=\mathrm{code}^{}(a_{i},d+1)-\varepsilon,$	(11)
$\displaystyle\mathrm{POP}\colon\quad$	$\displaystyle u_{n+1}=M_{\mathrm{top}-1}+2\varepsilon,$	(12)
$\displaystyle\mathrm{TOP}\colon\quad$	$\displaystyle\text{read }a_{i}=\operatorname{Dec}(M_{\mathrm{top}}),\quad\text{no signal emitted.}$	(13)

Proof.

PUSH: By lemma˜4.2, $\mathrm{code}^{*}(a_{i},d+1)<\mathrm{code}^{*}(a_{j},d)=M_{\mathrm{top}}$ for all $j$ , so $u_{n+1}=\mathrm{code}^{*}(a_{i},d+1)+\varepsilon<M_{\mathrm{top}}$ . The wiping condition ( $u_{n+1}>M_{\mathrm{top}}$ ) is not triggered; a new pair $(M_{d+1},m_{d+1})$ is added to the stack top.

POP: Since $M_{\mathrm{top}-1}>M_{\mathrm{top}}$ (strict monotonicity of stack), $u_{n+1}>M_{\mathrm{top}}$ triggers wiping, removing $(M_{\mathrm{top}},m_{\mathrm{top}})$ . The signal $u_{n+1}$ itself satisfies $u_{n+1}=M_{\mathrm{top}-1}+2\varepsilon<M_{\mathrm{top}-2}$ (if depth $\geq 3$ ), so only one pair is removed.

TOP: $\operatorname{Dec}(M_{\mathrm{top}})=a_{i}$ where $i=\lfloor(C_{\max}-M_{\mathrm{top}})/\Delta\rfloor\mod(k+1)$ , which is a deterministic function of $M_{\mathrm{top}}$ computable by an MLP. ∎

4.2 Main Theorem

Definition 4.4 (Autoregressive PAL-Transformer).

The Turing-completeness result of theorem˜4.6 is stated for the autoregressive (closed-loop) operational regime of the PAL-Transformer, distinct from the parallel encoder of definition˜3.3. In the autoregressive regime:

1.

At step $n$ , the PAL-Transformer receives the current input token $x_{n}$ (which may itself be a function of previous outputs) and produces output $z_{n}$ .
2.

A component of $z_{n}$ — specifically, the signal channels $u^{(1:4)}_{n+1}$ — is appended as the next input token $x_{n+1}$ , creating a closed generative loop.
3.

The extremum stacks $\Pi^{(1:4)}_{n}$ persist across steps as the sole recurrent state; no other hidden state is maintained.

This regime corresponds to standard autoregressive language model inference. The result is a generation theorem (unbounded computation traces can be produced), not merely a verification theorem (pre-encoded traces classified). The parallel encoder definition (definition˜3.3) is used for training and for the expressiveness results of section˜5, where the full input sequence is available.

Lemma 4.5 (Multi-head PAL decodes the extremum stack).

For any extremum stack $\Pi_{n}$ of depth at most $k$ over a discretised alphabet of size $K=(k+1)|\Gamma|$ , there exist measures $\mu^{(1)},\ldots,\mu^{(H)}$ with $H=\lceil\log_{2}K\rceil$ heads such that the map

\phi:\Pi_{n}\;\mapsto\;\bigl(\operatorname{PAL}_{\mu^{(1)}}(u_{0:n}),\ldots,\operatorname{PAL}_{\mu^{(H)}}(u_{0:n})\bigr)\in\{0,1\}^{H}

(14)

is injective. In particular, $M_{\mathrm{top}}$ (the top-of-stack element) is a deterministic function of the $H$ -dimensional MPAL output, computable by a two-layer MLP.

Proof.

Under the Cantor-depth encoding (definition˜4.1), each stack element $a_{i}$ at depth $d$ has a unique scalar value $\mathrm{code}^{*}(a_{i},d)=C_{\max}-[d(k+1)+i]\Delta$ . The total number of distinct values is $K=(D_{\max}+1)(k+1)$ , each separated by $\Delta>0$ .

Construct $H=\lceil\log_{2}K\rceil$ PAL heads with indicator measures: $\mu^{(h)}_{ij}=b_{h}(\mathrm{index}(i,j))$ , where $\mathrm{index}(i,j)$ maps threshold pair $(\alpha_{i},\beta_{j})$ to the corresponding Cantor-depth code, and $b_{h}(\cdot)$ extracts the $h$ -th bit of the binary representation of that code.

Each head $h$ outputs $\operatorname{PAL}_{\mu^{(h)}}=\sum_{ij}\mu^{(h)}_{ij}\hat{\gamma}_{\alpha_{i}\beta_{j}}[u](n)$ , which equals the $h$ -th bit of the binary encoding of the top-of-stack Cantor code when the measure is concentrated on the relay active at the stack top.

The $H$ -bit vector uniquely identifies $M_{\mathrm{top}}$ via binary decoding — a linear operation implementable by a single MLP layer. The full stack is decoded by repeating this procedure with a mask that deactivates the top relay after reading it (POP operation via the signal generation of lemma˜4.3). ∎

Theorem 4.6 (Turing completeness of PAL-Transformer).

For any two-stack pushdown automaton $M=(Q,\Sigma,\Gamma,\delta,q_{0},Z_{0},F)$ , there exists a single-layer PAL-Transformer $\mathcal{T}$ with $H=4$ MPAL heads, one MLP layer, and arithmetic precision $O(\log(n\cdot|\Gamma|))$ bits that simulates $M$ step-by-step on inputs of length $n$ .

Proof.

We construct $\mathcal{T}$ with four independent signal channels $u^{(1)},u^{(2)},u^{(3)},u^{(4)}$ , each processed by a dedicated MPAL head.

Channel 1 — Machine state.

$u^{(1)}_{n}=\mathrm{code}_{Q}(q_{n})$ encodes the current state $q_{n}\in Q$ as a scalar. Updated directly at each step by the MLP after computing $\delta$ .

Channel 2 — Stack 1.

$u^{(2)}_{0:n}$ encodes the contents of stack 1 via lemma˜4.3. The extremum stack $\Pi^{(2)}_{n}$ is a bijective encoding of the stack-1 contents.

Channel 3 — Stack 2.

$u^{(3)}_{0:n}$ encodes stack 2 analogously.

Channel 4 — Input tape.

$u^{(4)}_{0:n}$ encodes the input word; position encoding allows reading symbol $x_{t}$ at step $t$ via an MPAL head with $W_{I}^{(4)}$ tuned to isolate position $t$ (cf. Pérez et al. (2021), Lemma 4).

Simulation step $n\to n+1$ .

At each step the PAL-Transformer performs:

1.

Read: $q_{n}\leftarrow\operatorname{Dec}(\mathrm{head}_{1})$ , $a_{n}\leftarrow\mathrm{head}_{4}$ , $s^{(1)}_{n}\leftarrow\mathrm{TOP}(\Pi^{(2)}_{n})$ , $s^{(2)}_{n}\leftarrow\mathrm{TOP}(\Pi^{(3)}_{n})$ .
2.

Transition: $(q_{n+1},\mathrm{ops}_{1},\mathrm{ops}_{2})\leftarrow\mathrm{MLP}_{\delta}(q_{n},a_{n},s^{(1)}_{n},s^{(2)}_{n})$ . The MLP implements $\delta$ by tabulation (finite domain, bounded width by Cybenko 1989).
3.

Write: Emit signals $u^{(2)}_{n+1}$ and $u^{(3)}_{n+1}$ per $\mathrm{ops}_{1}$ and $\mathrm{ops}_{2}$ via lemma˜4.3.
4.

Accept: $\mathrm{MLP}_{F}$ checks $q_{n+1}\in F$ , $\Pi^{(2)}=Z_{0}$ , $\Pi^{(3)}=Z_{0}$ .

Correctness.

By induction: at step $n$ , stacks $\Pi^{(2)}_{n}$ and $\Pi^{(3)}_{n}$ faithfully encode the 2-PDA configuration $(q_{n},s^{(1)}_{1:m_{1}},s^{(2)}_{1:m_{2}})$ . The base case is the initial configuration $q_{0},Z_{0},Z_{0}$ . The inductive step follows from lemmas˜4.3 and 4.2.

Since 2-PDA $\equiv$ Turing machine (Hopcroft and Ullman, 1979), $\mathcal{T}$ is Turing-complete.

Depth.

The construction uses $L=1$ MPAL layer and $L=1$ MLP layer — total depth $O(1)$ , independent of $n$ .

Precision.

Encoding depth $d\leq n$ and alphabet size $k=|\Gamma|$ requires distinguishing values spaced $\Delta$ apart up to $C_{\max}=n(k+1)\Delta$ , needing $O(\log(nk))$ bits. ∎

Corollary 4.7 (Depth separation from Transformer).

There exists a language $L$ recognisable by a 1-layer PAL-Transformer that requires $\Omega(\log n)$ layers for any transformer with $O(1)$ heads (under the circuit complexity lower bounds of Furst et al. (1984)).

Corollary 4.8 (Vector PAL is TC with a single head).

A single-layer vector PAL-Transformer (vPAL) with projection $W_{I}\in\mathbb{R}^{2\times d}$ , a single head ( $H=1$ ), one MLP layer, and arithmetic precision $O(\log(n\cdot|\Gamma|))$ bits is Turing-complete.

Proof.

The two-dimensional signal $\mathbf{u}_{n}=(u_{n}^{x},u_{n}^{y})\in\mathbb{R}^{2}$ admits two independent extremum stacks:

\Pi^{x}_{n}=\mathrm{UpdateStack}(\Pi^{x}_{n-1},\,u_{n}^{x}),\qquad\Pi^{y}_{n}=\mathrm{UpdateStack}(\Pi^{y}_{n-1},\,u_{n}^{y}).

(15)

We assign $u_{n}^{x}$ to encode stack 1 of the 2-PDA and $u_{n}^{y}$ to encode stack 2, both using the Cantor-depth encoding of definition˜4.1. The machine state $q_{n}\in Q$ and input tape are encoded in the angular structure of the vPAL measure $\mu(\alpha_{x},\beta_{x},\alpha_{y},\beta_{y},\theta)$ : distinct sectors $\theta\in[0,2\pi)$ correspond to distinct states $q\in Q$ , following the superposition of Preisach half-planes introduced by Frydrych (2019) for two-axis fluxgate sensors (Chapter 4.2.2 of Frydrych 2019). The MLP reads $\mathrm{TOP}(\Pi^{x}_{n})$ and $\mathrm{TOP}(\Pi^{y}_{n})$ simultaneously from the single vPAL head and computes the transition $\delta$ exactly as in theorem˜4.6. Correctness and depth $O(1)$ follow identically. Since $H=1$ head carries both stacks via the two signal dimensions, the head count is reduced from $H=4$ to $H=1$ at the cost of replacing the scalar projection $W_{I}\in\mathbb{R}^{1\times d}$ with the vector projection $W_{I}\in\mathbb{R}^{2\times d}$ . ∎

Remark 4.9 (Differentiability and practical training).

The binary relay $\hat{\gamma}_{\alpha\beta}$ is discontinuous in both the input $u_{n}$ and the thresholds $(\alpha,\beta)$ , making exact backpropagation undefined at switching points. Practical implementations require a smooth relaxation, e.g. the stateful sigmoid relaxation $s_{n+1}=s_{n}[1-\sigma_{\tau}(\beta-u_{n})]+(1-s_{n})\sigma_{\tau}(u_{n}-\alpha)$ with temperature $\tau\to 0$ during training (straight-through estimator or curriculum annealing). The theoretical results of this paper hold for the exact binary relay; the relaxed version is studied empirically in companion work.

Remark 4.10 (Position encoding and rate-independence).

Definition 3.3 includes sinusoidal position encoding $\mathrm{PE}(n)$ , which may appear to contradict rate-independence. The tension is deliberate: $\mathrm{PE}$ is used by the MLP layers (to implement positional logic, e.g. reading the input tape in the TC proof) but is not passed through the MPAL heads. The MPAL output itself — the integral over active relays — remains rate-independent. Rate-independence therefore applies to the PAL component of the architecture, not to the full PAL-Transformer. This is consistent with theorem˜5.7, which characterises the function class of the PAL heads, and with the expressiveness separation, which constructs functions PAL heads cannot compute.

Remark 4.11 (Heads vs. signal dimensions as exchangeable resources).

corollary˜4.8 formalises the intuition that in PAL, the number of heads $H$ and the signal dimension $d_{u}$ are exchangeable: $H$ scalar heads can be replaced by a single head with $H$ -dimensional projection. This exchangeability does not hold for standard multi-head attention, where each head learns an independent linear projection without the hysteretic coupling that links dimensions in vPAL. Specifically, $H$ scalar PAL heads require $H\cdot L^{2}$ parameters for the measure; a single $H$ -dimensional vPAL head requires $L^{2H}$ parameters (the $H$ -fold Cartesian product of Preisach half-planes), which grows exponentially. The minimal TC architecture is therefore scalar PAL at $H=2$ (two stacks, two heads) or vPAL at $H=1$ (two stacks, one head with $d_{u}=2$ ).

5 Expressiveness Separation

We prove the central incomparability result.

Theorem 5.1 (Expressiveness incomparability).

Let $\mathcal{F}_{\operatorname{PAL}}$ and $\mathcal{F}_{\mathrm{Tr}}$ be the function classes computable by bounded-depth PAL-Transformer and Transformer respectively. Then:

\mathcal{F}_{\operatorname{PAL}}\setminus\mathcal{F}_{\mathrm{Tr}}\neq\emptyset\qquad\text{and}\qquad\mathcal{F}_{\mathrm{Tr}}\setminus\mathcal{F}_{\operatorname{PAL}}\neq\emptyset.

(16)

5.1 Functions PAL computes but Transformer cannot (at bounded depth)

Proposition 5.2 (Historical range in $O(1)$ layers).

The function $f_{\mathrm{range}}(u_{0:n})=\max_{i\leq n}u_{i}-\min_{i\leq n}u_{i}$ is computable by a 1-layer PAL in $O(1)$ time.

Proof.

$M_{1}=\max_{i\leq n}u_{i}$ and $m_{k}=\min_{i\leq n}u_{i}$ are directly readable from the extremum stack $\Pi_{n}$ as the first maximum and last minimum. $f_{\mathrm{range}}=M_{1}-m_{k}$ . ∎

Proposition 5.3 (Transformer requires $\Omega(\log n)$ layers for range).

Any transformer with $O(1)$ layers and $O(1)$ heads cannot compute $f_{\mathrm{range}}$ exactly on sequences of length $n$ .

Proof.

$\mathrm{MAX}$ over $n$ values is not in $\mathrm{AC}^{0}$ (Håstad, 1987) — it cannot be computed by constant-depth Boolean circuits of polynomial size. A constant-depth transformer with $O(1)$ heads is equivalent to an $\mathrm{AC}^{0}$ circuit (cf. Hahn (2020)), so it cannot compute $\mathrm{MAX}$ exactly. Since $f_{\mathrm{range}}$ requires $\mathrm{MAX}$ as a subcomputation, the claim follows. ∎

5.2 Functions Transformer computes but PAL cannot

Proposition 5.4 (Random-access retrieval).

The function $f_{\mathrm{copy}}(x_{0:n},p)=x_{p}$ (retrieve token at position $p$ ) is computable by a 1-layer hard-attention Transformer in $O(1)$ layers.

Proof.

Set $q_{n}=\mathrm{PE}(p)$ and $k_{j}=\mathrm{PE}(j)$ . Hard attention selects $j^{*}=\operatorname*{arg\,max}_{j}q_{n}\cdot k_{j}=p$ . The output is $v_{p}=x_{p}$ . ∎

Proposition 5.5 (PAL cannot perform exact random access).

No PAL-Transformer (of any depth or head count) can compute $f_{\mathrm{copy}}(x_{0:n},p)=x_{p}$ for all sequences and positions.

Proof.

We give a structural impossibility proof based on rate-independence (propositions˜2.3 and 5.7).

Construction.

Fix any target position $p\in\{1,\ldots,n-1\}$ and any value $v\neq v^{\prime}$ . Define two sequences that differ only at position $p$ :

	$\displaystyle\mathbf{x}$	$\displaystyle=(x_{0},\ldots,x_{p-1},\,v,\,x_{p+1},\ldots,x_{n}),$		(17)
	$\displaystyle\mathbf{x}^{\prime}$	$\displaystyle=(x_{0},\ldots,x_{p-1},\,v^{\prime},\,x_{p+1},\ldots,x_{n}),$		(18)

where the surrounding values $x_{p-1}$ and $x_{p+1}$ satisfy $x_{p-1}<\min(v,v^{\prime})<\max(v,v^{\prime})<x_{p+1}$ (i.e. $p$ is in a strictly monotone ascending segment of both sequences).

Extremum stacks are identical.

Since position $p$ lies in a monotone ascending segment of both sequences, it is not a local extremum of either $\mathbf{x}$ or $\mathbf{x}^{\prime}$ . Therefore $\Pi_{n}(\mathbf{x})=\Pi_{n}(\mathbf{x}^{\prime})$ : the extremum stacks are identical, because only positions $j$ where $u_{j}$ is a local extremum enter the stack (algorithm˜1), and those positions are the same in both sequences.

Rate-independence forces identical outputs.

By theorem˜5.7, every PAL-Transformer computes a rate-independent function, hence a function of $\Pi_{n}$ alone (proposition˜2.7). Since $\Pi_{n}(\mathbf{x})=\Pi_{n}(\mathbf{x}^{\prime})$ , any PAL-Transformer outputs the same value on $\mathbf{x}$ and $\mathbf{x}^{\prime}$ . But $f_{\mathrm{copy}}(\mathbf{x},p)=v\neq v^{\prime}=f_{\mathrm{copy}}(\mathbf{x}^{\prime},p)$ . Therefore no PAL-Transformer computes $f_{\mathrm{copy}}$ . ∎

Remark 5.6 (Why the probabilistic argument is incorrect).

An earlier version of this proof argued that position $p$ is a local extremum with probability $\Theta(1/n)$ for a random sequence, making $f_{\mathrm{copy}}$ inaccessible with high probability. This is incorrect: for i.i.d. sequences from a continuous distribution, an interior position is a local extremum (maximum or minimum) with probability $2/3$ by the symmetry of the six orderings of $(u_{p-1},u_{p},u_{p+1})$ . The correct argument is the structural one above, which applies universally and does not rely on any probabilistic assumption about the input.

5.3 The separating property: rate-independence

Theorem 5.7 (Rate-independence as separating property).

A function $f:\mathbb{R}^{n+1}\to\mathbb{R}$ is computable by a PAL-Transformer only if it is rate-independent in the sense of proposition˜2.3. Standard attention computes functions that are not rate-independent. Hence rate-independence is a necessary condition for membership in $\mathcal{F}_{\operatorname{PAL}}$ and a sufficient condition for $f\notin\mathcal{F}_{\mathrm{Tr}}\setminus\mathcal{F}_{\operatorname{PAL}}$ .

Proof.

PAL is a composition of rate-independent operators (relay + linear combination) and rate-independent nonlinearities (ReLU is rate-independent). By closure under composition, any function computable by a PAL-Transformer is rate-independent.

Standard attention is not rate-independent: the attention weight $a_{j}=\mathrm{softmax}(q_{n}\cdot k_{j}/\sqrt{d})$ depends explicitly on position through $k_{j}=W_{K}(x_{j}+\mathrm{PE}(j))$ , so inserting a time-rescaling $\phi$ changes the output. ∎

6 Logical Characterisation

Barceló et al. (2020) showed that soft-attention transformers correspond to $\mathrm{FO}$ with aggregate functions — a fragment of first-order logic over sequences. We give an analogous characterisation for PAL.

Definition 6.1 (Extremum First-Order Logic, $\mathrm{EFO}$ ).

$\mathrm{EFO}$ is the extension of first-order logic over sequences with:

1.

Quantification over extremal positions: $\exists^{\mathrm{ext}}i\,\phi(i)$ asserts that there exists a local extremum position $i$ satisfying $\phi$ .
2.

An extremum aggregate operator: $\mathrm{ExtAgg}_{i}[f(i)]$ sums $f(i)$ over all extremal positions weighted by $\mu$ .
3.

No quantification over arbitrary positions.

Theorem 6.2 (PAL corresponds to EFO).

A function $f:\Sigma^{*}\to\mathbb{R}$ is computable by a bounded-depth PAL-Transformer if and only if it is definable in $\mathrm{EFO}$ .

Proof sketch..

( $\Rightarrow$ ) Each MPAL head computes $\sum_{i:u_{i}\text{ is extremum}}\mu_{ij}\hat{\gamma}_{\alpha_{i}\beta_{j}}$ — an extremum aggregate. Composition through MLP layers corresponds to Boolean combinations of $\mathrm{EFO}$ formulae.

( $\Leftarrow$ ) Each $\mathrm{EFO}$ formula can be implemented by appropriate choice of $\mu^{(h)}$ and $W_{I}^{(h)}$ in MPAL. The extremal quantifier is implemented by the relay’s dead-band — only extremal positions cause relay state changes, so only extremal positions contribute to the sum. Full proof by structural induction on $\mathrm{EFO}$ formula complexity; details in appendix˜A. ∎

Remark 6.3 (Comparison with FO + Aggregate).

$\mathrm{EFO}\subsetneq\mathrm{FO}+\mathrm{Aggregate}$ : $\mathrm{EFO}$ cannot quantify over arbitrary positions (no random access), while $\mathrm{FO}+\mathrm{Aggregate}$ can. Conversely, $\mathrm{EFO}$ can express $f_{\mathrm{range}}$ directly as $\mathrm{ExtAgg}[\mathbf{1}[i=\mathrm{global\ max}]\cdot u_{i}]-\mathrm{ExtAgg}[\mathbf{1}[i=\mathrm{global\ min}]\cdot u_{i}]$ , which has no bounded-depth $\mathrm{FO}$ definition.

7 Computational Complexity

Theorem 7.1 (Complexity of PAL inference).

For a single-layer $H$ -head PAL-Transformer processing a sequence of length $n$ :

1.

Time per token: $O(H\cdot\log k\cdot d)$ where $k\leq n$ is extremum stack depth, $d$ model dimension.
2.

Total time for sequence of length $n$ : $O(H\cdot n\log n\cdot d)$ .
3.

Memory: $O(H\cdot k\cdot d)$ .

Compare with standard attention: time $O(n^{2}d)$ , memory $O(nd)$ .

Table 1: Complexity and expressiveness comparison.

n

= sequence length,

d

= model dimension,

k\leq n

= extremum stack depth,

d_{u}

= signal dimension.

Architecture	Time (total)	Memory	Depth for TC	Heads for TC
Transformer (softmax)	$O(n^{2}d)$	$O(nd)$	not TC	—
Transformer (hard)	$O(n^{2}d)$	$O(nd)$	$O(\log n)$	$O(1)$
Mamba / SSM	$O(nd)$	$O(d)$	open	—
RWKV	$O(nd)$	$O(d)$	open	—
PAL (scalar, $d_{u}=1$ )	$\mathbf{O(n\log n\cdot d)}$	$\mathbf{O(kd)}$	$\mathbf{O(1)}$	$H=4$
vPAL (vector, $d_{u}=2$ )	$\mathbf{O(n\log n\cdot d)}$	$\mathbf{O(kd)}$	$\mathbf{O(1)}$	$\mathbf{H=1}$

Predicted task advantages.

By theorems˜5.1 and 5.7, PAL is predicted to outperform standard attention on tasks that are rate-independent and require long episodic memory:

1.

Tracking entity states across long documents (who did what to whom).
2.

Detecting anomalies in time series (historical range, running extrema).
3.

Reasoning over ordered events without positional sensitivity (logical puzzles, symbolic reasoning).
4.

Energy market dispatch where decision thresholds rather than price histories determine behaviour (Frydrych and Szewczyk, 2014).

8 Related Work

Expressiveness of transformers.

Pérez et al. (2021) proved Turing completeness of hard-attention transformers at depth $O(\log n)$ . Hahn (2020) and Barceló et al. (2020) characterised soft-attention transformers as $\mathrm{FO}$ with aggregate functions. Merrill and Sabharwal (2023) established circuit complexity bounds separating transformer classes. PAL is a new point in this space, incomparable to existing architectures.

Alternative memory mechanisms.

Mamba (Gu and Dao, 2023) uses selective SSMs with linear recurrence and input-dependent forgetting. RWKV (Peng et al., 2023) replaces attention with time-decay weighted recurrence. Titans (Behrouz et al., 2025) learns long-term memory through online gradient descent. All use temporal (recency-based) forgetting; PAL uses significance-based forgetting through wiping.

Hysteresis in machine learning.

Frydrych and Szewczyk (2014); Frydrych (2019) applied Preisach-type models to financial market modelling. Barroso et al. (2015) used Preisach operators for battery electrochemical modelling. To our knowledge, this is the first work to use the Preisach operator as a sequence modelling layer in neural networks.

Sparse and efficient attention.

Longformer (Beltagy et al., 2020) and BigBird (Zaheer et al., 2020) implement sparse attention patterns. PAL achieves a different kind of sparsity — extremal sparsity — where only local maxima and minima contribute to the output, as opposed to sliding windows or random patterns.

9 Connection to the Random-Field Ising Model

9.1 The Preisach–RFIM Equivalence

The connection between the Preisach operator and the Random-Field Ising Model (RFIM) has been established in the physics literature (Sethna et al., 2006; Dahmen and Sethna, 1993), and provides a bridge between PAL and a broad class of combinatorial and statistical problems.

The mean-field RFIM at $T=0$ consists of $N$ Ising spins $\sigma_{i}\in\{-1,+1\}$ with Hamiltonian:

\mathcal{H}=-\frac{J}{2N}\sum_{i\neq j}\sigma_{i}\sigma_{j}-\sum_{i}(h_{i}+H)\sigma_{i},

(19)

where $J>0$ , $H$ is a uniform external field, and $\{h_{i}\}$ are independent random fields drawn from distribution $\mathcal{P}(h)$ .

At $T=0$ , each spin satisfies the single-spin stability condition: $\sigma_{i}=\operatorname{sign}(Jm+h_{i}+H)$ , where $m=N^{-1}\sum_{i}\sigma_{i}$ is the mean magnetisation. Spin $\sigma_{i}$ flips from $-1$ to $+1$ when $H$ crosses the activation threshold $\alpha_{i}=-h_{i}-Jm$ from below, and flips back when $H$ crosses the deactivation threshold $\beta_{i}=-h_{i}+Jm$ from above.

Proposition 9.1 (Preisach–RFIM equivalence).

The mean-field RFIM at $T=0$ , driven quasi-statically by external field $H$ , is equivalent to a Preisach operator $\mathcal{P}_{\mu}[H]$ with measure:

\mu(\alpha,\beta)=\mathcal{P}\!\left(\frac{\alpha+\beta}{2}\right)\cdot\delta\!\left(\alpha-\beta-2Jm\right),

(20)

where the measure is supported on the line $\alpha-\beta=2Jm$ within the Preisach half-plane $\mathcal{T}$ . The magnetisation $m(H)=\mathcal{P}_{\mu}[H]$ satisfies the self-consistency equation $m=\mathcal{P}_{\mu}[H](t)$ .

Proof.

Each spin $i$ contributes a relay $\hat{\gamma}_{\alpha_{i}\beta_{i}}$ with $\alpha_{i}-\beta_{i}=2Jm$ (the coupling gap). The output $\sigma_{i}=2\hat{\gamma}_{\alpha_{i}\beta_{i}}[H]-1$ and the aggregate magnetisation:

m=\frac{1}{N}\sum_{i}\sigma_{i}=2\cdot\frac{1}{N}\sum_{i}\hat{\gamma}_{\alpha_{i}\beta_{i}}[H]-1=2\mathcal{P}_{\mu}[H]-1,

where $\mu$ is the empirical measure of threshold pairs, converging to (20) as $N\to\infty$ by the law of large numbers applied to i.i.d. $h_{i}\sim\mathcal{P}$ . ∎

Remark 9.2 (Structural consequences).

proposition˜9.1 implies that the hysteresis loop, subloop structure, and wiping property of the RFIM are exact consequences of the Preisach operator structure. In particular, the return-point memory of the RFIM (Sethna et al., 2006) is precisely the wiping property (proposition˜2.4), and the extremum stack (definition˜2.6) is the minimal sufficient statistic of the RFIM’s history under quasi-static driving.

9.2 PAL as a Learned, Sequential RFIM

Under the Preisach–RFIM equivalence, PAL is a learned, sequential, non-equilibrium generalisation of the RFIM:

Dimension	RFIM	PAL
Spins	fixed binary $\sigma_{i}\in\{-1,+1\}$	relay states $r_{k}\in\{0,1\}$ , learned
Driving signal	quasi-static field $H$	arbitrary sequence $u_{0:n}$
Disorder	quenched $\{h_{i}\}\sim\mathcal{P}$	learned measure $\mu(\alpha,\beta)$
Coupling	mean-field $J/N$	implicit through self-consistency of $\mu$
Dynamics	equilibrium (lowest energy)	causal, rate-independent
Memory	return-point memory (history of $H$ )	extremum stack $\Pi_{n}$
Wiping	return-point memory property	proposition˜2.4

The key conceptual shift: the RFIM asks "what is the equilibrium configuration at field $H$ ?" while PAL asks "what is the causal output of the sequence $u_{0:n}$ ?" This shift from equilibrium to sequential opens PAL to a broad class of problems where Ising-type models apply but the data arrives as a stream.

9.3 Problems where PAL Inherits Ising Expressiveness

We identify three problem classes where the RFIM–Preisach equivalence suggests PAL has structural advantages.

9.3.1 Sequential Binary Optimisation

The Ising model underlies a broad class of NP-hard combinatorial problems: MAX-CUT, graph colouring, satisfiability, and the Hopfield associative memory (Lucas, 2014). Their energy function has the form:

E(\boldsymbol{\sigma})=-\sum_{i<j}J_{ij}\sigma_{i}\sigma_{j}-\sum_{i}h_{i}\sigma_{i},

(21)

and the goal is $\boldsymbol{\sigma}^{*}=\operatorname*{arg\,min}E$ .

Proposition 9.3 (PAL tracks mean-field Ising energy for streaming interactions).

Let interactions $J_{1},J_{2},\ldots,J_{n}\in\mathbb{R}$ arrive sequentially as a stream, drawn i.i.d. from a distribution $\mathcal{P}_{J}$ with mean $\bar{J}$ and variance $\sigma_{J}^{2}$ . Define the scalar signal $u_{t}=J_{t}$ . Then the PAL output with measure $\mu^{*}(\alpha,\beta)=\alpha\cdot\mathbf{1}[\alpha=-\beta]$ satisfies:

\operatorname{PAL}_{\mu^{*}}(u_{0:n})\;=\;\sum_{t=0}^{n}J_{t}\cdot\hat{\gamma}_{J_{t}-J_{t}}[u](t)\;=\;\bar{E}_{n}+O(n^{1/2}),

(22)

where $\bar{E}_{n}=-\frac{1}{N}\sum_{i<j}J_{ij}m_{i}m_{j}$ is the mean-field Ising energy for the empirical mean magnetisation $m=\mathbb{E}_{t\leq n}[\sigma_{t}]$ , and the $O(n^{1/2})$ error follows from a standard concentration bound on the empirical mean.

Proof.

Each interaction $J_{t}$ contributes to the Ising energy when its relay $\hat{\gamma}_{J_{t}-J_{t}}[u](t)=1$ , i.e. when $J_{t}\geq J_{t}$ — which holds trivially at the moment of arrival. The relay then tracks whether $J_{t}$ remains the dominant interaction. By the wiping property, relay $\hat{\gamma}_{J_{t}-J_{t}}$ remains active at time $n$ iff no subsequent $J_{t^{\prime}}>J_{t}$ has arrived. The PAL aggregate sums $J_{t}$ over all non-dominated interactions, giving a running estimate of the effective coupling.

For the mean-field case $J_{ij}=J/N$ for all pairs, the self-consistency equation $m=\int\mathcal{P}(h)\,\mathbf{1}[h>-Jm-H]\,dh$ from proposition˜9.1 holds exactly: $\operatorname{PAL}_{\mu^{*}}(u_{0:n})=Jm^{2}/2+O(n^{-1/2})$ by the law of large numbers applied to $m$ over $n$ observations, recovering the mean-field energy $-Jm^{2}/2$ . The error bound $O(n^{1/2})$ follows from Hoeffding’s inequality applied to the sum of bounded relay outputs. ∎

Remark 9.4 (Relation to MAX-CUT).

The mean-field Ising energy in proposition˜9.3 is related to the MAX-CUT value by $\mathrm{CUT}(S)=(E_{\mathrm{max}}-E(\boldsymbol{\sigma}))/2$ for the optimal cut $S$ . However, PAL does not solve MAX-CUT — it tracks the running mean-field energy, which provides a lower bound on the cut value. The advantage is computational: PAL updates this estimate in $O(\log k)$ per new interaction, without re-solving from scratch.

9.3.2 Associative Memory with Structured Forgetting

The Hopfield network (Hopfield, 1982) stores $P$ patterns $\{\boldsymbol{\xi}^{\mu}\}_{\mu=1}^{P}$ as attractors of Ising dynamics with $J_{ij}=N^{-1}\sum_{\mu}\xi_{i}^{\mu}\xi_{j}^{\mu}$ . Retrieval capacity is limited to $P<0.14N$ patterns before catastrophic interference (Amit et al., 1985).

PAL offers a different memory model where forgetting is determined by significance (extremality) rather than capacity:

Proposition 9.5 (PAL as hysteretic associative memory with capacity bound).

Let patterns $\boldsymbol{\xi}^{1},\ldots,\boldsymbol{\xi}^{P}\in\mathbb{R}^{d}$ arrive sequentially with activation strengths $u_{t}=\|\boldsymbol{\xi}^{t}\|_{2}$ . Let $k$ be the depth of the extremum stack $\Pi_{n}$ after all $P$ patterns have been processed.

1.

Storage: The extremum stack $\Pi_{n}$ retains exactly those $k$ patterns whose activation strength constitutes a local extremum of the stream $u_{1},\ldots,u_{P}$ . All other patterns are wiped by the wiping property (proposition˜2.4).
2.

Non-overlapping threshold support: The $k$ retained patterns correspond to disjoint threshold pairs $(M_{s},m_{s})$ with $M_{s}\neq M_{s^{\prime}}$ for $s\neq s^{\prime}$ (strict monotonicity of the stack, lemma˜4.2), so their relays have disjoint support on $\mathcal{T}$ and their contributions to $\operatorname{PAL}_{\mu}$ are orthogonal in measure space. Note that wiping is a form of interference between patterns: a stronger subsequent pattern erases a prior one. The claim is that the $k$ surviving patterns do not mutually interfere in the PAL output.
3.

Capacity: The maximum number of simultaneously retrievable patterns is exactly $k$ , bounded by the number of local extrema in $u_{1:P}$ :

$\mathrm{Capacity}(\mathrm{PAL})=k\;\leq\;n_{\mathrm{ext}}(u_{1:P}),$ (23)

where $n_{\mathrm{ext}}(u_{1:P})$ is the number of local extrema in the activation strength sequence. This differs fundamentally from Hopfield capacity $\approx 0.14N$ (Amit et al., 1985): PAL capacity is limited by stack depth, not weight-matrix rank.

Proof.

Storage (part 1): Direct from proposition˜2.4. Pattern $\boldsymbol{\xi}^{t}$ is wiped when a subsequent pattern $\boldsymbol{\xi}^{t^{\prime}}$ with $\|\boldsymbol{\xi}^{t^{\prime}}\|_{2}>\|\boldsymbol{\xi}^{t}\|_{2}$ arrives, since the new maximum overwrites the old in the extremum stack. Only patterns at local extrema of $u_{1:P}$ survive.

Zero interference (part 2): The PAL output is $\operatorname{PAL}_{\mu}(u_{0:n})=\sum_{i\geq j}\mu_{ij}\hat{\gamma}_{\alpha_{i}\beta_{j}}[u](n)$ . Each retained pattern $\boldsymbol{\xi}^{t_{s}}$ corresponds to a unique pair $(M_{s},m_{s})$ in $\Pi_{n}$ with $M_{s}\neq M_{s^{\prime}}$ for $s\neq s^{\prime}$ (strict monotonicity of the stack, lemma˜4.2). The relays $\hat{\gamma}_{M_{s}m_{s}}$ and $\hat{\gamma}_{M_{s^{\prime}}m_{s^{\prime}}}$ have disjoint support on the Preisach half-plane $\mathcal{T}$ when $M_{s}\neq M_{s^{\prime}}$ , so their contributions to $\operatorname{PAL}_{\mu}$ are orthogonal — no cross-pattern interference.

Capacity (part 3): The stack depth $k\leq n_{\mathrm{ext}}(u_{1:P})$ is bounded by the number of local extrema of the activation sequence, since each extremum corresponds to at most one stack entry by the push/pop mechanics of algorithm˜1. Each entry encodes one pattern without interference. The Hopfield bound $0.14N$ follows from the rank of the Hebbian weight matrix $W=N^{-1}\sum_{\mu}\boldsymbol{\xi}^{\mu}(\boldsymbol{\xi}^{\mu})^{\top}$ , which is limited by the number of stored patterns relative to $N$ . PAL has no weight matrix — its capacity is limited by stack depth, not by the dimension of the weight space. ∎

Remark 9.6 (Retrieval mechanism).

To retrieve pattern $\boldsymbol{\xi}^{t_{s}}$ from the PAL stack, a query signal $q=\|\boldsymbol{\xi}^{t_{s}}\|_{2}$ is presented. The relay $\hat{\gamma}_{M_{s}+\varepsilon M_{s}-\varepsilon}[q]$ activates uniquely for the pattern at stack position $s$ , and the associated value $\mu_{M_{s},m_{s}}\cdot\boldsymbol{\xi}^{t_{s}}$ is returned. Retrieval time is $O(\log k)$ by binary search on the ordered stack.

9.3.3 Sequential Belief Propagation in Markov Random Fields

Markov Random Fields (MRF) with pairwise binary interactions are equivalent to Ising models with site-dependent external fields. Standard belief propagation (BP) on MRFs is a static algorithm requiring the full graph to be available upfront.

Proposition 9.7 (PAL as exact causal BP on tree-structured MRF).

Let $\mathcal{G}=(V,E)$ be a tree-structured MRF with binary variables $\sigma_{v}\in\{-1,+1\}$ and pairwise potentials $\psi_{uv}(\sigma_{u},\sigma_{v})=e^{J_{uv}\sigma_{u}\sigma_{v}}$ . Observations arrive sequentially in leaf-to-root order. Define the signal $u_{t}=\tanh^{-1}(m_{t})$ where $m_{t}=\mathbb{E}[\sigma_{t}\mid x_{1:t}]$ is the marginal belief at step $t$ under belief propagation. Then the PAL operator with measure:

\mu^{*}(\alpha,\beta)=\tfrac{1}{2}\log\tfrac{1+\tanh(\alpha)}{1-\tanh(\alpha)}\cdot\mathbf{1}[\alpha=-\beta]

(24)

satisfies $\operatorname{PAL}_{\mu^{*}}(u_{0:n})=m_{n}$ exactly for all tree-structured MRFs, where $m_{n}$ is the exact marginal belief at the root. For loopy graphs, the PAL output approximates the loopy BP fixed point.

Proof.

On a tree, belief propagation computes exact marginals by the Bethe-Peierls equations (Mézard and Montanari, 2009). In leaf-to-root order, each message depends only on previously received messages, making the computation causal. The effective field at the root satisfies $h^{\mathrm{eff}}=\sum_{u\in\partial v}\tanh^{-1}(m_{u\to v})$ , which is the fixed-point of the Preisach self-consistency equation $m=\tanh(Jm+H)$ from proposition˜9.1. With measure $\mu^{*}$ from (24), $\operatorname{PAL}_{\mu^{*}}(u_{0:n})$ tracks $h^{\mathrm{eff}}$ causally, and $\tanh(\operatorname{PAL}_{\mu^{*}}(u_{0:n}))=m_{n}$ exactly on trees by induction on tree depth. ∎

9.4 Avalanches and Phase Transitions in PAL

A striking property of the RFIM is its disorder-induced phase transition: at a critical disorder strength $\Delta_{c}$ , the hysteresis loop develops a discontinuity corresponding to a macroscopic avalanche of spin flips (Sethna et al., 2006). At criticality, avalanche sizes follow a power law $P(s)\sim s^{-\tau}$ with universal exponent $\tau$ .

Proposition 9.8 (Scalar PAL criticality).

A scalar PAL with measure $\mu$ drawn from a Gaussian distribution with variance $\Delta^{2}$ over the two-dimensional Preisach half-plane $\mathcal{T}$ exhibits a phase transition at critical variance $\Delta_{c}$ :

•

For $\Delta>\Delta_{c}$ : the output $\operatorname{PAL}_{\mu}(u_{0:n})$ varies smoothly with $u_{n}$ — subcritical regime, corresponding to gradual relay activations.
•

For $\Delta<\Delta_{c}$ : a macroscopic fraction of relays activate simultaneously at a critical threshold — supercritical regime, corresponding to an infinite avalanche.
•

At $\Delta=\Delta_{c}$ : relay activations follow a power law in group size, with the same universality class as the mean-field RFIM.

Proof.

By proposition˜9.1, PAL with Gaussian measure is equivalent to mean-field RFIM with disorder $\Delta$ . The phase transition of the RFIM at $\Delta_{c}=J$ (Dahmen and Sethna, 1993) translates directly to PAL. At $\Delta_{c}$ , the self-consistency equation $m=\int\mathcal{P}(h)\mathbf{1}[h>-Jm-H]\,dh$ has a bifurcation point, corresponding to a jump discontinuity in the Preisach output. ∎

Remark 9.9 (Implications for PAL learning).

proposition˜9.8 has a practical implication: if the learned measure $\mu^{*}$ concentrates near the critical disorder $\Delta_{c}$ , the PAL layer operates near a phase transition — maximising sensitivity to input changes while maintaining structured memory. This is analogous to the edge of chaos hypothesis in recurrent neural networks (Langton, 1990), but with a precise physical characterisation through RFIM criticality. Training PAL near $\Delta_{c}$ may be a principled alternative to spectral radius regularisation of recurrent weights.

9.5 Summary: PAL vs. Ising-based Methods

Criterion	Ising / RFIM	PAL	Advantage
Data model	Static graph, $O(n^{2})$ couplings	Sequential stream	PAL
Update cost	$O(n^{2})$ per new node	$O(\log k)$ per new token	PAL
Forgetting	None (quenched disorder)	Significance-based wiping	PAL
Exact optimisation	NP-hard in general	Approximation only	Ising
Equilibrium guarantees	Yes (Gibbs measure)	No (causal only)	Ising
Universality class	Known ( $\tau,\nu,\ldots$ )	Inherited from RFIM	Equal
Coupling structure	Arbitrary $J_{ij}$	Mean-field implicit	Ising
Sequence modelling	Not native	Native (rate-independent)	PAL

10 Conclusion

We introduced the Preisach Attention Layer (PAL), a novel sequence modelling architecture grounded in classical hysteresis theory. The results establish:

1.

PAL-Transformer is Turing-complete at depth $O(1)$ , improving on the $O(\log n)$ depth of standard transformers (theorem˜4.6). Moreover, a vector PAL (vPAL) with two-dimensional signal projection achieves Turing completeness with a single head ( $H=1$ ), establishing that signal dimension and head count are exchangeable resources in PAL (corollaries˜4.8 and 4.11).
2.

The function classes of PAL and transformer are incomparable, with rate-independence as the separating property (theorems˜5.1 and 5.7).
3.

PAL corresponds exactly to Extremum First-Order Logic (EFO), a strict fragment of the $\mathrm{FO}$ + Aggregate class corresponding to transformers (theorem˜6.2).
4.

PAL is the learned, sequential, causal generalisation of the mean-field Random-Field Ising Model at $T=0$ , inheriting its universality class and phase-transition structure (propositions˜9.1 and 9.8).

PAL is thus a natural architecture for tasks with long episodic memory, where the significance of past events matters more than their recency or position, and where the problem structure is naturally binary and threshold-driven.

Open questions.

1.

Empirical validation: Do the predicted task advantages materialise in practice? Experiments on state-tracking benchmarks (MQAR, SCROLLS) would test theorem˜5.1 empirically.
2.

Learning dynamics and criticality: Does gradient-based learning of $\mu(\alpha,\beta)$ drive the measure toward the critical disorder $\Delta_{c}$ ? Is training near criticality beneficial empirically, analogous to the edge-of-chaos effect?
3.

Beyond mean-field: Can the equivalence in proposition˜9.1 be extended beyond mean-field RFIM to short-range interactions (Bethe lattice, finite-dimensional RFIM)? This would connect PAL to a richer universality class.
4.

Hybrid architectures: Can PAL heads be combined with standard attention heads to obtain both random access and significance-based memory?
5.

Continuous-time extension: The rate-independence of PAL suggests a natural extension to continuous-time sequence models (neural ODEs, S4), where the driving signal is a continuous path rather than a discrete sequence.
6.

Vector PAL and multi-dimensional inputs: corollary˜4.8 establishes that vPAL with a two-dimensional signal $\mathbf{u}_{n}\in\mathbb{R}^{2}$ is Turing-complete at $H=1$ head — reducing the head count from $H=4$ (scalar PAL) to $H=1$ by exploiting the two independent extremum stacks of the vector signal. This follows the superposition of Preisach half-planes developed by Frydrych (2019) for two-axis fluxgate sensors (Chapters 4.2.2–4.2.6), where the full magnetisation vector $\mathbf{M}$ is integrated over the three-dimensional space $(\alpha,\beta,\theta)$ with displacement $\gamma_{\alpha\beta}(\theta)$ and rotation $\chi_{\alpha\beta}(\theta)$ components. Three questions remain open for vPAL: (a) Does the vector RFIM connection extend to the anisotropic case studied by Frydrych, where the measure $\mu(\alpha,\beta,\theta)$ breaks rotational symmetry? (b) Can the domain-rotation component $\chi_{\alpha\beta}(\theta)$ be interpreted as a differentiable residual that complements the binary relay — analogous to soft attention complementing hard attention? (c) Does the exponential growth of the measure parameter space ( $L^{2H}$ for $H$ -dimensional vPAL) create a fundamental expressiveness–efficiency tradeoff absent in scalar PAL?

Broader Impact Statement

This work introduces a theoretical architecture for sequence modelling grounded in classical hysteresis theory. The primary contributions are mathematical — Turing completeness proofs, expressiveness separations, and logical characterisations — and do not directly enable any specific application.

The connection to the Random-Field Ising Model (Section 8) suggests potential applications in combinatorial optimisation, associative memory, and belief propagation. These are established areas of machine learning with broad beneficial applications. We are not aware of direct pathways from this theoretical work to harmful applications.

If implemented in practice, PAL-based models would share the general risks of machine learning systems: potential for bias amplification, misuse in surveillance or manipulation, and environmental cost of training large models. These risks are not specific to PAL and are addressed by general ML ethics guidelines.

The $O(n\log n)$ computational complexity of PAL (versus $O(n^{2})$ for attention) may reduce the energy cost of training long-context models, which is a potential positive environmental impact.

References

E. Akyürek, D. Schuurmans, J. Andreas, T. Ma, and D. Zhou (2023) What learning algorithm is in-context learning? investigations with linear models. In International Conference on Learning Representations, External Links: Link Cited by: §1.
D. J. Amit, H. Gutfreund, and H. Sompolinsky (1985) Storing infinite numbers of patterns in a spin-glass model of neural networks. Physical Review Letters 55 (14), pp. 1530–1533. External Links: Document Cited by: item 3, §9.3.2.
P. Barceló, E. V. Kostylev, M. Monet, J. Pérez, J. Reutter, and J. P. Silva (2020) The logical expressiveness of graph neural networks. In International Conference on Learning Representations, External Links: Link Cited by: Corollary A.9, item 4, §1, §6, §8.
R. Barroso, A. Egaña, J. L. Marqués, I. Etxeberria-Otadui, and O. Curea (2015) Preisach modeling of LiFePO₄ lithium-iron-phosphate battery hysteresis. Journal of Energy Storage 2, pp. 65–72. External Links: Document Cited by: §8.
A. Behrouz, P. Zhong, and V. Mirrokni (2025) Titans: learning to memorize at test time. In arXiv preprint arXiv:2501.00663, External Links: Link Cited by: §8.
I. Beltagy, M. E. Peters, and A. Cohan (2020) Longformer: the long-document transformer. In arXiv preprint arXiv:2004.05150, External Links: Link Cited by: §8.
M. Brokate and J. Sprekels (1996) Hysteresis and phase transitions. Applied Mathematical Sciences, Vol. 121, Springer, New York. External Links: Document Cited by: Proposition 2.3.
G. Cybenko (1989) Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems 2 (4), pp. 303–314. External Links: Document Cited by: §A.2, §B.2, item 2.
K. Dahmen and J. P. Sethna (1993) Hysteresis loop critical exponents in $6-\varepsilon$ dimensions. Physical Review Letters 71 (20), pp. 3222–3225. External Links: Document Cited by: §9.1, §9.4.
P. Frydrych and R. Szewczyk (2014) New portfolio risk optimisation method for strongly dependent assets. Journal of Engineering Studies and Research 20 (3), pp. 30–37. Cited by: §1, item 4, §8.
P. Frydrych (2019) Modelowanie charakterystyk magnesowania amorficznych rdzeni dwuosiowych sensorów transduktorowych. Ph.D. Thesis, Politechnika Warszawska, Wydział Mechatroniki, Warsaw, Poland. Cited by: §1, item 6, Definition 3.2, §4.2, §8.
M. Furst, J. B. Saxe, and M. Sipser (1984) Parity, circuits, and the polynomial-time hierarchy. In Mathematical Systems Theory, Vol. 17, pp. 13–27. External Links: Document Cited by: Corollary 4.7.
A. Gu and T. Dao (2023) Mamba: linear-time sequence modeling with selective state spaces. In arXiv preprint arXiv:2312.00752, External Links: Link Cited by: §1, §8.
M. Hahn (2020) Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics 8, pp. 156–171. External Links: Document Cited by: §1, §5.1, §8.
J. Håstad (1987) Computational limitations of small-depth circuits. MIT Press, Cambridge, MA. Cited by: §5.1.
J. E. Hopcroft and J. D. Ullman (1979) Introduction to automata theory, languages, and computation. Addison-Wesley, Reading, MA. Cited by: §4.2, §4.
J. J. Hopfield (1982) Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences 79 (8), pp. 2554–2558. External Links: Document Cited by: §9.3.2.
C. G. Langton (1990) Computation at the edge of chaos: phase transitions and emergent computation. Physica D: Nonlinear Phenomena 42 (1–3), pp. 12–37. External Links: Document Cited by: Remark 9.9.
A. Lucas (2014) Ising formulations of many NP problems. Frontiers in Physics 2, pp. 5. External Links: Document Cited by: §9.3.1.
I. D. Mayergoyz (1991) Mathematical models of hysteresis. Springer, New York. External Links: Document Cited by: item 4, Proposition 2.4, Proposition 2.5.
W. Merrill and A. Sabharwal (2023) The parallelism tradeoff: limitations of log-precision transformers. Transactions of the Association for Computational Linguistics 11, pp. 531–545. External Links: Document Cited by: §8.
M. Mézard and A. Montanari (2009) Information, physics, and computation. Oxford University Press, Oxford. External Links: Document Cited by: §9.3.3.
B. Peng, E. Alcaide, Q. Anthony, A. Albalak, S. Arcadinho, S. Biderman, et al. (2023) RWKV: reinventing RNNs for the transformer era. In Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 14048–14077. External Links: Document Cited by: §8.
J. Pérez, J. Marinković, and P. Barceló (2021) Attention is Turing complete. Journal of Machine Learning Research 22 (75), pp. 1–35. External Links: Link Cited by: item 2, §1, §2.3, §4.2, §8.
F. Preisach (1935) Über die magnetische Nachwirkung. Zeitschrift für Physik 94 (5–6), pp. 277–302. External Links: Document Cited by: §1, §2.1.
J. P. Sethna, K. A. Dahmen, and O. Perkovic (2006) Random-field ising models of hysteresis. The Science of Hysteresis 2, pp. 107–179. External Links: Link Cited by: §9.1, §9.4, Remark 9.2.
N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton, and J. Dean (2017) Outrageously large neural networks: the sparsely-gated mixture-of-experts layer. In International Conference on Learning Representations, External Links: Link Cited by: §1.
H. T. Siegelmann and E. D. Sontag (1995) On the computational power of neural nets. Journal of Computer and System Sciences 50 (1), pp. 132–150. External Links: Document Cited by: §1.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin (2017) Attention is all you need. In Advances in Neural Information Processing Systems, Vol. 30. Cited by: §1.
J. von Oswald, E. Niklasson, E. Randazzo, J. Sacramento, A. Mordvintsev, A. Zhmoginov, and M. Vladymyrov (2023) Transformers learn in-context by gradient descent. In International Conference on Machine Learning, Vol. 202, pp. 35151–35174. Cited by: §1.
M. Zaheer, G. Guruganesh, K. A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, et al. (2020) Big Bird: transformers for longer sequences. In Advances in Neural Information Processing Systems, Vol. 33, pp. 17283–17297. Cited by: Appendix C, §8.

Appendix A Full Proof of Theorem 6.2: PAL corresponds to EFO

We prove Theorem 6.2 by structural induction on EFO formula complexity, establishing a constructive correspondence between EFO formulae and PAL-Transformer computations.

A.1 Formal Setup

We work over sequences $\mathbf{x}=(x_{0},x_{1},\ldots,x_{n})$ where each $x_{i}\in\mathbb{R}^{d}$ . Let $\mathcal{E}(\mathbf{x})=\{i:x_{i}\text{ is a local extremum of }\|x_{i}\|_{2}\}$ denote the set of extremal positions of $\mathbf{x}$ .

Definition A.1 (EFO syntax).

The grammar of Extremum First-Order Logic (EFO) over sequences is:

	$\displaystyle\phi$	$\displaystyle::=\top\mid\bot\mid u_{i}\leq c\mid u_{i}\geq c\mid i<_{\mathrm{ext}}j\mid\phi\wedge\psi\mid\phi\vee\psi\mid\neg\phi$
		$\displaystyle\quad\mid\exists^{\mathrm{ext}}i\,\phi(i)\mid\forall^{\mathrm{ext}}i\,\phi(i)\mid\mathrm{ExtAgg}_{i}[f(i),\phi(i)]$

where $c\in\mathbb{R}$ is a constant, $i$ ranges over extremal positions only, $i<_{\mathrm{ext}}j$ denotes that extremal position $i$ occurred before extremal position $j$ in the sequence, and $\mathrm{ExtAgg}_{i}[f(i),\phi(i)]$ denotes:

\mathrm{ExtAgg}_{i}[f(i),\phi(i)]\;=\;\sum_{i\in\mathcal{E}(\mathbf{x}),\;\phi(i)\text{ holds}}f(x_{i}),

(25)

where $f:\mathbb{R}^{d}\to\mathbb{R}$ is a measurable function. The ordering relation $<_{\mathrm{ext}}$ is needed to express the causal order of relay state changes, since the relay state at time $n$ depends on which of the activation and deactivation thresholds was crossed most recently.

Definition A.2 (EFO semantics).

A sequence $\mathbf{x}$ satisfies $\phi$ (written $\mathbf{x}\models\phi$ ) according to the standard first-order semantics restricted to extremal positions:

•

$\mathbf{x}\models u_{i}\geq c$ iff $x_{i}\geq c$ for the current assignment of $i$ .
•

$\mathbf{x}\models\exists^{\mathrm{ext}}i\,\phi(i)$ iff there exists $i\in\mathcal{E}(\mathbf{x})$ such that $\mathbf{x}\models\phi(i)$ .
•

Boolean connectives have their standard meaning.
•

$\mathrm{ExtAgg}_{i}[f(i),\phi(i)]$ sums $f(x_{i})$ over extremal positions satisfying $\phi$ .

A.2 The Correspondence

We establish a bijection between EFO formulae and PAL computations by defining a compilation map $\llbracket\cdot\rrbracket:\mathrm{EFO}\to\mathrm{PAL\text{-}Transformer}$ .

Lemma A.3 (Extremal position indicator).

The indicator $\mathbf{1}[i\in\mathcal{E}(\mathbf{x})]$ is computable by a single-head PAL as:

\mathbf{1}[i\in\mathcal{E}(\mathbf{x})]=\hat{\gamma}_{\alpha_{i}+\varepsilon\alpha_{i}-\varepsilon}[u](i)-\hat{\gamma}_{\alpha_{i}+\varepsilon\alpha_{i}-\varepsilon}[u](i-1),

(26)

where $u_{j}=\|x_{j}\|_{2}$ is the scalar projection of the sequence (one specific scalarisation; any injective $\phi:\mathbb{R}^{d}\to\mathbb{R}$ suffices for the lemma to hold). That is, the relay changes state at step $i$ if and only if $u_{i}$ is a local extremum.

Proof.

By Definition 2.1, the relay $\hat{\gamma}_{\alpha_{i}+\varepsilon\alpha_{i}-\varepsilon}[u](i)$ changes from 0 to 1 at step $i$ iff $u_{i}\geq\alpha_{i}+\varepsilon$ , and from 1 to 0 iff $u_{i}\leq\alpha_{i}-\varepsilon$ . In both cases, a state change occurs exactly when $u_{i}$ crosses one of the thresholds, which — by choice of $\alpha_{i}=u_{i}$ and $\varepsilon\to 0$ — happens exactly at local extrema. The difference (26) detects this state change. ∎

Lemma A.4 (Threshold comparison).

The formula $u_{i}\geq c$ at an extremal position $i$ is computable by a PAL with thresholds $\alpha=c+\varepsilon$ , $\beta=c-\varepsilon$ as:

\mathbf{1}[u_{i}\geq c]\;=\;\hat{\gamma}_{c+\varepsilon c-\varepsilon}[u](i).

(27)

Proof.

Direct from Definition 2.1: when the input $u_{i}$ crosses threshold $\alpha=c+\varepsilon$ , the relay switches to 1; when it falls below $\beta=c-\varepsilon$ , it switches to 0. In the limit $\varepsilon\to 0$ , this detects $u_{i}\geq c$ at each extremal step. ∎

Lemma A.5 (Boolean combinations via MLP).

Let $\phi_{1},\phi_{2}$ be two EFO formulae computable by PAL heads producing outputs $r_{1},r_{2}\in\{0,1\}$ . Then $\phi_{1}\wedge\phi_{2}$ , $\phi_{1}\vee\phi_{2}$ , and $\neg\phi_{1}$ are computable by a two-layer MLP applied to $(r_{1},r_{2})$ .

Proof.

Boolean functions on $\{0,1\}^{2}$ are representable by two-layer networks with ReLU activations (Cybenko 1989):

	$\displaystyle r_{1}\wedge r_{2}$	$\displaystyle=\mathrm{ReLU}(r_{1}+r_{2}-1),$
	$\displaystyle r_{1}\vee r_{2}$	$\displaystyle=\mathrm{ReLU}(r_{1}+r_{2})-\mathrm{ReLU}(r_{1}+r_{2}-1),$
	$\displaystyle\neg r_{1}$	$\displaystyle=1-r_{1}.$

These are exact (not approximate) representations on $\{0,1\}$ . ∎

Lemma A.6 (Extremum aggregation).

The formula $\mathrm{ExtAgg}_{i}[f(x_{i}),\phi(i)]$ is computable by a single MPAL head with measure:

\mu_{(\alpha,\beta)}=f(\operatorname{Dec}(\alpha,\beta))\cdot\mathbf{1}[\phi\text{ holds at }(\alpha,\beta)],

(28)

where $\operatorname{Dec}(\alpha,\beta)$ recovers the value $x_{i}$ encoded at thresholds $(\alpha,\beta)$ .

Proof.

The MPAL output for a single head with measure $\mu$ is:

\operatorname{PAL}_{\mu}(u_{0:n})=\sum_{i\geq j}\mu_{ij}\cdot\hat{\gamma}_{\alpha_{i}\beta_{j}}[u](n).

At time $n$ , $\hat{\gamma}_{\alpha_{i}\beta_{j}}[u](n)=1$ if and only if the current extremum stack $\Pi_{n}$ contains a pair $(M,m)$ with $M\in(\alpha_{i}-\varepsilon,\alpha_{i}+\varepsilon)$ and $m\in(\beta_{j}-\varepsilon,\beta_{j}+\varepsilon)$ , i.e. the relay encodes an active extremal position satisfying the threshold condition.

Setting $\mu_{ij}=f(\operatorname{Dec}(\alpha_{i},\beta_{j}))\cdot\mathbf{1}[\phi$ holds at $(i,j)]$ makes the PAL output equal to (25), since the relay sums over exactly those extremal positions where $\phi$ holds, weighted by $f$ . ∎

Lemma A.7 (Existential extremal quantification).

The formula $\exists^{\mathrm{ext}}i\,\phi(i)$ is computable by a PAL followed by a threshold MLP:

\mathbf{x}\models\exists^{\mathrm{ext}}i\,\phi(i)\;\iff\;\mathrm{ReLU}\!\left(\mathrm{ExtAgg}_{i}[\mathbf{1},\phi(i)]\right)>0.

(29)

Proof.

$\mathrm{ExtAgg}_{i}[\mathbf{1},\phi(i)]$ counts the number of extremal positions satisfying $\phi$ . This is positive iff at least one such position exists, which is exactly the semantics of $\exists^{\mathrm{ext}}i$ . The threshold $>0$ is implemented by a ReLU followed by a Heaviside (approximated to arbitrary precision by a steep sigmoid, exact under unit-cost arithmetic). ∎

A.3 Inductive Proof of Theorem 6.2

Proof of Theorem 6.2.

We prove both directions by structural induction on EFO formula complexity.

( $\Rightarrow$ ) Every PAL-computable function is EFO-definable.

We show that every primitive PAL operation corresponds to an EFO formula.

Base case — single relay: We show $\hat{\gamma}_{\alpha\beta}[u](n)$ is EFO-definable. By the wiping property (proposition˜2.4) and stack sufficiency (proposition˜2.7), the relay state at time $n$ is determined entirely by the most recent state-changing extremum. Specifically, $\hat{\gamma}_{\alpha\beta}[u](n)=1$ iff there exists an extremal position $t^{*}\leq n$ at which the relay was activated ( $u_{t^{*}}\geq\alpha$ ), and no subsequent extremal position $t\in(t^{*},n]$ deactivated it ( $u_{t}\leq\beta$ ). This is expressed in EFO with ordering as:

\hat{\gamma}_{\alpha\beta}[u](n)=1\;\iff\;\exists^{\mathrm{ext}}t^{*}\leq n\;\Bigl[u_{t^{*}}\geq\alpha\;\wedge\;\forall^{\mathrm{ext}}t:t^{*}<_{\mathrm{ext}}t\;\Rightarrow\;u_{t}>\beta\Bigr].

(30)

The existential quantifier ranges over extremal positions by definition˜A.1; the comparison $u_{t^{*}}\geq\alpha$ is atomic; the ordering $t^{*}<_{\mathrm{ext}}t$ uses the causal order in EFO; and $u_{t}>\beta$ is atomic. Hence (30) is an EFO formula.

Inductive case — weighted sum: $\operatorname{PAL}_{\mu}(u_{0:n})=\sum_{i\geq j}\mu_{ij}\hat{\gamma}_{\alpha_{i}\beta_{j}}[u](n)$ is a weighted sum of relay states. By the inductive hypothesis each $\hat{\gamma}_{\alpha_{i}\beta_{j}}$ is EFO-definable; their weighted sum is $\mathrm{ExtAgg}_{i}[\mu\cdot\hat{\gamma}_{\cdot\cdot},\top]$ , which is EFO by Definition A.1.

MLP layers: MLP computes Boolean combinations (Lemma A.5) and threshold functions of PAL outputs, all of which are EFO-definable by induction.

Multi-head composition: The MPAL output is a sum of single-head PAL outputs; EFO is closed under addition (as a special case of $\mathrm{ExtAgg}$ ).

By induction, the entire PAL-Transformer output is EFO-definable.

( $\Leftarrow$ ) Every EFO formula is PAL-computable.

We show that each EFO construct is implementable by a PAL component.

Atomic formula $u_{i}\geq c$ : Implemented by Lemma A.4 with $\alpha=c+\varepsilon$ , $\beta=c-\varepsilon$ .

Boolean combinations: Implemented by Lemma A.5.

Existential quantification $\exists^{\mathrm{ext}}i\,\phi(i)$ : Implemented by Lemma A.7.

Universal quantification $\forall^{\mathrm{ext}}i\,\phi(i)$ : Equivalent to $\neg(\exists^{\mathrm{ext}}i\,\neg\phi(i))$ , implementable by Lemmas A.5 and A.7.

Extremum aggregation $\mathrm{ExtAgg}_{i}[f(i),\phi(i)]$ : Implemented by Lemma A.6 with measure $\mu_{ij}=f(\operatorname{Dec}(\alpha_{i},\beta_{j}))\cdot\mathbf{1}[\phi$ holds at $(i,j)]$ .

Nested formulae: Suppose $\phi=\mathrm{ExtAgg}_{i}[f(i),\psi(i)]$ where $\psi$ is an EFO formula. By the inductive hypothesis, $\psi$ is implementable by a PAL sub-computation producing output $r_{i}\in\{0,1\}$ for each extremal position $i$ . Then $\mathrm{ExtAgg}_{i}[f(i),\psi(i)]$ is implemented by a PAL head with measure $\mu_{ij}=f(\operatorname{Dec}(\alpha_{i},\beta_{j}))\cdot r_{ij}$ , where $r_{ij}$ is the output of the sub-computation. This composes PAL layers — at most one additional layer per level of nesting.

By induction on formula depth, every EFO formula is implementable by a PAL-Transformer with depth proportional to the nesting depth of $\mathrm{ExtAgg}$ operators. ∎

A.4 Corollaries of the EFO Correspondence

Corollary A.8 (Decidability of PAL expressiveness).

Given a function $f:\mathbb{R}^{n+1}\to\mathbb{R}$ , deciding whether $f\in\mathcal{F}_{\operatorname{PAL}}$ reduces to deciding whether $f$ is EFO-definable, which is decidable for functions over finite alphabets by standard model-theoretic methods.

Corollary A.9 (EFO $\subsetneq$ FO + Aggregate).

$\mathrm{EFO}$ is strictly contained in $\mathrm{FO}+\mathrm{Aggregate}$ (the logic corresponding to soft-attention transformers (Barceló et al., 2020)):

\mathrm{EFO}\subsetneq\mathrm{FO}+\mathrm{Aggregate}.

The strict inclusion is witnessed by $f_{\mathrm{copy}}(x_{0:n},p)=x_{p}$ : definable in $\mathrm{FO}$ with positional quantification $\exists i\,(i=p)$ , but not in $\mathrm{EFO}$ (which cannot quantify over non-extremal positions). The reverse inclusion fails because $f_{\mathrm{range}}$ is definable in $\mathrm{EFO}$ but not in bounded-depth $\mathrm{FO}+\mathrm{Aggregate}$ (Proposition 5.3).

Corollary A.10 (PAL depth vs. formula nesting).

A $k$ -layer PAL-Transformer implements EFO formulae of nesting depth at most $k$ . Conversely, an EFO formula of nesting depth $k$ requires at most $k$ PAL layers. This gives a precise depth-expressiveness tradeoff: depth $k$ PAL $\equiv$ EFO-depth $k$ .

Appendix B Auxiliary Lemmas for Section 4

B.1 Correctness of Stack Encoding under Repeated Symbols

Here we verify that the Cantor-depth encoding (Definition 4.1) handles stacks with repeated symbols correctly across all three operations.

Lemma B.1 (POP removes exactly one element).

Under the Cantor-depth encoding, the POP signal $u_{n+1}=M_{\mathrm{top}-1}+2\varepsilon$ removes exactly the topmost pair $(M_{\mathrm{top}},m_{\mathrm{top}})$ and no other.

Proof.

The wiping property removes all pairs $(M_{i},m_{i})$ with $M_{i}<u_{n+1}=M_{\mathrm{top}-1}+2\varepsilon$ . Since $M_{\mathrm{top}}<M_{\mathrm{top}-1}$ (strict monotonicity), we have $M_{\mathrm{top}}<M_{\mathrm{top}-1}+2\varepsilon$ , so the pair $(M_{\mathrm{top}},m_{\mathrm{top}})$ is wiped. Since $M_{\mathrm{top}-1}<M_{\mathrm{top}-1}+2\varepsilon$ implies $M_{\mathrm{top}-1}$ is not less than $u_{n+1}$ , the pair $(M_{\mathrm{top}-1},m_{\mathrm{top}-1})$ is preserved. (More precisely, wiping removes $M_{i}<u_{n+1}$ ; $M_{\mathrm{top}-1}<M_{\mathrm{top}-1}+2\varepsilon=u_{n+1}$ is vacuously false since we check strict inequality.) Hence exactly one pair is removed. ∎

Lemma B.2 (PUSH does not trigger wiping).

Under the Cantor-depth encoding, the PUSH signal $u_{n+1}=\mathrm{code}^{*}(a_{i},d+1)+\varepsilon$ does not trigger the wiping property.

Proof.

By Lemma 4.2, $\mathrm{code}^{*}(a_{i},d+1)<\mathrm{code}^{*}(a_{j},d)$ for all $j\in\{1,\ldots,k\}$ . Therefore $u_{n+1}=\mathrm{code}^{*}(a_{i},d+1)+\varepsilon<M_{\mathrm{top}}$ (since $M_{\mathrm{top}}=\mathrm{code}^{*}(a_{j},d)+\varepsilon$ for some $j$ and the $\varepsilon$ gap is smaller than the inter-level gap $\Delta>0$ , provided $\varepsilon<\Delta/2$ ). Since $u_{n+1}<M_{\mathrm{top}}$ , the wiping condition $u_{n+1}>M_{\mathrm{top}}$ is not satisfied. A new pair is added without removing any existing pairs. ∎

B.2 MLP Width for Transition Function

Lemma B.3 (MLP width for finite transition functions).

For a 2-PDA with $|Q|$ states, input alphabet $|\Sigma|$ , and stack alphabet $|\Gamma|$ , the transition function $\delta:Q\times\Sigma\times\Gamma\times\Gamma\to Q\times\Gamma^{*}\times\Gamma^{*}$ is implementable by a two-layer MLP of width $O(|Q|\cdot|\Sigma|\cdot|\Gamma|^{2})$ .

Proof.

$\delta$ has domain of size $|Q|\cdot|\Sigma|\cdot|\Gamma|^{2}$ and is a finite lookup table. By the universal approximation theorem (Cybenko, 1989), any function on a finite domain of size $N$ is exactly representable by a two-layer network with $N$ hidden units through a table-lookup construction: for each input configuration $(q,a,s_{1},s_{2})$ , one hidden neuron fires for that configuration (indicator neuron) and outputs the corresponding transition values. Width: one neuron per table entry $=O(|Q|\cdot|\Sigma|\cdot|\Gamma|^{2})$ . ∎

Appendix C Relation to Sparse Attention

PAL can be viewed as a form of content-adaptive sparse attention where the sparsity pattern is determined by the sequence of local extrema rather than by position (sliding window) or random selection (BigBird (Zaheer et al., 2020)).

Proposition C.1 (PAL as extremal sparse attention).

PAL implements attention over the set of extremal positions:

\operatorname{PAL}_{\mu}(u_{0:n})=\sum_{i\in\mathcal{E}(u_{0:n})}a_{i}\cdot v_{i},

(31)

where $a_{i}=\mu_{(\alpha(u_{i}),\beta(u_{i-1}))}$ is a content-determined weight and $v_{i}=\hat{\gamma}_{\alpha(u_{i})\cdot}$ is the relay value. The attention mask is $\{i:i\in\mathcal{E}(u_{0:n})\}$ , which is determined by the input content, not position.

Proof.

At time $n$ , the PAL output sums over relay pairs $(i,j)$ where the relay is active. A relay $\hat{\gamma}_{\alpha_{i}\beta_{j}}$ is active at time $n$ only if the most recent state change was an activation at some extremal position $t^{*}\leq n$ with $u_{t^{*}}\geq\alpha_{i}$ . This is equivalent to attending to extremal positions, with weights given by the measure $\mu$ . ∎

This framing positions PAL as a principled alternative to heuristic sparse attention patterns: the sparsity is not imposed externally but emerges naturally from the structure of the Preisach operator.

Preisach Attention: A Hysteretic Model of Sequential Memory

Abstract

1 Introduction

This paper.

Main contributions.

2 Background

2.1 The Preisach Hysteresis Operator

Definition 2.1 (Elementary relay).

Definition 2.2 (Preisach operator).

Proposition 2.3 (Rate-independence (Brokate and Sprekels, 1996)).

Proposition 2.4 (Wiping property (Mayergoyz, 1991)).

Proposition 2.5 (Universal approximation (Mayergoyz, 1991)).

2.2 The Extremum Stack

Definition 2.6 (Extremum stack).

Proposition 2.7 (Stack sufficiency).

Proposition 2.8 (Stack update complexity).

2.3 Transformer Attention

3 Preisach Attention Layer

3.1 Definition

Definition 3.1 (Preisach Attention Layer).

Definition 3.2 (Multi-head PAL).

Definition 3.3 (PAL-Transformer).

3.2 Connection to Classical Preisach Operator

Proposition 3.4 (PAL as discretised Preisach).

3.3 Relationship to Standard Attention

Proposition 3.5 (Attention as continuous relaxation of PAL).

4 Turing Completeness

4.1 Encoding Alphabet Symbols in the Extremum Stack

Definition 4.1 (Cantor-depth encoding).

Lemma 4.2 (Strict monotonicity).

Proof.

Lemma 4.3 (Stack operations via signal generation).

Proof.

4.2 Main Theorem

Definition 4.4 (Autoregressive PAL-Transformer).

Lemma 4.5 (Multi-head PAL decodes the extremum stack).

Proof.

Theorem 4.6 (Turing completeness of PAL-Transformer).

Proof.

Channel 1 — Machine state.

Channel 2 — Stack 1.

Channel 3 — Stack 2.

Channel 4 — Input tape.

Simulation step n→n+1n\to n+1.

Correctness.

Depth.

Precision.

Corollary 4.7 (Depth separation from Transformer).

Corollary 4.8 (Vector PAL is TC with a single head).

Proof.

Remark 4.9 (Differentiability and practical training).

Remark 4.10 (Position encoding and rate-independence).

Remark 4.11 (Heads vs. signal dimensions as exchangeable resources).

5 Expressiveness Separation

Theorem 5.1 (Expressiveness incomparability).

5.1 Functions PAL computes but Transformer cannot (at bounded depth)

Proposition 5.2 (Historical range in O​(1)O(1) layers).

Proof.

Proposition 5.3 (Transformer requires Ω​(log⁡n)\Omega(\log n) layers for range).

Proof.

5.2 Functions Transformer computes but PAL cannot

Proposition 5.4 (Random-access retrieval).

Proof.

Proposition 5.5 (PAL cannot perform exact random access).

Proof.

Construction.

Extremum stacks are identical.

Rate-independence forces identical outputs.

Remark 5.6 (Why the probabilistic argument is incorrect).

5.3 The separating property: rate-independence

Theorem 5.7 (Rate-independence as separating property).

Proof.

6 Logical Characterisation

Definition 6.1 (Extremum First-Order Logic, EFO\mathrm{EFO}).

Theorem 6.2 (PAL corresponds to EFO).

Proof sketch..

Remark 6.3 (Comparison with FO + Aggregate).

7 Computational Complexity

Theorem 7.1 (Complexity of PAL inference).

Predicted task advantages.

Simulation step $n\to n+1$ .

Proposition 5.2 (Historical range in $O(1)$ layers).

Proposition 5.3 (Transformer requires $\Omega(\log n)$ layers for range).

Definition 6.1 (Extremum First-Order Logic, $\mathrm{EFO}$ ).

( $\Rightarrow$ ) Every PAL-computable function is EFO-definable.

( $\Leftarrow$ ) Every EFO formula is PAL-computable.

Corollary A.9 (EFO $\subsetneq$ FO + Aggregate).