PaperlayerView exact revision on arXiv

Source-linked AI summary

Maverick: Private and Verifiable LLM Inference Made Practical via Matrix-Vector Multiplication Delegation

Ben Merbaum, Mohammad Amin Raeisi, Wenhao Wang, Charalampos Papamanthou, Katerina Sotiraki, Fan Zhang

arXiv:2609.10264v1cs.CRcs.LG

TL;DR

Large open-source LLMs are difficult to run locally, while outsourcing inference raises privacy and correctness concerns. Maverick combines verifiable matrix–vector delegation with pseudorandom masking for private, verifiable inference, achieving substantial throughput gains over local inference on Qwen3-4B.

  • Problem

    Large-scale open-source LLMs require substantial computational resources locally, while third-party inference raises privacy and correctness concerns.

  • Method

    Maverick combines an information-theoretically sound matrix–vector delegation protocol with coding-theoretic pseudorandom masks to provide private and verifiable LLM inference with negligible server overhead.

  • Results

    Across 1–8 client threads, Maverick improves throughput over local inference by 12×–20× in standard mode, 34×–135× with offline mask generation, and 38×–157× in verification-only mode.

  • Takeaways & Limitations

    Maverick demonstrates private and verifiable outsourced LLM inference with substantial speedups on Qwen3-4B.

  • Takeaways & Limitations

    Extending privacy to a client-owned private matrix requires client-run preprocessing, which is most useful when amortized across many queries.

Abstract

from arXiv · show

Open-source large language models (LLMs) are increasingly competitive with closed-source models while offering transparency and the ability to run inference without exposing user inputs to a service provider. However, running large-scale models locally requires substantial computational resources. In practice, users may still resort to a third-party provider, giving rise to privacy and correctness concerns. Existing solutions that address these problems often impose substantial server overhead or introduce additional trust assumptions. In this paper, we present Maverick, a novel approach to private and verifiable LLM inference based on a protocol for delegating matrix-vector multiplication, a dominant operation in LLMs. At its core, Maverick provides, to our knowledge, the first information-theoretically sound verification protocol for matrix-vector multiplication delegation with transparent preprocessing, efficient (batch) verification, and virtually no server overhead. We combine this verification primitive with LPN-based pseudorandom masking to provide input privacy. We implement our matrix-vector delegation primitive and use it to build an end-to-end prototype of Maverick, which we evaluate on Qwen3-4B by measuring throughput in tokens per second. We evaluate client configurations with 1-8 threads. With one client thread and a CPU server using up to 128 threads, Maverick achieves throughput gains over local inference of up to 17x when privacy masks are generated online, 45x when they are precomputed, and 44x when only verification is required. With four client threads, the corresponding gains are 13x, 18x, and 17x. When server computation is no longer the bottleneck, client-side microbenchmarks with simulated network delay show speedups of 12x-20x, 34x-135x, and 38x-157x.

1 Introduction

Maverick enables computationally constrained clients to outsource private, verifiable LLM inference to untrusted servers with negligible server overhead. Its matrix–vector delegation protocols combine information-theoretic verification, transparent preprocessing, efficient batch checks, and pseudorandom masking, yielding substantial throughput gains on Qwen3-4B.

  • vMVMD: The vMVMD protocol provides information-theoretically sound verification with transparent preprocessing and efficient verification runtime.Preprocessing uses public matrices and codes, so its correctness can be verified without adding a trust assumption.
  • Maverick: Maverick delegates LLM linear operations to an untrusted server while clients perform inexpensive nonlinear operations locally.The prototype evaluates this design on the open-source Qwen3-4B model.
  • vMVMD: Sparse challenges reduce verification from O(mn) to Oκ(m+n), while error-correcting codes spread errors to reduce the soundness weakness of direct sparse checking.The strawman sparse protocol can miss an error affecting one coordinate with probability 1−t/m; coding-based checks address this issue.
  • pvMVMD: Pseudorandom masks generated from sparse vectors hide client inputs, and preprocessing makes mask removal efficient without adding server computation.The resulting client time is Oλ,κ(m+n), while the server performs the ordinary multiplication without overhead.
  • Implementation and evaluation: 45×, 44×, and 17× throughput improvements over local inference occur in boost, verification-only, and standard modes with one client thread.With four client threads, the corresponding improvements are 18×, 17×, and 13×.
  • Implementation and evaluation: 12×–20×, 34×–135×, and 38×–157× improvements over local inference occur for standard, boost, and verification-only modes across 1–8 client threads under simulated network delay.The experiment uses 50 ms and 100 ms network RTTs with sufficiently fast server computation.

2 Related Work

Prior approaches provide private or verifiable outsourced inference but often add server-side proof, encrypted-computation, authentication, or trust costs. Maverick targets these trade-offs with lightweight matrix–vector delegation, transparent preprocessing, and single-server operation.

  • Prior systems also include encrypted computation, plaintext authentication, VOLE proofs, and related combinations for private or verifiable matrix computation.
  • Existing inference-verification systems use interactive proofs or SNARKs that certify more computation but require additional server-side proof generation.
  • Publicly verifiable schemes require authentication or proof generation beyond the target matrix–vector multiplication, adding considerable server-side work.
  • Maverick’s concurrent comparison emphasizes single-server outsourcing and transparent preprocessing, unlike approaches requiring two non-colluding servers or a trusted setup party.
  • MOSAIC provides privacy but not verifiability and introduces nonzero protocol-error probability from Gaussian noise, whereas Maverick’s matrix–vector delegation introduces no such error.

3 Preliminaries

The preliminaries define finite-field vector and code notation, Freivalds-style verification, error-correcting codes, and the dual-LPN assumption used for privacy. They establish that ordinary matrix–vector verification remains quadratic, motivating the paper’s coding-based construction.

  • The notation defines finite fields, sparsity, support, Hamming weight, computational and statistical security parameters, and negligible functions.
  • Freivalds’ algorithm checks a claimed product by sampling a random vector and comparing two projected products without explicitly computing the full matrix product.
  • For matrix–vector multiplication, Freivalds’ algorithm still costs O(n^2) field operations, matching direct computation asymptotically.
  • Linear codes encode vectors as redundant codewords; rate and relative distance characterize efficiency and error-detection capability.

4 Model and Security Definitions

The model considers a client delegating matrix–vector products to an untrusted server while seeking efficient computation, verification, and optionally input privacy. Security combines information-theoretic verification soundness with computational privacy and transparent reusable preprocessing.

  • vMVMD lets a client verify whether an untrusted server’s output y satisfies y = Mx for a public matrix M.
  • Protocols are efficient when they run in oλ,κ(mn) time and asymptotically optimal when they run in Oλ,κ(m+n), the cost of processing inputs and outputs.
  • The vMVMD interface preprocesses M into public parameters and verifies input–output pairs using those parameters.
  • vMVMD soundness is information-theoretic: no unbounded adversary can produce an incorrect pair accepted with non-negligible probability over verifier randomness.
  • pvMVMD encrypts x, lets the server compute on the ciphertext, then verifies and decrypts the result while requiring client privacy.
  • Transparent preprocessing contains no secret trapdoor or client-specific key, can be publicly validated, and can be reused across clients and future queries.

5 Verifiable Matrix–Vector Multiplication Delegation (vMVMD)

The vMVMD construction combines sparse challenges with high-distance linear codes and transparent preprocessing to obtain efficient, information-theoretically sound verification. Batch verification reuses challenges and auxiliary preprocessing to reduce client online work for multiple matrix–vector claims.

  • The protocol is an asymptotically time-optimal vMVMD construction using coding theory and includes a batch-verification extension for LLM workloads.
  • 5.1 Our Construction: Sparse Freivalds challenges reduce verification to Oκ(m+n), but the uncoded check has soundness error at least 1−t/m for a one-coordinate error.
  • 5.1 Our Construction: High-distance encoding spreads every nonzero error across at least δN coordinates, making sparse challenge supports likely to intersect the encoded error.
  • 5.2 Security: Theorem 5.2 establishes completeness and soundness, with code-distance failure contributing an additional p_fail term to the overall error bound.
  • 5.3 Efficiency: Oκ(m+n) verification is asymptotically time-optimal, while preprocessing computes Q = G^⊤M in O(mn) time.
  • 5.4 Batch Verification: An additional challenge–response round moves expensive projection work to the server and reduces client online time to the stated batched complexity.
  • 5.4 Batch Verification: Batch verification achieves perfect completeness and can choose parameters giving soundness error at most 2^−κ.

6 Private and Verifiable Matrix–Vector Multiplication Delegation (pvMVMD)

pvMVMD combines verifiable matrix–vector delegation with dual-LPN-based pseudorandom masking to provide private, verifiable computation with transparent preprocessing and efficient client online time. Under stated code and dual-LPN assumptions, it achieves completeness, soundness, and client privacy while keeping preprocessing quadratic and online client work linear.

  • Construction: pvMVMD combines vMVMD verification with dual-LPN-friendly masking codes to hide client inputs without adding server overhead.The client masks x using a pseudorandom vector G_xe_x, while preprocessing computes P = MG_x.
  • Limitations: Extending privacy to hide a client-owned matrix requires private client-run preprocessing, making amortization across many queries important.This stronger privacy variant is most useful when preprocessing can be amortized across repeated queries.
  • Verification: The client verifies each response through repeated sparse-code checks comparing masked matrix–vector products before accepting.The protocol computes G_y^⊤ b_y and repeats ℓ checks involving Qb_x and G_y^⊤b_y.
  • Security: Under relative-distance and dual-LPN assumptions, pvMVMD satisfies completeness, soundness, and client privacy.Incorrect responses are accepted with probability at most 2^-κ, while privacy follows from computational indistinguishability of pseudorandom masks from uniform vectors.
  • Efficiency: O_λ,κ(m+n) client online time and O(mn) preprocessing keep online delegation linear while preprocessing remains quadratic.VERIFY runs in O_κ(m+n), ENCRYPT and DECRYPT in O_λ(m+n), and preprocessing computes P and Q through linear-time code encodings.

7 Evaluations

The evaluation measures pvMVMD costs and Maverick’s throughput against local inference and prior verifiable MVM systems. Maverick provides substantial speedups, especially when mask generation is precomputed or verification is performed without privacy.

  • 7.1 Evaluation of pvMVMD: At n = 2^14, client online work is approximately 12.4× smaller than the delegated multiplication, while small matrices can make outsourcing un worthwhile.At n = 2^13, client online time is 4.56 ms versus 34.68 ms for server multiplication.
  • 7.1 Evaluation of pvMVMD: At n = 2^14, one-time preprocessing takes approximately 135.80 s, including 46.57 s for privacy and 89.23 s for verification.Preprocessing grows approximately quadratically because it processes the complete matrix for both privacy and verification.
  • 7.1 Evaluation of pvMVMD: Across evaluated dimensions, pvMVMD is 2.5×–34.8× faster than Dumas–Zucca and 60.7×–194.8× faster than Sum-Check+BaseFold.At n = 4,096, pvMVMD takes 421.943 ms versus 1.056 s and 82.196 s, respectively.
  • 7.2 Evaluation of Maverick: 45.85× is Maverick’s maximum end-to-end speedup over local inference in boost mode, compared with 17.62× in standard mode.Verification-only mode also provides substantial speedups; the comparison spans client and server thread counts, with communication excluded.
  • 7.2 Evaluation of Maverick: Increasing server threads beyond 64 provides no consistent speedup, indicating an implementation parallelization limit near 64 server threads.The evaluation fixes 64 server threads and two client threads for detailed end-to-end breakdowns.
  • 7.2 Evaluation of Maverick: In standard mode, inference takes 958.3 ms at 8.35 tokens/s, yielding a 14.7× speedup over the 0.57 tokens/s local baseline.Privacy-mask generation keeps the client as the main bottleneck; boost and verification-only modes shift the bottleneck to the server.

8 Conclusions and Future Directions

Maverick delegates LLM linear operations through a new private and verifiable matrix–vector multiplication primitive. The Qwen3-4B prototype demonstrates substantial speedups, while reducing communication rounds remains future work.

  • 8 Conclusions and Future Directions: Maverick combines transparent-preprocessing matrix–vector delegation with efficient client verification to support private and verifiable LLM inference.The implementation delegates model linear operations and evaluates the approach on Qwen3-4B.
  • 8 Conclusions and Future Directions: Qwen3-4B experiments demonstrate substantial speedups for Maverick over local inference.The conclusion identifies reducing communication rounds for private inference as an important direction for future work.
  • 8 Conclusions and Future Directions: Reducing communication rounds for private inference is identified as an important direction for future work.

A Learning Parity with Noise

This section defines dual-LPN over code-generator distributions and relates its security to resistance against linear tests. It also records assumptions about noise structure and the equivalence between dual-LPN and primal LPN.

  • A Learning Parity with Noise: Dual-LPN assumes that samples Ge, combined with a random inner product, are computationally indistinguishable from uniform over the field.The assumption is parameterized by a field, dimensions, code-generator distribution, and noise distribution.
  • A Learning Parity with Noise: Dual-LPN is equivalent to primal LPN through the parity-check matrix of the dual code, with n′ = N − n.The equivalence follows by relating generator and parity-check matrices through row reduction.
  • A Learning Parity with Noise: Linear testing searches for a vector v whose inner product with LPN samples has non-negligible bias.Resistance to such tests follows from sufficiently large code minimum distance, which reduces bias against sparse noise.
  • A Learning Parity with Noise: For an asymptotically good code with constant relative distance, choosing sparsity t = O_λ(1) supports λ − log_2 N bits of security under the stated bound.The bound is obtained by setting e^(−δt) ≤ 2^(−λ+log_2 N).
  • A Learning Parity with Noise: The linear-test framework does not cover highly structured noise with sufficiently many samples, so the construction uses exact noise distributions to mitigate algebraic attacks.The section specifically mentions Arora–Ge attacks as an example of this risk.

B Repeat-Accumulate-Accumulate Codes

RAA codes instantiate the dual-LPN masking assumption and provide efficient encoding and syndrome computation. Their non-algebraic structure and minimum-distance analyses support, but do not fully establish, their LPN-friendliness.

  • B Repeat-Accumulate-Accumulate Codes: Maverick instantiates dual-LPN with Repeat-Accumulate-Accumulate codes, for which prior work supports LPN-friendliness and asymptotic goodness.The section describes RAA codes as non-algebraic and conjectures that efficient decoding is unavailable.
  • B Repeat-Accumulate-Accumulate Codes: RAA generators compose repetition, random permutation, diagonal randomization, and accumulation matrices.The component operations respectively repeat entries, permute positions, multiply by nonzero diagonal values, and compute prefix sums.
  • B Repeat-Accumulate-Accumulate Codes: RAA encoding requires at most 4N field operations, while syndrome computation requires approximately 5N field operations.These costs follow from composing repetition, permutation, randomization, and accumulation operations.
  • B Repeat-Accumulate-Accumulate Codes: Minimum-distance analyses over prime fields provide evidence for constant relative distance and therefore security against linear tests.Earlier work covered binary fields, while later analyses extended asymptotic goodness and concrete bounds to arbitrary prime fields.
  • B Repeat-Accumulate-Accumulate Codes: For fixed F_q with q > 2^31 and δ = 0.5, choosing r = N/n ≥ 3 makes the failure probability decrease polynomially with N.A public distance-testing framework can further reduce the failure probability in polynomial time.

C Private Matrix Extension

The private-matrix extension hides both operands while delegating matrix-vector multiplication, and it provides completeness, soundness, and client privacy with near-linear online client work.

  • Private-matrix pvMVMD: Private-matrix pvMVMD extends delegation to hide both a client’s matrix M and vector x from the compute server.This models outsourcing linear-layer computation for a proprietary model owned by the client.
  • Protocol construction: The protocol preprocesses a masked matrix, encrypts the input with a sparse pseudorandom mask, verifies the server response, and decrypts the result using local state.The main algorithms are PREPROCESS, ENCRYPT, VERIFY, and DECRYPT.
  • Security: Under trapdoor correctness, pseudorandomness, and dual-LPN assumptions, pvMVMD satisfies completeness, soundness, and client privacy.The theorem requires |F| ≥ 4, code-distance conditions, and polynomially many independent samples.
  • Correctness: Decryption removes the privacy-mask contribution and the trapdoored matrix contribution from the server response to recover y = Mx.The identity follows from P = bMGx, TDM.EVAL(tdM′,x) = M′x, and bM = M+M′.
  • Efficiency: The online client work is Oλ,κ(m+n) aside from trapdoor evaluation, while the server performs exactly one field matrix-vector multiplication.Preprocessing requires O(mn) field operations; linear-time trapdoor evaluation yields asymptotically optimal online time.

D Soundness Composition

Maverick composes a private delegation protocol with a sound verifiable delegation layer: verification is added without changing encryption or decryption, and incorrect outputs are rejected except with negligible probability.

  • Composition principle: A private delegation protocol can be made sound by composing it with a sound verifiable delegation protocol.This composition is the technique used to construct ΠpvMVMD from ΠvMVMD.
  • Construction: The composed protocol runs verifiable preprocessing and verification alongside private preprocessing, while retaining the private protocol’s encryption and decryption.The composition therefore separates soundness from the private delegation mechanism.
  • Soundness: If the decrypted output differs from Mx, the corresponding server response cannot satisfy the verified masked claim, so VERIFY detects the inconsistency except with negligible probability.The argument uses completeness of the private protocol and soundness of the verifiable protocol.

E Attack on Slalom at the Carnival

The paper identifies a privacy flaw in Slalom at the Carnival: its efficiency requires a short projection basis, which lets the server distinguish masked inputs from random ones.

  • Privacy attack: S@C claims client privacy, but the paper shows that a semi-honest server can recover projections of client input vectors.The attack targets the protocol’s masking construction rather than its matrix-vector computation.
  • Attack condition: S@C is efficient only when the number of preprocessing vectors ℓ is smaller than the input dimension n.In this range, the server can use Gaussian elimination to construct a projection matrix annihilating all preprocessing vectors.
  • Consequence: The annihilating projection matrix distinguishes the transmitted masked vector from a uniformly random vector, preventing a privacy simulator from working for every input.Thus the protocol’s claimed client privacy fails in the parameter range needed for efficiency.
Loading 2609.10264v1…