← All problems
#94 SSM Selective Scan Medium

Implement the forward pass of a State Space Model (SSM) selective scan, the core operation in Mamba-style sequence models. Given an input sequence u, time-step parameters delta, state-transition matrix A, input projection B, output projection C, and skip-connection weights skip, compute the output sequence y in float32.

h₀ h₁ h₂ h₃ Ā Ā Ā B̄u₀ B̄u₁ B̄u₂ B̄u₃ y₀ y₁ y₂ y₃

Implementation Requirements

Implement the function solve(u, delta, A, B, C, skip, y, batch, seq_len, d_model, d_state) with the signature unchanged. Do not use external libraries beyond the allowed framework. Write the result into the pre-allocated output tensor y.

For each batch b, position t, and channel d, the computation is:

\[ \bar{A}_{b,t,d,n} = \exp(\Delta_{b,t,d} \cdot A_{d,n}) \] \[ \bar{B}_{b,t,d,n} = \Delta_{b,t,d} \cdot B_{b,t,n} \] \[ h_{b,t,d,n} = \bar{A}_{b,t,d,n} \cdot h_{b,t-1,d,n} + \bar{B}_{b,t,d,n} \cdot u_{b,t,d} \] \[ y_{b,t,d} = \sum_{n} C_{b,t,n} \cdot h_{b,t,d,n} + \text{skip}_d \cdot u_{b,t,d} \]

The initial hidden state \(h_{b,-1,d,n} = 0\) for all \(b, d, n\). All channels d are independent: they share the same B and C projections but have separate state-transition rows in A.

Example

Input:
  u     = [[[1.0, 0.0], [0.0, 1.0], [1.0, 1.0], [0.0, 0.0]]]  shape (1,4,2)
  delta = [[[1.0, 1.0], [1.0, 1.0], [1.0, 1.0], [1.0, 1.0]]]  shape (1,4,2)
  A     = [[-0.5, -1.0], [-0.5, -1.0]]                         shape (2,2)
  B     = [[[1.0, 0.0], [0.0, 1.0], [1.0, 1.0], [0.5, 0.5]]]  shape (1,4,2)
  C     = [[[1.0, 0.0], [0.0, 1.0], [1.0, 1.0], [0.5, 0.5]]]  shape (1,4,2)
  skip  = [0.0, 0.0]                                            shape (2,)
  batch=1, seq_len=4, d_model=2, d_state=2

Derivation (delta=1 everywhere, so A_bar_dn = exp(A_dn)):
  A_bar[d=0] = [exp(-0.5), exp(-1.0)] ≈ [0.607, 0.368]
  A_bar[d=1] = [exp(-0.5), exp(-1.0)] ≈ [0.607, 0.368]

  Hidden state h has shape (d_model=2, d_state=2); initial h = zeros.
  t=0: h = [[1.000, 0.000], [0.000, 0.000]]  →  y[0,0] = [1.000, 0.000]
  t=1: h = [[0.607, 0.000], [0.000, 1.000]]  →  y[0,1] = [0.000, 1.000]
  t=2: h = [[1.368, 1.000], [1.000, 1.368]]  →  y[0,2] = [2.368, 2.368]
  t=3: h = [[0.830, 0.368], [0.607, 0.503]]  →  y[0,3] = [0.599, 0.555]

Output:
  y = [[[1.000, 0.000], [0.000, 1.000], [2.368, 2.368], [0.599, 0.555]]]

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.