acceptodds
Under review as a conference paper at ICLR 2027

Incremental Verifiable Inference for State-Space Language Models

Abstract

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 increase in sequence length, total prover time grows by only , 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/.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
verifiable inference, state-space models, incremental verifiable computation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ksHNOpenReview ↗
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
  1. 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.
  2. KIMI/Qwen both have a hybrid model with GDN + softmax attention. Pure linear models are not common in practice.
  3. Even for the 187M model, this cost is not negligible. Running directly with 4K tokens takes 20 minutes, which is completely unacceptable.
  4. 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.

1 comment
AuthorsOpenReview ↗

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:

ModelProver timePeak host RSSGPU memoryProof size
187M2.93 min15.6 GiB20.5 GiB264.9 kB
443M6.42 min26.0 GiB20.8 GiB368.8 kB
1.5B22.92 min44.7 GiB21.4 GiB390.0 kB

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:

  • GDN layers have a fixed-size recurrent state, like Mamba. The same chunk-boundary approach can organize their proofs, with arithmetic checks designed for the GDN update rule and its numerical program.
  • Softmax-attention layers require checks for the attention computation, including softmax, together with authenticated KV-cache reads and appends. Their access to a growing history adds sequence-dependent work.

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.

  • The original 22.85 min covered 4,096 tokens including prefill. MProof now proves 1024 prefill plus 4,096 output tokens, 5,120 in total, in 6.62 min.
  • Over 64K outputs, the cost averages 0.076 s per output token, including prefill proving time.

Two points put this cost in context:

  • Proof delivery can be asynchronous. A service can return responses before proof completion and produce proofs for requests selected for audit. Prover time then determines the compute cost and how soon those responses can be verified.
  • Published runtime context (Section 4.3). zkAgent reports 0.2955–0.4162 s per output token for GPT-2 (124M) on a 32-core CPU. MProof records 0.1701 s per output token for 187M at 1024 prefill plus 1024 outputs on a 6-core CPU and one L4. These figures provide context across different models, hardware, and workloads. At 64K outputs, MProof's measured 264.9 kB cryptographic proof is over three orders of magnitude smaller than the 333.7 MB–10.61 GB projected for zkAgent from its reported measurements.

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.

Reviewer_9HCjOpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes a cryptographic method to verify state-space language model outputs. This is important because LLM providers may not faithfully serve the required models, and this work provides one way to provide proofs for Mamba 3 models up to 188M params, with some chunking efficiency ideas.

Critical strengths

The paper studies an important problem to ensure an LLM provider is serving the exact same model as advertised, and the method seems to be fast and efficient compared to other methods.

Critical weaknesses

I don't have any background in cryptography or zero knowledge proofs, so I cannot evaluate the technical details of the paper. However, as an outsider, the following weaknesses come to mind: Given that ICLR is a machine learning conference, the vast majority of the audience do not have any background in cryptography, and despite the introduction's effort in motivating the problem, I believe the authors should provide more background in terms of what works have been done in this space, and what exactly their contribution means. Apart form terminology, I have the following questions:

  • Why is the 22 minute time an important factor in providing a proof from a practical perspective? To my understanding, we need occasional proof checks, and as long as the proof time is reasonable, it doesn't matter how long it takes.
  • Why only Mamba 3 and up to 187M parameters? What prevents this method from being scaled up to real world hybrid LLMs?
Questions for authors

See weaknesses

1 comment
AuthorsOpenReview ↗

Response to Reviewer 9HCj

Thank you for recognizing the importance of the problem and the efficiency of MProof. We answer each point directly below; all references are to sections of the revised PDF.

1. "The authors should provide more background in terms of what works have been done in this space, and what exactly their contribution means."

Prior work (Section 2.1). Existing ways to audit a model service either give indirect evidence, such as behavioral audits and model fingerprints, or rely on trusted hardware. Cryptographic proofs bind an output to committed model parameters and an agreed computation. Prior proof systems provide different ways to organize this work:

  • zkLLM and zkGPT target Transformer forward-pass proofs.
  • zkAgent proves a whole completed transcript at once, so its working set grows with transcript length.
  • zkRNN proves recurrent steps one at a time.

Our contribution. We show how the model architecture can make long generation cheaper to prove, and exploit two properties of state-space models:

  • Fixed-size state. Mamba-3's recurrent state does not grow with the sequence. Each proof extension checks a new chunk and its connection to the preceding state (Section 3.1).
  • State-space duality. SSD exposes matrix structure within a chunk. Wide arithmetization uses this structure and repeated operators to share checks across the chunk's tokens (Section 3.2).

At fixed model and chunk width, proving work grows linearly with generated length, while the cryptographic proof stays compact. The measured 187M proof is 264.9 kB from 1K to 64K outputs (Section 4.2), over three orders of magnitude smaller than the projected 64K proof sizes for zkAgent (333.7 MB–10.61 GB; Section 4.3). The client verifies that the public tokens follow the committed model, prompt, and specified fixed-point program, without rerunning inference. Section 4.5 evaluates that program's agreement with BF16, and Section 2.3 now introduces the proof tools in plain terms.

2. "Why is the 22 minute time an important factor ... we need occasional proof checks, and as long as the proof time is reasonable, it doesn't matter how long it takes."

Occasional auditing is one useful deployment: responses can be returned before proof completion, with proofs produced asynchronously for selected requests. Prover time still affects two practical quantities:

  • Cost and coverage. Faster proving lets a fixed compute budget audit more requests and accommodate longer generations.
  • Time to verification. A response gains its cryptographic guarantee when its proof is checked. Faster proving shortens that interval, even when response delivery proceeds independently.

The revised measurements quantify both the cost of a short audit and its growth with request length. With the GPU implementation developed after submission, 1024 prefill plus 4,096 output tokens take 6.62 min. A 64K-output request takes 82.72 min on one L4, averaging 0.076 s per output token including prefill proving time. Peak host RSS stays approximately 18.2 GiB from 4K to 64K outputs (Section 4.2).

3. "Why only Mamba 3 and up to 187M parameters? What prevents this method from being scaled up to real world hybrid LLMs?"

Why Mamba-3. Its fixed-size recurrent state gives each proof update a bounded interface to the preceding computation. Full attention accesses a KV cache that grows with the sequence, so its proof must also account for that growing history (Section 2.2).

Model size. We now report 443M and 1.5B models (Section 4.2). On one L4 at C = 128 with 1024 prefill and 1024 output tokens:

ModelProver timePeak host RSSProof size
187M2.93 min15.6 GiB264.9 kB
443M6.42 min26.0 GiB368.8 kB
1.5B22.92 min44.7 GiB390.0 kB

Across these single verified runs, prover time increases by 2.2x and 7.8x relative to 187M, broadly tracking parameter count. All three configurations complete on one 24 GB L4.

Hybrid LLMs. The fixed-state approach provides a basis for proving the recurrent layers of a hybrid:

  • Mamba layers can use MProof's existing checks when their computation matches the supported numerical program.
  • Other fixed-state layers, such as Gated DeltaNet, can use the same chunk-boundary approach with checks designed for their update rule and numerical operations.
  • Softmax-attention layers need proofs of attention and softmax, together with authenticated KV-cache reads and appends. Their access to the growing history adds sequence-dependent work.

This gives a concrete path to a hybrid prover: retain bounded recurrent boundaries and add the attention proofs. The resulting cost depends on the attention layers' computation and cache access; implementing and evaluating that full system is future work.

Reviewer_LDPkOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
2(+1)
Soundness
3
Read review
Paper summary

This paper proposes MProof, an incremental proof system for state-space models(SSMs), which enables clients to verify the faithfulness of inference procedure without rerunning the target model, at a hundred-million-parameter scale. Authors’ approach consists of two major components: Chunkwise Proving and Wide Arithmetization. Chunkwise Proving incrementally extends proofs over fixed-size chunks, eliminating the need to re-prove earlier computations. Wide Arithmetization reduces redundant proof computations by jointly verifying operations across generated tokens. Furthermore, they adapt GKR composition and evaluation accumulation to SSMs’ inference procedure to further reduce recursive proving overhead. Experiments show that MProof achieves near-linear scaling of proving time with sequence length while maintaining nearly constant verification time.

Critical strengths
  1. A notable strength of this work is its end-to-end system implementation. Rather than focusing on an isolated proof technique, the authors integrate multiple techniques into a complete framework for verifying long, autoregressive inference.

  2. The paper demonstrates that cryptographic proofs of long, autoregressive inference can scale near-linearly with sequence length on SSMs. This suggests that the well-known efficiency advantage of SSMs on dealing with long sequences is extended to verifiable inference.

  3. The effectiveness of the proposed optimization techniques is supported by ablation studies, suggesting that these techniques play an important role in improving proving efficiency.

Critical weaknesses
  1. In Section 3.3, several technical concepts (e.g., GKR/LogUp reductions) are introduced in a terse manner without sufficient explanation. While they are treated as background knowledge in this paper, an intuitive figure showing how these components interact and reduce computational overhead would improve the clarity of this section.

  2. The model size is fixed throughout the paper, leaving the model-size complexity analysis in Section 3.5 and Appendix C (Eq. 25) unvalidated. At least one smaller or larger model (or both) would clarify how prover time and memory grow with model size.

  3. The ablations in Table 3 are conducted only at a small configuration (C=8,T=32C = 8, T = 32), whereas the default configuration uses C=128C = 128 (Table 2), and the paper does not explain this choice. Why was this smaller configuration chosen? How do the gains from token-wide and SSD target sharing vary with chunk width CC?

Questions for authors

See Critical Weaknesses part.

4 comments
AuthorsOpenReview ↗

Response to Reviewer LDPk

Thank you for the careful reading and for recognizing the end-to-end system, its near-linear scaling, and the role of our optimizations. Your suggestions led to three concrete additions; all references are to sections of the revised PDF.

W1. "GKR/LogUp reductions are introduced in a terse manner ... an intuitive figure showing how these components interact and reduce computational overhead would improve the clarity."

Section 2.3 explains both tools in plain terms before Section 3 uses them:

  • GKR checks arithmetic. To check Y = XWᵀ without recomputing it, the verifier checks a randomly weighted combination of the entries of Y, and sumcheck reduces this to a few evaluations of X and W.
  • LogUp checks table lookups. Every (input, output) pair of a quantized nonlinearity must be a table row; LogUp compares a random fingerprint of all queries with a fingerprint of the table, weighted by how often each row is used.

The overview figure in Section 3.1 illustrates joint checks within a chunk and the compact information carried between chunks. For C = 128, the process is:

  1. Wide arithmetization stacks repeated operations across the 128 tokens into tensor relations; for example, the projections y_t = W x_t become one relation Y = XWᵀ.
  2. GKR and LogUp check these relations jointly across the chunk. The reductions leave short claims of the form "this committed tensor has value v at point r".
  3. Accumulation merges these claims with those carried from earlier chunks, retaining one claim per registered tensor family.
  4. Recursion checks the reduced verifier computation and extends the running proof.

Step 2 shares checking work across tokens (Section 3.2); steps 3–4 keep the recursive computation bounded at fixed model and chunk width (Section 3.3). W3 below gives a default-width experiment isolating gate-product sharing.

W2. "The model size is fixed throughout the paper, leaving the model-size complexity analysis in Section 3.5 and Appendix C (Eq. 25) unvalidated."

We have added 443M and 1.5B models (Section 4.2), all using the same machine configuration with a 6-core CPU and one NVIDIA L4, at C = 128 with 1024 prefill and 1024 output tokens:

ModelProver timePeak host RSSGPU memoryProof size
187M2.93 min15.6 GiB20.5 GiB264.9 kB
443M6.42 min26.0 GiB20.8 GiB368.8 kB
1.5B22.92 min44.7 GiB21.4 GiB390.0 kB

The measurements are consistent with the predicted scaling:

  • Prover time increases by about 2.2x for 443M and 7.8x for 1.5B, relative to 187M. This broadly tracks parameter count, as expected from the dominant dense-layer term, layers × width², in Section 3.5 and Appendix C.5.
  • Memory increases more slowly over the tested sizes. Host RSS rises by 1.7x and 2.9x, while GPU memory stays at 20.5–21.4 GiB. All three configurations complete on one 24 GB L4.
  • Proof size stays below 400 kB.

Each configuration is measured once, with its proof verified. These runs use the GPU implementation and memory optimizations developed after submission; Appendix A.4 records the builds and timing boundaries.

W3. "Why was this smaller configuration chosen? How do the gains from token-wide and SSD target sharing vary with chunk width C?"

Why C = 8, T = 32. The small setting let us isolate each sharing mechanism cheaply. Following your suggestion, we now report the ablation at the default setting: C = 128 with 1024 prefill and 1024 output tokens (Section 4.4). The control checks the gate and SwiGLU products one token at a time; everything else, including the 16 recursive updates, is identical.

ConfigurationProver timePer output tokenPeak RSS
MProof175.29 s171.2 ms15.58 GiB
No sharing338.26 s330.3 ms21.49 GiB

At the default width, token-wide sharing makes proving 1.93x faster and saves 5.9 GiB of peak memory. It also cuts the recursive circuit from an estimated 13.47–13.87M to 6.15–6.55M constraints per update (Appendix A.6).

How the gains vary with C. The analysis in Section 3.2 describes the checking work saved as the chunk grows:

  • Token-wide sharing combines repeated operator checks across C token positions into a joint tensor check.
  • SSD target sharing combines C per-target reductions and reduces the decay-product checking path to two stages.

These structural savings explain how sharing scales with C. Their end-to-end benefit also depends on the cost and size of the wider tensors. The new ablation measures gate-product sharing at C = 128; the full-system sweep separately measures the overall chunk-width tradeoff. From C = 8 to C = 128, prover time falls 10.6x (30.95 to 2.93 min) and recursive updates fall 16x, while peak RSS rises from 7.6 to 15.6 GiB. At C = 256, prover time rises to 3.92 min and RSS to 31.2 GiB, consistent with the growing SSD tensors. We therefore use C = 128, the fastest tested width, as the default (Section 4.2).

Thank you for the detailed response and the additional experiments.

First of all, I recommend that the authors highlight the added or changed text in the revised PDF, which would make the comparison much easier.

The 443M/1.5B results address my second concern, and the new Section 2.3 makes the GKR/LogUp roles clearer.

However, two points remain.

  • Figure 1 labels wide arithmetization, GKR reduction and accumulation, but it does not show the flow of the procedure—what each step consumes and produces—nor the fourth step (recursive verification) or where LogUp enters. The four-step description in your response is exactly what a general ML reader needs; please add it as a flow figure (or extend Figure 1) and as the opening of Section 3.3.

  • It looks like Table 3’s experimental design changed. The original submission isolated token-wide sharing and SSD target sharing separately, but the revised PDF does not have such a result: the new control disables only gate/SwiGLU product sharing, so the effect of SSD target sharing at the default width is no longer measured. Could you explain why this axis was dropped?

We are glad the larger-model results and Section 2.3 were helpful. The revised PDF marks first-round changes in blue and this round’s changes in brown.

Proof flow. Thank you for suggesting that we show what each step takes as input and produces as output. Figure 2 and the opening of Section 3.3 now trace one chunk through all four steps, including where LogUp enters and how recursive verification extends the running proof.

Sharing ablations. Our first revision kept SSD target sharing enabled to isolate gate and SwiGLU product sharing. Table 3 now reports all four combinations of token-local and SSD target sharing at C = 128. To stay within the host memory available on our test machine, we used the first two layers of the 187M checkpoint for all four configurations. At that depth, the no-sharing configuration peaked at 25 GiB of host memory. Disabling SSD target sharing alone increased prover time by 80%.

Thank you for the revision and for highlighting the changes. The Figure 2 and the opening of Section 3.3 now make the four-step flow clear, including where LogUp enters and how recursion extends the proof, and the full 2×2 ablation at C=128 answers my question about SSD target sharing. Both concerns are resolved, and I will raise my score accordingly.

I remain somewhat unsure about the fit of this work for ICLR, but I leave that judgment to the AC and other reviewers.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.