Foundations of Large Language Models: Abilities and Limitations through a Formal Language Learning Perspective

Foundations of Large Language Models

Abilities and Limitations of Large Language Models: A Formal Language Learning Perspective

Seminar Inspired by Michael Hahn's prior course: theory-25

The rise of large language models (LLMs) has drawn researchers from theory and empirical machine learning into a shared inquiry: what are the abilities and limitations of these models? A common thread across both perspectives is the use of formal languages to study LLMs, theoretically, to ask which languages or tasks are learnable, and empirically, to test whether these predictions hold in practice and to probe other phenomena of LLMs beyond learnability. The seminar is a chance to engage with LLMs from both angles, useful whether your interests lean toward formal methods or applied machine learning.

Our pursuit of understanding LLMs is divided into three axes:

No assumption about the computational model. What do classical results say about the learnability of a language, agnostic to any computational model?
A simplified model of the transformer. What is the computational model of a transformer? Can we study this model to understand the expressiveness and learnability of transformers?
LLMs in practice. Can we explain the phenomena of LLMs, e.g., different modes of learning, the world model implicit in the LLM, and the interplay between memorization and learning?

In each axis, controlled formal languages help us derive precise claims about the abilities and limitations of LLMs, something that is otherwise difficult with natural language.

Artifact

(LLM)

Environment

(Formal language)

"An ant, viewed as a behaving system, is quite simple. The apparent complexity of its behavior over time is largely a reflection of the complexity of the environment in which it finds itself." – Herbert Simon in The Sciences of the Artificial, 1996

Logistics

Instructors: Bishwamittra Ghosh, Krishna P. Gummadi.
Location: Max Planck Institute for Software Systems, Kaiserslautern, Room 207.
Schedule: Weekly, Thursday, 2–4 pm.
Intended audience: PhD and Master's students in computer science.
Format: Weekly seminar sessions in which students present and discuss the papers listed below.
Prerequisites: No specific coursework is required, but a basic understanding of formal languages and large language models (LLMs) is expected.
Paper selection: Select your papers here, by 23 October, 11:59 pm.
Slides: Introductory meeting.

Grading

Presentation (40%). A 45–60 minute presentation of the assigned paper, followed by Q&A. Motivate the question and state it formally, go deep on one proof or experiment and explain why you find it important, and explain your takeaways from the paper.
Report (40%). A report on the presented paper, to be submitted before the next class. Maximum 2 pages. It should discuss at least one aspect of the paper that an AI reviewer, the presenter, or the original authors have missed, and introduce insights to motivate future research. The best three reports will count toward the grade.
Class participation (20%). Read the paper before the session and ask questions during the Q&A, the more difficult, the better.

Students pass the seminar with a combined score of at least 50% across all three components.

Syllabus (tentative)

Date	Topic	Reading	Presenter
	Generation in the Limit	Kleinberg, Jon, and Sendhil Mullainathan. “Language Generation in the Limit.” In Proc. NeurIPS 2024, pp. 66058–66079.
	Model of a Transformer	Weiss, Gail, Yoav Goldberg, and Eran Yahav. “Thinking Like Transformers.” In Proc. ICML 2021.
	Predicting Length Generalization	Zhou, Hattie, et al. “What Algorithms Can Transformers Learn? A Study in Length Generalization.” In Proc. ICLR 2024.
	Recovering the Learned Program	Friedman, Dan, Alexander Wettig, and Danqi Chen. “Learning Transformer Programs.” In Proc. NeurIPS 2023.
	Difficulty of Learning	Liu, Bingbin, et al. “Exposing Attention Glitches with Flip-Flop Language Modeling.” In Proc. NeurIPS 2023.
	Implicit World Models	Vafa, Keyon, et al. “Evaluating the World Model Implicit in a Generative Model.” In Proc. NeurIPS 2024.
	Learning Modes	Ghosh, Bishwamittra, et al. “Fine-Tuning vs. In-Context Learning in Large Language Models: A Formal Language Learning Perspective.” In Proc. ACL 2026.
	Memorization & Learning	Ghosh, Bishwamittra, et al. “Understanding the Interplay between Memorization and Learning in Large Language Models.” In Proc. NeurIPS 2026.

Axis 1: No assumption about the computational model

Gold, E. Mark. “Language Identification in the Limit.” Information and Control, 1967.
Kalavasis, Alkis, Anay Mehrotra, and Grigoris Velegkas. “On the Limits of Language Generation: Trade-Offs between Hallucination and Mode Collapse.” In Proc. STOC 2025.
Charikar, Moses, and Chirag Pabbaraju. “Exploring Facets of Language Generation in the Limit.” 2024.

Axis 2: A simplified model of the transformer

Hahn, Michael. “Theoretical Limitations of Self-Attention in Neural Sequence Models.” TACL, 2020.
Liu, Bingbin, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. “Transformers Learn Shortcuts to Automata.” In Proc. ICLR 2023.
Lindner, David, et al. “Tracr: Compiled Transformers as a Laboratory for Interpretability.” In Proc. NeurIPS 2023.
Strobl, Lena, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. “What Formal Languages Can Transformers Express? A Survey.” TACL, 2024.
Hahn, Michael, and Mark Rofin. “Why Are Sensitive Functions Hard for Transformers?” In Proc. ACL 2024.
Merrill, William, and Ashish Sabharwal. “The Expressive Power of Transformers with Chain of Thought.” In Proc. ICLR 2024.
Merrill, William, Jackson Petty, and Ashish Sabharwal. “The Illusion of State in State-Space Models.” In Proc. ICML 2024.
Jerad, Selim, Anej Svete, Sophie Hao, Ryan Cotterell, and William Merrill. “Context-Free Recognition with Transformers.” 2026.

Axis 3: LLMs in practice

Bhattamishra, Satwik, Kabir Ahuja, and Navin Goyal. “On the Ability and Limitations of Transformers to Recognize Formal Languages.” In Proc. EMNLP 2020.
White, Jennifer C., and Ryan Cotterell. “Examining the Inductive Bias of Neural Language Models with Artificial Languages.” In Proc. ACL 2021.
Delétang, Grégoire, et al. “Neural Networks and the Chomsky Hierarchy.” In Proc. ICLR 2023.
Allen-Zhu, Zeyuan, and Yuanzhi Li. “Physics of Language Models: Part 1, Learning Hierarchical Language Structures.” 2023.
Ruoss, Anian, et al. “Randomized Positional Encodings Boost Length Generalization of Transformers.” In Proc. ACL 2023.
Borenstein, Nadav, et al. “What Languages Are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages.” In Proc. ACL 2024.
Kallini, Julie, Isabel Papadimitriou, Richard Futrell, Kyle Mahowald, and Christopher Potts. “Mission: Impossible Language Models.” In Proc. ACL 2024.