In this technical note, we study the problem of inverse permutation learning in decoder-only transformers. Given a permutation and a string to which that permutation has been applied, the model is tasked with producing the original (``canonical'') string. We argue that this task models a natural robustness property across a variety of reasoning tasks, including long-context retrieval, multiple choice QA and in-context learning. Our primary contribution is an impossibility result: we show that an arbitrary depth, decoder-only transformer cannot learn this task. This result concerns the expressive capacity of decoder-only transformer models and is agnostic to training dynamics or sample complexity. We give a pair of alternative constructions under which inverse permutation learning is feasible. The first of these highlights the fundamental role of the causal attention mask, and reveals a gap between the expressivity of encoder-decoder transformers and the more popular decoder-only architecture. The latter result is more surprising: we show that simply padding the input with ``scratch tokens" yields a construction under which inverse permutation learning is possible. We conjecture that this may suggest an alternative mechanism by which chain-of-thought prompting or, more generally, intermediate ``thinking'' tokens can enable reasoning in large language models, even when these tokens encode no meaningful semantic information (e.g., the results of intermediate computations).

翻译：在本技术报告中，我们研究了仅解码器Transformer中的逆置换学习问题。给定一个置换及其应用后的字符串，模型的任务是生成原始（“规范”）字符串。我们认为该任务建模了多种推理任务中自然的鲁棒性属性，包括长上下文检索、多项选择问答和上下文学习。我们的主要贡献是一个不可能性结果：我们证明任意深度的仅解码器Transformer无法学习此任务。该结果涉及仅解码器Transformer模型的表达能力，且与训练动态或样本复杂度无关。我们提出了两种使逆置换学习可行的替代构造。第一种构造突显了因果注意力掩码的基础性作用，并揭示了编码器-解码器Transformer与更流行的仅解码器架构之间的表达能力差距。后一结果更为令人惊讶：我们证明仅通过在输入中填充“草稿令牌”即可构造出使逆置换学习可行的方案。我们推测这可能暗示了一种替代机制，通过该机制，思维链提示或更广义的中间“思考”令牌能够使大语言模型进行推理，即使这些令牌不编码任何有意义的语义信息（例如中间计算结果）。