Can linear-attention RNNs recognise formal regular languages?
Attention-free recurrent models like RWKV promise linear-time inference. The open question is capacity: does the compressed recurrent state actually retain what a Transformer's full attention window retains? I built a controlled setting where the answer is checkable rather than vibes-based.
The benchmark
Four synthetic regular languages, chosen so each isolates a different failure mode rather than blending them:
Hard negatives
Random negatives are too easy: a model can pass by learning surface statistics. Every negative in the suite is a perturbation of a positive at edit distance 1-3, so a correct answer requires the decision boundary to sit exactly on the language, not near it.
The CUDA operator
RWKV's WKV state transition is sequential, so the naive PyTorch implementation launches a kernel per timestep and dominates training time. I wrote wkv_kernel.cu as a custom C++/CUDA extension with a fused forward and backward pass, which made sweeps over sequence length and model size affordable enough to run the full architecture grid.
// on results
Quantitative results from this internship are not published. The setup, benchmark design and kernel are described here in full; I'm happy to walk through findings and their limitations in conversation.