- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper finds that state-space language models expose a fixed-size recurrent state and chunk-level matrix structure (state-space duality). It proposes MPROOF, using chunkwise proving and wide arithmetization to share operator and contraction checks. On a 187M Mamba-3 model, proving 4,096 tokens takes 22.85 minutes with verification under 0.5 seconds.
Critical strengths
Precise and under-explored problem formulation. Rigorous and honest cost decomposition.
Critical weaknesses
- The verified model is too small and insufficient. Only Mamba with a size of 187M, and the longest token length is only 16k. Actual cloud-deployed LLMs will not be so small.
- KIMI/Qwen both have a hybrid model with GDN + softmax attention. Pure linear models are not common in practice.
- Even for the 187M model, this cost is not negligible. Running directly with 4K tokens takes 20 minutes, which is completely unacceptable.
- Besides, the memory pressure is also extremely high. 200GB is a very large number.
Questions for authors
Please see weakness. As far as the current experiment is concerned, this article is difficult for me to believe has any value.
Response to Reviewer ksHN
Thank you for recognizing the precise problem formulation and the rigorous, honest cost decomposition. We have expanded the model-size and sequence-length experiments and clarified the extension to hybrid models; all references are to sections of the revised PDF.
W1. "The verified model is too small ... Only Mamba with a size of 187M, and the longest token length is only 16k."
We have extended both (Section 4.2).
Model size. We now report 443M and 1.5B models, an 8x range. On one L4 at C = 128 with 1024 prefill and 1024 output tokens:
Across these runs, prover time increases by 2.2x and 7.8x relative to 187M, broadly tracking parameter count, while host memory increases by 1.7x and 2.9x. All three models complete on a single 24 GB L4. Each configuration is measured once, with its proof verified.
Sequence length. The 187M model now runs to 64K output tokens after a 1024-token prefill, 4x beyond the original 16K evaluation. This takes 82.72 min (0.076 s per output token, including prefill proving time) with 18.2 GiB peak host RSS. The cryptographic proof stays at 264.9 kB at every tested length from 1K to 64K, and peak host RSS remains approximately 18.2 GiB in the 4K, 16K, and 64K runs. These measurements show how chunkwise proving extends generation while keeping the proof compact and the per-chunk working set bounded. The full bundle grows with the public token script, reaching 1.33 MB at 64K outputs.
W2. "KIMI/Qwen both have a hybrid model with GDN + softmax attention. Pure linear models are not common in practice."
Hybrid models make the fixed-state structure useful beyond pure SSMs. The extension has two parts:
MProof establishes the fixed-state part of this design on Mamba-3 (Sections 2.2 and 3.1). Combining it with attention proofs provides a path to hybrid models, whose total cost will depend on the attention layers as well. An end-to-end hybrid prover is future work.
W3. "Running directly with 4K tokens takes 20 minutes, which is completely unacceptable."
That figure came from our original CPU-only implementation. After submission, we developed GPU acceleration and memory optimizations while retaining the proof protocol. All new results use a single machine with a 6-core CPU and one NVIDIA L4.
Two points put this cost in context:
W4. "The memory pressure is also extremely high. 200GB is a very large number."
The revised implementation brings the 187M run with 1024 prefill and 1024 output tokens to 15.6 GiB peak host RSS and 20.5 GiB peak GPU memory. Across the longer 4K–64K runs, peak host RSS remains approximately 18.2 GiB. The 1.5B model completes with 44.7 GiB peak host RSS and 21.4 GiB peak GPU memory. Section 4.2 reports host and GPU memory separately, and Appendix A.5 explains the accounting.
On the value of the work. The expanded evaluation demonstrates two forms of scaling: model size up to 1.5B at 1K outputs, and generation up to 64K outputs at 187M, each on one L4. For the 187M length sweep, the cryptographic proof stays at 264.9 kB and peak host RSS remains at or below 18.2 GiB. These results give concrete evidence that long generation can be proved through bounded chunk updates on a single-GPU machine.