Interactive Proofs of Proximity for Model Evaluation

arXiv:2609.32007 · cs.CC · Submitted 2026-09-25 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Interactive Proofs of Proximity for Model Evaluation".

Jane: Here's the gist of the paper. The paper studies interactive proofs of proximity (IPP) applied to model evaluation, where a resource-limited verifier interacts with an untrusted prover, typically a model owner, to certify statistical properties of a model under an unknown input distribution.

Tom: The formulation is designed around practical evaluation constraints by distinguishing between sampling the input distribution (real audit data or black-box sampling) and querying the model for output evaluation (chosen-randomness or gray-box access).

Jane: The core focus is on doubly-sublinear IPPs for weighted Hamming weight properties.

Tom: The initial step provides a tolerant dsIPP for ordinary Hamming weight, demonstrating that using logarithmic rounds yields O(1/g) verifier queries and O(1/g 2) honest-prover queries, improving upon the cubic dependence of prior work.

Paper summary: Tom: So we're looking at this paper titled "Interactive Proofs of Proximity for Model Evaluation". Basically, it’s about how you can check if an untrusted model is doing what it’s supposed to do, even if you only have limited resources.

Jane: That sounds like a practical problem, but what exactly are they trying to prove? What's the big idea here?

Tom: The core idea is using something called interactive proofs of proximity, or IPPs, where a resource-limited verifier talks to an untrusted prover—which is usually the owner of the model—to get some statistical guarantees about that model under an unknown input distribution.

Lu: They’re focusing on something specific: doubly sublinear IPPs and weighted Hamming weight properties. This means both the verifier and the honest prover use resources that grow slower than linearly with something, which is good for real-world auditing scenarios.

Meng: But I always wonder about the practical constraints here. How does this actually translate to running a model in production? What are they dealing with when you try to deploy this?

Lalam: I think the paper frames it by separating sampling the input distribution from querying the model and evaluating its output, which lets them treat those costs independently, distinguishing between real audit data and generated data.

Tom: Right, so they’re setting up this separation between getting samples of the inputs and actually running those inputs through the model to get an output score. That distinction is key for their protocol design.

Jane: And they specifically look at two different ways you can get that input data: real audit data, which is black-box sampling, and generated data, which is gray-box access to the sampler.

Lu: The paper shows that for ordinary Hamming weight properties, using logarithmic rounds lets the verifier make about one over g queries to the prover and only about one over g squared queries from the honest prover.

Meng: One over g squared for the honest prover sounds pretty good if it’s true. But what happens when we move to distribution-weighted Hamming weight, like in their second part?

Tom: That's where things get more specific. For black-box sampling, they find that you need about one over g squared samples but only about one over g evaluations for the model.

Jane: So the quadratic sample complexity seems necessary when you're dealing with black-box sampling in this context? Does that make sense for someone who just wants a quick check?

Paper summary: Lu: It does, because they show that in the interior regime of this problem, quadratic sample complexity is what you need to satisfy. However, if you have chosen-randomness access to a sampler instead, things get much better.

Meng: Chosen-randomness access sounds like something we can control in a lab setting. How does that change the resource requirements?

Lalam: When you have chosen-randomness access to the sampler, they can reduce the problem back down to ordinary Hamming weight, and then you only need about one over g evaluations and one over g queries from the verifier.

Tom: That's a big improvement from what they achieved for the general case. But what about when we have evaluators who might disagree?

Jane: Oh, that’s a nuance. They look at evaluator disagreement where some people might disagree on a fraction of the distribution and others by up to some gamma elsewhere.

Lu: They maintain doubly sublinear IPPs as long as g is greater than two times kappa, where kappa is defined by that fraction rho plus the deviation gamma multiplied by one minus rho.

Meng: So if there's disagreement, we still get a good proof structure, provided the disagreement isn't too messy relative to the parameter g. That gives us some confidence in deployment even with imperfect evaluation scores.

Tom: The paper also makes a trade-off between using real population data versus using synthetic data from a generator. Real population data requires about one over g squared fresh samples, but a generator lets you get away with about one over g evaluations and queries for the model.

Jane: So it seems they’re telling us that if we can generate synthetic data that mimics the real distribution well enough, we might be able to run these audits much more efficiently in a gray-box setting.

Lu: That’s the central implication: model auditing can be made much more efficient when you use synthetic data, as long as that synthetic data accurately reflects the real distribution being tested.

Meng: From an engineering standpoint, that means we need to focus on building good generators that don't just look right in a test but actually hold up when we deploy them at scale.

Paper summary: Lalam: I'm pretty sure the paper is really connecting this abstract proof theory idea with the concrete needs of production auditing. It’s showing how interactive proof theory can offer concrete protocols for what auditors actually need to do.

Tom: So, looking at it from a higher level, they’re suggesting that because model owners have way more resources than auditors, the setup assumes a powerful prover because the owner benefits from favorable audit outcomes like deployment.

Jane: I think the authors are really pushing back on just assuming you can always trust the prover without proof structure. They want to show how efficiency is achieved *with* that assumption, not despite it.

Lu: The work connects interactive proof theory with practical auditing needs by offering concrete protocols and lower bounds that characterize how much more efficient we can be than non-assisted auditing methods. It’s about proving the limits of what’s possible in this setting.

Meng: So the main thing I'm getting is that if we want to audit a model efficiently, we need to design our data access and evaluation strategy around these sublinear proof structures. It puts a specific mathematical constraint on how fast we can verify things without having infinite resources ourselves.

Lalam: The paper shows that by carefully choosing the access model—sampling versus chosen-randomness—we can get much better guarantees on resource usage, which is exactly what production engineers care about when planning an audit cycle.

Tom: So, to sum up, this paper lays out a framework using IPPs to certify statistical properties of models. It shows that depending on whether you have real data or synthetic data access, the required number of samples and queries drops significantly compared to older methods.

Jane: And the core message is that if you can make your synthetic data look good enough, model auditing becomes much more feasible for resource-limited verifiers.

Lu: It’s a solid contribution because it moves beyond just asking "is this model good?" to providing actual mathematical bounds on how efficiently we can verify its properties under these practical constraints.

Meng: I think the main thing is that it gives us a concrete way to measure the efficiency gain, which is something we desperately need when trying to build systems that scale.

Lalam: The paper shows that the cost structure of sampling versus querying allows for these different complexity bounds, which is a very practical insight for anyone designing an auditing system.

Conclusion: Tom: So we’re wrapping up this look at "Interactive Proofs of Proximity for Model Evaluation." Basically, this paper is about using interactive proofs to check if an untrusted model is doing what it’s supposed to do.

Jane: I remember the big idea being checking those statistical properties of a model even when you only have limited resources. It’s focused on these doubly sublinear proofs.

Lu: The core focus was on weighted Hamming weight properties, which is just a way of counting how often certain things happen in the model's output. They showed that using logarithmic rounds gives us better query numbers for both the verifier and the honest prover compared to older methods.

Meng: But what does that actually mean for me? If I’m trying to run this at scale, it sounds complicated. What’s the real cost here?

Lalam: Well, they break it down by separating sampling the input distribution from querying the model and evaluating its output. That lets them talk about different costs for those two things.

Tom: So they looked at black-box sampling—getting samples without being able to control which ones you get—and found that quadratic sample complexity is needed in certain situations, but that changes when you have chosen randomness access.

Jane: And when you *do* have chosen randomness access to the sampler, things simplify a lot. It turns the hard problem into ordinary Hamming weight, and you only need those logarithmic round queries for both the verifier and the honest prover.

Lu: They also looked at what happens if there’s disagreement among evaluators—if some people are off by a certain fraction of data but others are off by something else. They kept these proofs working as long as the error isn't too big compared to their round parameter, which we call kappa.

Meng: So for someone trying to deploy this, they’re saying that if you can use synthetic data that looks really good, it might be much more efficient than running a full real-world audit with massive amounts of fresh samples.

Lalam: That’s the main practical implication they push—that using synthetic data accurately mimicking the real distribution lets us get away with fewer calls and evaluations for the model itself.

Tom: To put it simply, they’re showing how to build a mathematical proof structure that lets you verify model quality much faster than traditional auditing methods allow.

Jane: It connects this heavy math to real-world needs by giving concrete protocols that show exactly how much efficiency we can expect gains when designing an audit system.

Lu: It’s a solid contribution because it gives us actual lower bounds on how efficient we can be, not just some abstract idea of what’s possible. (Sound of the radio jingle swelling slightly)

Université Paris Cité · McGill University

cs.CC

Submitted: 2026-09-25

Updated: 2026-11-12

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: The paper studies interactive proofs of proximity (IPP) applied to model evaluation, where a resource-limited verifier interacts with an untrusted prover, typically a model owner…

Key concepts

Interactive Proofs of Proximity (IPP)
A method where a limited verifier checks a model's statistical properties by interacting with an untrusted prover, like a model owner. It allows the verifier to gain confidence in the model's behavior without needing full access to its internal workings or all input data.
Doubly-Sublinear IPPs
A specific type of proof where the number of queries made by both parties (verifier and prover) grows slowly relative to the total size of the problem. The study shows that for certain properties, this approach achieves better efficiency than previous methods, reducing query complexity significantly.
Hamming Weight Properties
This refers to a statistical measure applied to model outputs. In this context, it measures how many times a specific output or feature appears in the model's predictions across the input distribution. The paper focuses on proving properties about these counts efficiently.
Access Models (Black-box Sampling vs. Chosen-Randomness)
These define how the verifier can interact with the model owner. Black-box sampling means querying samples from a real data distribution, while chosen-randomness access allows the verifier to control which samples are provided by the prover, simplifying or changing the required proof complexity.

Terminology

Summary

The paper studies interactive proofs of proximity (IPP) applied to model evaluation, where a resource-limited verifier interacts with an untrusted prover, typically a model owner, to certify statistical properties of a model under an unknown input distribution. p. 0

Where the paper says it

Interactive Proofs of Proximity for Model Evaluation Geoffroy Couteau1 , Nikolas Melissaris1 , and Tamara Paris1,2 1Université Paris Cité, CNRS, IRIF 2Université Paris Cité, McGill University Abstract We study interactive proofs of proximity (IPP) for model evaluation: 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 is shaped by the constraints of practical evaluation: it separates sampling the input distribution from querying the model and evaluating its output, allowing their costs and access patterns to be treated independently; it distinguishes real audit data (black-box sampling) from generated data (chosen-randomness, or gray-box, access to the sampler); and it allows the prover and the verifier to score outputs with different evaluators, as happens when scores come from human or judge models.

The formulation is designed around practical evaluation constraints by distinguishing between sampling the input distribution (real audit data or black-box sampling) and querying the model for output evaluation (chosen-randomness or gray-box access). p. 0
Where the paper says it

Interactive Proofs of Proximity for Model Evaluation Geoffroy Couteau1 , Nikolas Melissaris1 , and Tamara Paris1,2 1Université Paris Cité, CNRS, IRIF 2Université Paris Cité, McGill University Abstract We study interactive proofs of proximity (IPP) for model evaluation: 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 is shaped by the constraints of practical evaluation: it separates sampling the input distribution from querying the model and evaluating its output, allowing their costs and access patterns to be treated independently; it distinguishes real audit data (black-box sampling) from generated data (chosen-randomness, or gray-box, access to the sampler); and it allows the prover and the verifier to score outputs with different evaluators, as happens when scores come from human or judge models.

The core focus is on doubly-sublinear IPPs for weighted Hamming weight properties. p. 0

Where the paper says it

Our formulation is shaped by the constraints of practical evaluation: it separates sampling the input distribution from querying the model and evaluating its output, allowing their costs and access patterns to be treated independently; it distinguishes real audit data (black-box sampling) from generated data (chosen-randomness, or gray-box, access to the sampler); and it allows the prover and the verifier to score outputs with different evaluators, as happens when scores come from human or judge models. We focus on doubly-sublinear IPPs, in which both the verifier and the designated honest prover use sublinear resources, and on (weighted) Hamming weight properties, which capture the expectation of a Boolean evaluation rule under an unknown distribution and, consequently, a broad range of model-evaluation statistics.

The initial step provides a tolerant dsIPP for ordinary Hamming weight, demonstrating that using logarithmic rounds yields O(1/g) verifier queries and O(1/g 2) honest-prover queries, improving upon the cubic dependence of prior work. p. 0
Where the paper says it

As a first step, we give a tolerant dsIPP for ordinary Hamming weight. For completeness and soundness radii 𝜀c < 𝜀f and gap 𝑔 = 𝜀f − 𝜀c, its logarithmic-round instantiation uses 𝑂e(1/𝑔 ) verifier queries and𝑂 (1/𝑔 2 ) honest-prover queries, improving the cubic dependence of Amir, Goldreich, and Rothblum [ITCS 2025].

The study then extends this to distribution-weighted Hamming weight under various access models:

  1. Black-box sampling: The verifier requires theta(1/g 2) samples but only O(1/g) evaluations, showing that quadratic sample complexity is necessary in the interior regime.

  2. Chosen-randomness access to a sampler: This reduces the problem to ordinary Hamming weight, requiring O(1/g) verifier calls and evaluations.

  3. Evaluator disagreement: When evaluators may disagree on a rho-fraction of the distribution and by up to gamma elsewhere, protocols remain doubly sublinear as long as g > 2 kappa, where kappa = rho + (1 - rho) gamma.

The work quantifies the trade-off between synthetic and real data: using real population data requires theta(1/g 2) fresh samples, while a generator allows for O(1/g) calls and evaluations, trading a weaker guarantee about deployment fidelity. p. 8

Where the paper says it

A quantified trade-off for synthetic audit data. Synthetic data is known to be a weaker basis for evaluation than data collected from the deployed population: generators may misrepresent that population, in particular in low-density regions [VBQVDS23], and a certificate obtained on generated data transfers to the real population only under an additional fidelity assumption (Section 5.

The central thesis posits that the assumption of a powerful prover is motivated because the model owner benefits from favorable audit outcomes (e. p. 8

Where the paper says it

Interactive proofs of proximity assume a powerful prover and explore how it allows going beyond the efficiency limitations of property testing. A central thesis of our work is that this assumption is not just a technical convenience: it is reasonable and well-motivated in the setting of model evaluation.

g., deployment or sales) and possesses significantly more resources than auditors. p. 3
Where the paper says it

For example, sampling synthetic data is less costly than sampling “in-the-wild” data, and evaluating the output is less costly when it only involves computations than when it requires manual labeling by experts. Therefore, a dsIPP that significantly reduces the query complexity while maintaining a sample complexity close to that of a tester is still useful in settings where querying is significantly more costly than sampling.

The paper concludes that model auditing can be made much more efficient in a gray-box setting, provided synthetic data accurately mimics the real distribution. p. 9
Where the paper says it

We end this discussion with some perspectives for future works. First, we show that model auditing can be made much more efficient in a gray-box setting, but this setting implicitly assumes that the synthetic data accurately mimics the distribution of real-world data.

The framework connects interactive proof theory with practical auditing needs, offering concrete protocols and lower bounds characterizing achievable efficiency gains over non-assisted auditing methods. p. 7
Where the paper says it

Our contribution is neither aimed at advancing the theory of interactive proofs of proximity nor at proposing an end-to-end usable auditing system. Rather, it is a framework that connects the two, together with concrete protocols and lower bounds that characterize the limits of what can be achieved.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Efficient verification of statistical properties via distribution weighted Hamming weight claims: The system can verify a claim about whether a model's output distribution is close to a target distribution using interactive proofs of proximity, achieving sublinear query complexity for both the verifier and the honest prover in regimes where the tolerance gap is large enough.

  2. Flexible access models for data handling: The system can distinguish between black-box sampling (collecting fresh independent data points) and gray-box sampling (using a deterministic sampling oracle), allowing it to adapt its verification protocol based on whether synthetic or real-world data is being used.

  3. Handling evaluator disagreement in audits: The AI system can verify model claims even when the prover and verifier use different evaluation functions, modeling this as a bounded mismatch problem where the protocol uses a binary-splitting check to reduce the tolerance gap based on the mismatch parameter kappa.

  4. Application of audit criteria as weighted Hamming weight claims: The system can be used to certify complex auditing criteria like accuracy, group fairness (demographic parity, equal opportunity), and calibration by reducing them to a small number of distribution weighted Hamming weight tests.

  5. Cost-effective auditing with synthetic data: When using generated data from a public source, the system can perform the necessary model evaluations on a single set of samples while allowing multiple auditors to verify claims cheaply using only chosen randomness calls to the generator.

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 epsilon c< epsilon f and gap g= epsilon f-epsilon c, a logarithmic-round instantiation uses (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 Θ(1/g 2) verifier samples but only (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 (1/g) calls and evaluations. If the parties' evaluators disagree arbitrarily on a ρ-fraction of the distribution and by at most γ elsewhere, our protocols remain doubly sublinear whenever g>2κ, where κ=ρ+(1-ρ)γ. Applications include auditing accuracy, group fairness, calibration, harmlessness, usefulness, and average-case robustness.

Sources

Related papers