Towards Sampling Data Structures for Tensor Products in Turnstile Streams
Authors: Zhao Song
Shenghao Xie
Samson Zhou
Venue: ICLR 2026 Poster (2026)
Keywords: data structures
sampling
turnstile streams
lower bound
hardness
space complexity
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: This paper studies the computational challenges of large-scale attention-based models in artificial intelligence by introducing innovative sampling methods in the streaming setting. Inspired by the classical definition of the $\ell_2$ sampler and the recent progress of the attention scheme in Large Language Models (LLMs), we propose the definition of the attention sampler. These attention samplers select the important coordinates in attention computation efficiently, bypassing the quadratic computational burden of computing the entire attention matrix. We demonstrate the effectiveness of the attention sampler from a theoretical perspective, including space and update time. Additionally, our framework exhibits scalability and broad applicability across various model architectures and domains.

Published as a conference paper at ICLR 2026
TOWARDS SAMPLING DATA STRUCTURES FOR TENSOR PRODUCTS IN TURNSTILE STREAMS
Zhao Song"
Shenghao Xiel
Samson Zhou !
ABSTRACT
This paper studies the computational challenges of large-scale attention- based models in artificial intelligence by introducing innovative sampling methods in the streaming setting. Inspired by the classical definition of the & sampler and the recent progress of the attention scheme in Large Language Models (LLMs), we propose the definition of the attention sampler. These attention samplers select the important coordinates in attention computation efficiently, bypassing the quadratic computational burden of computing the entire attention matrix. We demonstrate the effectiveness of the attention sampler from theoretical perspective, including space and update time. Additionally, our framework exhibits scalability and broad applicability across various model architectures and domains.
INTRODUCTION
In recent years, the field of artificial intelligence has witnessed a significant paradigm shift with the
advent of attention-based models, particularly in the domains of natural language processing and
computer vision (Vaswani et al. 20177: Devlin et al. 2019 Liu et al. [019 Yang et al., 2019 Brown
al., 2020 Zhang et 2022]] Chowdhery al.] 2023 Touvron al. 2023a Inc. [2023] Manyika
& Hsiao 2023). At the heart of these models lies the attention mechanism (assaani et al., (017)).
which is powerful tool for enhancing the performance of deep learning networks. It enables models
to focus on relevant parts of the input data, thereby facilitating context-aware processing.
However, as these models scale in size and complexity (Zeng et al. 2024 Reid et al. 2024 Zhang et al. 2024; Dubey et al.] 2024 Abdin et al.) 2024). the computational demands of the attention mechanism increase exponentially, posing significant challenges in terms of efficiency and scalability [Fu 2024). In particular, traditional attention mechanisms used in Transformer models (Vaswani cet al. 2017) require computing attention weights across all elements of the input sequence. leading to quadratic increase in computational complexity with respect to the sequence length (Alman &
Song 2023 Kacham et al.) [2023] Han et al.] 2024) Zandich et al.) 2023 Alman & Song] 2024a b 2025a). This computational burden becomes particularly pronounced in large-scale applications. It
hinders the usage of attention- based models in resource-constraine settings and limits their real-time
processing capabilities. To deal with this problem, the core question we ask in this paper is:
Instead of computing all entries, can recover the most important ones in efficient space and time?
Attention samplers. We adopt the classical idea of sampling a dataset, which selects important items
to represent the entire dataset. Sampling is a central and effective technique for analyzing large- scale
datasets, which has broad application in the field of big data (Vitter) 1985 Gemulla et al.
2008
Cohen et al. [01 1 2014), including network traffic monitoring MMa et al. (2066] Huang et al.
2007
Thottan et 2010). database management (Haas & Swami 1992; Haas 2016 Cohen Geri
2019
and data summarization (Frieze et al.) 2004] Aggarwal et al. 2009 Mahabadi et al. 2019 9 Indyk
al. 22000; Mahabadi et al. 2020). A well-known example is the bg sampler that is first asked by Cormode et al. (2005) and studied by Monemizadeh & Woodruff (2010): given a vector x E IR"" we
sample an index E [n] with probability |
Inspired by the l sampler, we propose the following
* "University of California, Berkeley. E-mail:
Texas A&M University. E-mail: xshl1020ee w0w.:/22mmmm.....m..o..
Texas A&M University. E-mail: samsonzhou@gmai1 con

---

Published as a conference paper at ICLR 2026
attention sampler, which seeks to sample the most important coordinates in attention computation, reducing computational overhead and computer storage.
Definition 1.1 (Attention sampler), Given matrix A E R="'xd xd vector Z E Rdd and a distribution
(Ax)). function g. the attention sampler samples index i E [nx] with probability p: Ee= ([(A));))
To understand the matrix-vector multiplication Ar in our attention sampler. recall that given input matrices A1, A2 gexd the linear where Wq. WK E Raxd are learned weighted projections. For linear self-attention, A1 and A2 are identical. Let X = W be the fused key and query projection matrix, let A A @ A2 E
matrix is defined QK' := A WeW k A
R=nxxd x and let x vec( E Rdd we simplify the expression by a well-known tensor product vec(A, AT) Av. Here, vec denotes the vector representation of a matrix by concatenating the rows. Therefore, our attention sampler detects the dominant entry in the linear attention matrix with respect to the distribution function g.
construction (Alman & Song 2024a): vec(QK
A crucial practical relevance of our attention sampler is the sparse attention mechanisms. The attention matrix has been shown to be naturally sparse empirically and theoretically (see e.g. Child
eet al.] 2019: Deng et al.] (002bb). Based on this observation, researchers seek to reduce computation
by focusing on heavy coordinates (Child et al., 2019 Kitaev al. [020 Wang et al. 2020; Allmn & Song 2023; Brand et al. 2024; Deng et al.] 2023c. Lai et al. 2025; Xiao et al. | Zhang et al.
20250. In particular, they construct a sparse mask that selects the importance entries in the attention
scheme while zeroes out the others. Since the attention sampler recovers the heavy coordinates in the sparse attention matrix, they can be applied to enhance the construction of the sparse mask.
Attention samplers in turnstile streams. Suppose that we can store and process the entire attention matrix, then the sampling problem is trivial since we can compute the sampling probabilities explicitly, However, mentioned earlier, we have strict memory and process time constraints in real- world applications, which inspires us to study the attention sampler in the streaming model. In this model, an underlying dataset is defined implicitly by data stream, in which each element of the dataset arrives sequentially. The core advantage of streaming algorithms is their ability to provide accurate estimates without storing the entire input stream, enabling real-time monitoring of large-scale datasets. Therefore, this paradigm is particularly well-suited to tackle the computational bottleneck for modern attention mechanisms. For instance, recent theoretical work (Han et al., 2025| Haris & Onak 2025) studied attention approximation algorithms in the streaming model inspired by auto-regressive Transformers. These results closely align with the practical requirements of research in streaming Large Language Models (Xiao et al. 2024). a field that has seen a surge of interest in LLM research (Strati et al., 2024; Yao et al.] 2024 Shikhar et al., 2025 Xiao et al., 2025). where the motivation comes from long (or infinite) sequence generation, c.g., chat bot having day-long conversation.
We study the attention sampler in the streaming model, where each entry in the input matrix A, the weight vector or both A and x is updated by a data stream, and the goal is to report valid sample at all times using efficient space and update time. In particular, we consider the turnstile data streams where the entries of A Turnstile streams naturally capture settings where data must be updated, not only appended. A key application is machine unlearning, where we need to remove or negate the contribution of specific data points without retraining the entire model. In the turnstile model, the attention sampler need to incorporate both positive updates (new tokens or training examples) and negative updates (removing or editing previous tokens, retracting user-provided data, or forgetting specific training segments).
either be increased or decreased upon each streaming update.
1.1 OUR RESULTS
Inspired by softmax attention, where scores are defined by the exponential function g(2) = exp(z),
we consider the exponential sampler that reports an index with probability Σ exp([An))]]* We show that there is a quadratic lower bound on the space complexity of exponential samplers.
exp((Ar).)
Theorem 1.2. [Informal statement of Theorem 4.4 Given a matrix A E xd= and a vector
r E of where either or x, or both are changed by sequence of updates. Then any algorithm that samples an index E [nn?] with probability proportional to P; Σ" exp((An),)
expl (Ax).. must use M(n))
2

---

Published as a conference paper at ICLR 2026
bits of space, even if the sampling probabilities are allowed to be distorted by as large as ne for some constant C and even if || = O(logn). n).
This result demonstrates that the quadratic space complexity is unavoidable for exponential samplers, even when allowing a polynomial distortion n to the sampling probabilities (i.e., p; suffices to be in i (=xxex((AAz))) n (exp((())))
2- (Az])) Σز exp((Am),] ). Moreover, the hard instance is established within insertion-only streams, where updates to A and x limited to increments, and naturally generalizes turnstile streams. Our findings are consistent with offline time complexity lower bounds (Alman & Song 2023), which show that entry-wise approximations the softmax attention matrix are unattainable in sub-quadratic time when entries exceed (log r1). In fact, our results further relax this assumption, showing that quadratic space required for exponential samplers even if the entries are bounded.
These hardness results highlight the inherent difficulty in computing softmax attention scores, Con- versely, recent work has shown both theoretically and empirically that polynomial attention can effectively simulate softmax while admitting more favorable al algrrithmic structure (Kacham et al. 2023, Koohpayegani & Pirsiavash, 2024] (Saaachhanrran al. 2024] Aliakbarpour et al., 2025). In particular, the PolySketchF achieves model quality comparable to softmax attentions with efficient low-dimensional approxi- mations. Furthermore, polynomial attention schemes perform competitively in vision and Natural Language Processing (NLP) tasks, including the linear attention in Koohpayegani & Pirsiavash (2024)
(Kacham et al.) (023) demonstrates that polynomial attention
and the polynomial attention in Saratchandran al. (2024). In addition, Aliakbarroour et al. (025
showed that under certain structural properties, softmax attention can be efficiently simulated using a combination of polynomial attentions and sketching methods. Motivated by these positive results,
study the polynomial sampler that reports an index with probability Σ5-1 [(==)]]= We obtain fast
[[Am),12
and space-efficient polynomial attention samplers under various settings, summarized as follows:
Theorem 1.3. Given a matrix X E xd", a vector w E RR, and an accuracy parameter e,
then there exists algorithms that sample an index i E [n] with probability proportional ps [( at all times in the following settings:
(1 (1
E= [[An),]?
Updating and fixed x: the algorithm uses dl logn + poly (2 logn) bits of space and poly (2, update time (see Theorem 5.3
Fixed A and updating x: the algorithm uses de poly log bits of space and O(1) update time (see Theorem 5.5).
Updating both A and x: the algorithm uses d poly logg bits of space and poly logn) update time (see Theorem 5.7
In addition, for updating both A and x, any polynomial attention sampler requires MdF) space (see Theorem 6.2).
Our results establish the first algorithmic framework for sampling polynomial attention mechanisms with space complexity that is strictly sublinear in the sequence length n, bypassing the quadratic barrier in sampling and estimating softmax attention. This efficiency is particularly notable in turnstile streams, where our algorithms handle dynamic updates to both input tokens and model weights. We complement our results by showing the space lower bound when updating both A and x, which shows that our space complexity is tight up to poly-logarithmic factors.
Finally, we provide attention samplers for the tensor formulation of the attention matrix (A1 & Ag)ar, where x is fixed and one of A₁ and A₂ is updating. We note that the algorithm has faster update time compared to explicitly updating = A & Ag and applying the algorithms in Theorem 1.3
Theorem 1.4. [Informal statement of Theorem 7.6| Given matrices AI, A2 E R for A = A X
A₂ 18= xd? where one of A and A₂ is updating, and fixed gdd we sample (2, = [n]] approximately according to the E2 sampling distribution on Ax E =R= TTee algorithm uses ( space and (n) update time. Note that the trivial result takes (n2) space.
3

---

Published as a conference paper at ICLR 2026
2
RELATED WORK
In this section, we present related work in sampling and tensor sketch.
On sampling. Given a vector v E Rn and a distribution function g. recall that the classical g-sampler samples index i E [n]] with probability p. Σーー 8(0,)' A well-known example is the Lp sampling defined by g(z) |e| for p 2 O. The existence of such a L, sampler algorithms first posed as a question by Cormode et al. (2005) in 2005. Monemizadeh & Woodrufi (2010) partially answered this question in the affirmative by giving an L, sampler using polylogarithmic space for E 2], although the sampling probabilities were distorted by multiplicative (1 + E) factor and an additive poly(n]
o(1))
_1 factor. We note that the sampler is perfect if there is no e-multiplicative distortion; it is truly perfect if there is no additive distortion, i.e., the sampling probability is exact. The space requirements of the algorithm were subsequently improved (Andoni et al. 2011; Jowhari et al. (011)) and extended to other choices of index domain U and weight function W (Cohen & Geri| 2019 Mahabadi et al. 2020; 2022), , while retaining a multiplicative distortion in the sampling probability. Surprisingly, Jayaram & Woodruff (2021) showed that is possible to achieve no perfect samplers while using polylogaritmicc space, while conversely Jayaram et al. 2022) showed that truly perfect samplers would require linear space, essentially closing the line of work studying the space complexity of I,p samplers for E [1,2]. It should be noted however, achieving such guarantees (no additive distortion) in sub-polynomial update time while retaining the space guarantees remains an intriguing open question (Jayaram et al. 2022). For the other regime of p > 2, recently, Woodruff et al. (2025) complemented the results by providing efficient perfect I,p samplers for p > 2. (Swartworth al. (2025) achieved perfect samplers with polylogarithmic update time for p > 2, improving on the previous update time, For a more comprehensive background on samplers, we refer to the survey by
Cormode & Jowhari 2019))
On tensors. In the realm of tensor decomposition, the canonical polyadic (CP) decomposition, specifically the CANDECOMPIPARAFAI
method, stands out for its unique ability to break down tensors into rank-1 tensors in singular way, distinct from matrix decomposition (Harshman) 1970 Song et al. 2016). This method, having applications in computational neuroscience, data mining, and statistical learning (Wang et al., 2015), emphasizes the rigidity and uniqueness of tensor decom- position. Earlier studies (Tsourakat) aakiu 2210 Phan et al.) 2013) Choi & Vishwanathan 2014] Huang iet al. 2013 Kang et al.) [0122 Wang et al. 2014 (Bhojanapalii & Sanghavi (2015) have delved into efficient tensor decomposition methods. Subsequent works introduced methods for fast orthogonal tensor decomposition using random linear sketching techniques (Wang et al. (0155) and explored symmetric orthogonally decomposable tensors' properties, integrating spectral theory (Robeval 2016)
Robeva & Seigal 2017). Additionally, importance sampling for quicker decomposition was proposed (Song et | 2016). (Deng et al. 2023a) studies the tensor cycle low rank approximation problem.
In algebraic statistics, tensor decompositions are linked to probabilistic models, particularly in determining latent variable models' identifiability through low-rank decompositions of specific moment tensors (Allman et al. 2009a b) Rhodes & Sullivant] 2012). Kruskal's theorem (Kruskal 1977) was pivotal in ascertaining the precision of model parameter identification. However, this approach, assuming infinite sample size, does not provide the minimum sample size for learning model parameters within given error bounds. A more robust uniqueness guarantee is needed to ensure that the low-rank decomposition of an empirical moment tensor approximates that of actual moment tensor, thus offering more insight into empirical moment tensors' decomposition.
Roadmap. In Section 3, we provide some standard notations and definitions in literature. In Section 4 we study the exponential sampler. In Section 5 we study the streaming upper for the E2 sampling problem, i.e., sampling coordinates from vector Ar. where A and x may be updated across data stream. In Section 6) we present lower bounds for the same &g sampling problem. In Section 7 we discuss the tensor sampling problem.
3 PRELIMINARIES
For any positive integer n, we use [n] to denote the set {1, 2,.. .n]. We use E|-] to denote the expectation. We use Pr[-] to denote the probability. We use 1, to denote a length-n vector where all the entries are ones. Given two length-n vectors, we use (Ir to denote the inner product
4

---

Published as a conference paper at ICLR 2026
between r and y, i.e, (x. v) := Ei= Z4y; For vector I E R", we use exp(x) E "R" to denote vector that has length n and the i-th entry is xx)( For a matrix A, we use exp(A) to denote the matrix that (i. --th coordinate is exp(A..). For a vector æ, we use ||ж|| == (E== =/)1/2. We use || := Ei |rs]. We use ||rllo to denote the lo norm of æ, which is the number of nonzero entries in x. We use | to denote the Ex norm of I, which is maX |za]--
Let n1, n2, d1, d2 be positive integers. Let A E Re and B Reaxds We define the Kronecker product between matrices A and B, denoted A B E grinnxxdde as (A8 (i tia 11dd+++ is equal to A1 Bia.ja where é E [ma]].] E [d1]. d2 E 12 E [d2].
We use poly(n) to denote ne where C > is some constant. For any function f, we use Ō(f) to denote f poly(log f). For two sets A and B. we use An to denote their intersection. We use |A (AnD B] to denote the cardinality of A B. We use A U B to denote the union of A and B.
TensorSketch. We next define Sketch (Pagh 2013), which has been extensively used many sketching and optimization problems (Diao et al. 2018 Song et al. [019 DDioo et al. 2019 Ahle ctt al. 2020; Song et al., 2021 2024 2022 Zhang 2022, Song et al. 2023b). Song et al. (2022)
defined TeasorSparse by composing Sparse embedding (Nelson & Nguyen 2013 Cohen 2016 with a tensor operation (Pagh 2013).
Definition 3.1 (TensorSparse, see Definition 7.6 in Song et al. (2022)) Let h1 h2 : [m] x [s]
[m/s] be Olog 1/ independent hash functions and let 01 d2 : [n] x [s] - [=1} be
O(log 1 independent random sign functions. Then, the degree two tensor sparse trans-
form, S _" x Rn + IR' is given as:
Rr,(1.) = 3k E [s] ::::: (i (j)2))
([(hhiii,)) + h2((i, k)) mod m/s) + (k- 1/m r]
For = 1, the above definition becomes TensorSketch (Pagh 2013).
4 EXPONENTIAL SAMPLER
In this section, we define and consider exponential samplers. We then show strong space lower bounds for achieving such a data structure when the input dataset arrives in a data stream. We remark that we let be an n² x d2 matrix when we define the attention matrix in the introduction (see e.g., Definition L.1,, since A is the tensor product A₁ @ A2 of two input matrices A1, Raxd However, in the tollowing sections, for simplicity of expression, we let A be an n x d matrix, and hence the goal is to design attention samplers with space sublinear in
Let us firstly describe the offline version:
Definition 4.1 (Exponential sampler). Given matrix A Raxd and x E Rdd the goal is to sample index ~ [n)] with probability p: = (cxp(Ar), 1,,)- exp(Ar);, where 1, denotes a length-n vector, exp(Ax) E R denotes length-n vector with exp(Ax); exp((Ar):), and exp(=) is the usual exponential function.
Now, consider y - Ar E IR" where either A or x, or both are arriving in a data stream, we use the following definition for each of the various cases:
Definition 4.2. Let C > the exponential sampler outputs an index j* such that for all E [n]. Pr(j* = i) = Co (exp(M)...)
be any fixed constant and let Co [n C, ", Let y be a vector, Then
exp(x.)
We first recall the (two-party) set-disjointness communication problem Set in which two parties Alice and Bob have subsets A and B, respectively, of [n]. Note that we can equivalently view A and B as binary vectors in nediimensional space, serving as the indicator vector for whether each index i E [n] is in the player's 's input subset. The task for the players is determine whether there exists a common element in their intersection, i.e., whether there exists E [r] such that i E (A n B) or equivalently, A; B, 1. In fact, the problem promises that either the inputs are completely disjoint, AAn. B = 0 or the inputs contain only a single coordinate in their intersection. |An B 1. We recall the following standard communication complexity result of set-disjointness.
Theorem 4.3 (Kalyanauundaram & Schnitger (1992); Razborov (1992); Bar- Yossef al. 2004
Any protocol that solves the set-disjointness problem SetDisj,, with probability at least & requires (n) bits of total communication.
5

---

Published as a conference paper at ICLR 2026
We show that even sampler that relaxes the probability distribution defined in Definition 4.2 up to factor of n is infeasible in the streaming model.
Theorem 4.4. Let y R" that arrives as a data stream and let C > be a constant. Then any
algorithm that samples an index i E [n] with probability proportional to p; = (exp(a))
explys)
must use
(n) bits of space, even if the sampling probabilities are allowed to be distorted by as large as ne and even if |1y/loc = Ollogn).
Proof. Let A, B E 1)" be input vectors from the set disjointness problem, so that the goal is to determine whether there exists E [n] such that A, B; = O. Observe that Alice and Bob can multiply A and B by 100C log n for some constant C > 0. Now, note that in the disjoint case, we have 100C log n and in the non-disjoint case, have that A Bl|> 200C log
that || + B| In particular, in the non-disjoint case, there exists i E [n]] such that A, + B; = 200C' log n and for all j o i, we have that A,+ + B, I 100C log n. Hence, in the non-disjoint case, any exponential sampler will output with probability proportional to exp log n) and output * i with probability proportional to n exp(110CC log Even if the sampling probabilities are distorted by a factor of n. , any exponential sampler would output i with probability at least 1.
Thus, Alice and Bob can use such a data structure to sample an index and then check whether A; B; = 1. In particular, Alice can first create data stream encoding the vector A, run the sampling algorithm on the data stream, and then pass the state of the algorithm to Bob. Bob can then create another portion of the data stream encoding an addition of the vector B, take the state of the algorithm from Alice, run the sampling algorithm on the portion of the data stream, and query the algorithm for an index i. Bob can then take the index and pass it to Alice, and the two parties can finally communicate whether A, = B; = 1, thereby solving set-disjointness with probability at least Note that the communication of the protocol is the space used by the sampling algorithm. Therefore by Theorem 4.3 such a sampler must use M(n) bits of space.
5 lg SAMPLER UPPER BOUND WITH A AND x
In this section, we describe a standard data structure for & sampling. We start with providing the definition of & sampler as follows,
Definition 5.1. Let n denote a positive integer. Let 2 0 denote parameter. In &g sampling, we receive each coordinate of y E 12th in turnstile data stream, and the goal is to output an index / [n] at all times such that for each j [ni], Pr(I jl (1 + e)
|ys| M
+ 1/ poly(n).
We describe various instantiations of the Eg sampler for sampling entries from a vector Ar E R", based upon whether the matrix A E Raxd is updated during the data stream, whether the vector x E Id is updated during the data stream, or both.
5.1 A IS UPDATED DURING THE STREAMING AND T IS FIXED
In this section, we describe the construction of lg sampler for sampling coordinates of the vector Ax E R", in the setting where the vector z E IRd is fixed, but the entries of A E Rgad are evolving as the data stream progresses.
Definition 5.2 (Updating A and fixed 2:). In this setting, assume E IRd is fixed, we receive updates to the entries of A E Rnxd in a turnstile data stream. Then for = Ax, we want a data structure that produces the &a sampling guarantee for y.
We remark that turnstile data stream means that each update of the data stream can increase or decrease a single entry of A.
In this work, we are interested in the regime of n >> d. Then we have the following guarantee: Theorem 5.3. Suppose y = Ax, for x E R", which is fixed, and E Raxd which is defined by turnstile stream. There exists an fg-attention sampler that uses dlog + poly (t,, logo m) bits of
space and returns I [n) such that Pr[T j) = (1 + c) 1v, data structure is poly (2 logn).
llll + +1/ The update time of the

---

Published as a conference paper at ICLR 2026
Proof. Recall that existing approximate & samplers, e.g., Algorithm 2 maintains linear sketch by. where & E IR=x", for m = poly ( log n)). We have y = Ax, where R is fixed but A E Rnxd is defined through turnstile updates. Nevertheless, whenever we receive an update in A. by A, then we can compute Deze, Ar to update the sketch AAr To analyze the space complexity, observe that storing AAr requires O(m) words of space and x requires d words of space, which d log n + poly ( log n)) bits of space in total. Moreover, we need to update all the m entries in 4 Ax upon each update, using O(m) poly ( log time.
maintain the state of @Ar.. In particular,
5.2 x IS UPDATED DURING THE STREAMING AND A FIXED
We next consider the setting where the vector æ E Rd is updated as the data stream progresses, but the entries of A E guxd are fixed.
Definition 5.4 (Fixed A and updating 2). We assume A 1xd Rd in a turnstile data stream. Then for Az, we want a data structure that produces the &2 sampling guarantee for y.
x is fixed, we receive updates to
We have the following algorithmic guarantees for this setting:
Theorem 5.5. Suppose y for A E _gaxd, which is fixed, and x E IR", which is defined by a turnstile stream. There an Ez-attention sampler that uses poly (2. log bits of space and
returns I E [n]] such that Pr[I- = jl = (1+c) structure is (1).
1a,12 + 1/lo)((n)) The update time of the data
lalll
Proof. Again recall that existing approximate & samplers, e.g., Algorithm maintains a linear sketch by. where & E Rm for m poly (2. log n2). Since y = Ar, but A E Ruxd is too large to store, while In is defined through turnstile updates, we can instead maintain the sketch 4A and the vector x and compute Arr by after the stream concludes. Note that storing & A requires O (mmd) words of space and x requires d words of space, which is poly (t log n) bits of space in total. Moreover, each update to x changes single entry, so the update time is O(1).
5.3 BOTH A AND E ARE UPDATED DURING THE STREAMING
Finally, we consider the setting where both the vector z E Rd and the entries of A E Raxd can be changed by updates from the data stream.
Definition 5.6 (Updating A and updating x). In this setting, we receive updates to both A E Raad and Rd in a turnstile data stream. Then for Az, we want data structure that provides the fg sampling guarantee for y.
We have the following guarantees:
Lemma 5.7 (Upper Bound). Suppose y = Ax. for Rxd and x E Rdd, which are each defined in stream through turnstile updates. There exists an f- 2-attention sumpler that uses d poly (,. n) bits of space and returns I E [ni] such that Pr[/ j] (1 ee is poly log..
1 + 1/ poly(n). The update time
T
Proof. As before, recall that existing approximate & samplers, e.g., Algorithm maintains linear sketch Py, where E mm for m = poly (1. lo.. Since = Az, but now both E gaa can instead maintain the sketch 4 and the
and x E I are defined through turnstile updates, vector x and compute Ax = by after the stream concludes. Observe that maintaining A requires ((m)) words of space and requires d words of space, which is poly (1 looo n) bits of space in total. Each update to A can change all m entries of in a single column of A, while each update to x changes single entry. Hence, the update time is poly (:) logn).
7

---

Published as a conference paper at ICLR 2026
6 l SAMPLER LOWER BOUND (WITH A AND x)
In this section, we give lower bounds for l2 sampling from a vector = x when either A or are updated in a data stream. We show that in any of these cases, the general problem substantially more difficult than the previous case where = 1.
We first recall the Index problem for one-way communication. In the INDEX, problem, Alice receives a vector E {0, 1)"h and Bob receives coordinate i E [n.. The goal is for Bob to compute with probability at least 3. given some message II from Alice. We recall the following communication complexity lower bounds for Index.
Theorem 6.1 Kremer et al. (1999)). Any protocol that solves INDEX, with probability at least 2
requires (nn) bits of communication.
Lemma 6.2 (Lower Bound). Any streaming algorithm that solves problem defined Definition 5.6 will require (id) space.
Proof. Suppose Alice receives a vector u E {0, 13d. Then Alice creates the diagonal matrix M e {0, 1) 1]dxd so that the j-th diagonal entry of A is v/. for all j [nt]. Finally, Alice creates A e R(d+1)xd by appending the row consisting of 10th in all of its d entries to M. Suppose Bob receives the coordinate i E [d] and wants to determine v; Then Bob can set x to be the elementary vector e E Rd, which has in its i-th coordinate and zeros elsewhere. Observe that by construction, Ar is the i-th column of A. If u; 1, then the i-th column of A consists of a 1 in the i-th entry, Toio in the (d + 1)-st entry, and zeros elsewhere. Hence, a sampler with the desired properties will output i with probability at least 5. Similarly, if v; = O, then the i-th column of A consists of To in the (d + )-tt entry and zeros elsewhere. Thus, the sampler with the desired properties will output + with probability 1. Bob can therefore distinguish between these two cases with probability at least 3 4' thereby solving INDEX, with probability at least Therefore, by Theorem 6.1 such sampler must use at least (d) space.
1
In fact, we show that if y A where A E R so that A E R=nxx" xn" denotes the p-wise self-tensor and x E Tp="" then actually L2 sampling from y uses (mn) bits of space.
Lemma 6.3. Let A E Raxa and A E R="xx" denote the p-wise self-tensor. Let y= A so that x E gn. Then even if all the entries of arrive in a data stream stream followed by all the entries of A. Le sampling from y requires Q(n) bits of space.
Proof. Let S E {0, 1} be an instance of INDEX,, Suppose Alice creates the diagonal matrix A with exactly S being the entries across its diagonal, i.e., A1,1 Si..... .. An, Sn, Bob has index i E [m]. and sets the vector to be the elementary vector e,. where construction Az is the all zeros vector if S; = and otherwise there is a nonzero entry, which allows Alice and Bob to solve INDEX,,. Hence, L2 sampling from y requires Q(n) bits of space.
i 12--1 Then by
THE TENSOR VERSION PROBLEM
In this section, we further consider sampling from a tensor product. We provide the tensor notations and objects.
Definition 7.1. Let A₁ Raxd let A gaxd we define A Ai Ag E 2x
Let E d
Let A; R denote the i-th block of A.
Definition 7.2 (Fixed x, streaming sampler for one A and As is updating.). We assume Rdd is fixed. We assume that (1) one of A₁ and A₂ is updating, (2) one of A1 and Ag is fixed. Let Az, we want E sampling guarantee for sampling one coordinate in yı " for all E [n²].
To motive this model, recall that the tensor product (Ai @ A2) equals the linear cross-altention matrix QK = A, W W AJ, where Q = A₁ Wo is the query matrix and K = Wr is the key matrix. Our model addresses practical scenario involving real-time contextual processing with static reference dataset. In this setting, the key matrix K is precomputed by the language model, representing static dataset such embeddings of knowledge base, user profiles, multimedia
8

---

Published as a conference paper at ICLR 2026
features. Then, the entries of input matrix A₁ is updated by turnstile data stream, which changes the entries in the query matrix Q implicitly, representing real-time dynamic data queries. In particular, model is suitable for uugo-regressive Transformers, where the key matrix K is given and the rows of input matrix A arrives one-by-one as a data stream. Thus, our attention sampler recovers the important coordinates in attention computation in auto-regressive Transformers.
We use the following formulation of Nisan's 's pseudorandom generator to derandomize our algorithm.
Theorem 7.3 (Nisan's PRG, Nisan (1992). Suppose A is an algorithm that requires 5 = 2l n) bits of space and R random bits. Then there exists pseudorandom generator for A that succeeds with probability 1/poly(n) (n) and uses O(S log Rt) bits of space.
Algorithm Algorithm for sampling based on S(1 2 x22
Suppose use ((n)) space to store A and A2 (Avoid n² time/space)
2: Suppose we receive an update E [2]. E [m].] E [d], A
3: Suppose we have hash function g to access uniform number
4: if q then
5: p 3 g(i(n - 1) + I, .............................. in)) (p E Rn)
6: y + ()= (A2)as)/p { is decided by k1,
7: else
8: 1/2 y2 + 22e,A ( is decided by h2, 02)
9: end if
In the following Lemma, we state a streaming algorithm to solve tensor related sampling problem. We consider the situation that one of A, and Ag is fixed, and the other one is updated streaming fashion. We show the following estimation guarantees using the standard CountSketch analysis,
c.f., Charikar et al. (2004); Jowhari et al. (20TT). We defer the proof to appendix C
Lemma 7.4 (Tensor f2 Tail Estimation). Let y = (A1 A2)x R²² Let only of A and A2 be updated in streaming. Let w Jun for constant u, E [0, 1] generated uniformly at random.
There is an algorithm that that uses ((nd) + poly (2, space. uses (nn) update time, and estimates each element of w up to additive error c- || 12/1,, where denotes the tail vector of w without the largest 2 entries in magnitude. Specifically, for all E [n²]], we have (0 wil S c ||
We state the following lemma as a structural property that will allow to achieve our tensor product sampler. We remark that the proof is simple adaptation of existing proofs for approximate Ép sampling (Jowhari et al. 2011). Thus we defer the proof to Appendix
Lemma 7.5. Let y = (A1 @ A2)æ R²² and let w E RTn so that w, = Lh U, [0, generated uniformly at random. Let denote the tail vector of w without the largest A entries in magnitude. Let Z be 2-upproximation to ||=||2 and Y be 2-approximation to ||y/]|, then have Pr|Z V(Clog log n)/c 8 s O(c) poly(n)
Juc for a constant
Finally, we describe the guarantees of our tensor-based sampler, deferring the proof to Appendix D
Theorem 7.6. Let y (A, Az)æ g=² and let w R"² so that for each E [n²], w; vuū for constant u, E [0,1] generated uniformly at random. Let z denote the tail vector of w without the largest 3 entries magnitude. Suppose there exists:
1. An algorithm A₁ that provides a 2-approximation to llvlla with probability 1
n
2. An algorithm A2 that provides a 2-approximation to ||z||2 with probability - + 3. An algorithm Ag that estimates each element of w up to additive error e || 10m, wal / e ||æ]|z,for for all i [n?]]
Then there exists data structure that uses poly ( logn) bits of space, Onn) update time, and outputs each index i with probability = + c)
1/2 + poly!]j
M

---

Published as a conference paper at ICLR 2026
We remark that the algorithms A1 and Ag in the context of Theorem 7.6 can be achieved using the standard AMS & norm estimator (Alon et al. 1999). Moreover, algorithm Ag in the context of Theorem 7.6 can be achieved using the standard CountSketch algorithm (Charikar et al. 2004).
CONCLUSIONS
To achieve efficient attention mechanisms, we introduce the attention sampler and study its behavior in the streaming model. We established efficient polynomial samplers under various streaming settings, when the input matrix, the weight vector, both evolve dynamically, and we complement the results by proving space lower bounds. Our sampling framework recovers the important coordinates in attention matrix, offering a foundation for efficient simulations of large-scale attention schemes, which is central to modern machine learning and LLMs.
For future directions, from theoretical perspective, given the (?()) lower bound on exponential samplers in general circumstances, it would be valuable to explore whether space under certain assumptions, e.g., restricting the entries in the attention matrix to olog n.). From practical perspective, it would be beneficial to evaluate sampler's performance in real-world Transformer applications, especially in sparse attention schemes and streaming attention schemes.
achieve o(n)
ACKNOWLEDGMENTS
Shenghao Xie is supported in part by NSF CCF-2335411. Samson Zhou is supported in part by NSF CCF-2335411. Samson Zhou gratefully acknowledges funding provided by the Oak Ridge Associated Universities (ORAU) Ralph E. Powe Junior Faculty Enhancement Award.
ETHIC STATEMENT
This paper does not involve human subjects, personally identifiable data, sensitive applications. do not foresee direct ethical risks. follow the ICLR Code of Ethics and affirm that all aspects of this research comply with the principles of fairness, transparency, and integrity.
REPRODUCIBILITY STATEMENT
We ensure reproducibility of our theoretical results by including all formal assumptions, definitions, and complete proofs in the appendix. The main text states each theorem clearly and refers to the detailed proofs. No external data or software is required.
REFERENCES
Marah Abdin, Sam Ade Jacobs, Ammar Ahmad Awan, Jyoti Aneja, Ahmed Awadallah, Hany Awadalla, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Harkirat S. Behl, Alon Benhaim, Misha Bilenko, Johan Bjorck, Sébastien Bubeck, Martin Cai, Caio César Teodoro Mendes, Weizhu Chen, Vishrav Chaudhary, Parul Chopra, Allie Del Giorno, Gustavo de Rosa, Matthew Dixon, Ronen Eldan, Dan Iter, Amit Garg, Abhishek Goswami, Suriya Gunasekar, Emman Haider, Junheng Hao, Russell Hewett, Jamie Huynh, Mojan Javaheripi, Xin Jin, Piero Kauffmann, Nikos Karampatziakis, Dongwoo Kim, Mahoud Khademi, Lev Kurilenko, James R. Lee, Yin Tat Lee, Yuanzhi Li, Chen Liang, Weishung Liu, Eric Lin, Zeqi Lin, Piyush Madan. Arindam Mitra, Hardik Modi, Anh Nguyen, Brandon Norick, Barun Patra, Daniel perez-BBecker Thomas Portet, Reid Pryzant, Heyang Qin, Marko Radmilac, Corby Rosset, Sambudha Roy, Olatunji Ruwase, Olli Saarikivi, Amin Saied, Adil Salim, Michael Santacroce, Shital Shah, Ning Shang. Hiteshi Sharma, Xia Song, Masahiro Tanaka, Xin Wang, Rachel Ward, Guanhua Wang. Philipp Witte, Michael Wyatt, Can Xu, Jiahang Xu, Sonali Yadav, Fan Yang, Ziyi Yang. Donghan Yu, Chengruidong Zhang, Cyril Zhang, Jianwen Zhang, Lyna Zhang, Yi Zhang, Yue Zhang, Yunan Zhang, and Xiren Zhou. Phi-3 technical report: A highly capable language model locally your phone. CoRR, Abb/24404.14211 2024. doi: 10.48550/ARXIV.2400 14219. URL http:tt::: /ww.ooo..... 10. 40.48550/arx1t 2404. 14219
10

---

Published as a conference paper at ICLR 2026
Ankit Aggarwal, Amit Deshpande, and Ravi Kannan. Adaptive sampling for k-means clustering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX and 13th International Workshop. RANDOM. Proceedings, pp. 15-28, 2009.
Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh. Oblivious sketching of high-degree polynomial kernels. In Pro- ceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 141-160. SIAM, 2020.
Maryam Aliakbarpour, Vladimir Braverman, Junze Yin, and Haochen Zhang. Support basis: Fast attention beyond bounded entries. CoRR, 10.01144, 2025.
Elizaheth S. Allman, Catherine Matias, and John A. Rhodes. Identifiability of parameters in latent structure models with many observed variables. The Anmals of Statistics, 37(6A), dec 2009a. doi: 10.1214/09-a0s68, URL httph:
wwg/10../.0. 121452FCS aos689
Elizabeth S. Allman, Sonja Petrović, John A. Rhodes, and Seth Sullivant. Identifiability of 2-tree mixtures for group-based models, 2009b. URL htLL::ttt://axxv.oorr org/ abs/ 0909. 1854
Josh Alman and Zhao Song. Fast attention requires bounded entries. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurlPS, 2023.
Josh Alman and Zhao Song. How to capture higher-order correlations? generalizing matrix soft- max attention to kronecker computation. In The Twelfth International Conference on Learning Representations, ICLR, 2024a.
Josh Alman and Zhao Song. The fine the-grained complexity of gradient computation for training large language models. In The eighth Annual Conference on Neural Information Processing Systems, 2024b. httthhhss//:/eeeee
net wtret/fooummiii http://oormmmmuuuttooa WWwwoo
Josh Alman and Zhao Song. Fast rope attention: Combining the polynomial method and fast fourier transform. arXiv preprini arXiv:2505.//892, 2025a.
Josh Alman and Zhao Song. Only large weights (and not skip connections) can prevent the perils of rank collapse. arXiv preprint arXiv:2505./6284 2025b.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999.
Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via precision sampling, In IEEE 52nd Annual Symposium Foundations of Computer Science, FOCS, pp. 363-372, 2011.
Pranjal Awasthi and Anupam Gupta. Improving length-genneralzzaton in transformers via task hinting. arXiv preprint arXiv:2310.0072. 2023.
Ziv Bar- Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004.
Srinadh Bhojanapalli and Sujay Sanghavi. A new sampling technique for tensors. In arXiv preprint. https::/srriv..rr////e http://pdd1111...000 05023 2015.
Jan van den Brand, Zhao Song, and Tianyi Zhou. Algorithm and hardness for dynamic attention maintenance in large language models. In Forty-first International Conference on Machine Learning, ICML. OpenReview.net. 2024.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NewrIPS, pp. 1877-1901, 2020.

---

Published as a conference paper at ICLR 2026
Moses Charikar, Kevin C. Chen, and Martin Parach-Colton Finding frequent items in data streams. Theor: Comput. Sci., 312(1):3-15, 2004.
Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré. Scatterbrain: Unifying sparse and low-rank attention. Advances in Neural Information Processing Systems (NeurIPS), 34: 17413-17426, 2021.
Beidi Chen, Tri Dao, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, and Christopher Re. Pixelated butterlly: Simple and efficient sparse training for neural network models. In International Conference on Learning Representations, ICLR, 2022.
Rewon Child, Scott Gray, Alec Radford, and lya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: 10509, 2019.
Joon Hee Choi and S. Vishwanathan. Dfacto: Distributed factorization of tensors. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems, NeurlPS, pp. 1296- 2014.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi. Sasha Tsyyashchenko, Joshua Maynez, Abhishck Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Seiir-Hellsteen. Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language modeling with pathways. Mach. Learn. Res., 24:240: 1-24::0:122::11 13, 2023.
Edith Cohen and Ofir Geri. Sampling sketches for concave sublinear functions of frequencies. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems, NeurlPS, pp. 1361-1371, 2019.
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, and Mikkel Thorup. Efficient stream sampling for variance-optimal estimation of subset sums. SIAM J. Comput., 4065):1402-1431 2011.
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, and Mikkel Thorup. Algorithms and estimators for summarization unaggregated data streams. J. Comput. Syst. Sci., 10(7):211411244, 2014.
Michael B. Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, USA, January 10-12, 2016, pp. 278-287, 2016
Michael Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In Proceedings of the 51 Anmual ACM Symposium on Theory of Computing (STOC). bttps: : / /awxiv.vvvv.. wwtp:////////ooeeeeeeeeeeeeeeeoo
07896 pdf, 2019.
Graham Cormode and Hossein Jowhari. 1p samplers and their applications: survey. ACM Comput. Surv, (2(())16:11166::: 2019.
Graham Cormode, S. Muthukrishnan, and Irina Rozenbaum. Summarizing and mining inverse distributions on data streams via dynamic inverse sampling. In Proceedings of the 31st International Conference Very Large Data Bases, pp. 25-36. ACM, 2005.
Giannis Daras, Nikita Kitaev, Augustus Odena, and Alexandros G Dimakis. Smyrf-efficient attention using asymmetric clustering. Advances in Neural Information Processing Systems (NeurIPS), 33: 6476-6489, 2020.
12

---

Published as a conference paper at ICLR 2026
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. arXiv preprint arXiv.1807.038/1 2018.
Yichuan Deng, Wenyu Jin, Zhao Song, Xiaorui Sun, and Omri Weinstein, Dynamic kernel sparsifiers. arXiv preprint arXiv:2211.44000 2022a.
Yichuan Deng, Zhao Song. Omri Weinstein, and Ruizhe Zhang. Fast distance oracles for any symmetric norm. In Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurlPS, 2022b.
Yichuan Deng, Yeqi Gao, and Zhao Song. Solving tensor low cycle rank approximation. In IEEE International Conference on Big Data, BigData 2023, Sorrento, Italy, December 15-18, 2023, pp. 6-16. IEFE, 2023a.
Yichuan Deng, Zhihang Li, and Zhao Song. Attention scheme inspired softmax regression. arXiv preprint ar arXiv:2304. 1043144.01,, 2023b.
Yichuan Deng, Sridhar Mahadevan, and Zhao Song. Randomized and deterministic attention sparsifi- cation algorithms for over-parametterized feature dimension. arxiv preprint: arxiv 2304.03426, 2023c.
Yichuan Deng, Zhao Song, and Shenghao Xie. Convergence of two-layer regression with nonlinear units. arXiv preprint arXiv:2308.0883: 2023d.
Yichuan Deng, Zhihang Li, Sridhar Mahadevan, and Zhao Song. Zero-th order algorithm for softmax attention optimization. In /EEE International Conference on Big Data, BigData 2024, Washington, DC, USA, December 15-18, 2024, pp. 24-33. IEEE, 2024a.
Yichuan Deng, Zhao Song, and Chiwun Yang. Attention is naturally sparse with gaussian distributed input. arXiv preprint arXivv2404.02699, 2024b.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT, pp. 11166. Association for Computational Linguisties, 2019.
Huaian Diao, Zhao Song, Wen Sun, and David P. Woodruff. Sketching for kronecker product regression and p-splines. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, volume 84 of Proceedings of Machine Learning Research, pp. 1299-1308. PMLR, 2018.
Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, and David Woodruff. Optimal sketching for kronecker product regression and low rank approximation. Advances in neural information processing systems, 32, 2019.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurélien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Rozière, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius, Daniel Song, Danielle Pintz, Danny Livshits, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Garcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Graeme Nail, Grégoire Mialon, Guan Pang. Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo Touvron, Iliyan Zarov, Imanol Arrieta Ibarra, Isabel M. Kloumann, Ishan Misra, Ivan Evtimov, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Mahadeokar, Jeet Shah, Jeimer van der Linde, Jennifer Billock, Jenny Hong, Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang. Jiecao Yu, Joanna Bitton, Joe Spisak. Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Vasuden Alwala, Kartikeya Upasani, Kate Plawiak, Ke Li, Kenneth Heafield, Kevin Stone, and et al. The llama 3 herd of models. CoRR, abs/2407.2178.. 2024. URL //ooi org/ 10. 48550/ arxiv. 2407. 21783
13

---

Published as a conference paper at ICLR 2026
Benjamin L. Edelman, Surbhi Goel, Sham M. Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning, ICML, volume 162 of Proceedings of Machine Learning Research, pp. 5793-5831. PMLR, 2022.
Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. Fast monte-carlo algorithms for finding low-rank approximations. J. ACM, 1225:1102-, 2004.
Yao Fu. Challenges in deploying long-context transformers: theoretical peak performance analysis.
CoRR, abs/22405008944 2024. doi: 10.48550ARXIV.2405..00 088944 URL httpht:///oooorre 10. N0.48550/arxiv/ 2405. 08944
Yeqi Gao, Lianke Qin, Zhao Song, and Yitan Wang. A sublinear adversarial training algorithm. arXiv preprint arXiv:2208.05399) 2022.
Yeqi Gao, Sridhar Mahadevan, and Zhao Song. An over-parameterized exponential regression. arXiv preprint (rxXiv:2303.6654 2023.
Yeqi Gao, Zhao Song, and Junze Yin. An iterative algorithm for rescaled hyperbolic functions
regression. In International Conference on Artificial Intelligence and Statistics, AISTATS, volume 258 of Proceedings of Machine Learning Research, pp. 2548 2548-2556. PMLR, 2025.
Rainer Gemulla, Wolfgang Lehner, and Peter Haas. Maintaining bounded-size sample synopses of evolving datasets. VLDB J., 17(2):173-202, 2008.
Yuzhou Gu and Zhao Song. A faster small treewidth sdp solver. arXiv preprint arXiv:2211.06033 2022.
Yuzhou Gu, Zhao Song, Junze Yin, and Lichen Zhang. Low rank matrix completion via robust alternating minimization in nearly linear time. In The Twelfth International Conference on Learning Representations, ICLR. OpenReview.net, 2024.
Peter J. Haas. Data-stream sampling: Basic techniques and results. Data Stream Management Processing High-Speed Data Streams, Data-Centric Systems and Applications, pp. 13-44. Springer, 2016.
Peter J. Haas and Arun N. Swami. Sequential sampling procedures for query size estimation. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 341-350, 1992.
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David Woodruff, and Amir Zandieh. Hyperattention: Long-context attention in near-linear time. In The Twelfth International Conference on Learning Representations, ICLR. OpenReview.net, 2024.
Insu Han, Michael Kapralov, Ekaterina Kochetkova, Kshiteej Sheth, and Amir Zandich. Balancekv: KV cache compression through discrepancy theory. CORR, abs/2502.07861, 2025.
Themistoklis Haris and Krzysztof Onak. Compression barriers for autoregressive transformers.
CORR, abs/2502.15955, 2025. doi: 1048500AR33122500.5555. Utl.hhttpps///oi..co
10. 0t.48550/axiv..2022 15955
Richard A Harshman. Foundations of the parafac procedure: Models and conditions for an" explana-
tory" multimodal factor analysis. 1970.
Furong Huang, Niranjan U. N. Mohammad Umar Hakeem, Prateck Verma, and Animashree Anand- kumar. Fast detection of overlapping communities via online tensor methods on gpus. CORR, abs/1309.0786 037799777....0 2013.
Ling Huang, XuanLong Nguyen, Minos N. Garofalakis, Joseph M. Hellerstein, Michael Jordan, Anthony D. Joseph, and Nina Taft. caammunication-effiiieeee online detection of network-widh anomalies. In INFOCOM. 26th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, pp. 142, 2007.
Adobe Inc. Adobe firefly. http:///ww..aaalcccocommmeeeeeee
2023.
14

---

Published as a conference paper at ICLR 2026
Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, and Alireza Rezaci. Composable core-sets for determinant maximization problems via spectral spanners. In Proceedings of the 2020 ACM-SIAM Symposium Discrete Algorithms, SODA, pp. 1675-1694, 2020.
Rajesh Jayaram and David P. Woodruff. Perfect I sampling in a data stream. SIAM Comput,, 50 (2):382-439, 2021.
Rajesh Jayaram, David P. Woodruff, and Samson Zhou. Truly perfect samplers for data streams and sliding windows. In PODS '22: International Conference on Management of Data, pp. 29-40, 2022.
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. Faster dynamic matrix inverse for faster Ips. arXiv preprint arXiv:2004.07470, 2021.
Hossein Jowhari, Mert Saglam, and Gábor Tardos. Tight bounds for Ip samplers, finding duplicates in streams, and related problems. In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGARR Symposium on Principles of Database Systems, PODS, pp. 49-58, 2011.
Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. Polysketchformer: Fast transformers via sketches for polynomial kernels. arXiv preprint arXiv:2310.01655,, 2023.
Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Discret. Math., 5(4):545-557, 1992.
U. Kang, Evangelos E. Papalexakis, Abhay Harpale, and Christos Faloutsos. Gigatensor: scaling tensor analysis up by 100 times algorithms and discoveries. In KDD, pp. 316-324, 2012.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mnns: Fast autoregressive transformers with linear attention. In International conference on machine learning, pp. 5156-5165. PMLR, 2020.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv: 2001.04451, 2020.
Soroush Abbasi Koohpaycgani and Hamed Pirsiavash. Sima: Simple softmax-fret free attention for vision transformers. In IEEE/CVF Winter Conference Applications of Computer Vision, WACV, pp. 2595-2605. IEBE, 2024.
Ilnn Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. Comput. Complex. 8(1):21-4)) 1999.
Joseph B. Kruskal. Three-way arrays: rank and uniqueness trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra and its Applications, 18(2):95- 138, 1977. ISSN 0024-3795. doi: http:://oo.oooo//..0000000022010 //www. scw.ncediiicc.ccc.co rect wtt.eeccoocsssieeeeeee http://///.eeee/errraaaa////////
URL https
Xunhao Lai, Jianqiao Lu, Yao Luo, Yiyuan Ma, and Xun Zhou. Flexprefill: context-aware sparse attention mechanism for efficient long-sequence inference. In The Thirteenth International Conference on Learning Representations. OpenReview.net, 2025.
Yin Tat Lce, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. COLT, hitps: arxiv. wttp://wwggg/p///....... 04447. 2019.
Zhihang Li, Zhao Song, and Tianyi Zhou. Solving regularized exp, cosh and sinh regression problems. arXiv preprint orXiv:2303. /5755, 2023.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining 2019.
approach. arXiv preprint
Sepideh Mahabadi, Piotr Indyk, Shayan Oveis Gharan, and Alireza Rezaei. Composable core-sets for determinant maximization: A simple netr-optimal algorithm. In Proceedings of the 36th International Conference Machine Learning, ICMI. 2019, volume 97, pp. 4254 4263, 2019.
15

---

Published as a conference paper at ICLR 2026
Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, and Samson Zhou. Non-adaptive adaptive sampling on turnstile streams. In Proceedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1251-1264, 2020.
Sepideh Mahabadi, David P. Woodruff, and Samson Zhou, Adaptive sketches for robust regression with importance sampling. In Approximation, Rundomization, and Combinatorial Optimization. Algorithuss and Techniques, APPROX/RANDOM, pp. 31:1-31:21, 2022.
Arvind V. Mahankali, David P. Woodruff, and Ziyu Zhang. Near-linear time and fixed-parameter tractable algorithms for tensor decompositions. In 15th Innovations in Theoretical Computer Science Conference, ITCS, volume 287 of LIPlcs, pp. 79:1-79:23. Schloss Dagstuhl Leibnii- Zentrum für Informatik, 2024.
Jianning Mai, Chen-Nee Chuah, Ashwin Sridharan, Tao Ye, and Hui Zang. sampled data sufficient for anomaly detection? In Proceedings of the 6th ACM SIGCOMM Internet Measurement Conference, IMC, pp. 165-176, 2006.
James Manyika and Sissie Hsiao. An overview of bard: an early experiment with generative ai. AL. Google Static Documents, 2, 2023.
Gary Marcus, Ernest Davis, and Scott Aaronson. A very preliminary analysis of dall-e 2. arXiv preprint arXiv:2204. 3807, 2022.
Morteza Monemizadeh and David Woodruff. 1-pass relative-error ly-sampling with applications. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1143-1160. SIAM, 2010.
Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundatiosss of computer science, pp. 117-126. IEEE, 2013.
Noam Nisan. Pseudorandom generators for space-bounded computation. Comb., 12(4))449 461, 1992.
Rasmus Pagh. Compressed matrix multiplication. ACM Transactions on Computation Theory (TOCT), 5(3):1117, 2013. 2013.
Anh-Huy Phan, Petr Tichavsky, and Andrzej Cichocki. Low complexity damped gauss-newton algorithms for candecomp/purafac.. SIAM Journal on Matrix Analysis and Applications, 34(1): 126-147, 2013.
Lianke Qin, Rajesh Jayaram, Elaine Shi, Zhao Song, Danyang Zhuo, and Shumo Chu. Adore: Differentially oblivious relational database operators. VLDB, 2022a.
Lianke Qin, Aravind Reddy, Zhao Song, Zhaozhuo Xu, and Danyang Zhuo Adaptive and dynamic multi-resolution hashing for pairwise summations. In IEEE International Conference on Big Data, Big Data, pp. 115-120. IEEE, 2022b.
Lianke Qin. Zhao Song, and Yitan Wang. Fast submodular function maximization. arXiv preprint wwxi::2305.08367 2023a.
Lianke Qin, Zhao Song, Lichen Zhang, and Danyang Zhuo An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization. In International Conference on Artificial Intelligence and Statistics, pp. 101-156. PMLR, 2023b.
Lianke Qin, Zhao Song, and Ruizhe Zhang. A general algorithm for solving rank-one matrix sensing. In International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 757-765. PMLR, 2024.
Alexander A. Razborov. On the distributional complexity of disjointness. Theor Comput. Sci., 106 (2):385-390, 1992.
Aravind Reddy, Zhao Song. and Lichen Zhang. Dynamic tensor product regression. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS, 2022.
16

---

Published as a conference paper at ICLR 2026
Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy P. Lillicrap. Jean- Baptiste Alayrac, Radu Soricut, Angeliki Lazaridou. Orhan Firat, Julian Schrittwieser, loannis Antonoglou, Rohan Anil, Sebastian Borgeaud, Andrew M. Dai, Katie Millican, Ethan Dyer, Mia Glaese, Thibault Sottiaux, Benjamin Lee, Fabio Viola, Malcolm Reynolds, Yuanzhong Xu, James Molloy, Jilin Chen, Michael Isard, Paul Barham, Tom Hennigan, Ross Mcllroy, Melvin Johnson, Johan Schalkwyk, Eli Collins, Eliza Rutherford, Erica Moreira, Kareem Ayoub, Megha Goel, Clemens Meyer, Gregory Thornton, Zhen Yang, Henryk Michalewski. Zaheer Abbas, Nathan Schucher, Ankesh Anand, Richard Ives, James Keeling, Karel Lenc, Salem Haykal, Siamak Shakeri, Pranav Shyam, Aakanksha Chowdhery, Roman Ring, Stephen Spencer, Eren Sezener, and et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. CoRR, /tbb///44300550000 2024, doi: 10448500ARXX..440005555 0553000 URL https 10. 48550/ 240.
John A Rhodes and Seth Sullivant. Identifiabiliiyy of large phylogenetic mixture models. Bulletin of mathematical biology, 74:212-231, 2012.
Elina Robeva. Orthogonal decomposition of symmetric tensors. SIAM Journal on Matrix Analysis and Applications, 37(1))86-100) 2016.
Elina Robeva and Anna Seigal. Singular vectors of orthogonally decomposable tensors, Linear and Multilinear Algebra, (5(12):2457-2471, 2017.
Hemanth Saratchandran, Jianqiao Zheng, Yiping Ji, Wenbo Zhang, and Simon Lucey. Rethinking softmax: Self-attention with polynomial activations. CoRR, abs/2410. 18613, 2024.
Sambal Shikhar, Mohammed Irfan Kurpath, Sahal Shaji Mullappilly. Jean Lahoud, Fahad Shahbaz Khan, Rao Muhammad Anwer, Salman H. Khan, and Hisham Cholakkal. Llmvox: Autoregressive streaming text-to-speech model for any LLM. In Findings of the Association for Computational Linguistics, ACI. pp. 20481-22 12499. Association for Computational Linguistics, 2025.
Charlie Snell, Ruiqi Zhong, Dan Klein, and Jacob Steinhardt. Approximating how single head attention learns. arXiv preprint arXhv:2103.07601 2021.
Zhao Song, David P. Woodruff, and Huan Zhang. Sublinear time orthogonal tensor decomposition. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems (NIPS) 2016, December 5-10, 2016, Barcelona, Spain, pp. 793-801, 2016.
Zhao Song, David P. Woodruff, and Peilin Zhong. Relative error tensor low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2772-2789. SIAM, 2019.
Zhao Song, David Woodruff, Zheng Yu, and Lichen Zhang. Fast sketching of polynomial kernels of polynomial degree. In International Conference Machine Learning, pp. 9812-9822, PMLR, 2021.
Zhao Song, Zhaozhuo Xu, and Lichen Zhang, Speeding sparsification using inner product search data structures. arXiv preprint 2tt.::222440020999 2022.
Zhao Song, Xin Yang, Yuanyuan Yang, and Lichen Zhang. Sketching meets differential privacy: Fast algorithm for dynamic kronecker projection maintenance. In International Conference on Machine Learning, ICML, volume 202 of Proceedings of Machine Learning Research, pp. 32418-32462. PMLR, 2023a.
Zhao Song, Mingquan Ye, and Lichen Zhang. Streaming semidefinite programs: o(yR) passes, small space and fast runtime. Manuscript, 2023b.
Zhao Song, Lichen Zhang, and Ruizhe Zhang. Training multi-layer over-parametrized neural network in subquadratic time. 15th Innovations in Theoretical Computer Science Conference, ITCS, volume 287 of L.Plcs, pp.
Schloss Dagstuhl- Leibniz-7Zntrrum für Informatik, 2024.
Foteini Strati, Sara McAllister, Amar Phanishayee, Jakub Tarnawski, and Ana Klimovic. Déjävu: Ky-cache streaming for fast, fault-tolerant generative LLM serving. In Forty-first International Conference Machine Learning, ICML. OpenReview.net, 2024.
17

---

Published as a conference paper at ICLR 2026
William Swartworth, David P. Woodruff, and Samson Zhou. Perfect ip sampling with polylogarithmic update time. In IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), 2025.
Marina Thottan, Guanglei Liu, and Chuanyi Ji. Anomaly detection approaches for communication networks. In Algorithms for Next Generation Networks, Computer Communications and Networks, pp. 239-261. Springer, 2010.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro. Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 2023a
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprini arXiv:2307.092888 2023b.
Charalampos E. Tsourakakis. MACH: fast randomized tensor decompositions, In SDM, pp. 689-700, 2010.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Jeffrey Scott Vitter. Random sampling with a reservoir. ACM Trans. Math. Softw., 11(1):37-57, 1985.
James Vuckovic, Aristide Baratin, and Remi Tachet des Combes. A mathematical theory of attention. arXiv preprint arXiv:2007.02876 2020.
Chi Wang, Xueqing Liu, Yanglei Song, and Jiawei Han. Scalable moment-based inference for latent dirichlet allocation. In ECML-PKDD, pp. 290-305, 2014.
Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04766 2020.
Yining Wang, Hsiao-Yo Tung, Alexander J Smola, and Anima Anandkumar. Fast and guaranteed tensor decomposition via sketching. In Advances in Neural Information Processing Systems (NIPS), pp. 991-9999999.. https://azzee wwg. hwtp:g/pp//1500..0 04448 2015.
Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: case study on
approximating turing machines with transformers. arXiv preprint 13Xiv:2107.13163, 2021.
David P. Woodruff, Shenghao Xie, and Samson Zhou. Perfect sampling in turnstile streams beyond small moments. Proc. ACM Manag. Data, 1(6)::06:1-1066 2025.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Representations, ICLR. OpenReview.net, 2024.
Guangxuan Xiao, Jiaming Tang, Jingwei Zuo, Junxian Guo, Shang Yang, Haotian Tang, Yao Fu, and Song Han. Duoattention: Efficient long-context LLM inference with retrieval and streaming heads. In The Thirteenth International Conference on Leurning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ Salakhutdinov, and Quoc Le. Xlnet: Generalized autoregressive pretraining for language understanding, Advances in neural information processing systems, 32, 2019.
Yao Yao, Zuchao Li, and Hai Zhao. SirlIm: Streaming infinite retentive LLM. In Lui-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers). ACL, pp. 2611-2624 Association for Computational Linguisties, 2024.
Guanghao Ye. Fast algorithm for solving structured convex programs. The University of Washington, Undergraduate Thesis, 2020.
18

---

Published as a conference paper at ICLR 2026
Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi. Kdeformer: Accelerating transformers via kernel density estimation. In ICML. arXiv preprint arXiv:2302.02451, 2023.
Aohan Zeng, Bin Xu, Bowen Wang, Chenhui Zhang, Da Yin, Diego Rojas, Guanyu Feng. Hanlin Zhao, Hanyu Lai, Hao Yu, Hongning Wang, Jiadai Sun, Jiajie Zhang, Jiale Cheng, Jiayi Gui, Jie Tang, Jing Zhang, Juanzi Li, Lei Zhao, Lindong Wu, Lucen Zhong, Mingdao Liu, Minlie Huang. Peng Zhang, Qinkai Zheng, Rui Lu, Shuaiqi Duan, Shudan Zhang. Shulin Cao, Shuxun Yang. Weng Lam Tam, Wenyi Zhao, Xiao Liu, Xiao Xia, Xiaohan Zhang, Xiaotao Gu, Xin Lv, Xinghan Liu, Xinyi Liu, Xinyue Yang. Xixuan Song, Xunkai Zhang, Yifan An, Yifan Xu, Yilin Niu, Yuantao Yang. Yueyan Li, Yushi Bai, Yuxiao Dong. Zehan Qi, Zhaoyu Wang, Zhen Yang, Zhengxiao Du Zhenyu Hou, and Zihan Wang. Chatglm: A family of large language models from doi: 1044550/ARXV..4066.1222 URL https: / //dol wttp//0..45////.2........ wwt.:rxwii.......22.......
GLM-130B to GLM-4 all tools. CoRR, abs/2406. 0200222446.1279.... 2024,
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiy Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15393, 2020.
Jintao Zhang, Chendong Xiang, Haofeng Huang, Jia Wei, Haocheng Xi, Jun Zhu, and Jianfei Chen. Spargeattn: Accurate sparse attention accelerating any model inference. CoRR, abs/2502.181377 2025. doi: 10,48500ARXW.2502..1111 URL https: /topps://do... 009//1004450//rxxi 25C2 18137
Lichen Zhang. Speeding up optimizations via data structures: Faster search, sample and maintenance. Master's thesis, Carnegie Mellon University, 2022.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint 0tt.:2205001066 2022.
Xinrong Zhang, Yingfa Chen, Shengding Hu, Zihang Xu, Junhao Chen, Moo Khai Hao, Xu Han, Zhen Leng Thai, Shuo Wang, Zhiyuan Liu, and Maosong Sun. ocbench: Extending long context evaluation beyond 100k tokens. CoRR, abs/2402.13718, 2024. URL httlltttp://ooo /tttps://doi.org/10
48550/arXiv 2402. 13718
Haoyu Zhao, Abhishek Panigrahi, Rong Ge, and Sanjeev Arora. Do transformers parse while predicting the masked word? In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, pp. 16513-16542, Association for Computational Linguistics, 2023.
19

---

Published as a conference paper at ICLR 2026
Appendix
Roadmap. In Section A] we provide additional related work. In Section B we briefly discuss the background on lg sampler. In Section[[ we show that how to use the tail bound to obtain sampling result. In Section D we present the tensor sampling result. In Section E we discuss the LLM usage of the paper.
A ADDITIONAL RELATED WORK
On sketching.
The application of sketching and sampling techniques in numerical linear algebra has been remarkably effective, revolutionizing a broad spectrum of core tasks. These methods are crucial linear programming (LP), evidenced by Cohen et al. (2019); Jiang et al. (2021): ) Ye (2020); Gu & Song (2022), and have significantly impacted tensor approximation (Song et al. 2019; Mahankali et al.
2024 Deng al., 2023a). Sketching and sampling techniques also have been widely applied in
(023b), submodular function maximization (Qin al. (023a). dynamic sparsification (Deng et al. [202aa). dynamic tensor product regression (Reddy et al. 2022). and semi-definite programming
matrix completion (Gu et al. (2024) matrix sensing (Qin et al. 20244] Deng et al.)
(Song et al. 2023a).
Additionally, sketching has been pivotal iterative sparsification problems
(Song et al. 2022).
adversarial training (Gao et al.) 2022). kernel density estimation (Qin et al. 2022b). sol ving the
distance oracle problem (Deng et 2002b), and empirical risk minimization (Lee et al. 2019 Qin
et al. 2023b). Its applications furthermore extends to relational databases (Q Qnn et al. 2022a and
Large Language Model (LLM)) research (Deng et al. 2023c b. Gao et al. 2025
Li al.
2023
On theoretical attention.
comprehensive body of research, including studies (Child et al. 2019: Kitaev et al.
2020 Wang
let al. 2020, Daras et al., 2020 Katharopoulos et al. 2020; Chen et al. 2021 2022 Zandieh et al.
2023
Alman & Song 2023 Brand et al. [2224] Deng et al. 2023c; Kacham et al. 2023: Alman
& Song 2024a; Han et al. 2024; Awasthi & Gupta 2023 Marcus et al. 2022 Alman & Song 2025a b). has progressively shed light on the complexities and optimization of attention
2024b
matrix computation. This exploration has been further enriched by insights into the effectiveness of
attention mechanisms in Transformers (Dehghani et al. 2018 Vuckovic et al. 2020; /Zhang et al.
2020 Edelman et al. 2022] Snell et al. [021 Wei al. 2021 Deng al. [023d]] 2024a). Among
these, Zhao et al. (2023) revealed the adeptness of mid-scale masked language models in identifying
syntactic elements, paving the way for innovations like partial parse tree reconstructions. Inspired the exponential mechanism in attention structure, Gao et al. (2023) provide an analysis which shows exponential regression within the over-parameterized neural tangent kernel framework can converge. In the over-constrained setting, several work show the convergence for attention inspired regression
problem (Li et al. 2023 Deng et al. 20236).
B le SAMPLER
We give the full details of the standard Le sampler from Jowhari et al. (2011); Mahabadi et al. (2020)
in Algorithm? 2] The proof of correctness is verbatim from Jowhari et al. (2011); Mahabadi ct al.
2020)
The challenge is how implement the data structures of y. which is implicitly defined
as (A1
@ Az)x. By comparison, in the standard setting of & samplers Monemizadeh & Woodruff
2010
Andoni et al. (201 T): Jowhari et al. (201T): Jayaram & Woodruff (2021) Mahabadi al. is given as a data stream.
2020
C FROM TAIL TO SAMPLING
Lemma C.1 (Restatement of Lemma be updated in streaming. Let
7.4. Lery y = (A1 @ A2)x E R²² Let only one of A and A Tu. for constant u, [0, generated uniformly at random.
There is an algorithm A that that uses ((nd) + +poly lo, space, uses O(n) update time, and estimates each element of w up to additive error e- | where 2 denotes the tail vector of w without the largest 2 entries in magnitude. Specifically, for all E [n?], have (ū wal S E ||
20

---

Published as a conference paper at ICLR 2026
Algorithm 2 Standard & Sampler, e.g., extension Jowhari et al. [2011) to 2
1: For each E [n]] let u, E [0, 1] be chosen uniformly at random
2: f Vag
1 2 entries in magnitude 3: Let = denote the tail vector of w without the largest
4: Let Y be a 2-approximation of ||yl|2
5: Let 2 be a 2-approximation of ||=||2
6: argmax;e[m] [0:]
7: Let C' > 0 be a large constant determined by the additive faliure probability poly(m)
8: if 2 C n y or |wy| < V Clong
Y then
9: Return FAIL
10: else
11: Return with estimate Vug wi
12: end if
Proof. Consider hash function h1 b2 : [n]] - [b]. Consider random sign functions 0 02 : [m]
+1) We consider fixed index i E [n.] Let (i1) + h2(22) (mod b). Let / (j)
denote the the pairs (i1, 12) E [x] x [n] such that h (i1) + (22)2) (mod b) j. Note that D:
induced by h is Wi w, - s,8 W12. For ease of presentation, write o,
2,i and 2212
[[ = E wi +
Σ (())())) B[wy]] +
Σ
B[o(1) o()) wi
leh (MMD
IEA - (OM
uy +
Σ
E[o(1) (lo())))((()) wi Wi:
10A-1
where the first step follows from definition, the second step follows from linearity of expectation, the third step follows from (i) and o(l) are independent, the forth step follows from E[a = 0.
We now upper bound the variance of W; y/1 by analyzing [ )). Let be the set of the top 2 items and let & be the event that none of the items in H. are mapped to h(i), ie., h(a) * h(i) for all a E H.
100 2. we have that Pr[E] 0.9. Then we have: Observe that for b
Bi 2
[8]=B[(
Σ
(()))())
Σ
wf
/Eln|/\AH,EEE
Σ
wf S 5 (wf + ... w Σ wf
IEMPAWLEE 10)
1E7
100e2: ||=112,
for b 100 since is the vector corresponding y that removes the entries in H. By Cheby- 2 shev's inequality, we have that Pr[l w.l ||=||| 8 10' Since Pr[g] 0.9, then Pr [0; wp| e || < 0.2, for fixed hash function h. By taking the median of (log n) estima- tions corresponding
(log n)) different hash functions h, we have that Pr[[u;; w.l 2 e || <
Thus by union hound over E [r) [n), we have that with probability at least n.. we have
g all E [n]. [0; wil 2 e ||2||2-
Lemma C.2 (Restatement of Lemma 7.5 Lety (A1 & A2)x E TR= and let E T so that
Mi_ W; Vuz for constant u, [0, 1] generated uniformly at random. Let denote the tail vector
of w without the largest 1 entries in magnitude. Let Z be 2-approximation to || and be 2-approximation to [|y||2. Then
C'log n
Pr 2 >
4 <((e) + pnly(n)
21

---

Published as a conference paper at ICLR 2026
Proof. Let E denote the event that 2 is 2-approximation to ||=||2 and Y is 2-approximation to |yy 12, so that
1
Pr[Ei] 2 1 (o)y(n)
Conditioned on E it suffices to bound the probability that
4||=||2 > V CClog |1v122
Let j E [n²] fixed index and let Uj be fixed.
Let T ve- llyll2 and for each E [n²]], define the indicator random variable W; if [ws] > T and W; = 0 otherwise, if |wy| S T. Note that W; is an indicator random variable for whether the coordinate w, in the vector w is "heavy" magnitude.
We then define
w 72
2;
(1 - W;)
to be the scaled contribution of the small entries of and observe that Z, E [0, 1].
Let
W
denote the total number of heavy indices besides possibly index j and Z = -ig(ne) Zi denote the total scaled contribution of the light indices besides possibly index j. Let v denote the vector containing the heavy indices, so that v; wt for W; and u; 0 otherwise for W; Note that v has sparsity at most Y + and moreover U = [ v 2- We also have that || I || u|1a
unless W 2 3.
Let & denote the event that W 2 2 and let &, denote the event that Z 2
C'logn 167
11
Observe
that if neither Eg nor Eg occur, then we have 4|22112 S bound the probability of the failure events Eg and Eg.
C'oog
||y||2, desired. Thus remains
We have E[W.]
| so that [[W] S By Markov's inequality, we have that Pr[E2] s 5.
u² We now upper bound Pr[Ea]. Recall that Z, _ (1 W.) To? (1 Wt), since w, ver
w²
N² since T Se. |lull2. For (0, 1),
Observe that Z, only if |wa] T. ie.. if us e ll
thus have
[
B3 [
<
zddu
[
Vi
dw.-
72
Now, let & be the event that i; 2
1 for all E [n²], so that Pr[Es] 2 1- 20
Then
y 1/n0//2 u, T
E 7
Ed 5
du;
1
C' log TI
T Mi
22

---

Published as a conference paper at ICLR 2026
Thus, have
BiZ
Eg] =
E|Z Ed]
kE(12)
C
T Vi
iE[na]
Clogg n vi
1
(E[x²]
log n
Thus by Markov's inequality, the probability that larger than Clogn |1yl 1672g
C logn is at most
16
The claim then follows from taking union bound over the events El, -E,, EEg, -E.
D TENSOR SAMPLING
Theorem D.I (Restatement of Theorem 7.6). Let y (A₁ & A2)a E ER² and let w E IR² so that for each E [n²], w; yue
Xiا for a constant u; E [0, 1] generated uniformly random. Let denote
the tail vector of without the largest 2o entries in magnitude. Suppose there exists:
1. An algorithm A1 that provides 2-approximation to llyl| with probability
2. An algorithm A2 that provides a 2-approximation to || with probability 13
3. An algorithm As that estimates each element of w up to additive error e ||/||/2
W wil S E ||
for all E [n2).
Then there exists data structure that uses poly (1 log n) bits of space and outputs each index i with probability Ps. such that
1
(1-c)
S S 61+
+
poly(n)
11 (oly
Proof. Let be fixed and let denote the event that u, < Clogg Y so that |uv
C log P.
Let 3 denote the event that Ý a 2-approximation to ||v|12. Ż is a 2-approximation to ||=||2. and
[ w:/ < e || for all i E [m)]. Let &g denote the event that Ż Clogn and let Eg denote
the event that multiple indices j satisfy |wyl
C log
V. Finally, let Ea denote the event that
logn
Intuitively, & is a good event, i.c., correctness of the data structures, which we would like to hold. On the other hand, E2, &s, &4 are bad events that distort the sampling probabilities, which would like to avoid.
We first note that &, holds with high probability due the correctness of the CountSketch and Lg-norm estimation data structures. We next note that by Lemma 7.5 the probability that Eg occurs O(e).
Next, that the probability that for a fixed j [n], uy satisfies By
Clogn Y is most
for some constant C'. Thus summing over all [n]], the probability that there exist Iog b
an additional j E [n]] for which [wy] > log 4 is O(c). Thus the probability that &g occurs is
(
23

---

Published as a conference paper at ICLR 2026
Finally, conditioned on -E,, we have that 7 Clog Y.
V
Then conditioning on ε we have
||=||2 s 7 and thus [0; mil eZ logno that & only occur for Clog
|us] <
C log Y, which is at most probability O Clog v Y over the randomness of u;-
In summary, observe that conditioned some value being output, the probability that item i is selected proportional to the event that the events & and occur, and none the events E2, E3, E occur. The probability that & occurs is Cllog F22 which u, is chosen uniformly random. Due to the event ε₁, the sampling probability is distorted additively by poly(nj' while due to the events E2, Eg 4 the sampling probability is distorted multiplicatively by (1 +e. Thus conditioned on the event that some index is returned, the probability p; that index is returned satisfies
of
y
1
(1 c)
SP S c1+
1
poly(n)
1lv1
poly(n)
as desired.
E LLM USAGE DISCLOSURE
LLMs were used only to polish language, such as grammar and wording. These models did not contribute idea creation or writing, and the authors take full responsibility for this paper's content.
24


Reviews:
[{"review_id": "cItwzeHISb", "reviewer": "Reviewer_XQKc", "summary": "The authors propose to use attention sampler for efficient attention computation in the streaming setting. They primarily provide theoretical time & space lower and upper bound for L2 sampler. The authors also extend the analysis to the case of tensor multiplication.", "questions": "N/A", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The theoretical investigation seems solid and also quite comprehensive. They also extend the analysis to tensors, which might shed light on some tensor attention applications.", "weaknesses": "- Line 086-090: bullet point 1 and 2 are somewhat overlapping and provide different claims on complexity for the same underlying setting on A and x.\n- The primary problem is that there are no experiments to demonstrate actual efficiency improvement in a Transformer, even though the paper is clearly motivated by solving the efficiency challenge of large-scale attention-based models computation.", "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": "m69VIEKrfc", "reviewer": "Reviewer_odpP", "summary": "The paper studies and characterizes a polynomial type sampling algorithms for the application of streaming LLMs where the model is\nexpected to engage in large inference sequence generations (as a long chat bot conversation).\nMoreover, the authors derive a lower bound for the softmax distribution arguing for its \"hardness\", as well as upper and\nlower bounds for polynomial type samples.", "questions": "* In the abstract you claim: \"Our approach significantly reduces the computational burden of traditional attention mechanisms\"\nCould you elaborate why this is true. My understanding is that the scope of streaming LLMs is not commonplace and\ntherefore the claim appears to encompass a wider scope. Am I missing something?\n* In the conclusion you claim: \"our framework identify the critical components in attention computation\" could you\n  succinctly state what does critical components are?\n* Could any of this work be applied to pre-training a model or it can only be applied to inference?\n* I might've missed this motivation, but what is the value of having a tensor version of the problem? What do we gain?\n* Line 049. What do you mean by first asked? \"A well-known example is the \\ell_2 sampler first asked by\" Maybe typo.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The paper contains a comprehensive theoretical analysis for polynomial type samples proving several bounds and some\n  lower bounds.", "weaknesses": "* The paper is motivated by the computational challenges of large-scale attention-based models which I'm familiar with.\nHowever, the paper does not motivate why are we using particularly turnstile streams.\nSome clearer motivation of a general Machine Learning audience would be highly valuable.\nMoreover, Definition 1.1 talks about the attention sample for a matrix that is not square on the sequence length, which\ndeviates from the usual attention definition.\n* I understand that the paper is a theoretical one where a thorough analysis is done to some polynomial type of\n  algorithms. However, no empirical demonstration is done to corroborate its the core question of the paper:\n  \"instead of computing all the entries, can we recover the most important ones in efficient space and time?\"\n* I'm willing to revisit my score if the motivation for the work and its applicability is clearer to me.", "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": "fX3lLZhsnx", "reviewer": "Reviewer_dsvo", "summary": "The paper proposes attention sampling - sampling a token index from a token stream from a distribution constructed according to the attention function. It gives a space lower bound for this problem and also provides upper bounds for similar L2 sampling questions.", "questions": "1. How are the entries of matrix $A$ updated? Is it row-by-row, or any kind of update is acceptable?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The problem considered by the paper is interesting: sampling from a distribution according to the attention mechanism. Understanding the complexity of this problem and designing efficient algorithms for can have an important impact on efficient AI algorithms.\n2. The methods proposed by the paper, though they generalize prior approaches and techniques, are applied with clarity and in a set of well-motivated theoretical settings.\n3. The paper is rigorous and methodical in its approach. Its algorithms are well stated and proven.\n4. The paper provides an extensive literature review.", "weaknesses": "1. The motivation behind \"attention sampling\" is not very well supported. The authors state that solving this problem would be positive towards developing efficient transformers, but this is not justified via experiments or suggestions of ways their algorithms can be used in practice. And without those, it is hard to see why attention sampling would be an important problem to solve. Furthermore, the authors show an $\\Omega(n)$ lower bound for exponential sampling, meaning that even if attention sampling is very useful, the best thing we can do is calculate the underlying distribution explicitly. \n    * As a smaller comment, streaming space lower bounds for attention mechanisms have been proposed and analyzed before (also via communication complexity reductions). It would be nice for the paper to cite these works as well: [1], [2].\n2. The L2 sampling contributions, while interesting, deviate from the main theme of the paper. Attention sampling, as proposed, should intuitively be related to the Transformer architecture or attention mechanism. Perhaps for different normalization functions (other than softmax), sampling in sublinear space is possible, which would give further motivation towards studying and using those functions. The L2 results seem like a natural extension of the well-studied problem of $L_p$ sampling in a turnstile stream, and though they make use of non-trivial sketch constructions to deal with updates in the $A$ matrix, they don't fit in very well to the paper's narrative in my opinion.\n\n**References**\n* [1] Han, I., Kapralov, M., Kochetkova, E., Sheth, K., & Zandieh, A. (2025). Streaming Attention Approximation via Discrepancy Theory. arXiv preprint arXiv:2502.07861.\n* [2] Haris, Themistoklis, and Krzysztof Onak. \"Compression barriers for autoregressive transformers.\" arXiv preprint arXiv:2502.15955 (2025).", "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)