Combining Theoretical and Empirical Approaches for Understanding the Foundations of LLMs

The rise of large language models (LLMs) has drawn researchers from formal language theory, computational complexity, and empirical machine learning into a shared inquiry: how can we better understand the learnability and expressiveness of the LLMs? This seminar brings together theoretical and empirical perspectives on that question.

LLM Artifact

(Encoder-only, decoder-only, or both;
Soft/hard attention, position encoding;
Reasoning ability or agentic tool calling)

Environment

(natural language, formal language)

Our goal is to study LLMs within their operating environments, focusing on their expressiveness and learnability. Expressiveness concerns what problems (or languages, more broadly) can be represented or computed by an LLM; learnability concerns whether these languages can indeed be trained on by the LLM via standard training procedures. Our pursuit of understanding LLMs is divided into three important axes:

• LLMs in practice. Analyze the current state of LLMs as used in practice.
• Constrained architecture. Simplify the model by constraining its architecture — for example, restricting attention to hard attention or bounding computational precision.
• No computational model. Set aside architectural assumptions altogether and study the model with no specific computational model in mind.

In each axis, we control the environment of the LLMs by considering controlled formal languages, enabling us to make precise claims about the artifact itself.

Tentative syllabus

This reading list is still tentative — suggestions for additional or alternative papers are welcome.