Incremental Verifiable Inference for State-Space Language Models

Large language models (LLMs) are widely deployed as remote services, where users observe only the inputs and outputs and cannot directly check whether the advertised model was executed faithfully. This challenge becomes more pronounced for long autoregressive generations, where an execution may span thousands of dependent tokens and proving the full sequence can become increasingly expensive. We present \mproof, an incremental proof system for end-to-end autoregressive inference in state-space language models at the hundred-million-parameter scale. Our design builds on two properties of modern state-space models. Their recurrent state has a fixed size independent of sequence length, providing a compact interface between successive chunks; state-space duality (SSD) additionally represents the computation within a chunk as parallel matrix operations. \mproof exploits these two structures to verify completed chunks jointly and extend an existing proof as generation proceeds, without revisiting earlier model computation. On a 187M-parameter Mamba-3 model, \mproof proves 4,096 tokens in 22.85 minutes using 128-token chunks, with prepared verification taking 0.451 seconds. Across a $16\times$ increase in sequence length, total prover time grows by only $13.6\times$, while prepared verification stays below 0.5 seconds and cryptographic proof size is unchanged. Our code is available at https://anonymous.4open.science/r/MProof-6D18/.