Building HSS from Scratch

I implemented the Hierarchical State Space forward pass from scratch in C. No libraries. No framework. Just arrays and loops.

The core equation is simple: h_{t+1} = A·h_t + B·x_t. But making it work efficiently took months.

The challenge was discretization. A continuous state space needs to be turned into a discrete recurrence. I used first-order Taylor expansion: A_bar = I + Δt·A, B_bar = Δt·B. This gives a simple update rule that compiles to efficient machine code.

The forward scan is sequential — each timestep depends on the previous. I implemented it as a plain for-loop over the sequence dimension. For v0.1.0, this is single-threaded CPU. GPU parallel scan is planned for v0.5.0.

What works: the math. Given random weights, the state evolves correctly. The scan produces the expected O(n log n) memory footprint — we store O(log n) intermediate states instead of O(n) like attention.

What doesn't work yet: training. The backward pass requires differentiating through the scan, which needs a custom autodiff node. That's a stub in v0.1.0.

The HSS code lives in src/arch/hss/. It's about 500 lines of C89-compatible C. No VLAs. No _Atomic. Compiles with MSVC, GCC, Clang.