Fractional State Space Models: Chunked Parallel Algorithm

Deriving a chunked algorithm for fractional state space models and implementing its forward pass in PyTorch

Introduction#

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.

FRAC Scan#

Let’s start from the simple mathematical formulation. FRAC’s scan can be found in equations 2121 and 2222 of the paper 1:

st,r,m=ρt,mst−1,r,m+κt,mut,r21s_{t,r,m} = \rho_{t,m} s_{t-1,r,m} + \kappa_{t,m} u_{t,r} \quad\quad \text{21}
ht,r=∑m=1Mct,mst,r,m22h_{t,r} = \sum_{m=1}^{M} c_{t,m}s_{t,r,m} \quad\quad\quad\quad\quad\quad \text{22}

Here t∈{1,…,T}t\in\lbrace 1, \ldots, T \rbrace indexes time steps, r∈{1,…,R}r\in\lbrace 1,\ldots,R\rbrace indexes features, and m∈{1,…,M}m\in\lbrace1,\ldots,M \rbrace indexes memory modes. The coefficients ρt,m\rho_{t,m}, κt,m\kappa_{t,m}, and ct,mc_{t,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 in range(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).

Chunked Parallel Form#

Linear attention models like Mamba-2[2] 2 develop a chunked parallel algorithm for their recurrence form by doing the following steps:

  1. Unroll the sequential form to get a general formulation.
  2. Express the general formulation as a matrix multiplication.
  3. Develop a chunk-based matrix multiplication, as materializing the whole matrix isn’t practical.

Next, we will go over these three steps for the FRAC scan.

1) General Formulation#

First, we can unroll st,r,ms_{t,r,m}:

st,r,m=ρt,mst−1,r,m+κt,mut,r=ρt,m(ρt−1,mst−2,r,m+κt−1,mut−1,r)+κt,mut,rs_{t,r,m} = \rho_{t,m} s_{t-1,r,m} + \kappa_{t,m} u_{t,r} = \rho_{t,m} (\rho_{t-1,m} s_{t-2,r,m} + \kappa_{t-1,m} u_{t-1,r}) + \kappa_{t,m} u_{t,r}

Expanding the parentheses, we get:

st,r,m=ρt,mρt−1,mst−2,r,m+ρt,mκt−1,mut−1,r+κt,mut,rs_{t,r,m} = \rho_{t,m}\rho_{t-1,m}s_{t-2,r,m} + \rho_{t,m}\kappa_{t-1,m}u_{t-1,r} + \kappa_{t,m}u_{t,r}

Unrolling one more time, we get:

st,r,m=ρt,mρt−1,mρt−2,mst−3,r,m+ρt,mρt−1,mκt−2,mut−2,r+ρt,mκt−1,mut−1,r+κt,mut,rs_{t,r,m} = \rho_{t,m}\rho_{t-1,m}\rho_{t-2,m}s_{t-3,r,m} + \rho_{t,m}\rho_{t-1,m}\kappa_{t-2,m}u_{t-2,r} + \rho_{t,m}\kappa_{t-1,m}u_{t-1,r} + \kappa_{t,m}u_{t,r}

If we keep unrolling until the initial state, we get:

st,r,m=(∏j=1tρj,m)s0,r,m+∑i=1t(κi,mui,r∏j=i+1tρj,m)s_{t,r,m} = \left(\prod_{j=1}^{t}\rho_{j,m}\right)s_{0,r,m} + \sum_{i=1}^{t} \left( \kappa_{i,m}u_{i,r} \prod_{j=i+1}^{t}\rho_{j,m} \right)

If the initial state is zero (we will add it later), the first term disappears:

st,r,m=∑i=1t(κi,mui,r∏j=i+1tρj,m)(1)s_{t,r,m} = \sum_{i=1}^{t} \left( \kappa_{i,m}u_{i,r} \prod_{j=i+1}^{t}\rho_{j,m} \right) \tag{1}

Substituting this into ht,rh_{t,r} gives:

ht,r=∑m=1Mct,m∑i=1t(κi,mui,r∏j=i+1tρj,m)h_{t,r} = \sum_{m=1}^{M} c_{t,m} \sum_{i=1}^{t} \left( \kappa_{i,m}u_{i,r} \prod_{j=i+1}^{t}\rho_{j,m} \right)

Reordering the sums gives the contribution of every input ui,ru_{i,r} to the output at time tt:

ht,r=∑i=1t[∑m=1Mct,mκi,m∏j=i+1tρj,m]ui,rh_{t,r} = \sum_{i=1}^{t} \left[ \sum_{m=1}^{M} c_{t,m}\kappa_{i,m} \prod_{j=i+1}^{t}\rho_{j,m} \right]u_{i,r}

2) Matrix Formulation#

For a fixed feature rr and a sequence of length TT, we can write the same operation as a multiplication by a lower-triangular matrix:

[h1,r∑m=1Mh2,r∑m=1Mh3,r∑m=1M⋮hT,r∑m=1M]=[∑m=1Mc1,mκ1,m00⋯0∑m=1Mc2,mρ2,mκ1,m∑m=1Mc2,mκ2,m0⋯0∑m=1Mc3,mρ3,mρ2,mκ1,m∑m=1Mc3,mρ3,mκ2,m∑m=1Mc3,mκ3,m⋯0⋮⋮⋮⋱⋮∑m=1McT,mκ1,m∏j=2Tρj,m∑m=1McT,mκ2,m∏j=3Tρj,m∑m=1McT,mκ3,m∏j=4Tρj,m⋯∑m=1McT,mκT,m][u1,r∑m=1Mu2,r∑m=1Mu3,r∑m=1M⋮uT,r∑m=1M]\begin{aligned} \begin{bmatrix} h_{1,r} \vphantom{\displaystyle\sum_{m=1}^{M}} \\[6pt] h_{2,r} \vphantom{\displaystyle\sum_{m=1}^{M}} \\[6pt] h_{3,r} \vphantom{\displaystyle\sum_{m=1}^{M}} \\ \vdots \\[6pt] h_{T,r} \vphantom{\displaystyle\sum_{m=1}^{M}} \end{bmatrix} &= \left[ \begin{array}{lllll} \displaystyle\sum_{m=1}^{M} c_{1,m}\kappa_{1,m} & 0 & 0 & \cdots & 0 \\[6pt] \displaystyle\sum_{m=1}^{M} c_{2,m}\rho_{2,m}\kappa_{1,m} & \displaystyle\sum_{m=1}^{M} c_{2,m}\kappa_{2,m} & 0 & \cdots & 0 \\[6pt] \displaystyle\sum_{m=1}^{M} c_{3,m}\rho_{3,m}\rho_{2,m}\kappa_{1,m} & \displaystyle\sum_{m=1}^{M} c_{3,m}\rho_{3,m}\kappa_{2,m} & \displaystyle\sum_{m=1}^{M} c_{3,m}\kappa_{3,m} & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\[6pt] \displaystyle\sum_{m=1}^{M} c_{T,m}\kappa_{1,m}\prod_{j=2}^{T}\rho_{j,m} & \displaystyle\sum_{m=1}^{M} c_{T,m}\kappa_{2,m}\prod_{j=3}^{T}\rho_{j,m} & \displaystyle\sum_{m=1}^{M} c_{T,m}\kappa_{3,m}\prod_{j=4}^{T}\rho_{j,m} & \cdots & \displaystyle\sum_{m=1}^{M} c_{T,m}\kappa_{T,m} \end{array} \right] \begin{bmatrix} u_{1,r} \vphantom{\displaystyle\sum_{m=1}^{M}} \\[6pt] u_{2,r} \vphantom{\displaystyle\sum_{m=1}^{M}} \\[6pt] u_{3,r} \vphantom{\displaystyle\sum_{m=1}^{M}} \\ \vdots \\[6pt] u_{T,r} \vphantom{\displaystyle\sum_{m=1}^{M}} \end{bmatrix} \end{aligned}

If we call the lower-triangular matrix W\mathbf{W}, then:

hr=Wur\mathbf{h}_r = \mathbf{W}\mathbf{u}_r

where:

Wt,i={∑m=1Mct,mκi,m∏j=i+1tρj,m,i<t,∑m=1Mct,mκi,m,i=t,0,i>t.(2)W_{t,i} = \begin{cases} \displaystyle \sum_{m=1}^{M} c_{t,m}\kappa_{i,m} \prod_{j=i+1}^{t}\rho_{j,m}, & i < t, \\[6pt] \displaystyle\sum_{m=1}^{M} c_{t,m}\kappa_{i,m}, & i = t,\\[6pt] 0, & i > t. \end{cases} \tag{2}

Now, using this full matrix directly isn’t feasible for long sequences for two main reasons. First, materializing it requires O(T2)O(T^2) memory, which defeats the efficiency purpose of linear attention.

The second reason is about computing the individual entries of the matrix. Each Wt,iW_{t,i} needs the product ∏j=i+1tρj,m\prod_{j=i+1}^{t}\rho_{j,m}, which is different for each pair (t,i)(t,i) and every mode mm. 3

Mamba-2 has the same decay product. But its ρ\rho is a scalar that doesn’t depend on mm and comes out of the sum. In our notation:

Wt,i=(∏j=i+1tρj)∑m=1Mct,mκi,mW_{t,i} = \left(\prod_{j=i+1}^{t}\rho_{j}\right) \sum_{m=1}^{M} c_{t,m} \kappa_{i,m}

The sum is a matrix multiplication reducing over the MM dimension. Each term is a factor that depends on tt but not on ii times a factor that depends on ii but not on tt. The decay product is computed once per pair (t,i)(t,i) 4 and applied to the result as a mask. So, we can build W\mathbf{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 MM 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)\href{#eq-w-entries}{\text{(2)}} isn’t a matrix multiplication anymore since the decay product depends on both tt and ii. As discussed in GLA[3] (Section 4.1 of their paper), building W\mathbf{W} as a matrix multiplication would require splitting the decay product (from 3) into a part that depends on tt but not on ii, and a part that depends on ii but not on tt:

Wt,i=∑m=1M(ct,m∏j=1tρj,m)(κi,m∏j=1iρj,m)(3)W_{t,i} = \sum_{m=1}^{M} \left(c_{t,m}\prod_{j=1}^{t}\rho_{j,m}\right) \left(\frac{\kappa_{i,m}}{\prod_{j=1}^{i}\rho_{j,m}}\right) \tag{3}

This is a matrix multiplication again, but it is numerically unstable. ρj,m\rho_{j,m} is in (0,1](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×∞0 \times \infty, which produces NaN. Without this unstable split, we have to compute the decay product for every pair (t,i)(t,i) and every mode directly without matmul.

The chunked formulation will solve both of these problems. W\mathbf{W} is materialized only for small diagonal blocks, which makes computing the pairs directly feasible. And, everything off-diagonal is summarized by a state.

3) Chunked Formulation#

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\mathbf{W} the same way. Let’s consider three chunks of size QQ, so T=3QT=3Q:

[hr(1)hr(2)hr(3)]=[W(1,1)00W(2,1)W(2,2)0W(3,1)W(3,2)W(3,3)][ur(1)ur(2)ur(3)](4)\begin{bmatrix} \mathbf{h}_r^{(1)} \\[6pt] \mathbf{h}_r^{(2)} \\[6pt] \mathbf{h}_r^{(3)} \end{bmatrix} = \left[ \begin{array}{l|l|l} \textcolor{#cf3f4f}{\mathbf{W}^{(1,1)}} & \mathbf{0} & \mathbf{0} \\[6pt] \hline \textcolor{#218c4e}{\mathbf{W}^{(2,1)}} & \textcolor{#cf3f4f}{\mathbf{W}^{(2,2)}} & \mathbf{0} \\[6pt] \hline \textcolor{#218c4e}{\mathbf{W}^{(3,1)}} & \textcolor{#218c4e}{\mathbf{W}^{(3,2)}} & \textcolor{#cf3f4f}{\mathbf{W}^{(3,3)}} \end{array} \right] \begin{bmatrix} \mathbf{u}_r^{(1)} \\[6pt] \mathbf{u}_r^{(2)} \\[6pt] \mathbf{u}_r^{(3)} \end{bmatrix} \tag{4}

where hr(q),ur(q)∈RQ\mathbf{h}_r^{(q)}, \mathbf{u}_r^{(q)} \in \mathbb{R}^{Q} and W(q,p)∈RQ×Q\mathbf{W}^{(q,p)} \in \mathbb{R}^{Q \times Q}, for p,q∈{1,2,3}p,q \in \{1,2,3\}.

Given this setup, we can view each block row as a sum of contributions from previous chunks\textcolor{#218c4e}{\text{previous chunks}} and the current chunk\textcolor{#cf3f4f}{\text{current chunk}} to get hr(q)\mathbf{h}_r^{(q)}. The diagonal blocks\textcolor{#cf3f4f}{\text{diagonal blocks}} map inputs to outputs within the same chunk, and the lower off-diagonal blocks\textcolor{#218c4e}{\text{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:

hr(3)=W(3,1)ur(1)+W(3,2)ur(2)⏟previous chunks+W(3,3)ur(3)⏟current chunk\mathbf{h}_r^{(3)} = \textcolor{#218c4e}{ \underbrace{ \mathbf{W}^{(3,1)}\mathbf{u}_r^{(1)} + \mathbf{W}^{(3,2)}\mathbf{u}_r^{(2)} }_{\text{previous chunks}} } + \textcolor{#cf3f4f}{ \underbrace{ \mathbf{W}^{(3,3)}\mathbf{u}_r^{(3)} }_{\text{current chunk}} }

Let’s assume Q=2Q=2. Expanding the blocks of Equation (4)\href{#eq-w-blocks}{\text{(4)}} into individual matrix entries gives:

[h1,rh2,rh3,rh4,rh5,rh6,r]=[W1,100000W2,1W2,20000W3,1W3,2W3,3000W4,1W4,2W4,3W4,400W5,1W5,2W5,3W5,4W5,50W6,1W6,2W6,3W6,4W6,5W6,6][u1,ru2,ru3,ru4,ru5,ru6,r]\left[ \begin{array}{c} h_{1,r} \\[4pt] h_{2,r} \\[4pt] \hline h_{3,r} \\[4pt] h_{4,r} \\[4pt] \hline h_{5,r} \\[4pt] h_{6,r} \end{array} \right] = \left[ \begin{array}{cc|cc|cc} \textcolor{#cf3f4f}{W_{1,1}} & 0 & 0 & 0 & 0 & 0 \\[4pt] \textcolor{#cf3f4f}{W_{2,1}} & \textcolor{#cf3f4f}{W_{2,2}} & 0 & 0 & 0 & 0 \\[4pt] \hline \textcolor{#218c4e}{W_{3,1}} & \textcolor{#218c4e}{W_{3,2}} & \textcolor{#cf3f4f}{W_{3,3}} & 0 & 0 & 0 \\[4pt] \textcolor{#218c4e}{W_{4,1}} & \textcolor{#218c4e}{W_{4,2}} & \textcolor{#cf3f4f}{W_{4,3}} & \textcolor{#cf3f4f}{W_{4,4}} & 0 & 0 \\[4pt] \hline \textcolor{#218c4e}{W_{5,1}} & \textcolor{#218c4e}{W_{5,2}} & \textcolor{#218c4e}{W_{5,3}} & \textcolor{#218c4e}{W_{5,4}} & \textcolor{#cf3f4f}{W_{5,5}} & 0 \\[4pt] \textcolor{#218c4e}{W_{6,1}} & \textcolor{#218c4e}{W_{6,2}} & \textcolor{#218c4e}{W_{6,3}} & \textcolor{#218c4e}{W_{6,4}} & \textcolor{#cf3f4f}{W_{6,5}} & \textcolor{#cf3f4f}{W_{6,6}} \end{array} \right] \left[ \begin{array}{c} u_{1,r} \\[4pt] u_{2,r} \\[4pt] \hline u_{3,r} \\[4pt] u_{4,r} \\[4pt] \hline u_{5,r} \\[4pt] u_{6,r} \end{array} \right]

Let’s compute h6,rh_{6,r} from the third chunk. The first four inputs belong to previous chunks, and the last two belong to the current chunk:

h6,r=W6,1u1,r+W6,2u2,r+W6,3u3,r+W6,4u4,r⏟previous chunks+W6,5u5,r+W6,6u6,r⏟current chunk.h_{6,r} =\textcolor{#218c4e}{ \underbrace{W_{6,1}u_{1,r}+W_{6,2}u_{2,r}+W_{6,3}u_{3,r}+W_{6,4}u_{4,r}}_{\text{previous chunks}} } +\textcolor{#cf3f4f}{ \underbrace{W_{6,5}u_{5,r}+W_{6,6}u_{6,r}}_{\text{current chunk}} }.

We can generalize this to ht,rh_{t,r}. Chunk qq starts at a=(q−1)Q+1a=(q-1)Q+1. For an output tt in that chunk, the earlier inputs stop at a−1a-1, while the current chunk contributes inputs from aa through tt:

ht,r=∑i=1a−1Wt,iui,r⏟previous chunks+∑i=atWt,iui,r⏟current chunk,withq=⌈tQ⌉,a=(q−1)Q+1.\begin{aligned} &h_{t,r} =\textcolor{#218c4e}{ \underbrace{\sum_{i=1}^{a-1}W_{t,i}u_{i,r}}_{\text{previous chunks}} } +\textcolor{#cf3f4f}{ \underbrace{\sum_{i=a}^{t}W_{t,i}u_{i,r}}_{\text{current chunk}} }, \\[8pt] &\text{with}\quad q=\left\lceil\frac{t}{Q}\right\rceil, \quad a=(q-1)Q+1. \end{aligned}

For the current chunk, we can just materialize W(q,q)\mathbf{W}^{(q,q)}. For previous chunks, materializing the blocks would bring back the O(T2)O(T^2) 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)\href{#eq-w-entries}{\text{(2)}}.

ht,r=∑i=1a−1∑m=1Mct,mκi,mui,r∏j=i+1tρj,m+∑i=atWt,iui,r.h_{t,r} =\textcolor{#218c4e}{\sum_{i=1}^{a-1}\sum_{m=1}^{M} c_{t,m}\kappa_{i,m}u_{i,r}\prod_{j=i+1}^{t}\rho_{j,m}} +\textcolor{#cf3f4f}{\sum_{i=a}^{t}W_{t,i}u_{i,r}}.

For each earlier input, its decay product crosses the boundary before aa. Split that product into the decays before the boundary and those inside the current chunk:

∏j=i+1tρj,m=(∏j=i+1a−1ρj,m)(∏j=atρj,m).\prod_{j=i+1}^{t}\rho_{j,m} =\left(\prod_{j=i+1}^{a-1}\rho_{j,m}\right) \left(\prod_{j=a}^{t}\rho_{j,m}\right).

For a fixed mode mm, the decay inside the current chunk, ∏j=atρj,m\prod_{j=a}^{t}\rho_{j,m}, and ct,mc_{t,m} do not depend on ii. We can take them outside the sum over earlier inputs:

ht,r=∑m=1Mct,m(∏j=atρj,m)∑i=1a−1κi,mui,r∏j=i+1a−1ρj,m⏟sa−1,r,m+∑i=atWt,iui,r.\begin{aligned} h_{t,r} &=\textcolor{#218c4e}{\sum_{m=1}^{M} c_{t,m}\left(\prod_{j=a}^{t}\rho_{j,m}\right) \underbrace{\sum_{i=1}^{a-1}\kappa_{i,m}u_{i,r} \prod_{j=i+1}^{a-1}\rho_{j,m}}_{s_{a-1,r,m}}} \\[8pt] &\quad+\textcolor{#cf3f4f}{\sum_{i=a}^{t}W_{t,i}u_{i,r}}. \end{aligned}

The inner sum contains every input before aa, decayed to a−1a-1. It is exactly the unrolled state in Equation (1)\href{#eq-state}{\text{(1)}} at t=a−1t=a-1. Replacing that sum by sa−1,r,ms_{a-1,r,m} gives:

ht,r=∑m=1Mct,m(∏j=atρj,m)sa−1,r,m+∑i=atWt,iui,r.(5)h_{t,r} =\textcolor{#218c4e}{\sum_{m=1}^{M}c_{t,m} \left(\prod_{j=a}^{t}\rho_{j,m}\right)s_{a-1,r,m}} +\textcolor{#cf3f4f}{\sum_{i=a}^{t}W_{t,i}u_{i,r}}. \tag{5}

Every output in the chunk uses the same incoming state, sa−1,r,ms_{a-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.

Computing the incoming states#

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 qq starts at a=(q−1)Q+1a=(q-1)Q+1 and ends at b=qQb=qQ. Its final state, sb,r,ms_{b,r,m}, becomes the next chunk’s incoming state. From Equation (1)\href{#eq-state}{\text{(1)}}:

sb,r,m=∑i=1bκi,mui,r∏j=i+1bρj,m.s_{b,r,m}=\sum_{i=1}^{b}\kappa_{i,m}u_{i,r}\prod_{j=i+1}^{b}\rho_{j,m}.

Split this sum at the start of the chunk, aa:

sb,r,m=∑i=1a−1κi,mui,r∏j=i+1bρj,m+∑i=abκi,mui,r∏j=i+1bρj,m.s_{b,r,m} =\sum_{i=1}^{a-1}\kappa_{i,m}u_{i,r}\prod_{j=i+1}^{b}\rho_{j,m} +\sum_{i=a}^{b}\kappa_{i,m}u_{i,r}\prod_{j=i+1}^{b}\rho_{j,m}.

We can rewrite the first sum as the incoming state sa−1,r,ms_{a-1,r,m} (Equation (1)\href{#eq-state}{\text{(1)}} at t=a−1t=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,mz_{q,r,m}:

sb,r,m=(∏j=abρj,m)sa−1,r,m+∑i=abκi,mui,r∏j=i+1bρj,m⏟zq,r,m.(6)s_{b,r,m} =\left(\prod_{j=a}^{b}\rho_{j,m}\right)s_{a-1,r,m} +\underbrace{\sum_{i=a}^{b}\kappa_{i,m}u_{i,r} \prod_{j=i+1}^{b}\rho_{j,m}}_{z_{q,r,m}}. \tag{6}

Note that zq,r,mz_{q,r,m} only depends on values within the chunk qq. All chunks can compute their own zq,r,mz_{q, 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,mz_{q,r,m} to the decayed incoming state and passes the result to the next chunk. 7

We now have formulas for the output ht,rh_{t,r} and the state passed to the next chunk, sb,r,ms_{b,r,m}. Next, we will see how to compute and reuse the decay products in these formulas.

Computing the decay products#

The formulas for ht,rh_{t,r} (Equation (5)\href{#eq-h-chunk}{\text{(5)}}) and sb,r,ms_{b,r,m} (Equation (6)\href{#eq-state-update}{\text{(6)}}) use four different decay products:

ht,r:∏j=atρj,m⏟multiplying sa−1,r,m,∏j=i+1tρj,m⏟inside Wt,i,a≤i≤t≤b,sb,r,m:∏j=abρj,m⏟multiplying sa−1,r,m,∏j=i+1bρj,m⏟inside zq,r,m,a≤i≤b.(7)\begin{aligned} h_{t,r}:\quad & \underbrace{\prod_{j=a}^{t}\rho_{j,m}}_{\text{multiplying }s_{a-1,r,m}}, \qquad \underbrace{\prod_{j=i+1}^{t}\rho_{j,m}}_{\text{inside }W_{t,i}}, &\qquad a\leq i\leq t\leq b, \\[12pt] s_{b,r,m}:\quad & \underbrace{\prod_{j=a}^{b}\rho_{j,m}}_{\text{multiplying }s_{a-1,r,m}}, \qquad \underbrace{\prod_{j=i+1}^{b}\rho_{j,m}}_{\text{inside }z_{q,r,m}}, &\qquad a\leq i\leq b. \end{aligned} \tag{7}

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 aa. To get a product starting at i+1i+1, we can divide out the factors from aa through ii. Since ρj,m>0\rho_{j,m}>0:

∏j=i+1tρj,m=∏j=atρj,m∏j=aiρj,m,a≤i≤t≤b.\prod_{j=i+1}^{t}\rho_{j,m} =\frac{\prod_{j=a}^{t}\rho_{j,m}} {\prod_{j=a}^{i}\rho_{j,m}}, \qquad a\leq i\leq t\leq b.

We can compute these cumulative products once within each chunk. Call the product from aa through tt, Pt,mP_{t,m}:

Pt,m=∏j=atρj,m,a≤t≤b.(8)P_{t,m}=\prod_{j=a}^{t}\rho_{j,m}, \qquad a\leq t\leq b. \tag{8}

The two products needed for ht,rh_{t,r} in Equation (7)\href{#eq-decay-products}{\text{(7)}} are now Pt,mP_{t,m} and Pt,m/Pi,mP_{t,m}/P_{i,m}. Setting t=bt=b in these products gives the two needed for sb,r,ms_{b,r,m}. Together, the four cases are:

∏j=atρj,m=Pt,m,∏j=i+1tρj,m=Pt,mPi,m,∏j=abρj,m=Pb,m,∏j=i+1bρj,m=Pb,mPi,m.\begin{aligned} \prod_{j=a}^{t}\rho_{j,m}&=P_{t,m}, &\qquad \prod_{j=i+1}^{t}\rho_{j,m}&=\frac{P_{t,m}}{P_{i,m}}, \\[10pt] \prod_{j=a}^{b}\rho_{j,m}&=P_{b,m}, &\qquad \prod_{j=i+1}^{b}\rho_{j,m}&=\frac{P_{b,m}}{P_{i,m}}. \end{aligned}

When i=ti=t in the first row or i=bi=b in the second, the numerator and denominator are equal, giving 1 for the empty product. 9

We can now replace all four decay products in the output and state formulas, Equations (5)\href{#eq-h-chunk}{\text{(5)}} and (6)\href{#eq-state-update}{\text{(6)}}:

ht,r=∑m=1Mct,mPt,msa−1,r,m+∑i=atWt,iui,r,Wt,i=∑m=1Mct,mκi,mPt,mPi,m,a≤i≤t≤b,sb,r,m=Pb,msa−1,r,m+zq,r,m,zq,r,m=∑i=abκi,mui,rPb,mPi,m.(9)\begin{aligned} h_{t,r} &=\textcolor{#218c4e}{\sum_{m=1}^{M}c_{t,m}P_{t,m}s_{a-1,r,m}} +\textcolor{#cf3f4f}{\sum_{i=a}^{t}W_{t,i}u_{i,r}}, \\[10pt] W_{t,i} &=\sum_{m=1}^{M}c_{t,m}\kappa_{i,m}\frac{P_{t,m}}{P_{i,m}}, \qquad a\leq i\leq t\leq b, \\[10pt] s_{b,r,m} &=P_{b,m}s_{a-1,r,m}+z_{q,r,m}, \\[10pt] z_{q,r,m} &=\sum_{i=a}^{b}\kappa_{i,m}u_{i,r}\frac{P_{b,m}}{P_{i,m}}. \end{aligned} \tag{9}

Once Pt,mP_{t,m} is available, we can compute Wt,iW_{t,i} and zq,r,mz_{q,r,m} independently for every chunk. The state update then supplies the incoming state for each chunk, giving us everything needed to compute ht,rh_{t,r}. Next, we will implement these formulations in PyTorch.

Implementing the chunked forward pass#

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 TT, R is the feature dimension, and chunk_size is QQ. 10

Computing the cumulative decays#

We first need Pt,mP_{t,m} (Equation (8)\href{#eq-p-def}{\text{(8)}}) and its ratios. To avoid dividing cumulative products that may have underflowed to zero, we can represent them through their logarithms. For positive ρ\rho:

ℓt,m=log⁡Pt,m=∑j=atlog⁡ρj,m.\ell_{t,m}=\log P_{t,m}=\sum_{j=a}^{t}\log\rho_{j,m}.

We recover a product by exponentiating, and a ratio by subtracting the logarithms before exponentiating:

Pt,m=exp⁡(ℓt,m),Pt,mPi,m=exp⁡(ℓt,m−ℓi,m).P_{t,m}=\exp(\ell_{t,m}), \qquad \frac{P_{t,m}}{P_{i,m}}=\exp(\ell_{t,m}-\ell_{i,m}).

After reshaping to (B, nchunks, chunk_size, M), a cumulative sum along dimension 2 computes ℓt,m\ell_{t,m} within each chunk. The function returns these values as log_cum_rho and each chunk’s last value, ℓb,m\ell_{b,m}, as chunk_decay. Both are logarithms.

chunk_cumsum_ref
import torch
def chunk_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,mz_{q,r,m}.

Computing each chunk’s own state contribution#

Input ui,ru_{i,r} adds κi,mui,r\kappa_{i,m}u_{i,r} to the state. Multiplying by its decay to bb and summing over the chunk’s inputs gives, as in Equation (9)\href{#eq-chunked-forms}{\text{(9)}}:

zq,r,m=∑i=abκi,mui,rPb,mPi,m=∑i=abκi,mui,rexp⁡(ℓb,m−ℓi,m).z_{q,r,m} =\sum_{i=a}^{b}\kappa_{i,m}u_{i,r}\frac{P_{b,m}}{P_{i,m}} =\sum_{i=a}^{b}\kappa_{i,m}u_{i,r}\exp(\ell_{b,m}-\ell_{i,m}).

In the code, decay_to_end is the exponential factor and scale includes κi,m\kappa_{i,m}. The einsum sums over input positions, producing states: the contribution zq,r,mz_{q,r,m} for every feature and mode in every chunk.

chunk_state_ref
def chunk_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)
lcr_end = log_cum_rho_4d[:, :, -1:, :]
decay_to_end = torch.exp(lcr_end - log_cum_rho_4d)
scale = decay_to_end * kappa_4d
states = torch.einsum("bntr,bntm->bnrm", u_4d, scale)
return states

We can compute all these contributions independently. Next, we will combine them with the state entering each chunk.

Passing the state between chunks#

Starting from the supplied initial state, we can now apply the update we derived in Equation (9)\href{#eq-chunked-forms}{\text{(9)}}:

sb,r,m=Pb,msa−1,r,m+zq,r,m=exp⁡(ℓb,m)sa−1,r,m+zq,r,m.s_{b,r,m} =P_{b,m}s_{a-1,r,m}+z_{q,r,m} =\exp(\ell_{b,m})s_{a-1,r,m}+z_{q,r,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,rh_{t,r} uses the state entering its chunk. The final value of running is returned as the sequence’s final state.

state_passing_ref
def state_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 is None:
running = states.new_zeros(B, R, M)
else:
running = initial_state
states_acc = states.new_empty(B, nchunks, R, M)
for n in range(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,rh_{t,r}. The remaining quantity is the current chunk’s weights, Wt,iW_{t,i}.

Computing the local weights#

Each weight connects an input at ii to an output at tt in the same chunk. We multiply κi,m\kappa_{i,m} by the decay from ii to tt and by ct,mc_{t,m}, then sum over modes, as in Equation (9)\href{#eq-chunked-forms}{\text{(9)}}:

Wt,i=∑m=1Mct,mκi,mPt,mPi,m=∑m=1Mct,mκi,mexp⁡(ℓt,m−ℓi,m),a≤i≤t≤b.\begin{aligned} W_{t,i} &=\sum_{m=1}^{M}c_{t,m}\kappa_{i,m}\frac{P_{t,m}}{P_{i,m}} \\[6pt] &=\sum_{m=1}^{M}c_{t,m}\kappa_{i,m}\exp(\ell_{t,m}-\ell_{i,m}), \qquad a\leq i\leq t\leq b. \end{aligned}

diff contains ℓt,m−ℓi,m\ell_{t,m}-\ell_{i,m} for every output-input pair within a chunk. We set the decay to zero for future inputs, i>ti>t, and sum over the final mode dimension to obtain the weights.

chunk_w_ref
def chunk_w_ref(
c: torch.Tensor, # (B, L, M)
kappa: torch.Tensor, # (B, L, M)
log_cum_rho: torch.Tensor, # (B, L, M)
chunk_size: int,
) -> torch.Tensor: # (B, nchunks, chunk_size, chunk_size)
B, L, M = log_cum_rho.shape
nchunks = L // chunk_size
c_chunked = c.view(B, nchunks, chunk_size, M)
kappa_chunked = kappa.view(B, nchunks, chunk_size, M)
lcr = log_cum_rho.view(B, nchunks, chunk_size, M)
diff = lcr.unsqueeze(3) - lcr.unsqueeze(2) # [B, nchunks, t, k, M]
positions = torch.arange(chunk_size, device=lcr.device)
noncausal = positions[:, None] < positions[None, :]
# Mask before exponentiating to avoid overflow above the diagonal.
decay = torch.exp(diff.masked_fill(noncausal[..., None], -torch.inf))
W = (c_chunked.unsqueeze(3) * decay * kappa_chunked.unsqueeze(2)).sum(-1)
return W

The returned W contains one Q×QQ\times Q block per chunk: these are the diagonal blocks\textcolor{#cf3f4f}{\text{diagonal blocks}} in Equation (4)\href{#eq-w-blocks}{\text{(4)}}. We can now combine them with the incoming states to compute ht,rh_{t,r}.

Computing the outputs#

Every quantity in our formula for ht,rh_{t,r} in Equation (9)\href{#eq-chunked-forms}{\text{(9)}} is now available:

ht,r=∑m=1Mct,mexp⁡(ℓt,m)sa−1,r,m⏟h_inter+∑i=atWt,iui,r⏟h_intra.\begin{aligned} h_{t,r} &=\textcolor{#218c4e}{\underbrace{\sum_{m=1}^{M}c_{t,m}\exp(\ell_{t,m})s_{a-1,r,m}}_{\texttt{h\_inter}}} \\[8pt] &\quad+\textcolor{#cf3f4f}{\underbrace{\sum_{i=a}^{t}W_{t,i}u_{i,r}}_{\texttt{h\_intra}}}. \end{aligned}

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.

chunk_readout_ref
def chunk_readout_ref(
u: torch.Tensor, # (B, L, R)
c: torch.Tensor, # (B, L, M)
states_acc: torch.Tensor, # (B, nchunks, R, M)
W: torch.Tensor, # (B, nchunks, chunk_size, chunk_size)
log_cum_rho: torch.Tensor, # (B, L, M)
chunk_size: int,
) -> torch.Tensor: # (B, L, R)
B, L, R = u.shape
M = c.shape[-1]
nchunks = L // chunk_size
u_chunked = u.view(B, nchunks, chunk_size, R)
c_chunked = c.view(B, nchunks, chunk_size, M)
log_cum_rho_chunked = log_cum_rho.view(B, nchunks, chunk_size, M)
decay = torch.exp(log_cum_rho_chunked)
c_decay = c_chunked * decay
h_inter = torch.einsum("bntm,bnrm->bntr", c_decay, states_acc)
h_intra = torch.einsum("bntk,bnkr->bntr", W, u_chunked)
return (h_inter + h_intra).reshape(B, L, R)

Putting the forward pass together#

We can now put these functions together into the full forward pass.

frac_scan
def frac_scan(
u: torch.Tensor, # (B, L, R)
c: torch.Tensor, # (B, L, M)
kappa: torch.Tensor, # (B, L, M)
rho: torch.Tensor, # (B, L, M)
chunk_size: int,
initial_state: torch.Tensor | None = None, # (B, R, M)
) -> tuple[
torch.Tensor, # (B, L, R)
torch.Tensor, # (B, R, M)
]:
log_rho = torch.log(rho)
log_cum_rho, chunk_decay = chunk_cumsum_ref(log_rho, chunk_size)
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,096ForwardBackward
Loop11.5baseline124.4baseline
Chunked PyTorch4.075e-2282×0.197632×
Timestep loop vs chunked PyTorchB=2 · R=128 · M=16 · chunk_size=64Forward0.11101001000Time per call (ms)1,0242,0484,0968,19216,38432,768LLoop: 3.76 ms at L = 1,024Loop: 7.789 ms at L = 2,048Loop: 11.5 ms at L = 4,096Loop: 26.18 ms at L = 8,192Loop: 62.43 ms at L = 16,384Loop: 124.7 ms at L = 32,768Chunked PyTorch: 2.099e-2 ms · 179× vs Loop at L = 1,024Chunked PyTorch: 2.855e-2 ms · 273× vs Loop at L = 2,048Chunked PyTorch: 4.075e-2 ms · 282× vs Loop at L = 4,096Chunked PyTorch: 8.268e-2 ms · 317× vs Loop at L = 8,192Chunked PyTorch: 0.3371 ms · 185× vs Loop at L = 16,384Chunked PyTorch: 0.5894 ms · 212× vs Loop at L = 32,768Backward0.111010010001,0242,0484,0968,19216,38432,768LLoop: 28.35 ms at L = 1,024Loop: 59.21 ms at L = 2,048Loop: 124.4 ms at L = 4,096Loop: 270.9 ms at L = 8,192Loop: 642.4 ms at L = 16,384Loop: 1899 ms at L = 32,768Chunked PyTorch: 5.903e-2 ms · 480× vs Loop at L = 1,024Chunked PyTorch: 9.505e-2 ms · 623× vs Loop at L = 2,048Chunked PyTorch: 0.197 ms · 632× vs Loop at L = 4,096Chunked PyTorch: 0.3668 ms · 738× vs Loop at L = 8,192Chunked PyTorch: 0.849 ms · 757× vs Loop at L = 16,384Chunked PyTorch: 1.95 ms · 974× vs Loop at L = 32,768

We now have a chunked PyTorch implementation of FRAC, with autograd handling the backward pass.

References#

[1]

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