Seminar Upcoming

Transformers, the architecture behind today’s large language models, can be viewed as a model of parallel computation. The input is a sequence of tokens, each represented by a vector. In every layer, each token gathers information from all other tokens and then updates its own vector. Two parameters determine the size of the model: the depth, which is the number of layers, and the width, which is the dimension of the vectors and so the amount of information each token can hold. A natural question is how large these parameters must be for a transformer to solve a given algorithmic problem. Graph problems such as connectivity, cycle detection and subgraph counting are a good test case. They have clean answers and span a wide range of difficulty, and lower bound techniques from distributed computing and complexity theory can be applied to them. Earlier work showed a close connection between transformers and the Massively Parallel Computation (MPC) model. As a result, many graph problems can be solved with logarithmic depth when the width is sublinear in the number of nodes.

In the first part of the talk, I will show what changes when the width is allowed to grow linearly in the number of nodes. In this regime, a constant number of layers suffices for many problems, including connectivity and cycle detection. Other problems provably require more, from superlinear to nearly quadratic width. The lower bounds come from communication complexity and from conjectured hardness in MPC. Experiments show that wide and shallow models match the accuracy of deep ones and run considerably faster.

In the second part, I will turn to a question that does not arise for text: how a graph should be encoded as a sequence of tokens. We study three natural encodings, based on adjacency rows, the eigenvectors of the Laplacian, and random walk statistics. We show that the same problem can be easy under one encoding and hard, or even impossible, under another. Moreover, a transformer of bounded depth cannot in general convert one encoding into another. The proofs use tools from circuit complexity, communication complexity and spectral graph theory.

Short bio: Gilad Yehudai is a faculty member at the Technion, with a joint appointment in Computer Science and Electrical Engineering. Previously, he was a postdoc at NYU working with Joan Bruna and did his PhD at the Weizmann Institute with Ohad Shamir. His research is in the theory of machine learning, in particular the expressive power of transformers, its connections to computational complexity, and learning theory.