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

arXiv: https://arxiv.org/abs/2607.08961 · HTML: https://mlsanity.com/paper/2607.08961/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 65 references that are in the map.
- First posted on arXiv 9 Jul 2026.

## Builds on (most cited first, 26 of 26)

- [G-Eval: NLG Evaluation using GPT-4 with Better Human Alignment](https://mlsanity.com/paper/2303.16634/) (2023)
- [A Survey on LLM-as-a-Judge](https://mlsanity.com/paper/2411.15594/) (2024)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [Prometheus: Inducing Fine-grained Evaluation Capability in Language Models](https://mlsanity.com/paper/2310.08491/) (2023)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [The Effects of Reward Misspecification: Mapping and Mitigating Misaligned Models](https://mlsanity.com/paper/2201.03544/) (2022)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [What Can We Learn from Collective Human Opinions on Natural Language Inference Data?](https://mlsanity.com/paper/2010.03532/) (2020)
- [The 'Problem' of Human Label Variation: On Ground Truth in Data, Modeling and Evaluation](https://mlsanity.com/paper/2211.02570/) (2022)
- [We're Afraid Language Models Aren't Modeling Ambiguity](https://mlsanity.com/paper/2304.14399/) (2023)
- [Eliciting Human Preferences with Language Models](https://mlsanity.com/paper/2310.11589/) (2023)
- [Stop Measuring Calibration When Humans Disagree](https://mlsanity.com/paper/2210.16133/) (2022)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Learning with Bounded Instance- and Label-dependent Label Noise](https://mlsanity.com/paper/1709.03768/) (2017)
- [Limits to scalable evaluation at the frontier: LLM as Judge won't beat twice the data](https://mlsanity.com/paper/2410.13341/) (2024)
- [What Prompts Don't Say: Understanding and Managing Underspecification in LLM Prompts](https://mlsanity.com/paper/2505.13360/) (2025)
- [Reliability without Validity: A Systematic, Large-Scale Evaluation of LLM-as-a-Judge Models Across Agreement, Consistency, and Bias](https://mlsanity.com/paper/2606.19544/) (2026)
- [Validating LLM-as-a-Judge Systems under Rating Indeterminacy](https://mlsanity.com/paper/2503.05965/) (2025)
- [Active Task Disambiguation with LLMs](https://mlsanity.com/paper/2502.04485/) (2025)
- [Diagnosing the Reliability of LLM-as-a-Judge via Item Response Theory](https://mlsanity.com/paper/2602.00521/) (2026)
- [Beyond Consensus: Perspectivist Modeling and Evaluation of Annotator Disagreement in NLP](https://mlsanity.com/paper/2601.09065/) (2026)
- [Language Models as a Service: Overview of a New Paradigm and its Challenges](https://mlsanity.com/paper/2309.16573/) (2023)
- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [Information-theoretic Distinctions Between Deception and Confusion](https://mlsanity.com/paper/2501.16448/) (2025)
- [Towards Provably Unbiased LLM Judges via Bias-Bounded Evaluation](https://mlsanity.com/paper/2603.05485/) (2026)

## Abstract (arXiv)

Large language models increasingly provide labels, evaluations, and feedback for tasks specified in natural language. When a specification admits multiple readings but the supervision channel does not reveal which is operative, additional labels reduce sampling error without resolving the resulting identification problem. We introduce Natural Language PAC (NL-PAC), a framework that uses a fixed model's thresholded decoding law to define admissible labels and candidate targets. The probability that multiple labels are admissible equals the diameter of the pointwise-admissible target class, and under target-blind supervision every learner incurs worst-case risk of at least half this diameter, at every sample size; the exact randomized minimax risk over this class is attained by a data-independent strategy. Finite-sample confidence bounds make these quantities certifiable from held-out unlabeled inputs. In a frozen Qwen~2.5--3B audit, one prespecified prompt yields a positive model-relative certificate, whereas a paraphrase and exact-rule controls yield zero. A held-out bridge audit finds that supplied candidate reading clauses fail the admissibility condition needed to transfer the certificate to coherent readings. The guarantee is specific to the audited model, prompt, threshold, and input distribution; extending it to human interpretations requires external validation.