Is PAC-unlearnability a fundamental limitation for LLM reasoning?

Question

For simplicity, let’s focus on knowledge reasoning tasks with Yes/No answers. According to learning theory, even moderately complex knowledge reasoning tasks are PAC-unlearnable. This implies that no learning-based reasoning engine trained on a finite sample set can achieve an accuracy strictly greater than 50%. In contrast, a trivial algorithm that determines answers by flipping a coin would also achieve 50% accuracy.

Therefore, I am puzzled as to why there are so many LLM reasoning models nowadays, attempting to achieve high-quality knowledge reasoning by chasing benchmark scores. According to the aforementioned theory, such models do not seem to offer a fundamental advantage over the trivial coin-flipping algorithm.

Some people might argue that the theory of PAC-learnability requires reasoning tasks to be stably learnable under any distribution, while in real-world scenarios, the probability distribution of knowledge reasoning problems is specific. Therefore, the PAC-unlearnability limitations may not apply to LLM reasoning models.

However, it is evident that we do not actually know this specific distribution in real-world knowledge reasoning. In particular, since human needs are constantly evolving, it remains uncertain whether such a specific probability distribution even exists. Moreover, according to existing research, learning probability distributions itself is also unlearnable.

Is there a misunderstanding in my reasoning? What is your perspective on this issue?

Answer 1

Since the classical PAC framework was originally designed for supervised learning from i.i.d. samples and a fixed concept class following a fixed unknown distribution with a hypothesis class of bounded complexity, indeed LLMs' self-supervised pre-training with a hypothesis class of seemingly unbounded complexity don’t neatly fall under the PAC framework. In practice, however, the vast structured pre-training data sufficiently allow LLMs to extract meaningful patterns and perform auto-regression tasks well above your 50% baseline empirically. One main explanation is that the attention mechanism aligned with human language generation acts as a strong inductive bias to significantly reduce the complexity of the hypothesis class, so that the PAC-framework could still be applied approximately or at least consistent with LLMs' empirically verified good accuracy and calibration metrics.

Similarly for LLMs' reasoning tasks, based on the above pre-trained foundation models, techniques like chain-of-thought reasoning to help these models break down complex reasoning processes into more manageable steps are not captured by supervised classifier learning but are fine-tuned by reinforcement learning with sequential non-i.i.d. samples where PAC framework doesn't apply either. In practice benchmarks are designed around specific knowledge expert or reasoning tasks that often have different exploitable structure.