🔬 condensed matter

Preisach Attention: A Hysteretic Model of Sequential Memory

This paper introduces the Preisach Attention Layer (PAL), a novel sequence modeling architecture that replaces softmax attention with a hysteresis-based binary relay operator to achieve Turing-completeness in O(1) depth, enable efficient computation of historical range statistics, and provide O(n log n) inference costs for tasks requiring long episodic memory with weak positional dependence.

Original authors: Piotr Frydrych

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Piotr Frydrych

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: A New Way for AI to Remember

Imagine you are trying to teach a robot to read a long story. The current superstar of AI, the Transformer, remembers things by looking at where words appear in the sentence. It's like a librarian who only remembers the book's position on the shelf. If you move the book to a different spot, the librarian gets confused. Also, the librarian has to check every single book on the shelf to find one, which gets very slow and expensive as the library grows.

The author of this paper, Piotr Frydrych, proposes a new kind of memory called Preisach Attention (PAL). Instead of caring about where something happened, PAL cares about how important the changes were. It's inspired by an old physics concept called "hysteresis," which describes how magnets remember their history.

Think of PAL not as a librarian, but as a mountain climber keeping a diary of peaks and valleys.

How It Works: The Mountain Climber's Diary

Imagine you are hiking up a mountain range. You don't write down every single step you take. You only write down the highest peaks you reach and the lowest valleys you drop into.

The "Extremum Stack" (The Diary):
- As you hike, you keep a list of your highest peak and lowest valley so far.
- The Magic Rule (Wiping): If you climb a new peak that is higher than your previous highest peak, your diary automatically erases the old peak and everything below it. It only keeps the new, more significant record.
- Why this matters: If you walk back and forth in a small valley, your diary doesn't change. It only updates when you make a major move. This means the AI ignores the "noise" and only remembers the big, significant events.
Rate-Independence (The "Time Doesn't Matter" Rule):
- Standard AI models get confused if you speed up or slow down a story.
- PAL doesn't care about time. Whether you hike the mountain in 1 hour or 100 years, your diary of peaks and valleys looks exactly the same. It only cares about the order of the big changes, not how long it took to get there.

Why Is This Better? (The Paper's Claims)

The paper makes three major claims about why this new "Mountain Climber" memory is special:

1. It's Smarter (and Faster) at Math

The Claim: A single layer of this new AI is mathematically powerful enough to solve any problem a computer can solve (Turing-complete).
The Analogy: Standard AI models need to stack many layers (like building a tall tower of blocks) to solve complex logic puzzles. This new model can solve the same puzzles with just one layer. It's like having a Swiss Army knife that does the job of a whole toolbox.
Speed: Because it only tracks peaks and valleys, it doesn't have to check every single word in a long document. It's much faster for very long stories.

2. It's Different, Not Just "Better"

The Claim: PAL and standard AI are "incomparable." They are good at different things.
The Analogy:
- Standard AI is great at finding a specific word if you know its position (e.g., "What is the 5th word?"). It has "random access."
- PAL is terrible at that. It can't tell you the 5th word because it doesn't count positions.
- However, PAL is amazing at finding the "biggest change" in a story (e.g., "What was the highest temperature recorded?"). Standard AI struggles with this because it has to look at everything to find the max. PAL just looks at its diary of peaks.

3. It Forgets Based on Importance, Not Time

The Claim: Standard AI forgets old things because they are "old" (recency). PAL forgets things because they are "small."
The Analogy: Imagine you are remembering a conversation.
- Standard AI: "I remember what you said 5 minutes ago, but I forgot what you said 1 hour ago."
- PAL: "I forgot what you said 1 hour ago because it was a small detail. But I remember what you said 1 hour ago because it was a huge, shocking revelation that changed the whole conversation."
- This is called the "Wiping Property." A new, bigger event wipes out the memory of smaller, less significant events.

The Physics Connection: The "Magnet" Analogy

The paper connects this AI to a physics model called the Random-Field Ising Model (think of a bunch of tiny magnets).

In physics, these magnets flip back and forth based on a magnetic field. They have a "memory" of their past states.
The author shows that PAL is essentially a learned, moving version of these magnets.
Why does this help? It means PAL inherits cool physics properties, like the ability to handle "avalanches" (sudden, massive changes in data) very naturally. It suggests that if you tune the AI just right, it operates at a "critical point" where it is super sensitive to new information, similar to how a snowflake can trigger a massive avalanche.

Summary: Who is this for?

The paper argues that PAL is the perfect tool for tasks where:

History matters more than position: You need to know the "big picture" of a long event, not the exact timestamp.
Significance matters more than recency: You want to remember the biggest shocks, not just the most recent ones.
The data is long: It's much more efficient (cheaper and faster) for very long sequences than current AI models.

In short: The paper introduces a new type of AI memory that acts like a hiker remembering only the highest peaks and deepest valleys, ignoring the small steps in between. This makes it incredibly efficient for long stories and complex logic, though it trades away the ability to count exact positions.

Technical Summary: Preisach Attention: A Hysteretic Model of Sequential Memory

Problem Statement

Current dominant sequence modeling architectures, particularly the Transformer, rely on attention mechanisms that are either temporal (decaying by distance) or positional (indexed by token location). While theoretical analyses have established the Turing completeness of hard-attention Transformers, they require $O(\log n)$ depth to achieve this, and standard softmax attention corresponds to limited fragments of first-order logic. A critical limitation shared by Transformers, Recurrent Neural Networks (RNNs), and State Space Models (SSMs) is the lack of a memory mechanism based on the significance of past inputs rather than their recency or absolute position. There is a need for an architecture capable of maintaining long episodic memory where the output depends on the sequence of local extrema of the input history, independent of temporal spacing.

Methodology

The paper introduces the Preisach Attention Layer (PAL), a novel sequence modeling architecture grounded in the classical Preisach hysteresis operator from mathematical physics.

Core Mechanism: The Preisach Operator

The Preisach operator aggregates the outputs of binary relays $\hat{\gamma}_{\alpha\beta}$ , each characterized by an activation threshold $\alpha$ and a deactivation threshold $\beta$ . In the context of sequence modeling:

Binary Relay: For an input sequence $u$ , the relay state switches to 1 if $u_n \geq \alpha$ and to 0 if $u_n \leq \beta$ . Otherwise, it retains its previous state.
Extremum Stack: A fundamental consequence of the "wiping property" is that the operator's output depends only on the current extremum stack ( $\Pi_n$ ). This stack stores alternating local maxima and minima. A new extremum erases all previous extrema of smaller magnitude, providing a natural, significance-based forgetting mechanism.
Rate-Independence: The output depends solely on the sequence of local extrema, not on the absolute time or position of tokens.

Architecture Definition

PAL Layer: The layer computes a weighted sum of binary relay outputs over a discretized measure $\mu$ on the threshold plane $(\alpha, \beta)$ .
Multi-Head PAL (MPAL): Extends the scalar PAL to vector-valued sequences by projecting inputs to scalar signals, processing them through multiple heads, and projecting back.
PAL-Transformer: A standard Transformer encoder-decoder structure where the standard attention mechanism is replaced by MPAL. It retains sinusoidal position encoding (PE) and MLP layers, but the core memory mechanism is hysteretic.

Key Contributions and Results

1. Turing Completeness at $O(1)$ Depth

The paper proves that a single-layer PAL-Transformer is Turing-complete.

Mechanism: The architecture simulates an arbitrary two-stack pushdown automaton (2-PDA), which is equivalent to a Turing machine.
Encoding: Alphabet symbols and stack depths are encoded into the extremum stack using "Cantor-depth encoding."
Depth Advantage: This simulation is achieved with $O(1)$ depth (one MPAL layer and one MLP layer). This contrasts with standard hard-attention Transformers, which require $O(\log n)$ depth to achieve Turing completeness (Pérez et al., 2021).
Vector PAL (vPAL): A variant using a two-dimensional signal projection achieves Turing completeness with a single head ( $H=1$ ), demonstrating that signal dimension and head count are exchangeable resources in PAL.

2. Expressiveness Separation

The paper establishes that the function classes computable by PAL and Transformers are incomparable.

PAL $\setminus$ Transformer: PAL can compute historical range statistics (e.g., $max(u) - min(u)$) in $O(1)$ layers. Standard Transformers with bounded depth cannot compute this exactly due to circuit complexity lower bounds (MAX is not in $AC^0$ ).
Transformer $\setminus$ PAL: Transformers can perform exact random-access retrieval (e.g., retrieving the token at position $p$ ). PAL cannot perform this because its rate-independence property implies that if a token is not a local extremum, its value is "wiped" from the stack's influence, making position-based retrieval impossible without auxiliary state.
Separating Property: Rate-independence is identified as the fundamental property separating the two classes. PAL outputs are invariant to time-rescaling of the input sequence, whereas standard attention is not.

3. Logical Characterization

The paper defines Extremum First-Order Logic (EFO), an extension of first-order logic that allows quantification only over local extremal positions and includes an extremum aggregate operator.

Theorem: A function is computable by a bounded-depth PAL-Transformer if and only if it is definable in EFO.
Implication: EFO is a strict fragment of the logic corresponding to standard Transformers (FO + Aggregate), confirming that PAL cannot express arbitrary positional logic but excels at extremum-based aggregation.

4. Connection to Physics and Complexity

RFIM Equivalence: The paper demonstrates that PAL is a learned, sequential, non-equilibrium generalization of the Random-Field Ising Model (RFIM) at $T=0$ . The extremum stack corresponds to the minimal sufficient statistic of the RFIM's history.
Complexity: PAL inference has a total time complexity of $O(n \log n)$ (due to stack updates and binary search) and memory $O(kd)$, compared to $O(n^2)$ for standard attention.
Phase Transitions: Drawing from RFIM theory, the paper suggests that PAL layers operating near a critical disorder strength may exhibit "edge of chaos" behavior, maximizing sensitivity to input changes while maintaining structured memory.

Significance and Claims

The paper claims that PAL offers a fundamentally different memory mechanism for sequence modeling, shifting from recency-based or positional memory to significance-based memory.

Theoretical Advancement: It provides a new point in the space of sequence models that is incomparable to existing architectures, offering $O(1)$ depth Turing completeness and a unique logical characterization (EFO).
Efficiency: By relying on the extremum stack, PAL reduces inference complexity from quadratic to near-linear ( $O(n \log n)$ ), making it theoretically suitable for tasks requiring long episodic memory.
Task Suitability: The authors posit that PAL is predicted to outperform standard attention on tasks that are rate-independent and rely on historical range statistics, such as:
- Tracking entity states across long documents.
- Detecting anomalies in time series based on historical ranges.
- Reasoning over ordered events without positional sensitivity.
- Energy market dispatch where decision thresholds drive behavior.

The paper concludes that while PAL cannot perform random access, its ability to maintain a minimal sufficient statistic of input history for all rate-independent functionals makes it a natural architecture for problems where the significance of past events matters more than their recency or absolute position. The work remains theoretical, with empirical validation and learning dynamics (specifically regarding criticality) identified as open questions for future research.