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

• URL: http://arxiv.org/abs/2607.08961v1
• Date: Thu, 09 Jul 2026 21:53:00 GMT
• Title: NL-PAC: Specification Ambiguity and Certified Minimax Risk Floors in LLM-Mediated Supervision
• Abstract summary: We introduce Natural Language PAC, a framework that uses a fixed model's thresholded decoding law to define admissible labels and candidate targets.<n>In a frozen Qwen2.5--3B audit, one prespecified prompt yields a positive model-relative certificate, whereas a paraphrase and exact-rule controls yield zero.
• Score: 0.9475982252982437
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• A distribution-free certification framework for trustworthy crash-severity prediction [1.089614199781423]
  We develop a certification layer that wraps any severity model unmodified.<n>On 5.2 million Texas records across seven base models spanning four decades, the layer attaches identical validity.<n>The framework is released as an open-source package with theorem-level tests.
  arXiv  Detail & Related papers  (2026-09-10T14:20:08Z)
• Finite-Sample Coverage Audits for High-Recall Candidate Generation: Certification and Learning-Theoretic Design [0.0]
  We study how many audit labels are needed to certify, with finite-sample validity, that this missed relevant mass is small.<n>We first show that no procedure using only labels from inside the candidate set can certify any non-trivial bound on the missed mass.<n>We develop an exact finite-sample toolkit, using binomial and hypergeometric inversion rather than approximation, that certifies missed mass.
  arXiv  Detail & Related papers  (2026-07-23T16:21:30Z)
• Verifier-Bound Communication for LLM Agents: Certified Bounds on Covert Signaling [0.0]
  Colluding language-model agents can hide coordination in messages that remain policy-compliant at the surface level.<n>We present CLBC, a protocol where generation and admission are separated.<n>We show how this protocol yields an upper bound on transcript leakage in terms of latent leakage plus explicit residual channels.
  arXiv  Detail & Related papers  (2026-02-27T23:42:37Z)
• Conditional Coverage Diagnostics for Conformal Prediction [47.93989136542648]
  We show that conditional coverage estimation can be a classification problem.<n>We call the resulting family of metrics excess risk of the target coverage (ERT)<n>We release an open-source package for ERT as well as previous conditional coverage metrics.
  arXiv  Detail & Related papers  (2025-12-12T18:47:39Z)
• LEC: Linear Expectation Constraints for False-Discovery Control in Selective Prediction and Routing Systems [95.35293543918762]
  Large language models (LLMs) often generate unreliable answers, while uncertainty methods fail to fully distinguish correct from incorrect predictions.<n>We address this issue through the lens of false discovery rate (FDR) control, ensuring that among all accepted predictions, the proportion of errors does not exceed a target risk level.<n>We propose LEC, which reinterprets selective prediction as a constrained decision problem by enforcing a Linear Expectation Constraint.
  arXiv  Detail & Related papers  (2025-12-01T11:27:09Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• COPU: Conformal Prediction for Uncertainty Quantification in Natural Language Generation [14.461333001997449]
  Uncertainty Quantification (UQ) for Natural Language Generation (NLG) is crucial for assessing the performance of Large Language Models (LLMs)<n>We propose ourmethod, a method that explicitly adds the ground truth to the candidate outputs and uses logit scores to measure nonconformity.
  arXiv  Detail & Related papers  (2025-02-18T07:25:12Z)
• Conformal Language Modeling [61.94417935386489]
  We propose a novel approach to conformal prediction for generative language models (LMs) Standard conformal prediction produces prediction sets with rigorous, statistical guarantees. We demonstrate the promise of our approach on multiple tasks in open-domain question answering, text summarization, and radiology report generation.
  arXiv  Detail & Related papers  (2023-06-16T21:55:08Z)
• Ambiguity-Resistant Semi-Supervised Learning for Dense Object Detection [98.66771688028426]
  We propose a Ambiguity-Resistant Semi-supervised Learning (ARSL) for one-stage detectors. Joint-Confidence Estimation (JCE) is proposed to quantifies the classification and localization quality of pseudo labels. ARSL effectively mitigates the ambiguities and achieves state-of-the-art SSOD performance on MS COCO and PASCAL VOC.
  arXiv  Detail & Related papers  (2023-03-27T07:46:58Z)
• Dist-PU: Positive-Unlabeled Learning from a Label Distribution Perspective [89.5370481649529]
  We propose a label distribution perspective for PU learning in this paper. Motivated by this, we propose to pursue the label distribution consistency between predicted and ground-truth label distributions. Experiments on three benchmark datasets validate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2022-12-06T07:38:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.