NL-PAC: Specification Ambiguity and Certified Minimax Risk Floors in LLM-Mediated Supervision

Technical Summary: NL-PAC: Specification Ambiguity and Certified Minimax Risk Floors in LLM-Mediated Supervision

Problem Statement
Modern learning pipelines increasingly rely on Large Language Models (LLMs) to provide labels, evaluations, and feedback for tasks specified in natural language. A critical issue arises when a natural language specification admits multiple valid interpretations (readings), but the supervision channel (the LLM acting as a judge) adopts one interpretation without revealing which one is operative. This regime, termed target-blind supervision, creates a fundamental identification problem: additional observations from the same channel do not resolve the ambiguity because the channel's observation law is independent of the operative target.

Unlike classical statistical learning theory, where the task specification and supervision channel are distinct, LLM-mediated systems collapse this separation. The task is defined by a natural language instruction, and the supervision signal is produced by a model interpreting that same instruction. Consequently, the learner faces an irreducible risk floor caused not by statistical noise or a corruption budget, but by the indistinguishability of admissible readings inherent to the model's decoding of the prompt. The paper asks: How much minimax risk remains when the channel defining admissible targets is also the sole source of supervision, and can this risk floor be certified from unlabeled inputs?

Methodology: The NL-PAC Framework
The authors introduce Natural Language PAC (NL-PAC), a framework that formalizes the interaction between a fixed model, a prompt, and a decoding threshold to define the geometry of admissible labels.

1. Model-Admissible Geometry:

   • For a fixed description $f_{NL}$, model $LLM_\theta$, and threshold $\tau$, an admissible label set $A_\tau(x)$ is defined at each input $x$ containing all labels $y$ where the model's decoding probability $\pi(y|f_{NL}, x) \ge \tau$.
   • The admissible-overlap mass $D^*_\tau$ is the probability mass of inputs where $|A_\tau(x)| \ge 2$ (i.e., multiple labels are admissible).
   • The framework defines a model-admissible labeling class $F_{\tau, \zeta}$ (labelings admissible on all but a $\zeta$-mass set) and its core $Sel_\tau$ (almost-everywhere admissible labelings).
   • The diameter of this core, $\text{diam}_P(Sel_\tau)$, is shown to equal $D^*_\tau$.

2. Target-Blindness and Risk Floors:

   • The supervision channel is target-blind if the observation law does not depend on the operative target. Under this condition, the paper proves that no learner can distinguish between targets that induce the same observation law.
   • Pairwise Floor: For any two admissible targets $f_1, f_2$ that disagree on a set of mass $D$, the minimax risk is at least $D/2$, regardless of sample size.
   • Exact Minimax Value: Over the entire admissible core $Sel_\tau$, the exact minimax risk is $V^*_\tau = \mathbb{E}_x[1 - 1/k(x)]$, where $k(x)$ is the number of admissible labels at $x$. This value is attained by a data-independent randomized learner that selects uniformly from the admissible set at each input.
   • Coherent Readings: The paper distinguishes between pointwise admissible selections and coherent readings (global interpretations defined by specific reading clauses). It establishes a "bridge" bound showing that the minimax risk over a finite family of coherent readings is close to $V^*_\tau$ only if the family satisfies an $\eta$-uniform coverage condition and low admissibility violation.

3. Finite-Sample Certification:

   • The paper constructs finite-sample certificates for these quantities using held-out unlabeled inputs from the deployment distribution.
   • Exposed Probabilities: If the model's decoding probabilities are accessible, the audit estimates $D^*_\tau$ and $V^*_\tau$ directly, providing Hoeffding-based lower bounds on the minimax risk floor.
   • Sampled Decoding: If only sampled outputs are available, the audit uses a plug-in estimator. This introduces a threshold-margin term ($\kappa(\xi)$) and a finite-depth error term, which can render the certificate vacuous if the decoding depth is insufficient or if many inputs lie near the threshold $\tau$.

Key Contributions

1. Representation: Formalizing the model-admissible labeling class and proving its diameter equals the admissible-overlap mass $D^*_\tau$, with tight bounds for tolerance classes.
2. Blind-Channel Value: Proving that target-blind supervision imposes a sample-size-independent minimax floor of $D^*_\tau/2$ (for binary overlap) or $V^*_\tau$ (exact value), attained by a data-independent strategy.
3. Coherent Readings Bridge: Deriving conditions under which the pointwise minimax value transfers to a finite family of global reading clauses, highlighting the gap between pointwise admissibility and semantic coherence.
4. Certification: Developing algorithms to compute one-sided confidence bounds for the risk floor from unlabeled data, distinguishing between cases where probabilities are exposed versus when only samples are available.

Empirical Results
The authors conducted an audit on a frozen Qwen 2.5–3B model:

• Positive Certificate: For a specific content moderation prompt (P1), the audit found a significant overlap mass ($D^*_\tau = 0.29$ at $\tau=0.20$), certifying a minimax risk floor of 0.0838. This indicates that even with infinite data, the worst-case error cannot be reduced below this threshold due to the model's inherent ambiguity.
• Zero Certificates: A paraphrase of the prompt (P2) and exact-rule control tasks yielded zero certificates. P2 collapsed to a single label (entropy diagnostic), while the exact rules left no room for ambiguity.
• Transfer Failure: A "bridge" audit testing whether the pointwise certificate transfers to two supplied candidate reading clauses failed. While the mixture coverage was favorable, the clauses violated the admissibility condition (high violation rates), resulting in a loose bound that did not certify the transfer of the positive floor.
• Sampling Limits: A sampled-decoding audit with shallow depth ($r=3$) yielded vacuous (zero) certificates due to the large finite-depth correction term, illustrating the cost of not having access to raw probabilities.

Significance and Scope
The paper claims to provide a decision-theoretic step missing from current LLM-as-a-judge diagnostics. While existing work focuses on judge bias, calibration, or agreement rates, NL-PAC quantifies the irreducible ambiguity imposed by the specification-channel pair itself.

• Modesty of Claims: The authors explicitly state that the certificate is model-relative and specific to the audited tuple $(LLM_\theta, \Pi, \tau, P)$. It does not identify the designer's intended target nor establish human task ambiguity. A positive floor certifies that this specific channel cannot resolve the ambiguity, not that the task is inherently ambiguous to humans.
• Implications: A positive certificate implies that increasing sample size or improving the learner will not reduce the worst-case risk; the only path to lowering the floor is to change the information structure (e.g., clarify the specification, use a different model, or introduce reading-revealing supervision).
• Limitations: The guarantee relies on target-blindness and the observability of admissible sets. Extending the guarantee to coherent human readings requires external validation of the reading pool's coverage and admissibility, which the paper's bridge audit found to be a non-trivial hurdle.

In summary, NL-PAC provides a rigorous method to audit the "floor" of learnability in LLM-mediated supervision, demonstrating that specification ambiguity can create permanent, certifiable barriers to performance that are independent of data volume.