NL-PAC: Specification Ambiguity and Certified Minimax Risk Floors in LLM-Mediated Supervision
2026-07-09 • Machine Learning
Machine LearningArtificial Intelligence
AI summaryⓘ
The authors study how large language models label or evaluate tasks described in natural language when the instructions can be understood in multiple valid ways. They propose a framework called NL-PAC that defines which labels are acceptable based on a model’s behavior and shows that if the actual intended meaning is unknown, there is a fundamental limit to how accurately any learner can perform. They test this method on a specific model and prompt, showing some cases where their approach can provide guarantees and others where it cannot. Their results focus on the specific model and conditions tested, and applying it to human understanding would need further checks.
Large Language ModelsNatural Language SupervisionNL-PAC FrameworkAdmissible LabelsIdentification ProblemRandomized Minimax RiskThresholded DecodingModel AuditingFinite-Sample ConfidenceTarget-Blind Supervision
Authors
Berkay Anahtarci
Abstract
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.