PhD Thesis Defense: Emma Graham

ZOOM LINK

"On Computations of Sequences"

Abstract

Many problems and observations of the world can be represented as sequences. Sequence modeling bears on how we solve problems and represent information, and on how small, ordered components give rise to properties that none of them has alone. Deep sequence models now write fluent text and predict protein structures, and are increasingly integrated into consequential settings. Yet apparent competence does not by itself establish what a model can compute. 

Two questions guide this dissertation: Does a model have the computational ability for your task? Under what conditions do its computations remain reliable? Drawing on the theory of computation, it studies computations of sequences from five directions: sequences generated by grammars of known computational classes, benchmarks of pretrained language models on those sequences, the design of a new deep sequence model, an analysis of its computations, and its implementation on a sequence task.

Asked a simple question, is this sentence grammatical?, frontier AI models disagree with people and with one another. On generated sentences whose dependencies exceed those of any known natural-language rule, human participants and nearly all conventional large language models answered no. Models with added inference-time computation effort answered yes far more often, and more so as that effort increased.

These evaluations motivate a new model architecture, the Lattice-Induction State-Space Sequence Model (LiSSM), which combines continuous state with learned logical relations. LiSSM can simulate a universal counter machine, which makes it Turing-complete under exact-arithmetic, unbounded-state, and unbounded-time assumptions. A separate result proves that any prescribed finite execution of this simulation keeps its decoded symbolic states under perturbation, provided accumulated error stays within an explicit margin. Built into a Logical Recurrent Network block, LiSSM matched or exceeded Mamba and transformer baselines on an initial selective-copying task.

Together, these results build toward a fundamental understanding of sequence models, one that accounts for what a model does, what its architecture can represent, and which of its computations are reliable. The more these models are trusted in high-stakes settings, the more we need to know their abilities and limits, and the assumptions under which they hold.

Thesis Committee

• Richard Granger (chair)
• George Cybenko
• Bryce Ferguson
• Brooks Paige (University College London)

Contact

For more information, contact Thayer Registrar at thayer.registrar@dartmouth.edu .