RACE Attention: A Strictly Linear-Time Attention for Long-Sequence Training
Authors: Sahil Joshi
Agniva Chowdhury
Amar Kanakamedala
Ekam Singh
Evan Tu
Anshumali Shrivastava
Venue: ICLR 2026 Poster (2026)
Keywords: Sketching
Locality Sensitive Hashing
RACE
Attention
Linear
Transformers
Primary area: foundation or frontier models, including LLMs
TL;DR: We introduce an efficient attention mechanism based on a differentiable LSH sketch, designed for long-sequence training.

Abstract: Softmax Attention has a quadratic time complexity in sequence length, which becomes prohibitive to run at long contexts, even with highly optimized GPU kernels. For example, FlashAttention-2/3 (exact, GPU-optimized implementations of Softmax Attention) cannot complete a single forward–backward pass of a single attention layer once the context exceeds $\sim 4$ million tokens on an NVIDIA GH200 (96 GB). We introduce **R**epeated **A**rrays-of-**C**ount **E**stimators (RACE) Attention, a kernel-inspired alternative to Softmax Attention that is strictly linear in sequence length and embedding size. RACE Attention replaces the exponential kernel with a sharpened angular similarity, and approximates attention outputs via Gaussian random projections and \emph{soft} Locality-Sensitive Hashing (LSH), avoiding construction of the full attention matrix. Across language modeling, masked language modeling, and text/image classification, RACE Attention matches or outperforms strong baselines up to $64$K seqeuence length while reducing wall-clock time and memory usage. In addition, we conduct a controlled scaling study on a single attention layer and demonstrate processing of up to 12 million tokens on an NVIDIA GH200 GPU and 75 million tokens on an Intel Xeon® Gold 5220R CPU in a single forward–backward pass, which is well beyond the capabilities of current state-of-the-art attention implementations. RACE Attention thus offers a practical and theoretically grounded mechanism for long-context training on today’s hardware.

Published as a conference paper at ICLR 2026
RACE ATTENTION: A STRICTLY LINEAR-TIME ATTENTION FOR LONG-SEQUENCE TRAINING
Sahil Joshi
Agniva Chowdhury
Amar Kanakamedala
Ekam Singh
Evan Tu
Anshumali Shrivastava
Department of Computer Science
Rice University
Houston, TX 77005, USA {s {s ac508 ask20, es100, et62, as143 edu
ABSTRACT
Softmax Attention has a quadratic time complexity in sequence length, which becomes prohibitive to run at long contexts, even with highly optimized GPU ker- nels. For example, FlashAttention-2233 (exact, GPU-optimized implementations of Softmax Attention) cannot complete single forward backward pass of sin- gle attention layer once the context exceeds ~ 4 million tokens on an NVIDIA GH200 (96 GB). We introduce Repeated Arrays-of-Count Estimators (RACE) Attention, a kernel-inspired alternative to Softmax Attention that is strictly lin- ear sequence length and embedding size. RACE Attention replaces the ex- ponential kernel with a sharpened angular similarity, and approximates atten- tion outputs via Gaussian random projections and soft Locality-Sensitivv Hash- ing (LSH), avoiding construction of the full attention matrix. Across language modeling, masked language modeling, and text/image classification, RACE At- tention matches outperforms strong baselines up to 64K sequence length while reducing wall-clock time and memory usage. addition, we conduct a con- trolled scaling study
single attention layer and demonstrate processing of up to 12 million tokens on an NVIDIA GH200 GPU and 75 million tokens on pass, which
Intel Xeon Gold 5220R CPU in single is well beyond the capabilities of current state-of-the-art attention implementa- tions. RACE Attention thus offers a practical and theoretically grounded mech- anism for long-context training on today's 's hardware. We release our code at https:: /tte:///gtttbb/.t com/ http//aahiijohhhhoo Att.aaassttt/cccAAttte.t...
INTRODUCTION
The Transformer (Vaswani et al., 2017; Dehghani al., 2019) is the backbone of modern sequence modeling across language, vision (Parmar et al., 2018), and speech (Luo et al., 2020). We have seen remarkable improvements over the past few years in reasoning and understanding capabilities. Most of these are attributed to the increased parameters of the transformers along with the capability to process longer context windows than before. All this progress, however, expensive primitive: Softmax Attention, whose time scales quadratically with context length. As models and contexts grow, spanning multi-document reasoning. long-form code, audio, and video, the quadratic barrier increasingly dictates who can train and deploy capable systems. Industrial labs mitigate the cost with large-scale distributed hardware; most practitioners cannot. There is growing need for attention mechanisms that are accurate, fast, and memory-efficint. To highlight the limits of Softmax Attention: even with FlashAutention-225 (Dao, 2024; Shah et al., 2024), the state-of-the-art GPU implementations, single nawaad-bbccwaadd pass of single attention layer (1 batch, heads, 128 embedding size) remains computationally and memory intensive and cannot process sequences beyond 4 million tokens achieve an outrageously long context where the target context size is hundreds of millions of tokens beyond, fundamental rethinking of attention (Bahdanau al., 2014) will be required.
a computationally
NVIDIA GH200 (96 GB) GPU. Clearly, to

---

Published as a conference paper at ICLR 2026
47
01
Qh
41
kg
R
K5
R4
04
05
boah
09
kg
Konh
kp
query 45
3 (dra(Ps +11)) - degeey + daxi Mar) Phis dhis th + dayi Ua)
where a, softmax(gghk)
where probability that gi hashes hash table bucket
Softmax Attention
RACE Attention
Figure I: This figure demonstrates the difference between the linear complexity of RACE Attention and the quadratic complexity Softmax Attention. Specifically, we highlight how the final repre- sentation is computed under Softmax versus RACE. In Softmax, the entire fifth column of the attention score matrix is required. In contrast, RACE does not require the full matrix; instead, aggregates statistics within LSH-mapped buckets, utilizing the appropriate collision probability o to compute 05-
Linearized and Low-Rank Approximations to Quadratic Attention: Due the significance of the problem, very large body of work attempts to accelerate attention by approximating softmax with linear approximations (Zeng et al., 2021) or clever kernel feature maps (Katharopoulos et al., 2020; Choromanski et al., 2021; Peng et al., 2021; Qin et al., 2022). A work more closely lated to ours is YOSO Attention (Zeng et al., 2021), which also approximates a powered angular kernel using hard LSH. Despite this same kernel formulation, the underlying estimators differ sub- stantially. RACE Attention leverages a smooth, differentiable relaxation classical RACE-based hashing (Coleman & Shrivastava, 2020) approximate the powered angular kernel. More impor- tantly, YOSO lacks formal theoretical guarantees on its approximation quality and a mechanism that enables causal language modeling. RACE addresses both of these limitations: Sections 3.2 and 3.3 develop a theoretically grounded estimator with quantifiable approximation error, and Al- gorithm presents a practical attention mechanism that naturally supports causal settings. We defer an in depth comparison between RACE and YOSO to Section 3.1. Two notable lines of work in the direction of linearly approximating attention are Linear Attention (Katharopoulos et al., 2020) and Performer (Choromanski al., 2021). Linear Attention replaces the softmax similarity with simple positive kernel via a feature map, e.g. ((x) = elu(x) + This lets the attention be re- ordered into associative sums, achieving linear computation. Although such kernel trick reduces computational complexity, it often degrades accuracy, as clearly demonstrated by our experiments in Section 4. Performer takes different approach and cleverly leverages the classical idea of ap- proximating the exponential of an inner product using Random Fourier Features (Rahimi & Recht, 2007). However, this strategy comes with its own drawbacks. In particular, the method incurs time complexity that is quadratic in the embedding size, which offsets many of the intended compu- tational savings. Furthermore, is well established that approximations based Random Fourier Features require high-diman diggn-iinnsionnl representations to achieve satisfactory accuracy (Backurs et al., 2017). Our experimental results in fig. reinforce this limitation by showing that these methods exhibit poor scalability in practice.
Another category of work replaces the full N N attention matrix with a low-rank surrogate. Some methods learn length-wise projections for keys/values (e.g., Linformer), while others use Nyström landmarks to approximate Softmax Attention matrix with a rank-k decomposition (e.g., Nyströmformer). These approaches reduce the leading cost from O(N2d) to O(Nkd), at the cost of choosing (and occasionally increasing) to maintain accuracy (Wang et al., 2020; Xiong et al., 2021). Moreover, these methods provide support for autoregressive tasks. As shown in Section 4, our method outperforms Linformer in accuracy despite Linformer having 13% more parameters than the other methods. Beyond the empirical shortcomings, deeper conceptual issue persists: existing
2

---

Published as a conference paper at ICLR 2026
approximation approaches lack a rigorous mathematical framework characterize the trade-off's be- tween efficiency and accuracy. For example, while Performer provides strong approx-appoonnnaaiion guarantees, general framework connecting efficiency knobs (e.g., feature count m) to downstream accuracy remains limited, and strong accuracy frequently entails large m in practice. As a result, design decisions often appear ad hoc and fragile, leaving methods vulnerable to instability between tasks and settings. Taken together, these limitations explain why, despite the abundance of approxi- mations, Softmax Attention continues to remain the most widely adopted and reliable formulation.
Sparsity is Complementary: We note that there is also a popular line of work (Beltagy et al., 2020: Zaheer et al., 2020: Kitaev al., 2020; Han et al., 2024; Petrick al., 2022) that exploits structural information in natural language, with sparsity in attention being among the most widely studied. These approaches are complementary to our proposal, which focus on making the attention mechanism itself more efficient and mathematically grounded. In principle, our method can be inte- grated with structural priors such as sparsity to further improve scalability and accuracy. However, since our objective in this paper is to develop fundamentally efficient attention, we will not discuss this line of structural approaches further, instead we view combining them with our method as an important direction for future work.
Key Idea: Standard attention relies on the well-known softmax function, computing
0 = =softmax
QK
V.
where the softmax is applicd row-wise so that attention weights are nonnegative and sum to one. In this paper, leverage alternative to the softmax -amely, higher-degree monomial of an angular kernel based on cosine geometry:
0 0- /cos 1QQ (1-(00-(Q0))
V
π
Eq. 2 should be read as an informal analogue to Eq. I, where the angular kernel replaces the expo- nential. A more precise definition, with explicit cosine normalization and row-wise normalization, is given in Section 3.1. We argue that, for sufficiently large values of y, this formulation closely mimics the behavior of softmax and refer to it as Angular Attention in the subsequent sections. Importantly, it admits linear-time approximation algorithm. In particular, we leverage the connec- tion (Section 2.2) between Repeated Prrays-of-Coum Estimators (RACE) (Coleman & Shrivastava, 2020: Luo & Shrivastava, 2018) and the angular kernel to design our algorithm in Section 3.2. We therefore refer to our proposed method as RACE Attention.
RACE Attention is drop-in replacement for Softmax Attention. We evaluate it in Transformers on causal language modeling, masked language modeling, and text/image classification (Section 4 and Appendix A.2). By reframing similarity around powered angular kernel and using differentiable LSH-based sketches, it provides principled alternative that supports very long contexts on com- modity hardware. The sketching view keeps constant factors small: each query mixes with only a fixed bank of S = IR bucket summaries rather than all N keys. Since we never materialize the full attention matrix, the working set stays compact and activation memory drops, cnabling much longer sequences with reduced latency. In contrast, FlashAttention-225 (Dao, 2024; Shah et al., 2024) reduce the memory footprint of attention via tiling, but still require computing all key-query interactions, preventing processing of much longer sequences comparable speed, as shown in fig. 4. In addition to our novel findings about RACE Attention and rigorous supporting experimental evidence, we provide the following:
I. Long-context scaling: RACE scales to sequence lengths far beyond prior attention mechanisms, processing up to 75M tokens on CPU and 12M tokens on GPU in single howward-bcckward pass of single attention layer, using the same hyperparameters as in our accuracy evaluations. II. Trainable RACE: We introduce a differentiable sketch by replacing hard hashing with smooth soft assignments over hypercube corners, enabling end-to-end training.
III. CPU/GPU pre-training: Our approach supports both causal (autoregressive) and non-causal (bidirectional) pre-training on CPU and GPU, with custom OpenMP/CUDA kernels that compute causal prefix operations in a single streaming pass for linear-time, memory-efficiene training. IV. Theoretical Insights: Section 3.3 establishes approximation guarantees based on the LSH framework and analyzes how the parameters L (number of hash tables) and R (buckets per table) govern the variance- parianceaacuuray tradeoff.
3

---

Published as a conference paper at ICLR 2026
2 BACKGROUND
2.1 LOCALITY-SENSITIVE HASHING (LSH)
An LSH family H. for a similarity Sim makes near pairs collide more often than far pairs. Formally, H is (So, cSu, P1, P2) -eessitiee if for all y R.P
Sim(r, v) 2 So Pra-Heh(a h(w)] 2 Pl:
Sim(x, S cSp = Pra~H = hly] S P2.
where p1 P2 and < Such families enable sublinear-time approximate nearest-neighhor data structures. A convenient sufficient condition, satisfied by SimHash and WTA (Charikar, 2002; Yag- nik et al., 2011; Chen Shrivastava, 2018), is that the collision probability monotone function of similarity, Pra~n(h(z>) h(v)] (a)mm(z, with f' increasing.
2.2 RACE SKETCH
Coleman et al., 2020) shows that any similarity expressible as a nion-negative) linear combination of LSH collision kernels can be sketched using ACE-style estimation (Luo & Shrivastava, 2018). It provides unbiased estimator of kernel-density sums for LSH collision kernels and their powers. In particular, RACE estimates EBED k(x, q) by hashing items into counters and reading the counters addressed by the query; averaging across L independent rows reduces variance.
RACE (Coleman & Shrivastava, 2020;
Lemma 1 (Theorem 1 of (Coleman & Shrivastava, 2020)), Given a dataset D, an LSH family H with finite range [1, R] and parameter p. construct an LSH function h(x) + [1, RP] by concate- nating independent hashes from H. Let A be an ACE array constructed using h(x). Then for any query q.
[[([((g)]]]
Σ Ek(z,g) k(x,9))
RED
INTRODUCING RACE ATTENTION
Algorithm RACE Attention (non-causal)
Input: Q,K, E R Nxx,, number of hash tables L; number of hyperplanes P; temperature 3 > 0.
Output: Ô E Nxd
1: for L 1 do
Draw W(O) Pxd with rows w Lid (O.
2:
3: Define the corner set V= {+1]" (R 2P) with U, E {+1)P.
4: Build (6)
( NxR with rows
exp (tanh ( ((0x))(()))) Trp}
[o)) Σ, exp(3 (tanh( (W(())))))))) Tupe x Kz)
5: Per-table bucket statisties: 0 T
B(O) = VER))
6: end for
7: Compute average across tables: Num
J, H "00 B and Den + 110 A(9)
8: Return Ô diag(Den)-1 Num
3.1 SOFTMAX-LIKE SIMILARITIES THAT ADMIT LINEAR- TIME ESTIMATION
Given a sequence of N tokens, a Transformer produces for each position a query
Q: E Rdd and for every position j key K, E Rd and value V, E Rd.
4

---

Published as a conference paper at ICLR 2026
Softmax
Angular
[]
cos -os- (OK M/))
cos [OK
(1
cos-
[OK"
10
(1 -os
[OK Mn
softmax(OK (vd)
90
coo
0.00
40
sist
Ques
20
0/0
0.23
20
21350
0000
9 20
20
Key index
Key Index
7
6
= 10
7 12
Figure 3: Comparison of Softmax and Angular kernels at different sharpening levels y. As (non- linearity) increases, Angular transitions from flat similarity scores to a sharper distribution, recover- ing behavior similar to the exponential in Softmax.
The output at position is a weighted sum of the values, where the weight Vj reflects the relevance of token j to token i. In the standard formulation (Vaswani et al.,
||Angular Softmax||
300
250
2017), relevance is computed via the scaled dot product given by Eq. 1. This choice guarantees two useful prop- erties of the attention weights: (i) non-negativity and (ii) they sum to one, so O₂ is a convex combination of the values. Equally important, the exponential introduces strong non-linear mapping from similarity scores to atten- tion weights, amplifying small score differences. This ob- servation suggests broader view: attention weights can be derived from any normalized highly non-linear (expo- nential like) similarity function. Let sim Id Rd R20 be any non-negato neg-nieee similarity function. We can de- fine normalized similarity attention as
200
150
100
50
1
7
10
13 16
Sharpening paremeter y
Figure 2: Frobenius error between An-
gular and Softmax Attention 7.
O, Σ (im(Qi,Ae K,) V,
Σz=1 sim Kj)
Our quest is for finding non-linear (softmax-like) similarity kernels that admit accurate linear-time estimation, eliminating the quadratic cost of attention in both training and inference. Similar to YOSO (Zeng al., 2021), argue that good starting point is well known LSHable (Coleman & Shrivastava, 2020; Choromanski et al., 2017) angular similarity. It is well behaved and normalized, in particular, it depends only the angle between the vectors Q, and Kj and is invariant their
[Q.]ıKK /TT However, unlike exponential in softmax, the raw angular kernel is relatively flat near high similarity values, reducing its ability to sharply discriminate between nearly aligned vectors. To increase contrast, we propose to exponentiate the angular kernel with a sharpening parameter which accentuates differences among highly similar pairs. After sharpening the kernel, the similarity function becomes follows:
norms: sim (Q:, Ky) 1 cos- Q.K, 1
sim Qi, K2) (1 cas
Q (1Q.1I ( (
(
O,K,K K2
/
(4)
In fig. 3, we show that for sufficiently large y, the angular kernel becomes almost indistinguishable from softmax kernel. This is expected because higher degree monomial like 12 behaves similarly to an exponential. Furthermore, fig. we plot the frobenius error between Angular and Softmax Attention. The eиror sharply decreases can be achieved with modest polynomial degree (e.g., 7 8).
increases, demonstrating that softmax-level sharpness
In its current form, evaluating the attention with similarity given by Eq. 4 is no different from soft- max. It naively still requires all 2 query-key interactions. Fortunately, any constant exponentiation of angular kernel, belongs to family, that admits efficient kernel density estimation using RACE sketches (Coleman & Shrivastava, 2020), and we use these sketches to approximate the kernel in linear time obtaining algorithmically efficient alternative to Softmax Attention!
5

---

Published as a conference paper at ICLR 2026
Finally, outlined in Section 1, YOSO (Zeng al., 2021) and our method operate on the same kernel in Eq. 4, but differ fundamentally in how attention is computed. YOSO employs hard LSH to generate Bernoulli collision indicators, yielding an unbiased estimator of the unnormalized attention numerator Σ (2, K in Eq. 3. then applies post-hoc & normalization, which does not correspond standard attention normalization. Since this hard formulation is non-differentiable, YOSO relies on surrogate lower-bound gradients derived from additional Bernoulli samples rather than directly differentiating the kernll. This introduces quadratic complexity in the embedding dimension d, resulting in poor scalability during end-to-ens training (see fig. 5c). To see how RACE constructs a smooth, differentiable LSH-based estimator that linear in in contrast to YOSO, refer to Section 3.2.
N
3.2 THE FINAL ALGORITHM
At a high level, RACE avoids explicitly approximating the NxN attention matrix, which would otherwise remain quadratic. Instead, RACE sketches the sufficient statistics needed to compute attention outputs directly in linear time. Fig. 1 illustrates this difference using os. the output em- bedding of token 5. In Softmax Attention, computing 05 requires the full attention column, whereas RACE softly assigns queries and keys (Qs and Ks) into R LSH-indexed bucket summaries under the same LSH scheme. The values weighted by the key probabilities and then combined with the query probabilities. Averaging over L independent hash tables further reduces variance, following standard sketching practice. Comprehensive visualizations are provided in Appendix (figs. 7, 8).
We next formalize the RACE Attention mechanism in Algorithm 1. As described in Section 2.2, one final technical hurdle remains: the RACE algorithm non-differentiable. We get around the non-differentiability of RACE sketches by replacing discrete bucket assignments with soft proba- bilities and using standard cross-entropy loss. preserving differentiability for end-to-end training. Algorithm 1 consists of three key stages: (i) Soft bucketization: Each query/key E R is ran- domly projected via ((O) hyperplanes and softly assigned to R = 2 corners with distribution (x)(2) (z) (steps 2-4). (ii) Bucket aggregation: For each table L, we form per-bucket statistics by accumulating key weights and their weighted values, namely the mass vector A E I² and the value-sum matrix B(d) E Ritxd, so that A [r] is the total (soft) mass in bucket r and [r,] is the corresponding sum of values. (step 5), (iii) Global normalization: The algorithm averages across L tables to form Num = 1, E. (1) B(8) and Den = 1, Ee $ A(0), and reconstructs the final outputs as Ô diag(Den) Num (steps 7-8).
Q
A useful way to interpret Algorithm is through the kernel perspective introduced in Section 2.2. In classical RACE (Coleman & Shrivastava, 2020), P random hyperplanes generate hash h(x)= (ign(W(0)))). 2r) and two vectors collide under this hash with probability Pr(M(Q;) sim(Q: K2), which is exactly the P-powered angular kernel in Eq. 4 with = P. In soft RACE, we keep this geometric structure intact, but replace the hard sign map with a smooth approxima- tion: we compute a "soft" sign vector tanh(W(())) and evaluate its alignment with each of the R = 22" corner sign patterns U, E {+1] assigning x to buckets with nonzero probability via a softmax over these alignments. This turns the discrete collision event of classical RACE into a dif- ferentiable quantity while preserving its underlying angular dependence. In particular, vectors with small angular distance still assign most of their mass to the same buckets, mirroring the behavior of the P'ppowered angular kernel. As a result, the per-table quantity ((.) T (x(()) (KG) serves as a smooth approximation to the P-powered angular similarity that our attention mechanism seeks to approximate. We formalize these kernel quantities in the Section 3.3, where the RACE-based approximation S.y is introduced.
((KK)] = Siy ==
Computational Complexity: The per-table runtime of Algorithm 1 can be decomposed according to its main steps: Step 2 (random projections) costs (NN Step 3 (logits over It = 2" corners) costs O(N P PR), and Step 5 (bucket aggregation) costs ONN)) The global accumulation in Step 7 adds ON Rd) per table. Thus, the tar-table runtime is ONN + NPR + N Rd) = R())d), with memory ONN R + Rd). Across L tables, this becomes O(LNRd) time and O(L Rd) space. Compared to FlashAttention-2233
(N2dd) time and O(N)) space, RACE is more efficient since R, I. < N and R, I. < d, even for moderate N and d.

---

Published as a conference paper at ICLR 2026
3.3 THEORETICAL ANALYSIS OF ALGORITHM
Algorithm is presented in terms of random projections, soft bucketization, and per-bucket aggre- gation. For analysis it is easier take kernel approximation view of attention. Each hash table L -..... L induces randomized feature map の( R R" where R. 2 is the number of hypercube corners, and defines the approximate kernel S = (Q((() T ((0) (K))) Then, averag- kj
ing across independent tables yields 3 = - Σ S(t), This view places soft RACE Attention in the language of kernel methods: it replaces the angular kernel (7 P) in Eq. 4 with the random- ized sketch $ based on LSH-sttle features. Since (xx) is softmax distribution, the approximate kernel S inherits concentration properties from the underlying random Gaussian projections. This allows us to analyze its deviation from the target angular kernel using standard tools from random- ized numerical linear algebra (RandNLA) (Tropp. 2015). Our analysis requires the following two mild assumptions
the target kernel S:
(A1) Row sums of are bounded away from zero i.e, Smin := min; (S1), 2 C for some con- stant C1 > 0, which ensures stable normalization in attention.
(A2) Spectral norm of S is bounded i.e., ||S||2 I C2N, which follows from Sij E [o, 1].
Several comments necessary to better understand the above structural conditions. Condition (A1) rules out degenerate cases where a query has vanishing similarity with all keys, which would make the row-normalization in attention unstable. In practice this assumption is mild: with learned representations, attention rows rarely collapse to near-zero mass, so requiring Smin 2 CNN simply rules out degenerate cases where a query is effectively isolated (assigns negligible weight almost all keys). Condition (A2) is even less restrictive: since Sij E [o, 1], the worst case is attained by the all-ones matrix JN. whose spectral norm is exactly |J ll2 = N. Thus bounding ||S||2 S C2N merely rules out pathological growth beyond this trivial maximum, and is always satisfied with result:
C2= == 1. We are now ready to state our main
Theorem 2. Let Q, K, V Nx be the query, key, and value matrices. For parameters L, P. and
B, and under conditions (Al) and (A2), the estimator Ô produced by Algorithm I satisfies
10 Olrmm -0(5
(og(N/5)
log N/8) L
|IVIE
with probability at least Here, O E Nxd with the 8th now O₂ is defined using Eqs. equation and equation 4 with 7 = P. and 11õ Ollmms == V EN 11Ō - -O,13 denotes per-token root- mean-square (RMS) error between O and Ô.
The bound decomposes into a bias term O(P/3) and variance term O (o/g(//))/L) Larger B reduces the bias, while increasing L reduces the variance. The dependence on P arises because pow- ering the angular kernel by P makes collisions sharper, but soft bucketization (finite 3) smooths out these decisions and introduces an additional bias. To keep this bias small, should be scaled with P. In particular, as B, L, + oc, the approximation error vanishes. In fact, taking L = O(log N) prevents the variance from exploding. Together, this kernel reinterpretation provides a precise RandNLA lens for analyzing RACE Attention, with L, P. and 3 jointly governing its accuracy- -fficiccyyffcccnnyy trade-offs. The proof of Theorem 2, together with all intermediate lemmas, is deferred to Appendix B due to space constraints.
Remark (Causal masking): Our language modeling experiments (Tables 4 and 8) use causal RACE Attention, implemented efficiently in OpenMP/CUDA (Algorithm 2). Our theory, however, covers only the non-causal setting. Extending Theorem 2's bias-variance guarantees to the causal case re- mains an open problem, since the cumulative-sum constraint interacts non-trivially with the random- feature construction. A rigorous causal analysis is a key direction for future work.
4 EXPERIMENTS
To ensure comparability and avoid cherrypicking, we adopt the standard evaluation suites used in prior efficient-attention work-Lined Attention, Linformer, and Random Feature Attention (RFA) (Katharopoulos et al., 2020; Wang et al., 2020; Peng et al., 2021). We evaluate text clas- sification QNLI, SST-2, IMDB, Yahoo, and Arxiv (Rajpurkar al., 2016; Socher et al., 2013;
7

---

Published as a conference paper at ICLR 2026
Long-context classification performance on 40GB A100 GPU. Train/Test denote per- epoch runtimes in seconds, and Acc. denotes accuracy.
Table 1:
Arxiv Long- Document Classification
16K
32K
64K
Method
Train +
Test +
Acc. 1
Train
Test :
Acc.
Train !
Test
Acc. 1
RACE (P=2,I=2)
80.5s
3.9s
70.3%
282s
15s
89.4%
561s
22s
97.14%
RACE (P=3.L=3)
82.4s
4.0s
71.3%
289s
15.6s
90.6%
584s
22.5s
97.92%
RACE LP=4.L=4)
84.7s
4.1s
70.8%
300s
91.1%
594s
22.9s
97.4%
Linear
83.8s
4.0s
67.9%
286s
15.9s
87.3%
591s
22.8s
96.35%
Linformer- 128
86s
3.2s
64.1%
296s
10.7s
87.5%
616s
15.2s
97 97.4%
Performer-256
128s
5.8s
68.9%
449s
24.6s
86.5%
952s
35s
96.61% %%
FlashAttention2
95.7s
3.7s
69.8%
471s
20s
89.7%
1645s
47s
97%
Table 2: Comparison of attention methods across diverse tasks.
Table 3: Food-101 @ 16K (Image Classification)
Method
CIFAR-10 @ 111224
QNLI 22048
Tiny Stories @ @1024
Method
Train +
Test 4
Acc. f
(%))
(%)
PPL.
RACE (P=2, L=2)
891s
37s
42.4%
RACE L-22
63.7
60.7
4.2
RACE (P=3, L-3)
62.5
60.7
3.2
RACE (P=3, L=3)
950s
40s
43,5%
RACE (Pe4, L=4)
61.1
RACE (P=4, L=4)
1042s
40.3%
Linformee- 128
63.7
60.6
3.7
Linear
I 1166s
44s
41.4%
FllstAlict
61.44
61.1
Linformer-122 128
1250s
49s
20.2%
Angular ()-8)
Performer-256
2546s
105s
42.4%
Performer-256
64.9
61.0
10.0
Sigmoid
57.2
61.1
FlashAttention2
2600s
95s
42.1%
Maas et al., 2011: Zhang al., 2015; He et al., 2019); autoregressive language modeling WikiText-103 and PTB (Merity et al., 2017: Marcus et al., 1993); masked language modeling on Tiny Stories (Eldan & Li, 2023); image classification 101 using ViT architecture (Krizhevsky, 2009; Xiao et al., 2017; Bossard et al., 2014; Dosovitskiy al., 2021); and long-context reasoning on Long Range Arena tasks (e.g., ListOps and Text Re- trieval) (Tay et al., 2021). Together, these benchmarks span bidirectional and autoregressive model- ing, well moderate- and long-context text and image classification. During training, we treat 3, introduced in Algorithm 1, as trainable parameter.
CIFAR-10, FashionMNIST, and Food-
Beyond standard benchmarks, we conduct extreme-lengte length scaling experiments on a single attention layer, reaching sequences of tens of millions of tokens while using the same hyperparameters as in the accuracy evaluations. Finally, FlashAttention are exact fused implementations of Softmax Attention, and we use the terms interchangeably when reporting accuracy and runtime.
Baselines: We compare RACE against widely used baselines with publicly available implementa- tions: FlashAttention2 (Dao et al., 2022), Linear Attention (Katharopoulos et al., 2020), Performer (Choromanski et al., 2021), Linformer (Wang et al., 2020), Sigmoid Attention (Ramapuram al., 2025), and YOSO (Zeng al., 2021). These span exact, kernel-linear, and low-rank approximations. All models are tuned per authors' guidelines and trained under identical settings.
Is RACE Attention Accurate as Transformers? We report text-classification. image- classification, and masked language modeling results in Tables 1, 2, and 3. Specifically, in Ta- ble 3, "Train/Test" denote per-epoch runtimes in seconds, and "Acc." denotes accuracy. Results for Linear Attention, Linformer, and Performer were collected using batch size I due to out-of- memory failures batch size 8. In contrast, both RACE and FlashAttention2 remain memory- efficient at this sequence length and are evaluated with batch size 8. Additional experiments can be found Appendix, refer Tables 6, 7, and 10. For autoregressive language modeling. RACE matches softmax-level perplexity on WikiText- 103 and improves upon it on PTB (Tables and 8). These results indicate that RACE preserves accuracy in the overlapping regime while deliv- ering consistent gains on moderate- and long-con context settings. Unless stated otherwise, all methods use the same Transformer backbone (layers, heads, embedding size, dropout) and training budget.
8

---

Published as a conference paper at ICLR 2026
0.30
0.30
0.25
0.20
0.15
0.15
0.10
Alterbinn
0.10
Alterton
MACE
RKF
0.05
0.00
130K
2M
12M
130K
2M
4M
10M
Sequence Length
Sequence Length
(a) GPU: RACE (P 2,
(b) GPU: RACE (P 3, 3)
100
FACE
Factttection
8
0.20
(st
Signsl
0.15
Perlarras
0.10
0.05
Jafbrrr
0.01
0.00
130K
2M
4M
7M
130K
2M
4M
12M
Sequence Length
Sequence Langth
(c) GPU: RACE (P= 4,
(d) GPU scaling
100
flesh-ttention2-c GPU
Flechmmenionn
CPU-RACE
Time (s)
1000.00
RACE
Liner
Linterer
Time (S)
Sigmoid GPU
Pafformia
100.00
0.2
10.00
1.00
2.05K
131.07K
4,19M
75M
130K
1M Sequence Length
32M 75M
Sequence Length
(e) CPU-RACE vs. GPU-Baselines
(I) CPU scaling
Figure 4: Scaling stress-tests on GPU and CPU: All plots use logarithmic axes and report a single
pass (batch size 1, 4 attention heads, d=128) of single attention layer. Lin- former and Performer use the same hyperparameters as in Table 2. (a-d) compare the scaling behav- ior of RACE against attention basclines on GPU, while (c-f) show scaling for RACE (P=3, L-3) on CPU, highlighting its superior efficiency at long sequence lengths.
We train with identical optimizers, schedulers, and batch sizes; full hyperparameters appear in Table 5. Metrics are reported from the best-validation checkpoint. All accuracy experiments conducted on single NVIDIA A GPU.
Table 4: WikiText-100 1024
Method
PPI. 4
RACE (P=2, L=2)
23.9
RACE (P=2, L=3)
23.4
Can we reach 100 million context window on popular hard- ware? Now, we evaluate how RACE Attention scales across common hardware relative strong baselines. For RACE, use sketch parameters (P, L) chosen to match FlashAttention2's ac- curacy/perplexity on the same tasks in Table For each method, we measure the wall-clock time for single pass of single attention layer with batch, 4 heads, and em- bedding size 128, function of sequence length, stress-testing
RACE (P=3, L=3)
21.9
RACE (P=3, L=4)
21.5
RACE (P=4, L=4)
20.9
FlashAttention2
20.9
Angular (y=8)
19.0
context lengths up to 100 million tokens. Since FlashAttention 2/3 are designed specifically for GPU hardware, use PyTorch's optimized F. sca eed.dddd wed.do._ppp..eoeeoodod.eoee www.doo.orruuuttttt.eeepopooood. wec.uu.atteetiii.. implementation as the FlashAttention baseline when reporting CPU scaling results.
How far sequences of up to 75 million tokens for single on CPU. By contrast, FlashAttentian becomes prohibitively slow ~ 2 million tokens due to the
scale attention standard Intel Xeon@ Gold 5220R CPU? RACE scales to pass of a single attention layer

---

Published as a conference paper at ICLR 2026
5000
FashMMtention--G
40
feeshitteetinn22 GPU
RACE YC5O 16
4000
FischAttantion--Gr
FlashAttention3.44 GPU
Soeedup
3000
Sigmoid GPU
Sigmald GPU
Time (5)
2000
0.01
1000
10
0.001
128k 512k 1M Sequence Length
32k 120k 512k
2M
Sequence Lengon
Sequence Length
(a) GPU-RACE Speedup
(b) CPU-RACE Speedup
YOSO vs. RACE on GPU
Figure 5: Speedup of RACE relative to GPU-only attention baselines, with RACE executed on
GPU in (a) and on CPU in (b). (c) YOSO (CUDA kernel) fails beyond 32K tokens due memory constraints, whereas RACE continues to scale to much longer sequences.
quadratic time scaling in sequence length N (see fig. 4f). is worth noting that FlashAttention does not run out of memory on the CPU DRAM. RACE is more than 10000 faster than FlashAtten- tion at context length of ~ 33 million. RACE finishes comfortably under 10 seconds for a single forward- baakwddd pass on this hardware while FlashAttention takes approximately 10yh seconds on the same hardware. Although the absolute runtime grows with N, RACE's speedup over FlashAt- tention increases. At 75 million tokens, RACE finishes in about 100 seconds. This is expected because RACE is linear and FlashAttention is quadratic in N. The experiments also highlight that linear attentions' approximations are not only inaccurate but also significantly slower and have large memory overheads due to large hidden constants (see fig. 6 in Appendix). They run about an order of magnitude slower than RACE Attention and even go out of memory at ~ 33 million tokens.
How far can we scale attention on the most powerful GH200 GPU? An NVIDIA GH200 has 96GB of memory. Here, we observe a similar trend. RACE scales up to 12 million tokens for single forward-backward pass of single attention layer, whereas FlashAttemmion-2233 and Sig- moid Attention becomes impractical around ~ million tokens (see fig. 4). ~ million tokens RACE takes merely 0.1 seconds to finish, while FlashAttention2 needs about 550 seconds, making RACE about 5500x faster on GPUs for processing 4 million tokens. Additionally, RACE is about 5000x faster than Sigmoid and 2600 faster than FlashAttention3 for processing 4 million tokens (see fig. 5a). FlashAttention removes the quadratic memory cost of attention scores, but exact at- tention still requires storing token-level Q, K. V, and O activations and their gradients, incurring ((BHNd) memory. For large N, this linear footprint alone exceeds GPU HBM capacity. In con- trast, RACE compresses queries and keys into R bucket summaries per table, reducing activation memory to O O(BH BENHIN- + Rd)), which scales more favorably on GPU even than the linear atten- tion baselines that exhaust memory at approximately ~ million tokens (see fig. 4). As a result, RACE supports contexts up to 3.5x longer than FlashAttentionn22233 and Sigmoid Attention.
Right Algorithm beats Hardware Acceleration: While GPUs offer substantial speedups for a fixed algorithm, comparing FlashAttention 2/3 and Sigmoid on high-end GH200 GPU against RACE on a single CPU highlights the impact of algorithmic accelcration. Fig. 4c reports the runtime of single backwar pass of single attention layer as the context length in- creases. For short to moderate sequences (N S. 131K), the GPU's massive parallelism dominates and FlashAAtenntion2223 remain faster. Beyond this scale, however, the asymptotic behavior becomes decisive: the GPU kernels begin to saturate, and RACE becomes faster. At sequence length of 4 million tokens (the largest supported by Stashhttention-2// in our configuration), RACE on CPU is roughly 40x faster than FlashAttention-2 and Sigmoid Attention on GPU, and about 20x faster than FlashAttention-3 (see fig. 5b). These results show that, in the long-context regime, tate-of-theean GPU attention kernels are fundamentally constrained by their quadratic dependence on sequence length. In contrast, RACE's algorithmic efficiency enables to outperform even the most advanced GPU-accelerated methods by wide margin, despite executing on substantially weaker hardware.
5 CONCLUSION
We introduce RACE Attention, a linear-time, memory-efficient alternative to Softmax Attention that approximates a sharpened angular kernel via RACE sketches. This formulation will enable substan- tially more efficient key-value caching during inference and suggests a clear path toward optimized CUDA kernels that preserve favorable scaling behavior and theoretical guarantees in autoregressive settings. We leave full exploration of these directions to future work.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We would like to thank the anonymous reviewers for their helpful comments. We are also grateful Aditya Desai and Zhaozhuo Xu for their valuable insights and thought-provoking discussions. This work was supported by the National Science Foundation (NSF) CCF-2336612 and Rice Ken Kennedy Institute (K21) Generative AI Cluster Funding.
ETHICS STATEMENT
Our work is focused on speeding up algorithm and reducing the memory complexity for Attention. As such, it could have significant broader impacts by allowing practitioners to train models fast and deploy them constrained resource settings. Our experimental work uses publicly available datasets evaluate the performance of our algorithm; ethical considerations raised.
REPRODUCIBILITY STATEMENT
We provide the source code and configuration for the key experiments (Language Modelling, Masked Language Modelling, and Classification) including instructions on how to generate data and train the models. All proofs are stated in the appendix with explanations and underlying assump- tions. We thoroughly checked the implementation and also verified empirically that the proposed algorithm holds.
REFERENCES
Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks. Advances in Neural Information Processing Systems, 2017.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv: 409.0473, 2014.
Iz. Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint wwxiv:2004.001355 2020.
Lukas Bossard, Matthieu Guillaumin, and Lue Van Gool. Food-101 mining discriminative com- ponents with random forests. European Conference on Computer Vision, 2014.
Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the 34th Annual ACM Symposium Theory of Computing, 2002.
Beidi Chen and Anshumali Shrivastava. Densified winner take all (wta) hashing for sparse datasets. In Proceedings of the 34th Conference Uncertainty in Artificial Intelligence (UAI), 2018.
arXiv:1810.00115.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Davis, Afroz Mohiuddin, tukasz Kaiser, David Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
Krzysztof M. Choromanski, Mark Rowland, and Adrian Weller. The unreasonable effectiveness of structured random orthogonal embeddings. In Advances in Neural Information Processing Systems, 2017.
Benjamin Coleman and Anshumali Shrivastava. Sub-linear RACE sketches for approximate kernel density estimation on streaming data. In World Wide Web Conference, 2020.
Benjamin Coleman, Richard Baraniuk, and Anshumali Shrivastava. Sub-linear memory sketches for near neighbor search on streaming data. International Conference on Machine Learning, 2020.
11

---

Published as a conference paper at ICLR 2026
Tri Dao. FlashAttention-2: Faster attention with better parallelism and work partitioning. In Inter- national Conference on Learning Representations, 2024.
Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. FlashAttention: Fast and memory-efficient exact attention with io-awareness. In Advances in Neural Information Process- ing Systems, 2022.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. In International Conference Learning Representations, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x 16 words: Transformers for image recognition scale. In International Conference on Learning Representations, 2021.
Ronen Eldan and Yuanzhi Li. Tinystories: How small can language models be and still speak coherent english? arXiv preprini arXiv:2305.07759, 2023.
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David Woodruff, and Amir Zandieh. Hy- perattention: Long-context context attention in near-linear time. In International Conference on Learning Representations, 2024.
Jun He, Liqun Wang, Liu Liu, Jiao Feng, and Hao Wu. Long document classification from local word glimpses via recurrent attention learning. IEEE Access, 7:40707-40716 2019.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnss: Fast autoregressive transformers with linear attention. In International Conference Ma- chine Learning, 2020.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference Learning Representations, 2020.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Chen Luo and Anshumali Shrivastava. Arrays of (locality-sensitive) count estimators (ace): Anomaly detection the edge. In World Wide Web Conference, 2018.
Haoneng Luo, Shiliang Zhang, Ming Lei, and Lei Xie. Simplified self-attention for transformer- based end-to-end speech recognition. CoRR, abs/2005.1046. 2020.
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Association for Computational Linguis- tics, 2011.
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of english: The penn treebank. Computational Länguistics, 19:313-330, 1993.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In International Conference on Machine Learning, 2018.
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A. Smith, and Lingpeng Kong. Random feature attention. In International Conference Learning Representations, 2021.
Frithjof Petrick, Jan Rosendahl, Christian Herold, and Hermann Ney. Locality sensitive hashing for long context neural machine translation. In International Conference on Spoken Language Translation, 2022.
Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong, cosformer: Rethinking softmax in attention. In International Conference Learning Representations, 2022.
12

---

Published as a conference paper at ICLR 2026
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, 2007.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Empirical Methods Natural Language Processing, 2016.
Jason Ramapuram, Federico Danieli, Eeshan Dhekane, Floris Weers, Dan Busbridge, Pierre Ablin, Tatiana Likhomanenko, Jagrit Digani, Zijin Gu, Amitis Shidani, and Russ Webb. Theory, analysis, and best practices for sigmoid self-attention. International Conference on Learning Represen- tations, 2025.
Jay Shah, Ganesh Bikshandi, Ying Zhang. Vijay Thakkar, Pradeep Ramani, and Tri Dao. Flashattention-3: Fast and accurate attention with asynchrony and low-precision. In Advances in Neural Information Processing Systems, 2024.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang. Christopher D. Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Empirical Methods in Natural Language Processing, 2013.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Scbastian Ruder, and Donald Metzler. Long Range Arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2021.
Joel A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2)11-230, 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, 2017.
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint 201.::20006.47788, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST novel image dataset for bench- marking machine learning algorithms. arXiv preprint crXiv:1708.07744 2017.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and
Vikas Singh. Nyströmformer: nyström- based algorithm for approximating self-attention. In AAAI conference on artificial intelligence, 2021.
Jay Yagnik, Dennis Strelow, David A. Ross, and Ruci-Sung Lin. The power of comparative reason- ing. In 2011 International Conference on Computer Vision, 2011.
Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems, 2020.
Zhanpeng Zeng, Yunyang Xiong. Sathya Ravi, Shailesh Acharya, Glenn M. Fung, and Vikas Singh. You only sample (almost) once: Linear cost self-attention via bernoulli sampling. International Conference on Machine Learning, 2021.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. In Neural Information Processing Systems, 2015.
13

---

Published as a conference paper at ICLR 2026
A APPENDIX
A.1 LLM USAGE
An LLM used exclusively refine the language and improve clarity across the manuscript. It was not used for idea generation, experimental design, analysis, or to produce results.
A.2
ADDITIONAL. NOTES ON EXPERIMENTS
Table 5: Experiment Setup and Hyperparameters
Dataset
Task
Hyperparameters
PTB
Language Modeling
N=128; layers=l; heads=2; d=128; batch=16; Ir=6e (0x9,
0.999); s=le "; wd=0.1; dropout = 0.3; epochs=70
WikiText-103
Language Modeling
N=1024; layers=8; heads=8; d=512; batch=16; Ir=Ge ; (0.9,
0,999); e=le "; wd=0,1; dropout=U.1: 1pppoutt..:cpoccs=1100 epochs=100
1MDB
Text Classification
N=512: layers=1; heads=2; d=128; batch=32: Ir=1e 6; wd=5e
1; epochs=150
Yahoo
Text Classification
N=256; layers=l; hcads=2; d=128: batch=32; Ir=le wd=5e
dropout 0.1; epochs:100
ListOps
Text Classification
N=2000; layers=8; heads=8; d=512; batch= Ir=1e "3; wd=le
dropout=0.1; epochs=10
Text Retrieval
Text Classification
N=8000; layers=4; heads=2; d=384; batch=l; Ir=2e 4 wd=le
dropout=0.1; epochs=20
Tiny Stories
Masked Language Modelling
N=512-1024: layers=6; heads=4; d=384; batch=32; Ir=6e 4:
8's=(0.9, 0,999); <=le wd=0.1; 0: epochs= sto-
rics=20000
QNLI
Text Classification
N=2048; layors=4; heads=3; d=384; hatch=32; Ir=le=;; wd=5e
dropout=0.1; cpppott00 epochs=
SST-2
Text Classification
N=1024: layers=4; heads=8; d=384; batch=32: Ir=1e 9; wd=5e 9;
drupout=0.1;; :pppsut00 epochs=100
CIFAR-10
Image Classification
N=1024; layers=2; heads=4; d=384; batch=32; In=6o (0s9,
0.999); #=le :; wd=0.1; cpochut: epochs=75
FashionMNIST
Image Classification
N=784; layers=2; heads=4; d=384; batch=32; In-6 ('s=
0,999); e=le "; wde0.1; dropout=0.1; epochs=:75
Food-101
Image Classification
N= 16344; layers=8; heads=8; d=512; hatch=8; Ir=3e 4; wd=0.001;
dropout=0.1; epochs=100; grad.accum.stepsse
Arxiv
Text Classification
N=16K-64K; laycrs=4; heads=4; d=256; batch=2; Ir=3e
wd=0.01; dropout=0.1: epuchs=100; aecumaccmeellpss-11
Description:
Unless otherwise specified, we adopt a linear warmup-decay learning-rai -aati sched- ule. Let T denote the total number of optimizer updates,
T = epochs x len(train loader).
The learning rate increases linearly from to the base learning rate (reported in Table 5) over the first 0.017 updates, and then decays linearly to 0 over the remaining T 0.017 updates. The learning-rate scheduler is stepped once per optimizer update. We use the AdamW optimizer with hyperparameters listed in Table 5. For experiments with a learning rate below not apply linear warmup or a learning-rate scheduler; instead, we train the model using a constant learning rate for the number of epochs specified in Table 5.
10-4 we do
Data Pre-processing for Arxiy:
To evaluate long-context classification performance, we construct 16K-, 32K-, and 64K-token variants of the ArXiv dataset using two-stage preprocessing pipeline. First, we tokenize all documents with a basic English tokenizer and retain only those whose raw token length exceeds predefined minimum threshold, ensuring that each example contains suffi ciently long context. Next, we perform streaming sequence packing. Documents are grouped by class and concatenated sequentially until a target sequence length of 16K, 32K, or 64K tokens is reached. To maintain high packing efficiency, only very small residual fragments are discarded. This procedure yields long, contiguous sequences that preserve the natural structure of individual documents while enabling fixed-length training. After balancing classes, the resulting dataset sizes are as follows: 16K (1,947 training examples, 209 test examples), 32K (3,650 training examples, 520 test examples), and 64K (3,882 training examples, 384 test examples).
14

---

Published as a conference paper at ICLR 2026
Table
FashionMNIST
@
Table 7: Tiny Stories @ 512
Table 8: Penn Tree Bank @
784
128
Method
Perplexity
Method
Accuracy
RACE (P=3, L=4)
3.9
Method
Test PPL
RACE (P=2, L=5)
87.7%
RACE (P=4, L=4)
3.3
RACE (P=2, L=2)
54.7
RACE (P=3, L=5)
87.5%
RACE (P=5, l.=4)
2.7
RACE (P=3, L=3)
54.2
RACE (P=4, I==)
86.6%
RACE (P=5, L=5)
5.1
RACE (P=4, I==4)
53.4
RACE (P=4, L=5)
85.7%
Linear
6.0
Angular (1=8)
58.8
Linformer-
87.7% %
Angular (1=8)
2.9
Angular (y=12)
57.6
FlashAttention2
87.2%
FlashAttention2
3.1
Linear
73.2
Angular (7=8)
86.4%
Linformer- 128
4.6
FlashAttention2
55.4
Lincar
85.8%
Performer-256
7.1
Performer- 256
86.6%
Table 9: Comparison of attention methods on Table 10: Comparison of attention methods on nat- ural language understanding tasks
Long Range Arena
Method
ListOps @ 2000
Text Retrieval 6/8000
Method
Vahoo 256
IMDB @:512
SST-2 @ 1024
(%)
Acc.
Acc. (%)
Acc. (%)
Acc. (%)
RACE (P=2, L=2)
41.9%
80.3%:
(P=2,
(P=3, L-=))
41.3%
80.8%
RACE (P=3, L=3)
66.6%
81.3%
77.1%
RACE (P=4,1=4) L=4)
41 166
80.9%
RACE (P=4, L=4)
67.2%
81.3%
79.4%
Linformer-128
38,90 38.9%
76.1%
Linformer- 128
64,7%
78.2%
75.1%
FlashAttention2
FlashAAtention2
67.2%
80.0%
78.5%
Angular (y=8)
42.2%
0OM
Angular (ym8)
67.0%%
79.6%
77.25 77.2%
Linear
39.6%.
80.6%
Linear
66.9%
80.9%
78.0%
Performer-256
40.2%
80.8%
Performer 256
YOSO-16
50000
500 00
150.00
8
400.00
100
300.00
0.00
0.00
130K
1PM
75M
130K
Sesuence Length
Length
Sequence
CPU: RACE (P=
(b) CPU: RACE =,
CPU: RACE (P -,,
Attention RACE
2500.00
Unear
Time (S)
0.20
1500.00
Time
1000.00
0.10
500.00
0.05
Iefbrrer
0.00
0.00
Parfarme
16K 32K
64K
128K
130K
2M
4M Sequence Length
7M
Embedding Dimension
(d) d scaling @ -565536
(e) GPU: RACE (P 4,
Figure 6: (a-c) CPU results for different (P, L). (d) Linear attention scales quadratically in d, while RACE scales linearly (fixed N -555536) (e) GPU scaling under hyperparameters different from fig. 4.
Data Pre-processing for Food-101: To evaluate long-context image classification on the Food- 101 dataset with 16K token context length, reduce the dataset size by discarding 50 classes. We train the model on 20,000 samples and evaluate on a held-out test set 2,500 samples. Images are processed using patch size of 4, an input resolution of 512 512, and stride of 4. All remaining hyperparameters are reported in 5.
15

---

Published as a conference paper at ICLR 2026
B PROOF OF THEOREM 2
This section provides a complete, self-contained theoretical treatment showing that our RACE At- tention closely approximates Angular Attention. We give explicit high-probability bounds for (i) the kernel error, (ii) the attention matrix error with a clean separation of numerator vs. denominator effects, and (iii) the end-to-end output error (Theorem 2). Let's also reintroduce the notations for the convenience of the reader.
B.1
SETUP AND ASSUMPTIONS
Data. Sequence length N, head (per-head) dimension d. Queries/keys are unit vectors:
Q Kg E Rd with l|Qell2 || = 1, 1, E (I....,N).
Target kernel (P-powered angular).
n(Qu, K2) == Kang (Q,, = =(1- 21- (0T E 10,
S NNN with St, = k(Qu,, Kj).
Soft RACE features. For each ensemble l f= 1,....,.. Ia:
Draw random hyperplanes W(()) E Pxd whose rows w are i.i.d.
Corners y [+1]* (size R = 2P), with corner vectors e, (+1)P.
Logits s (z; = (w00) Ur, temperature 3 > 0.
Define the (probability) feature ())) (x:
expl (0p(3 10 (x) Σn exp(3 (3 s00) (x;
RACE kernel and matrices.
For each ensemble, define the per-table kernel matrix
$ (Q:))
$ L Σ 30 t=1
Let the (single-table) bias matrix be B = E[ S.
Assumptions. For convenience, we restate the two assumptions from Section 3.3
(A1) Row sums of S are bounded away from zero i.e., 8min min,(S1); 2 C1N for
some constant C1 > O, which ensures stable normalization in attention.
(A2) Spectral norm of is bounded ie., ||S||| & C2N, which follows from S.g [0, 1].
Notation: We denote |/2 as spectral norm for matrix and Euclidean norm for a vector, || || for the Frobenius norm matrix and a matrix M, we denote || [] = max; E, MMal induced row-sum norm.
B.2 KERNEL CONSTRUCTION WITH THE BIAS TERM
We begin by formalizing how single hash table induces kernel matrix via the soft RACE features. The next lemma records norm properties that will be used repeatedly.
Lemma 3 (Bounds for single ensemble). Let (1() N be the matrix with the i-th row (00(2)) (Q.) and 4x defined analogously. Then:
1. 500 क (2) TT
2. Each row of 11 and o K is probability vector; hence 1
(6) 2 [F, | 1a VN.
3. Consequently |/ N.
16

---

Published as a conference paper at ICLR 2026
Proof. Each (x) is softmax over R 2 corners, entries nonnegative and sum to 1. Item (1) is by definition of " For (2), every row p satisfies llpll2 - || = 1, hence [ 11?
Σ, (Q)0)())) & N (and similarly for T ( Item (3) follows from || || | S |||||||
Having controlled the feature-induced matrix norms, we quantify the zero-mer mean fluctuation of one ensemble around its expectation and prepare moment bounds needed for matrix concentration. Note that the hash projections W (and hence S(t) are independent for & - l..... L.
Lemma 4. Let X = 3 E.S((e and write
L x(0) + B.
A = S S-S-
S =
Σ
L
Then:
1. [[ [*]
2. [X [|2 S 2N.
3. With
(1X10) (1-10)
Σ (2x10)) (
1.
Σ
:: max
we have U & 4NN2/.
Proof. (1) By definition, ( S(0) - E[S(0), hence B[x TESSTO] - [[S(0
(2) By Lemma 3(3) we have ||$00||2 S || || S N. By convexity of the spectral norm,
||B[S - 1[ N.
Therefore, by the triangle inequality,
(X 1l | - = < ||000 + 1BB I 2.V.
(3) Let Let = (0 Then
L
Σ (x(0) = L Σ E
Using subadditivity of || 11,, Jensen, and ||AB||| -
Σ ((
Σ
E [[X
s D t=1
1 F
Σ
4N2 (2N)²
< L t=1
L
E=1
The same bound holds for two yields e & 4N2/LL
Ete B[(Y(0)TY(0)]
by symmetry. Taking the maximum of the
L
To convert the moment and uniform bounds above into a high-probability spectral- -orm bound, we invoke standard matrix Bernstein inequality from Tropp (2015), stated next for completeness.
Lemma (Matrix Bernstein). If (() mx independent mean-zero matrices with |2 S H and variance proxy v, then any t > 0,
2t < (m + n) exp ( t2/2
P
Σ 2
U Ht/3)
17

---

Published as a conference paper at ICLR 2026
Next, applying Lemma 5 with the parameters established in Lemma 4, obtain the following nonasymptotic deviation bound for the kernel estimator. Theorem 6 (Kernel deviation with explicit constants).
With probability least 8,
N
2N
2NN 3
4 N
| S - |Bll2 + 4
log
log
VT.
L
5
Proof. First, rewrite S S-S S-San -as
L S-S 1 Σ 50 - S
1 Σ
(50
-300))331)) + (B1310) - = -
x + +B. B.
L 8=1
t=1
E=1
By the triangle inequality,
- 8112
1
Σ x
+ |lBl112
L
It remains to upper bound the random term with high probability.
Set z( = - Then the g(0) are independent, mean-zero, N x random matrices. From
Lemma 4(2) we have (|x(0) s 2N. Therefore. || ( 1le s H. == 2N
L Similarly, Lemma 4(3)
4N2 gives v < I_ Applying Lemma with m = n = yields
L
12 2 Ht/3)
Σ
21 < 2N exp
Let = log
2N 6. To make the RHS & 6, it suffices that
2uH
2
20 v
2 0.
( Ht/3)
3
Choose
2
t 2/eu H
Writing a = 2//u and b = Hu (so + b) gives
2 2uH t- 2uv (a + b)²
2uH
(a + b) -2u (4vu 2wv) (
Hu Huv 2 20. 0.
Therefore,
Σ
z
s 2/eeu +
2
with probability at least
2
Plugging S 4N² and H-
2N T.
yields
L
4N2
2
2N
N
4 A +
Σ
< 2
u +
u
4
V u
u.
L
3
L
VL
3 L
1=1
2
Since Σ/_ 7(0
1
((0,, we conclude that
I
1 Σ x(0)
1
S N
2N
4
N
2N
log
+
log
with probability
2 1 5,
VL
3
5
2
and therefore
S - S112 < | 2 + 4
N
log
2N
+
4
2N log
VL
3
L
8
claimed.
18

---

Published as a conference paper at ICLR 2026
The deviation bound decomposes into variance term and (deterministic) bias term B. We now bound B explicitly function of 3 and P. Before stating the result, we introduce the following technical result that proves deterministic inequality and will be required to bound || 22-
Lemma 7. Let P. E I be probability vectors with nonnegative entries summing to one. Let E arg max, Pr and E arg max, 9r. Then
1p 1fa - bb} 1 (1-Pa) + (1))))
Proof. We consider two cases.
Case 1: b. Then 1 1a b] and
p 1|
9 1 Pada
since p 2 Pa9a
By the inequality (1 - (1 - y) 2 0 = 1 xy zy - (1 x) + (1 - y). we obtain
1 - p S (1 - Pa) + (1 %a) = (1 Pa) + (1 - Qb)-
Case 2: + b. Then 1fa b) 0. Because maximizes q, we have ar S ob for all and la S - (since the total mass outside b is 1 - (b). Hence
p Pala + Eprg S Pa(1 26) 9b > P. Pall 96) + (1 Pa)
rza
Finally,
(1 - Pa) + (1 96) - [Pa - (1 = 2[(1- - -Pa)(1 96) 2 0,
so 9 (1- Pa) + Combining both cases gives the desired bound.
-b).
Lemma 8 (Bounding the bias term). Fix P 2 1 and B > 0. With S and B as above, let e ==
tann(1). Then
B
<
4
NP
+ (v2 NPe
2T
B
Proof. Let denote the inner product similarity by p== Q, Ky. and recall that the angular kernel is Kang (Q,, K2) = 1 cos-=((p From standard LSH theory, for P i.i.d. Gaussian hyperplanes
W(t) E Pxd, the probability that all P bits match is exactly:
P (hr(Q.) (r(())())))))) Kang (Qi, Kg) Sij-
Now define the softmax sketch feature for the hash table &:
1 (x:r) == tanh(w((0)) Ter, Ur.
[x)) = En (x:"")
where e, E ( denotes the binary corner vectors length P. and = 2P. Let S00 NNN be the kernel matrix for single hash table:
EC ( = E (0000)))((00()))))))
(000
Syy = Kang (Qi, (Qi,K)) K,)
and recall the bias matrix is B == E S. Our goal is to bound || To do this, fix any pair (i,j) and note:
E E(S - Styl = E (0)1))))) T (00 P(hr(Q.)) = =
Next, let r* (x) = arg max, s (z;r) sign(u(z)) denote the maximizing corner for x, where
ue(x) tan 2:). The function (00) (x:;) Ep ue(x)) r, is linear form over the binary
19

---

Published as a conference paper at ICLR 2026
corners {=1)P. To evaluate the normalization term in the softmax, note that the exponentials factorize across coordinates because r, appears only in the term uc(2)r Hence,
P
(z:r)
Σ
Σ rp=#1
e ((
E
Σ
II
re(t1p
r1=#1
PI r1=#1
1p=#1l=1
P
P
P (z))))
Σ
Sue (x)rr
II
(cBell)) + te (e
II
where the last equality uses the evenness of the hyperbolic cosine, cosh(z) = cosh(|=|). Therefore, the softmax probability assigned the dominant corner r* (x) can be written in closed form
e E. (x))
(o (x)))-())) II, cosh (z)))
II t=1
II (2
((((( + (()
where or (2) 1/(1+e denotes the logistic function. This factorization expresses the max-comer mass as a product of por-ccordinate logistic terms.
To bound the total probability mass outside the dominant corner, the incquality - II, a+) S Σ, ar for a₂ E [0, 1). which we apply to Oz = 1 - a (23)u,())) Hence,
p
p
1 1-
=1 1- II (23 S (1-0 S
Σ (x))
(5)
t=1
where the final inequality follows from the standard logistic bound 1 1- 1 (2) S e for all 2 0. Intuitively, this means that the total softmax probability mass outside the most likely corner decays exponentially with the scaled activation strength 33 (1)] along each coordinate. Now, for each bit,
ux(2) tanh(w, x) with w/ x (0, 1). Let Z w. x. Then
E (x]] Ele 2 tanh(2))].
We split into two regions. (1) On |2| S 1, we use Hence
Itanh 2|
2
|e]
2 so e 28 tanb(Z)] S e -
/'' E -B= dz S
2 1
Ele tanh(
1|2|51] S V2T J
V2T B
(2) On | > 1, we use tanh = 2 (anh(1), so e - tanh(2)) < -2 taub((), Thus
2
Ele 2 tanh /
1 | S 2, 2anbb 1) PP(() > = 2c 2/3 -2/ tanh(1)
P(Z 1) S 2,5 tanh(1)
e -08
where the second last bound is due to Mill's inequality and the last inequality follows from the fact that / / 1/2 1. Here tanh(1). Combining the two expectations get,
Ele 2f]
+e - e 2 (aan(11).
V2 3
Substituting back into Eq. equation 5, obtain
2P
T (0) (x))
S
+ (9.
/2T 3
Next, let p = (Q.) and = (K2) denote the softmax feature vectors for Q; and Kj. and let = r" (Qi), r* (K,) be their respective dominant corners. By the deterministic inequality in Lemma 7
Ip q 1aa = b} < (1 pp.) + (1-qb),
valid for any probability vectors p, g and indices b, we have
B | Sty
|lpp q) IPaa- = bl| EF(1 Pa] + E -b
20

---

Published as a conference paper at ICLR 2026
Using the bound on the expected softmax tail probability for both Q₁ and Ky then gives
[B[S Siyl S 2
2P
+ +((P)
4P
+ +
(6)
2
V
Therefore,
|B S || z N
Biyl S N
4P 2 3
+ O(PE (0P)
in
This proves the claim.
We now propagate the kernel-level emorr into the attention matrix. This requires controlling the normalization (row sums) and its inverse, which we address next.
B.3 FROM KERNELS TO ATTENTION (NUMERATOR VS. DENOMINATOR)
Let S = S + A, D (iag(S1). and î didgga()) ($1) D E. Define the attention matrices
= D Ā : 5-13.
The following lemma ties the row-sum perturbation E to A and gives simple invertibility condition
for D.
Lemma 9 (Row-sum and inverse diagonal control). Recall that smin min; Di > O. Then
1. Fll2 & | < V
2. If | | S 8min//, then 1 112 2/8 Smin-
Proof. (1) Row-sum control. Since S = S + A and D = diag (11, we rewrite
E Ō= = diag (IS - -5)1) = diag( A1).
Hence each diagonal entry Es = (A1); = Σn= Dij. so
N
|||| = max Exl = max (A1);
max
A,yl = ||
j=1
For the second inequality, by Cauchy-
Cauchy-Schwarz Schwarz each row i,
1/2
VN
VN 11A,,112
Moreover,
max A |12 max A| T eill2
A |22lez/12 ||
Taking the maximum over yields
|| max Σ < VN max /AA,112 S VN
(2) Inverse diagonal control. Because D D + E is diagonal, its smallest diagonal entry satisfies min D.s min min + Ea)) 2 min D,: max Exa Smin
E||2-
If E| < Smin/2 /2, then min, Di 2 Smin/2 so D is invertible and 1
1
2 Smin
1 max D
<
8min
|
8min Smin/
21

---

Published as a conference paper at ICLR 2026
Assumption (AI) ensures D has diagonals of order N, but we must still control E. The next lemma shows that the condition || 2 $ Smin/2 /2 holds with high probability once L and / are moderately large.
Lemma (Concentration bound for F.). Recall == 5 D diag((S - 1) and assume (AI): N. Then with probability at least - 5,
8min
|El|2 NV log 2N2
4 NP
O(NPE
c= 2 tanh(())
V2T
3
In particular,
|| S
2 Smin holds with probability at least whenever
2N
32
I. 2 Ci
log
B
P.
8
Civ2
in which case the exponentially small term N Pe can be absorbed into constants.
Proof. Since
== D - D diag( ($ - -S)1),
have
N
|||| max Σ (S.g 5:y)
Decompose the kernel error as
S-S -S- - S) - + B,
where B is the bias matrix.
Hence for any row i,
(SS - Si)) $ Σ Siy - E[S + Σ |iyl
$ N max 18.g E[Syy]l + N max Biyl-
Taking the maximum over gives
||E||2 N max |S
B[S N max Byyl- 1.j
()
3( Each Sij is an average of L i.i.d. random variables Si [0, 1]. By Hoeffding's inequality,
Pr([S., B[š E) 2e 21.²
union bound over all N2 entries yields that with probability at least - 6,
max 1
|S, E[ S V
1 log 2N² 8
27.
Eq. 6 gives the entrywise bias bound
4 P
max 1,j
Buyl <
O(Pe-a8) -88).
22T B
Combining the bounds proves
Ell2 S NV I log 2N2
4 NP
+ (().
2m
Under assumption (AI), 8min
C.N. Thus [||| 5 fmin is ensured whenever
27. log
2N
4
P
<
C1 2
2 3
22

---

Published as a conference paper at ICLR 2026
A sufficient explicit choice is
2N
2 C
log
8
P.
Ci Ci 2T
while the exponentially small term is absorbed into constants for moderate 3.
Now, with row-sums controlled, relate A and A exactly through a decomposition that isolates the contributions of A in both the numerator and denominator.
Lemma 11 (Exact perturbation identity and bound).
A
D- 1D-1-D-13
Moreover, whenever |El| < Smin+
|
|||| EE
|| - Al S
8min
Mmin (miin
[E
Proof.
Using 3 55 S and π D E,
A A = 1-13----S---A++00--00
For the bound, we apply the submultiplicativity property of norms. When
E|| < 8min, we have
1|2 ||D-11|
1/ i/mmin and
|| [
|
1|2 - 1/(smin |Ell2)) Moreover,
|
D- 112 | 1ー1 --
D 112 - 1 |
112
8min (8min || (2112)
Hence,
||
|| ||
| - A -
|D= || + 11-1 11-11-111111 S
8min
|
8min (8min
Specializing Lemma 11 to the regime | S 8min/2 (guaranteed w.h.p. by Lemma 10), we obtain concise spectral bound for Ā All2 in terms of ||2
Lemma 12 (Attention deviation). If Ell| S 8min /2, then
21 A11 211
|| - A|22 v
VN ||
Smin smn
Proof. From Lemma 11,
||
||S||2
|F
A All2
Smin
E|
Smin
(Smin
[ll12)
Since ||]|2 < Smin/2 2 follows that
2
Smin
E 2
Smin//
Sziin
Substituting this bound gives
A||
2||S1|2
A
All2
|F/1
Smin
s2
By Lemma 9(1), |E < || S VN || Therefore.
2 ||A
S1
| All2 <
VN ||]|2
8min
which proves the claim.
23

---

Published as a conference paper at ICLR 2026
Finally, we translate attention deviation into end-to-end output deviation by single multiplication with the value matrix V, yielding the main saiite-sappe guarantee.
Theorem 13 (End-to-end output error), Let V E IR-xx be the value matrix. With probability at least - 8, if BlI22 S Smin/2 then
110001 <
S min
4
NP
OONNEE -0)
log o +
N |
log
Fmin
22
B
VL
T.
where c 2 t1nh
Proof. By the estimator identity, Ō = AV and O = AV, hence using submultiplicativity of the Frobenius norm,
110 - O1 [I A)V F S - Alla |
Under the condition
| S Smin/ Lemma 12 (Attention deviation) gives
|| A 2
2 Smin
||S S112.
min
Applying Theorem 6 (Kernel deviation) yields, with probability least 1 8,
N
2N
2.V 5
| - S112 I |B|| +
log
+
log
VL
3 L
Finally, substitute the explicit bias bound from Lemma 8:
NP
B -
+ OONNE
== 2 tanh
V
B
Combining the three equations proves the stated inequality:
(
4 NP
N
N
||ō Ji==Ole S
W
ONNN
VL V
log
2N
log
2N
||
Bentn
min
B
L
Proof of Theorem 2. Under assumptions (A1) and (A2), we have 8min Therefore, the prefactor on the r.h.s. of Eq. equation 7 boils down to
2 C and ||S|| S C2N.
2
2/15||2//
2 CN
2C2NVN O
1
(8)
C2N2
8min
min
Therefore, combining eqs. equation 7 and equation 8 yields
11ō O =0
N
I. log 2N 8 + NPe |IV| log
VI
PVN
N 3
log
2N
VN log 2N + PVN |
T
Dividing both sides of Eq. equation by V to express the bound in terms the per-token RMS enror gives
Ō - 1
0
log(2N/8)
+ log 2N o + Pe IIV|LE
L
To compare the last two variance terms, observe that
log 2N
(og(2N/6)
log(2N/8)
Hence, whenever L > 1og(22/6) Olog N). the (1/L) log(2N term is asymptotically domi- nated by Vlog(2N/8)/T and can therefore be absorbed into it. The exponentially small correction Pe-eB is also negligible for moderate values of B. Absorbing all constants and the mild difference between 1og(2./00 and log(N/6) into the Big-O, we obtain
Õ -0-O
( (og(N/6) L |I
with probability at least - 6. This completes the proof.
24

---

Published as a conference paper at ICLR 2026
B.4 CAUSAL RACE ATTENTION
Algorithm RACE Attention (causal)
Input: Q. RNxd, number of hash tables number of hyperplanes P; temperature 0.
Output: Ō
IR Nxd
1: for 1=1,,.. l.,....,44 do
2:
Draw W(() Pxd
I| P random hyperplanes |/ R. corners
3: Define the corner set V [+1}² (R=2%) with E {+1}
4: Build o D RRN with rows
exp(((tan((W + ( Σn (xp(3(tanh( ( (x)) v,,)
x E (2)
Initialize cumulative bucket statistics: A < OR R. B ORxd E Rxd
5:
6:
for / ,,...., N do
[ R"
Vi E Rd
8:
(1) + (00
+ (+ (1 [1
II RRR 1/ R Rxd
B + B + (Ø K TV
9:
10:
[t, R
num
(8)
4 Q [4,
Blu
II (1 R) -RR d) Rd
den
(4) ① (2) [1, 4 Acum
11 (1 R) (R) R
end for
14: end for
For each
N: N:
Num, L
1
Σ num
(e)
E Rdd
Den, 1
Σ
den, (0) R
Ô, Den;
Num,
E R
[
16: Return: Ô
R Nxd
We implemented the causal version (see Algorithm efficiently using OpenMPiCUDA-based par- allelization rather than a naive nested-loop approach. Each hash table is processed in a separate thread with its own cumulative bucket arrays, and updates are performed incrementally sin- gle left-to-right scan. This avoids redundant recomputation at every step using torch. cumsum)) and enables CPU/GPU-Level parallel execution with negligible synchronization overhead.
25

---

Published as a conference paper at ICLR 2026
Q
K
hush
heads
agaregate probwbilttes with valses
PRUN
00.8
[Kua Aiatth Liuatt
L
2a.1
RRaa Roy R
N
normaline
query sitonn
prothabiliiies
fanen
05.1
01.1
morenleed DE vecuu bocket
MAUN
MalMal
2V
Figure 7: RACE Attention pipeline from the inputs Q, K.V. RNxx to the output O R queries/keys are soft-hashed into R buckets across L tables, keys/values form per- per-bucket summaries, and each query mixes the bucket summaries to produce O.
hashed
keys
After
long
hiking
young boy
cooked
dinner
lake
3
of
the
by
by the
After
long
day
of
hiking
the
young
boy
cooked
dinner
the
lake
hashed query
R=
L
Figure 8: An intuitive schematic of how RACE Attention runs with L hash tables and buckets per table. Similarity between Queries and Keys is highest they both assign higher mass same buckets across all hash tables.
26


Reviews:
[{"review_id": "FwFW2WZhm0", "reviewer": "Reviewer_W9FA", "summary": "This paper introduces a novel linear-time attention mechanism. The approach replaces the exponential softmax kernel with a monomial of cosine similarity raised to a power, enabling approximation through randomized projections. By leveraging angular similarity, Locality-Sensitive Hashing, the authors propose an efficient that enables outrageously large context windows  up to 75 million tokens on CPUs and 12 million on GPUs.", "questions": "see weakness section.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This method enables linear-time and memory-efficient attention that scales to tens of millions of tokens on standard hardware, which is impressive. \n2. The algorithm is simple, differentiable, and can serve as a drop-in replacement for softmax attention.", "weaknesses": "1. **This paper is very similar to YOSO [1] (for example, the finding the similarity between equation (1) and (2) in the text, the use of LSH in estimating the similarity function, the algorithm of estimating attention outputs via hashtables), but this paper does not discuss and contrast with [1].**\n2. The experiments only show model accuracy on short sequence lengths (< 8K). What about longer sequences? \n3. The efficiency results in Figure 3 are not very meaningful as any linear attentions can be extremely efficient by tuning their hyperparameters. For example, for $\\phi(Q) \\phi(K)^T$ type attention, by setting the output dimension of $\\phi$ to be 1, its efficiency can beat any other methods. To show efficiency, the runtime and memory results should be coupled with the corresponding accuracy results. \n4. Figure 5 has the same issue, what about the accuracy? \n\n**If the authors can address my concerns, I am willing to raise my score.**\n\n[1] Zhanpeng Zeng, Yunyang Xiong, Sathya N. Ravi, Shailesh Acharya, Glenn Fung, Vikas Singh. You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Sampling. ICML 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "smaO5gXsZv", "reviewer": "Reviewer_eQBU", "summary": "This paper introduces RACE Attention, a method to address the quadratic time and memory complexity of standard softmax attention. The authors propose replacing the exponential softmax kernel with a high-degree monomial of an angular (cosine) similarity kernel. This specific kernel choice allows them to leverage Locality Sensitive Hashing (LSH) and Repeated Arrays-of-Count Estimators (RACE) sketches to compute the attention output in linear time and space complexity.", "questions": "1. Can authors elaborate on how to choose $\\gamma$? Would it be through a hyperparameter search or is there a principled way of approximating a good value for it?\n\n2. Once more question on $\\gamma$, could authors provide any sensitivity analysis of how the final result changes with respect to the small changes in $\\gamma$? Perhaps another useful figure would be to use the data from Fig 2 and plot the distribution of the attention distances between softmax and the angular attention to see how it varies as $\\gamma$ is changed.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.  The primary contribution and strength of this paper are the scaling results. Figure 5 shows that RACE on a CPU can outperform FlashAttention on a high-end GPU at massive sequence lengths, is a compelling demonstration of the algorithm's effect over hardware acceleration.\n\n2. The paper is well-written and easy to follow.\n\n3. The theoretical result also provides a nice bias-variance trade-off of their approach.", "weaknesses": "1. The paper seems to be lacking some important baselines. The authors compare their result to FlashAttention, however, at the moment FlashAttn 2 and 3 are also available that performs much faster and are not included in the comparison. Moreover, the paper focuses on alternatives to softmax and is for example lacking a comparison to Sigmoid Attention which also provides a simple kernel implementation.\n\n2. The paper is a bit vague and ambiguous in their main algorithm. The authors argue that they use cosine kernel to prevent the exponential of softmax and be able to use RACE sketch. However, it seems that Algorithm 1 is still trying to implement softmax. Am I misunderstanding this? Technically, it seems that the connection between the features $\\phi$ and the angular attention is never clearly made.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x2DbWcemNn", "reviewer": "Reviewer_if3U", "summary": "This paper describes RACE attention as a linear-time alternative to softmax attention for very long contexts. The main idea is to replace softmax with powers of angular similarity, and then approximate this term using RACE sketches. To do this, the algorithm uses soft LSH so that its differentiable. This achieves far reduced complexity versus quadratic for standard attention, as is common in most methods for self-attention approximation. What is nice is that the experiments are broad and cover language modeling, masked LM, and classification. In this context, scaling experiments show processing of tens of millions of tokens on CPU and GPU for a single attention layer's forward-backward pass. This will be the main highlight of this work for most readers.", "questions": "1. Minor: Is adapting the analysis to causal masking relatively easy (but hasn't been worked out yet) or does one run into problems?\n2. check some of the references above. There may be others.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The scaling experiments are quite impressive. Regardless of my other comments below, this is a good practical contribution. Also, it is interesting that CPU-based RACE is viable and in some regimes can do better than FlashAttention. This point about algorithmic efficiency versus hardware acceleration could really be a main message of the paper (more on this below). In any case, reaching 50M/75M tokens is definitely a strength (but in the current version of the paper, this comes with some disclaimer).\n\n2. The experimental breadth is very good. Both CPU and GPU kernels with OpenMP are mentioned. This is a strong engineering effort and if code is provided, it can benefit many groups working in this area. \n\n3. Experimental verification of how increasing degree can mimic exponential behavior in this setting is useful. Some analysis is included for the bias-variance to guide the choices in the sketching component. This is all good.", "weaknesses": "1. I am a bit confused by the numerous instances of \"stress test\" and therefore it unclear what the scaling experiments actually show. When stress testing 1 forward-backward pass with the multi-head attention layer, is this timing a single layer, not end-to-end model training? If so, the 75M token claim is for one attention operation, not training the full model? Is this paper only describing benchmarking the primitive or does any model work at these lengths? The reason for this question is the title \"outrageously large context windows\" -- is this only for the stress tests? The most reasonable reading of the title suggests full model capability.\n\n2. I am having trouble understanding the tables on page 8. Is angular expected to be better than RACE? \n\n3. The paper https://proceedings.mlr.press/v139/zeng21a.html uses related ideas and also seems motivated by similar upstream papers. Another one is https://aclanthology.org/2022.iwslt-1.4.pdf. The positioning of this work on page 4/5 should at least describe how they differ.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)