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.
Class: Weekly, Thursday, 2–3:30 pm, Room 112, Max Planck Institute for Software Systems, Kaiserslautern.
Office hours: Weekly, Friday, 2–3:30 pm, Room 112.
Email: fllm26instructors@mpi-sws.org.
Report submission: Moodle.
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:
- Required: No strict course prerequisites, but students must demonstrate mathematical maturity and a strong willingness to engage with technical, proof-based computer science content (formal language theory, computational complexity, linear algebra, and basic probability).
- Recommended: Prior knowledge of theoretical computer science (automata theory, circuit complexity) and deep learning architecture fundamentals.

Grading

Presentation (40%). A 45–60 minute presentation of the assigned paper, followed by Q&A. Motivate the research problem, go deeper into at least one topic, and teach what you have learned from the paper. Where two students present the same paper, one takes the role of champion and the other of critic.
Report (40%). Due by 2 pm on the day the paper is presented. We provide an LLM-generated review; write what you like about it and what it misses.
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

Date	Topic	Reading	Presenter	Material
22 October 2026	Short intro and Q&A	—	—	Slides
29 October 2026	No class	—	—
5 November 2026	Generation in the Limit	Kleinberg, Jon, and Sendhil Mullainathan. “Language Generation in the Limit.” In Proc. NeurIPS 2024, pp. 66058–66079.	Muhammad Umer, Baris Akdogan*	LLM review
12 November 2026	Model of a Transformer	Weiss, Gail, Yoav Goldberg, and Eran Yahav. “Thinking Like Transformers.” In Proc. ICML 2021.	Sanika Patil, Golbahar AbbasiHormozi, Hasib Aslam
19 November 2026	Predicting Length Generalization	Zhou, Hattie, et al. “What Algorithms Can Transformers Learn? A Study in Length Generalization.” In Proc. ICLR 2024.	Adnan Mohammed (433512), Disha Tarun Patil, Faizkhan Pathan
26 November 2026	Recovering the Learned Program	Friedman, Dan, Alexander Wettig, and Danqi Chen. “Learning Transformer Programs.” In Proc. NeurIPS 2023.	Ramin Shahbazi*
3 December 2026	Difficulty of Learning	Liu, Bingbin, et al. “Exposing Attention Glitches with Flip-Flop Language Modeling.” In Proc. NeurIPS 2023.	Rushikesh Santosh Kulkarni, Shrushti Sachin Sabale
14 January 2027	Implicit World Models	Vafa, Keyon, et al. “Evaluating the World Model Implicit in a Generative Model.” In Proc. NeurIPS 2024.	Parth Salat, Maham Sami
21 January 2027	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.	Adnan (434470)
28 January 2027	Memorization & Learning	Ghosh, Bishwamittra, et al. “Understanding the Interplay between Memorization and Learning in Large Language Models.” In Proc. NeurIPS 2026.	Dhiraj Udhani, Ishita Nag

* Student is not enrolled.

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.