Preprint
Preisach Attention: A Hysteretic Model of Sequential Memory Piotr Frydrych The Metrology and Biomedical Engineering Institute Faculty of Mechatronics, Warsaw University of Technology [email protected]
arXiv:2605.23603v1 [cs.LG] 22 May 2026
Preprint.
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 γ̂αβ parameterised by learned activation and deactivation thresholds (α, β), 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(n2 ) for standard attention.
Keywords: Preisach operator, hysteresis, attention mechanism, Turing completeness, expressiveness, sequence modelling, long-range dependence, rate-independence.
1
Preprint
Contents 1
Introduction
4
2
Background
5
2.1
The Preisach Hysteresis Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2
The Extremum Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3
Transformer Attention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
3
4
5
Preisach Attention Layer
6
3.1
Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2
Connection to Classical Preisach Operator . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.3
Relationship to Standard Attention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Turing Completeness
7
4.1
Encoding Alphabet Symbols in the Extremum Stack . . . . . . . . . . . . . . . . . . . . . .
7
4.2
Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Expressiveness Separation
10
5.1
Functions PAL computes but Transformer cannot (at bounded depth) . . . . . . . . . . . . .
10
5.2
Functions Transformer computes but PAL cannot . . . . . . . . . . . . . . . . . . . . . . .
10
5.3
The separating property: rate-independence . . . . . . . . . . . . . . . . . . . . . . . . . .
11
6
Logical Characterisation
11
7
Computational Complexity
12
8
Related Work
13
9
Connection to the Random-Field Ising Model
13
9.1
The Preisach–RFIM Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
9.2
PAL as a Learned, Sequential RFIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
9.3
Problems where PAL Inherits Ising Expressiveness . . . . . . . . . . . . . . . . . . . . . .
14
9.3.1
Sequential Binary Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
9.3.2
Associative Memory with Structured Forgetting . . . . . . . . . . . . . . . . . . . .
15
9.3.3
Sequential Belief Propagation in Markov Random Fields . . . . . . . . . . . . . . .
16
9.4
Avalanches and Phase Transitions in PAL . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
9.5
Summary: PAL vs. Ising-based Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
10 Conclusion
17
2
Preprint
A Full Proof of Theorem 6.2: PAL corresponds to EFO
20
A.1 Formal Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
A.2 The Correspondence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
A.3 Inductive Proof of Theorem 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
A.4 Corollaries of the EFO Correspondence . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
B Auxiliary Lemmas for Section 4
23
B.1 Correctness of Stack Encoding under Repeated Symbols . . . . . . . . . . . . . . . . . . .
23
B.2 MLP Width for Transition Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
C Relation to Sparse Attention
24
3
Preprint
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 γ̂αβ , each characterised by an activation threshold α and a deactivation threshold β, weighted by a learned measure µ(α, β) 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 µ ∈ L2 (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.
4
Preprint
2
Background
2.1
The Preisach Hysteresis Operator
The Preisach operator (Preisach, 1935) was introduced to model magnetic hysteresis in ferromagnetic materials. Let T = {(α, β) ∈ R2 : α ≥ β} be the Preisach half-plane. Definition 2.1 (Elementary relay). For (α, β) ∈ T and input sequence u = (u0 , u1 , . . .) ∈ RN , the elementary relay γ̂αβ [u] : N → {0, 1} is defined by: if un ≥ α, 1 γ̂αβ [u](n) = 0 (1) if un ≤ β, γ̂αβ [u](n − 1) otherwise. The interval (β, α) is the dead band of the relay. Definition 2.2 (Preisach operator). Let µ ∈ L1 (T ) be a signed measure on T . The Preisach operator Pµ : RN → RN is: ZZ Pµ [u](n) = γ̂αβ [u](n) µ(α, β) dα dβ. (2) T
The Preisach operator has three properties central to this paper. Proposition 2.3 (Rate-independence (Brokate and Sprekels, 1996)). For any non-decreasing bijection ϕ : [0, T ] → [0, T ], Pµ [u ◦ ϕ] = Pµ [u] ◦ ϕ. Proposition 2.4 (Wiping property (Mayergoyz, 1991)). Let Mi > mi > Mi+1 > mi+1 > . . . be the alternating local maxima and minima of u. If Mi+1 > Mi , then the relay state induced by Mi is erased — the output Pµ [u] after Mi+1 is identical to what it would be had Mi not occurred. Proposition 2.5 (Universal approximation (Mayergoyz, 1991)). The set {Pµ : µ ∈ L2 (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 u0:n is the sequence: Πn = [(M1 , m1 ), (M2 , m2 ), . . . , (Mk , mk )]
(3)
of alternating local maxima M1 > M2 > . . . > Mk and local minima m1 > m2 > . . . > mk , stored in decreasing order, where the pair (Mi , mi ) records the i-th local maximum and its subsequent local minimum. Proposition 2.7 (Stack sufficiency). Pµ [u](n) is a measurable function of Πn alone. In particular, two sequences u and v with identical extremum stacks Πun = Πvn satisfy Pµ [u](n) = Pµ [v](n) for all µ. 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 ≤ n is the current stack depth. The relay state γ̂αβ [u](n) can be read from Πn in O(log k) time by binary search. 2.3
Transformer Attention
For completeness we recall standard definitions. Given query q ∈ Rd , keys K ∈ Rn×d and values V ∈ Rn×d , scaled dot-product attention is: qK ⊤ Attn(q, K, V ) = softmax √ V. (4) d Hard attention replaces softmax with argmax: aj = 1[j = arg maxi q · ki ]. 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. 5
Preprint
Algorithm 1 Extremum Stack Update Require: Current stack Πn , new observation un+1 , previous observation un Ensure: Updated stack Πn+1 1: if un+1 > un then ▷ Input rises: update maxima 2: while Πn ̸= ∅ and Mtop < un+1 do 3: mlast ← mtop ▷ Save last minimum before popping 4: pop(Πn ) ▷ Wiping 5: end while 6: push(Πn , (un+1 , mlast )) ▷ New maximum with last surviving minimum 7: else if un+1 < un then ▷ Input falls: update minima 8: while Πn ̸= ∅ and mtop > un+1 do 9: Mlast ← Mtop ▷ Save last maximum before popping 10: pop(Πn ) ▷ Wiping 11: end while 12: push(Πn , (Mlast , un+1 )) ▷ New minimum with last surviving maximum 13: end if 14: return Πn+1 ← Πn
3
Preisach Attention Layer
3.1
Definition
Definition 3.1 (Preisach Attention Layer). Let u0:n ∈ Rn+1 be a scalar input sequence and µ = {µij }i≥j ∈ RL×L a discretised measure on the grid GL = {(αi , βj ) : i ≥ j, i, j ∈ {1, . . . , L}} with αi = i∆, βj = j∆. The Preisach Attention Layer is: X PALµ (u0:n ) = µij · γ̂αi βj [u](n) ∈ R. (5) i≥j
Definition 3.2 (Multi-head PAL). Let x0:n ∈ R(n+1)×d be a vector-valued sequence. Multi-head PAL with H heads is: H X (h) (h) MPAL(x0:n ) = WO · PALµ(h) WI x0:n ∈ Rd , (6) h=1 (h) where WI
(h)
1×d
∈ R projects to a scalar signal and WO ∈ Rd projects back to the model dimension. The scalar projection is a simplifying assumption of the present work; Section 10 discusses the vector exten(h) sion (vPAL) where WI ∈ R2×d and the measure µ is defined over the three-dimensional space (α, β, θ) following Frydrych (2019). Definition 3.3 (PAL-Transformer). An L-layer PAL-Transformer is defined by: zn(0) = xn + PE(n), (l−1) zn(l) = LN zn(l−1) + MPAL(l) (z0:n ) , zn(l) = LN zn(l) + MLP(l) (zn(l) ) ,
(7) (8) (9)
where PE is sinusoidal position encoding, LN is layer normalisation, and MLP(l) is a two-layer network with ReLU. 3.2
Connection to Classical Preisach Operator
Proposition 3.4 P (PAL as discretised Preisach). PALµ (u0:n ) is the discretised Preisach operator Pµ∆ [u](n) where µ∆ = i≥j µij δ(αi ,βj ) is an atomic measure concentrated on the grid GL . As L → ∞ and ∆ → 0 with L∆ = C fixed, PALµ → Pµ uniformly on C([0, C]) by theorem 2.5. 6
Preprint
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 γ̂αβ [u](n) ∈ {0, 1} is replaced by the soft weight aj = softmax(q · kj / d) ∈ (0, 1), 2. The measure µ(α, β) is replaced by the value matrix V , 3. Rate-independence is broken: attention depends on absolute position through q ·kj , 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 Γ = {a1 , . . . , ak } be a stack alphabet, Dmax a depth bound, ∆ > 0 a resolution parameter, and Cmax = Dmax (k + 1)∆. The Cantor-depth encoding is: code∗ (ai , d) = Cmax − [d(k + 1) + i]∆,
i ∈ {1, . . . , k}, d ∈ {0, . . . , Dmax }.
(10)
Lemma 4.2 (Strict monotonicity). For all i, i′ ∈ {1, . . . , k} and d ≥ 0: code∗ (ai′ , d + 1) < code∗ (ai , d). Proof. code∗ (ai , d) − code∗ (ai′ , d + 1) = [(d + 1)(k + 1) + i′ − d(k + 1) − i]∆ = [(k + 1) + i′ − i]∆ ≥ [(k + 1) − k]∆ = ∆ > 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: PUSH(ai ) :
un+1 = code∗ (ai , d + 1) + ε,
POP :
un+1 = Mtop−1 + 2ε,
TOP :
read ai = Dec(Mtop ),
un+2 = code∗ (ai , d + 1) − ε,
(11) (12)
no signal emitted.
(13)
Proof. PUSH: By theorem 4.2, code∗ (ai , d + 1) < code∗ (aj , d) = Mtop for all j, so un+1 = code∗ (ai , d + 1) + ε < Mtop . The wiping condition (un+1 > Mtop ) is not triggered; a new pair (Md+1 , md+1 ) is added to the stack top. POP: Since Mtop−1 > Mtop (strict monotonicity of stack), un+1 > Mtop triggers wiping, removing (Mtop , mtop ). The signal un+1 itself satisfies un+1 = Mtop−1 + 2ε < Mtop−2 (if depth ≥ 3), so only one pair is removed. TOP: Dec(Mtop ) = ai where i = ⌊(Cmax − Mtop )/∆⌋ mod (k + 1), which is a deterministic function of Mtop 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 theorem 3.3. In the autoregressive regime: 1. At step n, the PAL-Transformer receives the current input token xn (which may itself be a function of previous outputs) and produces output zn .
7
Preprint
(1:4)
2. A component of zn — specifically, the signal channels un+1 — is appended as the next input token xn+1 , creating a closed generative loop. (1:4)
3. The extremum stacks Πn maintained.
persist across steps as the sole recurrent state; no other hidden state is
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 (theorem 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 Πn of depth at most k over a discretised alphabet of size K = (k + 1)|Γ|, there exist measures µ(1) , . . . , µ(H) with H = ⌈log2 K⌉ heads such that the map ϕ : Πn 7→ PALµ(1) (u0:n ), . . . , PALµ(H) (u0:n ) ∈ {0, 1}H (14) is injective. In particular, Mtop (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 (theorem 4.1), each stack element ai at depth d has a unique scalar value code∗ (ai , d) = Cmax − [d(k + 1) + i]∆. The total number of distinct values is K = (Dmax + 1)(k + 1), each separated by ∆ > 0. (h)
Construct H = ⌈log2 K⌉ PAL heads with indicator measures: µij = bh (index(i, j)), where index(i, j) maps threshold pair (αi , βj ) to the corresponding Cantor-depth code, and bh (·) extracts the h-th bit of the binary representation of that code. P (h) Each head h outputs PALµ(h) = ij µij γ̂αi β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 Mtop 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 theorem 4.3). Theorem 4.6 (Turing completeness of PAL-Transformer). For any two-stack pushdown automaton M = (Q, Σ, Γ, δ, q0 , Z0 , F ), there exists a single-layer PAL-Transformer T with H = 4 MPAL heads, one MLP layer, and arithmetic precision O(log(n · |Γ|)) bits that simulates M step-by-step on inputs of length n. Proof. We construct T with four independent signal channels u(1) , u(2) , u(3) , u(4) , each processed by a dedicated MPAL head. (1)
Channel 1 — Machine state. un = codeQ (qn ) encodes the current state qn ∈ Q as a scalar. Updated directly at each step by the MLP after computing δ. (2)
(2)
Channel 2 — Stack 1. u0:n encodes the contents of stack 1 via theorem 4.3. The extremum stack Πn is a bijective encoding of the stack-1 contents. Channel 3 — Stack 2.
(3)
u0:n encodes stack 2 analogously. (4)
Channel 4 — Input tape. u0:n encodes the input word; position encoding allows reading symbol xt at step (4) t via an MPAL head with WI tuned to isolate position t (cf. Pérez et al. (2021), Lemma 4).
8
Preprint
Simulation step n → n + 1.
At each step the PAL-Transformer performs: (1)
(2)
(2)
(3)
1. Read: qn ← Dec(head1 ), an ← head4 , sn ← TOP(Πn ), sn ← TOP(Πn ). (1)
(2)
2. Transition: (qn+1 , ops1 , ops2 ) ← MLPδ (qn , an , sn , sn ). The MLP implements δ by tabulation (finite domain, bounded width by Cybenko 1989). (2)
(3)
3. Write: Emit signals un+1 and un+1 per ops1 and ops2 via theorem 4.3. 4. Accept: MLPF checks qn+1 ∈ F , Π(2) = Z0 , Π(3) = Z0 . (2)
(3)
Correctness. By induction: at step n, stacks Πn and Πn faithfully encode the 2-PDA configuration (1) (2) (qn , s1:m1 , s1:m2 ). The base case is the initial configuration q0 , Z0 , Z0 . The inductive step follows from theorems 4.2 and 4.3. Since 2-PDA ≡ Turing machine (Hopcroft and Ullman, 1979), T is Turing-complete. Depth. of n.
The construction uses L = 1 MPAL layer and L = 1 MLP layer — total depth O(1), independent
Precision. Encoding depth d ≤ n and alphabet size k = |Γ| requires distinguishing values spaced ∆ apart up to Cmax = n(k + 1)∆, 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 Ω(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 WI ∈ R2×d , a single head (H = 1), one MLP layer, and arithmetic precision O(log(n · |Γ|)) bits is Turing-complete. Proof. The two-dimensional signal un = (uxn , uyn ) ∈ R2 admits two independent extremum stacks: Πyn = UpdateStack(Πyn−1 , uyn ).
Πxn = UpdateStack(Πxn−1 , uxn ),
(15)
We assign uxn to encode stack 1 of the 2-PDA and uyn to encode stack 2, both using the Cantor-depth encoding of theorem 4.1. The machine state qn ∈ Q and input tape are encoded in the angular structure of the vPAL measure µ(αx , βx , αy , βy , θ): distinct sectors θ ∈ [0, 2π) correspond to distinct states q ∈ 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 TOP(Πxn ) and TOP(Πyn ) simultaneously from the single vPAL head and computes the transition δ 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 WI ∈ R1×d with the vector projection WI ∈ R2×d . Remark 4.9 (Differentiability and practical training). The binary relay γ̂αβ is discontinuous in both the input un and the thresholds (α, β), making exact backpropagation undefined at switching points. Practical implementations require a smooth relaxation, e.g. the stateful sigmoid relaxation sn+1 = sn [1 − στ (β − un )]+(1−sn )στ (un −α) with temperature τ → 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 PE(n), which may appear to contradict rate-independence. The tension is deliberate: PE is used by the MLP layers (to implement positional logic, e.g. reading the input tape in the TC proof) but is not
9
Preprint
passed through the MPAL heads. The MPAL output itself — the integral over active relays — remains rateindependent. 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). theorem 4.8 formalises the intuition that in PAL, the number of heads H and the signal dimension du 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 · L2 parameters for the measure; a single H-dimensional vPAL head requires L2H parameters (the H-fold Cartesian product of Preisach halfplanes), 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 du = 2).
5
Expressiveness Separation
We prove the central incomparability result. Theorem 5.1 (Expressiveness incomparability). Let FPAL and FTr be the function classes computable by bounded-depth PAL-Transformer and Transformer respectively. Then: FPAL \ FTr ̸= ∅ 5.1
and
FTr \ FPAL ̸= ∅.
(16)
Functions PAL computes but Transformer cannot (at bounded depth)
Proposition 5.2 (Historical range in O(1) layers). The function frange (u0:n ) = maxi≤n ui − mini≤n ui is computable by a 1-layer PAL in O(1) time. Proof. M1 = maxi≤n ui and mk = mini≤n ui are directly readable from the extremum stack Πn as the first maximum and last minimum. frange = M1 − mk . Proposition 5.3 (Transformer requires Ω(log n) layers for range). Any transformer with O(1) layers and O(1) heads cannot compute frange exactly on sequences of length n. Proof. MAX over n values is not in AC0 (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 AC0 circuit (cf. Hahn (2020)), so it cannot compute MAX exactly. Since frange requires MAX as a subcomputation, the claim follows. 5.2
Functions Transformer computes but PAL cannot
Proposition 5.4 (Random-access retrieval). The function fcopy (x0:n , p) = xp (retrieve token at position p) is computable by a 1-layer hard-attention Transformer in O(1) layers. Proof. Set qn = PE(p) and kj = PE(j). Hard attention selects j ∗ = arg maxj qn · kj = p. The output is vp = xp . Proposition 5.5 (PAL cannot perform exact random access). No PAL-Transformer (of any depth or head count) can compute fcopy (x0:n , p) = xp for all sequences and positions. Proof. We give a structural impossibility proof based on rate-independence (theorems 2.3 and 5.7).
10
Preprint
Construction. Fix any target position p ∈ {1, . . . , n − 1} and any value v ̸= v ′ . Define two sequences that differ only at position p: x = (x0 , . . . , xp−1 , v, xp+1 , . . . , xn ),
(17)
′
(18)
′
x = (x0 , . . . , xp−1 , v , xp+1 , . . . , xn ),
where the surrounding values xp−1 and xp+1 satisfy xp−1 < min(v, v ′ ) < max(v, v ′ ) < xp+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 x or x′ . Therefore Πn (x) = Πn (x′ ): the extremum stacks are identical, because only positions j where uj 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 rateindependent function, hence a function of Πn alone (theorem 2.7). Since Πn (x) = Πn (x′ ), any PALTransformer outputs the same value on x and x′ . But fcopy (x, p) = v ̸= v ′ = fcopy (x′ , p). Therefore no PAL-Transformer computes fcopy . 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 Θ(1/n) for a random sequence, making fcopy 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 (up−1 , up , up+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 : Rn+1 → R is computable by a PAL-Transformer only if it is rate-independent in the sense of theorem 2.3. Standard attention computes functions that are not rate-independent. Hence rate-independence is a necessary condition for membership in FPAL and a sufficient condition for f ∈ / FTr \ FPAL . 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 aj = softmax(qn ·kj / d) depends explicitly on position through kj = WK (xj + PE(j)), so inserting a time-rescaling ϕ changes the output.
6
Logical Characterisation
Barceló et al. (2020) showed that soft-attention transformers correspond to 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, EFO). EFO is the extension of first-order logic over sequences with: 1. Quantification over extremal positions: ∃ext i ϕ(i) asserts that there exists a local extremum position i satisfying ϕ. 2. An extremum aggregate operator: ExtAggi [f (i)] sums f (i) over all extremal positions weighted by µ. 3. No quantification over arbitrary positions.
11
Preprint
Table 1: Complexity and expressiveness comparison. n = sequence length, d = model dimension, k ≤ n = extremum stack depth, du = signal dimension.
Architecture
Time (total)
Memory
Depth for TC
Transformer (softmax) Transformer (hard) Mamba / SSM RWKV PAL (scalar, du = 1) vPAL (vector, du = 2)
O(n2 d) O(n2 d) O(nd) O(nd) O(n log n · d) O(n log n · d)
O(nd) O(nd) O(d) O(d) O(kd) O(kd)
not TC O(log n) open open O(1) O(1)
Heads for TC — O(1) — — H=4 H=1
Theorem 6.2 (PAL corresponds to EFO). A function f : Σ∗ → R is computable by a bounded-depth PALTransformer if and only if it is definable in EFO. P Proof sketch. (⇒) Each MPAL head computes i:ui is extremum µij γ̂αi βj — an extremum aggregate. Composition through MLP layers corresponds to Boolean combinations of EFO formulae. (h)
(⇐) Each EFO formula can be implemented by appropriate choice of µ(h) and WI 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 EFO formula complexity; details in section A. Remark 6.3 (Comparison with FO + Aggregate). EFO ⊊ FO + Aggregate: EFO cannot quantify over arbitrary positions (no random access), while FO + Aggregate can. Conversely, EFO can express frange directly as ExtAgg[1[i = global max] · ui ] − ExtAgg[1[i = global min] · ui ], which has no bounded-depth 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 · log k · d) where k ≤ n is extremum stack depth, d model dimension. 2. Total time for sequence of length n: O(H · n log n · d). 3. Memory: O(H · k · d). Compare with standard attention: time O(n2 d), memory O(nd).
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).
12
Preprint
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 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 σi ∈ {−1, +1} with Hamiltonian: X J X σi σj − (hi + H)σi , H=− 2N i
(19)
i̸=j
where J > 0, H is a uniform external field, and {hi } are independent random fields drawn from distribution P(h). At T P = 0, each spin satisfies the single-spin stability condition: σi = sign(Jm + hi + H), where m = N −1 i σi is the mean magnetisation. Spin σi flips from −1 to +1 when H crosses the activation threshold αi = −hi − Jm from below, and flips back when H crosses the deactivation threshold βi = −hi + 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 Pµ [H] with measure: α+β µ(α, β) = P · δ(α − β − 2Jm) , (20) 2 where the measure is supported on the line α−β = 2Jm within the Preisach half-plane T . The magnetisation m(H) = Pµ [H] satisfies the self-consistency equation m = Pµ [H](t). Proof. Each spin i contributes a relay γ̂αi βi with αi − βi = 2Jm (the coupling gap). The output σi = 2γ̂αi βi [H] − 1 and the aggregate magnetisation: 1 X 1 X σi = 2 · γ̂αi βi [H] − 1 = 2Pµ [H] − 1, m= N i N i 13
Preprint
where µ is the empirical measure of threshold pairs, converging to (20) as N → ∞ by the law of large numbers applied to i.i.d. hi ∼ P. Remark 9.2 (Structural consequences). theorem 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 (theorem 2.4), and the extremum stack (theorem 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 Driving signal Disorder Coupling Dynamics Memory Wiping
fixed binary σi ∈ {−1, +1} quasi-static field H quenched {hi } ∼ P mean-field J/N equilibrium (lowest energy) return-point memory (history of H) return-point memory property
relay states rk ∈ {0, 1}, learned arbitrary sequence u0:n learned measure µ(α, β) implicit through self-consistency of µ causal, rate-independent extremum stack Πn theorem 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 u0: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: X X E(σ) = − Jij σi σj − hi σi , (21) i<j
i
and the goal is σ ∗ = arg min E. Proposition 9.3 (PAL tracks mean-field Ising energy for streaming interactions). Let interactions J1 , J2 , . . . , Jn ∈ R arrive sequentially as a stream, drawn i.i.d. from a distribution PJ with mean J¯ and variance σJ2 . Define the scalar signal ut = Jt . Then the PAL output with measure µ∗ (α, β) = α · 1[α = −β] satisfies: PALµ∗ (u0:n ) =
n X
Jt · γ̂Jt −Jt [u](t) = Ēn + O(n1/2 ),
(22)
t=0
P where Ēn = − N1 i<j Jij mi mj is the mean-field Ising energy for the empirical mean magnetisation m = Et≤n [σt ], and the O(n1/2 ) error follows from a standard concentration bound on the empirical mean. Proof. Each interaction Jt contributes to the Ising energy when its relay γ̂Jt −Jt [u](t) = 1, i.e. when Jt ≥ Jt — which holds trivially at the moment of arrival. The relay then tracks whether Jt remains the dominant interaction. By the wiping property, relay γ̂Jt −Jt remains active at time n iff no subsequent Jt′ > Jt has 14
Preprint
arrived. The PAL aggregate sums Jt over all non-dominated interactions, giving a running estimate of the effective coupling. R For the mean-field case Jij = J/N for all pairs, the self-consistency equation m = P(h) 1[h > −Jm − H] dh from theorem 9.1 holds exactly: PALµ∗ (u0:n ) = Jm2 /2 + O(n−1/2 ) by the law of large numbers applied to m over n observations, recovering the mean-field energy −Jm2 /2. The error bound O(n1/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 theorem 9.3 is related to the MAXCUT value by CUT(S) = (Emax − E(σ))/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
µ P The Hopfield P µ µnetwork (Hopfield, 1982) stores P patterns {ξ }µ=1 as attractors of Ising dynamics with Jij = −1 N µ ξi ξj . 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 ξ1 , . . . , ξ P ∈ Rd arrive sequentially with activation strengths ut = ∥ξt ∥2 . Let k be the depth of the extremum stack Πn after all P patterns have been processed. 1. Storage: The extremum stack Πn retains exactly those k patterns whose activation strength constitutes a local extremum of the stream u1 , . . . , uP . All other patterns are wiped by the wiping property (theorem 2.4). 2. Non-overlapping threshold support: The k retained patterns correspond to disjoint threshold pairs (Ms , ms ) with Ms ̸= Ms′ for s ̸= s′ (strict monotonicity of the stack, theorem 4.2), so their relays have disjoint support on T and their contributions to PALµ 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 u1:P : Capacity(PAL) = k ≤ next (u1:P ),
(23)
where next (u1:P ) is the number of local extrema in the activation strength sequence. This differs fundamentally from Hopfield capacity ≈ 0.14N (Amit et al., 1985): PAL capacity is limited by stack depth, not weight-matrix rank. ′
Proof. Storage (part 1): Direct from theorem 2.4. Pattern ξt is wiped when a subsequent pattern ξ t with ′ ∥ξ t ∥2 > ∥ξt ∥2 arrives, since the new maximum overwrites the old in the extremum stack. Only patterns at local extrema of u1:P survive. P Zero interference (part 2): The PAL output is PALµ (u0:n ) = i≥j µij γ̂αi βj [u](n). Each retained pattern ξ ts corresponds to a unique pair (Ms , ms ) in Πn with Ms ̸= Ms′ for s ̸= s′ (strict monotonicity of the stack, theorem 4.2). The relays γ̂Ms ms and γ̂Ms′ ms′ have disjoint support on the Preisach half-plane T when Ms ̸= Ms′ , so their contributions to PALµ are orthogonal — no cross-pattern interference. Capacity (part 3): The stack depth k ≤ next (u1: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 15
Preprint
P from the rank of the Hebbian weight matrix W = N −1 µ ξ µ (ξ µ )⊤ , 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 ξ ts from the PAL stack, a query signal q = ∥ξ ts ∥2 is presented. The relay γ̂Ms +εMs −ε [q] activates uniquely for the pattern at stack position s, and the associated value µMs ,ms · ξ ts 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 sitedependent 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 G = (V, E) be a tree-structured MRF with binary variables σv ∈ {−1, +1} and pairwise potentials ψuv (σu , σv ) = eJuv σu σv . Observations arrive sequentially in leaf-to-root order. Define the signal ut = tanh−1 (mt ) where mt = E[σt | x1:t ] is the marginal belief at step t under belief propagation. Then the PAL operator with measure: 1+tanh(α) µ∗ (α, β) = 21 log 1−tanh(α) · 1[α = −β]
(24)
satisfies PALµ∗ (u0:n ) = mn exactly for all tree-structured MRFs, where mn 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 P the computation causal. The effective field at the root satisfies heff = u∈∂v tanh−1 (mu→v ), which is the fixed-point of the Preisach self-consistency equation m = tanh(Jm + H) from theorem 9.1. With measure µ∗ from (24), PALµ∗ (u0:n ) tracks heff causally, and tanh(PALµ∗ (u0:n )) = mn 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 ∆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) ∼ s−τ with universal exponent τ . Proposition 9.8 (Scalar PAL criticality). A scalar PAL with measure µ drawn from a Gaussian distribution with variance ∆2 over the two-dimensional Preisach half-plane T exhibits a phase transition at critical variance ∆c : • For ∆ > ∆c : the output PALµ (u0:n ) varies smoothly with un — subcritical regime, corresponding to gradual relay activations. • For ∆ < ∆c : a macroscopic fraction of relays activate simultaneously at a critical threshold — supercritical regime, corresponding to an infinite avalanche. • At ∆ = ∆c : relay activations follow a power law in group size, with the same universality class as the mean-field RFIM. Proof. By theorem 9.1, PAL with Gaussian measure is equivalent to mean-field RFIM with disorder ∆. The phase transition of the RFIM atR∆c = J (Dahmen and Sethna, 1993) translates directly to PAL. At ∆c , the self-consistency equation m = P(h)1[h > −Jm − H] dh has a bifurcation point, corresponding to a jump discontinuity in the Preisach output.
16
Preprint
Remark 9.9 (Implications for PAL learning). theorem 9.8 has a practical implication: if the learned measure µ∗ concentrates near the critical disorder ∆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 ∆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(n2 ) couplings O(n2 ) per new node None (quenched disorder) NP-hard in general Yes (Gibbs measure)
Sequential stream
PAL
O(log k) per new token Significance-based wiping Approximation only No (causal only)
PAL PAL
Update cost Forgetting Exact optimisation Equilibrium guarantees Universality class Coupling structure Sequence modelling
10
Known (τ, ν, . . .) Arbitrary Jij Not native
Inherited from RFIM Mean-field implicit Native (rateindependent)
Ising Ising Equal Ising PAL
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 (theorems 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 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 (theorems 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 thresholddriven. Open questions. 1. Empirical validation: Do the predicted task advantages materialise in practice? Experiments on statetracking benchmarks (MQAR, SCROLLS) would test theorem 5.1 empirically. 2. Learning dynamics and criticality: Does gradient-based learning of µ(α, β) drive the measure toward the critical disorder ∆c ? Is training near criticality beneficial empirically, analogous to the edge-ofchaos effect? 17
Preprint
3. Beyond mean-field: Can the equivalence in theorem 9.1 be extended beyond mean-field RFIM to shortrange 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 continuoustime 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: theorem 4.8 establishes that vPAL with a two-dimensional signal un ∈ R2 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 M is integrated over the three-dimensional space (α, β, θ) with displacement γαβ (θ) and rotation χαβ (θ) components. Three questions remain open for vPAL: (a) Does the vector RFIM connection extend to the anisotropic case studied by Frydrych, where the measure µ(α, β, θ) breaks rotational symmetry? (b) Can the domain-rotation component χαβ (θ) 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 (L2H 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(n2 ) for attention) may reduce the energy cost of training long-context models, which is a potential positive environmental impact.
References Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? investigations with linear models. In International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=0g0X4H8yN4I. Daniel J. Amit, Hanoch Gutfreund, and Haim Sompolinsky. Storing infinite numbers of patterns in a spin-glass model of neural networks. Physical Review Letters, 55(14):1530–1533, 1985. doi: 10.1103/ PhysRevLett.55.1530. Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=r1lZ7AEKvB. Ramón Barroso, Aitor Egaña, Jose Luis Marqués, Ion Etxeberria-Otadui, and Octavian Curea. Preisach modeling of LiFePO4 lithium-iron-phosphate battery hysteresis. Journal of Energy Storage, 2:65–72, 2015. doi: 10.1016/j.est.2015.06.001. 18
Preprint
Ali Behrouz, Peilin Zhong, and Vahab Mirrokni. Titans: Learning to memorize at test time. In arXiv preprint arXiv:2501.00663, 2025. URL https://arxiv.org/abs/2501.00663. Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. In arXiv preprint arXiv:2004.05150, 2020. URL https://arxiv.org/abs/2004.05150. Martin Brokate and Jürgen Sprekels. Hysteresis and Phase Transitions, volume 121 of Applied Mathematical Sciences. Springer, New York, 1996. doi: 10.1007/978-1-4612-4048-8. George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303–314, 1989. doi: 10.1007/BF02551274. Karin Dahmen and James P. Sethna. Hysteresis loop critical exponents in 6 − ε dimensions. Physical Review Letters, 71(20):3222–3225, 1993. doi: 10.1103/PhysRevLett.71.3222. Piotr Frydrych. Modelowanie charakterystyk magnesowania amorficznych rdzeni dwuosiowych sensorów transduktorowych. PhD thesis, Politechnika Warszawska, Wydział Mechatroniki, Warsaw, Poland, 2019. Piotr Frydrych and Roman Szewczyk. New portfolio risk optimisation method for strongly dependent assets. Journal of Engineering Studies and Research, 20(3):30–37, 2014. Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In Mathematical Systems Theory, volume 17, pages 13–27, 1984. doi: 10.1007/BF01744431. Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. In arXiv preprint arXiv:2312.00752, 2023. URL https://arxiv.org/abs/2312.00752. Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171, 2020. doi: 10.1162/tacl_a_00306. Johan Håstad. Computational Limitations of Small-Depth Circuits. MIT Press, Cambridge, MA, 1987. John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979. John J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences, 79(8):2554–2558, 1982. doi: 10.1073/pnas.79.8.2554. Christopher G. Langton. Computation at the edge of chaos: Phase transitions and emergent computation. Physica D: Nonlinear Phenomena, 42(1–3):12–37, 1990. doi: 10.1016/0167-2789(90)90064-V. Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics, 2:5, 2014. doi: 10.3389/fphy. 2014.00005. Isaak D. Mayergoyz. Mathematical Models of Hysteresis. Springer, New York, 1991. doi: 10.1007/ 978-1-4612-3028-1. William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531–545, 2023. doi: 10.1162/tacl_a_ 00562. Marc Mézard and Andrea Montanari. Information, Physics, and Computation. Oxford University Press, Oxford, 2009. doi: 10.1093/acprof:oso/9780198570837.001.0001. Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Stella Biderman, et al. RWKV: Reinventing RNNs for the transformer era. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 14048–14077, 2023. doi: 10.18653/v1/2023.findings-emnlp.936. Jorge Pérez, Javier Marinković, and Pablo Barceló. Attention is Turing complete. Journal of Machine Learning Research, 22(75):1–35, 2021. URL http://jmlr.org/papers/v22/20-1393.html.
19
Preprint
Franz Preisach. Über die magnetische Nachwirkung. Zeitschrift für Physik, 94(5–6):277–302, 1935. doi: 10.1007/BF01349418. James P. Sethna, Karin A. Dahmen, and Olga Perkovic. Random-field ising models of hysteresis. The Science of Hysteresis, 2:107–179, 2006. URL https://arxiv.org/abs/cond-mat/0406320. Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. In International Conference on Learning Representations, 2017. URL https://openreview.net/forum? id=B1ckMDqlg. Hava T. Siegelmann and Eduardo D. Sontag. On the computational power of neural nets. Journal of Computer and System Sciences, 50(1):132–150, 1995. doi: 10.1006/jcss.1995.1013. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, 2017. Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, volume 202, pages 35151–35174, 2023. Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, et al. Big Bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems, volume 33, pages 17283–17297, 2020.
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 x = (x0 , x1 , . . . , xn ) where each xi ∈ Rd . Let E(x) = {i : xi is a local extremum of ∥xi ∥2 } denote the set of extremal positions of x. Definition A.1 (EFO syntax). The grammar of Extremum First-Order Logic (EFO) over sequences is: ϕ ::= ⊤ | ⊥ | ui ≤ c | ui ≥ c | i <ext j | ϕ ∧ ψ | ϕ ∨ ψ | ¬ϕ | ∃ext i ϕ(i) | ∀ext i ϕ(i) | ExtAggi [f (i), ϕ(i)] where c ∈ R is a constant, i ranges over extremal positions only, i <ext j denotes that extremal position i occurred before extremal position j in the sequence, and ExtAggi [f (i), ϕ(i)] denotes: X ExtAggi [f (i), ϕ(i)] = f (xi ), (25) i∈E(x), ϕ(i) holds
where f : Rd → R is a measurable function. The ordering relation <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 x satisfies ϕ (written x |= ϕ) according to the standard firstorder semantics restricted to extremal positions: • x |= ui ≥ c iff xi ≥ c for the current assignment of i. • x |= ∃ext i ϕ(i) iff there exists i ∈ E(x) such that x |= ϕ(i). • Boolean connectives have their standard meaning. • ExtAggi [f (i), ϕ(i)] sums f (xi ) over extremal positions satisfying ϕ. 20
Preprint
A.2
The Correspondence
We establish a bijection between EFO formulae and PAL computations by defining a compilation map J·K : EFO → PAL-Transformer. Lemma A.3 (Extremal position indicator). The indicator 1[i ∈ E(x)] is computable by a single-head PAL as: 1[i ∈ E(x)] = γ̂αi +εαi −ε [u](i) − γ̂αi +εαi −ε [u](i − 1), (26) where uj = ∥xj ∥2 is the scalar projection of the sequence (one specific scalarisation; any injective ϕ : Rd → R suffices for the lemma to hold). That is, the relay changes state at step i if and only if ui is a local extremum. Proof. By Definition 2.1, the relay γ̂αi +εαi −ε [u](i) changes from 0 to 1 at step i iff ui ≥ αi + ε, and from 1 to 0 iff ui ≤ αi − ε. In both cases, a state change occurs exactly when ui crosses one of the thresholds, which — by choice of αi = ui and ε → 0 — happens exactly at local extrema. The difference (26) detects this state change. Lemma A.4 (Threshold comparison). The formula ui ≥ c at an extremal position i is computable by a PAL with thresholds α = c + ε, β = c − ε as: 1[ui ≥ c] = γ̂c+εc−ε [u](i).
(27)
Proof. Direct from Definition 2.1: when the input ui crosses threshold α = c + ε, the relay switches to 1; when it falls below β = c − ε, it switches to 0. In the limit ε → 0, this detects ui ≥ c at each extremal step. Lemma A.5 (Boolean combinations via MLP). Let ϕ1 , ϕ2 be two EFO formulae computable by PAL heads producing outputs r1 , r2 ∈ {0, 1}. Then ϕ1 ∧ ϕ2 , ϕ1 ∨ ϕ2 , and ¬ϕ1 are computable by a two-layer MLP applied to (r1 , r2 ). Proof. Boolean functions on {0, 1}2 are representable by two-layer networks with ReLU activations (Cybenko 1989): r1 ∧ r2 = ReLU(r1 + r2 − 1), r1 ∨ r2 = ReLU(r1 + r2 ) − ReLU(r1 + r2 − 1), ¬r1 = 1 − r1 . These are exact (not approximate) representations on {0, 1}. Lemma A.6 (Extremum aggregation). The formula ExtAggi [f (xi ), ϕ(i)] is computable by a single MPAL head with measure: µ(α,β) = f (Dec(α, β)) · 1[ϕ holds at (α, β)], (28) where Dec(α, β) recovers the value xi encoded at thresholds (α, β). Proof. The MPAL output for a single head with measure µ is: X PALµ (u0:n ) = µij · γ̂αi βj [u](n). i≥j
At time n, γ̂αi βj [u](n) = 1 if and only if the current extremum stack Πn contains a pair (M, m) with M ∈ (αi − ε, αi + ε) and m ∈ (βj − ε, βj + ε), i.e. the relay encodes an active extremal position satisfying the threshold condition. Setting µij = f (Dec(αi , βj )) · 1[ϕ holds at (i, j)] makes the PAL output equal to (25), since the relay sums over exactly those extremal positions where ϕ holds, weighted by f .
21
Preprint
Lemma A.7 (Existential extremal quantification). The formula ∃ext i ϕ(i) is computable by a PAL followed by a threshold MLP: x |= ∃ext i ϕ(i) ⇐⇒ ReLU(ExtAggi [1, ϕ(i)]) > 0. (29) Proof. ExtAggi [1, ϕ(i)] counts the number of extremal positions satisfying ϕ. This is positive iff at least one such position exists, which is exactly the semantics of ∃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. (⇒) 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 γ̂αβ [u](n) is EFO-definable. By the wiping property (theorem 2.4) and stack sufficiency (theorem 2.7), the relay state at time n is determined entirely by the most recent statechanging extremum. Specifically, γ̂αβ [u](n) = 1 iff there exists an extremal position t∗ ≤ n at which the relay was activated (ut∗ ≥ α), and no subsequent extremal position t ∈ (t∗ , n] deactivated it (ut ≤ β). This is expressed in EFO with ordering as: h i γ̂αβ [u](n) = 1 ⇐⇒ ∃ext t∗ ≤ n ut∗ ≥ α ∧ ∀ext t : t∗ <ext t ⇒ ut > β . (30) The existential quantifier ranges over extremal positions by theorem A.1; the comparison ut∗ ≥ α is atomic; the ordering t∗ <ext t uses the causal order in EFO; and ut > β is atomic. Hence (30) is an EFO formula. P Inductive case — weighted sum: PALµ (u0:n ) = i≥j µij γ̂αi βj [u](n) is a weighted sum of relay states. By the inductive hypothesis each γ̂αi βj is EFO-definable; their weighted sum is ExtAggi [µ · γ̂·· , ⊤], 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 ExtAgg). By induction, the entire PAL-Transformer output is EFO-definable. (⇐) Every EFO formula is PAL-computable. PAL component.
We show that each EFO construct is implementable by a
Atomic formula ui ≥ c: Implemented by Lemma A.4 with α = c + ε, β = c − ε. Boolean combinations: Implemented by Lemma A.5. Existential quantification ∃ext i ϕ(i): Implemented by Lemma A.7. Universal quantification ∀ext i ϕ(i): Equivalent to ¬(∃ext i ¬ϕ(i)), implementable by Lemmas A.5 and A.7. Extremum aggregation ExtAggi [f (i), ϕ(i)]: Implemented by Lemma A.6 with measure µij = f (Dec(αi , βj ))· 1[ϕ holds at (i, j)]. Nested formulae: Suppose ϕ = ExtAggi [f (i), ψ(i)] where ψ is an EFO formula. By the inductive hypothesis, ψ is implementable by a PAL sub-computation producing output ri ∈ {0, 1} for each extremal position i. Then ExtAggi [f (i), ψ(i)] is implemented by a PAL head with measure µij = f (Dec(αi , βj )) · rij , where rij is the output of the sub-computation. This composes PAL layers — at most one additional layer per level of nesting.
22
Preprint
By induction on formula depth, every EFO formula is implementable by a PAL-Transformer with depth proportional to the nesting depth of ExtAgg operators. A.4
Corollaries of the EFO Correspondence
Corollary A.8 (Decidability of PAL expressiveness). Given a function f : Rn+1 → R, deciding whether f ∈ FPAL 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 ⊊ FO + Aggregate). EFO is strictly contained in FO + Aggregate (the logic corresponding to soft-attention transformers (Barceló et al., 2020)): EFO ⊊ FO + Aggregate. The strict inclusion is witnessed by fcopy (x0:n , p) = xp : definable in FO with positional quantification ∃i (i = p), but not in EFO (which cannot quantify over non-extremal positions). The reverse inclusion fails because frange is definable in EFO but not in bounded-depth FO + 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 ≡ EFO-depth k.
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 un+1 = Mtop−1 + 2ε removes exactly the topmost pair (Mtop , mtop ) and no other. Proof. The wiping property removes all pairs (Mi , mi ) with Mi < un+1 = Mtop−1 + 2ε. Since Mtop < Mtop−1 (strict monotonicity), we have Mtop < Mtop−1 + 2ε, so the pair (Mtop , mtop ) is wiped. Since Mtop−1 < Mtop−1 + 2ε implies Mtop−1 is not less than un+1 , the pair (Mtop−1 , mtop−1 ) is preserved. (More precisely, wiping removes Mi < un+1 ; Mtop−1 < Mtop−1 + 2ε = un+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 un+1 = code∗ (ai , d + 1) + ε does not trigger the wiping property. Proof. By Lemma 4.2, code∗ (ai , d + 1) < code∗ (aj , d) for all j ∈ {1, . . . , k}. Therefore un+1 = code∗ (ai , d + 1) + ε < Mtop (since Mtop = code∗ (aj , d) + ε for some j and the ε gap is smaller than the inter-level gap ∆ > 0, provided ε < ∆/2). Since un+1 < Mtop , the wiping condition un+1 > Mtop 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 |Σ|, and stack alphabet |Γ|, the transition function δ : Q × Σ × Γ × Γ → Q × Γ∗ × Γ∗ is implementable by a two-layer MLP of width O(|Q| · |Σ| · |Γ|2 ). Proof. δ has domain of size |Q| · |Σ| · |Γ|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, s1 , s2 ), one hidden neuron fires for that configuration (indicator neuron) and outputs the corresponding transition values. Width: one neuron per table entry = O(|Q| · |Σ| · |Γ|2 ). 23
Preprint
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: X PALµ (u0:n ) = ai · vi , (31) i∈E(u0:n )
where ai = µ(α(ui ),β(ui−1 )) is a content-determined weight and vi = γ̂α(ui )· is the relay value. The attention mask is {i : i ∈ E(u0: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 γ̂αi βj is active at time n only if the most recent state change was an activation at some extremal position t∗ ≤ n with ut∗ ≥ αi . This is equivalent to attending to extremal positions, with weights given by the measure µ. 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.
24