Transformer-based language models are trained on large datasets to predict
the next token given an input sequence. Despite this simple training objective,
they have led to revolutionary advances in natural language processing.
Underlying this success is the self-attention mechanism. In this work, we ask:
$\textit{What}$ $\textit{does}$ $\textit{a}$ $\textit{single}$
$\textit{self-attention}$ $\textit{layer}$ $\textit{learn}$ $\textit{from}$
$\textit{next-token}$ $\textit{prediction?}$ We show that training
self-attention with gradient descent learns an automaton which generates the
next token in two distinct steps: $\textbf{(1)}$ $\textbf{Hard}$
$\textbf{retrieval:}$ Given input sequence, self-attention precisely selects
the $\textit{high-priority}$ $\textit{input}$ $\textit{tokens}$ associated with
the last input token. $\textbf{(2)}$ $\textbf{Soft}$ $\textbf{composition:}$ It
then creates a convex combination of the high-priority tokens from which the
next token can be sampled. Under suitable conditions, we rigorously
characterize these mechanics through a directed graph over tokens extracted
from the training data. We prove that gradient descent implicitly discovers the
strongly-connected components (SCC) of this graph and self-attention learns to
retrieve the tokens that belong to the highest-priority SCC available in the
context window. Our theory relies on decomposing the model weights into a
directional component and a finite component that correspond to hard retrieval
and soft composition steps respectively. This also formalizes a related
implicit bias formula conjectured in [Tarzanagh et al. 2023]. We hope that
these findings shed light on how self-attention processes sequential data and
pave the path toward demystifying more complex architectures.

自我注意力机制通过梯度下降训练能够学习自动生成下一个标记符号的自动机，其中学习步骤分为硬检索和软组合，梯度下降隐式地发现强连接组件并选择高优先级组件，以加工序列数据。

自注意力机制下的下一个标记预测机制

Mechanics of Next Token Prediction with Self-Attention

Transformer, as a strong and flexible architecture for modelling long-range
relations, has been widely explored in vision tasks. However, when used in
video inpainting that requires fine-grained representation, existed method
still suffers from yielding blurry edges in detail due to the hard patch
splitting. Here we aim to tackle this problem by proposing FuseFormer, a
Transformer model designed for video inpainting via fine-grained feature fusion
based on novel Soft Split and Soft Composition operations. The soft split
divides feature map into many patches with given overlapping interval. On the
contrary, the soft composition operates by stitching different patches into a
whole feature map where pixels in overlapping regions are summed up. These two
modules are first used in tokenization before Transformer layers and
de-tokenization after Transformer layers, for effective mapping between tokens
and features. Therefore, sub-patch level information interaction is enabled for
more effective feature propagation between neighboring patches, resulting in
synthesizing vivid content for hole regions in videos. Moreover, in FuseFormer,
we elaborately insert the soft composition and soft split into the feed-forward
network, enabling the 1D linear layers to have the capability of modelling 2D
structure. And, the sub-patch level feature fusion ability is further enhanced.
In both quantitative and qualitative evaluations, our proposed FuseFormer
surpasses state-of-the-art methods. We also conduct detailed analysis to
examine its superiority.

FuseFormer 是一种针对视频修复任务的 Transformer 模型，通过使用细粒度特征融合的新型软分割和软组合操作，实现了更加有效的特征传播和内容合成，优于现有技术方法。