The DOI matches its Crossref record; 82 of the 82 references it cites were found in a registry or an index; none of the 41 sources its claims cite is checked for support yet.
Faith and Fate: Limits of Transformers on Compositionality
Open accessAbstract
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 transformer LLMs, 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 transformer LLMs 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 autoregressive generations' performance can rapidly decay with\,increased\,task\,complexity.
Overview
AI snapshot
Written from the paper’s full text.
TL;DR
Transformer LLMs can achieve near-perfect in-domain accuracy on compositional tasks but fail sharply out-of-domain, often relying on linearized subgraph matching rather than systematic multi-step reasoning. The paper argues empirically and theoretically that error propagation makes autoregressive transformers increasingly unlikely to solve compositionally complex tasks as problem size grows.
Key findings
- Off-the-shelf ChatGPT and GPT4 achieve only 55% and 59% accuracy on 3-digit by 3-digit multiplication, and zero-/few-shot performance declines to near zero as problem size or graph parallelism increases.
- Fine-tuning GPT3 on task-specific question-answer or question-scratchpad data gives near-perfect in-domain performance but fails to generalize to out-of-domain deeper or wider computation graphs; grokking was not observed for multiplication after 420K question-answer steps or 30K scratchpad steps.
- Models appear to reduce multi-step reasoning to linearized subgraph matching: full computation subgraphs appear more frequently in training for correctly predicted test examples, and 82.3% of final correct answers for 4-digit by 2-digit multiplications had at least one error in the computation graph.
- Error analysis shows fully correct nodes decrease sharply with graph layer, propagation errors usually exceed local errors, and DP/puzzle tasks show high restoration errors; theoretical propositions show incorrect-prediction probability can converge exponentially to ≈1 as problem size increases under stated assumptions.
Methods
- The paper formulates compositional tasks as computation graphs and measures complexity via reasoning depth, reasoning width, average parallelism, and relative information gain.
- It studies three tasks—long-form multi-digit multiplication up to 5×5 digits, Einstein logic grid puzzles, and a dynamic-programming relaxation of maximum weighted independent set—evaluating GPT3, ChatGPT, GPT4, FlanT5, and LLaMA with zero-shot, few-shot, question-answer fine-tuning, and question-scratchpad fine-tuning; each task uses 500 test examples.
- It complements experiments with theoretical analysis of error accumulation for independent and iterated applications of estimated functions.
Limitations
- The paper states that scratchpad analysis can only establish correlation between model generation and preceding context because the authors lack access to model activations, and that alternative linearizations of reasoning may yield different performance.
- The paper also states that compute budget constraints and limited access to the largest language models prevented pushing empirical limits further.
- Evident from the text: fine-tuning is mainly on GPT3, grokking is tested only on multiplication, puzzle training uses a subset due to combinatorial explosion, and the theoretical results rely on assumptions such as independent errors, low collision, and c ≪ ϵ that may not hold generally.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
65 Own interpretation · 45 Own result · 17 Sources not found · 8 No basis given · 4 Own method
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Similarly, the prediction of the last digit (or two digits) of the output is observed to solely rely on the last digit (or two digits) of each input number.”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.2.1 Information Gain Explains Where Transformers Partially Excel
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“This observation holds for all tasks (See details in § B.4).”
§ Faith and Fate: Limits of Transformers on Compositionality > Limits of transformers with question-answer training
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“In all settings, the ratio of fully correct nodes is almost perfect but sharply decreases toward zero with increasing graph layers.”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.2.3 What Types of Errors do Transformers Make at Different Reasoning Depths?
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Moreover, the ratio of propagation errors is usually higher than the ratio of local errors.”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.2.3 What Types of Errors do Transformers Make at Different Reasoning Depths?
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“However, the performance sharply declines when evaluating unseen splits during training, i.e., out-of-domain (OOD).”
§ Faith and Fate: Limits of Transformers on Compositionality > Limits of transformers with question-answer training
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“82.3% of the final correct answers for 4-digit by 2-digit multiplications (a setting unseen during training) had at least one error in the computation graph, but still produced correct answers.”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.2.3 What Types of Errors do Transformers Make at Different Reasoning Depths?
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“However, this performance boost diminishes to zero as complexity increases.”
§ Faith and Fate: Limits of Transformers on Compositionality > Limits of transformers with question-answer training
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“For multiplication, relative information gain shows that the first digit (two digits) of the output highly correlates with the first digit (two digits) of each input number (see §C.1).”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.2.1 Information Gain Explains Where Transformers Partially Excel
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Similarly, prompting transformers with question-scratchpad pairs enhances the performance compared to the zero-shot setting (refer to § B.5).”
§ Faith and Fate: Limits of Transformers on Compositionality > Limits of transformers with question-answer training
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The trend remains the same for few-shot prompting (see §B.2).”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.1 Testing the Limits of Transformers with Zero-shot, Few-shot and Finetuning
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- It may state two separate claims as one. 29
- The quote only partly states this claim. 4
- Probably not a substantial claim. 25
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The results, presented in Figure 5b, show that once again GPT3 achieves near-perfect performance on in-distribution, but fails entirely in generalizing to OOD cases-in particular, wider or deeper computation graphs.”
§ Faith and Fate: Limits of Transformers on Compositionality > Limits of transformers with question-answer training
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Figure 6 shows that full computation subgraphs appear significantly more frequently in the training data for correctly predicted test examples than for incorrectly predicted ones”
§ Faith and Fate: Limits of Transformers on Compositionality > Given a model-generated computation graph G A(x)
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one. The quote only partly states this claim.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Both the DP and the puzzle tasks have a high ratio of restoration errors, suggesting memorization since correct outputs are produced despite incorrect computations.”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.2.3 What Types of Errors do Transformers Make at Different Reasoning Depths?
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Yet, off-the-shelf ChatGPT and GPT4 achieve only 55% and 59% accuracies on this task, respectively ( §3).”
§ Faith and Fate: Limits of Transformers on Compositionality > 1 Introduction
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Empirically, we verify that models indeed learn the patterns we predicted and other patterns as well (e.g., order of magnitude of the answer, number of trailing zeros for multiplication) in all the settings with and without scratchpad.”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.2.1 Information Gain Explains Where Transformers Partially Excel
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Empirical results show that training on task-specific data leads to near-perfect performance on indomain instances and under low compositional complexity, but fails drastically on instances outside of this region.”
§ Faith and Fate: Limits of Transformers on Compositionality > 1 Introduction
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Rests on an assumption: The three compositional tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“task performances deteriorate significantly from near perfection to zero with increasing complexity”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.1 Testing the Limits of Transformers with Zero-shot, Few-shot and Finetuning
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
The quote only partly states this claim.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Among these variations, the scratchpad version depicted in Figure 9 ultimately produced the most favorable outcomes.”
§ Faith and Fate: Limits of Transformers on Compositionality > A Compositional Tasks
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“since GPT3 often predicts shorter output sequences than the required size”
§ Faith and Fate: Limits of Transformers on Compositionality > C.4 Empirical Surface Pattern Results for Dynamic Programming Task
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper may give no reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The results indicate a lack of generalization for out-of-domain (OOD) examples while showcasing near-perfect performance for in-domain examples.”
§ Faith and Fate: Limits of Transformers on Compositionality > B.3 Limits of Transformers with question-answer Training
hedged- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“On all tasks, we can see that the model fails to generalize to OOD data while achieving perfect accuracy on in-domain data”
§ Faith and Fate: Limits of Transformers on Compositionality > B.3 Limits of Transformers with question-answer Training
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one. The quote only partly states this claim.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“We perform fine-tuning on GPT3 (text-davinci-003) for the three tasks, observing faster convergence when training on question-scratchpad pairs rather than question-answer pairs.”
§ Faith and Fate: Limits of Transformers on Compositionality > B.1 Models
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Moreover, o i is highly predicted by both (a i-2 , a i-1 , a i ) and (a i , a i+1 , a i+2 )”
§ Faith and Fate: Limits of Transformers on Compositionality > C.1 Relative Information Gain Predictions for Multiplication
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“The same applies for the rest of the models.”
§ Faith and Fate: Limits of Transformers on Compositionality > B.5 Limits of Transformers with Explicit Scratchpad Prompting
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“Generally, we observe that larger batch sizes tend to yield better results for larger datasets.”
§ Faith and Fate: Limits of Transformers on Compositionality > B.1 Models
hedgedcorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. The paper may give no reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“In contrast to other tasks, the value of m is not fixed, and depends on the task instance, but using solvers we know that m increases with problem size.”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. It may state two separate claims as one.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“As shown in Table 3, a i is a good predictor of o i , and this is especially true for a 1 and a n-1 , the first and last elements of the sequence.”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Prop. 4.1's proof ( §D.1) shows the rate of convergence is exponential, thus concluding that transformers will rapidly fail with increasing n.”
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
boosteddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“This implies that P(f n ̸ = f n ) decreases exponentially as n increases, with lim inf n→+∞ P(f n ̸ = f n ) ≥ 1 -c.”
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: In Proposition 4.1, h_n is a perfect estimator of h_n.
- The authors state this as an assumption: In Proposition 4.1, h_n has low collision, with c_n being an upper bound of h_n's collision rate (c_n < c for all n, with c << 1).
- The authors state this as an assumption: In Proposition 4.1, g's errors are independent.
In the paper
“Shortcut learning [29] via pattern-matching may yield fast correct answers when similar compositional patterns are available during training but does not allow for robust generalization to uncommon or complex examples.”
§ Faith and Fate: Limits of Transformers on Compositionality > 1 Introduction
What the sources say
- Not matchedcites [29]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
hedgedconditional- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. It may state two separate claims as one.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“All tasks analyzed empirically in this paper are instantiations of these abstractions ( §4).”
§ Faith and Fate: Limits of Transformers on Compositionality > 1 Introduction
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim.
- Rests on an assumption: Human problem-solving skills can be represented as a graph structure where vertices are partial solutions and edges are operators that modify those solutions.
- Rests on an assumption: Reasoning depth in a computation graph is a proxy for the maximum level of multi-hop reasoning required to solve the task.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“This type of learning could be largely effective when the compositional complexity of tasks is low but it becomes less efficient when tasks are increasingly complex.”
§ Faith and Fate: Limits of Transformers on Compositionality > Correct Final Answer Incorrect Final Answer
hedgeddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“If P(g ̸ = g) = ϵ > 0, then P(f n ̸ = f n ) decreases exponentially with n. Precisely, P(f n ̸ = f n ) ≥ 1 -(1 -ϵ -c) n-1 (1 -ϵ -c/(c + ϵ)), implying lim inf n→+∞ P(f n ̸ = f n ) ≥ 1 -c/(c + ϵ).”
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: In Proposition 4.2, the probability of recovering from a mistake due to the randomness of applying the estimator on an incorrect input is at most c.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Both phenomena suggest that models are able to correctly perform single-step reasoning, potentially due to memorizing such single-step operations during training, but fail to plan and compose several of these steps for an overall correct reasoning.”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.2.3 What Types of Errors do Transformers Make at Different Reasoning Depths?
hedgedconditional- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“Applying step-by-step reasoning is fundamental to human intelligence [69,68].”
§ Faith and Fate: Limits of Transformers on Compositionality > 1 Introduction
What the sources say
- Not matchedcites [69]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [68]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: fails — It may be too vague to check against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. It may be too vague to check against evidence. The paper’s conclusions may not depend on it.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Both the DP and the puzzle tasks have a high ratio of restoration errors, suggesting memorization since correct outputs are produced despite incorrect computations.”
§ Faith and Fate: Limits of Transformers on Compositionality > 3.2.3 What Types of Errors do Transformers Make at Different Reasoning Depths?
hedgeddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Note that Prop 4.1 and 4.2 apply to any high-performant estimator of reasoning tasks.”
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper may give no reason why it holds. It may state two separate claims as one.
- Rests on an assumption: The tasks evaluated are low collision settings.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Our insights indicate that the current configuration of transformers, with their reliance on a greedy process for predicting the next word, constrains their error recovery capability and impedes the development of a comprehensive global understanding of the task.”
§ Faith and Fate: Limits of Transformers on Compositionality > Theoretical Findings and their Empirical Implications
hedgeddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- The authors state this as an assumption: The theoretical proofs' assumptions hold for the abstract compositional tasks and autoregressive language models considered.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“All tasks evaluated in the present work can be seen as instances of the results just proven.”
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim.
- Rests on an assumption: The tasks evaluated are low collision settings.
What the paper did — it cites no source for this, so there is none to check. The quote shows it is in the paper.
In the paper
“However, because GPT3 often does not produce the correct output size, it hinders us from analyzing o n-1 .”
§ Faith and Fate: Limits of Transformers on Compositionality > C.4 Empirical Surface Pattern Results for Dynamic Programming Task
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. It may state two separate claims as one.
What the paper did — it cites no source for this, so there is none to check. The quote shows it is in the paper.
In the paper
“This limitation arises from our lack of access to the activations of the studied models.”
§ Faith and Fate: Limits of Transformers on Compositionality > 8 Limitations
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim.
In the paper
“Liu et al., [45] found that shallow transformers learn shortcuts during training, leading to poor OOD generalization.”
§ Faith and Fate: Limits of Transformers on Compositionality > Challenges of transformers in generalization
What the sources say
- Not matchedcites [45]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. It may state two separate claims as one.
- Not matched
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“However, these models have also been shown to struggle across multiple domains [32], including algorithmic reasoning [78], commonsense reasoning [62,40], theory of mind [65], planning [76], logical reasoning [70], and ethical reasoning [36].”
§ Faith and Fate: Limits of Transformers on Compositionality > 6 Related Work
What the sources say
- Not matchedcites [32]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [78]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [62]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [40]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Not matched
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“Recently, transformers [11,58,57,17,16,63,73,74] have demonstrated impressive reasoning abilities across a wide range of tasks, even outperforming humans in certain cases [79,28,15,85].”
§ Faith and Fate: Limits of Transformers on Compositionality > 6 Related Work
What the sources say
- Not matchedcites [11]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [58]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [57]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [17]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [16]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [63]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [73]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [74]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [79]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [28]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
boosted- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. It may state two separate claims as one.
- Not matched
In the paper
“Importantly, Hahn [30] shows that transformers cannot robustly model noncounter-free regular languages even when allowing infinite precision.”
§ Faith and Fate: Limits of Transformers on Compositionality > Grokking
What the sources say
- Not matchedcites [30]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
boosted- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim.
- Not matched
What the paper did — it cites no source for this, so there is none to check. The quote shows it is in the paper.
In the paper
“However, we acknowledge that due to our compute budget constraints as well as limited access to the largest language models such as GPT4, we are unable to push the empirical limits of transformers even further in terms of training data size and number of epochs.”
§ Faith and Fate: Limits of Transformers on Compositionality > Theoretical Findings and their Empirical Implications
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Should we choose to fine-tune GPT3 for 4 epochs on question-answer pairs, the cost would amount to $12 million and $700 million for question-scratchpad training.”
§ Faith and Fate: Limits of Transformers on Compositionality > B.3 Limits of Transformers with question-answer Training
hedgeddirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
In the paper
“Prop.4.2 directly applies to the recursive function of the dynamic programming task, as well as to m-by-1 digit multiplication, and to the puzzle through its elimination function (details in D.3).”
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
What the sources say
- Not matchedcites D.3
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Rests on an assumption: The tasks evaluated are low collision settings.
- Not matched
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“Transformers perform fairly well in singlestep reasoning tasks [70], but face challenges when it comes to effectively combining multiple steps to solve compositionally complex problems [84,55,66,81].”
§ Faith and Fate: Limits of Transformers on Compositionality > Challenges of transformers in compositional tasks
What the sources say
- Not matchedcites [70]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [84]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [55]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [66]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [81]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Solving the puzzle task may be seen as f m for some m, where f is the elimination function”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
hedgedconditional- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“When f is an affine transformation, the process falls simultaneously between two perspectives: time series [31] and dynamic programming and control [6].”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
What the sources say
- Not matchedcites [31]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites [6]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
- Not matched
In the paper
“In this latter literature, the focus is usually on the contractive regime in which accrued errors can be kept under control, and the subsequent convergence guarantees (e.g., [23]).”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
What the sources say
- Not matchedcites [23]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Assume P(h n = h n ) = 1 and P(h n (X) = h n (Y ) | X ̸ = Y ) < c n , lim n→+∞ P(f n ̸ = f n ) = 1.”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
The quote only partly states this claim.
- The authors state this as an assumption: In Proposition D.1, P(h_n = h_n)=1.
- The authors state this as an assumption: In Proposition D.1, P(h_n(X)=h_n(Y) | X≠Y) < c_n.
- The authors state this as an assumption: In Proposition D.1, c_n ≤ β α^n for some α∈(0,1) and β>0.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“In the DP task, the reconstruction of the desired subsequence given already computed dp values may be viewed as f m (x) for an input list of size m.”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
hedgedcorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“In the DP task, dp's computation may be viewed as f m-2 (x) for a list of size m”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
hedged- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“where c n < c for some constant c ≪ 1 (i.e.h n perfectly estimates h n , and h n is almost injective).If P(g ̸ = g) = ϵ > 0 and errors in g are independent, lim inf n→+∞ P(f n ̸ = f n ) ≥ 1c.”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: fails — The paper may give no reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it. The paper may give no reason why it holds. It may state two separate claims as one.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Corollary D.3.The recursions for dynamic programming tasks, the m-by-1 digit multiplication, and the puzzle's elimination function are all tasks where there is a fixed reasoning step g being repeatedly applied.”
§ Faith and Fate: Limits of Transformers on Compositionality > C.4 Empirical Surface Pattern Results for Dynamic Programming Task
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
It may state two separate claims as one.
In the paper
“The process of repeatedly applying a noisy single operation or function f can be related to iterated random functions [24].”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
What the sources say
- Not matchedcites [24]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plaincorrelational- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
- Not matched
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Therefore, large m's (or alternatively, c ≪ ϵ) imply m m+1 will be close to 1.”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
plaindirect- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: fails — The paper’s conclusions may not depend on it.
- Based: passes — The paper gives a reason why it holds.
Probably not a substantial claim. The paper’s conclusions may not depend on it.
The paper relies on this without support.
The three compositional tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.
“These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.”
The paper relies on this without support.
Human problem-solving skills can be represented as a graph structure where vertices are partial solutions and edges are operators that modify those solutions.
“Human problem-solving skills can be conceptualized as a graph structure, where each vertex represents a partial solution and the edges represent operators that can be applied to modify these solutions.”
The paper relies on this without support.
Reasoning depth in a computation graph is a proxy for the maximum level of multi-hop reasoning required to solve the task.
“In computation graphs, reasoning depth is a proxy for the maximum level of multi-hop reasoning required to solve the task.”
The paper relies on this without support.
The three studied tasks are representative compositional tasks.
“we study three straightforward and flexible representative compositional tasks: long-form multiplication, logic grid puzzles (i.e., Einstein's puzzle [61]), and a classic dynamic programming problem.”
The paper relies on this without support.
As K and M increase, synthesizing different partial solutions that satisfy individual constraints becomes highly compositionally complex.
“As K and M increase, synthesizing different partial solutions that satisfy individual constraints becomes highly compositionally complex.”
The paper relies on this without support.
Algorithms designed to solve compositional tasks typically involve multiple independent applications of a function and/or iterated applications of the same function.
“Algorithms designed to solve compositional tasks typically involve multiple independent applications of a function and/or iterated applications of the same function.”
The paper relies on this without support.
A transformer executing such an algorithm acts as an estimator of these functions.
“A transformer executing such an algorithm acts as an estimator of these functions.”
The authors state this as an assumption.
In Proposition 4.1, h_n is a perfect estimator of h_n.
“Assume that h n is a perfect estimator of h n and that h n has low collision, with c n being an upper bound of h n 's collision rate (c n < c ∀n, with c ≪ 1).”
The authors state this as an assumption.
In Proposition 4.1, h_n has low collision, with c_n being an upper bound of h_n's collision rate (c_n < c for all n, with c << 1).
“Assume that h n is a perfect estimator of h n and that h n has low collision, with c n being an upper bound of h n 's collision rate (c n < c ∀n, with c ≪ 1).”
The authors state this as an assumption.
In Proposition 4.1, g's errors are independent.
“If P(g ̸ = g) = ϵ > 0 where g's errors are independent”
The authors state this as an assumption.
In Proposition 4.2, the probability of recovering from a mistake due to the randomness of applying the estimator on an incorrect input is at most c.
“Assume that the probability of recovering from a mistake due to the randomness of applying the estimator on an incorrect input has probability at most c.”
The authors state this as an assumption.
In Proposition 4.2's current form, there is a single valid reasoning for each input since g is a function.
“In Prop.4.2's current form, we implicitly assume that there is a single valid reasoning for each input since g is a function.”
The authors state this as an assumption.
When g has low collision, c << epsilon.
“It is reasonable to assume c ≪ ϵ when g has low collision, since c represents the probability of the estimator g(y) arriving at the correct output g(x) by chance when given the wrong input y ̸ = x.”
The paper relies on this without support.
The tasks evaluated are low collision settings.
“They are also all low collision settings.”
The authors state this as an assumption.
The theoretical proofs' assumptions hold for the abstract compositional tasks and autoregressive language models considered.
“The proofs presented in §4 show that, under reasonable assumptions, the probability of incorrect predictions converges exponentially to ≈ 1 for abstract compositional tasks.”
The authors state this as an assumption.
In Proposition D.1, P(h_n = h_n)=1.
“Assume P(h n = h n ) = 1”
The authors state this as an assumption.
In Proposition D.1, P(h_n(X)=h_n(Y) | X≠Y) < c_n.
“P(h n (X) = h n (Y ) | X ̸ = Y ) < c n”
The authors state this as an assumption.
In Proposition D.1, c_n ≤ β α^n for some α∈(0,1) and β>0.
“if c n ≤ βα n for some some α ∈ (0, 1) and β > 0”
The authors state this as an assumption.
In Lemma D.2, P(z(g(X))=1 | z(X)=0) ≤ c.
“Assume P(z( g(X)) = 1 | z(X) = 0) ≤ c”
The authors state this as an assumption.
In Lemma D.2, P(z(g(X))=0 | z(X)=1) = ε > 0 with c+ε<1.
“P(z( g(X)) = 0 | z(X) = 1) = ϵ > 0 with c + ϵ < 1”
The authors state this as an assumption.
In Proposition D.2, P(g(X)=g(Y) | X≠Y) ≤ c.
“Assume P(g(X) = g(Y ) | X ̸ = Y ) ≤ c”
The authors state this as an assumption.
In Proposition D.2, P(g≠g)=ε>0 with c+ε<1.
“If P(g ̸ = g) = ϵ > 0 with c + ϵ < 1”
The authors state this as an assumption.
The mathematical framework used is a simplified representation of how multi-step reasoning works.
“The mathematical framework used is a simplified representation of how multi-step reasoning works”
The authors state this as an assumption.
c ≪ ϵ when g has low collision.
“It is reasonable to assume c ≪ ϵ when g has low collision, since c represents the probability of the estimator g(y) arriving at the correct output g(x) by chance when given the wrong input y ̸ = x.”
The authors state this as an assumption.
Assuming approximately uniform errors, c ≈ ϵ/|Im(g)|, which implies c ≪ ϵ when g has low collision.
“Assuming approximately uniform errors, c ≈ ϵ/|Im(g)|, which in turn implies c ≪ ϵ since g being low collision implies |Im(g)| is large.”
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“This may be due to the increased complexity of the task (Dziri et al., 2023) where the ranking of N generations may become much more difficult as N gets larger (since the task complexity increases).”
From Benchmarking Cognitive Biases in Large Language Models as Evaluators (2024) · cites this paper as Dziri et al., 2023
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Frontier reasoning-tuned language models still fail on deductive tasks at depth, and the cost of improved performance through extended internal reasoning scales poorly.”
From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [6]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“First, accuracy degrades on long deductive chains, even for strong reasoning-tuned models.”
From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [6]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“we agree with Dziri et al. (2023) that there is a fundamental”
From What Algorithms can Transformers Learn? A Study in Length Generalization (2023) · cites this paper as Dziri et al. (2023)
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Limitations in compositionality, entity binding, long-context evidence use, and numerical grounding are therefore especially relevant, but are rarely examined within one unified setting [11][12][13][14][15][16][17][18].”
From Diagnosing the limits of large language models for structured scientific evidence extraction (2026) · cites this paper as [11]
Experimental — accuracy not yet measured
The cited source says what the claim attributes to it.
In the citing paper
“Earlier analyses of compositional tasks [6] and template-based variants of standard mathematics benchmarks [7] attribute such failures to pattern matching over training-distribution structure rather than genuine multi-step deduction, with accuracy degrading as the number of required reasoning steps grows.”
From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [6]
The cited source says what the claim attributes to it.
In the citing paper
“Dziri et al. (2023) represent reasoning tasks as computation graphs and find that full computation subgraphs appear much more frequently in training data for correct predictions than incorrect ones.”
From GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models (2024) · cites this paper as Dziri et al. (2023)
The cited source says what the claim attributes to it.
In the citing paper
“the reasoning performance of GPT-4 negatively correlates with the depth of the problem's computation graph (Dziri et al., 2023).”
From The expressive power of transformers with chain of thought (2023) · cites this paper as Dziri et al., 2023
The cited source says what the claim attributes to it.
In the citing paper
“Studies on compositional generalization show that models often struggle to combine familiar components into systematically correct novel structures [11,47,48].”
From Diagnosing the limits of large language models for structured scientific evidence extraction (2026) · cites this paper as [11]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
“lim n→+∞ P(f n = f n ) = 1. Recall that P(f n = f n ) < αβ n + (1 -ϵ) n • (1 -αβ n ).”
§ Faith and Fate: Limits of Transformers on Compositionality > Additional information
“0 ≤ lim inf n→+∞ P(f n = f n ) ≤ lim sup n→+∞ P(f n = f n ) ≤ lim sup n→+∞ βα n + (1 -ϵ) n • (1 -βα n ) = 0”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
“This implies that P(f n ̸ = f n ) decreases exponentially as n increases, with lim inf n→+∞ P(f n ̸ = f n ) ≥ 1 -c.”
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
“Prop. 4.1's proof ( §D.1) shows the rate of convergence is exponential, thus concluding that transformers will rapidly fail with increasing n.”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Faith and Fate: Limits of Transformers on Compositionality > Limits of transformers with question-answer training
“We separately finetune GPT3 models on ∼1.8M multiplication pairs, ∼142K DP pairs, and ∼41K puzzle pairs”
§ Faith and Fate: Limits of Transformers on Compositionality > B.3 Limits of Transformers with question-answer Training
“As for the puzzle task, the model was fine-tuned on puzzles of sizes ranging from 2x2 to 4x4 resulting in a total of 142k pairs.Additionally, for the DP task, the model was fine-tuned on problems with a sequence length of 5 resulting in 41K pairs.”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
“If P(g ̸ = g) = ϵ > 0, then P(f n ̸ = f n ) decreases exponentially with n.”
§ Faith and Fate: Limits of Transformers on Compositionality > 4 Error Propagations: The Theoretical Limits
“Note that if c ≪ ϵ then lim inf n→+∞ P(f n ̸ = f n ) ≈ 1.”
Citations
Cites
Language Models are Few-Shot Learners
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020) · arXiv · doi:10.48550/arxiv.2005.14165 · Cited by 23,372 · cited 5×
“5-turbo) [40], GPT3 (text-davinci-003) [8], FlanT5 [? ] and LLaMa [57].”
BackgroundMethodInfluentialScaling Laws for Neural Language Models
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., & Amodei, D. (2020) · arXiv · doi:10.48550/arxiv.2001.08361 · Cited by 9,550
de Moura, L., & Bjørner, N. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_24 · Cited by 6,595 · cited 1×
“Graph Construction Algorithm To solve the complex compositional reasoning process for a logical grid puzzle, we use existing puzzle solvers [21] to generate the computation graph.”
MethodFeigelson, E. (2003) · Statistics for Environmental Science and Management · doi:10.1007/978-3-319-03762-2_13 · Cited by 6,344 · cited 2×
“When f is an affine transformation, the process falls simultaneously between two perspectives: time series [26] and dynamic programming and control [5].”
BackgroundLLaMA: Open and Efficient Foundation Language Models
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. (2023) · arXiv · doi:10.48550/arxiv.2302.13971 · Cited by 4,602 · cited 3×
“[57] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample.”
BackgroundChain-Of-Thought Prompting Elicits Reasoning in Large Language Models
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q. V., & Zhou, D. (2022) · Advances in Neural Information Processing Systems 35 · doi:10.52202/068431-1800 · Cited by 4,505 · cited 3×
“[61] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou.”
BackgroundMethodThe Architecture of Complexity
Simon, H. A. (1991) · Springer eBooks · doi:10.1007/978-1-4899-0718-9_31 · Cited by 4,479 · cited 1×
“Applying step-by-step reasoning is fundamental to human intelligence [51, 50].”
BackgroundPaLM: Scaling Language Modeling with Pathways
Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. (2022) · arXiv · doi:10.48550/arxiv.2204.02311 · Cited by 2,590 · cited 1×
“Reasoning abilities in transformer LLMs Recently, transformers [11, 58, 57, 17, 16, 63, 73, 74] have demonstrated impressive reasoning abilities across a wide range of tasks, even outperforming humans in certain cases [79, 28, 15, 85].”
BackgroundSelf-Refine: Iterative Refinement with Self-Feedback
Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S., Yang, Y., et al. (2023) · arXiv · doi:10.48550/arxiv.2303.17651 · Cited by 2,314 · cited 2×
“[36] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark.”
BackgroundMethodSelf-citationShortcut learning in deep neural networks
Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Brendel, W., Bethge, M., & Wichmann, F. A. (2020) · Nature Machine Intelligence · doi:10.1038/s42256-020-00257-z · Cited by 2,224 · cited 2×
“[25] Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann.”
BackgroundSparks of Artificial General Intelligence: Early experiments with GPT-4
Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lundberg, S., et al. (2023) · arXiv · doi:10.48550/arxiv.2303.12712 · Cited by 1,526 · cited 3×
“” – Charles Dickens, A Tale of Two Cities Large-scale Transformers such as ChatGPT [40] and GPT-4 [41] demonstrate unprecedented capabilities [40, 56, 8, 11, 65], even noted as “sparks of AGI” [9].”
BackgroundScaling Instruction-Finetuned Language Models
Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, Y., Wang, X., Dehghani, M., Brahma, S., et al. (2022) · arXiv · doi:10.48550/arxiv.2210.11416 · Cited by 1,441 · cited 2×
“[13] Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Y.”
BackgroundEmergent Abilities of Large Language Models
Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., et al. (2022) · arXiv · doi:10.48550/arxiv.2206.07682 · Cited by 1,264 · cited 2×
“[60] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H.”
BackgroundTarjan, R. (1987) · CACM · doi:10.1145/214748.214752 · Cited by 895 · cited 1×
“We analyze a classic relaxation of the NP-complete Maximum Weighted Independent Set problem [39]: Given a sequence of integers, find a subsequence with the highest sum, such that no two numbers in the subsequence are adjacent in the original sequence .”
MethodIs ChatGPT a General-Purpose Natural Language Processing Task Solver?
Qin, C., Zhang, A., Zhang, Z., Chen, J., Yasunaga, M., & Yang, D. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.85 · Cited by 869
Is ChatGPT a General-Purpose Natural Language Processing Task Solver?
Qin, C., Zhang, A., Zhang, Z., Chen, J., Yasunaga, M., & Yang, D. (2023) · arXiv · doi:10.48550/arxiv.2302.06476 · Cited by 869
LaMDA: Language Models for Dialog Applications
Thoppilan, R., De Freitas, D., Hall, J., Shazeer, N., Kulshreshtha, A., Cheng, H.-T., Jin, A., Bos, T., Baker, L., Du, Y., et al. (2022) · arXiv · doi:10.48550/arxiv.2201.08239 · Cited by 778 · cited 3×
“” – Charles Dickens, A Tale of Two Cities Large-scale Transformers such as ChatGPT [40] and GPT-4 [41] demonstrate unprecedented capabilities [40, 56, 8, 11, 65], even noted as “sparks of AGI” [9].”
BackgroundHYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION PROBLEM
Prosser, P. (1993) · International Conference on Climate Informatics · doi:10.1111/j.1467-8640.1993.tb00310.x · Cited by 721 · cited 2×
“Einstein’s Puzzle Einstein’s puzzle is a well-known logic puzzle often used as a benchmark for solving constraint satisfaction problems [43].”
BackgroundDehaene, S., Molko, N., Cohen, L., & Wilson, A. J. (2004) · Current Opinion in Neurobiology · doi:10.1016/j.conb.2004.03.008 · Cited by 673 · cited 2×
“For instance, humans can solve 3-digit by 3-digit multiplication arithmetic after learning basic calculation rules [18, 28].”
Human problem solving: The state of the theory in 1970.
Simon, H. A., & Newell, A. (1971) · American Psychologist · doi:10.1037/h0030806 · Cited by 635 · cited 1×
“Applying step-by-step reasoning is fundamental to human intelligence [51, 50].”
BackgroundGalactica: A Large Language Model for Science
Taylor, R., Kardas, M., Cucurull, G., Scialom, T., Hartshorn, A., Saravia, E., Poulton, A., Kerkez, V., & Stojnic, R. (2022) · arXiv · doi:10.48550/arxiv.2211.09085 · Cited by 605 · cited 2×
“[55] Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic.”
BackgroundBeyond the Imitation Game: Quantifying and extrapolating the capabilities of language models
Srivastava, A., Rastogi, A., Rao, A., Shoeb, A. A. M., Abid, A., Fisch, A., Brown, A. R., Santoro, A., Gupta, A., Garriga-Alonso, A., et al. (2022) · arXiv · doi:10.48550/arxiv.2206.04615 · Cited by 569 · cited 3×
“[52] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R.”
BackgroundSelf-citationChatGPT Goes to Law SchoolPreprint
Choi, J. H., Hickman, K. E., Monahan, A., & Schwarcz, D. B. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4335905 · Cited by 565 · cited 3×
“” – Charles Dickens, A Tale of Two Cities Large-scale Transformers such as ChatGPT [40] and GPT-4 [41] demonstrate unprecedented capabilities [40, 56, 8, 11, 65], even noted as “sparks of AGI” [9].”
BackgroundDiaconis, P. W., & Freedman, D. A. (1999) · SIAM Review · doi:10.1137/s0036144598338446 · Cited by 502 · cited 2×
“Iterated Functions The process of repeatedly applying a noisy single operation or function f can be related to iterated random functions [20].”
BackgroundHuman Reasoning and Cognitive Science
Stenning, K., & van Lambalgen, M. (2008) · The MIT Press eBooks · doi:10.7551/mitpress/7964.001.0001 · Cited by 443 · cited 2×
“This contrasts with the systematic multi-step reasoning approach that learns to apply underlying computational rules required for building correct answers [53, 31, 23].”
BackgroundMissing Links@@@Conceptual and Procedural Knowledge: The Case of Mathematics
Sowder, L., & Hiebert, J. (1987) · doi:10.2307/749249 · Cited by 428 · cited 2×
“For instance, humans can solve 3-digit by 3-digit multiplication arithmetic after learning basic calculation rules [18, 28].”
Selection-Inference: Exploiting Large Language Models for Interpretable Logical ReasoningPreprint
Creswell, A., Shanahan, M., & Higgins, I. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2205.09712 · Cited by 338 · cited 2×
“Lastly, leveraging LLMs to generate each reasoning step iteratively via a selection and inference mechanism [16, 15, 54].”
BackgroundMethodProgram Induction by Rationale Generation: Learning to Solve and Explain Algebraic Word Problems
Ling, W., Yogatama, D., Dyer, C., & Blunsom, P. (2017) · Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/p17-1015 · Cited by 325 · cited 3×
“[35] Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom.”
BackgroundMethodScaling Language Models: Methods, Analysis & Insights from Training Gopher
Rae, J. W., Borgeaud, S., Cai, T., Millican, K., Hoffmann, J., Song, F., Aslanides, J., Henderson, S., Ring, R., Young, S., et al. (2021) · arXiv · doi:10.48550/arxiv.2112.11446 · Cited by 235 · cited 1×
“Reasoning abilities in Transformers Recently, Transformers [8, 41, 40, 13, 12, 45, 55, 56] have demonstrated impressive reasoning abilities across a wide range of tasks, even outperforming humans in certain cases [60, 24, 11, 65].”
BackgroundSelf-citationLogic, probability, and human reasoning
Johnson-Laird, P. N., Khemlani, S., & Goodwin, G. P. (2015) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2015.02.006 · Cited by 233 · cited 2×
“This contrasts with the systematic multi-step reasoning approach that learns to apply underlying computational rules required for building correct answers [53, 31, 23].”
BackgroundDiverse Demonstrations Improve In-context Compositional GeneralizationPreprint
Levy, I., Bogin, B., & Berant, J. (2022) · Annual Meeting of the Association for Computational Linguistics · doi:10.48550/arxiv.2212.06800 · Cited by 211 · cited 1×
“Lastly, choosing a training split that maximizes the number of observed patterns between the train and test data [10], or diversifying in-prompt examples to cover the maximum of patterns [41], ultimately enhancing generalization.”
BackgroundTransformers Learn Shortcuts to AutomataPreprint
Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., & Zhang, C. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.10749 · Cited by 180 · cited 1×
“Challenges of transformers in generalization Extensive research has been done to investigate the generalization capabilities of transformers [3, 54, 26, 64, 8, 46].”
BackgroundTransformers as Soft Reasoners over Language
Clark, P., Tafjord, O., & Richardson, K. (2020) · Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2020/537 · Cited by 176 · cited 2×
“[14] Peter Clark, Oyvind Tafjord, and Kyle Richardson.”
BackgroundTheoretical Limitations of Self-Attention in Neural Sequence Models
Hahn, M. (2020) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00306 · Cited by 165 · cited 2×
“We observe that all analyzed models match the Relative Information Gain prediction that o 1 (whether the first element goes into the output sequence or not) should be the easiest value to predict (see Figures 30, 31, and 32).”
BackgroundMethodTrain Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation
Press, O., Smith, N. A., & Lewis, M. (2021) · arXiv · doi:10.48550/arxiv.2108.12409 · Cited by 161 · cited 2×
“This encompasses various facets of generalization, including easy-to-hard generalization [49, 3], length generalization [42, 10, 37], and generalization on symbolic mathematical integration [64].”
BackgroundCan You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent NetworksPreprint
Schwarzschild, A., Borgnia, E., Gupta, A., Huang, F., Vishkin, U., Goldblum, M., & Goldstein, T. (2021) · Neural Information Processing Systems · doi:10.48550/arxiv.2106.04537 · Cited by 151 · cited 4×
“for A(x) x = [7,49] function multiply (x[1.”
BackgroundInfluentialScaling Laws for Autoregressive Generative Modeling
Henighan, T., Kaplan, J., Katz, M., Chen, M., Hesse, C., Jackson, J., Jun, H., Brown, T. B., Dhariwal, P., Gray, S., et al. (2020) · arXiv · doi:10.48550/arxiv.2010.14701 · Cited by 150 · cited 2×
“[27] Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B.”
BackgroundShow Your Work: Scratchpads for Intermediate Computation with Language Models
Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., et al. (2021) · arXiv · doi:10.48550/arxiv.2112.00114 · Cited by 144 · cited 5×
“[38] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena.”
BackgroundMethodInfluentialExplaining grokking through circuit efficiencyPreprint
Varma, V., Shah, R., Kenton, Z., Kramár, J., & Kumar, R. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2309.02390 · Cited by 137 · cited 1×
“Recently, [77] propose that grokking occurs when a task admits a generalizing and a memorizing solution, and the former is slower to learn.”
BackgroundBian, N., Han, X., Sun, L., Lin, H., Lu, Y., He, B., Jiang, S., & Dong, B. (2024) · Language Resources and Evaluation Conference (LREC) · doi:10.63317/32y85i5g9gso · Cited by 133 · cited 4×
“for A(x) x = [7,49] function multiply (x[1.”
BackgroundInfluentialProofWriter: Generating implications, proofs, and abductive statements over natural language
Tafjord, O., Dalvi, B., & Clark, P. (2021) · Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021 · doi:10.18653/v1/2021.findings-acl.317 · Cited by 122 · cited 2×
“Lastly, leveraging LLMs to generate each reasoning step iteratively via a selection and inference mechanism [16, 15, 54].”
BackgroundMethodTeaching Algorithmic Reasoning via In-context LearningPreprint
Zhou, H., Nova, A., Larochelle, H., Courville, A. C., Neyshabur, B., & Sedghi, H. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2211.09066 · Cited by 120 · cited 1×
“For example, Nye et al. [55] and Zhou et al. [86] used scratchpads to teach transformers how to perform algorithmic reasoning tasks such as addition by splitting the task into intermediate steps [44, 80].”
BackgroundNeural Theory-of-Mind? On the Limits of Social Intelligence in Large LMs
Sap, M., LeBras, R., Fried, D., & Choi, Y. (2022) · arXiv · doi:10.48550/arxiv.2210.13312 · Cited by 118 · cited 2×
“However, these models have also been shown to struggle across multiple domains, including algorithmic reasoning [59], commonsense reasoning [44, 34], theory of mind [47], planning [58], logical reasoning [52], and ethical reasoning [30].”
BackgroundSelf-citationNeural Theory-of-Mind? On the Limits of Social Intelligence in Large LMs
Sap, M., Le Bras, R., Fried, D., & Choi, Y. (2022) · Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/2022.emnlp-main.248 · Cited by 118
Self-citationNaturalProver: Grounded Mathematical Proof Generation with Language Models
Welleck, S., Liu, J., Lu, X., et al. (2022) · Neural Information Processing Systems · doi:10.48550/arxiv.2205.12910 · Cited by 109 · cited 2×
“Challenges of Transformers in compositional tasks Transformers perform fairly well in singlestep reasoning tasks [52], but face challenges when it comes to effectively combining multiple steps to solve compositionally complex problems [38, 48, 62].”
BackgroundSelf-citationChatGPT in Scientific Writing: A Cautionary Tale
Zheng, H., & Zhan, H. (2023) · The American Journal of Medicine · doi:10.1016/j.amjmed.2023.02.011 · Cited by 104 · cited 2×
“Reasoning abilities in Transformer LLMs Recently, Transformers [9, 42, 41, 14, 13, 46, 56, 57] have demonstrated impressive reasoning abilities across a wide range of tasks, even outperforming humans in certain cases [61, 25, 12, 66].”
BackgroundA Tale of Two Circuits: Grokking as Competition of Sparse and Dense Subnetworks
Merrill, W., Tsilivis, N., & Shukla, A. (2023) · arXiv.org · doi:10.48550/arxiv.2303.11873 · Cited by 97 · cited 1×
“…arises: [47] show that perfect generalization in an arithmetic addition task happens when there is sufficient data to determine the appropriate structured representation, later extended to sparse parity in [52] where a sparse subnetwork of neurons is shown responsible for generalization behavior.”
BackgroundUnveiling Transformers with LEGO: a synthetic reasoning taskPreprint
Zhang, Y., Bačkurs, A., Bubeck, S., Eldan, R., Gunasekar, S., & Wagner, T. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.04301 · Cited by 92 · cited 1×
“Transformers perform fairly well in single-step reasoning tasks [70], but face challenges when it comes to effectively combining multiple steps to solve compositionally complex problems [84, 55, 66, 81].”
BackgroundImpact of Pretraining Term Frequencies on Few-Shot Numerical Reasoning
Razeghi, Y., Logan IV, R. L., Gardner, M., & Singh, S. (2022) · Findings of the Association for Computational Linguistics: EMNLP 2022 · doi:10.18653/v1/2022.findings-emnlp.59 · Cited by 89 · cited 6×
“Collapsed Compositionality and Robustness Implications Transformers today demonstrate undeniably powerful empirical results.”
BackgroundInfluentialTowards Understanding Grokking: An Effective Theory of Representation Learning
Liu, Z., Kitouni, O., Nolte, N. S., Michaud, E. J., Tegmark, M., & Williams, M. (2022) · neural information processing systems · doi:10.52202/068431-2511 · Cited by 88
Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets
Power, A., Burda, Y., Edwards, H., Babuschkin, I., & Misra, V. (2022) · arXiv · doi:10.48550/arxiv.2201.02177 · Cited by 83 · cited 2×
“We explore whether extended training beyond overfitting leads to improved generalization abilities, a phenomenon known as grokking [59, 53].”
BackgroundGrokking of Hierarchical Structure in Vanilla Transformers
Murty, S., Sharma, P., Andreas, J., et al. (2023) · Annual Meeting of the Association for Computational Linguistics · doi:10.48550/arxiv.2305.18741 · Cited by 79 · cited 2×
“Following [53], we fine-tune GPT3 with question-answer pairs for 420K steps and separately finetune GPT3 with question-scratchpad pairs for 30K steps.”
BackgroundMethodValmeekam, K., Marquez, M., Olmo, A., Sreedharan, S., & Kambhampati, S. (2023) · Advances in Neural Information Processing Systems 36 · doi:10.52202/075280-1693 · Cited by 70 · cited 2×
“[58] Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati.”
BackgroundDiverse Demonstrations Improve In-context Compositional Generalization
Levy, I., Bogin, B., & Berant, J. (2023) · Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2023.acl-long.78 · Cited by 66
Draft, Sketch, and Prove: Guiding Formal Theorem Provers with Informal ProofsPreprint
Jiang, A. Q., Welleck, S., Zhou, J., Li, W., Liu, J., Jamnik, M., Lacroix, T., Wu, Y., & Lample, G. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.12283 · Cited by 65 · cited 1×
“[29] Albert Qiaochu Jiang, Sean Welleck, Jin Peng Zhou, Timothee Lacroix, Jiacheng Liu, Wenda Li, Mateja Jamnik, Guillaume Lample, and Yuhuai Wu.”
BackgroundSelf-citationLimitations of Autoregressive Models and Their Alternatives
Lin, C., Jaech, A., Li, X., Gormley, M. R., & Eisner, J. M. (2021) · Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT) · doi:10.18653/v1/2021.naacl-main.405 · Cited by 63 · cited 1×
“Transformers’ theoretical expressiveness Lin et al. [43] study autoregressive models’ limitations from a computational complexity theory perspective.”
BackgroundSelf-citationLanguage Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought
Saparov, A., & He, H. (2022) · arXiv · doi:10.48550/arxiv.2210.01240 · Cited by 46 · cited 1×
“Challenges of Transformers in compositional tasks Transformers perform fairly well in singlestep reasoning tasks [52], but face challenges when it comes to effectively combining multiple steps to solve compositionally complex problems [38, 48, 62].”
BackgroundExploring Length Generalization in Large Language Models
Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., & Neyshabur, B. (2022) · arXiv · doi:10.48550/arxiv.2207.04901 · Cited by 44 · cited 8×
“[2] Cem Anil, Yuhuai Wu, Anders Johan Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Venkatesh Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur.”
BackgroundInfluentialGenerating Sequences by Learning to Self-Correct
Welleck, S., Lu, X., West, P., Brahman, F., Shen, T., Khashabi, D., & Choi, Y. (2022) · arXiv · doi:10.48550/arxiv.2211.00053 · Cited by 41 · cited 2×
“Finally, we suggest augmenting Transformers with planning modules as well as using refinement methods, that can iteratively improve their generations [63, 36].”
BackgroundMethodSelf-citationVeličković, P., & Blundell, C. (2021) · Patterns · doi:10.1016/j.patter.2021.100273 · Cited by 39 · cited 1×
“However, these models have also been shown to struggle across multiple domains [32], including algorithmic reasoning [78], commonsense reasoning [62, 40], theory of mind [65], planning [76], logical reasoning [70], and ethical reasoning [36].”
BackgroundStine, R. A. (2014) · doi:10.1002/9781118445112.stat03480 · Cited by 39 · cited 1×
“While we make these arguments with affine maps, similar behaviors, perhaps even more acute, would hold with nonlinear maps [21]—but their study is beyond the scope of this paper.”
BackgroundFaithful Reasoning Using Large Language Models
Creswell, A., & Shanahan, M. (2022) · arXiv · doi:10.48550/arxiv.2208.14271 · Cited by 37 · cited 2×
“[15] Antonia Creswell and Murray Shanahan.”
MethodLocation Attention for Extrapolation to Longer Sequences
Dubois, Y., Dagan, G., Hupkes, D., & Bruni, E. (2020) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2020.acl-main.39 · Cited by 36 · cited 5×
“[22] Yann Dubois, Gautier Dagan, Dieuwke Hupkes, and Elia Bruni.”
BackgroundInfluentialHumans in Humans Out: On GPT Converging Toward Common Sense in both Success and FailurePreprint
Koralus, P., & Wang-Maścianica, V. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2303.17276 · Cited by 28 · cited 2×
“In stark contrast, the same models sometimes struggle with simple, intuitive tasks [7, 44, 34].”
BackgroundThe EOS Decision and Length Extrapolation
Newman, B., Hewitt, J., Liang, P., & Manning, C. D. (2020) · BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (BlackboxNLP) · doi:10.18653/v1/2020.blackboxnlp-1.26 · Cited by 24 · cited 6×
“Collapsed Compositionality and Robustness Implications Transformers today demonstrate undeniably powerful empirical results.”
BackgroundInfluentialThe Parallelism Tradeoff: Limitations of Log-Precision Transformers
Merrill, W., & Sabharwal, A. (2023) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00562 · Cited by 22 · cited 1×
“Transformer-specific work has focused on quantifying the class of problems that (not necessarily autoregressive) transformers can express assuming perfect parameters [51, 50, 14, 49, inter alia].”
BackgroundSymbolic Brittleness in Sequence Models: On Systematic Generalization in Symbolic Mathematics
Welleck, S., West, P., Cao, J., & Choi, Y. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i8.20841 · Cited by 21 · cited 2×
“This encompasses various facets of generalization, including easy-to-hard generalization [49, 3], length generalization [42, 10, 37], and generalization on symbolic mathematical integration [64].”
BackgroundSelf-citationCritical Thinking for Language ModelsPreprint
Betz, G., Voigt, C., & Richardson, K. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.07185 · Cited by 18 · cited 2×
“[6] Gregor Betz, Christian Voigt, and Kyle Richardson.”
BackgroundUnobserved Local Structures Make Compositional Generalization Hard
Bogin, B., Gupta, S., & Berant, J. (2022) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2022.emnlp-main.175 · Cited by 17 · cited 1×
“Lastly, choosing a training split that maximizes the number of observed patterns between the train and test data [10], or diversifying in-prompt examples to cover the maximum of patterns [41], ultimately enhancing generalization.”
BackgroundOn the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages
Bhattamishra, S., Ahuja, K., & Goyal, N. (2020) · International Conference on Computational Linguistics · doi:10.18653/v1/2020.coling-main.129 · Cited by 16 · cited 2×
“Challenges of transformers in generalization Extensive research has been done to investigate the generalization capabilities of transformers [3, 54, 26, 64, 8, 46].”
BackgroundBueno, M., Gemmell, C., Dalton, J., et al. (2022) · MATHNLP · doi:10.48550/arxiv.2208.11445 · Cited by 14 · cited 2×
“This encompasses various facets of generalization, including easy-to-hard generalization [49, 3], length generalization [42, 10, 37], and generalization on symbolic mathematical integration [64].”
Background(2023) · doi:10.18653/v1/2023.acl-short.38 · Cited by 12
Scaling Laws for Generative Mixed-Modal Language Models
Aghajanyan, A., Yu, L., Conneau, A., Hsu, W.-N., Hambardzumyan, K., Zhang, S., Roller, S., Goyal, N., Levy, O., & Zettlemoyer, L. (2023) · arXiv · doi:10.48550/arxiv.2301.03728 · Cited by 10 · cited 5×
“Scratchpad: dp[4] = max(input[4], 0) = max(2, 0) = 2 dp[3] = max(input[3], input[4], 0) = max(5, 2, 0) = 5 dp[2] = max(dp[3], input[2] + dp[4], 0) = max(5, 1 + 2, 0) = 5 dp[1] = max(dp[2], input[1] + dp[3], 0) = max(5, 2 + 5, 0) = 7 dp[0] = max(dp[1], input[0] + dp[2], 0) = max(7, 3 + 5, 0) = 8”
BackgroundInfluentialA Logic for Expressing Log-Precision Transformers
Merrill, W., & Sabharwal, A. (2023) · Advances in Neural Information Processing Systems 36 · doi:10.52202/075280-2284 · Cited by 6 · cited 1×
“Transformer-specific work has focused on quantifying the class of problems that (not necessarily autoregressive) transformers can express assuming perfect parameters [51, 50, 14, 49, inter alia].”
BackgroundAutomating Moral Reasoning (Invited Paper)
Slavkovik, M. (2022) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/oasics.aib.2022.6 · Cited by 5
The expressive power of transformers with chain of thought
Merrill, W., & Sabharwal, A. (2023) · arXiv · doi:10.48550/arxiv.2310.07923 · Cited by 4 · cited 1×
“Transformer-specific work has focused on quantifying the class of problems that (not necessarily autoregressive) transformers can express assuming perfect parameters [51, 50, 14, 49, inter alia].”
BackgroundTighter Bounds on the Expressivity of Transformer Encoders
Chiang, D., Cholak, P., & Pillay, A. (2023) · arXiv · doi:10.48550/arxiv.2301.10743 · Cited by 4 · cited 1×
“Transformer-specific work has focused on quantifying the class of problems that (not necessarily autoregressive) transformers can express assuming perfect parameters [51, 50, 14, 49, inter alia].”
BackgroundOn Small Perturbations of Stable Markov Operators: Unbounded Case
Delyon, B., & Juditsky, A. (1999) · doi:10.1137/s0040585x97977173 · Cited by 3 · cited 1×
“In this latter literature, the focus is usually on the contractive regime in which accrued errors can be kept under control, and the subsequent convergence guarantees (e.g., [23]).”
BackgroundLiang, Z., Zhang, Z., Bethard, S. J., & Surdeanu, M. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2305.00061 · Cited by 3 · cited 1×
“Second, encouraging transformers to generate reasoning steps explicitly within a single generation [55, 80, 44, 42].”
BackgroundReasoning with Transformer-based Models: Deep Learning, but Shallow Reasoning
Clavel, C. (2021) · UC Irvine · doi:10.24432/c5w300 · Cited by 2 · cited 2×
“We observe that all analyzed models match the Relative Information Gain prediction that o 1 (whether the first element goes into the output sequence or not) should be the easiest value to predict (see Figures 30, 31, and 32).”
BackgroundMethodTowards Understanding Grokking: An Effective Theory of Representation Learning
Liu, Z., Kitouni, O., Nolte, N., Michaud, E. J., Tegmark, M., & Williams, M. (2022) · arXiv · doi:10.48550/arxiv.2205.10343 · cited 2×
“Subsequent works focus on characterizing when and why grokking arises: [47] show that perfect generalization in an arithmetic addition task happens when there is sufficient data to determine the appropriate structured representation, later extended to sparse parity in [52] where a sparse subnetwork…”
BackgroundBian, N., Han, X., Sun, L., Lin, H., Lu, Y., He, B., Jiang, S., & Dong, B. (2023) · arXiv · doi:10.48550/arxiv.2303.16421
Research works printed but not linked: 6
- Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length general- ization in large language models. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 38546-38556.
- Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. End-to-end algorithm synthesis with recurrent networks: Extrapolation without overthinking. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 20232-20242.
- Yoshua Bengio, Réjean Ducharme, and Pascal Vincent. A neural probabilistic language model. In Advances in Neural Information Processing Systems, volume 13. MIT Press, 2000.
- D. Bertsekas. Abstract Dynamic Programming: 3rd Edition. Athena scientific optimization and computation series. Athena Scientific., 2022.
- Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans- formers learn shortcuts to automata. In International Conference on Learning Representations, 2023.
- Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large language models still can't plan (a benchmark for LLMs on planning and reasoning about change). In NeurIPS 2022 Foundation Models for Decision Making Workshop, 2022.
Cited by
Sorted by citations
Evaluation and mitigation of the limitations of large language models in clinical decision-making
Hager, P., Jungmann, F., Holland, R., Bhagat, K., Hubrecht, I., Knauer, M., Vielhauer, J., Makowski, M., Braren, R., Kaissis, G., et al. (2024) · Nature Medicine · doi:10.1038/s41591-024-03097-1 · Cited by 798
“The subset was evenly split between the four target pathologies with 20 patients randomly selected from each pathology and matching the makeup of the full dataset (Supplementary Section H).”
Dissociating language and thought in large language models
Mahowald, K., Ivanova, A. A., Blank, I. A., Kanwisher, N., Tenenbaum, J. B., & Fedorenko, E. (2024) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2024.01.011 · Cited by 345
“One solution to overcome these limitations has been to augment an LLM with a symbolic tracker of entity states and character beliefs (Sclar et al., 2023), an approach that mirrors the separation between language and theory of mind processing in humans.”
Generative AI for economic research: use cases and implications for economists
Korinek, A. (2023) · Journal of Economic Literature · doi:10.1257/jel.20231736 · Cited by 293
“Dziri et al. (2023) show that LLMs also have difficulties in handling tasks that demand intricate multistep reasoning.”
BackgroundFrom text to insight: large language models for chemical data extraction
Schilling-Wilhelmi, M., Ríos-García, M., Shabih, S., Gil, M. V., Miret, S., Koch, C. T., Marquez, J. A., & Jablonka, K. M. (2024) · Chemical Society Reviews · doi:10.1039/d4cs00913d · Cited by 178
Markovitch, D. G., Stough, R. A., & Huang, D. (2024) · Journal of Retailing and Consumer Services · doi:10.1016/j.jretconser.2024.103847 · Cited by 100
Metadata
- Authors
- Dziri, N., Lu, X., Sclar, M., Li, X. (., Jiang, L., Lin, B. Y., Welleck, S., West, P., Bhagavatula, C., Bras, R. L., Hwang, J., Sanyal, S., Ren, X., Ettinger, A., Harchaoui, Z., & Choi, Y.
- Venue
- Advances in Neural Information Processing Systems 36
- Published
- 2023
- Pages
- 70293-70332
- ISSN
- 1049-5258 (ISSN-L)
- OpenAlex
- W7133191918
- Cited by
- 335
- References
- 82
- Citations by year
- 2026: 106 · 2025: 77 · 2024: 92 · 2023: 60
- FWCI
- 610.22
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- neural information processing systems (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (2134012)
- Allen Institute for Artificial Intelligence
- Defense Advanced Research Projects Agency (N66001-19-2-4031, N66001-19)
- Naval Information Warfare Center Pacific
- Topics
- Social Sciences › Arts and Humanities › Language and Linguistics › Syntax, Semantics, Linguistic Variation
- Social Sciences › Arts and Humanities › Philosophy › Philosophy and Theoretical Science
- Social Sciences › Arts and Humanities › History and Philosophy of Science › Cybernetics and Technology in Society
- Keywords
- transformer models, compositional generalization, compositional reasoning, large language models
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-10-23, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-23 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
