title: Faith and Fate: Limits of Transformers on Compositionality
summary: 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.
paper_authors._id: 6476c556a0bde42d3f94a9a5
paper_authors.name: Nouha Dziri
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2023-10-19T15:47:44.830Z
paper_authors._id: 625888c2c964680d85d70bff
paper_authors.avatarUrl: /avatars/2ba91e452c5ea577ec9f1f71abc2fa49.svg
paper_authors.fullname: Nouha Dziri
paper_authors.type: user
paper_authors.user: nouhadziri
paper_authors._id: 6476c556a0bde42d3f94a9a6
paper_authors.name: Ximing Lu
paper_authors._id: 6476c556a0bde42d3f94a9a7
paper_authors.name: Melanie Sclar
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2023-05-31T12:01:18.561Z
paper_authors._id: 6274d1dba2d1b8d4982e36a8
paper_authors.avatarUrl: /avatars/933654c7b0946a8609aa38cfee364604.svg
paper_authors.fullname: Melanie Sclar
paper_authors.type: user
paper_authors.user: msclar
paper_authors._id: 6476c556a0bde42d3f94a9a8
paper_authors.name: Xiang Lorraine Li
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2023-11-16T15:51:01.366Z
paper_authors._id: 651dd123a4747c77c11bb960
paper_authors.avatarUrl: /avatars/c7d921d80db1d2f2c1179c576fdb50be.svg
paper_authors.fullname: Xiang Lorraine Li
paper_authors.type: user
paper_authors.user: lorraine921
paper_authors._id: 6476c556a0bde42d3f94a9a9
paper_authors.name: Liwei Jian
paper_authors._id: 6476c556a0bde42d3f94a9aa
paper_authors.name: Bill Yuchen Lin
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2023-05-31T07:54:43.319Z
paper_authors._id: 607f666a4ad99100d63ce35c
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/607f666a4ad99100d63ce35c/QxhxnvfeV6efkxwUFHwjI.png
paper_authors.fullname: Bill Yuchen Lin
paper_authors.type: user
paper_authors.user: yuchenlin
paper_authors._id: 6476c556a0bde42d3f94a9ab
paper_authors.name: Peter West
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2023-06-02T07:16:32.801Z
paper_authors._id: 6359e982548e5c7e6e6b2154
paper_authors.avatarUrl: /avatars/0cda044c09ca95254e001eebd00aebe8.svg
paper_authors.fullname: Peter West
paper_authors.type: user
paper_authors.user: peterwestuw
paper_authors._id: 6476c556a0bde42d3f94a9ac
paper_authors.name: Chandra Bhagavatula
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2023-05-31T07:25:08.684Z
paper_authors._id: 615c8ad1ce94868478737e42
paper_authors.avatarUrl: /avatars/5c1c694deabeac0d0e3836c74bbffdf5.svg
paper_authors.fullname: Chandra B
paper_authors.type: user
paper_authors.user: chandrab
paper_authors._id: 6476c556a0bde42d3f94a9ad
paper_authors.name: Ronan Le Bras
paper_authors._id: 6476c556a0bde42d3f94a9ae
paper_authors.name: Jena D. Hwang
paper_authors._id: 6476c556a0bde42d3f94a9af
paper_authors.name: Soumya Sanyal
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-02-07T11:17:42.892Z
paper_authors._id: 64a72adf3987f4dd3c40d0a6
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/64a72adf3987f4dd3c40d0a6/VPNPN_TRjhJikt4NJPTxq.jpeg
paper_authors.fullname: Soumya Sanyal
paper_authors.type: user
paper_authors.user: soumyasanyal
paper_authors._id: 6476c556a0bde42d3f94a9b0
paper_authors.name: Sean Welleck
paper_authors._id: 6476c556a0bde42d3f94a9b1
paper_authors.name: Xiang Ren
paper_authors._id: 6476c556a0bde42d3f94a9b2
paper_authors.name: Allyson Ettinger
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-10-31T09:55:55.358Z
paper_authors._id: 6500b18c9d5687f825518282
paper_authors.avatarUrl: /avatars/2abc8340eae436253b8b835eb8cfa505.svg
paper_authors.fullname: Allyson Ettinger
paper_authors.type: user
paper_authors.user: aettinger
paper_authors._id: 6476c556a0bde42d3f94a9b3
paper_authors.name: Zaid Harchaoui
paper_authors._id: 6476c556a0bde42d3f94a9b4
paper_authors.name: Yejin Choi
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2023-08-10T08:39:36.011Z
paper_authors._id: 64d42729f63b01b7f676b176
paper_authors.avatarUrl: /avatars/52e54bdd6a1fb6c774a40cd70f3d7925.svg
paper_authors.fullname: Yejin Choi
paper_authors.type: user
paper_authors.user: yejinchoinka
paper_title: Faith and Fate: Limits of Transformers on Compositionality
paper_summary: 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.
paper_ai_keywords: Transformer large language models (LLMs) multi-step reasoning compositional tasks multi-digit multiplication logic grid puzzles dynamic programming problem computation graphs stepped reasoning sub-procedures linearized subgraph matching systematic problem-solving skills abstract multi-step reasoning problems