論文の概要: Transformers are Efficient Compilers, Provably

• arxiv url: http://arxiv.org/abs/2410.14706v1
• Date: Mon, 07 Oct 2024 20:31:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-27 05:40:27.788519
• Title: Transformers are Efficient Compilers, Provably
• Title（参考訳）: トランスフォーマーは、おそらく効率的なコンパイラである
• Authors: Xiyu Zhai, Runlong Zhou, Liao Zhang, Simon Shaolei Du,
• Abstract要約: トランスフォーマーベースの大規模言語モデル(LLM)は、幅広い言語関連タスクにおいて驚くほど堅牢なパフォーマンスを示している。 本稿では,表現力の観点から,トランスフォーマーをコンパイラとして用いることの正式な調査に向けて第一歩を踏み出す。 代表言語であるMini-Huskyを導入し、現代のC言語の特徴をカプセル化する。
• 参考スコア（独自算出の注目度）: 11.459397066286822
• License:
• Abstract: 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.
• Abstract（参考訳）: トランスフォーマーベースの大規模言語モデル(LLM)は、プログラミング言語の理解や生成を含む幅広い言語関連タスクにおいて驚くほど堅牢なパフォーマンスを示している。 本稿では,表現力の観点から,トランスフォーマーをコンパイラとして用いることの正式な調査に向けて第一歩を踏み出す。 この目的のために,現代C言語の主要な特徴をカプセル化した代表型プログラミング言語Mini-Huskyを導入する。 入力符号列が抽象構文木(AST)と型推論(クリーンコード原理に基づく妥当な仮定)の両方に有界深さを持つ場合、変換器が要求するパラメータの数は、AST構成、シンボル分解、型解析などのコンパイルタスクを処理するために入力シーケンス長の対数にのみ依存することを示す。 重要な技術的課題は、トランスフォーマーが低レベルで動作し、各層が事前に定義された構造や意味を明示的に関連付けることなく、入力シーケンスを生ベクトルとして処理するという事実に起因している。 対照的に、高レベルのコンパイラタスクは複雑な関係と構造化されたプログラム情報を管理する必要がある。 私たちの主な技術的貢献はドメイン固有の言語であるCybertronの開発です。 さらに、リカレントニューラルネットワーク(RNN)は入力シーケンスに対して少なくとも1つの線形なパラメータを必要とすることを証明し、変換器とRNNを指数関数的に分離する。 最後に,Mini-Husky のコンパイラタスクにおいて,変換器と RNN を比較して理論的結果を実証的に検証する。

関連論文リスト

• Algorithmic Capabilities of Random Transformers [49.73113518329544]
  埋め込み層のみを最適化したランダムトランスフォーマーによって、どのような関数が学習できるかを検討する。 これらのランダムなトランスフォーマーは、幅広い意味のあるアルゴリズムタスクを実行することができる。 以上の結果から,これらのモデルが訓練される前にも,アルゴリズム能力がトランスフォーマに存在することが示唆された。
  論文  参考訳（メタデータ） (2024-10-06T06:04:23Z)
• Separations in the Representational Capabilities of Transformers and Recurrent Architectures [27.783705012503237]
  我々は,トランスフォーマーとRNNの表現能力の違いを,実践的妥当性のいくつかのタスクで分析する。 対数幅の一層変換器がインデックス検索を行うのに対し、RNNは線形サイズを隠蔽する必要があることを示す。 また、ログサイズの2層トランスは、最寄りのアルゴリズムをフォワードパスで実装できることを示す。
  論文  参考訳（メタデータ） (2024-06-13T17:31:30Z)
• Transformers meet Neural Algorithmic Reasoners [16.5785372289558]
  我々は、トランスフォーマー言語理解とグラフニューラルネットワーク(GNN)に基づくニューラルネットワーク推論(NAR)の堅牢性を組み合わせた新しいアプローチを提案する。 CLRS-30ベンチマークのテキストベースバージョンであるCLRS-Text上で得られたTransNARモデルを評価し,アルゴリズム推論のためのTransformerのみのモデルよりも大幅に向上したことを示す。
  論文  参考訳（メタデータ） (2024-06-13T16:42:06Z)
• The Expressive Power of Transformers with Chain of Thought [29.839710738657203]
  実際には、トランスフォーマーは「思考の連鎖」や「スクラッチパッド」を使用することで改善できる。 答えはYESであるが、増加量は中間生成量に大きく依存する。 また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置することが示唆された。
  論文  参考訳（メタデータ） (2023-10-11T22:35:18Z)
• Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection [88.23337313766353]
  この研究はまず、変換器がICLを実行するための包括的な統計理論を提供する。 コンテクストにおいて、トランスフォーマーは、幅広い種類の標準機械学習アルゴリズムを実装可能であることを示す。 エンフィングル変換器は、異なるベースICLアルゴリズムを適応的に選択することができる。
  論文  参考訳（メタデータ） (2023-06-07T17:59:31Z)
• Learning Transformer Programs [78.9509560355733]
  設計によって機械的に解釈可能なトランスフォーマーの訓練手順を導入する。 人書きプログラムをTransformerにコンパイルする代わりに、勾配に基づく最適化を用いてトレーニングできる改良されたTransformerを設計する。 Transformer Programsは適切なソリューションを自動的に見つけ、同等のサイズの標準のTransformerと同等に動作する。
  論文  参考訳（メタデータ） (2023-06-01T20:27:01Z)
• Error Correction Code Transformer [92.10654749898927]
  本稿では,トランスフォーマーアーキテクチャを任意のブロック長で線形符号のソフトデコードに拡張することを提案する。 我々は,各チャネルの出力次元を高次元に符号化し,個別に処理すべきビット情報のより良い表現を行う。 提案手法は、トランスフォーマーの極端なパワーと柔軟性を示し、既存の最先端のニューラルデコーダを、その時間的複雑さのごく一部で大きなマージンで上回る。
  論文  参考訳（メタデータ） (2022-03-27T15:25:58Z)
• Causal Transformers Perform Below Chance on Recursive Nested Constructions, Unlike Humans [7.897143833642971]
  2種類のネスト構造に対して4種類のトランスフォーマーLMを試験した。 トランスフォーマーは,短範囲の組み込み依存に対してほぼ完璧な性能を実現する。 長距離の組み込み依存関係では、Transformerのパフォーマンスは確率レベル以下に急落する。
  論文  参考訳（メタデータ） (2021-10-14T09:22:17Z)
• Thinking Like Transformers [64.96770952820691]
  本稿では,プログラミング言語の形式で変換器エンコーダの計算モデルを提案する。 RASPは、トランスフォーマーによって確実に学習できるタスクの解決策をプログラムするのにどのように使えるかを示す。 ヒストグラム、ソート、ダイク言語のためのRASPプログラムを提供する。
  論文  参考訳（メタデータ） (2021-06-13T13:04:46Z)
• Addressing Some Limitations of Transformers with Feedback Memory [51.94640029417114]
  トランスフォーマーは、フィードフォワードネットワークであるにもかかわらず、シーケンシャルな自動回帰タスクにうまく適用されている。 本稿では、過去のすべての表現を将来のすべての表現に公開する、フィードバックトランスフォーマーアーキテクチャを提案する。 言語モデリング、機械翻訳、強化学習の様々なベンチマークにおいて、表現能力の増大は、同等のトランスフォーマーよりもはるかに強力なパフォーマンスを持つ、小さくて浅いモデルを生成することができることを実証する。
  論文  参考訳（メタデータ） (2020-02-21T16:37:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。