We recently introduced FRAC[1], a new State Space Model (SSM) architecture based on fractional dynamics that replaces exponential decay with power-law long memory to improve performance on long contexts. In this post, I’ll focus on one question: How can we turn a sequential formulation of a new architecture into a parallel, hardware-friendly one?
We will discuss the scan part of FRAC, starting from the base sequential form, deriving a chunked parallel form, and implementing a minimal PyTorch-only version.
Let’s start from the simple mathematical formulation. FRAC’s scan can be found in equations 21 and 22 of the paper 1:
st,r,m=ρt,mst−1,r,m+κt,mut,r21
ht,r=m=1∑Mct,mst,r,m22
Here t∈{1,…,T} indexes time steps, r∈{1,…,R} indexes features, and m∈{1,…,M} indexes memory modes. The coefficients ρt,m, κt,m, and ct,m are shared across features, and we omit the batch index in our math.
We can implement a simple version of these equations in PyTorch:
frac_naive
s = u.new_zeros(B, R, M)
outs = u.new_empty(B, L, R) # L is equivalent to T in the post
for t inrange(L):
rho_t = rho[:, t:t+1, :] # [B, 1, M]
kap_t = kappa[:, t:t+1, :] # [B, 1, M]
u_t = u[:, t, :, None] # [B, R, 1]
c_t = c[:, t:t+1, :] # [B, 1, M]
s = rho_t * s + kap_t * u_t # [B, R, M]
h_t = (c_t * s).sum(dim=-1) # [B, R]
outs[:, t, :] = h_t
Obviously, this implementation doesn’t parallelize well on accelerators. We will derive a chunked parallel version of these equations next, which will give us substantial performance gains in pure PyTorch (compared to this naive version).
Now, using this full matrix directly isn’t feasible for long sequences for two main reasons. First, materializing it requires O(T2) memory, which defeats the efficiency purpose of linear attention.
The second reason is about computing the individual entries of the matrix. Each Wt,i needs the product ∏j=i+1tρj,m, which is different for each pair (t,i) and every mode m. 3
Mamba-2 has the same decay product. But its ρ is a scalar that doesn’t depend on m and comes out of the sum. In our notation:
Wt,i=(j=i+1∏tρj)m=1∑Mct,mκi,m
The sum is a matrix multiplication reducing over the M dimension. Each term is a factor that depends on t but not on i times a factor that depends on i but not on t. The decay product is computed once per pair (t,i)4 and applied to the result as a mask. So, we can build W with a matrix multiplication and one mask in the Mamba-2 setting. 5
We cannot do this for FRAC. In FRAC, each of our M modes has its own decay, meaning the decay product stays in the sum, and we can’t apply it as a mask. The sum in Equation (2) isn’t a matrix multiplication anymore since the decay product depends on both t and i. As discussed in GLA[3] (Section 4.1 of their paper), building W as a matrix multiplication would require splitting the decay product (from 3) into a part that depends on t but not on i, and a part that depends on i but not on t:
This is a matrix multiplication again, but it is numerically unstable. ρj,m is in (0,1], so the left product can shrink until it underflows, and the inverse product can grow until it overflows. The multiplication can become 0×∞, which produces NaN. Without this unstable split, we have to compute the decay product for every pair (t,i) and every mode directly without matmul.
The chunked formulation will solve both of these problems. W is materialized only for small diagonal blocks, which makes computing the pairs directly feasible. And, everything off-diagonal is summarized by a state.
We saw the need for a chunked formulation, and we will explore how to do it now. The Mamba-2 SSD algorithm[2] starts by partitioning the causal matrix into blocks. We can split W the same way. Let’s consider three chunks of size Q, so T=3Q:
where hr(q),ur(q)∈RQ and W(q,p)∈RQ×Q, for p,q∈{1,2,3}.
Given this setup, we can view each block row as a sum of contributions from previous chunks and the current chunk to get hr(q). The diagonal blocks map inputs to outputs within the same chunk, and the lower off-diagonal blocks map inputs from previous chunks to outputs in the current chunk. For instance, the last block row can be written as:
We can generalize this to ht,r. Chunk q starts at a=(q−1)Q+1. For an output t in that chunk, the earlier inputs stop at a−1, while the current chunk contributes inputs from a through t:
For the current chunk, we can just materialize W(q,q). For previous chunks, materializing the blocks would bring back the O(T2) cost, and it’s unnecessary since their contribution can be summarized by a single state. To see this, we can expand the formulation using Equation (2).
For each earlier input, its decay product crosses the boundary before a. Split that product into the decays before the boundary and those inside the current chunk:
j=i+1∏tρj,m=(j=i+1∏a−1ρj,m)(j=a∏tρj,m).
For a fixed mode m, the decay inside the current chunk, ∏j=atρj,m, and ct,m do not depend on i. We can take them outside the sum over earlier inputs:
The inner sum contains every input before a, decayed to a−1. It is exactly the unrolled state in Equation (1) at t=a−1. Replacing that sum by sa−1,r,m gives:
Every output in the chunk uses the same incoming state, sa−1,r,m, to account for earlier inputs. As we can see, the incoming state encodes the contribution of all inputs from previous chunks; hence, we never need to materialize the off-diagonal blocks. Next, we will see how we can compute this incoming state for each chunk.
We saw that the incoming state for each chunk can be used to account for earlier inputs. Now, we will go over a formulation to compute that incoming state efficiently.
Chunk q starts at a=(q−1)Q+1 and ends at b=qQ. Its final state, sb,r,m, becomes the next chunk’s incoming state. From Equation (1):
We can rewrite the first sum as the incoming state sa−1,r,m (Equation (1) at t=a−1) multiplied by the decay across the chunk. The second sum gives the current chunk’s own contribution to the state. Let’s call this zq,r,m:
Note that zq,r,m only depends on values within the chunk q. All chunks can compute their own zq,r,m independently of each other and in parallel. Then, each chunk 6 takes the incoming state, multiplies it by the decay across the chunk, adds its own zq,r,m to the decayed incoming state and passes the result to the next chunk. 7
We now have formulas for the output ht,r and the state passed to the next chunk, sb,r,m. Next, we will see how to compute and reuse the decay products in these formulas.
Note that all of these are products within a chunk, so we can compute them for every chunk independently and in parallel. 8
Both products in the first column start at a. To get a product starting at i+1, we can divide out the factors from a through i. Since ρj,m>0:
j=i+1∏tρj,m=∏j=aiρj,m∏j=atρj,m,a≤i≤t≤b.
We can compute these cumulative products once within each chunk. Call the product from a through t, Pt,m:
Pt,m=j=a∏tρj,m,a≤t≤b.(8)
The two products needed for ht,r in Equation (7) are now Pt,m and Pt,m/Pi,m. Setting t=b in these products gives the two needed for sb,r,m. Together, the four cases are:
Once Pt,m is available, we can compute Wt,i and zq,r,m independently for every chunk. The state update then supplies the incoming state for each chunk, giving us everything needed to compute ht,r. Next, we will implement these formulations in PyTorch.
The equations apply to each feature independently. In the code, u has shape (B, L, R), while rho, kappa, and c have shape (B, L, M). Here L is the sequence length T, R is the feature dimension, and chunk_size is Q. 10
We first need Pt,m (Equation (8)) and its ratios. To avoid dividing cumulative products that may have underflowed to zero, we can represent them through their logarithms. For positive ρ:
ℓt,m=logPt,m=j=a∑tlogρj,m.
We recover a product by exponentiating, and a ratio by subtracting the logarithms before exponentiating:
Pt,m=exp(ℓt,m),Pi,mPt,m=exp(ℓt,m−ℓi,m).
After reshaping to (B, nchunks, chunk_size, M), a cumulative sum along dimension 2 computes ℓt,m within each chunk. The function returns these values as log_cum_rho and each chunk’s last value, ℓb,m, as chunk_decay. Both are logarithms.
chunk_cumsum_ref
import torch
defchunk_cumsum_ref(
log_rho: torch.Tensor, # (B, L, M)
chunk_size: int,
) -> tuple[
torch.Tensor, # (B, L, M)
torch.Tensor, # (B, nchunks, M)
]:
B, L, M = log_rho.shape
nchunks = L // chunk_size
x = log_rho.view(B, nchunks, chunk_size, M)
log_cum_rho = torch.cumsum(x, dim=2)
chunk_decay = log_cum_rho[:, :, -1].contiguous()
log_cum_rho = log_cum_rho.reshape(B, L, M)
return log_cum_rho, chunk_decay
We can now use the decay from each input to its chunk’s end to compute zq,r,m.
In the code, decay_to_end is the exponential factor and scale includes κi,m. The einsum sums over input positions, producing states: the contribution zq,r,m for every feature and mode in every chunk.
chunk_state_ref
defchunk_state_ref(
u: torch.Tensor, # (B, L, R)
kappa: torch.Tensor, # (B, L, M)
log_cum_rho: torch.Tensor, # (B, L, M)
chunk_size: int,
) -> torch.Tensor: # (B, nchunks, R, M)
B, L, R = u.shape
M = kappa.shape[-1]
nchunks = L // chunk_size
u_4d = u.view(B, nchunks, chunk_size, R)
kappa_4d = kappa.view(B, nchunks, chunk_size, M)
log_cum_rho_4d = log_cum_rho.view(B, nchunks, chunk_size, M)
For each chunk, running holds the incoming state and states[:, n] holds its own contribution. We save running in states_acc before the update, since ht,r uses the state entering its chunk. The final value of running is returned as the sequence’s final state.
state_passing_ref
defstate_passing_ref(
states: torch.Tensor, # (B, nchunks, R, M)
chunk_decay: torch.Tensor, # (B, nchunks, M)
initial_state: torch.Tensor |None=None, # (B, R, M)
) -> tuple[
torch.Tensor, # (B, nchunks, R, M)
torch.Tensor, # (B, R, M)
]:
B, nchunks, R, M = states.shape
if initial_state isNone:
running = states.new_zeros(B, R, M)
else:
running = initial_state
states_acc = states.new_empty(B, nchunks, R, M)
for n inrange(nchunks):
states_acc[:, n] = running
decay = torch.exp(chunk_decay[:, n]).unsqueeze(1)
running = decay * running + states[:, n]
return states_acc, running
We now have the incoming state required by ht,r. The remaining quantity is the current chunk’s weights, Wt,i.
Each weight connects an input at i to an output at t in the same chunk. We multiply κi,m by the decay from i to t and by ct,m, then sum over modes, as in Equation (9):
diff contains ℓt,m−ℓi,m for every output-input pair within a chunk. We set the decay to zero for future inputs, i>t, and sum over the final mode dimension to obtain the weights.
W = (c_chunked.unsqueeze(3) * decay * kappa_chunked.unsqueeze(2)).sum(-1)
return W
The returned W contains one Q×Q block per chunk: these are the diagonal blocks in Equation (4). We can now combine them with the incoming states to compute ht,r.
For h_inter, we multiply c by the cumulative decay and sum against states_acc over modes. For h_intra, we multiply each chunk’s W block by its inputs. Adding these two terms gives the output.
states = chunk_state_ref(u, kappa, log_cum_rho, chunk_size)
states_acc, final_state = state_passing_ref(
states, chunk_decay, initial_state,
)
W = chunk_w_ref(c, kappa, log_cum_rho, chunk_size)
h = chunk_readout_ref(u, c, states_acc, W, log_cum_rho, chunk_size)
return h, final_state
Now, if we compare this against the original looped version we had in the beginning, the improvements are substantial for both forward and autograd’s backward. 11
Timestep loop vs chunked PyTorch
B = 2
R = 128
M = 16
chunk_size = 64
L = 4,096
Forward
Backward
Loop
11.5
baseline
124.4
baseline
Chunked PyTorch
4.075e-2
282×
0.197
632×
We now have a chunked PyTorch implementation of FRAC, with autograd handling the backward pass.
Ivan Kobyzev, Abbas Ghaddar, Ali Nasiri-Sarvi, Lifeng Shang, and Yufei Cui. Fractional State Space Transition for Long Sequence Modeling. NeurIPS 2026. https://arxiv.org/abs/2609.36314
[2]
Tri Dao and Albert Gu. Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality. ICML 2024. https://arxiv.org/abs/2405.21060
[3]
Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim. Gated Linear Attention Transformers with Hardware-Efficient Training. ICML 2024. https://arxiv.org/abs/2312.06635