Paper 2026/1038

Scaling Intelligence: Verifiable Decision Forest Inference with $\textit{Remainder}$

Ryan Cao, Modulus Labs

Nick Cosby, Modulus Labs

Vishruti Ganesh, Modulus Labs

Ende Shen, Modulus Labs

Daniel Shorr, Modulus Labs

Benjamin Wilson, Modulus Labs

Abstract

We present a highly scalable instantiation of ZKML via proof of a verifiable decision forest inference circuit using a structured version of the GKR protocol [GKR15], [Tha13]. Through a combination of data parallel GKR over a structured improvement to [ZFZS20]'s circuit, we are able to create GKR proofs for a decision forest of 128 trees, each of height 9, over a set of 128 inputs, each with 64 features, in under 54 seconds. Notably, this represents a per-tree-per-sample proof time of just over 0.003s, representing a mere 180x prover-side blowup with respect to simply running the computation on CPU. In order to achieve this performance, we present several key optimizations, including a multi-stage claim aggregation optimization to the interpolation strategy presented within [Tha13], reducing the per-stage prover runtime from $O(m \cdot n \cdot 2^n)$ to $O(m \cdot (n - k) \cdot 2^n)$ for $m$ claims over $n$ variables, where $k$ of the variables across all claimed evaluation points are coordinate-wise identical, as well as a generalization of the linear-time prover technique from [XZZPS19] to the data parallel setting, allowing us to achieve a prover time of $O(2^{s_{i + 1} + b})$. We additionally provide benchmarks demonstrating the scalability of the approach, showing a sublinear relationship between proof time and adding additional trees to the forest and inputs to the batch, as well as highlighting the efficacy of both the claim aggregation optimization, i.e., a 40-60% improvement in proof generation time over the verifiable decision forest circuit, and the "Libra-Giraffe" algorithm, i.e., a linear relationship between proof generation time and the layer size/number of data parallel circuit copies. Our GKR prover is combined with the Ligero polynomial commitment scheme for committing to the input layer of GKR circuits, and we call the combination $\textit{Remainder}$. Our system is made fully non-interactive via Fiat-Shamir, and all benchmarks were run in a non-interactive fashion using the Poseidon [GKRRS21] hash function as the random oracle.

Note: Note: This work was originally published on March 13, 2024 here: https://github.com/Modulus-Labs/Papers/blob/master/remainder-paper.pdf

@misc{cryptoeprint:2026/1038,
      author = {Makis Arsenis and Ryan Cao and Nick Cosby and Vishruti Ganesh and Ende Shen and Daniel Shorr and Benjamin Wilson},
      title = {Scaling Intelligence: Verifiable Decision Forest Inference with $\textit{Remainder}$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1038},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1038}
}