Faith and Fate: Limits of Transformers on Compositionality

The prediction of the last digit (or two digits) of the output solely relies on the last digit (or two digits) of each input number.

“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.”

The observation that models fail to learn component operations in a generalizable manner holds for all tasks.

“This observation holds for all tasks (See details in § B.4).”

In all settings, the ratio of fully correct nodes is almost perfect but sharply decreases toward zero with increasing graph layers.

“In all settings, the ratio of fully correct nodes is almost perfect but sharply decreases toward zero with increasing graph layers.”

The ratio of propagation errors is usually higher than the ratio of local errors.

“Moreover, the ratio of propagation errors is usually higher than the ratio of local errors.”

Performance sharply declines when evaluating unseen splits during training (out-of-domain) in multiplication and DP.

“However, the performance sharply declines when evaluating unseen splits during training, i.e., out-of-domain (OOD).”

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.

“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.”

The performance boost from question-scratchpad prompting diminishes to zero as complexity increases.

“However, this performance boost diminishes to zero as complexity increases.”

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.

“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).”

Prompting transformers with question-scratchpad pairs enhances performance compared to the zero-shot setting.

“Similarly, prompting transformers with question-scratchpad pairs enhances the performance compared to the zero-shot setting (refer to § B.5).”

The trend of performance deterioration with increasing complexity remains the same for few-shot prompting.

“The trend remains the same for few-shot prompting (see §B.2).”

No improvement in generalization for OOD cases beyond the overfitting point is observed even after extensive training periods for the multiplication task.

“Figure 4 shows no improvement in generalization for OOD cases beyond the overfitting point, even after extensive training periods.”

Models can memorize single-step operations.

“We find that while models can memorize single-step operations, they fail to compose them into correct reasoning paths, suggesting that they mostly make predictions based on shallow, rote learning rather than a deep, holistic task understanding ( §3.2.3).”

• AssumptionRests on an assumption: The three compositional tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.

Models fail to compose single-step operations into correct reasoning paths.

“We find that while models can memorize single-step operations, they fail to compose them into correct reasoning paths, suggesting that they mostly make predictions based on shallow, rote learning rather than a deep, holistic task understanding ( §3.2.3).”

• AssumptionRests on an assumption: The three compositional tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.

Errors rapidly escalate as the problem size grows.

“Concretely, we show that errors rapidly escalate as the problem size grows ( §3.2.3).”

Transformers at times predict partially correct answers even when the overall response is incorrect.

“At times transformers predict partially correct answers even when the overall response is incorrect.”

The triple (a_{i-2}, a_{i-1}, a_i) generally has higher scores than (a_i, a_{i+1}, a_{i+2}) in predicting o_i.

“with the former generally having higher scores than the latter.”

GPT-4 exhibits an increase in few-shot accuracy in most problem sizes when using question-scratchpad pairs of few-shot examples across the three tasks.

“GPT-4 exhibits an increase in few-shot accuracy in most problem sizes when using question-scratchpad pairs of few-shot examples across the three tasks.”

As predicted by Relative Information Gain, GPT3 few-shot without scratchpad predicts o1 correctly with the highest probability.

“As predicted by Relative Information Gain, the model predicts o 1 correctly with the highest probability.”

There is a notable decline in performance as task complexity increases, measured by graph parallelism for multiplication and dynamic programming and by propagation steps for puzzles.

“Overall, there is a notable decline in performance as the task complexity increases (measured by graph parallelism for multiplication and DP, and propagation steps for puzzles as shown in Figure14).”

GPT-4's performance with question-scratchpad pairs tends to decline as the complexity of the tasks increases.

“it tends to decline as the complexity of the tasks increases.”

All analyzed models match the Relative Information Gain prediction that o1 should be the easiest value to predict.

“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”

GPT2-XL fails to answer correctly 3x3 test examples.

“However, the performance is still low and GPT2-XL fails to answer correctly 3x3 test examples.”

GPT-4's performance with question-scratchpad pairs surpasses that of zero-shot and few-shot with question-answer pairs.

“While its performance surpasses that of zero-shot and few-shot with question-answer pairs”

Few-shot performance with question-answer pairs results in minimal improvement over the zero-shot setting for the multiplication and dynamic programming tasks.

“The few-shot performance with question-answer pairs results in minimal improvement over the zero-shot setting as depicted in Figure 16 and Figure 20 for the multiplication and DP tasks.”

For DP problems, o_i is highly predicted by (a_{i-1}, a_i, a_{i+1}).

“Table 4 shows that o i is highly predicted by (a i-1 , a i , a i+1 ).”

Grokking does not arise in the context of multiplication.

“We do not observe grokking arising in the context of multiplication, and we leave it to future work to explore whether this may be due to task difficulty hindering the learning of well-structured representations.”

GPT4 zero-shot accuracy in predicting partially correct responses is high.

“Figure 26: GPT4 zero-shot accuracy in predicting partially correct responses.This evidences surface pattern learning, since the accuracy of full answer prediction is significantly lower-and often near zero”

The few-shot setting did not lead to any improvement in the puzzle task.

“In contrast, the few-shot setting did not lead to any improvement in the puzzle task.”

Fine-tuning GPT3 on the tasks both with and without explicit reasoning graphs shows that models' learning fails to generalize beyond levels of complexity seen in training.

“For example, fine-tuning GPT3 on our tasks both with and without explicit reasoning graphs shows that models' learning fails to generalize beyond levels of complexity seen in training.”

In GPT4, o_{n-1} is among the easiest values to predict as expected by Relative Information Gain.

“In GPT4, we observe that o n-1 is among the easiest values to predict as expected by Relative Information Gain.”

GPT4 few-shot accuracy with question-scratchpad pairs degrades to zero as the complexity increases.

“GPT4 few-shot accuracy with question-scratchpad pairs on the 3 tasks.The performance improves for most problem sizes compared to zero-shot performance and few-shot using questionanswer pairs but degrades to zero as the complexity increases.”

The only case of a_i weakly helping predict neighbors with RelativeIG>0.1 is at the start of the sequence, where the first element helps predict the value of the second.

“The only case of this behavior with RelativeIG>0.1 is at the start of the sequence, where the first element helps predict the value of the second.”

GPT4 few-shot accuracy with question-scratchpad pairs improves for most problem sizes compared to zero-shot performance and few-shot using question-answer pairs.

“GPT4 few-shot accuracy with question-scratchpad pairs on the 3 tasks.The performance improves for most problem sizes compared to zero-shot performance and few-shot using questionanswer pairs but degrades to zero as the complexity increases.”

The accuracy of full answer prediction is significantly lower and often near zero.

“since the accuracy of full answer prediction is significantly lower-and often near zero”

a_i weakly helps to predict its neighbors.

“a i weakly helps to predict its neighbors.”

Systematic problem-solving capabilities do not emerge from maximum likelihood training on input-output sequences, even when prompted or trained with human-like reasoning steps (linearization of computation graphs).

“This substantial gap suggests that systematic problem-solving capabilities do not emerge from maximum likelihood training [5] on input-output sequences, even when prompted or trained with human-like reasoning steps (i.e., a linearization of computation graphs; §3.1).”

• cites [5]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionRests on an assumption: The three compositional tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.

Pattern matching, and not general reasoning capabilities, may be the cause behind correct model outputs.

“This high correlation suggests that pattern matching-and not general reasoning capabilities-may be the cause behind correct model outputs.”

The autoregressive characteristic of transformers, which forces them to tackle problems sequentially, presents a fundamental challenge that cannot be resolved by instructing the model to generate a step-by-step solution.

“These findings suggest that the autoregressive characteristic of transformers, which forces them to tackle problems sequentially, presents a fundamental challenge that cannot be resolved by instructing the model to generate a step-by-step solution.”

Models' success can be attributed, in part, to their exposure to training examples sub-graphs that involve the same computations required for solving test examples.

“Models' success can be attributed, in part, to their exposure to training examples sub-graphs that involve the same computations required for solving test examples (see Section 3.2.2)”

• AssumptionRests on an assumption: The three compositional tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.

The pattern of last-digit dependence holds true due to the principles of modulo arithmetic, which ensures the validity of this relationship in all cases.

“This pattern holds true due to the principles of modulo arithmetic, which ensures the validity of this relationship in all cases.”

If an output element heavily relies on a single or a small set of input features, transformers are likely to recognize such correlation during training and directly map these input features to predict the output element in testing, without going through rigorous multi-hop reasoning, giving a false illusion of performing compositional reasoning.

“These experiments suggest that if an output element heavily relies on a single or a small set of input features, transformers are likely to recognize such correlation during training and directly map these input features to predict the output element in testing, without going through the rigorous multi-hop reasoning and giving a false illusion of performing compositional reasoning.”

Pre-training is not sufficient to teach models how to combine basic operations to solve compositional problems, especially as problems grow more complex.

“These results indicate that pre-training is in fact not sufficient to teach models how to combine basic operations to solve compositional problems, especially as problems grow more complex.”

Transformers could be inherently limited in solving compositionally complex tasks out-of-the-box.

“We argue that transformers could be inherently limited in solving compositionally complex tasks out-of-the-box 3 .”

• AssumptionRests 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.
• AssumptionRests 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.
• AssumptionRests on an assumption: The three studied tasks are representative compositional tasks.

Humans can solve 3-digit by 3-digit multiplication arithmetic after learning basic calculation rules.

“For instance, humans can solve 3-digit by 3-digit multiplication arithmetic after learning basic calculation rules [22,34].”

• cites [22]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [34]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Even when training directly with guidance on the computation steps, models still fail to learn component operations in a generalizable manner.

“These results indicate that even when training directly with guidance on the computation steps, models still fail to learn component operations in a generalizable manner.”

Systematic problem-solving capabilities do not emerge via exhaustive training on task-specific data.

“Similar trends hold in all tasks (see § B.3), suggesting that systematic problem-solving capabilities do not emerge via exhaustive training on task-specific data.”

Models depend on a greedy process of producing the next word to make predictions without a rigorous global understanding of the task.

“Instead, models depend on a greedy process of producing the next word to make predictions without a rigorous global understanding of the task.”

Exponential error accumulation occurs in abstract compositional tasks.

“Importantly, we provide theoretical evidence of exponential error accumulation using abstract compositional tasks.”

• AssumptionRests 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.
• AssumptionRests 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.

Under the assumptions of Proposition 4.1, if c_n <= beta alpha^n for some alpha in (0,1) and beta > 0, then P(f_n != f_n) tends exponentially to 1 as n increases.

“Moreover, if c n ≤ βα n for some α ∈ (0, 1), β > 0, P(f n ̸ = f n ) tends exponentially to 1 as n increases.”

• AssumptionThe authors state this as an assumption: In Proposition 4.1, h_n is a perfect estimator of h_n.
• AssumptionThe 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).
• AssumptionThe authors state this as an assumption: In Proposition 4.1, g's errors are independent.

The spurious pattern of correlation between first digits is likely to be learned by a model.

“Hence, this spurious pattern is likely to be learned by a model.”

These patterns are possibly due to high frequency of (input, output) multiplication pairs in the pretraining data, in contrast to intermediate reasoning steps.

“These patterns are possibly due to high frequency of (input, output) multiplication pairs in the pretraining data, in contrast to intermediate reasoning steps.”

The observed performance gain in low-complexity and in-domain cases and the striking performance drop in OOD and highly complex cases may be elucidated by pattern-matching learning.

“This may elucidate the observed performance gain in low-complexity and in-domain cases and the striking performance drop in OOD and highly complex cases.”

The same transformer models sometimes struggle with simple, intuitive tasks.

“In stark contrast, the same models sometimes struggle with simple, intuitive tasks [9,62,40].”

• cites [9]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [62]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [40]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching, without necessarily developing systematic problem-solving skills.

“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.”

• AssumptionRests on an assumption: The three compositional tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.
• AssumptionRests 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.
• AssumptionRests 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.
• AssumptionRests on an assumption: The three studied tasks are representative compositional tasks.

Under the assumptions of Proposition 4.2, P(f_n != f_n) >= 1 - (1 - epsilon - c)^{n-1}(1 - epsilon - c/(c + epsilon)).

“Precisely, P(f n ̸ = f n ) ≥ 1 -(1 -ϵ -c) n-1 (1 -ϵ -c/(c + ϵ))”

• AssumptionThe 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.

Autoregressive generations' performance can rapidly decay with increased task complexity.

“we provide theoretical arguments on abstract multi-step reasoning problems that highlight how autoregressive generations' performance can rapidly decay with increased task complexity.”

• AssumptionRests 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.
• AssumptionRests 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.

Models mostly make predictions based on shallow, rote learning rather than a deep, holistic task understanding.

“We find that while models can memorize single-step operations, they fail to compose them into correct reasoning paths, suggesting that they mostly make predictions based on shallow, rote learning rather than a deep, holistic task understanding ( §3.2.3).”

• AssumptionRests on an assumption: The three compositional tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer.

Transformers may be too limited to solve compositionally complex tasks.

“We argue using stylized examples that transformers may be too limited to solve compositionally complex tasks.”

All tasks analyzed in the work belong to a class expressible by transformers.

“All tasks analyzed in our work belong to a class expressible by transformers”

• cites [51]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [50]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [14]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [49]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Certain tasks may not possess the inherent compositionality they seem to have.

“Despite initially appearing challenging, certain tasks may not possess the inherent compositionality they seem to have.”

The known upper bound might not be tight.

“suggesting that known upper bound might not be tight.”

Proposition 4.1 directly applies to multiplication, because m-by-n digit multiplication can be seen as n independent instances of m-by-1 digit multiplication.

“Prop.4.1 directly applies to multiplication, since m-by-n digit multiplication can be seen as n independent instances of m-by-1 digit multiplication (see Cor. D.1).”

• cites Cor. D.1Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionRests on an assumption: The tasks evaluated are low collision settings.

The proofs apply to autoregressive language models in general.

“Importantly, these proofs apply to autoregressive LMs in general.”

• AssumptionThe 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 Section 4 show that, under reasonable assumptions, the probability of incorrect predictions converges exponentially to approximately 1 for abstract compositional tasks.

“The proofs presented in §4 show that, under reasonable assumptions, the probability of incorrect predictions converges exponentially to ≈ 1 for abstract compositional tasks.”

• AssumptionThe authors state this as an assumption: The theoretical proofs' assumptions hold for the abstract compositional tasks and autoregressive language models considered.

Reaching full mastery is inherently challenging.

“Our findings show that reaching full mastery is inherently challenging, providing insights into the complexities involved.”

The strong performance of transformers should be taken with a certain grain of salt.

“More broadly, our findings suggest that the strong performance of transformers should be taken with a certain grain of salt”

Shortcut pattern matching can ultimately result in poor generalization.

“However, such an approach can ultimately result in poor generalization as shown in our study.”

Proposition 4.2's proof shows an exponential rate of convergence.

“Prop.4.2's proof also shows an exponential rate of convergence.”

Desired solutions could be readily derived from input-output sequences present in the training data, allowing for shortcut pattern matching to produce acceptable solutions.

“This is due to the fact that desired solutions could be readily derived from input-output sequences present in the training data, allowing for shortcut pattern matching to produce acceptable solutions.”

For the scratchpad approach, the study is limited to establishing only a correlation between the model generation and its preceding context, because it cannot inspect the exact tokens the model attends to when making the prediction.

“Although they are a useful way to systematically represent rigorous reasoning processes, it is important to note that for the scratchpad approach, we are limited to only establishing a correlation between the model generation and its preceding context, as we cannot inspect the exact tokens model attends to when making the prediction.”

Repeated applications of a function often imply unbounded errors: if g(x) can be expressed as an affine transformation F x + c, then it may be viewed as a first-order vector autoregression, which are known to be unstable when |lambda| >= 1 for at least one eigenvalue lambda of F.

“Moreover, repeated applications of a function often imply unbounded errors: if g(x) can be expressed as an affine transformation F x+c, then it may be viewed as a first-order vector autoregression, which are known to be unstable when |λ| ≥ 1 for at least one λ eigenvalue of F [31, Prop.10.1].”

• cites 31, Prop.10.1Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Transformers may have fundamental weaknesses in certain intellectual tasks that require true multi-step compositional operations such as multiplications and logic puzzles.

“Yet, our study suggests that they may have fundamental weaknesses in certain intellectual tasks that require true multi-step compositional operations such as multiplications and logic puzzles.”

The model cannot learn the underlying computational rules.

“indicating that it cannot learn the underlying computational rules.”

The value of the neighbors helps determine whether to select a number for the subsequence.

“since the value of the neighbors helps determine whether to select a number for the subsequence”

Pattern matching can hinder generalization in complex compositional tasks.

“Building upon this line of inquiry, we present a more rigorous examination of sub-graph matching between training and test instances for complex compositional tasks where we demonstrate how pattern matching can hinder generalization.”

The weakly predictive power of (a_{i-3}, a_{i-2}, a_{i-1}) to predict o_i is caused by the lexicographically smallest sequence bias.

“We believe that this last point is the cause of the weakly predictive power of (a i-3 , a i-2 , a i-1 ) to predict o i”

If c << epsilon, then lim inf_{n->+∞} P(f_n != f_n) is approximately 1.

“Note that if c ≪ ϵ then lim inf n→+∞ P(f n ̸ = f n ) ≈ 1.”

• AssumptionThe authors state this as an assumption: When g has low collision, c << epsilon.

Asking for the lexicographically smallest sequence biases the output subsequence to care more about the previous numbers rather than the following ones.

“asking for the lexicographically smallest sequence biases the output subsequence to care more about the previous numbers rather than the following ones.”

The total number of training examples required for multiplication up to 5 digits by 5 digits reaches approximately 9.1 billion examples.

“With this particular setup, the total number of training examples required for multiplication up to 5 digits by 5 digits reaches an astonishing figure of approximately 9.1 billion examples.”

The study suggests fundamental limitations that impede transformers from fully mastering certain compositional operations.

“Our study suggests fundamental limitations that impede transformers from fully mastering certain compositional operations.”

Transformers can often solve multi-step compositional problems by collapsing the depth of the compositional operations via analogical pattern matching.

“Our careful study based on the computation graph and analyses demonstrates that transformers can often solve multi-step compositional problems by collapsing the depth of the compositional operations via analogical pattern matching.”

In Proposition 4.2, if c ≪ ε then lim inf n→+∞ P(f_n ≠ f_n) ≈ 1.

“Note that in Proposition 4.2, if c ≪ ϵ then lim inf n→+∞ P(f n ̸ = f n ) ≈ 1.”

If a model M solves shifted addition perfectly but incorrectly solves at least one m-digit by 1-digit multiplication for some fixed m, then the probability that M solves any m-digit by n-digit multiplication using long-form multiplication tends to 0 as n tends to infinity.

“Corollary D.1.Assume that a model M solves shifted addition perfectly, but it incorrectly solves at least one m digit by 1 digit multiplication for some fixed m.Then, the probability that M will solve any m digit by n digit multiplication using the long-form multiplication algorithm tends to 0 when n tends to infinity.”

Under the assumptions P(z(g(X))=1 | z(X)=0) ≤ c and P(z(g(X))=0 | z(X)=1) = ε > 0 with c+ε<1, the limit inferior as n→∞ of P(z(g^n)=0) equals 1 - c/(c+ε).

“Assume P(z( g(X)) = 1 | z(X) = 0) ≤ c and P(z( g(X)) = 0 | z(X) = 1) = ϵ > 0 with c + ϵ < 1.Then, lim inf n→+∞ P(z( g n ) = 0) = 1c/(c + ϵ).”

• AssumptionThe authors state this as an assumption: In Lemma D.2, P(z(g(X))=1 | z(X)=0) ≤ c.
• AssumptionThe authors state this as an assumption: In Lemma D.2, P(z(g(X))=0 | z(X)=1) = ε > 0 with c+ε<1.

If for task T all valid reasoning chains to arrive at a correct result have at least length n, then the probability of solving task T correctly tends to at most c/(c+ε).

“If for task T we know that all valid reasoning chains to arrive at a correct result have at least length n (i.e., the equivalent of defining f n = g n in Lemma D.1) then the probability of solving task T correctly tends to at most c/(c + ϵ).”

Let f_n(x)=g^n(x). If P(g(X)=g(Y) | X≠Y) ≤ c and P(g≠g)=ε>0 with c+ε<1, then lim inf_{n→∞} P(f_n≠f_n) ≥ 1 - c/(c+ε).

“Proposition D.2.Let f n (x) = g n (x).Assume P(g(X) = g(Y ) | X ̸ = Y ) ≤ c (i.e.recovering from a mistake due to the randomness of applying the estimator on an incorrect input has probability at most c).If P(g ̸ = g) = ϵ > 0 with c + ϵ < 1, then lim inf n→+∞ P(f n ̸ = f n ) ≥ 1c/(c + ϵ).”

• AssumptionThe authors state this as an assumption: In Proposition D.2, P(g(X)=g(Y) | X≠Y) ≤ c.
• AssumptionThe authors state this as an assumption: In Proposition D.2, P(g≠g)=ε>0 with c+ε<1.

A very high a1 indicates that with high probability o2 will not be selected for the final subsequence.

“This again matches intuition, since a very high a 1 indicates that with high probability o 2 will not be selected for the final subsequence.”

If c_n < c for all n, then lim inf_{n→∞} P(f_n≠f_n) ≥ 1-c.

“Thus, lim inf n→+∞ P(f n ̸ = f n ) ≥ lim inf n→+∞ 1 -c -(1 -ϵ) n • (1 -c) = 1 -c”

If c_n ≤ β α^n, then lim_{n→∞} P(f_n=f_n)=1.

“Note: In the case where c n ≤ βα n , we can derive an even stronger conclusion.In this case, we can prove that lim n→+∞ P(f n = f n ) = 1.”

The high accuracy in predicting partially correct responses evidences surface pattern learning.

“This evidences surface pattern learning, since the accuracy of full answer prediction is significantly lower-and often near zero”