Skip to content
Preprint

Interactive Proofs of Proximity for Model Evaluation

Sep 2026 · 0 citations · 32 references
Computer Science

TL;DR

This formulation separates sampling the input distribution from querying the model and evaluating its output; distinguishes real audit data from generated data; distinguishes real audit data from generated data (chosen-randomness, or gray-box, access to the sampler); and allows the prover and verifier to use different evaluators.

Abstract

We study interactive proofs of proximity (IPPs) for model evaluation, where a resource-limited verifier interacts with an untrusted prover, typically the model owner, to certify statistical properties of a model under an unknown input distribution. Our formulation separates sampling the input distribution from querying the model and evaluating its output; distinguishes real audit data (black-box sampling) from generated data (chosen-randomness, or gray-box, access to the sampler); and allows the prover and verifier to use different evaluators. We focus on doubly-sublinear IPPs, where both the verifier and honest prover use sublinear resources, and on (weighted) Hamming weight properties. For ordinary Hamming weight, we give a tolerant doubly-sublinear IPP. For completeness and soundness radii $\varepsilon_c<\varepsilon_f$ and gap $g=\varepsilon_f-\varepsilon_c$, a logarithmic-round instantiation uses $\widetilde{O}(1/g)$ verifier queries and $O(1/g^2)$ honest-prover queries, improving the cubic dependence of Amir, Goldreich, and Rothblum (ITCS 2025). We prove matching query lower bounds up to polylogarithmic factors. For distribution-weighted Hamming weight, black-box sampling requires $\Theta(1/g^2)$ verifier samples but only $\widetilde{O}(1/g)$ evaluations; the quadratic sample complexity is necessary in the interior regime. With chosen-randomness access, the problem reduces to ordinary Hamming weight, yielding $\widetilde{O}(1/g)$ calls and evaluations. If the parties'evaluators disagree arbitrarily on a $\rho$-fraction of the distribution and by at most $\gamma$ elsewhere, our protocols remain doubly sublinear whenever $g>2\kappa$, where $\kappa=\rho+(1-\rho)\gamma$. Applications include auditing accuracy, group fairness, calibration, harmlessness, usefulness, and average-case robustness.

View source

Similar papers

Sep 2026

Consequences of Polylogarithmic Membership Comparability for SAT

This expanded version of this paper develops the full weak-advantage regime, where saving $2^{-O((log n)^d)}$ gives randomized SAT exponent $d$ and PH exponent $d^k$ at fixed level $k$; the quasipolynomial and exponential hierarchy consequences; binary-comparator advice bounds; and the certificate-length boundary betwe...

Sebastian Ben Daniel · 0 citations
Preprint Oct 2026

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages

Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evalu...

Marshall Ball, Peter Crawford-Kahrl, V. Podolskii et al. · 0 citations
Sep 2026

Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors

The main result extends the optimal nondeterministic advice bound for P-selective sets to every binary membership-comparable language, and a deterministic polynomial-time algorithm for promise Unique-Circuit-SAT gives 2-mc subseteq P/O(n).

Sebastian Ben Daniel · 1 citation
Preprint Sep 2026

Fresh-Challenge VDF Attestations for Model-Relative Response Latency

Can a finite verifier obtain public, model-relative evidence about response latency for sequential computation? Verifiable delay functions (VDFs) make this possible in principle: evaluation requires T sequential steps, whereas verification is efficient in the security parameter and polylogarithmic in the numerical valu...

Ansar Yesmukhanov, Aruzhan Tlessova · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.