Celer: A Lookup Argument for Large-Scale Queries

Lookup arguments are designed to prove that all elements in a query vector appear in a lookup table. These arguments are critical for efficiently proving ZK-unfriendly statements, such as range checks and the evaluation of complex functions. Most existing lookup arguments are optimized for scenarios where the query size is smaller than the table size. However, in many real-world applications, the query size $m$ is often much larger than $n$, the table size. This disparity leads to inefficiencies in such schemes.

To overcome this limitation, we propose Celer, a novel lookup argument in which the prover's runtime increases slowly with $m$, thereby providing improved scalability. The efficiency of our lookup PIOP stems from reducing the number of commitments to be sublinear in the query size $m$, while maintaining field operations linear in $m$. Experimental results demonstrate that our lookup scheme significantly outperforms state-of-the-art lookup schemes. For the workload of query size $m=2^{28}$ and table size $n=2^{16}$ (a real world case in proving Llama language model inference), our scheme achieves a 25.9$\times$ prover-time speedup over plookup and is 9.4$\times$ faster than LogUp.