論文の概要: The Discrete-Log Clock: How a Transformer Learns Modular Multiplication
- arxiv url: http://arxiv.org/abs/2606.17399v1
- Date: Tue, 16 Jun 2026 01:16:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-17 17:15:32.197927
- Title: The Discrete-Log Clock: How a Transformer Learns Modular Multiplication
- Title（参考訳）: 離散ログクロック:トランスフォーマーがモジュラ乗算を学習する方法
- Authors: Huu Danh Nguyen,
- Abstract要約: 以前の研究は、学習された埋め込みは全ての周波数を必要とする「密度」フーリエスペクトルを持つと報告していた。
この密度は、間違ったベースで分析する人工物であることを示す。
我々は,Nanda らの Clock アルゴリズムに類似した "Discrete-Log Clock" アルゴリズムを実装した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: When small transformers grok modular multiplication, prior work reports that the learned embedding has a "dense" Fourier spectrum requiring all frequencies. This contrasts with modular addition, where only a sparse set of key frequencies suffices. We show this density is an artifact of analyzing in the wrong basis. The natural Fourier transform for multiplication is not the standard additive DFT but the multiplicative character transform, which decomposes functions on the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ into its irreducible representations. Applying this transform to a grokked transformer trained on $a \cdot b \bmod 113$, we find the embedding spectrum becomes highly sparse (Gini coefficient 0.58 vs. 0.07 in the additive basis) with only 4 key frequencies carrying significant energy. Furthermore, 96.9% of MLP neurons are cleanly tuned to a single multiplicative frequency, and neuron activation heatmaps reveal 2D-periodic structure when reordered by the discrete logarithm. These results demonstrate the transformer reduces multiplication to addition in discrete-log space, implementing a "Discrete-Log Clock" algorithm analogous to Nanda et al.'s Clock algorithm for addition. The methodology generalizes: matching the analysis basis to the algebraic structure of the task reveals interpretable structure where standard tools see noise.
- Abstract（参考訳）: 小さな変圧器がモジュラー乗算を振る舞うと、先行研究は、学習された埋め込みは全ての周波数を必要とする「密度」フーリエスペクトルを持つと報告した。
これはモジュラー加算とは対照的で、キー周波数のスパースセットだけで十分である。
この密度は、間違ったベースで分析する人工物であることを示す。
乗法に対する自然なフーリエ変換は標準加法的 DFT ではなく、乗法群 $(\mathbb{Z}/p\mathbb{Z})^*$ 上の函数を既約表現に分解する乗法的文字変換である。
この変換を$a \cdot b \bmod 113$で訓練されたグラクテッド変圧器に適用すると、埋め込みスペクトルは非常にスパース(Gini coefficient 0.58 vs. 0.07)になる。
さらに、MLPニューロンの96.9%は1つの乗法周波数にきれいに調整され、ニューロンの活性化熱マップは離散対数で並べ替えられたときに2D周期構造を示す。
これらの結果から, 離散ログ空間における乗算を減らし, Nanda et al の Clock アルゴリズムに類似した "Discrete-Log Clock" アルゴリズムを実装した。
解析基底とタスクの代数構造とを合わせると、標準ツールがノイズを見ることができる解釈可能な構造が明らかになる。
関連論文リスト
- Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't [78.36679389968772]
パッド付き$textL$ constantprecision transformerは、表現性に対して驚くほど堅牢である。
glogd-looped constant-precision transformer reach $textFO-uniform TCd$, growing-precision transformer reach $textFO-uniform TCd$
論文 参考訳（メタデータ） (2026-05-28T19:58:43Z) - FUTON: Fourier Tensor Network for Implicit Neural Representations [56.48739018255443]
入射神経表現(INR)はシグナルを符号化する強力なツールとして現れてきたが、支配的な設計はしばしば収束が遅く、ノイズに過度に適応し、外挿が不十分である。
低ランクテンソル分解により係数がパラメータ化される一般化フーリエ級数として信号をモデル化するFUTONを導入する。
論文 参考訳（メタデータ） (2026-02-13T19:31:44Z) - Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。
本手法の様々な応用は, 微分問題を解く文脈で論じる。
論文 参考訳（メタデータ） (2026-02-11T07:24:33Z) - Machine learning modularity [6.316250090403085]
この研究は、複数の楕円ガンマ関数を含む複雑な表現を自動的に単純化する機械学習フレームワークを導入する。
このモデルは代数的恒等式、特にSL$(2,mathbbZ)$とSL$(2,mathbbZ)$モジュラー変換を適用して、強スクランブル表現を標準形式に還元する。
論文 参考訳（メタデータ） (2026-01-05T04:17:55Z) - A discrete Fourier transform based quantum circuit for modular multiplication in Shor's algorithm [0.0]
モジュラー指数化のための量子回路を提案する。
我々の提案のゲート複雑度は$O(L3)$であり、ここで L は分解される数を保存するのに必要なビット数である。
論文 参考訳（メタデータ） (2025-03-13T03:39:13Z) - Towards Empirical Interpretation of Internal Circuits and Properties in Grokked Transformers on Modular Polynomials [29.09237503747052]
モジュラー加算のグロキングは、変換器の三角形状のフーリエ表現とその計算回路を実装することが知られている。
各操作でグラクされたモデル間の転送性は、特定の組み合わせに限られることを示す。
マルチタスクの混合によってコグルーキングが発生し、すべてのタスクで同時にグルーキングが発生する。
論文 参考訳（メタデータ） (2024-02-26T16:48:12Z) - Sampled Transformer for Point Sets [80.66097006145999]
スパース変換器は、連続列列列関数の普遍近似器でありながら、自己アテンション層の計算複雑性を$O(n)$に下げることができる。
我々は、追加の帰納バイアスを伴わずに点集合要素を直接処理できる$O(n)$複雑性サンプリング変換器を提案する。
論文 参考訳（メタデータ） (2023-02-28T06:38:05Z) - Transform Once: Efficient Operator Learning in Frequency Domain [69.74509540521397]
本研究では、周波数領域の構造を利用して、空間や時間における長距離相関を効率的に学習するために設計されたディープニューラルネットワークについて検討する。
この研究は、単一変換による周波数領域学習のための青写真を導入している。
論文 参考訳（メタデータ） (2022-11-26T01:56:05Z) - Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
フーリエスパース集合関数を学習するための新しいアルゴリズム群を提案する。
Walsh-Hadamard変換に焦点をあてた他の研究とは対照的に、我々の新しいアルゴリズムは最近導入された非直交フーリエ変換で機能する。
いくつかの実世界のアプリケーションで有効性を示す。
論文 参考訳（メタデータ） (2020-10-01T14:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。