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
Published: 2023-05-29 23:24:14

Abstract: 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.