Eliciting Honest Answers Without Peers or Ground Truth
The core problem of information elicitation is simple to state: you have a worker completing a task, and you want to know how much information their output carries about the underlying task. The standard approaches all require something extra. Peer prediction needs a second worker doing the same job. Scoring rules need a future observation to compare against. Likelihood-ratio methods need to estimate densities that may be intractable. Each dependency adds complexity, fragility, or cost.
Zachary Robertson at Stanford takes a different path in "Mutual Evaluation and Supervision without Peers." The paper shows that if you can independently replicate a single worker on the same task, you can estimate both Pearson and Shannon information about the task without any of these requirements. No peers, no ground truth, no density estimation. The mechanism uses waiting times for critic-defined agreement events across two streams of samples: replications from the same task and samples from fresh tasks.
The Setup: A Worker, a Critic, and Replications
The formal model has three components. A task $X$ is drawn from a known prior $P$. A worker channel $w_1: X \to \Delta(R)$ maps tasks to distributions over returns. The worker produces a return $Y$ from this channel, then applies a reporting strategy $\sigma$ to produce a reported return $r$. A critic defines a rule $c: R \times R \to \{0, 1\}$ that determines which pairs of returns count as "matching." Both the worker and the critic are strategic agents seeking a common evaluation score.
The key insight is that a valid critic rule, one where the matching relation forms an equivalence relation on the return alphabet, can be represented as a finite annotation. There exists a map $g: R \to B$ from returns to a finite label set such that $c(y, y') = \mathbf{1}\{g(y) = g(y')\}$. This means the critic is fundamentally deciding which returns count as the same type. The annotation alphabet can always be chosen with size at most $|R|$.
This separation between the critic rule and the evaluation score it induces is central to the framework. The rule is the critic's strategic choice. The score is the mechanism's output. The analysis tracks how the rule's information loss, measured as regret relative to an unrestricted envelope, affects incentives.
The Replication Loop: Two Clocks, One Score
The mechanism works as follows. Fix a task $x$ and produce an anchor return $Y$ from the worker channel. Then run two parallel streams of independent replications.
The alternative stream draws $\tilde{Y}_1, \tilde{Y}_2, \ldots$ from the same task $x$. The null stream draws $Z_1, Z_2, \ldots$ from freshly sampled tasks $x_1, x_2, \ldots$ drawn from the prior $P$. Both streams are conditionally independent given the fixed task.
Define two hitting times. The alternative clock $\tau_{\text{alternative}}$ is the first index $n$ where the critic matches the anchor: $c(Y, \tilde{Y}_n) = 1$. The null clock $\tau_{\text{null}}$ is the first index $n$ where the critic matches the anchor against a fresh-task sample: $c(Y, Z_n) = 1$.
The geometric distribution governs both. Conditional on the anchor's annotation being $a$ and the task being $x$, the alternative clock is geometric with parameter $q_x(a) = \Pr(A = a \mid X = x)$, and the null clock is geometric with parameter $p(a) = \Pr(A = a)$. The ratio of these conditional probabilities is exactly the pointwise mutual information, and averaging over the joint distribution of $(X, A)$ gives the mutual information.
Two Scoring Rules With Unbiased Estimates
The paper provides two concrete scoring mechanisms, each producing an unbiased estimate of a different information functional.
The Pearson collision payment works as follows. Draw one same-task replication $\tilde{Y}_1$. If the critic does not match ($c(Y, \tilde{Y}_1) = 0$), stop and pay $-1$. If it matches, start the null clock and pay $\tau_{\text{null}} - 1$. The expected value of this payment equals $I_{\chi^2}(X; A)$, the Pearson mutual information between the task and the annotated return.
The KL two-clock payment runs both clocks simultaneously and pays the difference of harmonic numbers: $W_{\text{KL}} = H_{\tau_{\text{null}} - 1} - H_{\tau_{\text{alternative}} - 1}$, where $H_m = \sum_{j=1}^{m} 1/j$. The expected value equals $I(X; A)$, the Shannon mutual information.
The proof is clean. The expectation of $H_{\tau - 1}$ for a geometric random variable with parameter $p$ is $-\log p$. So the KL payment's conditional expectation given $X = x$ and $A = a$ is $\log q_x(a) - \log p(a) = \log(q_x(a)/p(a))$, which is the pointwise mutual information. Averaging over $(X, A)$ yields the mutual information $I(X; A)$.
Theorem 2 formalizes three properties: the replication sequences terminate almost surely (with probability one), both payments are integrable (finite expected absolute value), and the expected payments equal the corresponding mutual information functionals.
Why Replica Information Is Not Task Information
A natural objection is: why not just compare two replicas directly? If $Y$ and $Y'$ are independent replications from the same task, isn't $I(Y; Y')$ a sufficient measure?
The paper's motivating example shows this fails. Let $X$ be a fair bit and let $Y = X \oplus N$ and $Y' = X \oplus N'$ where $N, N'$ are independent Bernoulli noise bits with parameter $\varepsilon$. The true task information is $I(X; Y) = \log 2 - h(\varepsilon)$, where $h$ is the binary entropy function. But $Y \oplus Y' = N \oplus N'$, so $I(Y; Y') = \log 2 - h(2\varepsilon(1-\varepsilon))$, which is strictly smaller for $0 < \varepsilon < 1/2$.
The Data Processing Inequality makes this rigorous: $I(Y_1; Y_2) \leq I(X; Y_1)$, where the left side is the peer proxy and the right side is the true task information. Comparing replicas directly only gives a lower bound. The replication-loop mechanism avoids this by comparing same-task replications against fresh-task samples, which allows recovery of the actual information retained about the task rather than just the information shared between copies.
Critic Regret and the Value Envelope
The framework introduces a critic regret decomposition. For any valid critic $c$ with annotation $A = g(Y)$, the regret for Shannon information is $r_{\text{KL}}(c; P, k) = I(X; Y) - I(X; A) = I(X; Y \mid A)$, the conditional mutual information between task and return given the annotation.
This is the task information that the annotation throws away. Zero regret means the annotation is sufficient: conditioning on the annotation does not change task beliefs. The paper shows that a valid critic has zero regret exactly when $\pi_y = \bar{\pi}_{g(y)}$ for every $y$ with $p_Y(y) > 0$, where $\pi_y(x) = \Pr(X = x \mid Y = y)$ and $\bar{\pi}_a(x) = \Pr(X = x \mid A = a)$.
The literal-agreement critic $c_{\text{id}}(y, y') = \mathbf{1}\{y = y'\}$ always achieves zero regret and maximizes the envelope. But it need not be the only optimal critic. A nuisance-removing annotation like $g(x, u) = x$, stripping an independent nuisance variable $U$ from the return, can also achieve zero regret while compressing the return alphabet. This is useful because the runtime may depend on the complexity of the type annotations.
Sample Complexity and Variance Tradeoffs
The number of required replications is random and depends on the critic rule. The paper provides bounds on expected sample counts. For KL, the expected total count is $1 + \mathbb{E}[1/p(A)] + \mathbb{E}[1/q_X(A)] \leq 1 + 2m$, where $m = |\text{supp}(A)|$. For Pearson, the expected count is $3 + I_{\chi^2}(X; A) \leq 2 + m$.
Variance behaves differently between the two mechanisms. KL has uniformly bounded conditional variance (at most $\pi^2/3$) because harmonic numbers have bounded variance. Pearson's variance is not uniformly bounded: when $A = X \sim \text{Bernoulli}(\varepsilon)$, the variance of the Pearson payment grows as $(1-\varepsilon)/\varepsilon$ even though the expected sample count is constant at 4. This is a sampling-variance tradeoff inherent to the mechanism.
Connection to Variational Peer Prediction
The paper connects to variational peer prediction (VPP) through critic timing. In the correlated-agreement (CA) timing, the critic rule is selected assuming truthful reporting and then held fixed. In the VPP timing, the critic is reoptimized based on the actual outcome law.
A worked example with Boolean returns makes the difference concrete. At truth, both timings agree. But when a worker deviates by flipping a report, the committed critic's regret rises from zero to $1/2$, and the CA score drops from $5/4$ to $3/4$. The reoptimized VPP score remains at $5/4$ because it re-attains the envelope at the new law. The committed-loss identity decomposes the payoff change as the value decrease plus the new-law regret.
Theorem 5 (Equilibrium Transfer) connects the two: if weak robustness holds, meaning worker garbling cannot increase the envelope, then truth together with any critic optimal at truth is a Nash equilibrium of the replication game. The committed critic's fixed strategy, combined with the worker's truthful reporting, jointly maximizes the common payoff.
Formalization in Lean 4
Every theorem in the paper is formalized in Lean 4 and publicly available. The repository at https://github.com/zrobertson466920/mutual-evaluation maps each manuscript claim to specific formal declarations. The paper notes that AI tools assisted with formalizing proofs but not with formulating or reviewing theorem statements. The article prose was human-authored from the reviewed declarations.
This formalization is not incidental. The paper occupies an unusual position at the intersection of game theory, information theory, and mechanism design, where the correctness of incentive properties and unbiasedness guarantees depends on precise mathematical reasoning. The Lean formalization provides a machine-checked guarantee that the proofs are correct.
Practical Implications for Evaluation Systems
The mechanism class illustrated here matters for anyone building evaluation systems where ground truth is unavailable and recruiting multiple independent workers is expensive or impossible. The replication-loop approach requires only the ability to run the same computational worker multiple times under the same task specification.
The cost is a random, potentially unbounded number of replications. For practical deployment, this means the mechanism is best suited to settings where replication is cheap relative to the value of the information, or where the evaluation can tolerate variable completion times. The variance tradeoff between Pearson and Shannon scoring also matters: Pearson is simpler (one clock gate, one null search) but can have high variance, while KL is more complex (two parallel clocks) but has bounded variance.
The critic's annotation choice is a design decision with direct incentive consequences. A coarse annotation reduces sampling cost but increases regret. A fine-grained annotation approaches the envelope but may require more replications. The paper's sufficiency condition (zero regret when $\pi_y = \bar{\pi}_{g(y)}$) provides a principled way to choose: merge annotations that do not change task beliefs, and keep distinct any annotations that do.
What This Changes About How We Think About Elicitation
The traditional view treats peer prediction and scoring rules as fundamentally different mechanisms. Peer prediction compares workers. Scoring rules compare reports to outcomes. Robertson's framework unifies them under a common model where the critic's agreement rule is the strategic variable. The replication loop is not just a technical trick for removing the peer dependency. It is a demonstration that the critic's notion of agreement, treated as a choice rather than a given, determines both the information elicited and the incentives provided.
The framework also makes explicit something the peer prediction literature often leaves implicit: the critic has incentives too. A critic that commits to a rule before observing the outcome law may face regret if the worker deviates. A critic that reoptimizes always achieves the envelope at the new law but loses the incentive guarantees that commitment provides. This timing distinction connects the framework to variational peer prediction and shows that the choice between committed and reoptimized critics is not merely implementation-level but determines which equilibrium concepts apply.
By replacing the second worker with independent replications of the first, the paper does not just remove a dependency. It redefines what it means to evaluate a report honestly, showing that the strategic choices available to a critic, how they define agreement, when they commit to a rule, and how they annotate returns, are inseparable from the quality of the information elicited.