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

Jul 16, 2026

Upload by Rowan

Large language models increasingly generate labels, evaluations, and feedback from natural-language task specifications, where one prompt may admit multiple readings. When the supervision channel is target-blind and does not reveal which reading is operative, extra labels reduce sampling error but cannot resolve the identification ambiguity. NL-PAC defines admissible labels via a fixed model’s thresholded decoding rule, quantifies the irreducible risk floor, and provides finite-sample certifiable confidence bounds from held-out unlabeled inputs. Model- and prompt-specific audits demonstrate where certificates transfer or fail under paraphrases and admissibility conditions.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages45

Reading Time1 h 53 min

Introduction

Contributions

Representation

Blind-channel value

Coherent readings

arXiv :2607 .0896 1v 1 [ cs .LG] 9 Jul 2026 NL-PAC: Specification Ambiguity and Certified Minimax Risk Floors in LLM-Mediated Supervision Berkay Anahtarci Department of Mathematical Engineering, Özyeğin University, Istanbul, Türkiye [berkay.anahtarci@ozyegin.edu.tr](berkay.anahtarci@ozyegin.edu.tr) 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 pointwiseadmissible 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. 1 Introduction Modern learning pipelines increasingly use large-language-model (LLM) judgments in place of human evaluation or labeling, including in LLM-as-a-judge systems (Liu et al. , 2023b; Kim et al. , 2024 ; Guet al. , 2026) . Prompts and scoring rubrics specify these tasks in natural language and may admit multiple interpretations. The supervising model can adopt one interpretation without revealing which one governs its judgments. We call the supervision channel target-blind when its observation law does not reveal which reading is operative. This regime is common in practice: judge models are typically served through proprietary APIs whose internals are opaque to the analyst (La Malfa et al. , 2024), so the operative reading is unobservable by construction. Target blindness refers to this hidden reading; whether the model’s decoding probabilities are exposed is a separate matter that later governs the audit’s access mode. The resulting error is interpretive rather than statistical: additional observations from the same unresolved channel do not identify the operative reading, although a more informative channel can. We ask how much minimax risk remains when the channel defining the admissible targets is also the learner’s only source of supervision, and whether that risk floor can be certified from unlabeled inputs. We formalize the setting as Natural Language PAC (NL-PAC), characterize when such a channel creates an irreducible risk floor, and turn that floor into a finite-sample certificate. Classical statistical learning theory does not model this coupling between task specification and the supervision channel: in the Probably Approximately Correct (PAC) framework of Valiant (1984), the analyst fixes the instance space, distribution, target, and hypothesis class, and the learner pays only the statistical price of estimating a target inside that specification. This is the separation underlying VC theory and computational learning theory generally (Kearns and Vazirani, 1994) . Language-model systems collapse this separation: the task is given as a natural-language instruction, and the supervision signal is produced by a model interpreting that same instruction (Liu et al. , 2023a) . NL-PAC makes this specification–channel pair the o

FAQs

What does target-blind supervision mean in the NL-PAC setting?

Target-blind supervision means the supervising model’s observation does not reveal which interpretation of a natural-language specification is operative.

How does NL-PAC define admissible labels and candidate targets?

NL-PAC uses a fixed model’s thresholded decoding law to define, for each input, a set of admissible labels and the induced candidate target class.

Can the minimax risk floor be certified from unlabeled inputs?

Yes. Finite-sample confidence bounds allow the relevant ambiguity-induced quantities to be certifiable from held-out unlabeled deployment inputs, under the audit’s observable sets and access mode.

Jul 16, 2026

Upload by Rowan