FutureFill: Fast Generation from Convolutional Sequence Models
Authors: Naman Agarwal
Xinyi Chen
Evan Dogariu
Devan Shah
Hubert Strauss
Vladimir Feinberg
Daniel Suo
Peter Bartlett
Elad Hazan
Venue: ICLR 2026 Poster (2026)
Keywords: convolutional models
fast inference
Primary area: generative models
TL;DR: FutureFill introduces a fast autoregressive generation method for convolutional sequence-prediction algorithms — reducing generation time from quadratic to quasilinear in the context length and is supported by theoretical results and experiments.

Abstract: We address the challenge of efficient auto-regressive generation in sequence prediction models by introducing FutureFill—a general-purpose fast generation method for any sequence prediction algorithm based on convolutional operators. FutureFill reduces generation time from quadratic to quasilinear in the context length. Moreover,  when generating from a prompt, it requires a prefill cache whose size grows only with the number of tokens to be generated—often much smaller than the caches required by standard convolutional or attention‐based models. We validate our theoretical claims with language modeling experiments and demonstrate substantial efficiency gains when generating from a deep convolutional sequence prediction model.

Published as a conference paper at ICLR 2026
FUTUREFILL: FAST GENERATION FROM CONVOLU- TIONAL SEQUENCE MODELS
Naman Agarwal*
Xinyi Chen'
Evan Dogariu*
Devan Shah
Hubert Strauss"
Vlad Feinberg"
Daniel Suo"
Peter Bartlett"
Elad Hazan"
ABSTRACT
We address the challenge of efficient auto-regressive generation in sequence pre- diction models by introducing FutureFill a method for fast generation that ap- plies to any sequence prediction algorithm based on convolutional operators. Our approach reduces the generation time from quadratic to quasilinear relative to the context length. Additionally, FutureFill requires prefill cache sized only by the number of tokens generated, which is smaller than the cache requirements for stan- dard convolutional and attention- basdd models. We validate our theoretical find- ings with experimental evidence demonstrating correctness and efficiency gains language generation tasks. The project website can be found at adddsah.ioon iofuuurl/f
INTRODUCTION
Large Transformer models (Vaswani et al., 2017) have become the method of choice for sequence prediction tasks such as language modeling and machine translation. Despite their success, they face a key computational challenge: the softmax attention mechanism incurs quadratic computational cost during training and inference. This inefficiency has spurred interest in designing architectures that can handle long sequences more efficiently.
Convolution baaedd sequence prediction models (Li et al. 2022 Poli et al. 2023 Agarwal et al.
2023 Fu et al., 2024) have emerged as strong alternatives, primarily because they can leverage fast algorithms, particular the Fast Fourier Transform (FFT) achieve near-linear scaling in the sequence length during training. These models build on advances in State Space Models (SSMs),
which have shown promise modeling long sequences across diverse modalities (Gu et al.
2021a
Dao et al. 2022b Gupta et al.) 2022 Orvieto et al. 2023 Poli et al. 2023 Gu & Dao
2023
Convolutional models offer a more general framework than SSMs because they can represent any
linear dynamical system (LDS) without requiring parameters that scale with the dimensionality of
the hidden states (Agarwal et al. 2023). This flexibility has led to recent developments that can handle longer contexts more effectively both in theory and practice. For instance, Spectral State Space Models or Spectral Transform Units (STUs) (Agarwal et al.) (203)) use convolution- spectral filtering algorithms (Hazan et al. 2017 2018) to transform inputs into better-conditione bases for long-term memory. The Hyena series of models (Poli et al. 2023 Massaroli et al. 2024) is another example, which learns implicitly parameterized Markov operators using convolution. Both methods exploit the duality between time-domain convolution and frequency-domain multiplication accelerate prediction via the FFT algorithm.
While SSMs and recurrent models benefit from fast inference times independent of sequence length, convolutional models have significantly slower token generation times during inference. The best-known result for generating tokens with convolutional models is quadratic in sequence lonpth--omppaable to intentiionbbsed models (see Massaroli al. (2024) Lemma 2.1). This lim- itation has prompted research into distilling SSMs from convolutional models (Massaroli et al.) 2024]. but the distilled SSMs are an approximation of the original convolutional models and the approximation gaps are not fully understood.
Google DeepMind
Princeton University
Coorespondence to: namanagarwal @ooogggooll..ooooo

---

Published as a conference paper at ICLR 2026
In this paper, consider exact auto-regressive generation from convolutional models, significantly reducing both the generation time and the cache size. We present our main results in two settings:
1. Generation from Scratch: When generating L tokens from scratch, demonstrate that long convolutional sequence predictors can generate these tokens in total time O(Llog' L) with to- tal memory (L). This improves upon previous methods that require O time for gener- ation. We further provide memory-efficient version wherein the total runtime increases to /oog/)))og(()) but the memory requirement is bounded by Ogy
Generation with a Prompt: When generating K tokens starting from a prompt of length L, show that the total generation time is OLLlog L + K log" K) with cache size of O(K). Previously, the best-known results for convolutional models were a total generation time bounded by lo L + LK + K²) and cache size bounded by (L) Massaroli al., 2024).
Importantly, our algorithms generate exactly from the convolutional model without relying on any approximations. There are numerous recent advances for efficient inference using approximate methods, for example cache compression (Zhang et al. (2024) and sparse attention (Beltagy et al., 2020). Since our approach involves no quality loss, we consider these methods be in a different class and do not compare against them. Moreover, our methods are applicable to any convolutional model, regardless of how was trained.
The following tables compares our algorithm with standard implementation of convolution. It worth noting that naive online convolution does not require additional memory beyond storing the inputs and filters. Our methods, however, provide a spectrum of trade-offs between computa- tional complexity and memory usage. We also provide comparison of the time and cache size requirements for exact computation in attention- based models.
Prefill+Genertation Runtime
Generation Cache Size
Method
Runtime
Memory
Standard Conv
1
LK + Lloo L K2
L +
Standard Attn.
L
LA + KL
L'+
L
+
EpochedFF (ours)
3 Vlo
Volo L L
log L + K3/2 Vlog
ContinuousFF (ours)
log""
I. log T. + Klog* K
(a) Comparison for generating L tokens from scratch. Runtime is in asymptotic notation, i.e. O()) is omitted for brevity.
(b) Comparison for generating K tokens starting from a prompt of length L. runtime and cache- size are in asymptotic notation.
To determine whether our theoretical findings lead to empirical benefits, we apply our algorithms to generate tokens in both controlled settings and from deep convolutional sequence prediction mod- els. As a sanity check, we show empirically on isolated online convolutions that our algorithms achieve sub-quadratic scaling compared to the naive convolution implementation. We then consider more complex workloads where we generate from academic-sized models. We evaluate both purely convolutional and hybrid comvolution/attention language models, and demonstrate that for both gen- erating from scratch and generating from a prompt, our algorithms can achieve a substantial speedup of up to 1.7x compared to the baseline.
1.1 RELATED WORK
Due to space limitations we provide detailed related works section in the Appendix (Section D.I and provide short review in this section. Recurrent neural networks have been revisited in recent deep learning literature for sequence prediction in the form of state space models (SSMs), many of which can be parameterized as convolutional models. GGu et al. (2020) enable long-term mem- ory via specialized system matrices, with follow-up works (Gu et al. 202 Gupta et al. 2022 Smith et al.] 2023) improving stability and computational efficiency. Convolutional models such as LongConv (Fu al. 2023), SGConv (Li et al. 2022),, , and Hyena (Poli al. 2023) offer structured convolution kernel parameterizations for sequence prediction. For learning linear dynamical sys-
tems, spectral filtering (Hazan et al. 2017] emerges powerful, efficient method with provable
2

---

Published as a conference paper at ICLR 2026
regret guarantees even in MIMO settings. This technique is developed under the online convex op- timization (Hazan et al. 2016) framework, which lays the theoretical basis for adversarial sequence prediction. Given the strong guarantees, spectral filtering has been used to develop novel convo- lutional architectures for long range prediction and language modeling (Agarwal et al. 2023 Liu al. 2024). Finally, independent work (Oncescu et al. (024) presents very similar algorithm for convolutional model inference with a total runtime of O log (L) (same as Continuous- FutureFill result) using the method of relaxed polynomial interpolation. Our algorithms are based on the simple and intuitive idea of FutureFill, which allows create more practical algorithmic variants with lower memory usage and more streamlined implementation.
2 SETTING
For an imput sequence }uc} we denote by u1:t the sequence of inputs U1, ....... uq. For any i S let U:y denote the sub-sequence u, Ui+1.... ................................ Ug. When i j. Wi:j denotes the subsequence Mjzi in reverse order. We also denote [R:] = {1,
Notation:
2..,, ..., k u, let [uly denote the j-th coordinate of u; if u is a one-dimensional sequence, then let [ul, denote the j-th position of u. Given multi- multi-dimensional sequence ..... u, where each u, E R and given a vector E IR for brevity we overload the definition of inner products by defining y (u, u1:1)
set of k natural numbers. For a vector
with y Hd y/ Ei= 24 [u,l] E R. That is, is d-dimensional vector where the coordinate j is the inner product between v and the sequence [uil::...,[u. [ull5-
Convolution:
The convolution operator between two vectors u, E R outputs a sequence of length i whose element at any position E [4] is defined as
[u (s) = Σ u. u (11::: 0sa)-
(1)
A classical result in the theory of algorithms is that given two vectors u, & E RC, their convolution can be computed in time O(t log f), using the FFT algorithm.
Online Convolution: We consider the problem of performing the convolution
when one of the sequences & is fully available to the algorithm, however the other sequence w streams in the element u, is made available to the algorithm at the start of round release the output [u o/. This model of online convolution is immediately relevant to the online auto-regressive generation of tokens from a convolutional sequence model, as the output token at time becomes the input for the next round. In this setting, the sequence u corresponds to generated tokens and the sequence corresponds to the convolutional filter which is known the model. We further detail the setup of sequence generation in the next subsection.
which point it has to
Naive Online Convolution: Online convolution can be implemented by directly computing the inner product each time step, the new input becomes available. We refer to this method as naive online convolution. It has a computational complexity of O(L)) for predicting for L steps and requires no additional memory beyond storing the inputs and filters.
2.1 AUTO-REGRESSIVE SEQUENCE PREDICTION
Sequence Prediction: In this setting, the input is sequence of tokens denoted Miy... Uy ... where uy Rdd.., The predictor's 's task is to generate sequence ii..... Ut. St.... ..., where dt E Rd is generated after observing the inputs u....., 46-1- The output y: is observed after the predictor generates ột- The quality of the prediction is measured by the distance between the predicted and observed outputs according to a loss function l, (5r,, Vt), for example the f2 distance |! yel/2.
Auto-regressive Sequence Prediction: When predicting a sequence in an auto-regressive fashion, in each iteration online predictor first makes a prediction using the existing inputs #1.--., Ut-1, and then append the prediction ÿt to the inputs to be used in the next iteration, where the inputs
'This definition corresponds to the valid mode of convolution in typical implementations of convolution c.g. scipy.
3

---

Published as a conference paper at ICLR 2026
become "....., Mt-1, 9t- When predicting from scratch, the online predictor starts from given initial token and predicts, or generates, the rest of the sequence.
Auto-regressvee Sequence Prediction from Prompt: Auto-regressive sequence prediction start- ing from a prompt is commonly used by large language models. Herein the sequence model has to generate specified number of tokens given a certain context. In practice, this setting consists of two stages, the prefill stage and the decode stage.
During prefill, the model ingests the entire context and generates cache that stores context infor- mation required for generation. When decoding, the model takes the cache and the most recently generated token input and generates the next output token. The cache is then updated with the most recent input token. The cache stores the input information the prediction algorithm needs in order to generate the output. For instance. Transformers typically save the key and value vectors of past inputs in KV cache, and for convolutional models, naive online convolution stores all previ- ous inputs. As a result, for these models, generating tokens from a prefill of length L requires a cache of size O(L+K) This can be prohibitively large for long-context inference with an extensive prompt, and reducing the cache size is key in this setting (Hooper et al. 2024).
2.2 ONLINE CONVOLUTIONS IN SEQUENCE PREDICTION
We define a convolutional sequence prediction model to be given by a filter, which is a vector denoted by ø E R² where L is the context length of the model. It takes as an input sequence u, and outputs a prediction at time according to the following equation, ÿt = (0, Me.tL).
The above definition can be extended include nonlinearities and multiple filter channels. This paradigm captures several prominent convolutional sequence models considered in the literature, and we highlight some of them below (additional details are provided in the appendix in Section (.2)). Our online convolution techniques can be straightforwardly applied to all the following models, leading to an improvement in the generation time from (l2) to Ó(L). When generating from prompt, we improve the cache size from O + K) to O(K).
Spectral Transform Units:
The STU architecture was proposed in (Agarwal et al., 2023 based on the spectral filtering technique for linear dynamical systems (Hazan al.j 2017| 2018). These are convolutional sequence models based on carefully constructed filters that are not data- dependent. More specifically, the filters .I...., &b are derived from a fixed Hankel matrix H/ depending only on the sequence length L. The STU predicts according to the following rule 9i- = Et= Mi(or, vt:t-L), where M1. are learned projection matrices. Note that the inner prod- ucts (0,, Ut)-L) are the outputs of 6; u. The STU architecture is particularly appealing for learning LDS with long memory, as demonstrated by its dimension-free free sublinear regret guarantees for this setting (Agarwal et al. 2023). For more details see Appendix D.2
The Hyena architecture proposed in Poli et al. (2023) sequentially applies convolutions and element-wiss wise products in an alternatve fashion. Formally, given an input u1... N + 1 linear pro- jections U, 21, NN of the input are constructed (similar to the y, k; u sequences self-attention). The hyena operator sequence of convolutions with learnable filters h.... hx is then given by
Hyena:
= EN (by * (IN-1 - (hN-1 * (...))))
3 EFFICIENT ONLINE CONVOLUTIONS USING FUTUREFILL
We begin by introducing a simple and convenient primitive named FutureFill that forms the crucial building block of our algorithms. Intuitively, FutureFill corresponds to computing the contribution of the current and previously generated tokens on the future tokens yet to be generated. For a convolutional model (and unlike attention) this contribution even having generated the future tokens. Here onwards, for brevity of notation, for any u E Rf, we any j > I. Formally, given two sequences v E R4 E IR
be efficiently determined without
assume Uj 0 for any
more precisely, there are additional linear and constant terms depending on the exact filters used, such as 0--2 E Mfuuttii + Σ My Mes--)) L), see Agarwal al. (2023) for more details.
4

---

Published as a conference paper at ICLR 2026
define FutureFill(u, w) R
f2 Σ
Vs [t2 1] [FutureFill(e; w)]+
0t--++1 Wa+i
Figure in Appendix [.3 depicts the FutureFill operation between input sequence and volutional filter. Conceptually, [FutureFill( w)]s is the contribution of the input v of length 4 to the output [v w] position + 8. The FFT algorithm for convolutions can easily be extended to compute the FutureFill as well in time at most ((1 + f2) log(t1 + f2)). For example, the full mode of standard conv implementation (e.g., numpy) can be used compute FutureFill in the following way under Python slicing convention (exclusive of the last index),
FutureFill (V, w) = numpy- convolve (v, mode=fulll [t_1:t_1+t_2-1
To leverage FutureFill for efficient generation from a convolutional model, consider the proposition below that follows from the definition of convolution.
Proposition 1. Given two vectors b E IR, we have that vt,, E [t].
[a1.n d1a1ls [ar tat b1a-t,ls- + [FutureFillaann (FaauuueaaaTu b)]s-t1
is S 4
6).
That is, the convolution of two vectors a and can be broken into FutureFill operation and another convolution involving b and only the most recent positions of We provide proof in the appendix.
3.1 EPOCHEED-FTTUREFILL EFFICIENT ONLINE CONVOLUTION
When computing online convolutions, the FutureFill routine efficiently pre-computes the effect of past tokens on future ones. We leverage this property in the Epoched-Fuus FutureFill procedure outlined in I compute online convolutions.
Algorithm Epoched-Futtuue FutureFill: Efficient Online Convolutional Prediction
1: Input: Filter R.,. Input seq. Rh, streaming coordinate-wist K, the epoch length.
2: Set r = 1. Set FutureFill cache C IR to
3: for /= 2,, L do
4: Receive ur, and compute and output ÿt = EJ= M .05 + Cr.
5: if r = K' then
6: Compute FutureFill cache C' R defined C₁ [FttureFilluuu 01a4k)l;-
7: T+1
8:
else
9:
++++1
end if
11:
end for
The following theorem establishes the properties of Epoched- Filtrrelluuutlelll and provide trade-off be- tween the additional memory overhead and total runtime incurred by the algorithm. In particular, the runtime in this trade-off is optimized when the total memory is (o.oo I.), leading total runtime of 3/1 /log L).
Theorem 2. Algorithm KL) with total additional memory requirement of O(K). Setting K = log L to minimize the runtime, Algorithm 1 computes online convolution in O(L3/2 Vlog L)
7 computes the online convolution of sequences with length L and runs in
total time O ( (
total time and O log L) memory.
Proof. Since the proof of correctness is mainly careful accounting of various terms, we provide in the appendix and give the running time results in this proof. The running time consists of two
recall that denote [z) (1 ...2).

---

Published as a conference paper at ICLR 2026
components. First, at every iteration, line executed. One term, Cr, has already been computed and saved line 6 so we can retrieve in constant time. The other term is a sum of 7 products, execute line lineoland and update the
which can be computed in time (rr). Second, every K iterations, cache. The FutureFill operation can be computed via the FFT in at most ( log /.) time.
Summing L iterations, the total computational complexity is
L K
K Σー> =0 (Llog Llog L +
(L + KL) = =0 =0(132 (L8gL
K
r=1
where the last equality holds when the cache size K = Vollg T. chosen to minimize the sum.
17
3.2 CONTINUOUS- FUTUREFLL:: QUASILINEAR ONLINE CONVOLUTION
In this section specify procedure that significantly improves upon the runtime of Epoched- FutureFill. Our starting point is Proposition]] [ which implies that to compute the convolution be- tween sequences, we can break the sequences any point, compute the convolution between the corresponding parts and stitch them together via FutureFill computation. This motivates the following Divide and Conquer algorithm to compute the convolution of two sequences a, E R
Recursively compute d1:1,/2 b1.1/2, 01/2+1: by.r/2-
Output the concatenation of 01:L/2 11:1/2 and (1./2411+b1:.1/ FutureFill(aa.///
Since FutureFill for L-length sequences can be computed time O log L) via the FFT, a standard dividu-and-conquer approach yields an O log2 L.) computational complexity for the algorithm. Although this complexity is worse than an FFT, the advantage of the above method is that it can be executed online, i.c. the tokens can be generated as input streams in.
We provide formal description of the algorithm in Algorithm 2 We note that the algorithm de- scription essentially serializes the sequence operations involved in the above divide-and-conques procedure by their chronological order. For high-level intuition, encourage the reader to main- structure when understanding the algorithm. The algorithm proceeds
tain the divide-and-congee follows: at each time step, jt (wi:e, Φta)) is returned sum of C,, the cache that stores the contribution from past tokens, and uę Φ1, the contribution from token u, In Line 7, the algorithm then computes the contribution tokens u, 41=2 to positions + I,...,, + 2*(1) of [u * ø]. Finally, add the output of FutureFill the existing cache C accumulate the contributions. We provide schematic illustrating the flow the algorithm in the Appendix (Section D.3). In
the following theorem we provide running time bound for Algorithm and defer the proof the Appendix (Section]) F))
Theorem 3. Algorithm 2 computes the online convolution of sequences with length L and runs in total time (L log? (L)) with total additional memory requirement of O(L).
Algorithm Fontinuous-FutureFilll Quasilinear Generation From Convolutional Models
1: Input: Convolutional filter & R², Input sequence R4, streaming one coordinate every round.
2: Set b [log LJ. Set FutureFill cache C' E IR- to 0.
3: for 1..... do
4: Receive ue Output De Ct + u, 01.
5: Let k(t) be the highest power of 2 that divides f, i.e. k = max(i E [b] mod = 0).
6: Compute FF FutureFill 2,20 11.2000 1)
7: Set C, C, FF
i 1, 24(1
8:
end for
Remark 4. The computational complexity of Continuous-Futurele is optimal up poly-log fac- tors as we cannot hope to generate faster than constant time per token, and further improvements remain open question.

---

Published as a conference paper at ICLR 2026
Total generation time
Time per step
Nalvé
Naivé
200
Epoched-Futureff
fpoches-futurffil
Condinunus-Fute FutureFii
Continuous FutureFIl
048055
503
04863
04980
Figure 1: Total and average number of seconds per step when generating L tokens.
FAST AUTO-REGRESSIVE SEQUENCE GENERATION FROM A PROMPT
In this section consider the problem of auto-regressively generating K tokens starting from given prompt of length L. For convolutional models in particular, we define an abstract version of the problem: given a prompt vector p E g- and convolutional filter Φ BL-K K the aim is to iteratively generate the following sequence of tokens
4+411
Jt = (01-t-1, 11-1 + (prct, D1LL-12) =
Σ
リーーs 15 +
Σ PL+L-59j-
As the above definition clearly shows, the expected output is an online convolution where the input sequence u has a prefix of the prompt p and the input sequence is appended by the most recently generated output by the model (i.e. auto-regressive generation). Observe that the output can be com- puted from a FutureFill operation and another online convolution involving the generated tokens, which can be computed using either of our online convolution algorithms. In the Appendix (Section D.4), we formally provide Algorithm thh specifies the above method using Continuous FutureeFil (Algorithm{) ( the online convolution algorithm. The corollary below bounds the running time for the overall method which follows easily from Theorem 3
Corollary 5. Algorithm when supplied with a prompt of sequence length L, generates K tokens in total time OT log T. K log² K) using total cache of size O(K).
EXPERIMENTS
5.1 CONTROLLED SETTINGS
In this section, we verify our theoretical results on isolated online convolution operations. We ran- domly initialize dieenminnio filters and study the setting where generate from scratch, where algorithms generate outputs from a given initial input. We evaluate Epoched-FutureFi (Algo- rithm which has a runtime OL Vlog L) and
FutuureFFlll (Algorithm 2 which
has a runtime of log L) against the naive implementation, which has a runtime of O For increasing values of L, measure the time S(L) it takes to generate L outputs. In Figure we plot the amortized step time S(L)/ and total generation time S(L), respectively, as functions of L. The behavior is consistent with theory: the naive algorithm runs in amortized O(L) per step, while our methods achieve sublinear and logarithmic runtime complexities respectively. In the appendix significantly
(Section C) we present additional experiments where we show that Epoched-Future outperforms Transformer models with a standard KV cache and convolutional models with naive decoding (the state of the for convolutional models) for inference.
'The assumption of the filter being larger than T. + K is without loss of generality it can he padded with
Os

---

Published as a conference paper at ICLR 2026
irfwaace Tima Generation Length
Inference Time vs Cache Length K
1734
Model 6 Cache
120
STU-Orly fusurelt
Inference 1.1
StuiOnly
Model Cache
14:00
040
Only
120
925 05 M STU Only & Epoched FutureFil
140
60303
130000
1300
512
FutureFill caché length
(a) Decode time (in s). without prefill. Baselines in dashed lines.
(b) Decode time (in s) for fixed generation length of 65,536 tokens without prefill.
Figure 2: Decode time without prefill and ablations on cache length K
5.2
EXPERIMENTS ON CONVOLUTIONAL LANGUAGE MODELS
In this section, we further show that our theoretical results on FutureFill's sub-quadratic generation time hold when using academic-sioe convolutional language models, i.c. models of up to 826.05M parameters. We focus here on the more practical Spoched-Futturcee (Algorithm
5.2.1
SETUP
We conduct our experiments using two variants of FlashSTU-T, a convolutional model based on Spectral Transform Units as introduced in Liu al. (2024):
Fully convolutional variant: This model consists entirely of Spectral Transform Units (STUs) with the tensordot approximation, which convolve the projected input against fixed spectral filters and apply an MLP layer. End-to-end default precision float
Hybrid variant: This model combines STU blocks with local attention blocks at 1:1 ratio. We adhere closely the setup specified in Li al. (2024). apart from the number of layers and input dimensions as those will be modified in our ablations and the number of attention heads which is set to 4. See Appendix [. for more details. End-to-end default precision is oat1 6; only the FFT operation is upcasted to fl flott...
Since our focus in the ablations below is primarily on generation speed rather than downstream performance, we initialize the filters (Φ1x) uniformly at random while following the initialization approach detailed in Liu et al. (2024) for all other layers. To validate correctness, we also generate
text from 330M pretrained FlashSTU-T model and evaluate on downstream tasks. Our results show that the accuracy matches that of baseline using naive online convolution (Appendix(B.6)
Without prefill, we conduct three ablations colations-geneeaation length, model depth, and model each run from the </nndfftext/ token with prefill cache. With prefill, we ablate the input prompt length Lerumpt. generation length Lyen. and the depth and width of the fully convolutional variant of FlashSTU-T. Additionally, we ablate the cache size K, which we previously set to the theoretical optimum K ablation experiments are available in Appendix
Lgen log Lgen (Theorem 2 More details on the
5.2.2 RESULTS
All experiments were run on a single NVIDIA H100 GPU. For each model configuration and se- quence length, we measure the total decode time (including the full forward pass through MLPs and STU/attention blocks) over three successive runs and report the average of the final two.
Ablations Without Prefill Figure 2a reports the decode times for our two largest models (12 lay- ers, 1024-dim input, attention heads when applicable): the 670.75M-prr STU-only model
8

---

Published as a conference paper at ICLR 2026
and the 389.488-parammes hybrid model. Across all generation lengths, Epoched- FutureFFll ex- hibits clear sub-quadratic scaling, while the baseline shows near-quadratic growth in runtime.
Indeed, L grows larger, the runtime advantage of Sopoched-Futurehhe becomes more noticeable. At the largest generation length Lyen = 126,976, we observe a 1.7x speedup for STU-only and a 1.5x speedup for the hybrid variant, compared to naive convolution (baseline). More results for different combinations of depth and width are provided in Appendix B.2 and we achieve consistent speedup.
Ablations With Prefill, Input Prompt Longer than Generation In the case of prefilling, we measure the prefill time separately from the decode time. We average the prefill time per model over the generation length.
Decode time (S) generation length Tiges
Parameter count
Input dim
Layer count
Cache Type
Avg Prefill Time (s)
4096
8192
16384
515. 46M (STU only)
1024
Epuched FuturelFll
21.40
13.12 1. 0.05
26.18
0.01
52.22
0.08
466.46M (STU only)
1024
Baseline
21.28
25.23
52.31
1 0.02
111.92
1 0.06
670.75M (STU only)
1024
12
Epoched FutureFFll
31.98
19.06
+
37,80
4: 0.01
75.66
0.61
670.75M (STU only)
1024
Baseline
37.20
37.21
1. 0.02 77.15
0.01
165.13
Table End-to-End decode time (in with prefill on an input prompt of length prompt tokens. Error bars are +11 sample standard deviation over the two post-warmup runs.
32,768
Figure 2 reports the decode and prefill times in seconds for our two largest models (12 layers, 1024-dim input, 4 attention heads when applicable): the 67arate- STU-only model and the 189.448--prrames
decoding is substantially faster with increasing model size. It is even noticeable for smaller generation length when the initial prefill is large, as shown in Table 2 because the naive baseline recomputes the full prompt convolution at every token. At the largest generation length Lgen = 16,384, for prefill length of 32,768 tokens, we observe 2x speedup for both models, compared to the naive cached convolutions (baseline).
hybrid model.
For further examples depth-width pairings in the case where the input prompt exceeds the gener- ation length, Appendix [B3.1 In the less common scenario when the generation length is far longer than the input prompt - Appendix B.3.2] presents ablations over depth, width and generation length. In every case, the observed speedups robust and grow steadily as the model scales.
To arrive at a more fine mne-grained understanding of the speedups, we provide module-wiss wise timing breakdowns for the 670.75M 355--rrmmeter STU-only model in Appendix [B.] Our results show that convolution is by far the most time-consuming component of the model. These results further high- light that Apoohed-FutuurFiint significantly decreases the STU (conv/FFT) part of end-to-end decod- ing time to achieve the observed speedups, while other components change only marginally.
Remark 6. In our implementation, we computed the prefill pass on the same GPU that performed decoding, occasionally triggering GPU OOM errors when using very long prompts. In practical deployments, the prefill cache typically produced on separate host and then loaded onto the decoding GPU, eliminating this memory bottleneck.
Ablations on K, without prefill When the generation length is set to 65,536 tokens, the optimal K / Lgen log Lgea 1024 according Theorem 2 We empirically verify it in Figure 2b there is a monotonic improvement in the decode time until the theoretically optimal value of K.
Precision of the FFT & Downstream Tasks Using lower precision is common in language model inference. To understand its effect on our algorithm, we compare upcasting the FFT to fp32 vs fp16 while keeping the model in bf16. We chose fp16 because PyTorch FFT does not support 6 and lower precisions, while upcasting to fp32 is consistent with the method we used to measure genera- tion speed. Our results show that the lower precision does not have significant impact. Accuracy matches the naive convolution baseline in bfl6 across WinoGrande, HellaSwag, and PiQA, using an openly-available 330M -arammeerr pretrained hybrid FlashSTU-T (Appendix B.6).

---

Published as a conference paper at ICLR 2026
6 CONCLUSIONS
In this paper, we address the problem of efficiently generating from convolutional models and present FutureFill, novel method that reduces the computational complexity of generating L kens from OlL²) to OoL L). We introduce a simple but powerful subroutine which enables a flexible runtime/memory trade-off, making our method adaptable to different practical settings. Our experiments confirm the theoretical improvements, demonstrating significant efficiency gains in convolution sequence model generation. These results suggest that FutureFill can serve as an ef- ficient alternative to existing methods, particularly for problems requiring long- -equuecce modeling.
Reproducibility Statement: We have made careful efforts to aid reproducibility of our work and ensure that our results, and limitations of our results, are well understood. the Appendix, we have provided both an overview of each experiment and granular implementation details to aid in reproducibility. We have additionally uploaded our modification of FlashSTU (Liu et al., 2024) with the FutureFill algorithm setup. Beyond this, we devote much of the appendix to providing full proofs and grounding for theoretical arguments and to offering clarifying case studies. We excited about the potential impact of FutureFill and care deeply about ensuring our work is in the best possible position for adoption.
supplemental file and provide full details of our experimental
ACKNOWIEDGEMENTS
The authors thank Annie Marsden for useful discussions though the development of the project. EH gratefully acknowledges support from the Office of Naval Research and Open Philanthropy.
REFERENCES
Naman Agarwal, Daniel Suo, Xinyi Chen, and Elad Hazan. Spectral state space models. arXiv preprint arXiv.2312.06837, 2023.
Beltagy, Matthew Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv:2004.05 2020.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
Tri Dao. FlashAutention-2:: Faster attention with better parallelism and work partitioning. In Inter- national Conference on Learning Representations (ICLR), 2024.
Tri Dao, Daniel Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. FlashAttention Fast and memory-efficient exact attention with IO-awareness. In Advances in Neural Information Process- ing Systems (NeurIPS), 2022a.
Tri Dao, Daniel Y Fu, Khaled Saab, Armin W Thomas, Atri Rudra, and Christopher Ré. Hungry hungry hippos: Towards language modeling with state space models. arXiv preprint 2rXiv:2212. 14052, 2022b.
Dan Fu, Simran Arora, Jessica Grogan, Isys Johnson, Evan Sabri Eyuboglu, Armin Thomas, Ben- jamin Spector, Michael Poli, Atri Rudra, and Christopher Ré. Monarch mixer: A simple sub- quadratic gemm- based architecture. Advances in Neural Information Processing Systems, 36, 2024.
Daniel Y Fu, Elliot Epstein, Eric Nguyen, Armin Thomas, Michael Zhang, Tri Dao, Atri Rudra, and Christopher Ré. Simple hardware-cfficient long convolutions for sequence modeling. arXiv preprint wxXiv23302.06646 2023.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.0075 2023.
10

---

Published as a conference paper at ICLR 2026
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1474-1487. Curran Associates, Inc., 2020.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. arXiv preprint urXiv:2/11.0000 2021a
Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré. Com- bining recurrent, convolutional, and continuous-tima models with linear state space layers. Ad- vances in neural information processing systems, 34:572-585, 2021b.
Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective as structured state spaces. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: /ttp::s///pperevlee
het/forumt i d== iSo jot.sSr
Elad Hazan and Karan Singh. Introduction to online nonstochastic control. arXiv:2211.0961 2022.
arXiv preprint
Elad Hazan, Karan Singh, and Cyril Zhang. Learning linear dynamical systems via spectral filtering. In Advances in Neural Information Processing Systems, pp. 6702-6712, 2017.
Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. Spectral filtering for general linear dynamical systems. In Advances in Neural Information Processing Systems, pp. 4634- 4643, 2018.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Opti- mization, 2(3-4):157-325, 2016.
Coleman Richard Charles Hooper, Schoon Kim, Hiva Mohammadzadeh, Michael W. Mahoney, Sophia Shao, Kurt Keutzer, and Amir Gholami. KVQuant: Towards 10 million context length LLM inference with KV cache quantization. In The Thirty-eighth Annual Conference Neu- ral Information Processing Systems, 2024. URL httph:tpp///cc..... /tlLhttpp//opeeeeeeee.... 01Xotew9Du
Norman P Jouppi, Doe Hyun Yoon, George Kurian, Sheng Li, Nishant Patil, James Laudon, Cliff Young, and David Patterson. A domain supercomputer for training deep neural networks. Communications of the ACM, 63(7):67778, 2020.
Yuhong Li, Tianle Cai, Yi Zhang, Deming Chen, and Debadeepta Dey. What makes convolutional models great on long sequence modeling? arXiv preprint arXiv:2210.09299 2022.
Y Isabel Liu, Windsor Nguyen, Yagiz Devre, Evan Dogariu, Anirudha Majumdar, and Elad Hazan. Flash stu: Fast spectral transform units. arXiv preprint WeXiv22409.10480 2024.
Stefano Massaroli, Michael Poli, Dan Fu, Hermann Kumbong, Rom Parnichkun, David Romero, Aman Timalsina, Quinn McIntyre, Beidi Chen, Atri Rudra, et al. Laughing hyena distillery: Extracting compact recurrences from convolutions. Advances in Neural Information Processing Systems, 36, 2024.
Harsh Mehta, Ankit Gupta, Ashok Cutkosky, and Behnam Neyshabur. Long range language model- ing via gated state spaces. In The Eleventh International Conference on Learning Representationss 2023.
Costin-Andrei Oncescu, Sanket Purandare, Stratos Idreos, and Sham Kakade. Flash inference: Near linear time inference for long convolution sequence models and beyond. arXiv preprint arXiv:2410. 12982, 2024.
Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pas- canu, and Soham De. Resurrecting recurrett neural networks for long sequences. arXiv preprint arXiv:2303.00 06349 2023.
11

---

Published as a conference paper at ICLR 2026
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing
Systems 32, pp. 8024-8035, 2019.
URL performance deep learning Library.
9015 pytorch an imperative style high-
pdf
Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. In International Conference Machine Learning, pp. 28043-28078. PMLR, 2023.
Ofir Press, Noah A. Smith, and Mike Lewis. Train short, test long: enables input length extrapolation, 2022. hRKLatttss//aaa....////a/////// 12409
Attention with linear biases
Noam Shazeer. Glu variants improve transformer. arXiv preprint arXlv:2002.05202, 2020.
Jiaxin Shi, Ke Alexander Wang, and Emily Fox. Sequence modeling with multiresolution convo- lutional memory. In International Conference on Machine Learning, pp. 31312-31327. PMLR, 2023a.
Jiaxin Shi, Ke Alexander Wang, and Emily B. Fox. Sequence modeling modeling with multiresolution convo- 638
lutional memory, 2023b. /olLitttss:/rxxx.oorrg/////
Jimmy T.H. Smith, Andrew Warrington, and Scott Linderman. Simplitied state space layers for quence modeling. In The Eleventh International Conference on Learning Representations, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- fion processing systems, 30, 2017.
Tianyi Zhang, Jonah Wonkyu Yi, Zhaozhuo Xu, and Anshumali Shrivastava. KV cache is 1 bit per channel: Efficient large language model inference with coupled quantization. The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:// Seenreeiewwnet/Eorree 2tt
12

---

Published as a conference paper at ICLR 2026
A EXPANDED ABLATION DETAILS
Ablations Without Prefill:
We conduct three ablations generation length, model depth, and model width starting each run from the < endoftext > token with no prefill cache. Specifically, we:
Vary generation length Lgen from 4096 126976.
Vary the depth of the model within [6, 8, 12] layers while keeping a fixed input dimension of 1024.
Vary the width of the model within [112, 896, 1024] while keeping a fixed number of layers at 12.
Ablations with Prefill: this set of ablations, we only consider the fully convolutional variant of FlashSTU-T. Generation is initiated from a prompt which we use in the prefill stage. We:
Vary the length of the input prompt Lprompt from 512 + 32768. The length of the generation Lgenn is varied from 4096 + 130560.
Vary the depth and width of the model in the same manner as in the ablations without prefill, and fix the input dimension to be 1024, the number of layers to be 12.
In both sets of ablations, our baseline for comparison is naive online convolution, where past acti- vations are stored and the convolution is recomputed across the entire sequence at each generation step. These configurations yield models ranging from 160.7IM to 689.48M parameters. Refer to Appendices B.2 and Appendix B.3 for more details.
Ablation on cache size K Across all our previous experiments. we set the FutureFill epoch length to the theoretical optimum K / LLgen log Lgen (Theorem 2 To abate this choice, we consider a fixed generation length Teg of 65536 tokens without prefill, and we sweep K using fully convolutional FlashSTU-T of various sizes between 417.08 M and 826.05M.
B ADDITIONAL IMPLEMENTATION DETAILS AND ABLATIONS
B.1 ADDITIONAL IMPLEMENTATION DETAILS
All experiments were run on a single NVIDIA H100 GPU. All timings were measured over three independent runs. For each configuration, standard deviation over the remaining two. Error bars represent these sample standard deviations and are omitted whenever the standard deviation is below 0.01 Appendix timing tables report wall-clock decode time in seconds; throughput can be calculated via Lgen/T.
discard the first and compute the mean and sample
We employ the FlashSTU-T architecture from Liu et al. (2024). Our ablations use either hybrid variant alternatin between STU-T blocks and sliding window attention layers or fully convo- lutional STU-T only variant. Inputs are tokenized with the o200k_base tokenizer and embedded with tied weights between the input embedding and output unembedding matrices. We add special tokens (<1 eeeendo
>>, < endo |>) to signal generation boundaries.
For our attention layers, we leverage FlashAttention v2 (Dao et al. 2022a Dao 2024 with ALiBi positional encodings (Press et al. 2022). Each MLP layer has a hidden dimension 12x the input dimension.
Let æ F2. Ty E Rdd be the inputs the Spectral Transform Unit (STU) layer. the STU leverages
k = 48 spectral filters .i,..., de E R2,, with L 2 f, to compute U, = Σ It-s (5(() E Td..
The STU maintains learned parameters M, Ix to compute output 2 ΣØ= Mj Uy. Thus, the STU layer involves k convolutions per auto-regressive generation. The STU-T represents the Spectral Transform Unit with the tensordot approximation as introduced in Liu et al. (2024). For an STU with tensordot approximation, rather than maintaining k matrices M, aa concatenated as M E dxxxxd we approximate M M x (2), with (1) E kx and (2) E Rdxd This allows for a more convenient computation, as we can compute xz+1 = Σ (M O Makers [i]. where Mallers = (ø....., Φx] ())) e R and 2 denotes element wise product. Thus, the STU with tensordot approximation requires only d convolutions per token. Although the STU
13

---

Published as a conference paper at ICLR 2026
performance guarantees on learning linear dynamical systems (Appendix D.2) no longer holds for the tensordot approximation, the STU-T retains practical performance as shown in Liu et al. (002))
Convolutions within each STU-T block are implemented via an FFT-based operation: given batched inputs V E _Bxh and filters w E IR Bxt,, we zero-pad both to the next power-of-two length RFFT when memory allows, perform real-valued FFTs (rfft), multiply pointwise in the frequency domain, and invert back with irfft. This yields the causal convolution output in O(FFFT log (FFT) time, which significantly faster than direct convolution for long sequences. Note that, for memory reasons, we do this padding to the next power-of-two only for FFT sizes below 131072. In our PyTorch implementation (Paszke al., 2019), we cast inputs float for FFT compatibility, and finally truncate the result to the causal FutureFill window before casting back to the original dtype.
Time per stp
2000
Bux Paturchi
2000
Figure FlashSTU-T architecture. Figure from Liu al. (2024).
FlashSTU Liu et al. (2024) source code publicly available at htttss://iithut com/
hazan 1ab aaaaaaalllaas flash-stte stu It is released under the Apache License, Version 2.0, which permits
unrestricted use, modification, and distribution with attribution.
PyTorch (Paszke al., 2019) is used for the implementations and associated experiments, in the current section 5.2 of the main paper and section B of the Appendix. Py PyTorch's 's code is hosted athttps://githie com/ http//ytrccchcco syttorch/yytor.. pytorch (tag v2 0. 0) and distributed under the BSD 3-Clause License, allowing use and redistribution with minimal restrictions.
FlashAttention (Dao al., 2022a Dao 2024 is publicly available ltttps://githtti com/ Sto-AlLab/flashiy at ent ion As is PyTorch, FlashAttention is distributed under BSD
3-Clause License, allowing use and redistribution with minimal restrictions.
B.2 ADDITIONAL ABLATIONS, WITHOUT PREFILL
Parameeter coant laput dim
Layer count
Cuche Type
Decode generation length Legn
4096
N192
16384
32768
65536
128976
160.71M
512
6
Fgached FutureFill 9.51
0.01
18.42
0.03
37.08
0:05
74.05
0.30
147
0.15
322 28
0.06
180 13M
512
Epoched FutreFill
11.85
0.01
23.60
0.05
46.87
0.03
93.29
0.08
187
12
0.55
416.87
01.5
218 9834
512
12
Epached Futurchil
17.02
0.07
33.85
0.02
68.20
0.09
135.70
0.53
272
35
0.21
611.70
0.57
907. 62M
896
G
Epoched Futurchil 9.35
0.01
18.60
0.04
37.83
0:07
74,70
4 0.15
170
0.03
468.14
0.04
417
896
Tpached FutunFFill
11.77
0:01
0.03
47.12
94.05
0:711
210
98
613.40
12
Epached Putrccill
0.20
Epoched PuurcHill
0.02
75.21
521.45
237.20
670.75M
Lpocced FutureFill
17.07
34.07
140.32
347.01
1009.36.
0.02
Baseline
0.02
180-13M
19.33
96M
512
12
Baseline
13.85 0.001
27.83
55. 060
75 0.05
360
35
1035. 73 0.24
357 62M
806
Baseline
7.87 0.001
15.06
35.68
92.39
0.07
265
51
0.09
706.04
417 1SM
806
8
Basetin:
10.20
11.01
20.61 0.01
46.13
0.04
119.35
0.06
346
97
0.68
1848
45 1.06
535. 90M
806
12
Baseline
14.51 2:0.0 0:01
29. 88 00062:000
66.58
174
2 0.02
511
0.08
1555 87 0.07
437 81M
1024
6
Baselin
8.00 0.01
16.51
38.19
100.51
292
20
0.08
867.65 0.
515. J0M
1024
Baseline
10.99
0.01
21.
49.05
130.20
0.04
381
0.03
1167 59 0.11
670.76M
12
Baselin:
14.72
30.35
190.12
581
1731.67
Table 3: Decode time (in s) for STU-only models, without prefill.
14

---

Published as a conference paper at ICLR 2026
Parameeter count Iuput Layer count
Type
generatinn length Trges
4016
5192
16384
32768
65536
126976
163.0834
512
6
Epoched FutureFill
9.51
18.91
0.10
38.
00
0.02
75.
0.03
151.09
0.40
2933 22
0.04
183. 23M
512
Eprched FutunFill
12:11 + 0.01
24.01
+ 0.02
48 88.41-
0.05
96.5
0.31
195
0.01
370.8: 8:
0.24
633
512
13
Lpoched FuureFiil
16.89 0.00
30. 73
0.01
67
22
9.11
134.71
0.18
269.53
0.08
526.85
0.64
364. 78M
896
Lpoched Tuurefiil
9.83 0.00
19.68
30 10
0.02
18.50
156.52
0.45
315 21
1.83
Epsclted FutncFill
+
0.03
0.02
Epoched
Epoched FutureFill
12:21
24.44
0:000
0.00
1.4.9
0.23
689.46M
1024
12
Epoched FuturoFill
17.50
$4.93
$4.03:00.01
69.
139.13
0.72
281.83
0.00
008
0.16
Roseline comu)
145,
23M
Bascline
47
0.09
0.10
223
512
12
Baseline
0.00
31.00
0.16
0:00
264.36
0.30
364-775
200
Bascline
8.90
0.01
17.89
17.89+00.00
0.01
36.81
0.17
72.60
= 0.02
171
0.14
407
0.40
426 83M
896
8
Baseline
11:24
0.01
22.54
0.07
44
0.03
92.02
0.05
223.63
0.04
801
28
0.28
550 3.M
896
12
Baseline
15:94 1: 0.01
31.91
0.02
83 30
0.20
132.32
0.22
324
0.04
865
40
0.15
447.1 147-1774
1924
6
Bascline
3,88 4 0.02
17.75
0.03
36.
0.16
73.99
16
182
0.15
208
0.32
1024
Baseline
11:27 2:
0.03
95.20
0.02
257.
0.01
889.48M
1024
Baseline
31.90
03
0.12
136.06
0.14
340.37
967
0.12
Table 4: Decode time (in s) for Hybrid models (50% STU 50% Attention), without prefill.
B.3 ADDITIONAL ABLATIONS, WITH PREFILL
Prefill times reported below have been measured separately from generation times, i.e. generation times below do not include prefill times.
B.3.1 PREFILL LENGTH IS LARGER THAN (OR EQUAL TO) CENERATION LENGTH
During prefill, the minimal FFT length required to recover the linear convolution of prompt of length Lpnonpt and a generation of length Lngenerationn is
N next. ncxt_pow2 prrompp + (Lprompt + Lgeneration) 1).
-
For Lprompt 16 384 and Leeneration E {4 096, ... 32 768), this yields N 65 536. This is why Table 5 reports only the average prefill time and its sample standard deviation. Likewise, for Leromps 32 768 and Lgeneration E 096..... ... 16 384], the minimal FFT size is N 131 072, and Table 6 summarizes the corresponding average prefill times and their sample standard deviations.
Decode at generation length Lyen
Parameter count Input dām Layer count
Cache Type
Prefill Time
40%6
8192
16384
32768
160.71M
512
6
Epoched PutureFill
4.03
10.18 1 0.01
20.34
1: 0.03
40.30
+ 0.01
80.21
0.07
130
512
8
Epoched FutureFill
5.35
13.08
4 0.03
26.
51.45
2 0.01
103.50 80 - 0.21
218 98M
512
1/2
Epoched FutureHill
8.01 = 0.02
18.90
0.01
37
6
0.02
75.07
4: 0.08
149.97 4 0.08
337. 62M
896
6
Epeched FuturcFill
7.04::0.01 0.01
10.10
0.01
20.18
1
0.01
10.46
0.224
80.75 2:53::00 0.11
Epoched FutureFill
52.35
1024
Epoched FutureFill
515. 4AM
1024
Epoched FutureFill 10.74 0.03
13.08 1 0.01
26.22
0.04
52.37 2 0.02
104.91
0.09
535.99M
896
12
Epoched FutureFill 13.96 1: 0.02
19.03
37.64
1: 0.16
76.09
1: 0.28
152.01
1 0.06
670.72 75M
1024
12
Epoched FutureFiil
16.01 1: 0.02
18.91 4: 0.03
37.71
4: 0.16
75.99
1: 0.07
152.27
1. 0.20
160.7V 71M
512
Baseline
4.03 + 0.01
8.52
17.82
39.09 0.01
92.37
180
512
8
Baseline
5.36
10.99 + 0.02
23.13 0.01
50.94
120.74 = 0.05
218 96M
512
12
Baseline
8.02
16.17
0.01
33.96
74.95 - 0.04
178.56
0.01
357 62M
896
Baseline
7,056
12.11
25.78
0.02 57.09
134.20
0.03
417 08M
896
S
Buseline
9.37
15.34
33.73
74.74
175.99
0.05
Baseline
1024
Baseline
17.49
$1.94
0.02
193.78
535. 99.
896
12
Baseline
14.00
23.
0.01
49.34
109.55
0.04
259 24
0.02
650.75M
1024
12
Baseline
16.06
25.63
54.37 + 0.03 120.34 4 0.04
285 88
- 0.13
Table 5: Decode time (in s) for STU-only models, with prefill on an input prompt of length Ieproups 16,384 tokens.
15

---

Published as a conference paper at ICLR 2026
Parameter Input dim Layer
Cache Type
Prefil Time
Decode time at generation length Lgen
4096
8192
16384
160.71M
512
Epoched FutureFill
8.01
10.11 - 0.01
20.10 = 0.02
40.02
0.08
180.13M
512
8
Egoched FatureFill 10.58
0.01
13.07
- 0.01
25.96
52.11
0.19
218.98M
512
12
Epoched FatureFill 15.81 + 0.03
16.93
- 0.01
37.70 0.04
75.89
0.02
357. 62M
896
Epoched FutureFill 14.01
0.05
10.05
0.01
20.13
40.26
0.04
417 08M
896
Epoched FutureFill 18.66
0.04
13.18
0.001
26.29
0.04
52.36
0.04
437.5
1024
Epoched FutureFill 16.05
0.03
10.11
20.15
40.33
515.46M
1024
8
Egoched FutureFill 21.40 + 0.03
13.12
0.05
26.18
0.02
52.22
0.09
535
Epoched FutureFill 27.74
0.36
37.89
0.04
670.75M
1024
12
Epoched FutureFill 31.98
0.09
19.06
= 0.10
37.80
0.01
0.61 75.06
160.71M
512
6
Baseline
7.99
12.08
24.93 = 0.01
53.43 0.01
180.
512
Baseline
10.60
15.85
32.83
0.02
218.98M
512
12
Baseline
15.84
23.39 0.00
48.50
0.01
103.64
+ 0.02
357.6 357.62M
896
Baseline
14.03
17.48
36.20
0.01
77.18 0.01
417.0% 08.M
896
Baseline
18.62
22.96
47.51
101.50
0.02
437 81M
1024
Baseline
16.05
19.22
39.83
85.10
0.01
515 16M
1024
Baseline
21.28
25.23
52.31
0.02
111.92
0.06
635. 99M
896
12
Baseline
27.82
33.83 = 0.01
70.03
= 0.01
149.86 + 0.02
1024
Baseline
77.15
0.02
Table 6: Decode time (in s) for STU-only models, with prefill on an input prompt of length Lprompe 32,768 tokens.
B.3.2 PREFILL LENGTHI IS SMALLER TIIAN (OR BQUAL TO) GENERATION LENGTII
In the ablations shown this section, the prompt length is fixed pepmpes the column headers refer to the total sequence length T, = pprompt + I.gneratiion rather than to the generation length gen
alone. For instance, in the case of Lprompt = 512: = 8192 means that there are 512 tokens in the input prompt and 7680 generated tokens.
Parameter Impet dim Layer
Cache Type
Total length L( Lpen leprompe)
4076
32768
LA1072
Epeched Futureflll
0.17
0.94
417. 417.08M
856
Epoched FutureFill
11.24 0.03
28.5 91.911
0.08
49.54
0.07
0.40
228.71
0.12
0.21
536. 99M
806
12
Epochal FuturFill
16.22
2: 0.07
$1.49 0.08
71.42
0.03
145
0.09
334.20
0.17
976 05
1.00
315.4GM
1024
Epoched Futuecilll
11.13
23
19.57
0.02
101.80
0.22
245.07
0.45
735.22
0.11
670.75M
1024
12
Epoched FuttreFilll
18:33
0.02
10
72.42
100.12
36135
0.29
1007 50
180. 1.3M
612
Bascline
8.50 -: 0.02
18. 26 0.01
37.61
0.00
85.27
0.12
245.27
0.03
738
0.92
218 95M
512
12
Baseline
11.90
25.00
53.23
0.04
127. 73
0:14
339.73
0.25
105-1.02
0.01
417.08M
806
Bascline
8.53 0.003
19.20
0.04
44.06
0.02
119.
119.35-0
0.08
84
0.09
1111.11
0.08
90M
856
Baseline
12.59
21:38
64.81
0.06
512.10
0.05
1648.08
1024
8.94
19.
0.05
0.03
1238
0.02
Table 7: Decode time (in s) for STU-only models, with prefill input prompt of length Teprompt 512 tokens.
Prefill rimes associated with total length L(= Lyen + L Lprompt)
Parameter count Input dim Layer count
Cache Type
4096 8192 16384
32768
65536
131072
180. 13M
512
8
Epached FuturefFill 0.20 0.20
0.21
0.21
0.25
0.38
218.98M
512
12
FutureFill 0.30
0.30
0.31
0.32
0.36
0.57
417.08M
896
8
Epoched FutureFiil 0.39 0.39
0.40
0.41
0.46
0.70
635.99M 99M
896
12
Epoched FutureFill 0.58
0.58
0.59
0.62
0.69
1.05
1024
Epoched PutureFill 0.39
670.75M
1024
12
Epoched FutureFill 0.59
0.59
0.60
0.63
0.72
1.13
180. 13M
512
8
Baseline
0.20 0.20
0.20
0.20
0.20
0.20
218.98M
512
12
Buseline
0.30
0.30
0.30
0.30
0.30
0.30
417.08 088
896
Baseline
0.38
0.38
0.38
0.38
535. 99M
896
12
Baseline
0.57 0.57
0.57
0.57
0.57
0.57
615.46M
1024
Baseline
0.39
0.39
0.39
0.39
0.39
0.39
670.75M
1024
12
Baseline
0.58
0.58
0.58
0.58
0.38
0.58
Table 8: Prefill time (in s) for STU-only models, associated with an input prompt of length Ipprmpp 512 tokens.
16

---

Published as a conference paper at ICLR 2026
Parameter count Input dim Layer count
Cache Type
Total Ieugth 1/== Ligo Veyeomae)
4096
8192
16384
32768
65536
131072
180, 13M
512
8
Epoched Funureflll
9.77 =: 0.05
22.73
4 0.11
48.54
0.20
101.12
12
4: 0.35
205
98
1.05
480 10
1.05
218. 98M
512
12
Epoched Finurefill
11.86 0.002
32.30
0.06
69
0.04
143.38
0.00
281
0.62
670.61
1.28
417.06M
S96
6
Egoched FunaeFFill
9.68 = 0.02
22.32
0.02
48.05
0.03
99.31
4 0.21
226
0.20
658
0.30
685.90M
896
12
Egocled FunaeFiill
13.92
0.04
82.82
0.08
60
43
0.01
144.03
9:11
890
0.61
974-19
0.54
$15. 46M
1024
Epuched Finarefill
0.57 0.00
22.43
0.00
41:71
11711:00:35
0.13
100.29
0:30
242
0.20
733.30
0.12
870.75M
1024
Epoched FinareFill
13.63 0.02
31.80
0.07
68.55
143.44
1 0:40
25
1000
2.16
150.18M
512
Baseliue
7.13 = 0.01
16,62
+ 0.03
36.
0.07
86.23
+ 0.09
242
88
0.12
736.
0.13
218.98M
512
12
Baseluee
10:27
0.01
23.91
+ 0.01
51.78
0.32
126,30
0.03
367
94
0.41
1091
50
0.35
417.06M
596
Rasoline
7.00 0.00
17.94
0.03
0.06
118.07
0.08
0.04
0.00
635.80M
Reseline
10.83 0.01
25.61
0.18
0.08
1645.
0.11
Baseline
1237.85
0.11
187.76
0.07
1834.96
0.18
Table 9: Decode time (in s) for STU-only models, with prefill on an input prompt of length
Dprompt 1024 tokens.
Parameter count Input dim Layer count
Cache Type
Prefill times associated with total length L(= Lgen Lprompt)
4096 8192
16384
32768
65536
131072
180. 13M
512
Epoched FutureFill 0.38 0.39
0.39 + 0.09
0.10
0.43
0.56
218.98M
512
12
Epoched FutureFill 0.58 0.58
0.59
0.60
0.64
0.85
417. 117.08M
896
8
Epoched FutureFill 0.66 0.67
0.68
0.69
0.71
0.98
896
Epoched FutureFill 0.99
1.00
1.01
1.03
1.10
61M.46M
1024
8
Epoched FutureFill 0.76
0.76
0.77
0.79
0.84
1.12
670.75M
1024
12
Epoched FutureFill 1.13 1.14
1.15
1.18
1.26
1.68
180. 13M
512
Baseline
0.38 0.38
0.38
0.38
0.38
0.38
218.98M
512
12
Baseline
0.58 0.58
0.58
0.58
0.58
0.58
417.08M
896
8
Baseline
0.66 0.66
0.66
0.66
0.66
0.66
M35.99M
896
0.99
615.46M
1024
8
Baseline
0.75 0.75
0.75
0.75
0.75
0.75
670.75M
1024
12
Baseline
1.12 1.12
1.12
1.12
1.12
1.12
Table 10: Prefill time (in s) for STU-only models, associated with an input prompt of length
Lppropt 1024 tokens.
Parameter count Input dim Layer
Cache Type
Total Irngth = Jyan [epermat)
4996
16384
32768
65536
Epoched FonaretMll
195.44
450.41
0.70
0.02
662.80
0.35
417.06M
FutarcFill
595.00M
FutecFill
9.27
27.78
0:46
72
0.43
815.46M 46M
1024
Cpoched Funarefill
8.38
0.05
19:11
0.00
44.82
10121.0111
0.12
06.74
0.10
237
0.20
722.81
0.32
670.75M
1024
12
Epocled Fotareilll
9.09 +: 0.01
27:20
0:08
63.28
0.30
138.06
06
0.72
346.51
0.26
1077.220 0.62
0.05
218.96M
Biseline
48.35
122
0.14
354.58
1089.95
417.06M
896
Baseline
5.06
15.12
0:01
41.17
1:117:000
0.04
115.46
49
343.68
10T
0.05
535.00M1
896
12
Reseline
7:22 = 0.01
22.08
0:03
50.62
0.04
168.
0.08
506
506.41
0.35
1642.43-
0.11
513.
1024
8
Daseline
5.13
0.01
16.09
0:01
44.29
29 0.02
126.11
11
0.02
378 62
0.05
1234,521
0.04
670.75M
1024
12
Rascline
7.23 0.02
22.94
+ 0.02 64.01
0.05
184.11
= 0.04
557.94
0.41
1831
0.38
Table 11: Decode time (in s) for STU-only models, with prefill on an input prompt of length Lprompt 2048 tokens.
Parameter count Input dim Layer count
Cache Type
Prefill times associated with total length L(= Lgen + L Lprompt)
4096
8192
16384
32768
65536
131072
180, 13M
512
8
Epoched FutureFill 0.72
0.73
0.74
0.71
0.77
0.91
218.98M
512
12
Epoched FutureFill 1.09
1.09
1.10
1.11
1.15
1.36
417. 07M
896
Epeched FutureFill 1.27
1.27
1.28
1.29
1.34
1.58
635 99M
896
12
Epoched FutureFill 1.89
1.90
1.91
1.93
2.00
2.36
515.
1024
Epeched FutureFill
670.75M
1024
12
Epoched FutureFiil
2.16
2.17
2.18
2.21
2.29
2.70
13M
512
8
Baseline
0.73
0.73
0.73
0.73
0.73
0.73
98M
512
12
Baseline
1.09
1.09
1.09
1.09
1.09
1.09
417.08M 0808
896
Baseline
1.26
1.26
1.26
1.26
1.26
1.26
535. 99M
896
12
Baseline
1.88
1.88
1.88
1.88
1.88
1 1.88
515.46M
1024
Baseline
1.44
1.44
1.44
1.44
1.44
1.44
670.75M
1024
12
Buseline
2.14
2.14
2.14
2.14
2.14
2.14
Table 12: Prefill time (in s) for STU-only models, associated with an input prompt of length Ieprompt 2048 tokens.
17

---

Published as a conference paper at ICLR 2026
Parameter count Input dim Layer count
Cache Type
Total length I.(
Lyyon Lggromgs)
8192
16384
32768
65536
180. 13M
512
8
Epuched FuturcFill 12.70 =: 0.01
$7.95
0.11
88.26
0.12
189
96
0.51
438.92
0.69
218. 9SM
612
12
Epoched FuturcHill
18.58
05,
0.03
129.42
0.15
277
0.29
645.49
417 00M
896
Epuched FuturcFill
12.81:::0.
38.27
0.19
59.61
0.113
212
0.16
630.59
0.220
535.99M
896
Epoched PurareFill
18.53
55.65
0.01
130.20
0.330
307
0.13
923.36
0.33
Epuchal FuturcFill
89.17
701.11
Epoched
0.12
129.21
180.13M
512
8
Roscline
9.50 + 0.02
28.67 0.15
79.24
235.57
0.12
729.12
0.07
218.96M
512
12
Baseline
13.69
11.50
11.50:00000
116.01
0:00::000 0.0.4
347.99
99
0.25
1062.00
0.09
117.06M
Baseline
52.33
Boseline
10.93
39.15 0.03
0.01
373.
00
0.07
1229.
0.15
670.75M
1021
12
Baseline
15.70
56.81 = 0.02 176.90
2 0.15 550.
0.03
1824
0.01
Table 13: Decode time (in s) for STU-only models, with prefill on an input prompt of length Lprompt 4096 tokens.
Prefill times associated with total length l.(= Lyon Lepromp!)
Parameter count Input dim Layer count
Cache Type
8192
16384 32768
65536
131072
Epoched FutureFill
218. 98.
512
12
Epoched FutureFill 2.10
2.11
2.13
2.17
2.35
417.08M
896
Epoched FutureFill 2.46
2.47
2.48
2.53
2.74
99M
896
12
Epoched FutureFill 3.67
3.68
3.71
3.78
4.10
46M
1024
8
Epoched FutureFill 2.81
2.81
2.83
2.89
3.13
670.75M
1021
12
Epeched FutureFill
4.20
4.21
4.32
4.68
180. 13M
512
Baseline
1.40
1.40
1.40
1.40
1.40
218.98M
512
12
Baseline
2.08
2.08
2.08
2.08
2.08
417.00 07.08M
896
8
Baseline
2.45
2.45
2.45
2.45
2.45
896
3.65
515. 46M
1024
8
Baseline
2.79
2.79
2.79
2.79
2.79
670.75M
1024
12
Baseline
4.16
4.16
4.16
4.16
4.16
Table 14: Prefill time (in s) for STU-only models, associated with input prompt of length
Ixprompt = 4096 tokens.
B.4 ADDITIONAL. ABLATIONS THE EROCHED-FUTUREFHE CACHE LENGTH K, WITHOUT PREFILL
Input Layer
Type
DRM
Epechaal FutezFill
0.19
+
226.28
0.18
230.112
90M
16
Lioccted Fourrehll
472
447.05
43%
434 49
0.40
439 299.29
0.46
454.67
B85-40EM
1024
8
Epoched Futu:
262 35
0.17
248.88
0.57
243.40
0.28
241.89
0.10
241.61
0.45
257.85
0.06
670 75M
10226
12
Eppeched Putrrfiil
364. 17
0.024
364 04
1 0.52
353.01
0.17
352 96
0:20
358
0.15
377.52 0.53
820 85M
10044
16
Epocted FutreFill 565.50 0.17
478.47
0.2
467.12
1 0.18
463.74
0.35
471.32
606.88
0.13
Table 15: Decode time (in s) for STU-only models for fixed generation length of 65,536 tokens
(without prefill).
B.5 ADDITIONAL TIMING BREAKDOWNS
Generation length
4096
8192
16384
16384
32768
65536
126976
Prefill (in tokens)
32768
32768
32768
N/A
N/A
N/A
N/A
STU (= FFT)
26.76
56.02
121.77
31.90
102.38
362.86
1299.10
MLP
5.80
11.78
24.22
22.04
49.47
111.93
242.95
RMSNorm
3,90
7.85
16.08
14.29
32.19
73.21
159.49
Dropout
0.63
1.27
2.61
2.28
5.19
11.80
25.80
Embedding 0.13
0.24
0.46
0.40
0.89
2.02
4.50
Table 16: Module-wise times (in s) generation length (batch=l) 1) for the 670.75M-paramett STU-only model. Baseline model (naive convolutions).
18

---

Published as a conference paper at ICLR 2026
Generation length
4096
8192
16384
16384
32768
65536
126976
Prefill (in tokens)
32768
32768
32768
N/A
N/A
N/A
N/A
STU (=
9.79
19.41
38.83
35.26
73.06
191.76
637.01
MLP
5.16
10.28
20.69
18.21
37.42
86.89
209.14
RMSNorm
3,45
6,82
13.58
12.31
25.16
57.71
137.98
Dropout
0.55
1.10
2.19
1.95
3.97
9.06
21.50
Embedding
0.10
0.19
0.37
0.34
0.70
1.60
3.84
Table 17: Midule-wise times (in s) vs. generation length (batch=1) for the 670.75M 570.75M-parameter STU-only model, using FutureFill.
B.6 PRECISION THE FFT DOWNSTREAM TASKS
Our current implementation uses PyTorcc built-in FFT, which currently supports only float32, float64, and float16. We perform ablations on 330M parameter-pp preterree- hybrid-STU model using end-to-end 6 but upcasting the FFT to fpl when needed, to show that it does not degrade accuracy. The baseline kept end-to-end bf16. The pretrained model openly available at Hazan-I Laaraan-Labb/aaaae
WinoGrande
HellaSwag
PIQA
FutureFill, upcast to fp32
0,51381
0.3045
0.6553
FutureFill, upcast to fp16
0.5090
0.3047
0.6551
Baseline (convolution), bf16
0.5160
0.3046
0.6534
Table 18: Evaluation scores on downstream tasks for 330M hybrid-STU, using different precisions for the FFT. Other calculations and weights are kept in bf16.
C EXPERIMENTAL COMPARISON WITH TRANSFORMERS
We experimentally evaluate Epoched-FutureFin (Algorithm T which has a runtime of 3 Vlog L) and Continuous- (Algorithm 2 which has runtime of OlL L) against the naive implementation convolution which has runtime of O(L2) when generating tokens from scratch. We also provide comparison with self-atrention based Transformer model (with a standard implementation of KV cache and with the same hidden dimension, number of lay- and commensurately chosen other parameters, next subsection for complete details these models).
For increasing values of L, measure the time it takes for the model to generate L tokens from scratch (i.e. no prompt provided). In Figure we plot the total generation time, as functions of L. We see the behavior that is expected: the naive decoder runs in total time O(L?). similar to the decoder for transformer while our method EpochedFutureFill is able to achieve a significant sub-quadratic improvement.
19

---

Published as a conference paper at ICLR 2026
6000
NaiveConvalution
EpochedRutureFill
5000
Iransformer
Time [s]
3000
2000
1000
0.0
0.2
0.4
0.6
0.8
2.0
1s8
Figure 4: Total time for generating L tokens, as a function of L.
In the next section we provide the details of our implementation.
C.I EXPERIMENT DETAILS
For our experiments we consider two layer model with either multi-headed self-attention layers (referred to as Transformer) dimension (or the model dimension) of the networks are fixed to be 32, and for the Transformer we set the number of heads to be 4 and the key/value size to be 8. The networks do not have embedding or unembedding layers, and contain standard implementations of residual connections, layer-norms the STU
STU layers (referred to as convolutional network). The hidden
and feed-forward (FFN) layer between every attention STU layer. More information with tensordot approximation is available in Appendix B.I The FFN layer used in the experiments the FFNGeGLU layer proposed in Shazzer (2020). For the Transformer we employ standard implementation of KV-cache for efficiency (i.e. caching the KV values of previously generated tokens for every attention layer).
Since we have equated the hidden dimensionality of the network across all our settings, we can see that, naively computed, the number of flops per token of both the Transformer as well as the convolutional model are of the same order which is also observed in the experiments.
Finally the experiments in this section are implemented Jax (Bradbury et al. 2018 were per- formed on single Google TPUv2 machine (Jouppi et al., 2020).
D EXTENDED RELATED WORK AND DETAILS ON CONVOLUTIONAL SEQUENCE PREDICTION MODELS
D.I RELATED WORK
State space models and convolutional sequence prediction. Recurrent neural networks have been revisited in recent deep learning literature for sequence prediction in the form of state space models (SSMs), many of which can be parameterized as convolutional models. Gu et al.) (2020) pro- pose the HiPPO framework for continuous-time memorization, and shows that with a special class of system matrices (HiPPO matrices), SSMs have the capacity for long-range memory. Later works (Gu et al.] 2021b aj Gupta et al.) 2022] Smith et al.) 2023) focus on removing nonlincarities and devising computationally efficient methods that are also numerically stable. To improve the performance of SSMs on language modeling tasks Dao et al. (2022b) propose architectural changes as well as FFT algorithms with better hardware utilization, to close the speed gap between SSMs and Transformers. Further investigation in Orvieto et al. (2023) shows that training SSMs is brittle in terms of various hyperparameters. Many convolutional models have been proposed for sequence modelling, e.g. Fu et al. (2023); Li et al. (2022); Shi et al. (2023a). These works parameterize the convolution kernels with specific structures. The Hyena architecture was proposed in Poli et al.) 2023) and distilling it into an SSM was studied in Massaroli et al. (2024). Other proposed convo-
20

---

Published as a conference paper at ICLR 2026
lutional models include the LongConv (Fu al.
2023) and SGConv (Li et al. 2022) architectures, as well as nulti-resolution convolutional models (Shi et al. 2023b).
Spectral filtering. A promising technique for learning in linear dynamical systems with long memory is called spectral filtering put forth in Hazan et al. (2017). This work studies online pre- diction of the sequence of observations Ye. and the goal is to predict as well the best symmetric LDS using past inputs and observations. Directly learning the dynamics is non-convex optimiza- tion problem, and spectral filtering is developed as an improper learning technique with an efficient, polynomial-time algorithm and near-optimal regret guarantees. Different from regression- based methods that aim to identify the system dynamics, spectral filtering's guarantee does not depend on the stability of the underlying system, and is the first method to obtain condition number-fiv free regret guarantees for the MIMO setting. Extension to asymmetric dynamical systems was further studied in Hazan al. (2018). Spectral filtering is particularly relevant this study since it is convolu- tional model with fixed filters. Thus, our results can be immediately applied to this technique and imply provable regret bounds with guaranteed running time, improving upon the state of the art.
Online learning and regret minimization in sequence prediction. The methodology of online convex optimization, see e.g. Hazan et al. (2016), applies to sequences prediction naturally. In this setting, learner iteratively predicts, and suffers a loss according to an adversarially chosen loss function. Since nature is assumed to be adversarial, statistical guarantees are not applicable, and performance is measured in terms of regret, of the best algorithm in hindsight from a class of predictors. This is a particulary useful setting for sequential prediction since it requires methods. Sequential prediction methods that apply to dynamical systems are more complex as they incorporate the notion of a state. Recently the theory of online convex optimization has been applied to learning in dynamical systems, and the spectral filtering methodology was developed in this context. See Hazan & Singh (0022) for an introduction to this area.
the difference between the total loss and that
assumptions
the true sequence and leads to robust
In independent work Oncescu et al. (024) presents a very similar algorithm for inference with convolutional models, with a total runtime of O (T.) (same as our Continuous-FutturFFllll result) via the method of relaxed polynomial interpolation. Our algorithm builds on the simple and intuitive idea of FutureFill, allowing us to create a spectrum of trade-off' between compute and memory. An intermediate point on this spectrum is the Spooced-FFtturehee algorithm, which has streamlined implementation, low memory usage, and potentially stronger performance in practice.
D.2 MORE DETAILS ON CONVOLUTIONAL SEQUENCE PREDICTION MODELS
State Space Models
State space models such as those considered in Gu et al. (2021a) have shown considerable success and adoption for long range sequence modelling. They can be defined via the following dynamics equation of a Linear Dynamical System (LDS)
Ty = A + But, yt = Ca. + Du,
(2)
where u. y are the input and output sequences and A, B, C, D are the learned parameters. Vari- ous works deal with specifications of this model including initialization (Gu et al. 2020). diagonal versions (Gupta et al. 2022), gating (Mehta et al.) (202)) and other effective simplifications (Smith) et al. 2023). All these models can be captured by convolutional models since the output sequence y in equation can be written as
y= = + Du,
where the filter o satisfies o; C. Thus convolutional sequence model with learnable filters & generalizes these SSMs. However, SSMs are more efficient for generation as they can generate a token in constant time.
CongCo.vsSGCoon. The LongConv (Fu et al. 2023) and SGConv (Li ct al. 2022) architectures exploit the above connection and propose direct regularizations of the convolution kernel to bias them towards representing a state space model.
Spectral Transform Units. The STU architecture was proposed in Agarwal et al. (2023) based
on the spectral filtering technique for linear dynamical systems (Hazan al. 2017 2018). These
21

---

Published as a conference paper at ICLR 2026
Figure 5: FutureFill between input sequence and a convolutional filter.
convolutional sequence models based on carefully constructed filters that are not data-dependent. Let 01..... Ok be the first & eigenvectors of the Hankel matrix H given by
H HL=1 $
Pattada do E LRLL Pa = (a (o0,,)( .
The STU predicts according to the following rule Út Σe= Mi(Oi, uer-L), where Mise are learned projection matrices. Note that the inner products (ds,, V(:t-1)) L.) the outputs of Φ;; u. The STU architecture is particularly appealing for learning LDS with long memory, as demonstrated by its dimension-free sublinear regret guarantees for this setting (Agarwal al. 2023).
D.3 ALGORITHM SCHEMATICS
We provide illustrations of the FutureFill operation in Figure 5 describing our Algorithms/ and in Figures 6n 7
We further provide schematics
FutureFill cost O(L log
Compute A token - 0(k)
Overall:
pa. Auggt
8 Llgg
01,
Figure 6: Illustration for Algorithm
D.4 ALGORITHM FOR FAST AUTO-REGRESSIVE SEQUENCE GENERATION FROM A PROMPT
E FAST ONLINE CONVOLUTIONAL PREDICTION
In this section, we give a more detailed treatment on how FutureFill improves online convolutional prediction the context of regret minimization. When predicting sequence in an auto-regressive fashion, an online learner iteratively sees input u, and has to predict output ÿt. after which the true output yt is revealed. The goal is to minimize error according to a given Lipschitz loss function
mooe precisely, there are additional linear and constant terms depending on the exact filters used, such as 0--2+ 3 M Metl-+ + Σ Mr M L), see Agarwal al. (2023 for more details.
22

---

Published as a conference paper at ICLR 2026
16
Lgg
+
milt
[= 1
2,3
=- 4,5,67
Figure 7: Quasilinear Online Convolution using FutureFill: Figure shows the execution flow for Algorithm for convolving 8-length sequences. Input sequence u streams in an online fashion and filter is fully available to the algorithm. Colors representative of the size of the FutureFill operations performed and the time (also color-coded) highlights when the FutureFill operations were performed.
Algorithm 3 Fast auto-regressive sequence generation from prompt using FutureFill
1: Input: Generation length K > 0, L > 0. prompt PI.Z, convolutional filter & E RR+K
2: Set up FutureFill cache C R C < FutureFill(p, o).
3: Set up the online convolution algorithm with filter Φ and sequence length K, i.c. A t ContimuousFutureiillg
4: Running candidate token <- 0.
5: for t= 1, K do
6: Output 0r = C. +
7: Generate next token candidate y + A(Dr).
8: end for
(yee it). In online learning it uncommon to assume that the true output sequence was generated by the same family of models as those learned by the learner. As result the metric of performance usually taken be regret. Given a class of possible predictors, the goal minimize regret with respect to these predictors. For example, a linear predictor predicts according to the rule
MM (Wist, 91.-11)
M Σ Nath-j
The performance of a prediction algorithm A is measured by regret, or difference in total loss com- pared class of predictors 1I. such as that of linear predictors, e.g.
T
T
(egret,,(A) Σ Ee 014) - min Σ Ceve D.).
TEIl
This formulation valid for online sequence prediction of any signal. We are particularly inter- ested in signals that are generated by dynamical systems. A partially observed time-invariant linear dynamical system given by the dynamics equations
Tt+1 = Ax, + Bu, + Wt, 1/+ Cx, + Du: + St.
where 2, is the (hidden) state, u, the input or control to the system, and yı is the observation. The terms Sr are noise terms, and the matrices A, B, C. D are called the system matrices. A linear dynamical predictor with parameters A, B, C, D predicts according to
1-1
म AABCD(ULL (aa--11,--aaaa-
V1--1) = Σ
CA' 1 Bun + Duy-
23

---

Published as a conference paper at ICLR 2026
The best such predictor for given sequence is also called the optimal open loop predictor, and it is accurate if the signal is generated by an LDS without noise.
When modeling long-range dependencies, the class of marginally stable linear dynamical systems of particular interest. Marginally stable systems are systems whose dynamics matrix has eigen- values of magnitude up to 1, and thus observations Ye can depend inputs that arbitrarily far in the past. The long-range dependencies also make learning these systems challenging, and most techniques based on system identification do not have guarantees in this setting. The spectral fil- tering algorithm (Hazan et al. 2017) is a convex relaxation of the problem of learning marginally stable LDS online, and was the first algorithm to achieve sublinear, hidden dimension-fie free regret for learning systems with symmetric dynamics matrices. Spectral filtering uses convolutions to compute the prediction at each time step, and we demonstrate helow how FutureFill can naturally applied to accelerate this algorithm.
E.1 CASE STUDY: FAST ONLINE SPECTRAL FILTERING
We illustrate in more detail how the method works for the spectral filtering algorithm from Hazan et al. (017)) improving the total running time from O to ( log" L) while maintaining the same regret bound.
Algorithm 4 Efficient Spectral Filtering via FutureFill
1: Input: Number of filters N > 1.
2: Set variables {M] ... M E iR Xdin +- 0} and set fői...ØN' as the largest eigenvectors of Hy, the Hankel matrix corresponding to length-L sequences.
3: Initialize OnlineConvolution modules, one for each filter {.As (ox))))
4: for t- = 2, ..., do
5: Receive input token U2.
6: for k 1, 2, do
7: F2 - (we))
8: end for
9: Compute and predict d: = EE MfFF.
kk=
10: Observe y/, suffer loss l, (Mi Ilve Dell and update M + (l,(M).))
11:
end for
The main claim regarding the performance of Algorithm 4 follows directly from Theorems and and is as follows.
Corollary 7. Algorithm 4 with sequence length L guarantees the same regret bound spectral filtering (Hazan el al. (017) with context length L. Furthermore its computational complexity based on the online convolution module used are as follows:
If using Og L)..
1
Runtime O(L3/2 L).
Memory
If usiigg CortimonsFFuuurFFlllAlgggnnnn Runtime OLL L), Memory O(L).
DEFERRED PROOFS
Proof of Proposition 7 Note that by definition, [a b), Ei=1 a:bs41-5- We now consider the two cases: for 8 < 21. we have that
[a * biael 1.
Σ a.bs+1-1 b].
For the case when
> /1, we have that
s-ti
lautia b1:0-talo-t1
Σ
b
a
a:bst1-i
24

---

Published as a conference paper at ICLR 2026
where the last equality follows by redefining i = t1 Further have that
t- Σ
[FutureFill(anat) b))s
O4 041-1411 12-
on i+1 bb
Σ i=1
+1+1
where the second last equality follows by noting that aj is assumed to be for all j s 0 and the last equality follows by redefining i i+ Overall putting the two together get that
(o [FutureFill (11.1 8)1a-11 Σ ar 1100+1111
a. +1-+
Σ
aa.b
[a+b] s.
This finishes the proof.
F.1 PROOFS FOR ALGORITHM
Proof of correciness for Algorithm 7 Consider any time and the output dt- Let S / be the last time when Line 6 was executed, i.c. FutureFill was computed. By definition t' = Note the following computations.
01 = Σ 1141-5 03 +C, = Σ
U++1-3 65 + [FutureFilluuree <1x+k))=
1=1
d'+K-7
Ut+1-j 0j +
ue-jt1 Φrtj
1=1
Σ
U1+1-j 0j +
Σ
Ur Qr+j
1=1
==1
t-r
U1+1-j 03 + Σ
Ut Up-r- 0r+1
|=1
Σ U4+1-j :0 + +
Σ
Ut-j+1 0 [u d/+
+=
F.2 PROOFS FOR ALGORITHMM 2
Proof of Theorem 3 As can be seen from the algorithm for every generated token the most expen- sive operation is the FutureFill computed Line so bound the total runtime of that operation. Note that at any time t, the cost of Fulu operation is O((1 v k(t)) 2h(1)), where V b denotes the max of a and b. Summing this over every time step we get,
[log LJ
Σ [I V k(1))2
Σ k=
Ht k(t) k) V 4)2*
Llog LJ
[lo L
< S
2 Llg
k2 < 3L
Σ A=1
k < 3L log2 L.
A=
Thus the total runtime of the algorithm is bounded by O(L L).
Proof of correcteness for Algorithm 2
We will focus on showing that C, = Σi 4,+1-;;-- Since the output C. + un Φ1, this will suffice for the proof. For brevity of the proof and without loss
25

---

Published as a conference paper at ICLR 2026
of generality will assume L is power of 2. For cleaner presentation for the 8th coordinate of vector y we will use the notation U and v|s] interchanegably in this section.
We first introduce some definitions for convenience in this section. Given index i S. L we define its decomposition f21,22...in } as the unique sequence of numbers I log L such that following holds
> 12 and i E
These indices correspond to the ones in log L-bit representation of i. Note that k(i) defined in the algorithm is equal to im. Further we define the cumulants of as the following sequence of numbers (61,62..)) satisfying
29. j=1
Thus we have that o' < X/2 K... i. We now prove the following lemma which specifies when the FutureFill cache gets updated in an execution of the algorithm.
Lemma Given an index i I L, consider its decomposition {i1, i2 .m I and cumulants {i E2 ... as defined above. It holds that the value of Ci+1 updated (as in Line 8 in the algorithm) only when is one of {ig, ..,..
A direct consequence of the above lemma is that given any index i we have that the value of C++1 not updated after time step i. Further using decomposition {ii, 12,,2.... im and cumulants (1,, i/2 .... of and the update equations for C' (Line 8), we have that final value of C1+1 is given by the following.
n
C.11 FutureFilluulf
24 + +1: +1:1g1.00 01 2i +
j=1
2
u1i - k 1] Φli + +k]
j= k=1
111
Σ
u(r] o6 -
j=1
r=i -2 41
Σ u(rl Φi 11++1+++
Thus the output of the algorithm for any i, satisfies
i+1
0:+1 Cuitu = Σ durl-dlit---+t]-uu
=
uir] (rrl-o(i+--rte
[u+ x+1
This proves the requisite. We finally provide proof of Lemma to finish the proof.
Proof of Lemma 8 By the definition of the algorithm, to be able update C++1 at some time i + 1 it must be the case that
i+ E [t + 1,t 2
Consider some i and its decomposition (11, 62., ......,,) (. and cumulants {1 12 ... C By the definition of the update in Line 8, we have that at time we only update indices + 1 for which has the sequence {t, f/ tt,1) } in its decomposition as prefix. It then be seen that for given number i, the only such numbers are its cumulants, i.c. ( which finishes the proof.
26

---

Published as a conference paper at ICLR 2026
G HYENA ABLATIONS
In this section, we describe evaluations FutureFill on the Hyena Operator Poli et al. 2023). We consider a Hyena Operator with model dimension 768 and positional encoding MLP dim 33, which are the default parameters in the official Hyena runtime benchmarks, and we evaluate with batch size We maintain all other default parameters. After precomputing the max-length Hyena filters, we test the Hyena Operator on autoregressive generation of outputs of length 2 2 2 For FutureFill, we choose K
/2L log2 L.
Seq Length
Standardconv (s)
FutureFill (s)
Speedup
Improvement
16,384
1.368
1.492
0.917x
-9.1%
32,768
4.483
3,860
1.161x
13.9%
65,536
16.295
12.463
1.307x
23.5%
131,072
62,436
45.902
1.360x
26.5%
262,144
247.990
179.254
1.383x
27.7%
524,288
997.250
720.268
1.385x
27.8%
1,048,576
4027.779
2928.229
1.375x
27.3%
Table 19: Performance comparison for autoregressive generation for Hyena Operator with standard convolutions and Hyena Operator with FutureFill. Generation time measured in seconds.
27


Reviews:
[{"review_id": "iUpNLUwHcJ", "reviewer": "Reviewer_SKar", "summary": "The paper introduces FutureFill, a fast inference algorithm for convolutional sequence models that reduces generation complexity by precomputing future contributions via FFT-based convolutions. The method maintains exact output equivalence with standard convolution while achieving notable latency improvements on FlashSTU-T models, all without retraining or architectural changes. It also presents two practical variants—Epoched and Continuous FutureFill—that balance memory and speed for different deployment settings.", "questions": "- How does FutureFill scale with model size and longer sequence lengths (e.g., >100K tokens)?\n- Are the latency gains consistent across different hardware backends?\n- Could the authors report FLOPs per token to complement latency results?\n- How does the method compare with other efficient convolutional architectures in total throughput and memory cost?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Addresses a less-studied yet important bottleneck in convolutional language models.\n- Strong theoretical foundation with clear runtime and correctness guarantees.\n- Training-free and exact—no compromise on model quality.\n- Shows consistent practical gains and integrates seamlessly with existing architectures.\n- Provides clear implementation details enabling reproducibility.", "weaknesses": "- Scalability to multi-billion parameter models not yet validated.\n- Baselines limited; comparison with Hyena, RWKV, and S4 models would be useful.\n- Reports only latency metrics; including FLOPs or energy-based analysis would make results more hardware-agnostic.\n- Hardware dependency unclear—speedups may vary across GPUs/TPUs.\n- Memory–latency trade-offs and cache behavior could be analyzed more deeply.", "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": "n8ABm1dwJJ", "reviewer": "Reviewer_9QkU", "summary": "The paper positions itself with respect to recent work that uses convolutional operators as a way of mitigating complexity issues in autoregressive attention-based models.  Specifically, they propose a method FutureFill that reduces complexity in text generation below quadratic in context length; a core part of the idea is that there is a memory trade-off that permits the reduction in inference time complexity, which also allows a spectrum of algorithm variants in terms of that trade-off.  The paper contains some theoretical results on this complexity, and also some experimental results looking empirically at inference times as a function of context length, as well as checking the performance on several downstream tasks.", "questions": "Please see above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* Overall, I think this is quite a strong paper.  The use of convolutional approaches as in e.g. Hyena is an important direction to address the quadratic complexity issue, and this paper’s contribution looks like an important step in that, and could well be adopted quite widely as a source of performance improvements.", "weaknesses": "These are mostly relatively minor.\n\n* The Abstract is fairly short and bare-bones; it’s not really until reading the paper that the actual importance of the work comes through.\n\n* It’s fairly reasonable given space constraints to save most of the literature review of Sec 1.1 for the appendix.  However, something that I thought was missing in both Sec 1.1 and the appendix’s extended version was the discussion of differences wrt Oncescu et al. (2024).  This is presented as an independent work that achieves the same complexity result as the present paper, but there’s no argument made as to why FutureFill then is necessary.  Is there something more advantageous about the memory trade-off inherent in FutureFill?  Is there some limitation to Oncescu?  It’s not made clear why a new method with this complexity is a useful thing to have, and this is quite crucial for understanding the importance of the present paper's contribution.\n\n* Fig 5 in App D.3 is presented a depiction of the FutureFill operation between an input sequence and a convolutional filter; it’s where the reader is supposed to get a concrete idea of how the method works, to supplement the mathematical definitions.  However, the diagram is very schematic and abstract, and not actually much of a help.  Some fleshing out of the diagram and explanation in D.3 would be helpful.\n\n* For the proof of Propn 1, it would be helpful to link explicitly to App F.", "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": "OOtwprgPmA", "reviewer": "Reviewer_d6Cp", "summary": "This paper introduces \"FutureFill,\" a novel and efficient method for auto-regressive generation from sequence models that use convolutional operators. The primary contribution is an algorithmic technique that reduces the computational complexity of generating L tokens from scratch from a quadratic $O(L^2)$, which is typical for naive online convolution, to a quasilinear. The paper presents two concrete algorithms based on this idea:\n\n1. Continuous-FutureFill: An algorithm that achieves the $O(L log^2 L)$ runtime with $O(L)$ memory.\n2. Epoched-FutureFill: A more practical variant that offers a trade-off between runtime and memory.\n\nFurthermore, the paper shows that when generating K tokens from a prompt of length L, FutureFill significantly reduces the required cache size from $O(L+K)$ to $O(K)$, a crucial improvement for long-context applications. The authors validate their theoretical claims with experiments on both synthetic data and large-scale (up to 826M parameters) convolutional language models, demonstrating empirical speedups of up to 2x over baseline methods on modern hardware.", "questions": "1. Compared to other works that achieve the same complexity, could the authors elaborate more on the qualitative or practical differences between FutureFill and other concurrent works?\n\n2. How would the algorithm perform if the generation length is not known in advance, i.e. the epoch length \n was set to the theoretical optimum but what should peopole use in real-world scenerios?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1: The paper tackles a critical and well-known bottleneck in sequence modeling, i.e. the slow quadratic-time generation process for models based on convolutions. Making this efficient, especially in long-sequnece scenerios is a major practical contribution.\n\n2. The paper is clearly written and the theoretical claims are well-supported by theorems and complexity. The experiments not only demonstrate asymptotic behavior but also wall-clock time improvements.\n\n3. The idea of futurefill is intuitive and based on observations and intuition regarding the properties of convolution and FFT.", "weaknesses": "1. The paper points out that there has been independent and concurrent work that achieves the same runtime complexity, which slightly tempers the novelty.\n\n2. The paper seems to focus only on FlashSTU-T model and would be nice to show how this is generalizable to other convolutional models (e.g. Hyena).\n\n3. While the paper does demonstrate real speed improvement of 2x, it was not as dramatic as the difference from $O(L^2)$ to $O(L)$. More detailed analysis here on why the speedup was not significant would be interesting and informative.", "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": "MBPeZnj7WA", "reviewer": "Reviewer_y912", "summary": "This paper continues the line of work aiming to speed up inference with respect to sequence length and to avoid the quadratic complexity of standard Transformers. The authors propose a method for fast generation using convolutional sequence models. They focus on exact auto-regressive generation from convolutional models, reducing both generation time and cache size, achieving O(N log N) complexity instead of O(L²).\nEmpirical results at small scale show that the proposed algorithms achieve sub-quadratic scaling compared to naive convolution implementations, and they report up to 1.7× speedup over the baseline.\nOverall, this is a solid  paper that provides a practical speedup method, but the experimental validation feels limited.", "questions": "-", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work is technically sound and contributes to the ongoing effort of making sequence models more efficient at inference time.", "weaknesses": "The experiments are limited to relatively small language models (below 1B parameters), which makes it hard to assess the impact at realistic scales. In addition, only inference speed results are presented — there is no evaluation of model quality (e.g., perplexity or downstream performance), which is important to verify that the gains do not come at the cost of degraded output quality.", "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)