LLMs break classical learning theory
CMU's Tom Mitchell argues LLMs break classical PAC learning across three paradigms Simons Institute for the Theory of ComputingTL;DW
- LLMs enable explanation-based learning: systems generate natural-language justifications for labeled examples, distill them into interpretable rubrics, and improve classification without parameter tuning.
- Feature engineering problem reframed: LLMs can autonomously suggest relevant predictors given only a target variable description (e.g., "predict flu hospitalizations"), eliminating manual feature selection.
- Machine learning agents with self-reflection: systems generate their own learning subtasks by logging computations, analyzing failures via LLM-as-oracle, and iteratively debugging code to handle edge cases.
- PAC learning framework requires extension: target functions now have natural-language definitions; hypothesis classes consist of learned rubrics plus LLM interpretation; sample complexity must account for representation ambiguity.
- Conventional wisdom overturned: parameter tuning is no longer the dominant learning mechanism; big data plus statistics is insufficient; semantic knowledge representations with informal natural language now viable.
- Explanation-based learning from 1980s-90s deserves revival: prior work on learning from explanations (e.g., single-example chess tactics) failed due to inability to generate explanations; LLMs now enable this paradigm.
- Self-training and semi-supervised learning provide better theoretical framings than PAC learning for LLM-based systems: implicit inductive bias assumes LLM explanations are task-relevant, requiring ground truth data to focus learning.
- Data ground truth critically focuses LLM reasoning: flipping all training labels produces plausible but incorrect justifications; ground truth prevents models from exploiting multiple plausible explanations.
- Agents write and debug code autonomously: systems generate Python functions to interface with web APIs, merge datasets from heterogeneous sources, and maintain memory through persistent file storage.
- Theory should model natural language representation and approximate reasoning: key open questions concern formalizing informality in natural-language descriptions, agents with pervasive self-reflection, and endogenous learning task generation.
TL;DW
- LLMs enable explanation-based learning: systems generate natural-language justifications for labeled examples, distill them into interpretable rubrics, and improve classification without parameter tuning.
- Feature engineering problem reframed: LLMs can autonomously suggest relevant predictors given only a target variable description (e.g., "predict flu hospitalizations"), eliminating manual feature selection.
- Machine learning agents with self-reflection: systems generate their own learning subtasks by logging computations, analyzing failures via LLM-as-oracle, and iteratively debugging code to handle edge cases.
- PAC learning framework requires extension: target functions now have natural-language definitions; hypothesis classes consist of learned rubrics plus LLM interpretation; sample complexity must account for representation ambiguity.
- Conventional wisdom overturned: parameter tuning is no longer the dominant learning mechanism; big data plus statistics is insufficient; semantic knowledge representations with informal natural language now viable.
- Explanation-based learning from 1980s-90s deserves revival: prior work on learning from explanations (e.g., single-example chess tactics) failed due to inability to generate explanations; LLMs now enable this paradigm.
- Self-training and semi-supervised learning provide better theoretical framings than PAC learning for LLM-based systems: implicit inductive bias assumes LLM explanations are task-relevant, requiring ground truth data to focus learning.
- Data ground truth critically focuses LLM reasoning: flipping all training labels produces plausible but incorrect justifications; ground truth prevents models from exploiting multiple plausible explanations.
- Agents write and debug code autonomously: systems generate Python functions to interface with web APIs, merge datasets from heterogeneous sources, and maintain memory through persistent file storage.
- Theory should model natural language representation and approximate reasoning: key open questions concern formalizing informality in natural-language descriptions, agents with pervasive self-reflection, and endogenous learning task generation.
Mitchell presents explanation-based learning, LLM-driven feature discovery, and autonomous self-reflecting agents as three paradigms that invalidate fixed hypothesis classes and parameter tuning. He frames the shift as analogous to compilers over assembly: LLM improvements still matter, but a new research layer opens above them.