Recasting Self-Attention with Holographic Reduced Representations

ArXiv: 2305.19534

🎯 Pitch

Standard self-attention collapses under long sequences due to quadratic costs, but the Hrrformer replaces it with holographic reduced representations to slash complexity to O(TH log H) time. On malware classification, it's the only Transformer that scales to 131K tokens without crashing, while matching or beating all rivals in accuracy. Remarkably, it trains 280× faster than prior efficient methods, converging in just one layer.

---

1. Executive Summary

This paper proposes a neuro-symbolic reconstruction of self-attention using Holographic Reduced Representations (HRR), creating the Hrrformer as a drop-in replacement for standard self-attention in Transformers. The authors test the Hrrformer on the Long Range Arena (LRA) benchmark and the EMBER malware classification dataset, demonstrating that it achieves near state-of-the-art accuracy while providing substantial efficiency benefits — converging in 10× fewer epochs, requiring only a single layer to learn structure, and delivering up to 28× faster training throughput and 79.15% less GPU memory than the best prior method. On the EMBER malware dataset, the Hrrformer scales to sequence lengths of T = 131,072 where most competing methods fail with out-of-memory or out-of-time errors, achieving the highest accuracy (91.03% at T = 16,384) — establishing that HRR-based attention is a viable Transformer for very long sequences, outperforming pretraining-based approaches only when sequences fall within the model's capability range but traditional attention becomes computationally prohibitive.

2. Context and Motivation

The Core Problem: Quadratic Self-Attention Makes Long Sequences Impractical

The fundamental bottleneck this paper tackles is the quadratic complexity of standard self-attention. In the Transformer architecture introduced by Vaswani et al. (2017), the self-attention mechanism computes an all-pairs interaction between every position in a sequence and every other position. Concretely, for a sequence of length $T$ with hidden dimension $H$, the attention operation requires $\mathcal{O}(T^2)$ memory to store the attention matrix and $\mathcal{O}(T^2 H)$ compute to perform the matrix multiplications. This quadratic scaling means that as $T$ grows, the computational and memory requirements explode — doubling the sequence length roughly quadruples the cost.

This is not merely a theoretical concern. The authors are explicitly motivated by problems in malware detection, where processing raw executable bytes produces sequence lengths of $T \geq 100,000$ tokens. In practice, a single Windows portable executable (PE) file can range from tens of kilobytes to hundreds of megabytes, corresponding to potential sequence lengths up to $T = 200,\!000,\!000$ — well beyond what any standard Transformer implementation can handle even on high-end GPU hardware. As Figure 1 demonstrates, most existing xformer variants run out of memory (OOM) or time (OOT) before reaching useful sequence lengths on the EMBER malware classification benchmark. This is not a niche concern: malware detection from raw bytes is one of the most robust feature representations against adversarial obfuscation (Aghakhani et al., 2020), but the field has been stuck using simple n-gram features precisely because methods capable of learning complex sequential patterns — like Transformers — cannot scale to the required input sizes.

The problem extends well beyond malware. The paper operates in the broader context of the Long Range Arena (LRA) benchmark (Tay et al., 2020c), which was specifically designed to evaluate whether models can handle sequences from $1,\!024$ to $16,\!384$ tokens across diverse tasks including hierarchical reasoning (ListOps), byte-level text classification, document retrieval, image classification from flattened pixels, and spatial reasoning (Pathfinder). The standard Transformer fails entirely on the Path-X task ($T = 16,\!384$) and requires 200 epochs to converge on the other tasks — a training cost that is prohibitive at scale, especially when models must process very long sequences in domains like genomics, audio processing, or financial time series.

Why This Problem Matters: The Dual Barriers of Memory and Time

The paper identifies two distinct but related barriers created by quadratic attention:

Memory as a hard constraint. The $\mathcal{O}(T^2)$ memory requirement means that even with unlimited computational patience, there is an absolute ceiling on sequence length determined by available GPU memory. On the EMBER dataset, the standard Transformer runs out of memory at $T = 8,\!192$ even with an aggressively decaying batch size (halved each time sequence length doubles, starting from 256). This is not solved by simply reducing batch size further — at some point, the attention matrix alone exceeds device capacity. For practitioners working with long sequence data, this means Transformers are literally unusable regardless of accuracy.

Training time as a practical barrier. Even when models can fit in memory, the $\mathcal{O}(T^2 H)$ compute cost translates directly to wall-clock time. The LRA baseline requires 200 epochs of training, and on the EMBER dataset — which is 1 TB in size — training standard Transformers is "otherwise prohibitive in its scale" even at sequence lengths where memory is adequate. The authors note that the EMBER dataset's combination of sequence length and dataset size makes training time the limiting factor even before memory becomes an issue — a doubly constrained problem that prior xformer variants do not adequately solve.

These barriers have real consequences: the field has been forced into workarounds that sacrifice representational power. As the paper documents in its Related Work (Section 2), malware detection researchers have resorted to creating "images" from malware binaries (Nataraj et al., 2011; Liu & Wang, 2016), using compression-based similarity metrics (Li et al., 2004; Raff & Nicholas, 2017), and attempting to scale 1D convolutional networks over raw bytes (Krčál et al., 2018; Raff et al., 2018) — all because the model class that has dominated sequence modeling (Transformers) cannot handle the actual sequence lengths of the domain.

The Landscape of Prior Approaches: A Taxonomy of Quadratic Avoidance

Since Vaswani et al. (2017), a substantial literature has developed around making self-attention more efficient. The paper provides a structured taxonomy of these approaches in Section 2, drawing an analogy to the history of scaling Support Vector Machines (SVMs) — a connection that is worth understanding because it reveals the intellectual lineage of the solutions:

Projection-based methods reduce the effective dimensionality of the attention operation. Linformer (Wang et al., 2020) projects the key and value matrices from $T \times H$ down to $k \times H$ where $k$ is a fixed low-rank dimension, achieving $\mathcal{O}(TkH)$ complexity. The tradeoff is that information from some positions is permanently compressed, potentially losing fine-grained dependencies.

Sparse attention patterns restrict which positions can attend to which, creating a structured rather than dense attention matrix. This family includes: Reformer (Kitaev et al., 2020), which uses locality-sensitive hashing to group similar queries; Sparse Transformer (Child et al., 2019), which uses fixed sparse patterns (strided and local windows); Longformer (Beltagy et al., 2020) and BigBird (Zaheer et al., 2020), which combine local windows with global tokens and random sparse connections; and Sinkhorn Transformer (Tay et al., 2020b), which learns sparsity patterns via a differentiable sorting operation. The common weakness is that sparsity is an assumption — if long-range dependencies exist between positions that happen to fall in disconnected sparse regions, they are missed.

Random feature methods approximate the softmax attention kernel with randomized feature maps that enable linear-time computation through the associativity trick — computing $\phi(Q)(\phi(K)^\top V)$ rather than $\text{softmax}(QK^\top)V$. Performer (Choromanski et al., 2020) is the exemplar here, using orthogonal random features to approximate the softmax kernel. The tradeoff is that the approximation quality depends on the number of random features and can degrade for certain attention patterns.

Factorized or budgeted representations compress the sequence dimension. Luna (Ma et al., 2021) introduces a learnable "query projection" that compresses the $T$ input tokens into a fixed-length "packed" representation of $k$ positions (where $k$ is a hyperparameter like 256), then performs attention between the compressed and original representations. H-Transformer-1D (Zhu & Soricut, 2021) hierarchically decomposes the sequence, coarsening the temporal resolution at higher levels. Nyströmformer (Xiong et al., 2021) approximates the full attention matrix using the Nyström method for low-rank matrix approximation. These methods impose structural assumptions about what information is preserved across the compression.

Linear attention reformulates attention to remove the softmax nonlinearity, enabling the associativity trick directly. Linear Transformer (Katharopoulos et al., 2020) uses a kernel feature map and drops the softmax normalization, achieving genuine $\mathcal{O}(TH^2)$ complexity. This is simple and fast but loses the selective, saturation-like behavior of softmax attention that allows Transformers to focus sharply on relevant positions.

Replacement strategies abandon attention entirely in favor of alternative mixing operations. F-Net (Lee-Thorp et al., 2021) replaces self-attention with a 2D Fast Fourier Transform applied to the sequence and hidden dimensions, creating a fixed, unlearned mixing operation. The authors treat F-Net as particularly relevant because it shares the FFT as a computational primitive with their HRR-based approach, making it a natural comparison point. Synthesizer (Tay et al., 2020a) replaces query-key interactions with learned, data-independent attention weights.

Each of these families offers a specific point on a Pareto frontier trading accuracy, speed, and memory. But the paper identifies a critical shortcoming shared across them: none reproduce the same logical strategy as standard self-attention. They approximate it, restrict it, or replace it — but they operate from the premise that the exact mechanism is too expensive and must be compromised. The authors argue this premise deserves questioning: what if self-attention's logical structure — queries matching against keys, returning weighted values — can be preserved exactly through an entirely different mathematical formulation?

Where Prior Approaches Fall Short: The Accuracy-Speed-Memory Trilemma

The paper's assessment of the prior landscape, supported by its experimental results, reveals that existing methods face a trilemma:

High-accuracy methods are slow and memory-heavy. Luna-256 achieves the best average LRA score (61.95%) but processes only 23.74 examples/second and consumes 3,184.66 MB of GPU memory (Table 4). On the EMBER dataset, Luna-256's accuracy peaks at only 83.76% at $T = 8,\!192$ and it runs out of time at $T = 16,\!384$ — substantially worse than the Hrrformer's 90.89% at the same sequence length (Table 5). The paper hypothesizes that Luna's aggressive temporal compression fails when the task requires "more complex reasoning and feature extraction over time" — a hypothesis supported by Luna's poor performance on EMBER relative to its LRA ranking.

Fast, memory-efficient methods sacrifice accuracy. F-Net is consistently the fastest alternative (the only method faster than Hrrformer on EMBER), but its accuracy on LRA is a full 6.41 percentage points below Luna-256's (54.42% vs. 61.95%), and on EMBER it trails the Hrrformer by an absolute 4.53 percentage points at $T = 16,\!384$. The fixed, unlearned Fourier mixing cannot adapt to task-specific attention patterns.

Methods that work well on LRA do not transfer reliably. This is a critical but subtle finding. The paper shows that Luna-256 and H-Transformer-1D — the two highest-ranked methods on the LRA benchmark — perform "considerably worse on the malware task" (Figure 1, Table 5). Luna-256's accuracy on EMBER peaks below 84% versus Hrrformer's 91%, and H-Transformer-1D runs out of time at $T = 32,\!768$. This domain transfer failure suggests that the LRA benchmark, despite its diversity, does not capture all the challenges of real-world long-sequence tasks — specifically, the combination of very long sequences with the need for fine-grained temporal reasoning that malware byte analysis demands. The paper positions this as evidence that "best practices developed in the machine learning, computer vision, and natural language processing communities do not always transfer to this kind of data," citing prior observations of this phenomenon with CNNs (Raff et al., 2018) and Transformers for malicious URL detection (Rudd & Abdallah, 2020).

Convergence speed is ignored as an efficiency metric. All prior LRA methods train for 200 epochs. This is treated as a fixed constant in the literature, but in practice it represents a massive hidden cost — particularly on large datasets like EMBER (1 TB). A method that achieves the same accuracy in 20 epochs instead of 200 provides a 10× reduction in total training time that is rarely factored into efficiency comparisons. The paper makes this a first-class metric, positioning convergence speed as equally important to per-epoch throughput.

The Gap This Paper Fills: A Neuro-Symbolic Reformulation, Not an Approximation

The paper's distinctive intellectual move is to recast self-attention rather than to approximate it. This distinction matters:

• Approximation starts with the true attention mechanism $\text{softmax}(QK^\top/\sqrt{d})V$ and asks: how can we compute something close to this in less time? The answers involve random features, low-rank factorizations, sparsity patterns, or kernel approximations. There is an inherent accuracy-speed tradeoff because the true mechanism is being replaced by something simpler.

• Reconstruction starts with the high-level computational logic of attention — "a set of queries matching against a set of keys, and returning a weighted response of the values for each key" — and asks: is there an alternative mathematical framework that implements this same logic with different complexity characteristics? If successful, there need not be an accuracy-speed tradeoff because the mechanism is not being approximated; it is being reimplemented through a different formalism.

The authors select Holographic Reduced Representations (HRR) (Plate, 1992) as this alternative framework. HRR is a neuro-symbolic approach originating in cognitive science where abstract concepts are assigned to high-dimensional vectors, and operations of binding (associating two concepts into a single representation) and unbinding (retrieving one concept given the other) are performed using the Fast Fourier Transform. The key properties that make HRR suitable for attention:

1. Superposition: Multiple key-value bindings can be summed into a single fixed-size vector $\beta$ representing the entire sequence, with each binding remaining approximately recoverable.
2. Unbinding: Querying $\beta$ with a key's inverse $\mathbf{q}^\dagger$ approximately returns the associated value, even when many pairs are superposed.
3. $\mathcal{O}(TH \log H)$ complexity: The FFT-based bind/unbind operations cost $\mathcal{O}(H \log H)$ each and are performed $T$ times, giving linear scaling in sequence length with only a modest logarithmic factor in hidden dimension.

The critical insight is that these HRR properties directly mirror the query-key-value logic: keys bind to values (creating associations), queries unbind from the superposition (matching against all keys simultaneously), and the result approximates the weighted sum of values that would be returned by explicit query-key matching. The paper does not claim mathematical equivalence — it acknowledges the mechanism is not exact — but rather that it realizes the same high-level strategy through a different operationalization with fundamentally better scaling.

How This Paper Positions Itself

The paper positions itself at the intersection of two literatures that have rarely interacted: efficient Transformer variants and neuro-symbolic computation using HRR. It explicitly notes that "to the best of our knowledge, ours is the first work that attempts to re-create the same logic of self-attention with the HRR" (Section 2). This is not an incremental improvement over prior xformers — it is a category shift from approximation to reformulation.

The F-Net comparison is particularly instructive for understanding this positioning. Both Hrrformer and F-Net use the FFT as a computational primitive, but with fundamentally different philosophies:

• F-Net uses the FFT as a generic mixing operation: apply a 2D FFT to the sequence, replacing attention with an unlearned spectral transformation. There is no claim that this implements attention-like logic — it replaces attention entirely.
• Hrrformer uses the FFT to implement HRR binding/unbinding, which in turn implements the query-key-value logic. The FFT is not the mechanism; it is the computational engine for the symbolic operations that constitute the mechanism.

The paper argues this neuro-symbolic approach — using symbolic HRR operations implemented with neural-style differentiable computations — is what allows the Hrrformer to maintain high accuracy while achieving linear complexity. The empirical claim is that "reconstructing the same logic" (the neuro-symbolic approach) is superior to "using the FFT as a generic differentiable mixing strategy" (the F-Net approach), as evidenced by the Hrrformer's consistent accuracy advantage over F-Net across all benchmarks.

The paper also draws a clear boundary around its scope: it explicitly excludes RNNs, State Space Models (Gu et al., 2022), Legendre Memory Units (Voelker et al., 2019), and IGLOO (Sourkov, 2018) as "beyond the scope of our work." The goal is specifically to explore the value of recasting self-attention within HRR, not to compete with all possible sequence modeling approaches. This focused scope is important for evaluating the contribution — the Hrrformer is not claimed to be the best sequence model overall, but rather a proof that HRR-based attention achieves competitive results with substantial efficiency gains.

Finally, the paper positions itself honestly about a key limitation: it "slightly abuses the assumptions of HRRs" because the query, key, and value vectors produced by neural network layers are not I.I.D. Gaussian, which is the theoretical sufficient condition for clean HRR retrieval. The softmax-based denoising mechanism (explained in detail in Appendix D and discussed in Section 3) is presented as a practical fix for this mathematical violation — a fix that works because the softmax operation is invariant to the approximately constant-magnitude noise that non-I.I.D. vectors introduce into the HRR operations. This is described as a "strategic design" that "allows us to effectively remove additionally created noise," and it represents a key engineering insight that makes the theoretical framework work in practice despite violating its assumptions.

3. Technical Approach

3.1 Reader Orientation

The Hrrformer is a drop-in replacement for the self-attention mechanism inside a standard Transformer — you swap out the attention block and leave everything else (positional embeddings, feed-forward layers, residual connections, layer normalization) unchanged. The system solves the quadratic complexity problem of self-attention by using Holographic Reduced Representations (HRR) to perform the same logical operation — queries matching against keys to return a weighted combination of values — but in $\mathcal{O}(TH \log H)$ time and $\mathcal{O}(TH)$ memory rather than $\mathcal{O}(T^2 H)$ time and $\mathcal{O}(T^2)$ memory.

3.2 Big-Picture Architecture (Diagram in Words)

The Hrrformer modifies only the attention sub-layer of a Transformer encoder. Information flows through five sequential stages within a single attention head:

1. Linear projection: The input sequence $\mathbf{X} \in \mathbb{R}^{T \times H}$ is projected into queries $\mathbf{Q}$, keys $\mathbf{K}$, and values $\mathbf{V}$ using three learned linear transformations — exactly as in standard self-attention. These are split into $h$ heads, each operating on a $H' = H/h$ dimensional subspace.

2. HRR binding (superposition construction): For each head independently, every key-value pair $(\mathbf{k}_t, \mathbf{v}_t)$ is bound together using the HRR circular convolution operation, and all $T$ bound pairs are summed into a single fixed-size vector $\beta \in \mathbb{R}^{H'}$. This $\beta$ represents the entire sequence of key-value associations in one vector. This step replaces the $\mathcal{O}(T^2)$ explicit key-query interaction matrix.

3. HRR unbinding (querying): Each query $\mathbf{q}_t$ is unbound from the superposition $\beta$ using the HRR inverse operation, producing an approximate value vector $\hat{\mathbf{v}}_t$ for each position. This simultaneously checks the query against all keys — the HRR formalism allows the unbinding to retrieve the value associated with whatever key best matches the query.

4. Cosine similarity scoring: The extracted $\hat{\mathbf{v}}_t$ is compared against the original value $\mathbf{v}_t$ using cosine similarity, producing a scalar $a_t$ for each position. This scalar reflects how strongly position $t$'s value is "present" in the unbinding response. The $T$ scalars form an attention logits vector $\mathbf{a} \in \mathbb{R}^T$.

5. Softmax denoising and weighted aggregation: A softmax is applied to $\mathbf{a}$ to produce attention weights $\mathbf{w} \in \mathbb{R}^T$. These weights are then used to compute a weighted sum of the original values: $\sum_{t=1}^T w_t \mathbf{v}_t$. Multi-head outputs are concatenated and linearly projected to produce the final attention output.

After this attention block, the standard Transformer feed-forward network, residual connections, and layer normalization are applied normally. The architecture is shown in Figure 3, which visually maps the standard Transformer's query-key-value pipeline to the Hrrformer's bind-unbind-score pipeline, with tensor shapes annotated at each stage.

3.3 Roadmap for the Deep Dive

• First, the formal HRR operations — binding, unbinding, and inversion — because they are the mathematical primitives that the entire attention mechanism rests on; understanding why circular convolution via FFT gives superposition and clean retrieval is essential before seeing how it maps to attention.
• Second, the Hrrformer attention equations (Eqs. 1–4), walking through how the HRR primitives are arranged to implement query-key-value logic, with careful attention to what each equation computes and why the sequence of operations matters.
• Third, the complexity analysis — why the asymptotic costs are $\mathcal{O}(TH \log H)$ time and $\mathcal{O}(TH)$ space, and what the hidden constants are relative to standard attention.
• Fourth, the softmax denoising mechanism (Appendix D) — why the HRR theoretical assumptions are violated by neural network outputs, how this creates uniform-magnitude noise in the attention logits, and why softmax cancels this noise through its shift-invariance property. This is the crucial engineering insight that makes the approach work.
• Fifth, the multi-head extension and integration with the rest of the Transformer — showing that the Hrrformer is truly a drop-in replacement that preserves the multi-head design, the residual connections, and the training pipeline.
• Sixth, implementation details from the provided JAX code snippet — how the abstract equations map to concrete batched tensor operations, including the handling of padding masks.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a method paper whose core idea is that the logical structure of self-attention — queries matching against keys to produce a weighted combination of values — can be reimplemented using the neuro-symbolic operations of Holographic Reduced Representations with linear rather than quadratic complexity, without fundamentally approximating or restricting the attention mechanism.

---

HRR Mathematical Primitives: Binding, Unbinding, and Inversion

The Hrrformer is built on three operations from the HRR framework developed by Plate (1992). To understand the attention mechanism, we must first understand these primitives at a computational level.

Vector representation. In HRR, abstract concepts (like "red" or "cat") are assigned to high-dimensional vectors $\mathbf{x} \in \mathbb{R}^H$. These vectors are, in theory, randomly sampled I.I.D. from a Gaussian distribution with zero mean and variance $1/H$. This random initialization gives the vectors a crucial property: any two distinct random vectors are approximately orthogonal, meaning their dot product is approximately zero. This near-orthogonality is what allows multiple bound pairs to coexist in a single superposition with minimal interference — each pair occupies a nearly orthogonal subspace.

Binding operation ($\oplus$). The binding operation associates two vectors into a single vector of the same dimension. Formally:

$\mathbf{x} \oplus \mathbf{y} = \mathcal{F}^{-1}(\mathcal{F}(\mathbf{x}) \odot \mathcal{F}(\mathbf{y}))$

where $\mathcal{F}$ denotes the Discrete Fourier Transform (implemented via FFT), $\mathcal{F}^{-1}$ is the inverse FFT, and $\odot$ denotes element-wise (Hadamard) multiplication in the frequency domain.

What it computes: The binding operation takes two $H$-dimensional vectors and produces a third $H$-dimensional vector that represents their association. The computation is: (1) transform both vectors to the frequency domain via FFT, (2) multiply corresponding frequency components element-wise, (3) transform the result back to the spatial domain via inverse FFT. This is mathematically equivalent to circular convolution of the two vectors.

Why this form: Circular convolution is commutative ($\mathbf{x} \oplus \mathbf{y} = \mathbf{y} \oplus \mathbf{x}$) and associative, which are essential properties for the superposition logic. More importantly, binding in the frequency domain via element-wise multiplication is $\mathcal{O}(H \log H)$ (dominated by the FFT), whereas naive circular convolution in the spatial domain would be $\mathcal{O}(H^2)$. The FFT-based implementation is what gives the Hrrformer its favorable complexity scaling.

Binding can be thought of as creating a compressed representation of the pair $(\mathbf{x}, \mathbf{y})$ that is the same size as a single vector. This is the key enabler of superposition — many bound pairs can be summed without increasing the representation's dimension.

Inversion operation ($\dagger$). The inverse of a vector is defined as:

$\mathbf{y}^\dagger = \mathcal{F}^{-1}\left(\frac{1}{\mathcal{F}(\mathbf{y})}\right)$

where the division $1/\mathcal{F}(\mathbf{y})$ is applied element-wise to the complex frequency components.

What it computes: The inverse produces a vector that, when bound with the original vector, approximately reconstructs the identity element. The computation is: (1) transform the vector to the frequency domain, (2) take the reciprocal of each complex frequency component, (3) transform back via inverse FFT.

Why this form: In the frequency domain, binding is element-wise multiplication. Therefore, unbinding should be element-wise division (multiplication by the reciprocal). The inverse is the vector whose frequency-domain representation is the reciprocal of the original's frequency components, so that $\mathbf{y}^\dagger \oplus \mathbf{y} \approx \mathbf{1}$ (the identity for binding). This property extends to superpositions: if $\beta = (\mathbf{x} \oplus \mathbf{y}) + (\mathbf{a} \oplus \mathbf{b})$, then $\mathbf{x}^\dagger \oplus \beta \approx \mathbf{y}$ — querying with the inverse of a key retrieves the associated value, even when other key-value pairs are present. The approximation is due to the noise introduced by the other terms in the superposition; under I.I.D. Gaussian assumptions, this noise has expected magnitude proportional to $\sqrt{T/H}$.

Unbinding operation. While the paper uses the notation $\mathbf{q}_t^\dagger \oplus \beta$ for unbinding, this is simply the composition of inversion and binding: first compute the inverse of the query, then bind it with the superposition. The result is a vector that approximates the value originally bound to the matching key.

Superposition property. A critical HRR property exploited by the Hrrformer: multiple bound pairs can be summed into a single vector $\beta$:

$\beta = (\mathbf{k}_1 \oplus \mathbf{v}_1) + (\mathbf{k}_2 \oplus \mathbf{v}_2) + \dots + (\mathbf{k}_T \oplus \mathbf{v}_T)$

and each pair remains approximately recoverable via unbinding with the appropriate key inverse. The recovery quality degrades as $\mathcal{O}(\sqrt{T/H})$ due to interference between the summed terms, but for large $H$ relative to $T$, the interference is manageable. This is the mathematical basis for compressing all $T$ key-value pairs into a single fixed-size representation — which is what eliminates the $\mathcal{O}(T^2)$ bottleneck.

---

The Hrrformer Attention Mechanism: Step-by-Step Construction (Equations 1–4)

The paper defines the Hrrformer attention as a sequence of four operations applied to the projected query, key, and value vectors. We discuss each element-wise (for clarity of the HRR logic), but the implementation operates on batched tensors.

Input setup. For a single attention head with dimension $H'$, we have:

• Queries: $\mathbf{q}_t \in \mathbb{R}^{H'}$ for $t = 1, 2, \dots, T$
• Keys: $\mathbf{k}_t \in \mathbb{R}^{H'}$ for $t = 1, 2, \dots, T$
• Values: $\mathbf{v}_t \in \mathbb{R}^{H'}$ for $t = 1, 2, \dots, T$

These are produced by learned linear projections from the input, exactly as in standard attention. The matrices $\mathbf{Q}, \mathbf{K}, \mathbf{V} \in \mathbb{R}^{T \times H'}$ stack these vectors.

---

Step 1: Construct the key-value superposition (Equation 1).

$\beta = \sum_{i=1}^T \mathbf{k}_i \oplus \mathbf{v}_i$

where $\beta \in \mathbb{R}^{H'}$ is the superposition vector, $\mathbf{k}_i$ and $\mathbf{v}_i$ are the key and value vectors at position $i$, and $\oplus$ is the HRR binding operation (circular convolution via FFT).

What it computes: For every position in the sequence, bind the key and value together (creating an association pair), then sum all $T$ bound pairs into a single vector. This produces one $H'$-dimensional vector that represents the entire sequence of key-value associations.

Why this form: This is the critical step that eliminates quadratic complexity. In standard attention, computing query-key interactions requires explicit $T \times T$ pairwise comparisons. Here, all key-value pairs are compressed into a single representation before any query is processed. The compression is possible because HRR binding and superposition allow multiple associations to coexist in a fixed-size vector with approximate recoverability. The cost is $\mathcal{O}(T \cdot H' \log H')$ — $T$ binding operations, each requiring an FFT of size $H'$ — rather than $\mathcal{O}(T^2 H')$ for explicit pairwise attention.

A subtle design choice: the keys and values are bound before summation. An alternative would be to sum keys and values separately then bind, but $\sum \mathbf{k}_i \oplus \sum \mathbf{v}_i$ would produce cross-terms between different positions (e.g., $\mathbf{k}_1 \oplus \mathbf{v}_2$) that corrupt the association. The per-position binding ensures that each key is associated only with its corresponding value.

---

Step 2: Query the superposition (Equation 2).

$\hat{\mathbf{v}}_t = \mathbf{q}_t^\dagger \oplus \beta$

where $\mathbf{q}_t^\dagger$ is the HRR inverse of the query vector at position $t$, $\beta$ is the key-value superposition from Step 1, and $\hat{\mathbf{v}}_t \in \mathbb{R}^{H'}$ is the extracted value approximation.

What it computes: Unbinds the query from the superposition to retrieve an approximation of the value associated with the key that matches this query. The operation is: (1) compute the frequency-domain inverse of $\mathbf{q}_t$, (2) bind (circularly convolve) this inverse with $\beta$. Because $\beta$ contains $\mathbf{k}_i \oplus \mathbf{v}_i$ terms, the distributive property of circular convolution yields:

$\mathbf{q}_t^\dagger \oplus \beta = \sum_{i=1}^T \mathbf{q}_t^\dagger \oplus \mathbf{k}_i \oplus \mathbf{v}_i$

For positions $i$ where $\mathbf{q}_t \approx \mathbf{k}_i$, the term $\mathbf{q}_t^\dagger \oplus \mathbf{k}_i \approx \mathbf{1}$ (the identity), so that term contributes approximately $\mathbf{v}_i$ to the sum. For positions where $\mathbf{q}_t$ and $\mathbf{k}_i$ are dissimilar, the term contributes structured noise. Thus $\hat{\mathbf{v}}_t$ is approximately the value corresponding to the best-matching key, plus noise from all non-matching positions.

Why this form: This step performs what amounts to a simultaneous query against all keys in $\mathcal{O}(H' \log H')$ time per query, or $\mathcal{O}(T H' \log H')$ for all queries. There is no explicit $T \times T$ comparison — the key information is already compressed in $\beta$, and the HRR unbinding naturally retrieves the value most strongly associated with the query. This is the "single representation of all key-value pairs" concept described in Section 3.

Comment on the abuse of HRR assumptions. Standard HRR theory requires that all vectors be I.I.D. Gaussian for clean retrieval. Here, $\mathbf{q}_t$, $\mathbf{k}_i$, and $\mathbf{v}_i$ are outputs of learned linear layers — they are not I.I.D., they are correlated through the learning process, and they violate the distributional assumptions. The consequence is that $\hat{\mathbf{v}}_t$ contains substantially more noise than the theoretical $\mathcal{O}(\sqrt{T/H})$ bound. The softmax in Step 4 addresses this — but the noise is still present in $\hat{\mathbf{v}}_t$ at this stage, which is why $\hat{\mathbf{v}}_t$ cannot be used directly as the output (the paper reports that doing so "results in degenerate random-guessing performance").

---

Step 3: Compute scalar attention logits via cosine similarity (Equation 3).

$a_t = \text{cosine-similarity}(\mathbf{v}_t, \hat{\mathbf{v}}_t) = \frac{\mathbf{v}_t \cdot \hat{\mathbf{v}}_t}{\|\mathbf{v}_t\| \cdot \|\hat{\mathbf{v}}_t\|}$

where $a_t \in \mathbb{R}$ is the attention logit for position $t$, $\mathbf{v}_t$ is the original value vector at position $t$, and $\hat{\mathbf{v}}_t$ is the extracted value approximation from Step 2.

What it computes: Measures how similar the original value $\mathbf{v}_t$ is to the HRR-extracted approximation $\hat{\mathbf{v}}_t$. If position $t$'s query matched well against the superposition (meaning $\mathbf{q}_t \approx \mathbf{k}_t$), then $\hat{\mathbf{v}}_t \approx \mathbf{v}_t$ (plus noise), and the cosine similarity is high. If position $t$'s query matched poorly, $\hat{\mathbf{v}}_t$ is mostly noise, and the similarity is lower.

Why cosine similarity and not dot product or the HRR dot-product test: The HRR literature prescribes a dot-product test for presence: $\beta^\top \mathbf{y}^\dagger$ should be $\approx 1$ if $\mathbf{y}$ is present in the superposition, and $\approx 0$ otherwise. However, this test assumes I.I.D. vectors with unit expected norms. Neural network outputs violate these conditions — their norms can vary substantially, and they are correlated. Cosine similarity normalizes for vector magnitude, making the score invariant to the scale of the learned representations. Additionally, the paper found that attempting to use $\hat{\mathbf{v}}_t$ directly (without the cosine similarity step) produces degenerate performance — the similarity comparison with the original value acts as a secondary filtering mechanism that suppresses the noise component because noise vectors are, in expectation, orthogonal to the true value vectors.

---

Step 4: Softmax denoising and weighted output (Equation 4).

Let $\mathbf{a} = [a_1, a_2, \dots, a_T]$ be the vector of cosine similarity scores from Step 3. Then:

$\mathbf{w} = \text{softmax}(\mathbf{a}), \quad \text{where} \quad w_t = \frac{\exp(a_t)}{\sum_{j=1}^T \exp(a_j)}$

$\text{Attention}(\mathbf{Q}, \mathbf{K}, \mathbf{V}) = [w_1 \mathbf{v}_1, w_2 \mathbf{v}_2, \dots, w_T \mathbf{v}_T] = \sum_{t=1}^T w_t \mathbf{v}_t$

where $\mathbf{w} \in \mathbb{R}^T$ is the attention weight distribution over positions, and the output for a single query is a weighted sum of the original value vectors.

What it computes: The softmax converts the cosine similarity logits into a normalized probability distribution over positions. Then, instead of outputting the HRR-extracted approximate values $\hat{\mathbf{v}}_t$, the mechanism outputs a weighted combination of the original values $\mathbf{v}_t$, with weights proportional to how strongly each position's value was "detected" in the unbinding response.

Why softmax and why return weighted original values instead of $\hat{\mathbf{v}}_t$: This is the paper's key engineering insight for working around the violated HRR assumptions. The authors explain (Section 3 and Appendix D) that because the query, key, and value vectors are not I.I.D. Gaussian, the noise in each $a_t$ has approximately uniform magnitude across all positions. The softmax function has the property of shift-invariance: $\text{softmax}(\mathbf{x} + \epsilon \cdot \mathbf{1}) = \text{softmax}(\mathbf{x})$ for any constant $\epsilon$. If the noise contribution to each $a_t$ is roughly the same (because the same noisy terms from the superposition appear in all the unbinding computations), then applying softmax cancels this common noise offset and preserves the relative differences between positions.

The paper provides a more formal argument in Appendix D using the $H = 2$ dimensional case: when querying with $\mathbf{q} = \mathbf{a} + \mathbf{z}$ (true key plus noise) versus querying with a non-present key $\mathbf{c} + \mathbf{z}$, the response expressions share many common terms from the superposition structure. The noise vector $\mathbf{z}$ contributes similarly to both queries, so the softmax — invariant to uniform shifts — effectively denoises the relative comparison.

Why output weighted original values rather than $\hat{\mathbf{v}}_t$: There are two reasons. First, $\hat{\mathbf{v}}_t$ is noisy due to the violated HRR assumptions, and using it directly yields random-guessing performance. Second, even under ideal HRR conditions, $\hat{\mathbf{v}}_t$ approximates the value associated with the best-matching key, which is a hard selection rather than a soft weighted average. Standard attention's strength comes from soft, distributed weighting — attending to multiple positions simultaneously. By using the cosine similarity scores to re-weight the original values, the Hrrformer preserves this soft-attention property. The $\hat{\mathbf{v}}_t$ vectors are used only to determine the weights, not to be the output.

---

Summary of the four-step logic flow:

1. Bind all key-value pairs and sum them into $\beta$ → compress the entire sequence into one vector.
2. Unbind each query from $\beta$ → retrieve approximate values for each position.
3. Score the match between original values and retrieved values → produce attention logits.
4. Softmax and re-weight original values → produce the final attention output.

This sequence is designed so that the HRR operations handle the all-pairs query-key interaction (Steps 1–2), while the cosine similarity and softmax handle the noise introduced by violating HRR assumptions (Steps 3–4). Theorem A.1 formalizes that this process "approximates an all-pairs interaction between all queries and key-values," though the approximation is not mathematically exact — it is a structural correspondence rather than an asymptotic convergence guarantee.

---

Complexity Analysis: Why the Hrrformer Scales Linearly

Time complexity per attention head. The dominant operations in the Hrrformer attention are:

• Binding (Equation 1): $T$ binding operations, each requiring one forward FFT and one inverse FFT. Each FFT costs $\mathcal{O}(H' \log H')$. Total: $\mathcal{O}(T H' \log H')$.
• Unbinding (Equation 2): $T$ unbinding operations, each requiring one inverse computation (reciprocal in frequency domain, $\mathcal{O}(H')$) and one binding operation ($\mathcal{O}(H' \log H')$). Total: $\mathcal{O}(T H' \log H')$.
• Cosine similarity (Equation 3): $T$ dot products of $H'$-dimensional vectors plus $T$ norm computations. Total: $\mathcal{O}(T H')$.
• Softmax and weighted sum: $\mathcal{O}(T H')$ for the softmax over $T$ elements and the weighted combination of $T$ vectors of dimension $H'$.

Aggregating across all $h$ heads (each with dimension $H' = H/h$) and all layers, the per-layer time complexity is:

$\mathcal{O}(T H \log H)$

Space complexity per attention head. The Hrrformer stores:

• Query, key, value matrices: $\mathcal{O}(T H')$ each → $\mathcal{O}(T H')$ total.
• The superposition vector $\beta$: $\mathcal{O}(H')$.
• The extracted values $\hat{\mathbf{V}}$: $\mathcal{O}(T H')$.
• The attention logits and weights: $\mathcal{O}(T)$.
• No $T \times T$ attention matrix is ever materialized.

Aggregating across heads and layers, the per-layer space complexity is:

$\mathcal{O}(T H)$

Comparison to standard attention. Standard self-attention requires:

• Time: $\mathcal{O}(T^2 H)$ for the $QK^\top$ multiplication plus $\mathcal{O}(T^2 H)$ for the attention-weights-times-values multiplication.
• Space: $\mathcal{O}(T^2)$ for the attention matrix (stored for backpropagation in training), plus $\mathcal{O}(T H)$ for input and output representations.

The Hrrformer replaces the $\mathcal{O}(T^2 H)$ term with $\mathcal{O}(T H \log H)$. The practical significance of the $\log H$ factor is discussed in the paper: "the hidden size of the network is generally fixed and smaller than the sequence length. Thus we see in practice our design allows for faster execution in training and inference" (Figure 4 caption). For typical configurations (e.g., $H = 256$, $T \geq 4096$), $\log H \approx 8$ while $T$ is in the thousands, so the $\log H$ factor is negligible compared to the $T^2$ term it replaces.

A note on batched implementation. The paper's JAX implementation (Appendix A) handles the binding and unbinding operations in a batched manner across all $T$ positions simultaneously, using the FFT along the feature dimension. The code shows that binding(k, v, axis=-1) applies the FFT-based circular convolution to all positions in parallel, and np.sum(bind, axis=-2) performs the summation in Equation 1 over the sequence dimension. The multi-head splitting and merging follow the standard Transformer pattern: split the feature dimension into $h$ heads, apply attention in parallel within each head, merge back.

---

The Softmax Denoising Mechanism in Detail (Appendix D)

This section explains why the softmax can serve as a denoising step despite the violated HRR assumptions — the most subtle and important design choice in the Hrrformer.

The theoretical ideal. Under standard HRR assumptions (all vectors I.I.D. $\mathcal{N}(0, 1/H)$), the dot-product test for presence works cleanly:

$(\mathbf{a} \oplus \mathbf{b} + \mathbf{c} \oplus \mathbf{d})^\top \mathbf{a}^\dagger \approx 1 \quad \text{(a is present)}$ $(\mathbf{a} \oplus \mathbf{b} + \mathbf{c} \oplus \mathbf{d})^\top \mathbf{z}^\dagger \approx 0 \quad \text{(z is not present)}$

The expectations of these dot products are 1 and 0 respectively, with variance that grows as $\mathcal{O}(T/H)$. When $H$ is large relative to $T$, presence and absence are cleanly separable.

What happens when vectors are not I.I.D. The Hrrformer's query, key, and value vectors are outputs of learned neural network layers. They are:

• Correlated: The linear projections $\mathbf{W}_Q$, $\mathbf{W}_K$, $\mathbf{W}_V$ are learned, and the input $\mathbf{X}$ has structured correlations across positions.
• Non-Gaussian: Neural network activations are not Gaussian-distributed.
• Non-stationary: Mean and variance can vary across positions and across feature dimensions.

Under these violations, the HRR operations still compute something, but the noise is no longer bounded by the $\mathcal{O}(\sqrt{T/H})$ theoretical limit. The paper's key observation, demonstrated through the $H=2$ expansion in Appendix D, is that the noise introduced by non-I.I.D. vectors has approximately equal magnitude across all positions in the cosine similarity logits. This is not a theorem — it is an empirical claim about the structure of the noise.

Why the noise is approximately uniform across positions. Consider the expanded form of the cosine similarity logit for position $t$ when the query at position $t$ matches key $\mathbf{k}_t$ but also contains a noise component $\mathbf{z}$ (i.e., $\mathbf{q}_t = \mathbf{k}_t + \mathbf{z}$). The expansion of $\mathbf{q}_t^\dagger \oplus \beta$ produces terms involving:

• $\mathbf{k}_t^\dagger \oplus \mathbf{k}_t \oplus \mathbf{v}_t$ (the signal: approximately $\mathbf{v}_t$)
• $\mathbf{k}_t^\dagger \oplus \mathbf{k}_i \oplus \mathbf{v}_i$ for $i \neq t$ (cross-talk noise from other positions)
• $\mathbf{z}^\dagger \oplus \mathbf{k}_i \oplus \mathbf{v}_i$ for all $i$ (noise from the query noise interacting with all key-value pairs)

The critical observation is that $\mathbf{z}$ interacts with all positions' key-value pairs in the same summation. When querying with any position $t$, the noise terms involving the superposition structure (the $\beta$ vector) are the same for all queries because $\beta$ is fixed once computed. The only query-specific components are the signal term $\mathbf{k}_t^\dagger \oplus \mathbf{k}_t \oplus \mathbf{v}_t$ and the cross-talk terms $\mathbf{k}_t^\dagger \oplus \mathbf{k}_i \oplus \mathbf{v}_i$. The noise from $\mathbf{z}$ contributes a common offset to all $a_t$ values.

The softmax shift-invariance property. For any vector $\mathbf{x}$ and any scalar $\epsilon$:

$\text{softmax}(\mathbf{x} + \epsilon \cdot \mathbf{1}) = \text{softmax}(\mathbf{x})$

where $\mathbf{1}$ is the all-ones vector. This holds because multiplying all exponentials by $e^\epsilon$ factors out of both numerator and denominator and cancels:

$\frac{\exp(x_i + \epsilon)}{\sum_j \exp(x_j + \epsilon)} = \frac{e^\epsilon \exp(x_i)}{e^\epsilon \sum_j \exp(x_j)} = \frac{\exp(x_i)}{\sum_j \exp(x_j)}$

How this denoises the attention logits. If the non-I.I.D. noise introduces an approximately uniform additive offset $\epsilon$ to all $a_t$ values (relative to what they would be under ideal I.I.D. conditions), then the softmax output is identical to what it would be without that uniform offset. The softmax effectively "ignores" the common-mode noise and preserves only the relative differences between positions — and those relative differences are driven by the signal (which key matches which query), not the noise.

Why this is sufficient but not perfect. The noise is only approximately uniform — it will not be exactly identical across all positions due to the query-specific cross-talk terms. However, the paper's empirical results demonstrate that this approximate uniformity is sufficient for the softmax to produce meaningful attention weights. The alternative — using $\hat{\mathbf{v}}_t$ directly as the output without softmax re-weighting — fails completely, confirming that the cosine-similarity + softmax pipeline is essential for practical performance.

A note on temperature. The paper mentions in a footnote: "We find no meaningful difference in results when using a temperature softmax($\exp(\alpha)[a_1, \dots, a_T]$)." This suggests that the default temperature of 1.0 is adequate and the denoising property is robust — sharpening or softening the distribution does not materially affect the outcome, likely because the relative ordering of the $a_t$ values (not their absolute magnitudes) is what drives the attention weights.

---

Multi-Head Extension and Integration with the Transformer

The Hrrformer preserves the multi-head attention design of the original Transformer. The implementation (Figure 7, Appendix A) shows:

Head splitting. After linear projection, the $H$-dimensional query, key, and value vectors are split into $h$ heads, each operating on $H' = H/h$ dimensions. The code does this with a split function that reshapes from (B, T, H) to (B, h, T, H'). This is identical to standard multi-head attention.

Per-head HRR attention. Each head independently performs the four-step Hrrformer attention (bind → unbind → cosine similarity → softmax re-weight) on its $H'$-dimensional subspace. The heads do not share information during the attention computation — they operate in parallel on different feature subspaces, exactly as in standard multi-head attention.

Head merging. The per-head outputs (each of dimension $H'$) are concatenated along the feature dimension back to dimension $H$, then passed through a final linear projection dense(name='output'). This is the standard multi-head output projection.

Masking. The code includes optional masking for padding tokens: if mask is not None: scale = scale + (1. - mask) * (-1e9). This adds a large negative value to the attention logits of masked positions, causing their softmax weight to be effectively zero. This is standard practice in Transformer implementations.

Integration with the Transformer architecture. The Hrrformer attention block replaces the standard self-attention sub-layer. The rest of the Transformer is unchanged:

• Positional embeddings (learned or fixed, depending on the task — see Table 3)
• Feed-forward network (MLP block with ReLU activation)
• Residual connections around both the attention and feed-forward sub-layers
• Layer normalization (implied by standard Transformer architecture)
• Global average pooling before the classification head (for LRA tasks) or dense layers (for EMBER binary classification)

The block diagram in Figure 2 shows this flow for a single head: input vectors → bind/unbind operations → cosine similarity → softmax attention weights → weighted values → linear projection → output. Figure 3 shows the multi-head extension, with the left panel tracing tensor shapes through a single head and the right panel showing the parallel multi-head structure.

---

Implementation Details from the JAX Code Snippet

The provided code (Figure 7, Appendix A) reveals several implementation choices not explicitly discussed in the main text:

Binding and unbinding as modules. The code defines self.binding = Binding() and self.unbinding = Unbinding() as separate nn.Module instances. These are not further specified in the snippet, but from the HRR definitions they encapsulate the FFT-based circular convolution and inverse operations. They take an axis=-1 argument, indicating the FFT is applied along the feature dimension.

Summation over the sequence dimension. The line bind = np.sum(bind, axis=-2, keepdims=True) implements Equation 1's summation over $T$. The axis=-2 corresponds to the sequence dimension (shape (B, h, T, H') → (B, h, 1, H')). The keepdims=True preserves the dimension for broadcasting in subsequent operations.

Broadcasting in unbinding. The unbinding operation vp = self.unbinding(bind, q, axis=-1) takes the summed superposition of shape (B, h, 1, H') and the query tensor of shape (B, h, T, H'). The broadcasting over the sequence dimension means the same superposition $\beta$ is unbound with each query independently — exactly as specified in Equation 2.

Mask integration. The scale tensor has shape (B, h, T, 1) after the cosine similarity step. Masks are applied before softmax by adding -1e9 to masked positions — a large negative value that drives the softmax weight to zero. The mask shape must broadcast to (B, h, T, 1).

Weighted value computation and output. The line weighted_value = weight * v performs element-wise multiplication between the attention weights (B, h, T, 1) and the value tensor (B, h, T, H'), broadcasting over the feature dimension. This computes $w_t \mathbf{v}_t$ for each position. The merge function (not shown) concatenates heads back to (B, T, H), and the final dense layer projects to the output.

No scaling by $\sqrt{H'}$. Standard attention divides the query-key dot product by $\sqrt{H'}$ to prevent the softmax from saturating. The Hrrformer does not include this scaling because the cosine similarity step already normalizes the vectors to unit length. The cosine similarity values are bounded in $[-1, 1]$ regardless of the feature dimension, so no additional temperature scaling is needed. This is confirmed by the footnote that temperature scaling makes "no meaningful difference."

4. Key Insights and Innovations

Innovation 1: A Category Shift from Approximation to Reformulation — Neuro-Symbolic Reconstruction of Attention Logic

The paper's most fundamental intellectual move is not algorithmic optimization — it is a philosophical shift in what it means to make attention efficient. Prior to this work, the entire xformer literature operated under a single implicit premise: standard attention's exact computation is the gold standard, but it is too expensive, so we must find ways to compute something close to it with less resources. Each family of methods made a different compromise — projection methods compress dimensionality (Wang et al., 2020), sparse methods restrict the attention pattern (Child et al., 2019; Kitaev et al., 2020; Beltagy et al., 2020), random feature methods approximate the softmax kernel (Choromanski et al., 2020), factorized methods compress the sequence length (Ma et al., 2021; Xiong et al., 2021). All of these accept an accuracy-speed tradeoff as inevitable because they start from the premise that the exact mechanism is the target and the approximation is the concession.

The Hrrformer rejects this premise entirely. It asks a different question: can the same high-level computational logic — queries matching against keys, returning weighted values — be implemented through a completely different mathematical formalism that naturally has linear complexity? If the answer is yes, then there need not be a tradeoff at all, because the mechanism is not being approximated; it is being reimplemented through a formalism with different natural scaling properties. This is the difference between approximating $\text{softmax}(QK^\top/\sqrt{d})V$ (the standard approach) and constructing an alternative operation that performs query-key-value retrieval but happens to cost $\mathcal{O}(T H \log H)$ instead of $\mathcal{O}(T^2 H)$.

The choice of Holographic Reduced Representations as that alternative formalism is central to why this shift works. HRR was developed in cognitive science to model how brains might perform symbolic reasoning with distributed neural representations — it is a neuro-symbolic framework, meaning it provides explicit symbolic operations (binding, unbinding, superposition) with well-defined semantics, but implements them through continuous vector arithmetic that is differentiable and trainable with gradient descent. The binding operation semantically means "associate these two concepts," and the unbinding operation semantically means "retrieve what was associated with this concept." These are exactly the semantics of attention: keys are associated with values (binding), and queries retrieve values by matching against keys (unbinding). The formal properties of HRR — that superposition allows many bound pairs to coexist in a single fixed-size vector with approximate recoverability — directly enable the linear-time implementation without structural compromise.

This is fundamentally different from F-Net (Lee-Thorp et al., 2021), which also uses the FFT but as a generic, unlearned mixing operation with no symbolic semantics. F-Net replaces attention; the Hrrformer recasts it. The empirical gap between them — 54.42% vs. 60.83% average LRA accuracy, and an absolute 4.53 percentage point gap on EMBER at $T = 16{,}384$ — is the paper's evidence that symbolic reconstruction outperforms generic spectral mixing. The gap is not marginal; it is the difference between near-state-of-the-art and mediocrity.

Significance beyond performance. This innovation matters because it opens a new design space for efficient attention that is not constrained by the starting point of approximating the dot-product softmax formulation. If other symbolic formalisms — tensor product representations (Smolensky, 1990), Vector Symbolic Architectures, or spiking neural representations — can be mapped to the query-key-value logic, they may offer different complexity-accuracy tradeoffs that are unexplored. The paper does not claim that HRR is the only or best such formalism; it claims that the approach of neuro-symbolic recasting is viable and productive. This is a conceptual contribution that points toward a research program, not just a single model.

Distinguishing incremental from fundamental. This is a fundamental shift in framing, not an incremental improvement. The Hrrformer is not "Performer but with HRR instead of random features" — it does not approximate the softmax attention kernel. It implements an entirely different computation that happens to satisfy the same input-output contract. This is analogous to the difference between approximating a sorting algorithm with a faster heuristic and implementing sorting via a radix sort instead of a comparison sort — the latter achieves genuine complexity improvement by using a different mathematical structure, not by approximating the original algorithm.

Evidence anchoring. The claim that this reformulation preserves attention-like behavior is supported by the weight visualization in Figure 5 (and Appendix C, Figure 9). A single-layer Hrrformer trained on the LRA Image classification task learns attention patterns that recover the 2D structure of CIFAR-10 images from their 1D flattened representation — the weight vectors reshaped to $32 \times 32$ clearly delineate object shapes (airplanes, dogs, frogs, horses). Moreover, different heads learn to attend to different structural features (Head 3 activates differently for dog vs. frog, attending to different pixel intensities rather than simple color intensity). This demonstrates that the HRR-based attention is genuinely learning structured, task-relevant attention patterns — not just producing a generic mixing that happens to work for classification. The standard Transformer's corresponding visualization (Appendix C, Figure 10) is far less interpretable, suggesting the Hrrformer is not merely replicating standard attention's behavior but potentially learning qualitatively different (and in some sense cleaner) attention patterns.

Innovation 2: Softmax as a Denoising Mechanism — Making HRR Work Without Its Theoretical Preconditions

The paper makes a second essential conceptual contribution by identifying and solving a problem that would otherwise make the HRR reformulation fail: the theoretical sufficient conditions for HRR operations never hold in a neural network, but a specific architectural choice — softmax on cosine similarity scores — cancels the resulting noise due to its shift-invariance property.

This is not obvious. The HRR literature (Plate, 1992; Jones & Mewhort, 2007) assumes that all vectors are I.I.D. Gaussian with zero mean and variance $1/H$, and under these conditions, the presence/absence test works cleanly: querying with a present vector gives $\approx 1$, querying with an absent vector gives $\approx 0$. But the Hrrformer's query, key, and value vectors are outputs of learned linear projections applied to correlated, structured input sequences. They violate every distributional assumption: they are correlated across positions (adjacent tokens in a sequence are not independent), they are non-Gaussian (neural network activations follow complex, data-dependent distributions), and their statistics shift during training. Under these violations, the HRR unbinding produces output vectors with noise magnitudes far exceeding the theoretical $\mathcal{O}(\sqrt{T/H})$ bound. The paper reports that attempting to use $\hat{\mathbf{v}}_t$ directly — i.e., treating the HRR-extracted value as the attention output — "results in degenerate random-guessing performance."

The standard response to such noise would be to try to restore the theoretical conditions: initialize vectors to be approximately I.I.D., add regularization to keep them near-Gaussian, or reduce the superposition size $T$ to limit noise. All of these would compromise the method's scalability or expressivity. The paper's insight is more subtle and more powerful: the noise has structure that can be exploited rather than suppressed. The key observation, worked through algebraically in Appendix D for the $H = 2$ case, is that the noise introduced by the non-I.I.D. vectors is approximately uniform across all positions in the cosine similarity logits. This is because the superposition vector $\beta$ is shared across all queries — every query interacts with the same noisy aggregate of all key-value pairs. The query-specific components (the signal from matching keys and the cross-talk from non-matching keys) vary across positions, but the shared noise from the superposition structure contributes a roughly constant offset to every $a_t$.

Softmax is shift-invariant: $\text{softmax}(\mathbf{x} + \epsilon \cdot \mathbf{1}) = \text{softmax}(\mathbf{x})$ for any scalar $\epsilon$. If the noise contributes a common additive offset to all attention logits, the softmax output is identical to what it would be without that offset. The softmax does not "remove" the noise in any active sense — it is simply blind to it, because the noise affects all positions equally and softmax only cares about relative differences. The relative differences, in turn, are driven by the signal: which keys actually match the query, producing higher cosine similarity to the extracted values.

This is a genuinely novel use of softmax. In standard attention, softmax serves two purposes: converting dot-product scores to a probability distribution, and creating a sharp, selective weighting through the exponential's amplification of differences. In the Hrrformer, it serves a third purpose: denoising through shift-invariance. The paper does not claim that softmax was originally designed for this — it observes that softmax happens to have this property and that exploiting it allows the HRR reformulation to work without satisfying HRR's theoretical preconditions. This is a practical engineering insight grounded in a mathematical observation about the structure of the noise.

Comparison to prior work. Prior xformers that use softmax (which is most of them) use it in the standard way: to normalize attention scores. None identify or exploit its shift-invariance as a noise-cancellation mechanism. The Performer (Choromanski et al., 2020) explicitly avoids softmax in its kernel approximation because softmax is what creates the quadratic bottleneck; it approximates softmax with random features rather than using softmax as a denoising step. The Hrrformer's use of softmax is thus orthogonal to the approximation-vs-exact axis — it is repurposing an existing operation for a new function.

Significance beyond this paper. This innovation suggests a more general principle: when using symbolic or neuro-symbolic operations that have theoretical clean-retrieval guarantees under idealized distributional assumptions, one can look for architectural components whose mathematical properties incidentally cancel the noise introduced by distributional violations. Shift-invariance, scale-invariance, or other equivariance properties could serve similar roles in other contexts. This is a design pattern, not just a one-off fix.

Evidence anchoring. The claim that this mechanism is necessary (not just beneficial) is supported by the paper's statement that using $\hat{\mathbf{v}}_t$ directly without the cosine-similarity + softmax pipeline yields random-guessing performance — a stark binary contrast with the Hrrformer's near-state-of-the-art results. The claim that temperature scaling doesn't matter ("no meaningful difference") further supports the shift-invariance interpretation: if the denoising relies on softmax removing a common offset, then sharpening or flattening the distribution should not affect the relative ordering of weights, which is what drives the output. The weight visualizations (Figure 5, Figure 9 in Appendix C) provide qualitative evidence that the resulting attention patterns are meaningful and structured, not noise-dominated.

Innovation 3: Single-Layer Sufficiency — The HRR Formalism Induces Representations That Require Less Hierarchical Processing

Perhaps the most surprising empirical finding in the paper is that the Hrrformer is effective with just a single layer. On 3 of 5 LRA tasks (ListOps, Text, Image), the single-layer Hrrformer achieves the second-best results among all compared methods — including multi-layer versions of the standard Transformer and other xformers. On the Image classification task, the single-layer Hrrformer achieves 48.47% accuracy, outperforming all prior methods except the multi-layer Hrrformer itself (50.45%). This is not a small difference: the standard Transformer requires multiple layers (typically 2–6 in the LRA) and 200 epochs to achieve lower accuracy, while the Hrrformer achieves better results with one layer in 20 epochs.

This finding is significant because it challenges a foundational assumption of the Transformer architecture: that depth is necessary for hierarchical feature extraction. Transformers stack multiple attention layers because each layer can only attend to a limited representational subspace (divided across heads), and composing layers allows higher-order feature combinations. The fact that a single Hrrformer layer suffices suggests that HRR-based attention is doing something qualitatively different in a single pass — potentially because the binding operation itself creates a compressed, higher-order representation of key-value associations in the superposition $\beta$, which the unbinding operation then queries. If each attention head's binding operation effectively creates a distributed encoding of $T$ different key-value pairs, then a single Hrrformer layer may be performing computation that would require multiple standard attention layers to achieve through iterative refinement.

The authors do not fully explain why single-layer sufficiency occurs — they present it as an empirical finding and support it with visualization evidence that a single layer can recover 2D structure from 1D sequences (Figure 5). This is a productive mystery: if the HRR operations inherently perform more powerful per-layer computation than dot-product attention, this has implications for architecture design beyond just efficiency — it could mean shallower networks with the same representational capacity, reducing not just per-layer cost but total depth-related issues like vanishing gradients and training instability.

Comparison to prior work. All prior xformers benchmarked on the LRA use multiple layers (typically matching the standard Transformer's depth). The idea that a single-layer Transformer variant could be competitive was not seriously considered — the LRA benchmark itself was designed assuming multi-layer architectures. The Hrrformer's single-layer results (59.97% average LRA score, only 1.12% below the multi-layer best of 60.83%) effectively establish a new point on the accuracy-efficiency Pareto frontier: it achieves the second-highest speed (683.81 examples/second) and the lowest memory usage (663.88 MB) of any method tested, while maintaining accuracy that beats all but two multi-layer methods. This three-way advantage — near-top accuracy, highest speed, lowest memory — would not be possible without the single-layer capability.

Significance beyond performance. If the single-layer property generalizes to other tasks and datasets, it would change how practitioners approach model design for long-sequence problems. Instead of tuning depth, width, and attention hyperparameters, one might simply use a single-layer Hrrformer as a strong baseline and only add depth when proven necessary. The paper also notes reduced overfitting — the Hrrformer shows a train-test gap of only 6.83% on the LRA Image task, compared to 27.01% for the standard Transformer and 31.13% for Performer (Table 2). Shallower architectures with less overfitting are particularly valuable for domains with limited labeled data, which describes many real-world long-sequence tasks (including the malware detection application that motivated the work).

Distinguishing incremental from fundamental. This is an empirical discovery about the Hrrformer, not a claimed theoretical property of HRR operations. The paper does not prove that single-layer sufficiency follows from the HRR formalism; it demonstrates it and speculates about the mechanism (recovering structural information like 2D geometry from 1D sequences). Future work would need to establish whether this property is specific to HRR-based attention, to the tasks tested, or to some interaction between HRR operations and the particular datasets. As presented, it is a strong empirical finding that raises important questions.

Evidence anchoring. Table 1 shows the single-layer Hrrformer achieving 38.79% (ListOps), 66.50% (Text), 75.40% (Retrieval), 48.47% (Image), and 70.71% (Pathfinder) — competitive with or exceeding multi-layer methods on all tasks. Figure 5 provides visual confirmation of structural learning in a single layer. Figure 6 shows the single-layer Hrrformer in the top-right corner of the accuracy-speed Pareto plot with the smallest memory circle — a visualization that captures all three advantages simultaneously.

Innovation 4: Identifying the Failure of LRA-to-Real-World Transfer — Benchmark Rankings Do Not Predict Performance on Novel Long-Sequence Domains

The paper makes a critical methodological contribution by testing existing xformers on a real-world malware detection task and finding that LRA benchmark rankings do not transfer. Luna-256 and H-Transformer-1D — the two highest-ranked methods on LRA (61.95% and 61.41% average accuracy) — perform substantially worse than the Hrrformer on the EMBER malware classification dataset. Luna-256 peaks at 83.76% accuracy at $T = 8{,}192$ and times out at $T = 16{,}384$; H-Transformer-1D reaches 90.48% at $T = 16{,}384$ but times out at $T = 32{,}768$. The Hrrformer surpasses both in accuracy (91.03% at $T = 16{,}384$) and scales to $T = 131{,}072$ without hitting memory or time limits — the only method besides F-Net to do so, and with substantially higher accuracy than F-Net (89.46% vs. 86.40% at $T = 131{,}072$).

This finding is not merely "the Hrrformer is better on malware." It is a diagnostic about the LRA benchmark itself: the LRA may not capture the specific demands of some real-world long-sequence tasks, and high LRA ranking does not guarantee generalizable efficiency or accuracy. The paper hypothesizes that Luna-256's aggressive compression of the temporal dimension works for LRA tasks but fails when "more complex reasoning and feature extraction over time" is required — which malware byte analysis demands. Raw executable bytes contain hierarchical structure (headers, sections, code, data) with long-range dependencies (function calls, jump tables, string references) that sparse or compressed temporal representations may destroy.

This is significant because the LRA has become the de facto standard for evaluating efficient Transformers, and papers routinely claim state-of-the-art status based solely on LRA scores. The Hrrformer paper provides concrete counter-evidence that LRA-determined "best" methods may underperform in practice, which should encourage the field to (a) include diverse real-world benchmarks in evaluations, (b) be cautious about claims of general superiority based on LRA alone, and (c) investigate why certain compression strategies fail on certain sequence types. The paper also notes that this phenomenon has been observed before in related security domains — CNNs developed for ImageNet do not transfer well to malware byte classification (Raff et al., 2018), and Transformers for malicious URL detection required domain-specific modifications (Rudd & Abdallah, 2020).

Comparison to prior work. Most xformer papers evaluate solely on LRA and/or language modeling benchmarks (WikiText-103, etc.). The EMBER evaluation is distinctive in testing on a domain that is (a) known to require long sequences, (b) known to exhibit domain-specific behavior not captured by standard benchmarks, and (c) practically important (malware detection affects billions of devices). The paper is not the first to use EMBER with neural sequence models, but it is the first to systematically compare xformers on this task and demonstrate the ranking reversal relative to LRA.

Significance beyond this paper. This finding is a contribution to evaluation methodology for efficient sequence models. It argues — through demonstration rather than argumentation — that benchmark-based progress can be misleading if the benchmark does not include tasks that stress the specific failure modes of different efficiency strategies. Temporal compression (Luna), hierarchical coarsening (H-Transformer-1D), and fixed spectral mixing (F-Net) each fail on EMBER in different ways and at different sequence lengths. Understanding which real-world tasks expose which failure modes would enable more principled model selection and more informative benchmark design.

Distinguishing incremental from fundamental. This is a methodological contribution grounded in empirical evidence. It does not propose a new benchmark or metric; it uses an existing real-world task to reveal a limitation of current evaluation practice. As such, it is more of a "cautionary finding" than a "new technique" — but in a field where benchmark-driven development is the norm, cautionary findings about benchmark validity are arguably as important as new architectural proposals.

Evidence anchoring. Figure 1 visually captures the entire argument: Hrrformer (solid line) achieves the highest accuracy and scales furthest; H-Transformer-1D and Luna-256 (dashed lines) perform worse and hit time/memory limits earlier; all other methods (dotted lines) fail even earlier. Table 5 provides the numeric results: the Hrrformer achieves the highest accuracy at every sequence length from $T = 4{,}096$ through $T = 131{,}072$, and is the only method besides F-Net that remains viable at the longest sequence lengths. Table 4 shows that Luna-256, despite topping the LRA rankings, is 28× slower and uses 79.15% more memory than single-layer Hrrformer — efficiency advantages that translate directly to scalability on the EMBER task.

Innovation 5: Convergence Speed as a First-Class Efficiency Metric — 10× Fewer Epochs Reshapes the Cost Calculus

The paper makes a subtle but practically important contribution by treating convergence speed as a primary efficiency metric alongside per-epoch throughput and memory usage. All prior LRA evaluations train for 200 epochs as a fixed protocol. The Hrrformer achieves competitive or superior accuracy in 20 epochs — a 10× reduction in total training time that is independent of per-epoch speed improvements.

The significance of this is that the total cost of training a model is (time per epoch) × (number of epochs). The xformer literature typically reports only the first factor (speed in examples/second, or memory usage as a proxy for maximum batch size). But if Model A takes 200 epochs to converge and Model B takes 20, Model B can be slower per epoch and still be faster overall. The Hrrformer is both faster per epoch (up to 28× faster than Luna-256) and requires fewer epochs, yielding a compound speedup that the paper claims is approximately 280× faster total training time.

This finding also has implications for overfitting and generalization. The Hrrformer's lower train-test gap (Table 2: 6.83% overfitting vs. 27.01% for Transformer and 31.13% for Performer on the Image task) is likely related to early convergence — models that converge faster tend to find flatter minima that generalize better, as established in the optimization literature. The paper does not prove this causal link, but the correlation between fast convergence and low overfitting across the LRA tasks (Appendix Figure 8) is suggestive.

Comparison to prior work. Prior xformer papers treat the 200-epoch protocol as a constant and optimize for per-epoch speed or memory. This implicitly assumes that all methods converge at the same rate, which the Hrrformer paper shows is false. The finding that HRR-based attention converges in 10× fewer epochs raises the question of whether other efficient attention mechanisms might also converge faster if trained differently — or whether the fast convergence is specific to the HRR formulation. The paper does not investigate this, but it opens an avenue for future work on the optimization dynamics of different attention mechanisms.

Significance beyond this paper. Making convergence speed a reported metric could change how the field evaluates efficient attention. If Method A achieves 1% higher accuracy but requires 10× more epochs than Method B, which is "better" depends on the practitioner's constraints. For the EMBER dataset (1 TB), training for 200 epochs is "otherwise prohibitive in its scale" — the 10× reduction makes the difference between feasible and infeasible. For academic benchmarking, where compute budgets are more flexible, accuracy-maximization has been the norm. But as models and datasets grow, training cost will increasingly constrain research, and convergence speed will become as important as per-epoch efficiency.

Evidence anchoring. Table 1 includes an "Epochs" column showing all prior methods at 200 epochs vs. Hrrformer at 20. The learning curves in Appendix Figure 8 show that Hrrformer's test accuracy plateaus around epoch 10–15 on most tasks, with limited improvement thereafter — confirming that 20 epochs is sufficient, not an arbitrary truncation. Table 2 shows the Hrrformer's substantially lower train-test gap on the Image task. The compound 280× training speedup claim is derived from the combination of 28× faster per-epoch throughput (single-layer Hrrformer vs. Luna-256) and 10× fewer epochs, though the paper presents this as approximate rather than exact arithmetic.

5. Experimental Analysis

Evaluation Methodology

• Dataset. Experiments use two distinct benchmarks. The Long Range Arena (LRA) (Tay et al., 2020c) comprises six tasks covering image, text, math, language, and spatial modeling with sequence lengths from 1K to 16K: ListOps (10-way classification, max length 2K), Text (binary sentiment classification on IMDB reviews at character level, max length 4K), Retrieval (binary document similarity on ACL Anthology Network, max length 8K), Image (10-way classification on grayscale CIFAR-10 flattened to 1K sequences), Pathfinder (binary classification of connected circles with distractors, length 1K), and Path-X (harder Pathfinder variant, length 16K). The EMBER malware detection dataset (Anderson & Roth, 2018) provides 600K training samples (300K malicious, 300K benign) and 200K test samples (100K malicious, 100K benign) with raw byte sequences truncated or padded to lengths from 256 to 131,072, representing a real-world long-sequence classification task.

• Base model(s). All experiments use the Hrrformer architecture — a standard Transformer encoder where the self-attention sub-layer is replaced with HRR-based attention, with everything else (positional embeddings, feed-forward networks, residual connections, layer normalization) unchanged. Comparison models include: standard Transformer (Vaswani et al., 2017), H-Transformer-1D (Zhu & Soricut, 2021), Luna-256 (Ma et al., 2021), Performer (Choromanski et al., 2020), Linformer (Wang et al., 2020), F-Net (Lee-Thorp et al., 2021), and others as listed in Table 1. Hyperparameters per task are provided in Table 3, with embedding dimensions varying from 128 to 1,024, MLP hidden dimensions from 64 to 1,024, and 1 to 6 encoder layers depending on the task.

• Metrics. The primary metric is classification accuracy (%) on the test set for each task. For LRA, individual task accuracies are reported alongside an average across the five non-Path-X tasks (Path-X is reported separately since most methods fail on it). Computational efficiency is measured via training speed (examples per second), total training time (seconds per epoch), GPU memory usage (MB), and inference time. Overfitting is reported as the difference between training accuracy and test accuracy (Table 2). Speed and memory measurements for LRA comparison (Figure 6, Table 4) use a fixed configuration: byte-level text classification, batch size 4, sequence length 4,000, embedding size 32, feature size 64, 6 encoder layers, on a single NVIDIA TESLA PH402 32GB GPU.

• Baselines. The paper compares against 13 prior methods from the xformer literature as reported in the LRA benchmark (Tay et al., 2020c): Transformer, Local Attention, Linear Transformer (Katharopoulos et al., 2020), Reformer (Kitaev et al., 2020), Sparse Transformer (Child et al., 2019), Sinkhorn Transformer (Tay et al., 2020b), Linformer (Wang et al., 2020), Performer (Choromanski et al., 2020), Synthesizer (Tay et al., 2020a), Longformer (Beltagy et al., 2020), BigBird (Zaheer et al., 2020), F-Net (Lee-Thorp et al., 2021), Nyströmformer (Xiong et al., 2021), Luna-256 (Ma et al., 2021), and H-Transformer-1D (Zhu & Soricut, 2021). For the EMBER dataset, comparisons are against Transformer, H-Transformer-1D, Luna-256, Performer, Linformer, and F-Net (Figure 1, Table 5). All baselines are evaluated under the same hardware constraints and timeout limits.

• Generation budget / compute accounting. The paper does not use "generations" as a compute unit — the Hrrformer is a single-pass feed-forward model, not a search or sampling method. Compute efficiency is measured in wall-clock time (seconds per epoch or inference), throughput (examples per second), and peak GPU memory (MB). All LRA models are trained for 200 epochs (standard protocol); the Hrrformer is trained for only 20 epochs. For EMBER, models are trained for 10 epochs with an exponential batch size decay schedule: batch size = max(2^(16−log2 T), 1) to push each model to its maximum feasible sequence length under a 10,000-second per-epoch timeout and 32GB GPU memory limit across 16 GPUs. This accounts for the practical constraints that make quadratic-complexity methods infeasible.

• Cross-validation / statistical protocol. No cross-validation or statistical significance testing is reported. The LRA results follow the standard evaluation protocol from Tay et al. (2020c) with fixed train/test splits. The EMBER dataset has a pre-defined train/test split (600K/200K). The paper notes that the Pathfinder task has an ambiguity: the originally reported "hard" version differs from the "easy" version in the released code; the Hrrformer is evaluated on the hard version and the paper assumes other methods use the hard version, though F-Net authors indicated using the easy version and other authors had not clarified at time of writing. The paper acknowledges this creates uncertainty in the Pathfinder comparisons.

---

Main Quantitative Results

Long Range Arena Accuracy

Headline result. The multi-layer Hrrformer achieves 60.83% average accuracy across the five main LRA tasks (Table 1), ranking third overall behind Luna-256 (61.95%) and H-Transformer-1D (61.41%). The single-layer Hrrformer achieves 59.97% — only 1.12 percentage points behind Luna-256 — while being the only method besides Luna to achieve a Pareto improvement over the standard Transformer on every task. Critically, both Hrrformer variants achieve these results in 20 epochs, compared to 200 epochs for all other methods.

Task-by-task breakdown (Table 1).

• ListOps (2K): Hrrformer single-layer achieves 38.79%, multi-layer achieves 39.98% — second and third best overall, behind only H-Transformer-1D (49.53%). All other methods score between 15.82% and 37.98%.
• Text (4K): Hrrformer single-layer achieves 66.50% (second best), multi-layer achieves 65.38%, behind H-Transformer-1D (78.69%) but competitive with other top methods (Nyströmformer 65.52%, Luna-256 65.78%).
• Retrieval (4K): Hrrformer multi-layer achieves 76.15%, single-layer achieves 75.40%. Both trail the top two methods (Nyströmformer and Luna-256 at 79.56%) by a meaningful margin (~4 percentage points), but substantially outperform the Transformer baseline (57.46%).
• Image (1K): Hrrformer multi-layer achieves 50.45% — the single best result across all methods, exceeding Luna-256 (47.86%) and H-Transformer-1D (46.05%). Single-layer Hrrformer achieves 48.47%, which alone would rank second.
• Pathfinder (1K): Hrrformer multi-layer achieves 72.17%, single-layer achieves 70.71%. These are competitive but below the top performers: Luna-256 (78.55%), Performer (77.05%), and F-Net (77.78% on the easy version; 77.78% reported for the hard version is uncertain).
• Path-X (16K): All methods fail, including the Hrrformer.

Divergence from prior best methods. The two prior LRA leaders — Luna-256 and H-Transformer-1D — show task-specific weaknesses relative to the Hrrformer. Luna-256 excels on Pathfinder (78.55% vs. Hrrformer's 72.17%) but is substantially worse on Image (47.86% vs. 50.45%). H-Transformer-1D dominates ListOps (49.53% vs. 39.98%) and Text (78.69% vs. 65.38%) but falls behind on Image (46.05% vs. 50.45%) and Retrieval (63.99% vs. 76.15%). The Hrrformer is the only method besides Luna that exceeds the Transformer baseline on every task — it never catastrophically fails where the Transformer succeeds.

Convergence speed (Figure 8, Appendix). The learning curves for the multi-layer Hrrformer across all five LRA tasks show that test accuracy reaches near-asymptotic levels by epoch 10–15, with minimal improvement in the final 5–10 epochs. Training for 200 epochs (as prior work does) would not meaningfully improve results. The paper notes that "the 10-epoch performance of our Hrrformer is still highly competitive."

Overfitting reduction (Table 2). On the Image classification task, the Hrrformer's train accuracy is 57.28% with test accuracy 50.45%, yielding a train-test gap of only 6.83%. This is dramatically lower than all compared methods. For reference: the standard Transformer achieves 69.45% train / 42.44% test (27.01% gap), Performer achieves 73.90% / 42.77% (31.13%), and Linformer achieves 97.23% / 38.56% (58.67% — severe overfitting). The Hrrformer achieves the best test accuracy while having the lowest training accuracy among all methods — indicating it does not memorize training patterns but learns representations that genuinely generalize.

---

Computational Efficiency: Speed, Memory, and Throughput (Figure 6, Tables 4 and 6–7)

Training throughput comparison (Table 4). Measured on the LRA text classification task with 6 encoder layers, batch size 4, and sequence length 4,000:

• Single-layer Hrrformer: 683.81 examples/second — 28× faster than Luna-256 (23.74 ex/s), 9× faster than H-Transformer-1D (32.03 ex/s), and 64× faster than the standard Transformer (10.68 ex/s).
• Multi-layer Hrrformer: 246.45 examples/second — 10× faster than Luna-256, 7.7× faster than H-Transformer-1D, and 23× faster than the standard Transformer.
• The only method approaching Hrrformer speeds is Local Attention (93.51 ex/s) and Linformer (77.49 ex/s), both of which have substantially lower LRA scores (46.06% and 51.36% vs. Hrrformer's 59.97–60.83%).

GPU memory usage (Table 4). Single-layer Hrrformer uses 663.88 MB — 79.15% less than Luna-256 (3,184.66 MB) and 97% less than the standard Transformer (22,134.52 MB). Multi-layer Hrrformer uses 934.41 MB — 70.66% less than Luna-256. This is the lowest memory consumption of any method tested.

Inference time analysis (Tables 6 and 7). Inference measurements on the full LRA text classification test set across batch sizes 2–32 reveal:

• Single-layer Hrrformer inference: 31.82 seconds total (785.67 examples/second) — the fastest method, followed by multi-layer Hrrformer at 33.38 seconds (748.95 ex/s). These are 26× faster than the standard Transformer (813.67 seconds).
• Hrrformer inference time scales gracefully with batch size: from 152.99 seconds at batch size 2 to 80.83 seconds at batch size 32. In contrast, the standard Transformer inference time is nearly flat across batch sizes (975.98 seconds at batch size 2 to 807.13 seconds at batch size 32) — the Hrrformer with a batch size of 2 is still 5× faster than the Transformer with batch size 32.
• Memory at inference: single-layer Hrrformer uses 527.56 MB regardless of batch size (the paper reports the same value for both single- and multi-layer, which may indicate the measurement captures model parameters rather than activation memory, or an error in the table).

Compound training speedup. Combining per-epoch throughput and epoch count: single-layer Hrrformer is 28× faster per epoch than Luna-256 and trains in 20 rather than 200 epochs, yielding approximately 280× total training time reduction. The paper presents this as an approximate figure ("≈280× faster to train").

---

EMBER Malware Classification: Accuracy and Scalability (Figure 1, Table 5, Figure 4)

Headline result. The Hrrformer achieves the highest accuracy across nearly all sequence lengths on the EMBER malware classification task, and is one of only two methods (alongside F-Net) that scales to the maximum tested sequence length of T = 131,072 without running out of memory or time.

Accuracy by sequence length (Table 5):

• At T = 256, Linformer leads narrowly (79.52% vs. Hrrformer's 78.06%), with Performer at 78.00% and Transformer at 74.87%. The Hrrformer does not dominate at very short sequences.
• At T = 4,096, Hrrformer takes the lead at 90.59%, with H-Transformer-1D close behind at 90.14%, Performer at 89.06%, and Transformer at 88.43%.
• At T = 8,192, Transformer has already run out of memory. Hrrformer achieves 90.89%, ahead of Performer (89.88%), H-Transformer-1D (88.90%), Linformer (86.53%), Luna-256 (83.76%), and F-Net (86.36%).
• At T = 16,384 — the peak Hrrformer accuracy — it reaches 91.03%. H-Transformer-1D achieves 90.48% but times out at the next sequence length. Luna-256 achieves only 83.55% and also times out at T = 32,768. Performer and Linformer survive to T = 16,384 (85.68% and 86.94%) but time out at T = 32,768.
• From T = 32,768 to T = 131,072, only Hrrformer and F-Net remain viable. Hrrformer maintains 90.65% → 90.13% → 89.46%, while F-Net plateaus at 86.29% → 86.45% → 86.40%. The accuracy gap grows from 4.36 percentage points at T = 32,768 to 3.06 points at T = 131,072 (Hrrformer's accuracy degrades slightly more at extreme lengths, but remains substantially above F-Net).

Failures of prior methods (Figure 1, Table 5):

• Standard Transformer: Runs out of memory at T = 8,192. Even at T = 4,096 where it fits, accuracy (88.43%) is below Hrrformer's (90.59%).
• H-Transformer-1D: Runs out of time at T = 32,768 (timeout at 10,000 seconds per epoch). Accuracy at survivable lengths is competitive with Hrrformer (within ~0.5 percentage points at T = 16,384) but the hierarchical decomposition does not scale as far.
• Luna-256: Performs substantially worse at all sequence lengths — peaks at only 83.76% at T = 8,192, far below Hrrformer's 90.89% at the same length. Times out at T = 32,768. The aggressive temporal compression fails to capture the fine-grained sequential dependencies needed for malware byte analysis.
• Performer and Linformer: Both time out at T = 32,768 and achieve lower accuracy than Hrrformer at all lengths above T = 256 (Performer peaks at 89.88% at T = 8,192; Linformer peaks at 88.73% at T = 1,024 and declines thereafter).
• F-Net: Survives to T = 131,072 with the fastest runtime, but accuracy trails Hrrformer by 3–5 absolute percentage points at all lengths above T = 1,024. This gap demonstrates the value of HRR's neuro-symbolic reconstruction over F-Net's generic Fourier mixing.

Runtime analysis (Figure 4, Table 5). Despite F-Net being the only faster method, the absolute time difference between F-Net and Hrrformer shrinks as sequence length increases. At T = 256, F-Net takes 84.84 seconds/epoch vs. Hrrformer's 91.35 seconds (7.7% slower). At T = 131,072, F-Net takes 9,800.97 seconds vs. Hrrformer's 9,237.78 seconds — Hrrformer is actually 5.7% faster at extreme lengths. This is attributed to the hidden size H being fixed while sequence length T grows: Hrrformer's $\mathcal{O}(T H \log H)$ complexity becomes relatively more favorable as the constant overhead of the FFT amortizes over longer sequences, while the $\log H$ factor (approximately 8 for H = 256) becomes negligible compared to the sequence length.

Batch size decay effects. The apparent quadratic growth in runtime for all linear-complexity methods in Figure 1 is an artifact of the exponential batch size reduction (halved each time sequence length doubles). This was a deliberate experimental choice to push each model to its maximum sequence length — without batch size decay, linear-complexity methods would show approximately linear runtime growth. The paper is transparent about this design choice.

---

Ablation Studies and Robustness Checks

Single-layer vs. multi-layer performance (Table 1): The single-layer Hrrformer achieves 59.97% average LRA accuracy compared to 60.83% for the multi-layer variant — a difference of only 0.86 percentage points. On Image classification, the single-layer even outperforms all prior multi-layer methods (48.47% vs. Luna-256's 47.86%). This establishes that depth provides minimal marginal benefit for the Hrrformer, and a single layer is sufficient for competitive performance. The corresponding efficiency gains are substantial: single-layer is 2.8× faster in training throughput and uses 29% less memory than multi-layer (Table 4). This finding is not ablated in the traditional sense (the paper does not sweep layer counts from 1 to 6 and show a plateau) but the comparison between 1 and the task-appropriate layer counts (3–6 from Table 3) demonstrates that additional layers provide diminishing returns.

Temperature scaling in softmax (footnote, Section 3): The paper states: "We find no meaningful difference in results when using a temperature softmax(exp(α)[a_1, …, a_T])." This ablation — though reported only as a footnote — confirms that the default temperature of 1.0 is adequate and the denoising mechanism is robust to changes in the softmax sharpness. Since the theoretical justification for softmax denoising relies on shift-invariance (not on any specific temperature), this result is consistent with the mechanism and suggests the relative ordering of attention logits — not their absolute scale — drives performance.

Mask handling (code snippet, Appendix A): The implementation adds -1e9 to masked positions' attention logits before softmax, following standard Transformer practice. While not an ablation study, this design choice implies that mask positions contribute noise to the superposition β (they are included in Equation 1's summation) but are zeroed out in the final attention weights. An implicit ablation would be whether excluding masked positions from the superposition entirely improves results — this is not tested.

Pathfinder version ambiguity (Table 1 footnote): The paper acknowledges that the Pathfinder task has an "easy" and "hard" version, and that different prior works report results on different versions. The Hrrformer achieves 80.81% on the easy version (single-layer) and 80.77% (multi-layer). The main table reports 70.71% and 72.17% on the hard version. Since the paper cannot confirm which version each baseline used, the Pathfinder comparisons have an unquantified uncertainty — methods reported as outperforming the Hrrformer (e.g., Luna-256 at 78.55%, F-Net at 77.78%) may have used the easy version. This is not an ablation but a data quality limitation that the paper discloses honestly.

Batch size scaling (Tables 6 and 7): While not presented as a formal ablation, the inference time measurements across batch sizes 2–32 serve as a robustness check on the Hrrformer's throughput advantage. The Hrrformer maintains its speed advantage at all batch sizes, including the small-batch regime (batch size 2) where overhead typically dominates. The fact that Hrrformer inference at batch size 2 (152.99 seconds) is 5× faster than Transformer inference at batch size 32 (807.13 seconds) is a particularly strong demonstration that the efficiency gains are not dependent on large-batch parallelism.

Train/test overfitting gap (Table 2): The overfitting comparison on the Image task spans 11 baseline methods plus Hrrformer. The Hrrformer's 6.83% gap is not just the lowest — it is in a qualitatively different regime from all other methods, which range from 21.73% (Local Attention) to 58.67% (Linformer). This is not presented as the result of a specific regularization technique but as an emergent property of the HRR-based attention formulation, possibly related to the fast convergence and single-layer effectiveness. The learning curves in Appendix Figure 8 provide cross-task corroboration: the training and test curves remain closer for Hrrformer across ListOps, Text, Retrieval, Image, and Pathfinder than is typical for Transformer models, though the paper does not provide baseline overfitting curves for direct comparison.

LRA-to-EMBER transfer (Figures 1 vs. Table 1): The most informative implicit ablation is the cross-benchmark comparison. Methods that excel on LRA (Luna-256: 61.95% average) perform poorly on EMBER (83.76% peak accuracy, times out at T = 16,384). Methods that are fast on LRA (F-Net: 54.42% average, fastest runtime) maintain speed on EMBER but lose accuracy (86.40% vs. Hrrformer's 89.46% at T = 131,072). The Hrrformer is the only method that performs well on both benchmarks — near-top LRA accuracy with top EMBER accuracy and scalability. This cross-domain consistency is not ablated but demonstrated through the dual-benchmark evaluation design.

---

Critical Assessment

Does the Hrrformer Actually Reconstruct Attention, or Does It Approximate It?

The paper's central claim is that the Hrrformer performs "the same high-level strategy" as standard self-attention through a neuro-symbolic reformulation rather than an approximation. The experimental evidence supports functional similarity — the Hrrformer achieves competitive accuracy, learns interpretable attention patterns (Figure 5), and reproduces the expected behavior of attending to relevant input regions — but does not directly test whether the Hrrformer's internal computations correspond to standard attention's computations.

The weight visualizations (Figure 5, Appendix Figure 9) provide the strongest qualitative evidence: the learned attention patterns recover 2D spatial structure from 1D sequences, and different heads learn distinct, interpretable attention functions. However, these visualizations compare Hrrformer weights to nothing (or to the standard Transformer's less interpretable averaged attention matrix in Appendix Figure 10). A stronger test would be: for the same input, do the Hrrformer's attention weights correlate with the standard Transformer's attention weights? If the Hrrformer genuinely reconstructs attention, there should be some correspondence — not identity, but correlation — between which positions each mechanism attends to. This experiment is not performed.

The claim of "recasting" rather than "approximating" is thus supported primarily by the competitive accuracy and the structural argument that the HRR operations mirror the query-key-value logic, rather than by direct evidence that the Hrrformer computes something functionally equivalent to softmax attention. The results are consistent with the claim but do not prove it — an alternative interpretation is that the Hrrformer has discovered a different but equally effective attention-like mechanism whose relationship to standard attention is more metaphorical than mathematical.

The Single-Layer Claim: A Genuine Finding or an Artifact of Task Simplicity?

The paper presents single-layer sufficiency as a major benefit. The evidence is strong but limited: 3 of 5 LRA tasks show near-parity between single-layer and multi-layer performance, and the Image task shows single-layer superiority over all prior multi-layer methods. However, the paper does not systematically investigate why single-layer suffices. Several alternative explanations are not tested:

• Task difficulty ceiling: LRA tasks, despite long sequences, may not require deep hierarchical reasoning. If the tasks are solvable with relatively shallow feature extraction, any sufficiently expressive attention mechanism might work with one layer. The standard Transformer's poor single-layer performance (which is not reported — we don't know if a single-layer Transformer was tested) would need to be established as a baseline to claim that single-layer sufficiency is specific to the Hrrformer rather than being a property of the tasks.
• Embedding dimension compensation: The Hrrformer uses relatively large embedding dimensions (256–1,024, Table 3) for single-layer configurations. A single wide layer may have comparable representational capacity to multiple narrower layers. Without controlling for total parameter count between single-layer Hrrformer and multi-layer baselines, the single-layer advantage could be partially explained by width rather than HRR-specific properties.
• No comparison to single-layer baselines: The paper does not report single-layer results for any baseline method. We cannot determine whether the Hrrformer's single-layer sufficiency is unique or whether other xformers also perform well with one layer (but were never tested because the LRA protocol prescribes multiple layers).

The overfitting reduction (Table 2) provides complementary evidence — shallow architectures typically overfit less — but again, without single-layer baselines, we cannot attribute this specifically to the HRR mechanism.

Computational Efficiency: Impressive but Incompletely Benchmarked

The speed and memory measurements are the paper's strongest empirical contribution because they are objective, well-controlled, and dramatic. The 28× throughput improvement and 79% memory reduction over Luna-256 (Table 4) are measured under identical conditions (same hardware, batch size, sequence length, number of layers). However, several aspects of the efficiency evaluation merit scrutiny:

• Batch size 4 for throughput measurements: This is a small batch size that may not reflect production deployment. The inference time measurements across batch sizes 2–32 (Table 6) partially address this — Hrrformer remains faster at all sizes — but the headline 28× figure is specific to batch size 4.
• The 280× total training speedup is approximate, not measured: This figure multiplies the 28× per-epoch speedup (single-layer vs. Luna-256) by the 10× epoch reduction. But this is a comparison of two different Hrrformer configurations against two different aspects of Luna-256 — the per-epoch speedup uses 6-layer Hrrformer vs. 6-layer Luna-256 (Table 4), while the epoch reduction compares Hrrformer's 20 epochs vs. the LRA standard of 200 epochs. These numbers cannot be simply multiplied because the speedup measurement configuration (6 layers, batch size 4) differs from the accuracy measurement configuration (task-specific layers from Table 3, task-specific batch sizes). A fair compound speedup would need to measure total wall-clock time to reach a target accuracy on a fixed task.
• No FLOPs counting: The paper measures wall-clock time and memory, not FLOPs. Wall-clock time is more practically relevant but depends on hardware efficiency (FFT operations may be more or less optimized than matrix multiplications on different GPU architectures). FLOPs would provide a hardware-independent efficiency measure and allow theoretical scaling analysis parallel to the pretraining scaling laws literature.
• Path-X failure is under-analyzed: The Hrrformer fails on Path-X (T = 16,384), as do all methods. Since handling long sequences is the paper's primary motivation, the failure on the LRA's longest task deserves more investigation. Is this a fundamental limitation of the HRR approach (e.g., the superposition noise grows with T, and at T = 16,384 the softmax denoising is no longer sufficient)? Or is it a training configuration issue (e.g., the model was not tuned for this specific task)? The paper does not diagnose the failure mode.

The EMBER Results: Strong but Confounded by Batch Size Effects

The EMBER evaluation (Figure 1, Table 5) demonstrates that the Hrrformer is the only method combining high accuracy with extreme sequence length scalability. This is a genuinely impressive result for a real-world application where other methods fail outright. However, two factors complicate interpretation:

• Batch size decay confounds runtime comparisons: The exponential batch size reduction (halving at each doubling of T) means that runtime comparisons at different sequence lengths are not like-for-like — they measure different amounts of work per epoch. This was necessary to push models to their memory limits, but it makes the runtime-vs-sequence-length curves (Figure 1, Figure 4) difficult to interpret. A more informative comparison would fix the total tokens per epoch (batch size × sequence length) and measure runtime.
• Single epoch of EMBER is 600K samples: With batch size as low as 1 at T = 131,072, training for 10 epochs means processing 6 million samples with 131K-length sequences — a substantial computational effort. The paper does not report total training time for EMBER, only per-epoch time at each sequence length (Table 5). The fact that Hrrformer completes this in 9,237.78 seconds/epoch at T = 131,072 with batch size 1 (meaning ~92 seconds per sample) suggests that practical training at this scale is borderline even for the Hrrformer, though vastly more feasible than for any competitor (most of which cannot run at all).

What the Experiments Leave Unanswered

The paper's experiments are thorough for a conference paper but leave several important questions open:

1. How does Hrrformer scale to larger hidden dimensions? All experiments use H ≤ 1,024. Standard Transformers for language modeling use H = 768–12,288. The $\mathcal{O}(H \log H)$ factor from the FFT could become non-trivial at large H, potentially eroding the efficiency advantage. Without testing at larger scales, we cannot assess whether Hrrformer is suitable for large language model pretraining or only for the moderate-scale tasks tested.

2. Does Hrrformer support autoregressive decoding? The paper only evaluates encoder-only architectures for classification tasks. Autoregressive generation requires causal masking (preventing attention to future positions) and typically uses encoder-decoder or decoder-only architectures. The Hrrformer's superposition β sums over all positions — implementing causal masking would require computing a separate β at each time step, which would be $\mathcal{O}(T^2 H \log H)$ and defeat the purpose. The paper does not discuss this limitation, which is significant because autoregressive generation is the dominant use case for Transformers in NLP.

3. How does accuracy scale with sequence length on LRA? The LRA tasks have fixed sequence lengths. The EMBER results show accuracy slightly degrading at extreme lengths (91.03% at T = 16,384 to 89.46% at T = 131,072), but this could be due to truncation effects (more information lost) rather than model degradation. A controlled experiment varying sequence length on a fixed task (e.g., Image classification at resolutions from 32×32 to 256×256) would reveal whether HRR attention has a fundamental accuracy-length tradeoff.

4. Is the softmax denoising mechanism necessary, or would other normalization schemes work? The paper's theoretical argument for softmax as a denoising step is elegant but only tested implicitly (the method works, and removing the softmax/cosine-similarity pipeline causes random-guessing performance). Alternative normalization schemes — LayerNorm applied to the attention logits, or learned temperature parameters, or direct use of dot-product scores — are not compared. The paper asserts softmax shift-invariance is key, but does not experimentally verify that this specific property (as opposed to any normalization that produces a probability distribution) is responsible for the denoising.

5. No comparison to state-space models or RNN-based approaches. The paper explicitly excludes SSMs (Gu et al., 2022), Legendre Memory Units, and IGLOO as "beyond scope." This is a legitimate scope limitation, but it means we cannot assess whether the Hrrformer's efficiency advantages hold relative to the broader landscape of linear-complexity sequence models, as opposed to just the xformer subfield. Since the paper's primary claimed contribution is enabling Transformers for very long sequences, and SSMs have recently shown strong results on exactly these length regimes, this omission limits the practical significance assessment.

Summary Assessment

The experimental evidence strongly supports the paper's claim that the Hrrformer achieves competitive accuracy with substantially better computational efficiency than existing xformers, and that this efficiency translates to practical scalability on a real-world long-sequence task where most competitors fail. The convergence speed, memory efficiency, and single-layer capability are well-demonstrated. The claim of "reconstructing attention" rather than approximating it is supported by functional similarity (accuracy, interpretable weights) but not by direct mechanistic comparison. The efficiency claims are measured rigorously within the tested regime but have not been validated at larger scales (wider models, autoregressive generation) or against non-xformer baselines. The 280× training speedup figure is an illustrative compound estimate, not a directly measured quantity, and should be interpreted as approximate.

6. Limitations and Trade-offs

6.1 The Hrrformer Cannot Perform Autoregressive Decoding Without Losing Its Efficiency Advantage

The assumption or constraint. The Hrrformer is designed and evaluated exclusively as an encoder-only architecture for classification tasks. All experiments — LRA benchmarks and EMBER malware detection — process entire sequences in parallel to produce a single classification output. The core operation that enables linear complexity, Equation 1, constructs a single superposition vector β by summing over all positions in the sequence:

β = ∑_{i=1}^T k_i ⊕ v_i

This computation assumes access to the full sequence at once. In autoregressive generation — the dominant paradigm for language models and any task requiring token-by-token output — the model must prevent attention to future positions (causal masking). With standard attention, this is achieved by masking the upper triangle of the T × T attention matrix, preserving O(T² H) complexity but with a constant factor reduction. With the Hrrformer, enforcing causal masking would require computing a separate superposition β_t for each time step t that sums only over positions 1, 2, …, t. Since this must be done for all T positions, the total cost becomes O(T² H log H) — worse than standard attention's O(T² H) due to the log H factor, and completely defeating the purpose of the reformulation.

The paper never discusses this constraint. The entire evaluation is on encoder-only classification pipelines, and the introduction frames the motivation entirely around "sequence modeling" (which includes generation) and "self-attention" (which is used in both encoders and decoders). The abstract claims the Hrrformer makes "transformers" feasible for long sequences, but the standard Transformer is most famously a sequence-to-sequence model — and the decoder half of that architecture is incompatible with the Hrrformer's efficiency mechanism.

The consequence. The Hrrformer is not a general-purpose replacement for self-attention in all Transformer architectures. It works for bidirectional encoding (classification, retrieval, representation learning) but not for unidirectional decoding (language generation, translation, any autoregressive task). This dramatically limits its applicability: the majority of large-scale Transformer deployments (GPT-series, LLaMA, Chinchilla, PaLM) are decoder-only autoregressive models. Malware detection from raw bytes — the motivating application — is classification and therefore works, but many other long-sequence domains (genomics with base-pair generation, audio waveform generation, code completion) require autoregressive decoding.

The paper's framing as enabling "transformers" for long sequences is therefore misleading without this qualification. A more accurate characterization would be: the Hrrformer enables Transformer encoders for very long classification sequences, but does not solve the long-sequence problem for the autoregressive generation tasks that dominate NLP and constitute the majority of large-model training FLOPs.

What evidence exists in the paper. There is no evidence — the limitation is not tested, discussed, or even acknowledged. Every experiment in Section 4 uses encoder-only architectures: the LRA tasks all use global average pooling over the encoder output followed by a classification head (Section 4.2), and EMBER uses "back-to-back dense layers with ReLU activation" on the encoder output (Section 4.1). The code snippet in Appendix A implements a SelfAttention module with no causal mask support beyond padding masks. The multi-head diagram in Figure 3 shows only the encoder dataflow.

Mitigation status. The paper does not address this at all. A potential mitigation — not discussed — would be to use the Hrrformer for the encoder and standard attention for the decoder in encoder-decoder architectures, but this only helps when the encoder processes long sequences (e.g., document-level translation) and the decoder processes shorter outputs. For the typical case where both input and output are long, this provides no benefit. The limitation is fundamental to the HRR reformulation: superposition over all positions inherently requires all positions to be known. Future work would need a fundamentally different approach — perhaps chunked or hierarchical autoregressive HRR — that the paper does not suggest.

---

6.2 Path-X Failure Demonstrates a Fundamental Sequence Length Ceiling That Is Not Diagnosed

The assumption or constraint. The Hrrformer, like every method evaluated, fails on the Path-X task — the only LRA benchmark with sequence length T = 16,384 (Table 1). The failure is total: the result is simply listed as "FAIL" with no accuracy number, implying performance no better than random guessing. This is the same outcome as the standard Transformer and every other xformer tested. Yet the paper's motivating application (malware detection) pushes sequence lengths to T = 131,072 on EMBER. The paper claims success at these extreme lengths — 89.46% accuracy at T = 131,072 — but cannot explain why Path-X fails at an order of magnitude shorter sequence length.

This matters because it reveals that the Hrrformer's scalability is task-dependent in ways the paper does not characterize. Path-X is a spatial reasoning task requiring the model to determine whether two circles are connected by a path in the presence of distractor paths — it demands genuine long-range dependency resolution across the full 16K positions. EMBER malware classification, by contrast, may not require equally long-range dependencies — executable file formats have strong local structure (headers, section tables at predictable offsets, instruction sequences that are locally coherent), and a model could achieve high accuracy by attending primarily to local neighborhoods with occasional long-range references. If the Hrrformer's Path-X failure is due to the HRR superposition noise overwhelming the signal when long-range dependencies are essential, then the strong EMBER results at T = 131,072 may reflect the relative locality of the malware classification task rather than genuine long-range reasoning capability.

The consequence. Practitioners cannot assume that the Hrrformer will scale to long sequences on any task just because it does on EMBER. The failure on Path-X at T = 16,384 — a sequence length fully 8× shorter than the Hrrformer's maximum tested EMBER length — means there is some combination of task structure and sequence length at which HRR-based attention breaks down. The paper does not identify what that combination is, so there is no guidance for predicting whether a new task with long sequences will work.

More specifically: the noise in the HRR superposition β grows with √(T/H') under ideal I.I.D. assumptions (Section 3). At Path-X's T = 16,384 and with the Pathfinder task's H' = 128 (from H = 1024, h = 8 heads per Table 3), the theoretical noise scaling is √(16,384/128) = √128 ≈ 11.3. On the EMBER task at T = 131,072 with H' = 32 (H = 256, h = 8), the noise scaling is √(131,072/32) = √4,096 = 64. This is substantially worse — yet the Hrrformer succeeds on EMBER and fails on Path-X. This inversion of the naive noise prediction suggests either that (a) the theoretical noise scaling is a poor guide to practical performance because the softmax denoising compensates differently for different noise structures, or (b) the effective difficulty of Path-X is not captured by sequence length alone because the spatial reasoning task requires preserving fine-grained positional relationships that the HRR operations destroy even at moderate T. The paper does not investigate either possibility.

What evidence exists in the paper. Only the "FAIL" entry in Table 1. There is no error analysis, no per-head weight visualization for Path-X (unlike the rich visualizations for the Image task in Figure 5 and Appendix Figure 9), no measurement of intermediate representation quality, and no discussion of why this task fails when longer EMBER sequences succeed. The paper treats Path-X failure as an unremarkable universal outcome — "all methods fail" — but this universal failure is precisely what should motivate investigation into why all methods fail and whether the Hrrformer's specific failure mode differs from others. The fact that the Hrrformer does not fail on even longer EMBER sequences makes the Path-X failure more puzzling, not less.

Mitigation status. The paper does not address, diagnose, or even acknowledge this discrepancy. The Path-X result is simply reported alongside the universal failure, with no connection drawn to the EMBER scalability results. The paper suggests no experiments to isolate whether the failure is due to sequence length, dependency distance, task complexity, or an interaction between these factors and the HRR formulation. A minimal diagnostic — training the Hrrformer on Pathfinder (which it solves at T = 1,024 with 72.17% accuracy) with artificially padded longer sequences to see if length alone causes degradation — would help distinguish length effects from task effects, but is not performed.

---

6.3 The 280× Training Speedup Figure Is a Composite Estimate, Not a Directly Measured Quantity, and Overstates Practical Gains

The assumption or constraint. The paper's headline claim, appearing in the abstract and conclusion, is that the Hrrformer is "up to 280× faster to train" or "≈280× faster to train." This figure is derived by combining two separate measurements that come from different experimental configurations:

• Per-epoch speedup: Single-layer Hrrformer processes 683.81 examples/second vs. Luna-256's 23.74 examples/second (Table 4) — a 28× improvement. This measurement uses 6 encoder layers, batch size 4, sequence length 4,000, embedding size 32, and feature size 64 for the speed benchmark.
• Epoch reduction: The Hrrformer trains for 20 epochs vs. the LRA standard of 200 epochs — a 10× reduction.

Multiplying 28× by 10× yields approximately 280×. But these numbers come from different configurations measured under different conditions:

• The 28× throughput comparison uses a fixed 6-layer configuration for the speed benchmark (Table 4), but the accuracy results in Table 1 use task-specific layer counts from Table 3: 6 layers for ListOps and Text, 4 for Retrieval, 3 for Image, 2 for Pathfinder. The 28× figure is not measured at the layer counts where accuracy is reported.
• The 10× epoch reduction is claimed relative to "prior works" training for 200 epochs, but the paper only trains the Hrrformer for 20 epochs — it does not demonstrate that other methods require 200 epochs to converge on the LRA tasks. It is possible (though unlikely) that Luna-256 or Performer would also converge in fewer epochs if trained with early stopping, and the 200-epoch protocol is a fixed benchmark convention rather than a convergence requirement.
• The compound 280× figure does not account for the fact that the single-layer Hrrformer (which achieves the 28× throughput) has lower accuracy than the multi-layer version on 2 of 5 LRA tasks. If a practitioner needs the multi-layer accuracy, the per-epoch speedup drops to 10× (multi-layer Hrrformer: 246.45 ex/s vs. Luna-256: 23.74 ex/s, Table 4), and the compound figure becomes ~100× rather than 280×.
• Total training time depends on dataset size. The LRA tasks have relatively small training sets (e.g., 25K for Image, 160K for ListOps). On larger datasets, per-epoch time dominates total cost, and the 10× epoch advantage might shrink if other methods can use early stopping.

The consequence. The 280× figure is an illustrative upper bound, not a measured empirical result. It conflates the best-case per-epoch speedup (single-layer Hrrformer at a fixed benchmark configuration) with an epoch reduction that is presented as inherent to the method but may partially reflect the LRA's arbitrary 200-epoch protocol. Practitioners using this figure to estimate training cost reductions in their own settings would likely overestimate the savings, perhaps substantially — particularly if they need multi-layer accuracy or operate on datasets where convergence speed differences are smaller.

The paper is transparent that the 280× figure applies specifically to "the Long Range Arena benchmark" (Section 5, "≈280× faster to train"), but it does not disaggregate the components or discuss their conditional validity. The figure has been prominently featured in the abstract, conclusion, and discussions of the paper, making it likely to be cited without these qualifications.

What evidence exists in the paper. The component measurements exist but are scattered: Table 4 provides the throughput numbers for the fixed 6-layer, batch-size-4 benchmark; Table 3 provides the actual layer counts used for accuracy; Appendix Figure 8 provides learning curves showing Hrrformer convergence by epoch 10–15. What is missing is a unified measurement: total wall-clock time to reach a target accuracy on a fixed task, comparing Hrrformer against the best competitor under their respective optimal configurations. This is the only measurement that would validly support a compound speedup claim. The paper does not provide it.

Mitigation status. The paper presents the component measurements honestly (the throughput in Table 4, the epoch counts in Table 1, the learning curves in Appendix Figure 8) but does not acknowledge the compositional issue. The 280× figure is used as a summary without caveats. A more careful presentation would report the compound figure as "up to 28× per-epoch speedup combined with 10× fewer epochs, suggesting approximately 280× total training time reduction in the best case" and explicitly note the configuration mismatch between the throughput and accuracy benchmarks.

---

6.4 The Softmax Denoising Mechanism Is Theoretically Motivated but Never Experimentally Validated, and Its Failure Mode Is Unknown

The assumption or constraint. The entire Hrrformer mechanism depends on a specific mathematical property of the softmax function — shift-invariance — to cancel noise introduced by violating HRR's I.I.D. Gaussian assumptions. This is the paper's central engineering insight: because the query, key, and value vectors are outputs of learned neural network layers (not I.I.D. Gaussian), the HRR unbinding produces noisy approximate values \hat{v}_t. But the noise is claimed to be "approximately uniform across all positions" in the cosine similarity logits, so the softmax — which is invariant to constant additive shifts — effectively removes it (Section 3, Appendix D).

The paper provides a theoretical argument for this in Appendix D using an algebraic expansion of the H = 2 case, which demonstrates that the shared terms in the superposition contribute common noise to all positions' logits. However, this is a motivational derivation, not a proof. It shows that under the specific structure of the HRR computation, there exist shared terms that could produce uniform-magnitude noise, but it does not prove that (a) the noise is actually uniform in practice with learned, correlated neural network representations, (b) that the non-uniform component of the noise is small enough to be negligible, or (c) that the softmax denoising mechanism continues to work as T grows, as H changes, or as the model depth increases.

The paper offers two pieces of implicit validation: (1) using \hat{v}_t directly without the cosine-similarity + softmax pipeline "results in degenerate random-guessing performance" (Section 3), confirming that something in this pipeline is necessary; and (2) temperature scaling of the softmax makes "no meaningful difference" (footnote, Section 3), which is consistent with shift-invariance (temperature affects relative scaling but does not break shift-invariance). Neither of these validates that the mechanism works because of shift-invariance as opposed to some other property of the pipeline (e.g., the cosine similarity normalization itself, or the softmax simply providing a sharpening effect that any normalization would provide).

The consequence. The Hrrformer's behavior under distribution shift, architectural variation, or adversarial input is unpredictable without understanding the denoising mechanism's actual dynamics. Specifically:

• At what sequence length does the denoising fail? The theoretical noise in HRR superposition grows as O(√(T/H')). The softmax shift-invariance argument assumes the noise is uniform across positions, but the non-uniform component also grows with T. At some sequence length — task-dependent and not characterized — the non-uniform noise should dominate, and the softmax can no longer cancel it. The Path-X failure at T = 16,384 may be an instance of this, but EMBER's success at T = 131,072 suggests the failure threshold is task-specific. Without characterizing this threshold, practitioners cannot predict when the Hrrformer will work.
• Does the mechanism work differently for different head dimensions? The algebraic expansion in Appendix D uses H = 2 for tractability. The shift-invariance argument does not depend on H, but the structure of the noise might — larger H means more terms in the dot products, potentially averaging out some noise components. The paper does not analyze this.
• Could an adversary exploit the denoising mechanism? If the softmax is removing a common offset from attention logits, an adversary who can manipulate the input to create non-uniform noise could cause the attention to focus on attacker-chosen positions. This is speculative but relevant for the malware detection application (adversarial evasion is a central concern in security ML).

What evidence exists in the paper. Two qualitative pieces: the statement about degenerate performance without the pipeline (Section 3), and the footnote about temperature insensitivity. The Appendix D derivation is motivational mathematics, not an empirical validation. There is no experiment that directly tests the shift-invariance claim — for example, by measuring the variance of the noise component across positions, by comparing softmax to other shift-invariant normalizations (e.g., sparsemax, entmax), or by ablating the cosine similarity step to test whether an alternative similarity metric with different noise properties works equally well.

Mitigation status. The paper does not acknowledge this as a limitation. The softmax denoising argument is presented as an explanation for why the method works, not as a hypothesis requiring validation. The paper treats the empirical success of the Hrrformer as sufficient evidence that the mechanism is effective, without isolating whether the denoising works specifically through shift-invariance or through some other property of the pipeline. This is a gap in the paper's mechanistic understanding of its own method.

---

6.5 Evaluation Is Limited to Moderate Hidden Dimensions and Short Per-Sample Sequences; Scaling Behavior at Large Model Sizes Is Unknown

The assumption or constraint. All experiments in the paper use relatively small hidden dimensions H and head dimensions H' compared to production Transformer models:

• LRA tasks (Table 3): Embedding dimensions range from 128 (Retrieval) to 1,024 (Pathfinder). Head dimensions H' range from 32 (Retrieval: H = 128, h = 4) to 128 (Pathfinder: H = 1024, h = 8, Image: H = 256, h = 4 → H' = 64).
• EMBER (Table 3): Embedding dimension 256, 8 heads → H' = 32.
• Speed benchmark (Table 4): Embedding size 32, feature size 64 — even smaller.

By contrast, contemporary production Transformers use hidden dimensions from 768 (BERT-base) to 12,288 (GPT-3 Large), with head dimensions typically 64–128. The Hrrformer's computational complexity is O(T H log H), meaning the log H term — negligible at H = 256 (log 256 ≈ 8) — becomes more significant at production scales: log 768 ≈ 9.6, log 4096 ≈ 12, log 12288 ≈ 13.6. While still logarithmic, the constant factor matters: an FFT-based binding operation at H = 4096 costs approximately 12/8 = 1.5× more per dimension than at H = 256, and total per-layer cost is O(T * H * log H).

More importantly, the head dimension H' determines the noise properties of the HRR superposition. The theoretical noise scales as O(√(T/H')). At H' = 32 (EMBER) and T = 131,072, the noise factor is √(4,096) ≈ 64. At H' = 64 (typical for larger models), this improves to √(2,048) ≈ 45 — better, but how noise interacts with the softmax denoising at these scales is not tested. Conversely, if practitioners use the Hrrformer with standard head dimensions (H' = 64–128) to match typical Transformer configurations, the log H cost increases, potentially eroding the speed advantage relative to optimized sparse attention implementations.

The consequence. The paper's efficiency claims — 28× faster than Luna-256, 79% less memory, linear scaling in T — are validated only for the small-to-moderate model sizes tested. Whether these advantages persist, shrink, or grow at larger scales is unknown. This matters because the Hrrformer is motivated by making Transformers feasible for very long sequences — but production-scale Transformers for very long sequences would likely also need large hidden dimensions to have sufficient capacity. The paper does not demonstrate that the Hrrformer simultaneously supports large H and large T.

There is also a more subtle concern: the FFT is typically implemented on GPU via the cuFFT library. cuFFT performance relative to matrix multiplication (cuBLAS) depends on the FFT size, batch count, and GPU architecture. At small H (≤ 256), the FFT overhead is low and the linear complexity advantage dominates. At large H (≥ 4096), the log H factor grows, and the constant factors of cuFFT vs. highly-optimized cuBLAS matrix multiplications could shift the crossover point. The paper's throughput measurements (Table 4) use tiny embedding sizes (32) and may not reflect performance at realistic scales.

What evidence exists in the paper. All hyperparameters in Table 3 show embedding dimensions ≤ 1,024 and head dimensions ≤ 128. The paper provides no scaling study varying H while holding other parameters constant, and no measurements of FFT vs. matrix multiplication cost at different dimensions. The claim that "the hidden size of the network is generally fixed and smaller than the sequence length" (Figure 4 caption) is true for the tested configurations but is not a general law — large language models routinely have H comparable to or larger than modest sequence lengths (e.g., GPT-3: H = 12,288, context window = 2,048).

Mitigation status. The paper does not acknowledge this as a limitation or discuss how the Hrrformer's efficiency scales with hidden dimension. The complexity analysis in Section 3 presents O(T H log H) as an asymptotic bound without discussing constant factors or the practical regime of H. The paper does not suggest experiments or theoretical analysis to characterize the H-dependence. This is understandable for a conference paper introducing a new method — scaling studies are expensive — but the absence of even a small-scale ablation (e.g., measuring throughput at H = 64, 128, 256, 512 on a single task) leaves a significant gap in the efficiency characterization.

---

6.6 The Evaluation Does Not Compare Against Non-Transformer Sequence Models, So the Claim of Being the "First Viable Transformer" for Malware Is Meaningful Only Within the Transformer Family

The assumption or constraint. The paper explicitly scopes itself to comparing against other xformers (efficient Transformer variants) and explicitly excludes RNNs, State Space Models (Gu et al., 2022), Legendre Memory Units (Voelker et al., 2019), and IGLOO (Sourkov, 2018) as "beyond the scope of our work" (Section 2). The abstract and conclusion claim the Hrrformer is "the first viable Transformer for such long malware classification sequences" and achieves "near state-of-the-art accuracy on LRA benchmarks." But "state-of-the-art" here means "state-of-the-art among Transformer variants" — not among all sequence models. The LRA benchmark includes results from non-Transformer models in its original paper (Tay et al., 2020c), but the Hrrformer paper only compares against the Transformer-variant subset.

This is a legitimate scope limitation for a paper focused on recasting self-attention within the HRR framework. However, the practical motivation — enabling deep learning for malware detection at T = 100,000+ — does not require a Transformer-based solution. If a State Space Model or an RNN variant achieves better accuracy, faster training, or lower memory on EMBER at these sequence lengths, then the Hrrformer is not the best solution to the motivating problem — it is merely the best Transformer-based solution. The claim of being "the first viable Transformer" carries weight only if Transformer-level accuracy is actually needed for the task; if simpler or more efficient non-Transformer models already work well, the contribution is primarily of intellectual interest (demonstrating that attention logic can be recast in HRR) rather than practical significance.

The consequence. A practitioner deciding how to build a malware classifier for long byte sequences would want to know: should I use the Hrrformer, or should I use a State Space Model (S4, S4D, Mamba), or an RNN variant, or a 1D CNN with dilated convolutions? The paper provides no evidence to answer this question. The EMBER results show that the Hrrformer outperforms other xformers, but the non-Transformer approaches that have shown strong results on long-range sequence modeling (particularly S4 and its variants on Path-X and long-range audio tasks) are not evaluated. It is possible — though not demonstrated — that an S4 model would match or exceed the Hrrformer's accuracy on EMBER with even better efficiency.

This limitation is particularly relevant because the paper's primary finding about LRA-to-EMBER transfer failure (Luna-256 ranking first on LRA but performing poorly on EMBER) is presented as a caution about benchmark validity. If the paper is arguing that LRA rankings do not reliably predict real-world performance, then the absence of non-Transformer LRA leaders from the EMBER evaluation undermines the practical conclusion: we don't know whether the Hrrformer is actually the best approach for malware detection, only that it is the best among the Transformer variants tested.

What evidence exists in the paper. None — the scope exclusion is explicit. The paper does not cite EMBER results from any non-Transformer sequence model, nor does it provide LRA results from State Space Models or other non-Transformer approaches for context. The LRA baseline table (Table 1) omits the non-Transformer results that appeared in the original LRA paper (Tay et al., 2020c), such as the MLP-Mixer baseline and various RNN architectures. The paper's comparison is strictly within the xformer family.

Mitigation status. The paper draws a clear scope boundary in Section 2, acknowledging the exclusion. It does not present this as a limitation, but rather as a focused research scope: "Our goal is to explore the value of re-casting self-attention within the neuro-symbolic framework of HRR. As such, other sequence modeling approaches are out of scope." This is intellectually honest — the paper is about HRR-based attention, not about sequence modeling in general. However, the practical framing ("first viable Transformer for malware," "up to 280× faster to train") implicitly makes claims about practical utility that are weakened by the missing comparison. A fairer conclusion would be: among Transformer variants, the Hrrformer is the first to scale to T = 131,072 on EMBER with high accuracy; whether it is the best overall approach to long-sequence malware classification remains to be established through comparison with non-Transformer models.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper introduces a genuinely different way of thinking about efficient attention — not as an approximation problem but as a recoding problem. This distinction is subtle but has substantial consequences for how the field might approach the quadratic complexity bottleneck going forward.

The conceptual shift is this: prior work on efficient Transformers has overwhelmingly operated under the premise that the exact softmax dot-product attention formulation is computationally intractable, so we must find ways to compute something close to it with fewer resources. This premise creates an inherent accuracy-speed tradeoff — the closer you get to exact attention, the more you pay. The Hrrformer challenges this premise by asking whether a completely different mathematical formalism can implement the same computational contract (queries matching against keys, returning weighted values) with naturally linear complexity. If the answer is yes — and the paper provides evidence that it is — then the accuracy-speed tradeoff is not a law of nature but an artifact of the specific mathematical formulation we've chosen to implement attention. This is a reframing of the problem space, not an incremental improvement within the existing space.

The magnitude of this shift should not be overstated. The Hrrformer is not a paradigm shift in the sense that Transformers replaced RNNs — it does not propose a new architecture class or demonstrate order-of-magnitude improvements in capability. It is a reframing with moderate practical impact (competitive accuracy, substantial efficiency gains at tested scales) and potentially large intellectual impact if the neuro-symbolic recoding approach proves generalizable. The paper's most important contribution may be opening a design space that has been largely invisible to the ML community: using symbolic vector operations (binding, unbinding, superposition) as computational primitives for neural network components, rather than as cognitive models or knowledge representation tools. The HRR literature has existed in cognitive science and computational neuroscience for decades (Plate, 1992; Jones & Mewhort, 2007; Eliasmith et al., 2012) but has seen minimal adoption in deep learning. The Hrrformer demonstrates that at least one core deep learning operation — self-attention — can be productively reformulated in HRR terms with competitive results and efficiency benefits. This lowers the barrier for exploring whether other operations (cross-attention, routing, memory retrieval, graph message-passing) might also benefit from HRR-based reformulation.

A concrete reconciliation the paper provides is between two competing philosophies in efficient attention: structure-preserving approximation (Linformer, Performer, Nyströmformer — which try to maintain the mathematical form of attention while reducing cost) and structure-replacing mixing (F-Net, Synthesizer — which abandon attention's logic entirely in favor of cheaper operations). The Hrrformer demonstrates a third path: structure-preserving reformulation, where the logic is maintained but the mathematics is changed. The consistent accuracy advantage over F-Net (60.83% vs. 54.42% LRA average; 91.03% vs. 86.00% on EMBER at T = 16,384) provides evidence that preserving the query-key-value logic matters — it is not sufficient to just have any cheap mixing operation. Yet the efficiency advantage over approximation methods (28× faster than Luna-256, 79% less memory) demonstrates that preserving logic through reformulation can be more efficient than approximating the original formulation. This suggests a research prioritization shift: developing new mathematical formalisms for attention-like operations may be more productive than further optimizing approximations to the dot-product softmax formulation.

The paper also provides a valuable caution about benchmark-driven progress. The finding that LRA rankings do not transfer to the EMBER malware detection task — Luna-256 ranks first on LRA but performs substantially worse than Hrrformer on EMBER, while H-Transformer-1D ranks second on LRA but times out on EMBER at moderate sequence lengths — should give the field pause about treating LRA as a sufficient evaluation. This is not a new methodological concern (benchmark overfitting is well-known), but the paper provides specific, quantitative evidence that the best LRA methods fail on a real-world long-sequence task with different structural properties. The implication is that the efficient Transformer field needs multi-domain evaluation as a standard practice, not as an exceptional addition — and that benchmarks designed to stress-test specific efficiency strategies (e.g., temporal compression, sparsity patterns, low-rank approximation) would be more informative than aggregate rankings on a fixed task suite.

Follow-Up Research This Work Enables

Characterizing the Hrrformer's sequence-length ceiling through controlled length scaling on Pathfinder. The paper's most puzzling result is that the Hrrformer succeeds on EMBER at T = 131,072 but fails on Path-X at T = 16,384. A minimal diagnostic experiment would train the Hrrformer on the Pathfinder task (which it solves at T = 1,024 with 72.17% accuracy) with artificially padded sequences at lengths T = 2,048, 4,096, 8,192, 16,384 while keeping the task structure identical. If accuracy degrades smoothly with padded length, the failure is noise-related and predictable via the √(T/H') scaling. If accuracy collapses suddenly at a specific length, there may be a phase transition in the softmax denoising mechanism. If accuracy remains high regardless of padding, the Path-X failure is task-specific (the spatial reasoning requires preserving positional relationships that HRR destroys) rather than length-specific. This experiment would transform the Path-X failure from an unexplained anomaly into a diagnostic that reveals the Hrrformer's fundamental limitations — a negative result that would refine our understanding more than any additional positive result.

Directly validating the softmax denoising mechanism through ablations and noise measurements. The paper's central engineering claim — that softmax shift-invariance cancels HRR noise — is theoretically motivated but never experimentally validated. A follow-up study should measure the actual noise structure: for a trained Hrrformer on a fixed task, compute the attention logits a_t for each position, then measure the variance of the logits across positions and decompose it into a shared component (uniform across positions) and a position-specific component. If the shift-invariance hypothesis is correct, the shared component should dominate and the position-specific residual should be small relative to the signal. Further, replace the softmax with alternative shift-invariant normalizations (sparsemax, entmax, or a simple x - mean(x) followed by softmax) and with shift-dependent normalizations (standard softmax with a learned bias per position). If shift-invariance specifically is the mechanism, non-shift-invariant alternatives should underperform. If any normalization that produces a probability distribution works equally well, the mechanism is not shift-invariance but some other property (e.g., the cosine similarity step alone is sufficient, and softmax just provides a convenient output distribution). This experiment would convert the denoising claim from a plausible story to an empirically grounded mechanism.

Scaling the Hrrformer to larger hidden dimensions (H = 768 to H = 4,096) and measuring the FFT overhead relative to matrix multiplication. The paper's efficiency claims are validated only at small hidden dimensions (32–256). The O(H log H) factor from the FFT becomes more significant at larger scales, and the crossover point where the Hrrformer loses its advantage over optimized sparse attention or low-rank methods is unknown. A systematic benchmark measuring per-layer forward and backward pass time for Hrrformer vs. standard attention vs. Performer vs. Linformer at H = 128, 256, 512, 768, 1024, 2048, 4096 with fixed T = 4,096 would characterize the practical scaling envelope. The relevant metric is not just wall-clock time but also FLOPs (to measure hardware-independent efficiency) and peak memory (which often constrains production deployment). If the Hrrformer's advantage persists to H = 1,024 (typical for BERT-large and moderate generative models), it becomes relevant for a much broader set of applications. If the advantage erodes beyond H = 512, the method is best suited to the moderate-scale, very-long-sequence regime that the paper already demonstrates — useful but narrower than the paper implies.

Extending the Hrrformer to autoregressive decoding via chunked or blockwise HRR. The most significant architectural limitation of the current Hrrformer is its incompatibility with causal masking — the superposition β sums over all positions, requiring full sequence access. A natural extension would be chunked HRR attention: divide the sequence into non-overlapping blocks of length C, compute a separate superposition β_b for each block, and use standard attention within each block (with causal masking) while using HRR-based attention across blocks. For autoregressive generation, the model would compute a new β_b only when advancing to a new block, incurring O(T/C * C H log H) = O(T H log H) total cost — still linear in T with a controllable constant factor. The key design choice is the block size C: too small and intra-block attention is cheap but cross-block dependencies are coarse; too large and the HRR superposition becomes noisy. Evaluating such a model on language modeling (WikiText-103) or long-range text generation would test whether HRR-based attention can be made practical for the autoregressive use case that dominates large-scale Transformer deployment. This is likely the single most important extension for determining whether the Hrrformer is a niche method for classification encoders or a general-purpose attention replacement.

Combining HRR attention with State Space Models to understand the relationship between symbolic superposition and continuous state representations. The paper explicitly excludes SSMs from comparison, but the two approaches have a suggestive structural parallel: both compress the entire sequence history into a fixed-size state (the SSM's hidden state; the Hrrformer's superposition β), and both query that state to produce position-specific outputs. The difference is that SSMs use continuous dynamical systems with learnable transition matrices, while the Hrrformer uses discrete symbolic operations (binding/unbinding) with fixed mathematical structure. A hybrid architecture — using an SSM to learn a compressed sequence representation and HRR operations to perform structured queries against that representation — could potentially combine the SSM's strong empirical performance on very long sequences (Gu et al., 2022 show S4 solving Path-X) with the Hrrformer's interpretable attention patterns and faster convergence. A concrete experiment: replace the Hrrformer's superposition β (Equation 1) with the output of an S4 layer, then apply Equations 2–4 (unbinding, cosine similarity, softmax re-weighting) to produce attention weights. This tests whether the HRR query mechanism is beneficial even when the sequence compression is learned rather than constructed via binding. If it works, it suggests that HRR-style querying is a general-purpose attention mechanism that can operate on top of any sequence compression.

Adversarial robustness evaluation of HRR attention for malware detection. The motivating application — malware detection — operates in an explicitly adversarial domain where attackers modify binaries to evade classifiers. The Hrrformer's softmax denoising mechanism relies on the noise being approximately uniform across attention logits; an attacker who understands this mechanism might construct byte sequences that produce systematically non-uniform noise, causing the attention to focus on attacker-chosen positions or to distribute uniformly (degrading to random guessing). A red-team evaluation would apply gradient-based adversarial attacks (PGD, CW) to trained Hrrformer malware classifiers and measure the perturbation required to flip predictions, comparing against CNN and standard Transformer baselines (where they exist). If the Hrrformer is more robust (plausible, because HRR operations are non-linear in ways that might be harder to gradient-optimize against), this strengthens the practical case for the malware application. If it is more vulnerable, the denoising mechanism may create an attack surface that requires mitigation before deployment. Either outcome is informative; the current paper provides no robustness analysis despite the explicitly adversarial application domain.

Practical Applications and Downstream Use Cases

Malware detection from raw executable bytes at scale. This is the paper's motivating application and the one where the Hrrformer's advantages are most directly demonstrated. The EMBER results (Table 5) show the Hrrformer achieving 91.03% accuracy at T = 16,384 and maintaining 89.46% accuracy at T = 131,072 — the only method besides F-Net that scales this far, and with substantially higher accuracy than F-Net (86.40% at T = 131,072). For a production malware detection pipeline processing files with typical sizes of 100KB–10MB (T ≈ 100,000 to T ≈ 10,000,000), the Hrrformer provides the first Transformer-based architecture that can process entire files without chunking or truncation. This matters because chunked approaches (Rudd et al., 2022) lose cross-chunk dependencies — a function call at byte offset 5,000 may reference a string at byte offset 500,000, and chunked attention with a limited window cannot model this. The Hrrformer's O(T H log H) complexity means processing a 10MB file (T = 10,000,000) requires roughly 10,000,000 × 256 × 8 ≈ 2 × 10^10 operations per attention layer — feasible on a single GPU for inference. The practical deployment scenario is: use the Hrrformer as a first-pass classifier that processes raw bytes end-to-end, replacing multi-stage pipelines that extract handcrafted features (PE header parsing, section analysis, import table extraction) with a single learned model. The 79% memory reduction (Table 4) means this can run on commodity GPUs rather than requiring datacenter-grade hardware.

Long-document classification and retrieval in legal, medical, and scientific domains. The LRA Retrieval task (T = 4,000 per document pair, 76.15% accuracy) and Text task (T = 4,000, 65.38% accuracy) demonstrate the Hrrformer's effectiveness on byte/character-level document processing. Real-world document classification — legal document categorization, medical record analysis, scientific literature screening — routinely involves documents with 10K–100K tokens. These tasks are typically encoder-only (classification, retrieval, or representation learning), avoiding the autoregressive decoding limitation. A deployment scenario: a legal tech company needs to classify 50,000-word contracts (T ≈ 100,000 tokens at byte level) into liability categories. Using a standard Transformer is infeasible (OOM at T = 8,192 even with batch size 1, as the EMBER results show); using a sparse attention method like Longformer or BigBird may work but with uncertain accuracy. The Hrrformer provides a drop-in replacement — same training pipeline, same optimizer, same architecture except the attention block — that handles the full document length with 10× faster convergence (20 vs. 200 epochs) and substantially lower memory, making it feasible to train on a single GPU rather than a cluster. The reduced overfitting (6.83% train-test gap on Image, Table 2) is particularly valuable in legal and medical domains where labeled data is scarce and generalization to unseen document types is critical.

Real-time anomaly detection in high-frequency time series. While not directly evaluated in the paper, the Hrrformer's inference speed characteristics (Table 7: 785.67 examples/second for single-layer, 5× faster at batch size 2 than Transformer at batch size 32) make it suitable for streaming applications where latency constraints are tight. Consider industrial sensor monitoring with 1,000 sensors sampled at 1kHz — a sequence of T = 10,000 readings per second requiring real-time anomaly classification. The Hrrformer's linear scaling means processing this sequence takes O(10,000 × H log H) per forward pass rather than O(100,000,000 × H) for standard attention. With H = 256, this is approximately a 40× reduction in per-inference FLOPs. The single-layer effectiveness is critical here — shallow networks have lower latency, and the Hrrformer's competitive single-layer accuracy (59.97% LRA average vs. 60.83% multi-layer) means minimal accuracy sacrifice for the latency improvement. The concrete deployment scenario: deploy a single-layer Hrrformer on edge hardware (Jetson, FPGA with FFT acceleration) to process high-frequency sensor streams, with the memory efficiency (663.88 MB, Table 4) fitting within edge device constraints. The paper doesn't evaluate time series data, so this application would require validation on appropriate benchmarks (e.g., UEA Time Series Classification), but the architectural properties — linear scaling, fast inference at small batch sizes, single-layer effectiveness — align well with the requirements.