Can Transformers predict new syllogisms by composing established ones? More
generally, what type of targets can be learned by such models from scratch?
Recent works show that Transformers can be Turing-complete in terms of
expressivity, but this does not address the learnability objective. This paper
puts forward the notion of 'distribution locality' to capture when weak
learning is efficiently achievable by regular Transformers, where the locality
measures the least number of tokens required in addition to the tokens
histogram to correlate nontrivially with the target. As shown experimentally
and theoretically under additional assumptions, distributions with high
locality cannot be learned efficiently. In particular, syllogisms cannot be
composed on long chains. Furthermore, we show that (i) an agnostic scratchpad
cannot help to break the locality barrier, (ii) an educated scratchpad can help
if it breaks the locality at each step, (iii) a notion of 'inductive
scratchpad' can both break the locality and improve the out-of-distribution
generalization, e.g., generalizing to almost double input size for some
arithmetic tasks.

此论文提出了 “分布局部性” 的概念，用于捕捉正常 Transformer 模型有效实现弱学习的情况，同时证明了分布局部性高的情况下不能高效学习，并且介绍了通过破坏分布局部性和改进超出分布泛化能力的 “归纳式草稿” 概念。

Transformer 推理能力的界限与归纳式草稿板

How Far Can Transformers Reason? The Locality Barrier and Inductive  Scratchpad

Large pre-trained language models perform remarkably well on tasks that can
be done "in one pass", such as generating realistic text or synthesizing
computer programs. However, they struggle with tasks that require unbounded
multi-step computation, such as adding integers or executing programs.
Surprisingly, we find that these same models are able to perform complex
multi-step computations -- even in the few-shot regime -- when asked to perform
the operation "step by step", showing the results of intermediate computations.
In particular, we train transformers to perform multi-step computations by
asking them to emit intermediate computation steps into a "scratchpad". On a
series of increasingly complex tasks ranging from long addition to the
execution of arbitrary programs, we show that scratchpads dramatically improve
the ability of language models to perform multi-step computations.

利用逐步计算的方法，通过训练变换器模型在少量数据中输出中间运算结果到 “scratchpad”，为多步计算任务赋能，从而显著提高预训练语言模型处理复杂计算的能力。