9 papers
Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers
Gilad Yehudai, Clayton Sanford, Maya Bechler-Speicher +3
Transformers have revolutionized the field of machine learning. In particular, they can be used to solve complex algorithmic problems, including graph-based tasks. In such algorith…
Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers
Maya Bechler-Speicher, Gilad Yehudai, Gil Harari +3
Transformers have become a central architecture for graph learning, but their application to graphs requires first choosing a tokenization: a graph-to-token map that determines whi…
Geometric Factual Recall in Transformers
Shauli Ravfogel, Gilad Yehudai, Joan Bruna +1
How do transformer language models memorize factual associations? A common view casts internal weight matrices as associative memories over pairs of embeddings, requiring parameter…
When Can Transformers Count to n?
Gilad Yehudai, Haim Kaplan, Guy Dar +4
Large language models based on the transformer architecture can solve highly complex tasks, yet their fundamental limitations on simple algorithmic problems remain poorly understoo…
Compositional Reasoning with Transformers, RNNs, and Chain of Thought
Gilad Yehudai, Noah Amsel, Joan Bruna
It is well understood that different neural network architectures are suited to different tasks, but is there always a single best architecture for a given task? We compare the exp…
Emergence of Linear Truth Encodings in Language Models
Shauli Ravfogel, Gilad Yehudai, Tal Linzen +2
Recent probing studies reveal that large language models exhibit linear subspaces that separate true from false statements, yet the mechanism behind their emergence is unclear. We…