Faith and Fate: Limits of Transformers on Compositionality
Authors: name: Nouha Dziri, name: Ximing Lu, name: Melanie Sclar, name: Xiang Lorraine Li, name: Liwei Jian, name: Bill Yuchen Lin, name: Peter West, name: Chandra Bhagavatula, name: Ronan Le Bras, name: Jena D. Hwang, name: Soumya Sanyal, name: Sean Welleck, name: Xiang Ren, name: Allyson Ettinger, name: Zaid Harchaoui, name: Yejin Choi

Transformer large language models (LLMs) have sparked admiration for their
exceptional performance on tasks that demand intricate multi-step reasoning.
Yet, these models simultaneously show failures on surprisingly trivial
problems. This begs the question: Are these errors incidental, or do they
signal more substantial limitations? In an attempt to demystify Transformers,
we investigate the limits of these models across three representative
compositional tasks -- multi-digit multiplication, logic grid puzzles, and a
classic dynamic programming problem. These tasks require breaking problems down
into sub-steps and synthesizing these steps into a precise answer. We formulate
compositional tasks as computation graphs to systematically quantify the level
of complexity, and break down reasoning steps into intermediate sub-procedures.
Our empirical findings suggest that Transformers solve compositional tasks by
reducing multi-step compositional reasoning into linearized subgraph matching,
without necessarily developing systematic problem-solving skills. To round off
our empirical study, we provide theoretical arguments on abstract multi-step
reasoning problems that highlight how Transformers' performance will rapidly
decay with increased task complexity.