Rewrite the lookup as a sparse matrix product and reuse matmul. Zero additional commitments.

In order to prove the above, someone could directly use any state-of-the-art lookup argument. In practice, however, this would result in large prover overhead since it would have to additionally commit and open to a polynomial of size $\Omega(sd)$. Instead, we observe that the verifier has direct access to the index vector x meaning that the verification cost can be proportional to $|x| = s$. We thus propose a lightweight protocol that requires no additional commitments.

DeepProve · §4.3.1

• $Y = H_x\cdot T$ where $H_x$ is the one-hot encoding of the token sequence. The code confirms the paper: the prover builds a length-vocab reduced one-hot vector by scattering $\beta$ weights, and the verifier reconstructs its MLE directly from the plaintext token indices — no lookup, no memory argument.
• Correction to our old page's "zero commitments": that is true only of the one-hot input. The embedding matrix $T$ is committed — registered as a model polynomial and opened through the PCS like any weight. Only $H_x$ is uncommitted.
• Prover $O((t+s)d)$; the verifier's local reconstruction is $O(\text{seq len})$. Soundness inherits from the matmul PIOP.

        let (r1, r2) = one_hot_claim.point.split_at(vocab_nv as usize);
        let b1 = evals(r2);
        let sum = input.data().iter().take(unpadded_length).zip(b1).fold(
            F::ZERO,
            |sum, (token, beta)| {
                let token_value = token.to_element() as usize;
                let token_le_bits = to_bit_sequence_le(token_value, r1.len())
                    .map(|b| F::from(b as u64))
                    .collect_vec();
                let selector = beta * identity_eval(r1, &token_le_bits);
                sum + selector
            },
        );

Gather is a memory read, so it owes a read-consistency proof — and this is where Jolt Atlas attacks DeepProve directly.

Operations such as Gather require reading the tensor on which they operate, so we need to prove that those reads were correct. The most recent open-source implementation of DeepProve lacks these lookup arguments.

Jolt Atlas · §1.3

• A dedicated Read-RAF sumcheck (not the general memory stage): the prover commits a one-hot address polynomial ra, and one degree-2 sumcheck proves both the gathered value and the address read-back by γ-folding $\mathrm{dict}(k)+\gamma\!\cdot\!k$. The verifier supplies the address value from an IdentityPolynomial it evaluates in-circuit.
• Vocabulary-adaptive. GatherSmall (dict ≤ 65536) commits a single-chunk one-hot; GatherLarge uses the Shout $d$-chunk decomposition so the effective table is $d\cdot 2^{\log k_{chunk}}$ wide instead of a single ~70k-wide commitment.
• Only ra is committed; the dictionary and index tensors arrive as prior-node openings. ra's well-formedness is the standard Shout trio: booleanity (0/1), hamming-weight = 1 (exactly one row hot), ra-virtualization.
• This resolves the paper's own charge against DeepProve ("the most recent open-source implementation … lacks these lookup arguments") by showing exactly what a proven Gather read looks like in Jolt's own model.