📊 statistics

Concentration bounds on response-based vector embeddings of black-box generative models

This paper establishes high-probability concentration bounds for response-based vector embeddings of black-box generative models using the Data Kernel Perspective Space method, thereby determining the sample size required to accurately approximate population-level embeddings and providing algebraic tools applicable to noisy Classical Multidimensional Scaling.

Original authors: Aranyak Acharyya, Joshua Agterberg, Youngser Park, Carey E. Priebe

Published 2026-06-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Aranyak Acharyya, Joshua Agterberg, Youngser Park, Carey E. Priebe

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a room full of different "black box" AI models. You can't see inside them to understand how they work, but you can ask them questions and see what they say. The goal of this paper is to figure out how to mathematically map these AI models into a simple chart so we can compare them, and more importantly, to prove how many questions and answers we need to ask to make that map accurate.

Here is the breakdown using simple analogies:

1. The Problem: The "Black Box" Mystery

Think of each AI model as a mysterious chef in a kitchen. You can't see their recipes (the code), but you can order dishes (queries).

The Goal: You want to know which chefs are similar and which are different.
The Method: You ask every chef the same set of questions (queries). You take their answers, turn them into numbers (vectors), and calculate how "different" their answers are from one another.
The Map: Using a technique called Multidimensional Scaling (think of it as a GPS for data), you plot these chefs on a 2D or 3D map based on how similar their answers are. Chefs who give similar answers end up close together; those who give different answers end up far apart.

2. The Catch: We Only Have Samples

In a perfect world, we would know the exact probability of every possible answer a chef could give. This would give us a "perfect map" (the population-level embedding).

Reality: We don't know the perfect probabilities. We can only ask each chef a limited number of times (say, 100 times) and average their answers. This gives us a "sample map."
The Risk: If we don't ask enough questions, our sample map might be blurry or wrong. The chefs might look like they are in the wrong neighborhood.

3. The Paper's Big Claim: The "Safety Net"

The authors of this paper didn't just draw the map; they built a mathematical safety net around it. They calculated a "concentration bound."

The Analogy:
Imagine you are trying to guess the average height of a group of people by measuring a few of them.

If you measure only 2 people, your guess could be way off.
If you measure 1,000 people, your guess is very close to the truth.
This paper provides a formula that says: "If you measure X people, you can be 99% sure that your guess is within Y inches of the true average."

In this paper, the "people" are the AI models, the "measurements" are the responses to queries, and the "guess" is the position on the map.

4. The Key Findings (The Rules of the Game)

The paper proves that for this map to be accurate, you need to follow a specific recipe involving three numbers:

$n$ : The number of AI models (chefs).
$m$ : The number of different questions asked.
$r$ : The number of times you ask each question to each model (replicates).

The Magic Formula:
The paper shows that to get a sharp, accurate map, the number of times you repeat the questions ( $r$ ) needs to grow much faster than the number of models ( $n$ ).

Specifically, if you double the number of models, you need to increase your sample size ( $r$ ) by a factor of four (or more) to keep the map accurate.
They also found that asking more different questions ( $m$ ) helps, but increasing the number of repeats ( $r$ ) is the most powerful way to reduce error.

5. The "Real World" Test

The authors didn't just do math on paper. They ran two types of experiments:

Simulations: They created fake AI models that spit out random numbers. They showed that as they increased the number of samples, the error on the map shrank exactly as their formula predicted.
Real AI: They used a real Large Language Model (Google's Gemma). They asked it questions, took the answers, and turned them into vectors. Even with real, messy data, the "safety net" held up. In every single test, the actual error was smaller than the maximum error their formula predicted.

Summary

This paper is a guarantee manual for anyone trying to compare AI models using their answers.

What it does: It tells you exactly how much data (questions and repeats) you need to collect to be confident that your comparison map is accurate.
The takeaway: You can't just ask a few questions to a few models and expect a reliable result. To get a clear picture, you need to ask many questions many times, especially as you add more models to the mix. The paper gives you the math to know exactly when you have "enough" data.

Technical Summary: Concentration Bounds on Response-Based Vector Embeddings of Black-Box Generative Models

Problem Statement
Generative models, such as large language models (LLMs) and text-to-image diffusion models, are increasingly ubiquitous yet often function as black boxes, where their internal functional forms are inaccessible. To perform statistical analysis and inference on a collection of such models, researchers require methods to represent them as vectors in a finite-dimensional Euclidean space based on their responses to user queries. While methods like the Data Kernel Perspective Space (DKPS) embedding exist to generate these vector representations by computing pairwise dissimilarities of model responses, existing literature has primarily focused on asymptotic consistency. There is a lack of theoretical guarantees for finite-sample scenarios, particularly regarding how many sample responses are required to estimate population-level vector representations with a specific accuracy and confidence level. This paper addresses the need for high-probability concentration bounds for these sample-based vector embeddings.

Methodology
The paper utilizes the DKPS embedding framework, a variant of Classical Multidimensional Scaling (MDS). The setting involves a set of $n$ generative models $\{f_1, \dots, f_n\}$ responding to $m$ queries $\{q_1, \dots, q_m\}$ .

Population Level: The true response of model $f_i$ to query $q_j$ is a random vector $g(f_i(q_j))$ with distribution $F_{ij}$ . The population representation is defined by the matrix of expected responses $\mu_i$ . Pairwise population dissimilarities $\Delta_{ii'}$ are computed as the normalized Frobenius norm of the difference between $\mu_i$ and $\mu_{i'}$ . These dissimilarities are embedded into $\mathbb{R}^d$ via MDS to yield true perspectives $\psi$ .
Sample Level: Since true distributions are unknown, the authors use $r$ independent and identically distributed (iid) replicates of responses for each model-query pair to estimate the mean responses $\bar{X}_i$ . A sample dissimilarity matrix $D$ is constructed from these empirical means.
Embedding: The sample dissimilarity matrix is doubly centered to form $\hat{B}$ , and MDS is applied to obtain the sample vector embeddings $\hat{\psi}$ .

The core theoretical approach involves establishing concentration inequalities for the spectral norm of the difference between the sample matrix $\hat{B}$ and the population matrix $B$ . The authors rely on perturbation bounds for eigenvectors (Davis-Kahan Theorem) and eigenvalues (Weyl's Inequality) to relate the error in the dissimilarity matrices to the error in the resulting vector embeddings.

Key Assumptions
The theoretical results rely on two primary assumptions:

Assumption 1 (Distributional): The standardized concatenated mean responses are light-tailed with uncorrelated entries. Specifically, the density of the standardized vector is proportional to $e^{-U(w)}$ with a Hessian bounded below, and the responses are almost surely bounded. This is justified by the Central Limit Theorem for large sample sizes and the finite token nature of LLM outputs.
Assumption 2 (Rank): The rank of the population dissimilarity matrix $B$ is a constant $d$ that does not grow with $n$ . This implies the true perspectives reside in a fixed-dimensional space.

Key Results
The paper establishes high-probability concentration bounds for the estimation error of the vector embeddings:

Matrix Concentration (Theorem 1): Under Assumption 1 and assuming the trace of the response covariance matrices is uniformly bounded by $\Gamma$ , the spectral norm error $\|\hat{B} - B\|$ is bounded with probability at least $1 - e^{-nc}$ by a term scaling as $\frac{n}{\sqrt{mr}} + \frac{1}{r}$ .
Embedding Concentration (Theorem 2): Under Assumptions 1 and 2, and a signal-to-noise condition, there exists an orthogonal matrix $W^*$ such that the estimation error $\|\hat{\psi}W^* - \psi\|$ is bounded with high probability. The bound scales with the condition number of $B$ and the term $\left(\frac{n}{\sqrt{mr}} + \frac{1}{r}\right)$ .
Consistency Conditions (Proposition 2): The paper provides a sufficient condition for the eigenvalues of $B$ to grow linearly with $n$ (specifically $\lambda_d(B) \geq C(d)n$ ). This occurs if the collection of population mean response matrices contains only a finite number of distinct members (communities) with proportional membership. Under these conditions, if the number of replicates $r$ grows faster than $n^2$ (i.e., $r = \omega(n^2)$ ) while $m$ is constant, the estimation error approaches zero.

Numerical Experiments
The authors validate their theoretical bounds through two experiments:

Simulations: Using synthetic high-dimensional random vectors to simulate LLM responses, the study demonstrates that as $n$ increases (with $r \approx n^{2.25}$ ), the empirical estimation error decreases and remains well within the theoretical upper bound. The bounds held for 100% of Monte Carlo samples.
Real Data Analysis: Using the Google-gemma-2-2b-it model and Nomic-embed-text-v2-moe, the authors sampled responses to two specific queries. With $r \approx n^{2.75}$ , the empirical estimation error was consistently smaller than the theoretical bound across various values of $n$ , achieving 100% empirical coverage.

Significance and Claims
The paper claims to provide the first finite-sample, high-probability concentration bounds for response-based vector embeddings of black-box generative models. The significance lies in:

Practical Guidance: The bounds offer a theoretical basis for determining the necessary sample size $r$ to achieve a desired accuracy in inference tasks (e.g., testing if two models have the same perspective) with a specific confidence level.
Trade-off Analysis: The results suggest that accuracy can be improved not only by increasing the number of replicates ( $r$ ) but also by increasing the number of queries ( $m$ ), though the paper notes the trade-off between $m$ and the quality of row-wise estimators requires further investigation.
Non-Asymptotic Foundation: By establishing these bounds, the work facilitates statistical analysis in the non-asymptotic regime, moving beyond the unrealistic assumption of infinite sample sizes.
Realistic Setting: The methodology operates under a black-box setting, requiring only access to model responses, making it applicable to real-world proprietary or closed-source models.

The authors modestly note that their condition regarding the rank of $B$ and the growth of eigenvalues is sufficient but may be relaxed in future work to accommodate scenarios with an increasing number of distinct model communities. They also conjecture that their signal-to-noise condition is necessary, drawing parallels to simpler settings in existing literature.