NL-PAC Framework Quantifies LLM Supervision Ambiguity and Risk.

This paper introduces Natural Language PAC (NL-PAC), a framework designed to analyze and quantify the inherent ambiguity when Large Language Models (LLMs) are used for tasks specified in natural language. The core issue arises when a natural language prompt can be interpreted in multiple ways, and the LLM's output doesn't clarify which interpretation is being followed. This ambiguity means that simply adding more labels won't resolve the underlying identification problem, leading to a fundamental limit on how well a model can perform. NL-PAC defines admissible labels and candidate targets based on a fixed model's decoding behavior. It establishes that the probability of multiple labels being admissible directly relates to the "diameter" of the possible target interpretations. Crucially, the framework proves that any learning system, regardless of its complexity, will incur a worst-case risk at least half of this diameter, even with infinite data. The research also provides methods to certify these risk floors using unlabeled data, demonstrating its practical application through an audit of a Qwen~2.5--3B model.