证明了变换器可高效编译代码，参数量仅随输入长度对数增长。
Transformers are Efficient Compilers, Provably
- 用形式化语言构建代码编译任务，证明变换器在结构受限时参数量只需对数级
- 在迷你编程语言上实验证明变换器比RNN效率高，参数量差距呈指数级
- 适合对模型表达能力、编译原理感兴趣的读者
基于Transformer的大语言模型在编程语言理解与生成等任务中表现出色。本文首次从表达能力角度形式化研究变压器作为编译器的潜力。为此，提出一种代表性的编程语言Mini-Husky，涵盖现代C类语言的核心特征。我们证明：若输入代码序列在抽象语法树（AST）和类型推断中的深度有界（基于代码整洁性原则的合理假设），则变换器完成编译任务（如AST构建、符号解析、类型分析）所需的参数量仅依赖于输入序列长度的对数。主要技术挑战在于变换器以低层向量处理输入，缺乏显式结构关联；而编译任务需管理复杂程序结构信息。为此，我们开发了领域专用语言Cybertron，用于生成变换器表达能力的形式化证明。进一步证明，递归神经网络（RNN）所需参数量至少与输入序列长度成线性关系，从而确立了变换器与RNN之间指数级的参数效率差距。最后，我们在Mini-Husky上的编译任务上实证验证了理论结果。
原文摘要 · Abstract (English)
Transformer-based large language models (LLMs) have demonstrated surprisingly robust performance across a wide range of language-related tasks, including programming language understanding and generation. In this paper, we take the first steps towards a formal investigation of using transformers as compilers from an expressive power perspective. To this end, we introduce a representative programming language, Mini-Husky, which encapsulates key features of modern C-like languages. We show that if the input code sequence has a bounded depth in both the Abstract Syntax Tree (AST) and type inference (reasonable assumptions based on the clean code principle), then the number of parameters required by transformers depends only on the logarithm of the input sequence length to handle compilation tasks, such as AST construction, symbol resolution, and type analysis. A significant technical challenge stems from the fact that transformers operate at a low level, where each layer processes the input sequence as raw vectors without explicitly associating them with predefined structure or meaning. In contrast, high-level compiler tasks necessitate managing intricate relationships and structured program information. Our primary technical contribution is the development of a domain-specific language, Cybertron, which generates formal proofs of the transformer's expressive power, scaling to address compiler tasks. We further establish that recurrent neural networks (RNNs) require at least a linear number of parameters relative to the input sequence, leading to an exponential separation between transformers and RNNs. Finally, we empirically validate our theoretical results by comparing transformers and RNNs on compiler tasks within Mini-Husky.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。