- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper introduces a novel approach to sequence modeling called "neural finite state machine" (NSFM) that can be parallized via a parallel scan. In contrast to Linear RNNS, the associative mathematical object is a square matrix of "state transitions" for all possible states of that head. The paper rigorously derives that the transition matrix construct can be parallel-scanned.
Critical strengths
- The idea of parallelizing such a transition matrix is novel.
- The paper makes a rigorous derivation with good formalizations and proofs.
Critical weaknesses
- The main weaknesses of the paper lie in the poor experimental validation. The model was only tested on small synthetic tasks for which it was specifically designed for (long-sequence state tracking). There is no larger scale study that would prove the scalability of the method in terms of performance, speed, compute or memory requirements.
- The main paper is missing a section about training stability. I assume getting the gumbel softmax right is not straight-forward and might require some tricks to get it to run.
Questions for authors
- could you please add a table to compare performance, speed, compute and memory requirements across the methods you applied?
3 comments
Thank you for the additional experiments and clarifications regarding runtime. I decided to keep my score. I think it's a very interesting approach and theory, however it seems not be suitable yet for larger scale setting like language modeling.
We thank the reviewer for the follow-up and for finding the approach and the theory interesting.
We agree that large-scale language modeling is beyond the scope of this paper, and the NFSM was not designed for it here. The paper is first a general theoretical contribution. Theorem 4.1 characterizes what any affine recurrence (linear RNNs, linear attention, state space models) can track at finite precision. The NFSM is a constructive answer: it shows that this limit can be lifted while keeping scan compatibility, through a restoring organ in the sense of von Neumann.
The first theoretical half of the paper is tested on pretrained language models. In Section 7.2, released Mamba-2 checkpoints of up to 780M parameters, which we did not train, collapse on RULER as Theorem 4.1 predicts. Bounding their decay away from one, without retraining, restores retrieval with up to 128k tokens of text before the needle.
The same picture holds at 2.7B parameters. Beyond its 2k training context, Mamba-2 collapses, for the released checkpoint and after fine-tuning: the loss on PG19 books explodes, and on RULER needle 1 the passkey is lost at 16k. In ongoing work, guided by the analysis of this paper, we added a restoring organ to Mamba-2 while preserving Mamba-2 training and inference throughput. Converted from the same checkpoint and fine-tuned on 7B tokens, it keeps the PG19 loss flat up to 32k and retrieves the passkey at every tested length, without a significant drop in accuracy on common-sense reasoning benchmarks, when evaluated within the training context. This model is a separate contribution, with its own architecture, conversion recipe and evaluation at scale, which we cannot present and validate in full within this paper; we mention it here only because it bears on the scale question raised by the reviewer.
| 2.7B, trained at 2k | Zero-shot avg. (%) | Passkey 4k | Passkey 8k | Passkey 16k | Passkey 32k |
|---|---|---|---|---|---|
| Mamba-2, released | 63.2 | 100 | 99 | 0 | 0 |
| Mamba-2, fine-tuned | 64.5 | 100 | 92 | 0 | 0 |
| Hysteretic recurrence, fine-tuned | 64.3 | 100 | 100 | 100 | 100 |
Passkey: RULER needle 1, accuracy in %, 100 examples per length. Zero-shot: mean accuracy on LAMBADA, HellaSwag, PIQA, ARC-e, ARC-c and WinoGrande. Both fine-tuned models use the same recipe and token budget; one seed.
These results indicate that both the failure identified by Theorem 4.1 and the effect of adding a restoring organ carry over to language models at this scale.
Scaling the NFSM itself to language modeling is the natural next step. It depends on the fused kernel discussed with reviewer Gkds, and we will state this limitation explicitly in the final version.
Thank you again for your time and the constructive review.
We thank the reviewer for the review and answer the specific points below. The general comment describes the new experiments and lists the changes in the revised PDF.
Experimental validation and scale. Section 7.2 adds two experiments on real data, described in the general comment. The Mamba-2 experiment tests the theory on released models of up to 780M parameters, and on keyword spotting an NFSM trained on streams of a few seconds keeps its accuracy on streams of more than two hours. Moving the NFSM, or restorative recurrences in general, to large-scale experiments is ongoing work, and it needs substantial computational resources that we cannot afford during the discussion period.
Training stability. We did not observe training instability in our runs. Appendix H.3 describes the training procedure. The Gumbel estimator uses one temperature, ν=0.5, and the loss has one extra term that keeps the sampling exploratory. We used these settings on every task, without tuning. To measure how sensitive training is, we drew 15 configurations at random on keyword spotting, with learning rate from 10−4 to 3⋅10−3, batch size from 16 to 128, sampling temperature from 0.25 to 2, and weight decay from 10−6 to 10−2. Every configuration learns the task and none loses accuracy as the streams grow (Figure 8, accuracies in the general comment), and Section 7.2 now states this result. The four configurations drawn near a learning rate of 10−4 stay lower, possibly because they need more training steps.
Table comparing performance, speed, compute and memory. Thank you for the suggestion. We added Table 8, which gives, for every model on S4, the number of parameters, the failing length, and the time per training step and peak memory of one layer at L=212 and L=217. Figure 7 gives the full curves against the sequence length and the state size. Sections 5 and 6 give the theoretical cost of the NFSM, a scan of depth O(logL) whose merges take O(d) gathers. The measured numbers depend on the hardware and on dedicated kernels, which some baselines have and our implementation does not yet. Our response to reviewer Gkds discusses such a kernel.
We would be glad to answer further questions and, if time allows, to add measurements to Table 8 if the reviewer finds some missing.