path>/home/runner/work/LINMA2472/LINMA2472/Lectures/transformers.jlcell_results t$3d8add97-59e1-444a-838b-85c2a2ac60b3running§runtime4depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$3d8add97-59e1-444a-838b-85c2a2ac60b3depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ)Nbhas_pluto_hook_features¤bodyCross-Attention between
values and keys $E(CX + P)$ where $E$ is the encoder, and $X$ is the matrix of input tokens
query $Q$ depending on past output $Y$ and number of layers already applied
$$\text{MultiHead}(E(CX + P), E(CX + P), Q)$$
The embedding vectors $CX$ take then different projections for value, key, query and also for different heads!
$$\begin{multline}
\text{head}_j = \text{Attention}(W_j^VV, W_j^KK, W_j^QQ)\\
\text{where } V = K = E(CX + P)
\end{multline}$$
Residual connection
persist_js_state$6622f9f0-cecc-476e-9d49-7d651f433b9frunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6622f9f0-cecc-476e-9d49-7d651f433b9fdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ- has_pluto_hook_features¤bodyb
persist_js_state$70f395b2-f8c2-44d5-b0af-702659dd7feerunning§runtime69depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$70f395b2-f8c2-44d5-b0af-702659dd7feedepends_on_disabled_cells¦queued¤logsoutputmime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampAڪ`has_pluto_hook_features¤bodyprefixInt64objectidc8c9dd3b74dbd892typeArrayprefix_shortelements1text/plain1text/plainpersist_js_state$771d39a5-74dc-494e-929e-1164bb08b983running§runtime΄=ڸdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$771d39a5-74dc-494e-929e-1164bb08b983depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ
has_pluto_hook_features¤body hName Ref $n_\text{voc}$ $n_\text{ctx}$ Tokenizer GPT-2 [RWCL19] 50k 1024 tiktoken GPT-3 [BMRS20] 50k 2048 tiktoken GPT-3.5 100k 4096 tiktoken GPT-4 100k 32k tiktoken GPT-4o 200k 128k tiktoken Gemini-1 [TABA24] 256k 10M SentencePiece Gemini-1.5 [TGLB24] 256k 10M SentencePiece Gemma [TMHD24] 256k 8192 SentencePiece Gemma-2 [TRPS24] 256k 8192 SentencePiece Llama-2 [TMSA23] 32k 4k SentencePiece Llama-3 128k 8k tiktoken Llama-3.1 128k 128k tiktoken Llama-3.2 128k 128k tiktoken MegaByte [YSFA23] 256 8192 Bytes
[IS15] S. Ioffe and C. Szegedy. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift Mar 2015 ), arXiv:1502.03167 . Accessed on Nov 12, 2024.
Layer Normalization Jul 2016 ), arXiv:1607.06450 . Accessed on Nov 12, 2024.
et al. Attention Is All You Need Advances in Neural Information Processing Systems , Vol. 30 (Curran Associates, Inc., 2017). Accessed on Oct 11, 2024.
persist_js_state$61dc1905-338f-4bfd-a158-2f6bacff769erunning§runtimer> Ǹdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$61dc1905-338f-4bfd-a158-2f6bacff769edepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪhas_pluto_hook_features¤body<
[GBC16] I. Goodfellow, Y. Bengio and A. Courville. Deep Learning et al. Attention Is All You Need Advances in Neural Information Processing Systems , Vol. 30 (Curran Associates, Inc., 2017). Accessed on Oct 11, 2024.
persist_js_state$eb18303f-3dfb-4b87-90f2-f6dc542d7221running§runtime ;sdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$eb18303f-3dfb-4b87-90f2-f6dc542d7221depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ has_pluto_hook_features¤body
[PW17] O. Press and L. Wolf. Using the Output Embedding to Improve Language Models Feb 2017 ), arXiv:1608.05859 . Accessed on Nov 11, 2024.
et al. Attention Is All You Need Advances in Neural Information Processing Systems , Vol. 30 (Curran Associates, Inc., 2017). Accessed on Oct 11, 2024.
persist_js_state$76e2f97b-1c06-40cd-b134-d5155aa5587drunning§runtime vdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$76e2f97b-1c06-40cd-b134-d5155aa5587ddepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪhas_pluto_hook_features¤body~
[BDV00] Y. Bengio, R. Ducharme and P. Vincent. A Neural Probabilistic Language Model Advances in Neural Information Processing Systems , Vol. 13 (MIT Press, 2000). Accessed on Oct 11, 2024.
persist_js_state$f6f7376e-9984-4289-b8ff-9d47e5358791running§runtimewdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f6f7376e-9984-4289-b8ff-9d47e5358791depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAڪL÷has_pluto_hook_features¤bodypersist_js_state$b1a924f4-e2f0-445c-830f-94287a0e52f7running§runtime jdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$b1a924f4-e2f0-445c-830f-94287a0e52f7depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAڪhhas_pluto_hook_features¤body1numerical_lookup (generic function with 1 method)persist_js_state$f2cba2aa-c541-4692-a441-e65741750a15running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f2cba2aa-c541-4692-a441-e65741750a15depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ/Qhas_pluto_hook_features¤bodyR
Layer normalization
persist_js_state$6fc13413-53de-4c75-9b9e-620e0b7f8a1frunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6fc13413-53de-4c75-9b9e-620e0b7f8a1fdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ*4has_pluto_hook_features¤body&Is $W^O$ needed if $h = 1$ ? No, if $h = 1$ , we can merge $W^OW_1^V$ into a new $W_1^V$ .
Text to vectors : step 1 → tokenization
persist_js_state$5b4a67a9-e33e-4dc6-b9f0-fd9a2cca6f2arunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$5b4a67a9-e33e-4dc6-b9f0-fd9a2cca6f2adepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ#has_pluto_hook_features¤bodyI
[MKB+10] T. Mikolov, M. Karafiát, L. Burget et al. Recurrent Neural Network Based Language Model Proc. Interspeech 2010 Deep Learning
persist_js_state$86101f07-67c5-4df2-911c-4013c44d6c5brunning§runtime egdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$86101f07-67c5-4df2-911c-4013c44d6c5bdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪEhas_pluto_hook_features¤bodyAttention head provides a differentiable numerical dictionary [BCB16]
$$\begin{align}
\alpha
& =
\text{softmax}(\langle q, k_1 \rangle, \ldots, \langle q, k_{n_\text{ctx}}\rangle)
&
\text{Attention}(q, k, v)
& =
\sum_{i=1}^{n_\text{ctx}} \alpha_i v_i
\end{align}$$
Self-Attention
persist_js_state$6800afbf-8ac6-4308-b4cc-b37da57e42c1running§runtime ߸depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6800afbf-8ac6-4308-b4cc-b37da57e42c1depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ. has_pluto_hook_features¤body^
Attention is all you need
persist_js_state$18c26901-85eb-45ac-89bf-b03bd255007arunning§runtimeCedepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$18c26901-85eb-45ac-89bf-b03bd255007adepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪkhas_pluto_hook_features¤body ^Residual connection [HZRS15]
What would a numerical dictionary look like ? Consider keys $k_i \in \mathbb{R}^{d_k}$ and values $v_i \in \mathbb{R}^{d_v}$ . Given a query $q \in \mathbb{R}^{d_k}$ ,
Recurrent neural networks (RNN)
persist_js_state$c1437dcc-22cb-424f-9b8e-326172f82d86running§runtime 甸depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$c1437dcc-22cb-424f-9b8e-326172f82d86depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪL·has_pluto_hook_features¤bodyJpersist_js_state$c09ec483-9fcf-48e7-b3c0-2508289e3cf3running§runtime Vdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$c09ec483-9fcf-48e7-b3c0-2508289e3cf3depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪYhas_pluto_hook_features¤bodyV
Autoregressive Models
persist_js_state$1bbf2152-4fdf-4ed2-9bdf-95d699824d11running§runtime zƸdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$1bbf2152-4fdf-4ed2-9bdf-95d699824d11depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ+)Jhas_pluto_hook_features¤bodyWhy not encode each letter ?
Idea : Turn each letter into its one-hot encoding in $\mathbb{R}^{26}$ .
Issue : The "past text" only has $n_\text{ctx}$ characters so $n_\text{ctx}$ must be large but transformers have a complexity quadratic in $n_\text{ctx}$ !
Practical details : Text is encoded with UTF-8 so each character is encoded into 1 to 4 bytes. We encode each byte to a vector in $\mathbb{R}^{256}$ but care must be taken not to generate invalid UTF-8.
Why not encode each word ?
Language French English Dutch German $n$ 408,078 350,000 350,000 200,000
Feed-Forward network
persist_js_state$6aa690e9-389f-4398-abae-b95060db4d90running§runtime Ҹdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6aa690e9-389f-4398-abae-b95060db4d90depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ-Ahas_pluto_hook_features¤bodyL
Shared embedding
persist_js_state$4b61363d-87c9-4755-8286-44df34e9dd6arunning§runtime 44depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$4b61363d-87c9-4755-8286-44df34e9dd6adepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ+/has_pluto_hook_features¤bodyIs the order between the tokens taken into account by the model ? No. Since the same matrices $W_j^V$ , $W_j^K$ and $W_j^Q$ multiply the different position. The position information is completely lost !
Numerical dictionary
persist_js_state$225e58ba-b78d-4a0a-be4f-ad642c879b93running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$225e58ba-b78d-4a0a-be4f-ad642c879b93depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪEhas_pluto_hook_features¤bodyIt's difficult to model long-term dependencies as their gradient either vanish or explodes exponentially (think of the power method) [GBC16; Section 10.7]
Gated extensions attempting to solve this issue [GBC16; Section 10.10]:
Why don't we use $D = C^{-1}$ ? The $C$ matrix is not invertible as it is not square. Given a vector $u$ , the vector $v = Du$ could be computed to be the mininum norm solution of $u = Cv$ , this is what is done by v = D \ u. Computing D \ u would be more computational work than D' \ u but that's not the only reason D' is used. If $v$ is chosen so that $u = Cv$ , it means that $v$ is a linear combination allowing to reconstruct $u$ using the columns of $C$ . From that perspective, $v_i$ could be nonzero even though the direction of the vector $u$ us far from the direction of the column $C_{:i}$ . That does not correspond to what we want to do here.
Here, we want a probability vector $p$ with high probability $p_i$ when the direction of the column $C_{:i}$ is close to the direction of $u$ . In the vector $v = C^\top u$ , $v_i = \langle C_{:i}, u \rangle$ is the scalar product between the $i$ th column of $C$ and $u$ hence it is a good measure of how close the direction are to each other. Of course this assumes that the column of $C$ have the same norm, but the hope is for the model to figure in training that the columns of $C$ should have unit norm. We can then simply apply softmax to turn these scalar products into probabilities $p = \text{softmax}(v)$ .
$$\text{Masked-Attention}(V, K, Q)\
=
V\text{softmax}(M + K^\top Q/\sqrt{d_k})$$
Cannot sum $Cx_i + e_i$ with one-hot encoding $e_i \in \mathbb{R}^{n_\text{ctx}}$ as the dimension of $Cx_i$ is $\mathbb{R}^{d_\text{emb}}$ .
So we also add a positional embedding $P$ : $Cx_i + Pe_i = Cx_i + p_i$ .
With Self-Attention:
$$\text{Self-MultiHead}(CX + P, CX + P, CX + P)$$
Increasing length of "past text"
persist_js_state$6bff7bca-ea1d-44c6-b8c3-040250f90654running§runtime udepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$6bff7bca-ea1d-44c6-b8c3-040250f90654depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ08has_pluto_hook_features¤bodyJ
Cross-Attention
persist_js_state$c4bebd0d-eacf-4db4-b5b3-4dca50ab9e1brunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$c4bebd0d-eacf-4db4-b5b3-4dca50ab9e1bdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ~ŷhas_pluto_hook_features¤bodyWhat are the number of columns of $W_1$ and number of rows of $W_2$ now ? The matrix $W_1$ has $n_\text{ctx}d_\text{emb}$ columns. Assuming $d_\text{emb} \ll n_\text{voc}$ and $n_\text{ctx} \gg 1$ , this is much smaller than the number $n_\text{ctx}n_\text{voc}$ that we would have without the embedding. The number of rows of $W_2$ is $n_\text{voc}$ , unaffected by the embedding.
Multi-Head Attention
persist_js_state$a873f760-bfc1-489f-a58e-75e12afa54f2running§runtime q[depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a873f760-bfc1-489f-a58e-75e12afa54f2depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAڪorhas_pluto_hook_features¤body*highlight (generic function with 1 method)persist_js_state$76ba4e9b-8bb0-47c4-b607-2ca711f035e6running§runtime 3depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$76ba4e9b-8bb0-47c4-b607-2ca711f035e6depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ.has_pluto_hook_features¤bodyL
Masked Attention
persist_js_state$a5b20939-9afa-48c0-aa67-cbca6bc99804running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$a5b20939-9afa-48c0-aa67-cbca6bc99804depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ/Rhas_pluto_hook_features¤bodyD
Cost of LLMs
persist_js_state$91abc03b-fef7-4f93-96fc-13f1cf654f0drunning§runtimefոdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$91abc03b-fef7-4f93-96fc-13f1cf654f0ddepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪhas_pluto_hook_features¤bodygSee the table below for the size of embeddings of large language models:
Name Num params Ref $n_\text{voc}$ $d_\text{emb}$ GPT-2 1.5B [RWCL19] 50k 768 Gemma 2B [TMHD24] 256k 2048 Gemma 7B [TMHD24] 256k 3072 Gemma-2 27B [TRPS24] 256k 4608 Gemma-2 2B [TRPS24] 256k 2304 Gemma-2 9B [TRPS24] 256k 3584 Llama-2 7B [TMSA23] 32k 4096 base [VSPU17] 37k 512 big [VSPU17] 37k 1024
persist_js_state$beccf4e8-1b01-4cb2-b23c-bc5db604f21crunning§runtime
~depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$beccf4e8-1b01-4cb2-b23c-bc5db604f21cdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ$·has_pluto_hook_features¤bodyGiven a sequence of $n_\text{ctx}$ past vectors $x_{-1}, \ldots, x_{-n_\text{ctx}} \in \mathbb{R}^{n}$ , "predict" the next ones. Key idea : receding horizon :
$$\begin{align}
& p(x_0, x_1 | x_{-1}, \ldots, x_{-n_\text{ctx}})\\
& = p(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})p(x_1 | x_0, x_{-1}, \ldots, x_{-n_\text{ctx}+1}, \textcolor{red}{x_{-n_\text{ctx}}})\\
& \approx p(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}}) p(x_{1} | x_0, x_{-1}, \ldots, x_{-n_\text{ctx}+1})
\end{align}$$
Model : Probability of next vector $\hat{p}(x_0 | X)$ where $X$ concatenates $x_{-1}, \ldots, x_{-n_\text{ctx}}$ .
Loss : Cross-entropy : $\mathcal{L}_{\hat{p}}(X) \triangleq H(p, \hat{p}) = -\textbf{E}_p[\log(\hat{p})] = -\sum_{x_0} p(x_0 | X) \log(\hat{p}(x_0 | X))$
Particular case for $p(x_0 | X) = \delta_y$ : $\mathcal{L}_{\hat{p}}(X) = -\log(\hat{p}(y | X))$
What about Language Models ?
Given "past text", predict the "following text". How to turn text into vectors of $\mathbb{R}^n$ ?
[BCB16] D. Bahdanau, K. Cho and Y. Bengio. Neural Machine Translation by Jointly Learning to Align and Translate May 2016 ), arXiv:1409.0473 . Accessed on Oct 23, 2024.
persist_js_state$5058e4eb-c53d-4468-b7ff-4f04ded96418running§runtime'depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$5058e4eb-c53d-4468-b7ff-4f04ded96418depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ>has_pluto_hook_features¤bodyV@Transformers in Large Language Models (LLMs)
Benoît Legat
Full Width Mode
Present Mode
persist_js_state$5150d8f3-6e85-43f2-801a-eae5cc3e3095running§runtime ኸdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$5150d8f3-6e85-43f2-801a-eae5cc3e3095depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪF8Chas_pluto_hook_features¤bodysoftmax is then applied to each column :
$$\text{softmax}(K^\top Q/\sqrt{d_k})$$
Division by $\sqrt{d_k}$ scales the input of softmax to preferable regions [VSP+17; Secton 3.2.1].
Illustrated on the right from [BCB16; Figure 3(a)].
$$\text{Attention}(V, K, Q) = V\text{softmax}(K^\top Q/\sqrt{d_k})$$
💡 Key idea In the model for $\hat{p}(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})$ , incorporate sub-models
$$\begin{align}
\bar{p}(&x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})\\
\bar{p}(&x_{-1} | x_{-2}, \ldots, x_{-n_\text{ctx}})\\
& \quad\qquad\vdots\\
\bar{p}(&x_{-n_\text{ctx}+1} | x_{-n_\text{ctx}}).
\end{align}$$
Mask prevents $\hat{p}$ to look at inputs in the future:
$$M
=
\begin{bmatrix}
0 & 0 & \cdots & 0\\
-\infty & 0 & \ddots & \vdots\\
\vdots & \ddots & \ddots & 0\\
-\infty & \cdots & -\infty & 0
\end{bmatrix}$$
Let $\hat{Y}_{i}$ be the intermediate output of $i \in \{1, \ldots, N\}$ . The columns of the matrix $\text{softmax}(C^\top \hat{Y}_i)$ (column-wise softmax) can be thought as intermediate probabilities that we denote $\hat{p}_i$ :
$$(\hat{p}_i(x_{-n_\text{ctx}+1} | x_{-n_\text{ctx}}), \ldots, \hat{p}_i(x_{-1} | x_{-2}, \ldots, x_{-n_\text{ctx}}), \hat{p}_i(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}}))$$
and we predict the next token using $\hat{p}_N(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})$ .
[SVL14] I. Sutskever, O. Vinyals and Q. V. Le. Sequence to Sequence Learning with Neural Networks Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2 , NIPS'14 (MIT Press, Cambridge, MA, USA, Dec 2014); pp. 3104–3112. Accessed on Oct 23, 2024.
persist_js_state$c7f318b9-30e6-4b79-b7da-52f70904d246running§runtime
[HZRS16] K. He, X. Zhang, S. Ren and J. Sun. Identity Mappings in Deep Residual Networks Computer Vision – ECCV 2016 , edited by B. Leibe, J. Matas, N. Sebe and M. Welling (Springer International Publishing, Cham, 2016); pp. 630–645.
et al. Language Models Are Unsupervised Multitask Learners et al. RoFormer: Enhanced Transformer with Rotary Position Embedding Nov 2023 ), arXiv:2104.09864 . Accessed on Nov 12, 2024.
Large Language Models (LLMs)
persist_js_state$77f446ac-6030-48f2-9bea-93c427f9fcb9running§runtime.=depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$77f446ac-6030-48f2-9bea-93c427f9fcb9depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAڪ}has_pluto_hook_features¤body/softmax_lookup (generic function with 1 method)persist_js_state$d05e6f0f-0081-4fb6-91e9-ac2f58beda4arunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$d05e6f0f-0081-4fb6-91e9-ac2f58beda4adepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ.(has_pluto_hook_features¤body\
persist_js_state$d54b5390-0ec0-4ff8-ab18-51726482ca46running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$d54b5390-0ec0-4ff8-ab18-51726482ca46depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ-has_pluto_hook_features¤bodyP
Extensions of RNNs
persist_js_state$f572e113-b36b-4a6b-96c7-c26f100e1ad4running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f572e113-b36b-4a6b-96c7-c26f100e1ad4depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ0Qhas_pluto_hook_features¤body6
Utils
persist_js_state$c3db7eb2-356a-428f-9777-6369662d8b06running§runtime Idepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$c3db7eb2-356a-428f-9777-6369662d8b06depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ+b,has_pluto_hook_features¤bodymNote that the new tokens can also be part of the most frequence pair!
Recently, Mamba suggests a solution to the complexity issue [GD24]. As it scales better with $n_\text{ctx}$ , it is even suggested to get rid of the tokenizer : [WGYR24].
Consider one-hot encoding with vocabulary size $n_\text{voc}$ and a bigram model
$$\hat{p}(x_0 | x_{-1}) = \text{softmax}(W_d \tanh(\cdots\tanh(W_1 x_{-1})\cdots)$$
The matrix $W_d$ has $n_\text{voc}$ rows and $W_1$ has $n_\text{voc}$ columns → issue if $n_\text{voc}$ is large
Embedding : Use vectors $c_1, \ldots, c_{n_\text{voc}} \in \mathbb{R}^{d_\text{emb}}$ with embedding size (aka hidden size ) $d_\text{emb} \ll n_\text{voc}$ .
Equivalently, we still use one-hot encoding but we add an encoder $C \in \mathbb{R}^{d_\text{emb} \times n_\text{voc}}$ and decoder $D \in \mathbb{R}^{n_\text{voc} \times d_\text{emb}}$
$$\hat{p}(x_0 | x_{-1}) = \text{softmax}(D W_d \tanh(\cdots\tanh(W_1 C x_{-1})\cdots)$$
[TGL+24] G. Team, P. Georgiev, V. I. Lei et al. Gemini 1.5: Unlocking Multimodal Understanding across Millions of Tokens of Context Aug 2024 ), arXiv:2403.05530 . Accessed on Nov 11, 2024.
et al. Gemini: A Family of Highly Capable Multimodal Models Jun 2024 ), arXiv:2312.11805 . Accessed on Nov 11, 2024.
et al. Gemma: Open Models Based on Gemini Research and Technology Apr 2024 ), arXiv:2403.08295 . Accessed on Nov 11, 2024.
et al. Gemma 2: Improving Open Language Models at a Practical Size Oct 2024 ), arXiv:2408.00118 . Accessed on Nov 11, 2024.
Neural Machine Translation of Rare Words with Subword Units Jun 2016 ), arXiv:1508.07909 . Accessed on Oct 23, 2024.
et al. Language Models Are Unsupervised Multitask Learners et al. Language Models Are Few-Shot Learners Jul 2020 ), arXiv:2005.14165 . Accessed on Nov 11, 2024.
et al. Llama 2: Open Foundation and Fine-Tuned Chat Models Jul 2023 ), arXiv:2307.09288 . Accessed on Oct 23, 2024.
et al. MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers May 2023 ), arXiv:2305.07185 . Accessed on Oct 23, 2024.
persist_js_state$8eafcfed-9771-4d99-b0c5-bd75a6dab012running§runtime Ÿdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$8eafcfed-9771-4d99-b0c5-bd75a6dab012depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪhas_pluto_hook_features¤body
[CvMBB14] K. Cho, B. van Merrienboer, D. Bahdanau and Y. Bengio. On the Properties of Neural Machine Translation: Encoder-Decoder Approaches Oct 2014 ), arXiv:1409.1259 . Accessed on Nov 11, 2024.
Generating Sequences With Recurrent Neural Networks Jun 2014 ), arXiv:1308.0850 . Accessed on Nov 11, 2024.
Deep Learning Mamba: Linear-Time Sequence Modeling with Selective State Spaces May 2024 ), arXiv:2312.00752 . Accessed on Nov 11, 2024.
MambaByte: Token-free Selective State Space Model Aug 2024 ), arXiv:2401.13660 . Accessed on Nov 11, 2024.
persist_js_state$89305cae-098f-4644-9109-d00f1e3bc04crunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$89305cae-098f-4644-9109-d00f1e3bc04cdepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAڪ
has_pluto_hook_features¤body+pair_stats (generic function with 1 method)persist_js_state$bcf7667f-f99b-4d10-af84-5d3879f1db5drunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$bcf7667f-f99b-4d10-af84-5d3879f1db5ddepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ7has_pluto_hook_features¤bodyWhat difference do you expect with respect to the previous model ? The products $W_1C$ and $DW_d$ have the same dimension as the matrices $W_1$ and $W_d$ of the previous model. So the expressive power of the model was not improved while we increased the number of parameters and we potentially made the loss function "even more nonconvex".
If the hidden dimension (i.e., the number of rows of $C$ / columns of $W_1$ or the number of rows of $W_d$ / columns of $D$ ) is much smaller than $n_\text{voc}$ , then it's faster to compute $W_1(Cx)$ . Moreover, we are forcing the matrix $W_1C$ to have a low rank compared the model without $C$ . This means less expressivness but it might also prevent overfitting so the case isn't so clear.
The case become clearer when the input embedding $C$ is shared between more than one character, i.e., $n_\text{ctx} > 1$ . Same for the output embedding, $D$ is useful when it is not preceded by a linear with which it can just be merged.
How does the number of parameters of transformers compare with [BDV00] or RNNs for large $n_\text{ctx}$ ?
The number of parameters of the transformer does not depend on $n_\text{ctx}$ .
The number of parameters of [BDV00] depends linearly with $n_\text{ctx}$ . Assuming that the number of hidden neurons scales proportionally with $n_\text{ctx}$ , the number of parameters even scales quadratically with $n_\text{ctx}$ !
For RNNs, if the dimension of the internal state scales proportionally with $n_\text{ctx}$ , the number of parameters is also proportional with $n_\text{ctx}$ ! If the dimension of the internal state is kept too small, increasing the context won't be so helpful, due to encoder bottleneck , see next slide.
[BCB16] D. Bahdanau, K. Cho and Y. Bengio. Neural Machine Translation by Jointly Learning to Align and Translate May 2016 ), arXiv:1409.0473 . Accessed on Oct 23, 2024.
et al. Attention Is All You Need Advances in Neural Information Processing Systems , Vol. 30 (Curran Associates, Inc., 2017). Accessed on Oct 11, 2024.
persist_js_state$45efc71d-d5f8-474e-9b89-e72fac7110fdrunning§runtime sdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$45efc71d-d5f8-474e-9b89-e72fac7110fddepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪhas_pluto_hook_features¤bodyx
[BDV00] Y. Bengio, R. Ducharme and P. Vincent. A Neural Probabilistic Language Model Advances in Neural Information Processing Systems , Vol. 13 (MIT Press, 2000). Accessed on Oct 11, 2024.
persist_js_state$d050a7ee-3aa7-4539-a236-5b6446599dedrunning§runtime 1depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$d050a7ee-3aa7-4539-a236-5b6446599deddepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAڪvhas_pluto_hook_features¤bodypersist_js_state$579a203b-e6f7-4190-b874-18b00a5c3f77running§runtime F depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$579a203b-e6f7-4190-b874-18b00a5c3f77depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAڪꃝhas_pluto_hook_features¤body*load_llms (generic function with 1 method)persist_js_state$570fa160-3adb-463e-99b8-b7dd05076908running§runtime |]depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$570fa160-3adb-463e-99b8-b7dd05076908depends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAڪټhas_pluto_hook_features¤body(softmax (generic function with 1 method)persist_js_state$9cb90e76-3bb5-41ff-bc79-c4949400d904running§runtime |depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$9cb90e76-3bb5-41ff-bc79-c4949400d904depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ6has_pluto_hook_features¤body)With $n_\text{ctx} > 1$ , the encoder $C$ is shared by all tokens: See for instance the network below taken from [BDV00; Figure 1], the first popular application of neural nets for languages:
[TMH+24] G. Team, T. Mesnard, C. Hardin et al. Gemma: Open Models Based on Gemini Research and Technology Apr 2024 ), arXiv:2403.08295 . Accessed on Nov 11, 2024.
et al. Gemma 2: Improving Open Language Models at a Practical Size Oct 2024 ), arXiv:2408.00118 . Accessed on Nov 11, 2024.
et al. Language Models Are Unsupervised Multitask Learners et al. Llama 2: Open Foundation and Fine-Tuned Chat Models Jul 2023 ), arXiv:2307.09288 . Accessed on Oct 23, 2024.
persist_js_state$b9caae1a-38aa-4d01-9cda-3d6782fb0e03running§runtime2Bhdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$b9caae1a-38aa-4d01-9cda-3d6782fb0e03depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪv5has_pluto_hook_features¤bodySelf-Attention with embedding $C$ is:
$$\text{Masked-MultiHead}(CX, CX, CX)$$
The embedding vectors $CX$ take then different projections for value, key, query and also for different heads!
$$\text{head}_j = \text{Masked-Attention}(W_j^VCX, W_j^KCX, W_j^QCX)$$
$$\begin{align}
Q & = \begin{bmatrix}
q_1 & \cdots & q_{n_\text{ctx}}
\end{bmatrix} &
K & = \begin{bmatrix}
k_1 & \cdots & k_{n_\text{ctx}}
\end{bmatrix} &
K^\top Q & =
\begin{bmatrix}
\langle k_1, q_1 \rangle & \cdots & \langle k_1, q_{n_\text{ctx}} \rangle\\
\vdots & \ddots & \vdots\\
\langle k_{n_\text{ctx}}, q_1 \rangle & \cdots & \langle k_{n_\text{ctx}}, q_{n_\text{ctx}} \rangle
\end{bmatrix}
\end{align}$$
Different weights $W_1 \in \mathbb{R}^{d_\text{ff} \times d_\text{emb}}$ , $W_2 \in \mathbb{R}^{d_\text{emb} \times d_\text{ff}}$ for each layer:
$$x \mapsto W_2\max(0, W_1x + b_1) + b_2$$
Expansion factor $d_\text{ff} / d_\text{emb}$ is typically 4× like suggested in [VSP+17] (but not for Gemma)
Name Ref $d_\text{emb}$ $d_\text{ff}$ GPT-2 [RWCL19] 768 3072 Gemma [TMHD24] 2048 32768 Gemma [TMHD24] 3072 49152 Gemma-2 [TRPS24] 2304 18432 Gemma-2 [TRPS24] 3584 28672 Gemma-2 [TRPS24] 4608 73728 Llama-3 4096 base [VSPU17] 512 2048 big [VSPU17] 1024 4096
Challenging tradeoff : Encode text to increase length of "past text" while keeping $n_\text{ctx}$ and $n$ small enough.
Length of "past text" increases with vocabulary size $n_\text{voc}$ and context window $n_\text{ctx}$ .
$$\begin{align}
h^{(t+1)} & = \tanh(Wh^{(t)} + Ux^{(t+1)} + b)\\
o^{(t)} &= Vh^{(t)} + c\\
\hat{y}^{(t)} &= \text{softmax}(o^{(t)})
\end{align}$$
Illustrated on the right [GBC16; Figure 10.3].
RNNs as language model showcased in [MKB+10].
Issue : Training time and space complexity is proportional to $n_\text{ctx}$ and cannot parallelize to speed up.
Attention head
persist_js_state$f1afaf8c-d9ad-446a-9826-9c4cda19993frunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f1afaf8c-d9ad-446a-9826-9c4cda19993fdepends_on_disabled_cells¦queued¤logsoutputmimetext/plainrootassigneelast_run_timestampAڪhas_pluto_hook_features¤body*new_token (generic function with 1 method)persist_js_state$f7ca3ff7-b5cf-452b-b955-7219e7397324running§runtimeNpdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f7ca3ff7-b5cf-452b-b955-7219e7397324depends_on_disabled_cells¦queued¤logsoutputmime!application/vnd.pluto.tree+objectrootassigneeiter_1last_run_timestampAڪ+зhas_pluto_hook_features¤bodyprefixBPEobjectid189eeaf27bd5f4b8typestructprefix_shortBPEelementstext"ZabdZabac"text/plainpairsprefixDict{Tuple{Char, Char}, Char}objectiddf935a2cecbf0298typeDictprefix_shortDictelementsobjectidfb8c8201152e6a3atypeTupleelements'a'text/plain'a'text/plain!application/vnd.pluto.tree+object'Z'text/plain!application/vnd.pluto.tree+objectpersist_js_state$5f05e717-a51a-4a99-bb11-cc493217f93frunning§runtime[wdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$5f05e717-a51a-4a99-bb11-cc493217f93fdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ:dhas_pluto_hook_features¤body*Norm of gradient increases exponentially with depth. Issue for deep neural net. Consider output
$$\begin{bmatrix}
y_{1,1} & \ldots & y_{1,d_\text{emb}}\\
\vdots & \ddots & \vdots\\
y_{d_\text{batch},1} & \ldots & y_{d_\text{batch},d_\text{emb}}
\end{bmatrix}$$
Normalization : $y_{i,j} \mapsto g(y_{i,j} - \mu_{i,j})/\sigma_{i,j}$ for gain $g$ , mean $\mu$ and standard deviation $\sigma$ .
Batch normalization : $\sigma_{i,j} = \sigma_{j}$ [IS15]
Layer normalization : $\sigma_{i,j} = \sigma_{i}$ [BKH16]
Batch norm depends on the batch hence is tricky to implement . Layer normalization is used in [VSP+17].
[HZRS15] K. He, X. Zhang, S. Ren and J. Sun. Deep Residual Learning for Image Recognition Dec 2015 ), arXiv:1512.03385 . Accessed on Nov 12, 2024.
persist_js_state$57c2c944-0d91-489d-8ad7-f5520e71ef3erunning§runtime 4depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$57c2c944-0d91-489d-8ad7-f5520e71ef3edepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ+IIhas_pluto_hook_features¤bodyP
Byte Pair Encoding
persist_js_state$bf563783-9784-4c74-a7b1-6d7a3ed618c5running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$bf563783-9784-4c74-a7b1-6d7a3ed618c5depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ.ohas_pluto_hook_features¤body\
persist_js_state$f8330700-e964-4e19-9c55-2b11df45789erunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f8330700-e964-4e19-9c55-2b11df45789edepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ-ȷhas_pluto_hook_features¤bodyZ
Embedding sizes in LLMs
persist_js_state$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0ecrunning§runtime5udepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0ecdepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪf횷has_pluto_hook_features¤bodyWhat is the time complexity of inference with respect to $d_\text{emb}$ , $n_\text{voc}$ , $n_\text{ctx}$ , $d_\text{ff}$ , $h$ and $N$ ? Input Parameters Time $CX + P \in \mathbb{R}^{d_\text{emb} \times n_\text{ctx}}$ $W_j^V \in \mathbb{R}^{d_v \times d_\text{emb}}$ $O(d_v d_\text{emb} n_\text{ctx})$ $CX + P \in \mathbb{R}^{d_\text{emb} \times n_\text{ctx}}$ $W_j^K, W_j^Q \in \mathbb{R}^{d_k \times d_\text{emb}}$ $O(d_k d_\text{emb} n_\text{ctx})$ $K, Q \in \mathbb{R}^{d_k \times n_\text{ctx}}$ $O(d_k n_\text{ctx}^2)$ $V \in \mathbb{R}^{d_v \times n_\text{ctx}}, ... \in \mathbb{R}^{n_\text{ctx} \times n_\text{ctx}}$ $O(d_v n_\text{ctx}^2)$ $... \in \mathbb{R}^{d_v \times n_\text{ctx}}$ $W^O \in \mathbb{R}^{d_\text{emb} \times d_v}$ $O(d_\text{emb} d_v n_\text{ctx})$ $... \in \mathbb{R}^{d_\text{emb} \times n_\text{ctx}}$ $W_1 \in \mathbb{R}^{d_\text{ff} \times d_\text{emb}}$ $O(d_\text{emb} d_\text{ff} n_\text{ctx})$ $... \in \mathbb{R}^{d_\text{ff} \times n_\text{ctx}}$ $W_2 \in \mathbb{R}^{d_\text{emb} \times d_\text{ff}}$ $O(d_\text{emb} d_\text{ff} n_\text{ctx})$
So for $N$ layers (ignoring the complexity of the embedding):
$$O(Nn_\text{ctx}(n_\text{ctx}(d_v + d_k) + d_\text{emb}(d_v+d_k+d_\text{ff})))$$
Assuming that $d_v, d_k, d_\text{ff}$ has the same scale as $d_\text{emb}$ :
$$O(Nn_\text{ctx}^2d_\text{emb} + Nn_\text{ctx}d_\text{emb}^2)$$
Pre-activation for residual neural networks introduced in [HZRS16] and used in GPT-2 [RWC+19]. See figure on the right.
Rotary Positional Encoding [SLP+23] replaces $W^K(Cx_i + p_i)$ and $W^Q(Cx_i + p_i)$ by $R^i W^KCx_i$ and $R^i W^QCx_i$ where $R$ is a rotation matrix. Advantage : $\langle k_i, q_j \rangle$ contains $R^{i - j}$ → relative difference of position.
Key-Value (KV) cache
persist_js_state$2a7e5096-1e8d-4506-96d2-86de0a7d39aarunning§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$2a7e5096-1e8d-4506-96d2-86de0a7d39aadepends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ6YGhas_pluto_hook_features¤bodyٴForcing $D = C^\top$ appears to work well in practice [PW17], this is what is used in [VSP+17].
$$\begin{multline}
\hat{p}(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}}) = \\
\text{softmax}(W_2 \tanh(W_1
\begin{bmatrix}
C x_{-1}\\
\vdots\\
C x_{-n_\text{ctx}}
\end{bmatrix}
))
\end{multline}$$
The feed-forward network is implemented independently for the output of each query so each query can be processed independently through each layer . The next layer allows each queries to then look at the results of the previous layer for past (because of the mask) queries.
Machine translation
persist_js_state$d014e6aa-92f6-4ca1-be47-516565d1bb20running§runtime ETĸdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$d014e6aa-92f6-4ca1-be47-516565d1bb20depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪF4has_pluto_hook_features¤body 8Heads focus on different aspects. Their outputs are combined with $W^O \in \mathbb{R}^{d_\text{emb} \times hd_v}$ :
$$\begin{align}
\text{head}_j & = \text{Attention}(W_j^VV, W_j^KK, W_j^QQ)\\
\text{MultiHead}(V, K, Q)
& =
W^O\text{vcat}(\text{head}_1, \ldots, \text{head}_h)
\end{align}$$
See [VSP+17; Figure 2] on the right.
Similarly, in the masked case:
$$\begin{align}
\text{head}_j & = \text{Masked-Attention}(W_j^VV, W_j^KK, W_j^QQ)\\
\text{Masked-MultiHead}&(V, K, Q)
=
W^O\text{vcat}(\text{head}_1, \ldots, \text{head}_h)
\end{align}$$
[SHB16] R. Sennrich, B. Haddow and A. Birch. Neural Machine Translation of Rare Words with Subword Units Jun 2016 ), arXiv:1508.07909 . Accessed on Oct 23, 2024.
SentencePiece: A Simple and Language Independent Subword Tokenizer and Detokenizer for Neural Text Processing Aug 2018 ), arXiv:1808.06226 . Accessed on Oct 23, 2024.
persist_js_state$e2eca085-9f99-4e3a-9db4-e7f692aedd34running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$e2eca085-9f99-4e3a-9db4-e7f692aedd34depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ-\has_pluto_hook_features¤bodyx
Text to vectors : step 2 → embedding
persist_js_state$95504a74-d5ef-4fb7-83a0-88914c7cbc59running§runtimePositional encoding
persist_js_state$0583ee0c-3802-4e81-b179-a80a82493b43running§runtime 㮸depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$0583ee0c-3802-4e81-b179-a80a82493b43depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ6&)has_pluto_hook_features¤body@Byte Pair Encoding algorithm [SHB16] greedily merges the most frequent pair of tokens over the dataset into a new token. Most used implementations are SentencePiece [KR18] and tiktoken (play with it here ). For instance, on this example , the pair ('a', 'a') is the most frequent so we substitute it by a new token, say 'Z':
Should we discard all these intermediate $\hat{Y}_i$ we computated or can we reuse it for the following token ? For the next token, the corresponding intermediate probabilities would be:
$$(\hat{p}_i(x_{-n_\text{ctx}+2} | x_{-n_\text{ctx}+1}), \ldots, \hat{p}_i(x_{0} | x_{-1}, \ldots, x_{-n_\text{ctx}+1}), \hat{p}_i(x_1 | x_{0}, \ldots, x_{-n_\text{ctx}+1}))$$
Note that
$$\begin{align}
\hat{p}_i(x_{-n_\text{ctx}+2} | x_{-n_\text{ctx}+1})
& \approx
\hat{p}_i(x_{-n_\text{ctx}+2} | x_{-n_\text{ctx}+1}, x_{-n_\text{ctx}})\\
\hat{p}_i(x_{0} | x_{-1}, \ldots, x_{-n_\text{ctx}+1})
& \approx
\hat{p}_i(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})
\end{align}$$
So for any $j < n_\text{ctx}$ , the $j$ th column of the $\hat{Y}_i'$ that should be computed for the new token is approximately equal to the $(j+1)$ th column of $\hat{Y}_i$ that we already computed for the previous token. What's more, the column of $\hat{Y}_i$ was computed with one more token as context compared to what we need to compute in $\hat{Y}_i'$ . So even though it's not equal, reusing what we computed in $\hat{Y}_i$ should provide better result, assuming the trained transformers using this auto-regressive structure in his layers.
persist_js_state±published_objectsjulia_versionv1.13.0cell_dependencies t$3d8add97-59e1-444a-838b-85c2a2ac60b3precedence_heuristic cell_id$3d8add97-59e1-444a-838b-85c2a2ac60b3downstream_cells_mapupstream_cells_map Luxor.backgroundLaTeXStrings$32621224-a782-4bf6-9570-562cf2bb7360Luxor.originHTML@L_strHAlignhtml@drawLuxor.sethuetextLuxor.previewLuxor.DrawingBase.getindexhighlight$a873f760-bfc1-489f-a58e-75e12afa54f2Pointdraw_transformer$85a10748-8d19-44a8-a1c5-0d13b093f1bfLuxor.finishLaTeXStrings.latexstringBase@md_strfontsizeLuxor$32621224-a782-4bf6-9570-562cf2bb7360$92e01e21-ca77-43fc-9bf8-0c5a7aaed1bbprecedence_heuristic cell_id$92e01e21-ca77-43fc-9bf8-0c5a7aaed1bbdownstream_cells_mapupstream_cells_map@md_strgetindex$6622f9f0-cecc-476e-9d49-7d651f433b9fprecedence_heuristic cell_id$6622f9f0-cecc-476e-9d49-7d651f433b9fdownstream_cells_mapupstream_cells_map@md_strgetindex$70f395b2-f8c2-44d5-b0af-702659dd7feeprecedence_heuristic cell_id$70f395b2-f8c2-44d5-b0af-702659dd7feedownstream_cells_mapupstream_cells_mapdict$d558636d-c714-4033-ae73-5b92c3cdedf3$771d39a5-74dc-494e-929e-1164bb08b983precedence_heuristic cell_id$771d39a5-74dc-494e-929e-1164bb08b983downstream_cells_mapupstream_cells_mapllms$f39305ea-f7f5-440e-ac55-c83e27f6e7fctable$7e27c349-ee76-46bd-b1c2-a9ce54974e10$85a10748-8d19-44a8-a1c5-0d13b093f1bfprecedence_heuristic cell_id$85a10748-8d19-44a8-a1c5-0d13b093f1bfdownstream_cells_mapdraw_transformer$91abc03b-fef7-4f93-96fc-13f1cf654f0d$b9caae1a-38aa-4d01-9cda-3d6782fb0e03$c5be3956-5102-4d88-bfdb-9813c0555fe1$18c26901-85eb-45ac-89bf-b03bd255007a$5f05e717-a51a-4a99-bb11-cc493217f93f$f95a6de6-5e02-4237-88ba-ec44ef3d38c3$d1ba8da3-add8-4dbe-9ebf-9a32fa5cd5dd$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0ec$3d8add97-59e1-444a-838b-85c2a2ac60b3upstream_cells_mapscalesethuesetopacitytextreadpngPointLuxor.placeimageboxtranslatefontsizeLuxor$32621224-a782-4bf6-9570-562cf2bb7360$4f1d5112-dbac-4eb6-8518-0dc4193c3f8eprecedence_heuristic cell_id$4f1d5112-dbac-4eb6-8518-0dc4193c3f8edownstream_cells_mapbib$61dc1905-338f-4bfd-a158-2f6bacff769e$4df0a18d-cb14-41b1-ba40-fd6bfcbb0b03$97463c54-7cc7-4497-a8a6-6422f5f582bd$eb18303f-3dfb-4b87-90f2-f6dc542d7221$76e2f97b-1c06-40cd-b134-d5155aa5587d$75ca478c-916f-464a-9435-8208ee726d50$5b4a67a9-e33e-4dc6-b9f0-fd9a2cca6f2a$8eafcfed-9771-4d99-b0c5-bd75a6dab012$e41d13ca-1dc1-45ae-9fa6-a83c4101120d$c032b3ff-c539-4e38-81d0-39b28b3a8076$b56e9e56-e74a-401b-b4b5-f36bb33341d5$2a8433e3-9a3b-487b-abf3-09278ea42389$4dd7083a-e730-4f4b-bde8-fc1a5b08ebfc$45efc71d-d5f8-474e-9b89-e72fac7110fd$f7ca738d-5215-4e91-a2f3-a5ff10911313upstream_cells_mapbibrefsbiblio$1d5b1b7c-828c-4a16-b446-cff21b015d45$93200f46-7c8f-4362-a445-43c57b50a2d2precedence_heuristic cell_id$93200f46-7c8f-4362-a445-43c57b50a2d2downstream_cells_mapupstream_cells_mapllms$f39305ea-f7f5-440e-ac55-c83e27f6e7fcnames$2a8433e3-9a3b-487b-abf3-09278ea42389precedence_heuristic cell_id$2a8433e3-9a3b-487b-abf3-09278ea42389downstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$61dc1905-338f-4bfd-a158-2f6bacff769eprecedence_heuristic cell_id$61dc1905-338f-4bfd-a158-2f6bacff769edownstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$eb18303f-3dfb-4b87-90f2-f6dc542d7221precedence_heuristic cell_id$eb18303f-3dfb-4b87-90f2-f6dc542d7221downstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$76e2f97b-1c06-40cd-b134-d5155aa5587dprecedence_heuristic cell_id$76e2f97b-1c06-40cd-b134-d5155aa5587ddownstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$f6f7376e-9984-4289-b8ff-9d47e5358791precedence_heuristic cell_id$f6f7376e-9984-4289-b8ff-9d47e5358791downstream_cells_mapDocumenterCitationsLoggingCSV$579a203b-e6f7-4190-b874-18b00a5c3f77upstream_cells_map$b1a924f4-e2f0-445c-830f-94287a0e52f7precedence_heuristic cell_id$b1a924f4-e2f0-445c-830f-94287a0e52f7downstream_cells_mapnumerical_lookup$95504a74-d5ef-4fb7-83a0-88914c7cbc59upstream_cells_mapfindmaxcollectkeysvaluesdot$f2cba2aa-c541-4692-a441-e65741750a15precedence_heuristic cell_id$f2cba2aa-c541-4692-a441-e65741750a15downstream_cells_mapupstream_cells_map@md_strgetindex$6fc13413-53de-4c75-9b9e-620e0b7f8a1fprecedence_heuristic cell_id$6fc13413-53de-4c75-9b9e-620e0b7f8a1fdownstream_cells_mapupstream_cells_mapqa@md_strgetindex$ccf2dc71-b883-497a-bc58-29ffaf9ea4adprecedence_heuristic cell_id$ccf2dc71-b883-497a-bc58-29ffaf9ea4addownstream_cells_mapupstream_cells_map@md_strgetindex$5b4a67a9-e33e-4dc6-b9f0-fd9a2cca6f2aprecedence_heuristic cell_id$5b4a67a9-e33e-4dc6-b9f0-fd9a2cca6f2adownstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$86101f07-67c5-4df2-911c-4013c44d6c5bprecedence_heuristic cell_id$86101f07-67c5-4df2-911c-4013c44d6c5bdownstream_cells_mapupstream_cells_map@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$a3efd921-eb14-4901-9d6c-800cc812fe02precedence_heuristic cell_id$a3efd921-eb14-4901-9d6c-800cc812fe02downstream_cells_mapupstream_cells_map@md_strgetindex$6800afbf-8ac6-4308-b4cc-b37da57e42c1precedence_heuristic cell_id$6800afbf-8ac6-4308-b4cc-b37da57e42c1downstream_cells_mapupstream_cells_map@md_strgetindex$18c26901-85eb-45ac-89bf-b03bd255007aprecedence_heuristic cell_id$18c26901-85eb-45ac-89bf-b03bd255007adownstream_cells_mapupstream_cells_map Luxor.backgroundLuxor.originHTMLHAlignhtml@drawLuxor.sethueLuxor.previewLuxor.DrawingBase.getindexhighlight$a873f760-bfc1-489f-a58e-75e12afa54f2draw_transformer$85a10748-8d19-44a8-a1c5-0d13b093f1bfcite$94ae440d-0644-49db-9461-f1a1ff1d7f87Luxor.finishBaseimg@md_strLuxor$32621224-a782-4bf6-9570-562cf2bb7360$bcbb3db2-85b3-4cb0-9309-f5c032d14da5precedence_heuristic cell_id$bcbb3db2-85b3-4cb0-9309-f5c032d14da5downstream_cells_mapupstream_cells_map@md_strgetindex$4e10271c-49f8-4f1d-869c-5fa11275d7f6precedence_heuristic cell_id$4e10271c-49f8-4f1d-869c-5fa11275d7f6downstream_cells_mapupstream_cells_map@md_strgetindex$c1437dcc-22cb-424f-9b8e-326172f82d86precedence_heuristic cell_id$c1437dcc-22cb-424f-9b8e-326172f82d86downstream_cells_mapupstream_cells_map@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$c09ec483-9fcf-48e7-b3c0-2508289e3cf3precedence_heuristic cell_id$c09ec483-9fcf-48e7-b3c0-2508289e3cf3downstream_cells_mapupstream_cells_map@md_strgetindex$1bbf2152-4fdf-4ed2-9bdf-95d699824d11precedence_heuristic cell_id$1bbf2152-4fdf-4ed2-9bdf-95d699824d11downstream_cells_mapupstream_cells_map@md_strgetindex$728c16b7-50cd-43fe-a0d7-61d37952a6b3precedence_heuristic cell_id$728c16b7-50cd-43fe-a0d7-61d37952a6b3downstream_cells_mapupstream_cells_mappair_stats$89305cae-098f-4644-9109-d00f1e3bc04c$1faa4ab2-6c93-47dc-b631-8be52780fe7dprecedence_heuristic cell_id$1faa4ab2-6c93-47dc-b631-8be52780fe7ddownstream_cells_mapupstream_cells_mapdict$d558636d-c714-4033-ae73-5b92c3cdedf3softmax_lookup$77f446ac-6030-48f2-9bea-93c427f9fcb9$c3a9a0ce-3450-4b17-8696-2ab8534b29f2precedence_heuristic cell_id$c3a9a0ce-3450-4b17-8696-2ab8534b29f2downstream_cells_mapiter_3upstream_cells_mapnew_token$f1afaf8c-d9ad-446a-9826-9c4cda19993f$01372b00-ecb2-42bd-b408-13234717d969iter_2$736920df-e4bb-4535-b982-e397aa0a782d$e383bb72-49a1-4df1-84c3-b95a2ffe00f5precedence_heuristic cell_id$e383bb72-49a1-4df1-84c3-b95a2ffe00f5downstream_cells_mapupstream_cells_map@md_strgetindex$6aa690e9-389f-4398-abae-b95060db4d90precedence_heuristic cell_id$6aa690e9-389f-4398-abae-b95060db4d90downstream_cells_mapupstream_cells_map@md_strgetindex$4b61363d-87c9-4755-8286-44df34e9dd6aprecedence_heuristic cell_id$4b61363d-87c9-4755-8286-44df34e9dd6adownstream_cells_mapupstream_cells_mapBaseBase.getindex@html_strqa@md_strBase.Docs.HTML$94ae440d-0644-49db-9461-f1a1ff1d7f87precedence_heuristic cell_id$94ae440d-0644-49db-9461-f1a1ff1d7f87downstream_cells_mapcite $f4366cf6-2be0-42b8-96c4-120be3f5c25e$0583ee0c-3802-4e81-b179-a80a82493b43$2a7e5096-1e8d-4506-96d2-86de0a7d39aa$9cb90e76-3bb5-41ff-bc79-c4949400d904$55a09acc-84da-491c-86ba-9a66f4ea52fe$225e58ba-b78d-4a0a-be4f-ad642c879b93$a21fbc70-9137-4d0e-8c8c-cbdc5269778f$86101f07-67c5-4df2-911c-4013c44d6c5b$5150d8f3-6e85-43f2-801a-eae5cc3e3095$d014e6aa-92f6-4ca1-be47-516565d1bb20$18c26901-85eb-45ac-89bf-b03bd255007a$5f05e717-a51a-4a99-bb11-cc493217f93f$f95a6de6-5e02-4237-88ba-ec44ef3d38c3$d1ba8da3-add8-4dbe-9ebf-9a32fa5cd5dd$25b79953-fd7c-46c1-b760-d57c09910981$c1437dcc-22cb-424f-9b8e-326172f82d86upstream_cells_mapbibcitebiblio$1d5b1b7c-828c-4a16-b446-cff21b015d45$55435b26-7fc3-4c8b-8013-6fd4fb65a08eprecedence_heuristic cell_id$55435b26-7fc3-4c8b-8013-6fd4fb65a08edownstream_cells_mapupstream_cells_map@md_strgetindex$225e58ba-b78d-4a0a-be4f-ad642c879b93precedence_heuristic cell_id$225e58ba-b78d-4a0a-be4f-ad642c879b93downstream_cells_mapupstream_cells_map@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$32621224-a782-4bf6-9570-562cf2bb7360precedence_heuristiccell_id$32621224-a782-4bf6-9570-562cf2bb7360downstream_cells_mapLinearAlgebraMathTeXEngineHypertextLiteral$5058e4eb-c53d-4468-b7ff-4f04ded96418PlutoTeachingTools$5058e4eb-c53d-4468-b7ff-4f04ded96418PlutoUI$5058e4eb-c53d-4468-b7ff-4f04ded96418PrettyTablesLaTeXStrings$3d8add97-59e1-444a-838b-85c2a2ac60b3ExperimentalLayoutDataFramesLuxor$91abc03b-fef7-4f93-96fc-13f1cf654f0d$b9caae1a-38aa-4d01-9cda-3d6782fb0e03$c5be3956-5102-4d88-bfdb-9813c0555fe1$18c26901-85eb-45ac-89bf-b03bd255007a$5f05e717-a51a-4a99-bb11-cc493217f93f$f95a6de6-5e02-4237-88ba-ec44ef3d38c3$d1ba8da3-add8-4dbe-9ebf-9a32fa5cd5dd$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0ec$3d8add97-59e1-444a-838b-85c2a2ac60b3$85a10748-8d19-44a8-a1c5-0d13b093f1bfupstream_cells_map$e86a57ae-3945-4cbf-b2e4-a96f4b5295e0precedence_heuristic cell_id$e86a57ae-3945-4cbf-b2e4-a96f4b5295e0downstream_cells_mapupstream_cells_mapqa@md_strgetindex$0c0c1163-0aec-4089-9acc-539b3a86d0b3precedence_heuristic cell_id$0c0c1163-0aec-4089-9acc-539b3a86d0b3downstream_cells_mapupstream_cells_map@md_strgetindex$29474a70-32eb-4281-8626-87819afa7267precedence_heuristic cell_id$29474a70-32eb-4281-8626-87819afa7267downstream_cells_mapadd_pair$01372b00-ecb2-42bd-b408-13234717d969upstream_cells_mapprodpush!copyreplaceBPE$d050a7ee-3aa7-4539-a236-5b6446599ded=>$c5be3956-5102-4d88-bfdb-9813c0555fe1precedence_heuristic cell_id$c5be3956-5102-4d88-bfdb-9813c0555fe1downstream_cells_mapupstream_cells_map Luxor.backgroundLuxor.originHTMLHAlignhtml@drawLuxor.sethueLuxor.previewLuxor.DrawingBase.getindexhighlight$a873f760-bfc1-489f-a58e-75e12afa54f2draw_transformer$85a10748-8d19-44a8-a1c5-0d13b093f1bfLuxor.finishBase@md_strLuxor$32621224-a782-4bf6-9570-562cf2bb7360$7e27c349-ee76-46bd-b1c2-a9ce54974e10precedence_heuristic cell_id$7e27c349-ee76-46bd-b1c2-a9ce54974e10downstream_cells_maptable$771d39a5-74dc-494e-929e-1164bb08b983$91abc03b-fef7-4f93-96fc-13f1cf654f0d$f95a6de6-5e02-4237-88ba-ec44ef3d38c3upstream_cells_mapnothingString:Markdown!ismissingMarkdown.parsesortisnothingpretty_tableuniquenames$2e8b1a77-1f04-4035-8d82-4061d81ecb7aprecedence_heuristic cell_id$2e8b1a77-1f04-4035-8d82-4061d81ecb7adownstream_cells_mapupstream_cells_map@md_strgetindex$6bff7bca-ea1d-44c6-b8c3-040250f90654precedence_heuristic cell_id$6bff7bca-ea1d-44c6-b8c3-040250f90654downstream_cells_mapupstream_cells_map@md_strgetindex$c4bebd0d-eacf-4db4-b5b3-4dca50ab9e1bprecedence_heuristic cell_id$c4bebd0d-eacf-4db4-b5b3-4dca50ab9e1bdownstream_cells_mapupstream_cells_mapqa@md_strgetindex$6f72e8a5-819d-474c-a725-7f7318d964d7precedence_heuristiccell_id$6f72e8a5-819d-474c-a725-7f7318d964d7downstream_cells_mapupstream_cells_mapinclude$b7583418-f4fb-4c63-b421-b5b9af269768precedence_heuristic cell_id$b7583418-f4fb-4c63-b421-b5b9af269768downstream_cells_mapupstream_cells_map@md_strgetindex$a873f760-bfc1-489f-a58e-75e12afa54f2precedence_heuristic cell_id$a873f760-bfc1-489f-a58e-75e12afa54f2downstream_cells_maphighlight$91abc03b-fef7-4f93-96fc-13f1cf654f0d$b9caae1a-38aa-4d01-9cda-3d6782fb0e03$c5be3956-5102-4d88-bfdb-9813c0555fe1$18c26901-85eb-45ac-89bf-b03bd255007a$5f05e717-a51a-4a99-bb11-cc493217f93f$f95a6de6-5e02-4237-88ba-ec44ef3d38c3$3d8add97-59e1-444a-838b-85c2a2ac60b3upstream_cells_mapboxpolysmoothsethuePointsetopacity$76ba4e9b-8bb0-47c4-b607-2ca711f035e6precedence_heuristic cell_id$76ba4e9b-8bb0-47c4-b607-2ca711f035e6downstream_cells_mapupstream_cells_map@md_strgetindex$a5b20939-9afa-48c0-aa67-cbca6bc99804precedence_heuristic cell_id$a5b20939-9afa-48c0-aa67-cbca6bc99804downstream_cells_mapupstream_cells_map@md_strgetindex$91abc03b-fef7-4f93-96fc-13f1cf654f0dprecedence_heuristic cell_id$91abc03b-fef7-4f93-96fc-13f1cf654f0ddownstream_cells_mapupstream_cells_map llms$f39305ea-f7f5-440e-ac55-c83e27f6e7fcLuxor.backgroundLuxor.originHTMLHAlignhtml@drawtable$7e27c349-ee76-46bd-b1c2-a9ce54974e10Luxor.sethueLuxor.previewLuxor.DrawingBase.getindexhighlight$a873f760-bfc1-489f-a58e-75e12afa54f2draw_transformer$85a10748-8d19-44a8-a1c5-0d13b093f1bfLuxor.finishBase@md_strLuxor$32621224-a782-4bf6-9570-562cf2bb7360$79e6c4a8-cc1e-40cc-bb09-e9a7a9a8e475precedence_heuristic cell_id$79e6c4a8-cc1e-40cc-bb09-e9a7a9a8e475downstream_cells_mapupstream_cells_map@md_strgetindex$beccf4e8-1b01-4cb2-b23c-bc5db604f21cprecedence_heuristic cell_id$beccf4e8-1b01-4cb2-b23c-bc5db604f21cdownstream_cells_mapupstream_cells_map@md_strgetindex$e41d13ca-1dc1-45ae-9fa6-a83c4101120dprecedence_heuristic cell_id$e41d13ca-1dc1-45ae-9fa6-a83c4101120ddownstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$5058e4eb-c53d-4468-b7ff-4f04ded96418precedence_heuristic cell_id$5058e4eb-c53d-4468-b7ff-4f04ded96418downstream_cells_mapupstream_cells_mapHypertextLiteral$32621224-a782-4bf6-9570-562cf2bb7360HypertextLiteral.content@htlHypertextLiteral.ResultPlutoUI.TableOfContentsHypertextLiteral.BypassPlutoUI$32621224-a782-4bf6-9570-562cf2bb7360PlutoTeachingTools$32621224-a782-4bf6-9570-562cf2bb7360$PlutoTeachingTools.ChooseDisplayMode$5150d8f3-6e85-43f2-801a-eae5cc3e3095precedence_heuristic cell_id$5150d8f3-6e85-43f2-801a-eae5cc3e3095downstream_cells_mapupstream_cells_mapHAlignimg@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$8c27b182-0c3c-4c19-9619-df62b7dd6bf0precedence_heuristic cell_id$8c27b182-0c3c-4c19-9619-df62b7dd6bf0downstream_cells_mapupstream_cells_mapHAlign@md_strgetindex$9a8eef1b-27c0-4d57-a389-53708ade9058precedence_heuristic cell_id$9a8eef1b-27c0-4d57-a389-53708ade9058downstream_cells_mapupstream_cells_map@md_strgetindex$f39305ea-f7f5-440e-ac55-c83e27f6e7fcprecedence_heuristic cell_id$f39305ea-f7f5-440e-ac55-c83e27f6e7fcdownstream_cells_mapllms$771d39a5-74dc-494e-929e-1164bb08b983$91abc03b-fef7-4f93-96fc-13f1cf654f0d$f95a6de6-5e02-4237-88ba-ec44ef3d38c3$93200f46-7c8f-4362-a445-43c57b50a2d2upstream_cells_mapload_llms$579a203b-e6f7-4190-b874-18b00a5c3f77$f7ca738d-5215-4e91-a2f3-a5ff10911313precedence_heuristic cell_id$f7ca738d-5215-4e91-a2f3-a5ff10911313downstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$c7f318b9-30e6-4b79-b7da-52f70904d246precedence_heuristic cell_id$c7f318b9-30e6-4b79-b7da-52f70904d246downstream_cells_mapsubstituteupstream_cells_mapisless-replaceminprod+StringChar=>Tupleminimum$4dd7083a-e730-4f4b-bde8-fc1a5b08ebfcprecedence_heuristic cell_id$4dd7083a-e730-4f4b-bde8-fc1a5b08ebfcdownstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$8b78360a-21cb-4574-a84d-46ea4d0cedb1precedence_heuristic cell_id$8b78360a-21cb-4574-a84d-46ea4d0cedb1downstream_cells_mapupstream_cells_mapimg$95ec4140-9147-11ef-2af4-5528bad0e6f5precedence_heuristic cell_id$95ec4140-9147-11ef-2af4-5528bad0e6f5downstream_cells_mapupstream_cells_map@md_strgetindex$77f446ac-6030-48f2-9bea-93c427f9fcb9precedence_heuristic cell_id$77f446ac-6030-48f2-9bea-93c427f9fcb9downstream_cells_mapsoftmax_lookup$1faa4ab2-6c93-47dc-b631-8be52780fe7dupstream_cells_mapvalueskeyssum@showzipBase.reprBase.printlnBasedot*softmax$570fa160-3adb-463e-99b8-b7dd05076908$d05e6f0f-0081-4fb6-91e9-ac2f58beda4aprecedence_heuristic cell_id$d05e6f0f-0081-4fb6-91e9-ac2f58beda4adownstream_cells_mapupstream_cells_map@md_strgetindex$d54b5390-0ec0-4ff8-ab18-51726482ca46precedence_heuristic cell_id$d54b5390-0ec0-4ff8-ab18-51726482ca46downstream_cells_mapupstream_cells_map@md_strgetindex$f572e113-b36b-4a6b-96c7-c26f100e1ad4precedence_heuristic cell_id$f572e113-b36b-4a6b-96c7-c26f100e1ad4downstream_cells_mapupstream_cells_map@md_strgetindex$c3db7eb2-356a-428f-9777-6369662d8b06precedence_heuristic cell_id$c3db7eb2-356a-428f-9777-6369662d8b06downstream_cells_mapupstream_cells_map@md_strgetindex$a21fbc70-9137-4d0e-8c8c-cbdc5269778fprecedence_heuristic cell_id$a21fbc70-9137-4d0e-8c8c-cbdc5269778fdownstream_cells_mapupstream_cells_map@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$9e898325-e9e2-45bd-af74-3dd86f00f7b5precedence_heuristic cell_id$9e898325-e9e2-45bd-af74-3dd86f00f7b5downstream_cells_mapupstream_cells_map@md_strgetindex$97463c54-7cc7-4497-a8a6-6422f5f582bdprecedence_heuristic cell_id$97463c54-7cc7-4497-a8a6-6422f5f582bddownstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$8eafcfed-9771-4d99-b0c5-bd75a6dab012precedence_heuristic cell_id$8eafcfed-9771-4d99-b0c5-bd75a6dab012downstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$89305cae-098f-4644-9109-d00f1e3bc04cprecedence_heuristic cell_id$89305cae-098f-4644-9109-d00f1e3bc04cdownstream_cells_mappair_stats$728c16b7-50cd-43fe-a0d7-61d37952a6b3$01372b00-ecb2-42bd-b408-13234717d969upstream_cells_mapislessnextindeachindexgetlastindex+>DictStringrename!$570fa160-3adb-463e-99b8-b7dd05076908precedence_heuristic cell_id$570fa160-3adb-463e-99b8-b7dd05076908downstream_cells_mapsoftmax$77f446ac-6030-48f2-9bea-93c427f9fcb9upstream_cells_map/expsum$9cb90e76-3bb5-41ff-bc79-c4949400d904precedence_heuristic cell_id$9cb90e76-3bb5-41ff-bc79-c4949400d904downstream_cells_mapupstream_cells_map@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$75ca478c-916f-464a-9435-8208ee726d50precedence_heuristic cell_id$75ca478c-916f-464a-9435-8208ee726d50downstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$b9caae1a-38aa-4d01-9cda-3d6782fb0e03precedence_heuristic cell_id$b9caae1a-38aa-4d01-9cda-3d6782fb0e03downstream_cells_mapupstream_cells_map Luxor.backgroundLuxor.originHTMLHAlignhtml@drawLuxor.sethueLuxor.previewLuxor.DrawingBase.getindexhighlight$a873f760-bfc1-489f-a58e-75e12afa54f2draw_transformer$85a10748-8d19-44a8-a1c5-0d13b093f1bfLuxor.finishBase@md_strLuxor$32621224-a782-4bf6-9570-562cf2bb7360$9ff95a9a-192b-4a12-8e2e-7acd6659c066precedence_heuristic cell_id$9ff95a9a-192b-4a12-8e2e-7acd6659c066downstream_cells_mapupstream_cells_map@md_strgetindex$f95a6de6-5e02-4237-88ba-ec44ef3d38c3precedence_heuristic cell_id$f95a6de6-5e02-4237-88ba-ec44ef3d38c3downstream_cells_mapupstream_cells_map llms$f39305ea-f7f5-440e-ac55-c83e27f6e7fcLuxor.backgroundLuxor.originHTMLHAlignhtml@drawtable$7e27c349-ee76-46bd-b1c2-a9ce54974e10Luxor.sethueLuxor.previewLuxor.DrawingBase.getindexhighlight$a873f760-bfc1-489f-a58e-75e12afa54f2draw_transformer$85a10748-8d19-44a8-a1c5-0d13b093f1bfcite$94ae440d-0644-49db-9461-f1a1ff1d7f87Luxor.finishBase@md_strLuxor$32621224-a782-4bf6-9570-562cf2bb7360$ed5b5702-4cca-4116-a70f-4a562178f490precedence_heuristic cell_id$ed5b5702-4cca-4116-a70f-4a562178f490downstream_cells_mapupstream_cells_map@md_strgetindex$736920df-e4bb-4535-b982-e397aa0a782dprecedence_heuristic cell_id$736920df-e4bb-4535-b982-e397aa0a782ddownstream_cells_mapiter_2$c3a9a0ce-3450-4b17-8696-2ab8534b29f2upstream_cells_mapiter_1$f7ca3ff7-b5cf-452b-b955-7219e7397324new_token$f1afaf8c-d9ad-446a-9826-9c4cda19993f$01372b00-ecb2-42bd-b408-13234717d969$55a09acc-84da-491c-86ba-9a66f4ea52feprecedence_heuristic cell_id$55a09acc-84da-491c-86ba-9a66f4ea52fedownstream_cells_mapupstream_cells_mapHAlignimg@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$d558636d-c714-4033-ae73-5b92c3cdedf3precedence_heuristic cell_id$d558636d-c714-4033-ae73-5b92c3cdedf3downstream_cells_mapdict$70f395b2-f8c2-44d5-b0af-702659dd7fee$95504a74-d5ef-4fb7-83a0-88914c7cbc59$1faa4ab2-6c93-47dc-b631-8be52780fe7dupstream_cells_map=>Dict$8d231f2c-4b0c-4c37-a746-16e98d4cafc8precedence_heuristic cell_id$8d231f2c-4b0c-4c37-a746-16e98d4cafc8downstream_cells_mapupstream_cells_map@md_strgetindex$f1afaf8c-d9ad-446a-9826-9c4cda19993fprecedence_heuristic cell_id$f1afaf8c-d9ad-446a-9826-9c4cda19993fdownstream_cells_mapnew_token$f7ca3ff7-b5cf-452b-b955-7219e7397324$736920df-e4bb-4535-b982-e397aa0a782d$c3a9a0ce-3450-4b17-8696-2ab8534b29f2upstream_cells_mapStringBPE$d050a7ee-3aa7-4539-a236-5b6446599dedDict$f7ca3ff7-b5cf-452b-b955-7219e7397324precedence_heuristic cell_id$f7ca3ff7-b5cf-452b-b955-7219e7397324downstream_cells_mapiter_1$736920df-e4bb-4535-b982-e397aa0a782dupstream_cells_mapnew_token$f1afaf8c-d9ad-446a-9826-9c4cda19993f$01372b00-ecb2-42bd-b408-13234717d969$5f05e717-a51a-4a99-bb11-cc493217f93fprecedence_heuristic cell_id$5f05e717-a51a-4a99-bb11-cc493217f93fdownstream_cells_mapupstream_cells_map Luxor.backgroundLuxor.originHTMLHAlignhtml@drawLuxor.sethueLuxor.previewLuxor.DrawingBase.getindexhighlight$a873f760-bfc1-489f-a58e-75e12afa54f2draw_transformer$85a10748-8d19-44a8-a1c5-0d13b093f1bfcite$94ae440d-0644-49db-9461-f1a1ff1d7f87Luxor.finishBase@md_strLuxor$32621224-a782-4bf6-9570-562cf2bb7360$b56e9e56-e74a-401b-b4b5-f36bb33341d5precedence_heuristic cell_id$b56e9e56-e74a-401b-b4b5-f36bb33341d5downstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$57c2c944-0d91-489d-8ad7-f5520e71ef3eprecedence_heuristic cell_id$57c2c944-0d91-489d-8ad7-f5520e71ef3edownstream_cells_mapupstream_cells_map@md_strgetindex$bf563783-9784-4c74-a7b1-6d7a3ed618c5precedence_heuristic cell_id$bf563783-9784-4c74-a7b1-6d7a3ed618c5downstream_cells_mapupstream_cells_map@md_strgetindex$f8330700-e964-4e19-9c55-2b11df45789eprecedence_heuristic cell_id$f8330700-e964-4e19-9c55-2b11df45789edownstream_cells_mapupstream_cells_map@md_strgetindex$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0ecprecedence_heuristic cell_id$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0ecdownstream_cells_mapupstream_cells_map scaleLuxor.backgroundLuxor.originHTMLHAlignhtml@drawLuxor.sethuereadpngLuxor.previewLuxor.DrawingBase.getindexLuxor.placeimagedraw_transformer$85a10748-8d19-44a8-a1c5-0d13b093f1bfLuxor.finishBaseqatranslate@md_strLuxor$32621224-a782-4bf6-9570-562cf2bb7360$d1ba8da3-add8-4dbe-9ebf-9a32fa5cd5ddprecedence_heuristic cell_id$d1ba8da3-add8-4dbe-9ebf-9a32fa5cd5dddownstream_cells_mapupstream_cells_map scalesethueLuxor.backgroundarrowLuxor.originHTMLHAlignhtml@drawLuxor.sethueLuxor.previewLuxor.DrawingBase.getindexPointdraw_transformer$85a10748-8d19-44a8-a1c5-0d13b093f1bfcite$94ae440d-0644-49db-9461-f1a1ff1d7f87Luxor.finishBase@md_strLuxor$32621224-a782-4bf6-9570-562cf2bb7360$1d5b1b7c-828c-4a16-b446-cff21b015d45precedence_heuristic cell_id$1d5b1b7c-828c-4a16-b446-cff21b015d45downstream_cells_mapbiblio$94ae440d-0644-49db-9461-f1a1ff1d7f87$4f1d5112-dbac-4eb6-8518-0dc4193c3f8eupstream_cells_mapload_biblio!$a14e505e-2e4a-4c73-8133-7560ba58916bprecedence_heuristic cell_id$a14e505e-2e4a-4c73-8133-7560ba58916bdownstream_cells_mapupstream_cells_map@md_strgetindex$2a7e5096-1e8d-4506-96d2-86de0a7d39aaprecedence_heuristic cell_id$2a7e5096-1e8d-4506-96d2-86de0a7d39aadownstream_cells_mapupstream_cells_map@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$6712c883-b407-47e1-a666-4de05f8f8d6eprecedence_heuristic cell_id$6712c883-b407-47e1-a666-4de05f8f8d6edownstream_cells_mapupstream_cells_mapHAlignimg@md_strgetindex=>$af8194a1-a358-4cf7-b446-6b377cb76687precedence_heuristic cell_id$af8194a1-a358-4cf7-b446-6b377cb76687downstream_cells_mapupstream_cells_map@md_strgetindex$04e9b912-6712-4290-acc4-f24bb27a1469precedence_heuristic cell_id$04e9b912-6712-4290-acc4-f24bb27a1469downstream_cells_mapupstream_cells_map@md_strgetindex$d014e6aa-92f6-4ca1-be47-516565d1bb20precedence_heuristic cell_id$d014e6aa-92f6-4ca1-be47-516565d1bb20downstream_cells_mapupstream_cells_mapHAlignimg@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87=>$4df0a18d-cb14-41b1-ba40-fd6bfcbb0b03precedence_heuristic cell_id$4df0a18d-cb14-41b1-ba40-fd6bfcbb0b03downstream_cells_mapupstream_cells_mapbib$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$e2eca085-9f99-4e3a-9db4-e7f692aedd34precedence_heuristic cell_id$e2eca085-9f99-4e3a-9db4-e7f692aedd34downstream_cells_mapupstream_cells_map@md_strgetindex$95504a74-d5ef-4fb7-83a0-88914c7cbc59precedence_heuristic cell_id$95504a74-d5ef-4fb7-83a0-88914c7cbc59downstream_cells_mapupstream_cells_mapnumerical_lookup$b1a924f4-e2f0-445c-830f-94287a0e52f7dict$d558636d-c714-4033-ae73-5b92c3cdedf3$453544fc-0e3e-4e04-8c0c-192f3a038884precedence_heuristic cell_id$453544fc-0e3e-4e04-8c0c-192f3a038884downstream_cells_mapupstream_cells_map@md_strgetindex$0583ee0c-3802-4e81-b179-a80a82493b43precedence_heuristic cell_id$0583ee0c-3802-4e81-b179-a80a82493b43downstream_cells_mapupstream_cells_map@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$728f5fdf-77a5-46c7-b3ee-01064ef1b7e2precedence_heuristic cell_id$728f5fdf-77a5-46c7-b3ee-01064ef1b7e2downstream_cells_mapupstream_cells_mapqa@md_strgetindex$01372b00-ecb2-42bd-b408-13234717d969precedence_heuristic cell_id$01372b00-ecb2-42bd-b408-13234717d969downstream_cells_mapnew_token$f7ca3ff7-b5cf-452b-b955-7219e7397324$736920df-e4bb-4535-b982-e397aa0a782d$c3a9a0ce-3450-4b17-8696-2ab8534b29f2upstream_cells_mapislessfindmax+minminimumadd_pair$29474a70-32eb-4281-8626-87819afa7267pair_stats$89305cae-098f-4644-9109-d00f1e3bc04cBPE$d050a7ee-3aa7-4539-a236-5b6446599ded-=>$f4366cf6-2be0-42b8-96c4-120be3f5c25eprecedence_heuristic cell_id$f4366cf6-2be0-42b8-96c4-120be3f5c25edownstream_cells_mapupstream_cells_map@md_strgetindexcite$94ae440d-0644-49db-9461-f1a1ff1d7f87$c8923675-e73e-4621-82b9-966d8b003b97precedence_heuristic cell_id$c8923675-e73e-4621-82b9-966d8b003b97downstream_cells_mapupstream_cells_map@md_strgetindexlast_save_timeAڪ5notebook_id$585340e2-b27c-11f1-9d2c-d557321f93ffin_temp_dir¨metadatabondscell_execution_order t$32621224-a782-4bf6-9570-562cf2bb7360$6f72e8a5-819d-474c-a725-7f7318d964d7$5058e4eb-c53d-4468-b7ff-4f04ded96418$95ec4140-9147-11ef-2af4-5528bad0e6f5$c09ec483-9fcf-48e7-b3c0-2508289e3cf3$beccf4e8-1b01-4cb2-b23c-bc5db604f21c$ccf2dc71-b883-497a-bc58-29ffaf9ea4ad$1bbf2152-4fdf-4ed2-9bdf-95d699824d11$57c2c944-0d91-489d-8ad7-f5520e71ef3e$c3db7eb2-356a-428f-9777-6369662d8b06$2e8b1a77-1f04-4035-8d82-4061d81ecb7a$ed5b5702-4cca-4116-a70f-4a562178f490$e2eca085-9f99-4e3a-9db4-e7f692aedd34$9e898325-e9e2-45bd-af74-3dd86f00f7b5$bcf7667f-f99b-4d10-af84-5d3879f1db5d$e86a57ae-3945-4cbf-b2e4-a96f4b5295e0$6622f9f0-cecc-476e-9d49-7d651f433b9f$6aa690e9-389f-4398-abae-b95060db4d90$6712c883-b407-47e1-a666-4de05f8f8d6e$c4bebd0d-eacf-4db4-b5b3-4dca50ab9e1b$f8330700-e964-4e19-9c55-2b11df45789e$4e10271c-49f8-4f1d-869c-5fa11275d7f6$d54b5390-0ec0-4ff8-ab18-51726482ca46$6800afbf-8ac6-4308-b4cc-b37da57e42c1$55435b26-7fc3-4c8b-8013-6fd4fb65a08e$bcbb3db2-85b3-4cb0-9309-f5c032d14da5$d558636d-c714-4033-ae73-5b92c3cdedf3$70f395b2-f8c2-44d5-b0af-702659dd7fee$b1a924f4-e2f0-445c-830f-94287a0e52f7$95504a74-d5ef-4fb7-83a0-88914c7cbc59$8d231f2c-4b0c-4c37-a746-16e98d4cafc8$570fa160-3adb-463e-99b8-b7dd05076908$77f446ac-6030-48f2-9bea-93c427f9fcb9$1faa4ab2-6c93-47dc-b631-8be52780fe7d$bf563783-9784-4c74-a7b1-6d7a3ed618c5$9ff95a9a-192b-4a12-8e2e-7acd6659c066$76ba4e9b-8bb0-47c4-b607-2ca711f035e6$8c27b182-0c3c-4c19-9619-df62b7dd6bf0$0c0c1163-0aec-4089-9acc-539b3a86d0b3$b7583418-f4fb-4c63-b421-b5b9af269768$6fc13413-53de-4c75-9b9e-620e0b7f8a1f$d05e6f0f-0081-4fb6-91e9-ac2f58beda4a$a3efd921-eb14-4901-9d6c-800cc812fe02$4b61363d-87c9-4755-8286-44df34e9dd6a$453544fc-0e3e-4e04-8c0c-192f3a038884$92e01e21-ca77-43fc-9bf8-0c5a7aaed1bb$f2cba2aa-c541-4692-a441-e65741750a15$e383bb72-49a1-4df1-84c3-b95a2ffe00f5$af8194a1-a358-4cf7-b446-6b377cb76687$79e6c4a8-cc1e-40cc-bb09-e9a7a9a8e475$a5b20939-9afa-48c0-aa67-cbca6bc99804$a14e505e-2e4a-4c73-8133-7560ba58916b$9a8eef1b-27c0-4d57-a389-53708ade9058$728f5fdf-77a5-46c7-b3ee-01064ef1b7e2$c8923675-e73e-4621-82b9-966d8b003b97$04e9b912-6712-4290-acc4-f24bb27a1469$8b78360a-21cb-4574-a84d-46ea4d0cedb1$6bff7bca-ea1d-44c6-b8c3-040250f90654$f572e113-b36b-4a6b-96c7-c26f100e1ad4$f6f7376e-9984-4289-b8ff-9d47e5358791$1d5b1b7c-828c-4a16-b446-cff21b015d45$94ae440d-0644-49db-9461-f1a1ff1d7f87$f4366cf6-2be0-42b8-96c4-120be3f5c25e$0583ee0c-3802-4e81-b179-a80a82493b43$2a7e5096-1e8d-4506-96d2-86de0a7d39aa$9cb90e76-3bb5-41ff-bc79-c4949400d904$55a09acc-84da-491c-86ba-9a66f4ea52fe$225e58ba-b78d-4a0a-be4f-ad642c879b93$a21fbc70-9137-4d0e-8c8c-cbdc5269778f$86101f07-67c5-4df2-911c-4013c44d6c5b$5150d8f3-6e85-43f2-801a-eae5cc3e3095$d014e6aa-92f6-4ca1-be47-516565d1bb20$25b79953-fd7c-46c1-b760-d57c09910981$c1437dcc-22cb-424f-9b8e-326172f82d86$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$61dc1905-338f-4bfd-a158-2f6bacff769e$4df0a18d-cb14-41b1-ba40-fd6bfcbb0b03$97463c54-7cc7-4497-a8a6-6422f5f582bd$eb18303f-3dfb-4b87-90f2-f6dc542d7221$76e2f97b-1c06-40cd-b134-d5155aa5587d$75ca478c-916f-464a-9435-8208ee726d50$5b4a67a9-e33e-4dc6-b9f0-fd9a2cca6f2a$8eafcfed-9771-4d99-b0c5-bd75a6dab012$e41d13ca-1dc1-45ae-9fa6-a83c4101120d$c032b3ff-c539-4e38-81d0-39b28b3a8076$b56e9e56-e74a-401b-b4b5-f36bb33341d5$2a8433e3-9a3b-487b-abf3-09278ea42389$4dd7083a-e730-4f4b-bde8-fc1a5b08ebfc$45efc71d-d5f8-474e-9b89-e72fac7110fd$f7ca738d-5215-4e91-a2f3-a5ff10911313$85a10748-8d19-44a8-a1c5-0d13b093f1bf$d1ba8da3-add8-4dbe-9ebf-9a32fa5cd5dd$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0ec$a873f760-bfc1-489f-a58e-75e12afa54f2$b9caae1a-38aa-4d01-9cda-3d6782fb0e03$c5be3956-5102-4d88-bfdb-9813c0555fe1$18c26901-85eb-45ac-89bf-b03bd255007a$5f05e717-a51a-4a99-bb11-cc493217f93f$3d8add97-59e1-444a-838b-85c2a2ac60b3$d050a7ee-3aa7-4539-a236-5b6446599ded$29474a70-32eb-4281-8626-87819afa7267$89305cae-098f-4644-9109-d00f1e3bc04c$728c16b7-50cd-43fe-a0d7-61d37952a6b3$c7f318b9-30e6-4b79-b7da-52f70904d246$f1afaf8c-d9ad-446a-9826-9c4cda19993f$01372b00-ecb2-42bd-b408-13234717d969$f7ca3ff7-b5cf-452b-b955-7219e7397324$736920df-e4bb-4535-b982-e397aa0a782d$c3a9a0ce-3450-4b17-8696-2ab8534b29f2$579a203b-e6f7-4190-b874-18b00a5c3f77$f39305ea-f7f5-440e-ac55-c83e27f6e7fc$93200f46-7c8f-4362-a445-43c57b50a2d2$7e27c349-ee76-46bd-b1c2-a9ce54974e10$771d39a5-74dc-494e-929e-1164bb08b983$91abc03b-fef7-4f93-96fc-13f1cf654f0d$f95a6de6-5e02-4237-88ba-ec44ef3d38c3process_statusreadycell_order t$5058e4eb-c53d-4468-b7ff-4f04ded96418$95ec4140-9147-11ef-2af4-5528bad0e6f5$f4366cf6-2be0-42b8-96c4-120be3f5c25e$61dc1905-338f-4bfd-a158-2f6bacff769e$c09ec483-9fcf-48e7-b3c0-2508289e3cf3$beccf4e8-1b01-4cb2-b23c-bc5db604f21c$ccf2dc71-b883-497a-bc58-29ffaf9ea4ad$1bbf2152-4fdf-4ed2-9bdf-95d699824d11$57c2c944-0d91-489d-8ad7-f5520e71ef3e$0583ee0c-3802-4e81-b179-a80a82493b43$728c16b7-50cd-43fe-a0d7-61d37952a6b3$f7ca3ff7-b5cf-452b-b955-7219e7397324$736920df-e4bb-4535-b982-e397aa0a782d$c3db7eb2-356a-428f-9777-6369662d8b06$c3a9a0ce-3450-4b17-8696-2ab8534b29f2$4df0a18d-cb14-41b1-ba40-fd6bfcbb0b03$2e8b1a77-1f04-4035-8d82-4061d81ecb7a$ed5b5702-4cca-4116-a70f-4a562178f490$771d39a5-74dc-494e-929e-1164bb08b983$97463c54-7cc7-4497-a8a6-6422f5f582bd$e2eca085-9f99-4e3a-9db4-e7f692aedd34$9e898325-e9e2-45bd-af74-3dd86f00f7b5$bcf7667f-f99b-4d10-af84-5d3879f1db5d$2a7e5096-1e8d-4506-96d2-86de0a7d39aa$e86a57ae-3945-4cbf-b2e4-a96f4b5295e0$eb18303f-3dfb-4b87-90f2-f6dc542d7221$6622f9f0-cecc-476e-9d49-7d651f433b9f$6aa690e9-389f-4398-abae-b95060db4d90$9cb90e76-3bb5-41ff-bc79-c4949400d904$6712c883-b407-47e1-a666-4de05f8f8d6e$c4bebd0d-eacf-4db4-b5b3-4dca50ab9e1b$76e2f97b-1c06-40cd-b134-d5155aa5587d$f8330700-e964-4e19-9c55-2b11df45789e$91abc03b-fef7-4f93-96fc-13f1cf654f0d$75ca478c-916f-464a-9435-8208ee726d50$4e10271c-49f8-4f1d-869c-5fa11275d7f6$55a09acc-84da-491c-86ba-9a66f4ea52fe$5b4a67a9-e33e-4dc6-b9f0-fd9a2cca6f2a$d54b5390-0ec0-4ff8-ab18-51726482ca46$225e58ba-b78d-4a0a-be4f-ad642c879b93$a21fbc70-9137-4d0e-8c8c-cbdc5269778f$8eafcfed-9771-4d99-b0c5-bd75a6dab012$6800afbf-8ac6-4308-b4cc-b37da57e42c1$55435b26-7fc3-4c8b-8013-6fd4fb65a08e$bcbb3db2-85b3-4cb0-9309-f5c032d14da5$d558636d-c714-4033-ae73-5b92c3cdedf3$70f395b2-f8c2-44d5-b0af-702659dd7fee$b1a924f4-e2f0-445c-830f-94287a0e52f7$95504a74-d5ef-4fb7-83a0-88914c7cbc59$8d231f2c-4b0c-4c37-a746-16e98d4cafc8$86101f07-67c5-4df2-911c-4013c44d6c5b$570fa160-3adb-463e-99b8-b7dd05076908$77f446ac-6030-48f2-9bea-93c427f9fcb9$1faa4ab2-6c93-47dc-b631-8be52780fe7d$e41d13ca-1dc1-45ae-9fa6-a83c4101120d$bf563783-9784-4c74-a7b1-6d7a3ed618c5$9ff95a9a-192b-4a12-8e2e-7acd6659c066$5150d8f3-6e85-43f2-801a-eae5cc3e3095$c032b3ff-c539-4e38-81d0-39b28b3a8076$76ba4e9b-8bb0-47c4-b607-2ca711f035e6$8c27b182-0c3c-4c19-9619-df62b7dd6bf0$0c0c1163-0aec-4089-9acc-539b3a86d0b3$b7583418-f4fb-4c63-b421-b5b9af269768$d014e6aa-92f6-4ca1-be47-516565d1bb20$6fc13413-53de-4c75-9b9e-620e0b7f8a1f$d05e6f0f-0081-4fb6-91e9-ac2f58beda4a$a3efd921-eb14-4901-9d6c-800cc812fe02$b9caae1a-38aa-4d01-9cda-3d6782fb0e03$4b61363d-87c9-4755-8286-44df34e9dd6a$453544fc-0e3e-4e04-8c0c-192f3a038884$c5be3956-5102-4d88-bfdb-9813c0555fe1$92e01e21-ca77-43fc-9bf8-0c5a7aaed1bb$18c26901-85eb-45ac-89bf-b03bd255007a$b56e9e56-e74a-401b-b4b5-f36bb33341d5$f2cba2aa-c541-4692-a441-e65741750a15$5f05e717-a51a-4a99-bb11-cc493217f93f$2a8433e3-9a3b-487b-abf3-09278ea42389$e383bb72-49a1-4df1-84c3-b95a2ffe00f5$f95a6de6-5e02-4237-88ba-ec44ef3d38c3$af8194a1-a358-4cf7-b446-6b377cb76687$79e6c4a8-cc1e-40cc-bb09-e9a7a9a8e475$d1ba8da3-add8-4dbe-9ebf-9a32fa5cd5dd$4dd7083a-e730-4f4b-bde8-fc1a5b08ebfc$a5b20939-9afa-48c0-aa67-cbca6bc99804$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0ec$25b79953-fd7c-46c1-b760-d57c09910981$45efc71d-d5f8-474e-9b89-e72fac7110fd$a14e505e-2e4a-4c73-8133-7560ba58916b$9a8eef1b-27c0-4d57-a389-53708ade9058$728f5fdf-77a5-46c7-b3ee-01064ef1b7e2$c8923675-e73e-4621-82b9-966d8b003b97$04e9b912-6712-4290-acc4-f24bb27a1469$c1437dcc-22cb-424f-9b8e-326172f82d86$8b78360a-21cb-4574-a84d-46ea4d0cedb1$f7ca738d-5215-4e91-a2f3-a5ff10911313$6bff7bca-ea1d-44c6-b8c3-040250f90654$3d8add97-59e1-444a-838b-85c2a2ac60b3$f572e113-b36b-4a6b-96c7-c26f100e1ad4$32621224-a782-4bf6-9570-562cf2bb7360$f6f7376e-9984-4289-b8ff-9d47e5358791$6f72e8a5-819d-474c-a725-7f7318d964d7$1d5b1b7c-828c-4a16-b446-cff21b015d45$94ae440d-0644-49db-9461-f1a1ff1d7f87$4f1d5112-dbac-4eb6-8518-0dc4193c3f8e$85a10748-8d19-44a8-a1c5-0d13b093f1bf$a873f760-bfc1-489f-a58e-75e12afa54f2$d050a7ee-3aa7-4539-a236-5b6446599ded$29474a70-32eb-4281-8626-87819afa7267$89305cae-098f-4644-9109-d00f1e3bc04c$c7f318b9-30e6-4b79-b7da-52f70904d246$f1afaf8c-d9ad-446a-9826-9c4cda19993f$01372b00-ecb2-42bd-b408-13234717d969$f39305ea-f7f5-440e-ac55-c83e27f6e7fc$579a203b-e6f7-4190-b874-18b00a5c3f77$93200f46-7c8f-4362-a445-43c57b50a2d2$7e27c349-ee76-46bd-b1c2-a9ce54974e10cell_inputs t$3d8add97-59e1-444a-838b-85c2a2ac60b3metadatadisabled©show_logsîskip_as_script§cell_id$3d8add97-59e1-444a-838b-85c2a2ac60b3code_foldedäcode8HAlign(
md"""
*Cross-Attention* between
* values and keys ``E(CX + P)`` where ``E`` is the encoder, and ``X`` is the matrix of input tokens
* query ``Q`` depending on past output ``Y`` and number of layers already applied
```math
\text{MultiHead}(E(CX + P), E(CX + P), Q)
```
The embedding vectors ``CX`` take then different projections
for value, key, query and also for different heads!
```math
\begin{multline}
\text{head}_j = \text{Attention}(W_j^VV, W_j^KK, W_j^QQ)\\
\text{where } V = K = E(CX + P)
\end{multline}
```
""",
HTML(html(@draw begin
draw_transformer(false)
highlight(31, -97, 205, 5)
#sethue("red")
#setopacity(1)
fontsize(32)
text("CX + P", Point(-60, 252), halign = :center)
text("CY + P", Point(65, 252), halign = :center)
text(L"E(CX + P)", Point(-70, -160), halign = :center)
end 300 400)),
)$92e01e21-ca77-43fc-9bf8-0c5a7aaed1bbmetadatadisabled©show_logsîskip_as_script§cell_id$92e01e21-ca77-43fc-9bf8-0c5a7aaed1bbcode_foldedäcodemd"## Residual connection"$6622f9f0-cecc-476e-9d49-7d651f433b9fmetadatadisabled©show_logsîskip_as_script§cell_id$6622f9f0-cecc-476e-9d49-7d651f433b9fcode_foldedäcode!md"# Pre-transformers approaches"$70f395b2-f8c2-44d5-b0af-702659dd7feemetadatadisabled©show_logsîskip_as_script§cell_id$70f395b2-f8c2-44d5-b0af-702659dd7feecode_folded¤codedict[[1, 0]]$771d39a5-74dc-494e-929e-1164bb08b983metadatadisabled©show_logsîskip_as_script§cell_id$771d39a5-74dc-494e-929e-1164bb08b983code_foldedäcodeٙtable(llms, mandatory_columns = ["``n_\\text{ctx}``"], included_columns = [
"Name",
"Ref",
"``n_\\text{voc}``",
"``n_\\text{ctx}``",
"Tokenizer",
])$85a10748-8d19-44a8-a1c5-0d13b093f1bfmetadatadisabled©show_logsîskip_as_script§cell_id$85a10748-8d19-44a8-a1c5-0d13b093f1bfcode_folded¤codefunction draw_transformer(decoder_only = true)
scale(0.4, 0.4)
Luxor.placeimage(readpng("images/transformer.png"), centered = true)
if decoder_only
sethue("red")
setopacity(0.4)
box(Point(-350, -160), Point(320, 20), :fill)
box(Point(-350, 20), Point(0, 460), :fill)
translate(Point(-170, -190))
setopacity(1)
fontsize(32)
text("Not used for now", halign = :center)
end
end$4f1d5112-dbac-4eb6-8518-0dc4193c3f8emetadatadisabled©show_logsîskip_as_script§cell_id$4f1d5112-dbac-4eb6-8518-0dc4193c3f8ecode_folded¤code'bib(args...) = bibrefs(biblio, args...)$93200f46-7c8f-4362-a445-43c57b50a2d2metadatadisabled©show_logsîskip_as_script§cell_id$93200f46-7c8f-4362-a445-43c57b50a2d2code_folded¤codenames(llms)$2a8433e3-9a3b-487b-abf3-09278ea42389metadatadisabled©show_logsîskip_as_script§cell_id$2a8433e3-9a3b-487b-abf3-09278ea42389code_foldedäcode?bib(["ioffe2015Batch", "ba2016Layer", "vaswani2017Attentiona"])$61dc1905-338f-4bfd-a158-2f6bacff769emetadatadisabled©show_logsîskip_as_script§cell_id$61dc1905-338f-4bfd-a158-2f6bacff769ecode_foldedäcode4bib(["goodfellow2016Deep", "vaswani2017Attentiona"])$eb18303f-3dfb-4b87-90f2-f6dc542d7221metadatadisabled©show_logsîskip_as_script§cell_id$eb18303f-3dfb-4b87-90f2-f6dc542d7221code_foldedäcode0bib(["press2017Using", "vaswani2017Attentiona"])$76e2f97b-1c06-40cd-b134-d5155aa5587dmetadatadisabled©show_logsîskip_as_script§cell_id$76e2f97b-1c06-40cd-b134-d5155aa5587dcode_foldedäcodebib(["bengio2000Neural"])$f6f7376e-9984-4289-b8ff-9d47e5358791metadatadisabled©show_logsîskip_as_script§cell_id$f6f7376e-9984-4289-b8ff-9d47e5358791code_folded¤code(import DocumenterCitations, CSV, Logging$b1a924f4-e2f0-445c-830f-94287a0e52f7metadatadisabled©show_logsîskip_as_script§cell_id$b1a924f4-e2f0-445c-830f-94287a0e52f7code_folded¤codeلfunction numerical_lookup(dict, query)
_, i = findmax([dot(query, key) for key in keys(dict)])
return collect(values(dict))[i]
end$f2cba2aa-c541-4692-a441-e65741750a15metadatadisabled©show_logsîskip_as_script§cell_id$f2cba2aa-c541-4692-a441-e65741750a15code_foldedäcodemd"## Layer normalization"$6fc13413-53de-4c75-9b9e-620e0b7f8a1fmetadatadisabled©show_logsîskip_as_script§cell_id$6fc13413-53de-4c75-9b9e-620e0b7f8a1fcode_foldedäcodeoqa(md"Is ``W^O`` needed if ``h = 1`` ?", md"No, if ``h = 1``, we can merge ``W^OW_1^V`` into a new ``W_1^V``.")$ccf2dc71-b883-497a-bc58-29ffaf9ea4admetadatadisabled©show_logsîskip_as_script§cell_id$ccf2dc71-b883-497a-bc58-29ffaf9ea4adcode_foldedäcode0md"## Text to vectors : step 1 → tokenization"$5b4a67a9-e33e-4dc6-b9f0-fd9a2cca6f2ametadatadisabled©show_logsîskip_as_script§cell_id$5b4a67a9-e33e-4dc6-b9f0-fd9a2cca6f2acode_foldedäcode3bib(["mikolov2010Recurrent", "goodfellow2016Deep"])$86101f07-67c5-4df2-911c-4013c44d6c5bmetadatadisabled©show_logsîskip_as_script§cell_id$86101f07-67c5-4df2-911c-4013c44d6c5bcode_foldedäcode0md"""
Attention head provides a differentiable numerical dictionary $(cite("bahdanau2016Neural"))
```math
\begin{align}
\alpha
& =
\text{softmax}(\langle q, k_1 \rangle, \ldots, \langle q, k_{n_\text{ctx}}\rangle)
&
\text{Attention}(q, k, v)
& =
\sum_{i=1}^{n_\text{ctx}} \alpha_i v_i
\end{align}
```
"""$a3efd921-eb14-4901-9d6c-800cc812fe02metadatadisabled©show_logsîskip_as_script§cell_id$a3efd921-eb14-4901-9d6c-800cc812fe02code_foldedäcodemd"## Self-Attention"$6800afbf-8ac6-4308-b4cc-b37da57e42c1metadatadisabled©show_logsîskip_as_script§cell_id$6800afbf-8ac6-4308-b4cc-b37da57e42c1code_foldedäcodemd"# Attention is all you need"$18c26901-85eb-45ac-89bf-b03bd255007ametadatadisabled©show_logsîskip_as_script§cell_id$18c26901-85eb-45ac-89bf-b03bd255007acode_foldedäcodeHAlign(
md"""
Residual connection $(cite("he2015Deep"))
$(img("resnet"))
""",
HTML(html(@draw begin
draw_transformer()
highlight(210, -85, 290, -45)
highlight(360, -75, 440, 50)
highlight(210, 210, 290, 250)
highlight(360, 220, 440, 420)
end 300 400))
)$bcbb3db2-85b3-4cb0-9309-f5c032d14da5metadatadisabled©show_logsîskip_as_script§cell_id$bcbb3db2-85b3-4cb0-9309-f5c032d14da5code_foldedäcodeٰmd"
What would a numerical dictionary look like ? Consider keys ``k_i \in \mathbb{R}^{d_k}`` and values ``v_i \in \mathbb{R}^{d_v}``. Given a query ``q \in \mathbb{R}^{d_k}``,"$4e10271c-49f8-4f1d-869c-5fa11275d7f6metadatadisabled©show_logsîskip_as_script§cell_id$4e10271c-49f8-4f1d-869c-5fa11275d7f6code_foldedäcode&md"## Recurrent neural networks (RNN)"$c1437dcc-22cb-424f-9b8e-326172f82d86metadatadisabled©show_logsîskip_as_script§cell_id$c1437dcc-22cb-424f-9b8e-326172f82d86code_foldedäcodemd"""
* LSTM **encoder** → **context** → LSTM **decoder** $(cite("sutskever2014Sequence")). See $(cite("sutskever2014Sequence", "Figure 1")) below.
* Issue with *encoder bottleneck*. All information has to be summarized in the **context**.
"""$c09ec483-9fcf-48e7-b3c0-2508289e3cf3metadatadisabled©show_logsîskip_as_script§cell_id$c09ec483-9fcf-48e7-b3c0-2508289e3cf3code_foldedäcodemd"## Autoregressive Models"$1bbf2152-4fdf-4ed2-9bdf-95d699824d11metadatadisabled©show_logsîskip_as_script§cell_id$1bbf2152-4fdf-4ed2-9bdf-95d699824d11code_foldedäcodejmd"""
#### Why not encode each letter ?
* **Idea** : Turn each letter into its one-hot encoding in ``\mathbb{R}^{26}``.
* **Issue** : The "past text" only has ``n_\text{ctx}`` characters so ``n_\text{ctx}`` must be **large** but transformers have a complexity **quadratic** in ``n_\text{ctx}``!
* **Practical details** : Text is encoded with [UTF-8](https://en.wikipedia.org/wiki/UTF-8) so each character is encoded into 1 to 4 bytes. We encode each byte to a vector in ``\mathbb{R}^{256}`` but care must be taken not to generate invalid UTF-8.
#### Why not encode each word ?
* **Idea** : Turn each word into its one-hot encoding in ``\mathbb{R}^n``. The value of ``n`` is the number of words. Depending on the language ([source](https://en.wikipedia.org/wiki/List_of_dictionaries_by_number_of_words)):
| Language | French | English | Dutch | German |
|----------|---------|---------|---------|---------|
| ``n`` | 408,078 | 350,000 | 350,000 | 200,000 |
* **Issue** : The value of ``n`` is **too large**. We cannot trust the words of languages to be a tokenization that optimally compresses text for our dataset.
"""$728c16b7-50cd-43fe-a0d7-61d37952a6b3metadatadisabled©show_logsîskip_as_script§cell_id$728c16b7-50cd-43fe-a0d7-61d37952a6b3code_folded¤codepair_stats("aaabdaaabac")$1faa4ab2-6c93-47dc-b631-8be52780fe7dmetadatadisabled©show_logsîskip_as_script§cell_id$1faa4ab2-6c93-47dc-b631-8be52780fe7dcode_folded¤code softmax_lookup(dict, [0.8, 0.2])$c3a9a0ce-3450-4b17-8696-2ab8534b29f2metadatadisabled©show_logsîskip_as_script§cell_id$c3a9a0ce-3450-4b17-8696-2ab8534b29f2code_folded¤codeiter_3 = new_token(iter_2)$e383bb72-49a1-4df1-84c3-b95a2ffe00f5metadatadisabled©show_logsîskip_as_script§cell_id$e383bb72-49a1-4df1-84c3-b95a2ffe00f5code_foldedäcodemd"## Feed-Forward network"$6aa690e9-389f-4398-abae-b95060db4d90metadatadisabled©show_logsîskip_as_script§cell_id$6aa690e9-389f-4398-abae-b95060db4d90code_foldedäcodemd"## Shared embedding"$4b61363d-87c9-4755-8286-44df34e9dd6ametadatadisabled©show_logsîskip_as_script§cell_id$4b61363d-87c9-4755-8286-44df34e9dd6acode_foldedäcodeqa(
html"Is the order between the tokens taken into account by the model ?",
md"""
No. Since the same matrices ``W_j^V``, ``W_j^K`` and ``W_j^Q`` multiply the different position. The **position** information is completely **lost**!
"""
)$94ae440d-0644-49db-9461-f1a1ff1d7f87metadatadisabled©show_logsîskip_as_script§cell_id$94ae440d-0644-49db-9461-f1a1ff1d7f87code_folded¤code(cite(args...) = bibcite(biblio, args...)$55435b26-7fc3-4c8b-8013-6fd4fb65a08emetadatadisabled©show_logsîskip_as_script§cell_id$55435b26-7fc3-4c8b-8013-6fd4fb65a08ecode_foldedäcodemd"## Numerical dictionary"$225e58ba-b78d-4a0a-be4f-ad642c879b93metadatadisabled©show_logsîskip_as_script§cell_id$225e58ba-b78d-4a0a-be4f-ad642c879b93code_foldedäcodemd"""
It's difficult to model long-term dependencies as their gradient either vanish or explodes exponentially (think of the power method) $(cite("goodfellow2016Deep", "Section 10.7"))
*Gated* extensions attempting to solve this issue $(cite("goodfellow2016Deep", "Section 10.10")):
* Long short-term memory (LSTM) $(cite("graves2014Generating"))
* Gated recurrent unit (GRU) $(cite("cho2014Properties"))
"""$32621224-a782-4bf6-9570-562cf2bb7360metadatadisabled©show_logsîskip_as_script§cell_id$32621224-a782-4bf6-9570-562cf2bb7360code_folded¤code٥using PlutoUI, DataFrames, PrettyTables, LinearAlgebra, Luxor, LaTeXStrings, MathTeXEngine, PlutoUI, PlutoUI.ExperimentalLayout, HypertextLiteral, PlutoTeachingTools$e86a57ae-3945-4cbf-b2e4-a96f4b5295e0metadatadisabled©show_logsîskip_as_script§cell_id$e86a57ae-3945-4cbf-b2e4-a96f4b5295e0code_foldedäcode?qa(md"Why don't we use ``D = C^{-1}`` ?",
md"""
The ``C`` matrix is not invertible as it is not square. Given a vector ``u``, the vector ``v = Du`` could be computed to be the mininum norm solution of ``u = Cv``, this is what is done by `v = D \ u`. Computing `D \ u` would be more computational work than `D' \ u` but that's not the only reason `D'` is used.
If ``v`` is chosen so that ``u = Cv``, it means that ``v`` is a linear combination allowing to reconstruct ``u`` using the columns of ``C``.
From that perspective, ``v_i`` could be nonzero even though the direction of the vector ``u`` us far from the direction of the column ``C_{:i}``.
That does not correspond to what we want to do here.
Here, we want a probability vector ``p`` with high probability ``p_i`` when the direction of the column ``C_{:i}`` is close to the direction of ``u``.
In the vector ``v = C^\top u``, ``v_i = \langle C_{:i}, u \rangle`` is the scalar product between the ``i``th column of ``C`` and ``u`` hence it is a good measure of how close the direction are to each other.
Of course this assumes that the column of ``C`` have the same norm, but the hope is for the model to figure in training that the columns of ``C`` should have unit norm.
We can then simply apply softmax to turn these scalar products into probabilities ``p = \text{softmax}(v)``.
""")$0c0c1163-0aec-4089-9acc-539b3a86d0b3metadatadisabled©show_logsîskip_as_script§cell_id$0c0c1163-0aec-4089-9acc-539b3a86d0b3code_foldedäcodebmd"""
```math
\text{Masked-Attention}(V, K, Q)\
=
V\text{softmax}(M + K^\top Q/\sqrt{d_k})
```
"""$29474a70-32eb-4281-8626-87819afa7267metadatadisabled©show_logsîskip_as_script§cell_id$29474a70-32eb-4281-8626-87819afa7267code_folded¤codeٙfunction add_pair(bpe::BPE, subs)
pairs = copy(bpe.pairs)
push!(pairs, subs)
return BPE(replace(bpe.text, prod(subs.first) => subs.second), pairs)
end$c5be3956-5102-4d88-bfdb-9813c0555fe1metadatadisabled©show_logsîskip_as_script§cell_id$c5be3956-5102-4d88-bfdb-9813c0555fe1code_foldedäcodeHAlign(
md"""
Cannot sum ``Cx_i + e_i`` with one-hot encoding ``e_i \in \mathbb{R}^{n_\text{ctx}}`` as the dimension of ``Cx_i`` is ``\mathbb{R}^{d_\text{emb}}``.
So we also add a positional embedding ``P`` : ``Cx_i + Pe_i = Cx_i + p_i``.
With Self-Attention:
```math
\text{Self-MultiHead}(CX + P, CX + P, CX + P)
```
""",
HTML(html(@draw begin
draw_transformer()
highlight(310, 410, 530, 510)
end 300 400))
)$7e27c349-ee76-46bd-b1c2-a9ce54974e10metadatadisabled©show_logsîskip_as_script§cell_id$7e27c349-ee76-46bd-b1c2-a9ce54974e10code_folded¤codefunction table(df; mandatory_columns = String[], included_columns = nothing)
for col in mandatory_columns
df = df[(!ismissing).(df[!, col]), :]
end
if !isnothing(included_columns)
df = unique(df[!, included_columns])
end
Markdown.parse(pretty_table(
String,
sort(df),
backend = :markdown,
column_labels = names(df),
allow_markdown_in_cells = true,
formatters = [(v, _, _) -> ismissing(v) ? "" : v],
))
end$2e8b1a77-1f04-4035-8d82-4061d81ecb7ametadatadisabled©show_logsîskip_as_script§cell_id$2e8b1a77-1f04-4035-8d82-4061d81ecb7acode_foldedäcode)md"## Increasing length of \"past text\""$6bff7bca-ea1d-44c6-b8c3-040250f90654metadatadisabled©show_logsîskip_as_script§cell_id$6bff7bca-ea1d-44c6-b8c3-040250f90654code_foldedäcodemd"## Cross-Attention"$c4bebd0d-eacf-4db4-b5b3-4dca50ab9e1bmetadatadisabled©show_logsîskip_as_script§cell_id$c4bebd0d-eacf-4db4-b5b3-4dca50ab9e1bcode_foldedäcodeqa(md"What are the number of columns of ``W_1`` and number of rows of ``W_2`` now ?",
md"""
The matrix ``W_1`` has ``n_\text{ctx}d_\text{emb}`` columns. Assuming ``d_\text{emb} \ll n_\text{voc}`` and ``n_\text{ctx} \gg 1``, this is much smaller than the number ``n_\text{ctx}n_\text{voc}`` that we would have without the embedding. The number of rows of ``W_2`` is ``n_\text{voc}``, unaffected by the embedding.
""")$6f72e8a5-819d-474c-a725-7f7318d964d7metadatadisabled©show_logsîskip_as_script§cell_id$6f72e8a5-819d-474c-a725-7f7318d964d7code_folded¤codeinclude("utils.jl")$b7583418-f4fb-4c63-b421-b5b9af269768metadatadisabled©show_logsîskip_as_script§cell_id$b7583418-f4fb-4c63-b421-b5b9af269768code_foldedäcodemd"## Multi-Head Attention"$a873f760-bfc1-489f-a58e-75e12afa54f2metadatadisabled©show_logsîskip_as_script§cell_id$a873f760-bfc1-489f-a58e-75e12afa54f2code_folded¤codefunction highlight(a, b, c, d)
sethue("green")
setopacity(0.4)
#box(Point(a, b), Point(c, d), :fill)
polysmooth(box(Point(a, b), Point(c, d), vertices=true), 10, action = :fill)
setopacity(1)
polysmooth(box(Point(a, b), Point(c, d), vertices=true), 10, action = :stroke)
end$76ba4e9b-8bb0-47c4-b607-2ca711f035e6metadatadisabled©show_logsîskip_as_script§cell_id$76ba4e9b-8bb0-47c4-b607-2ca711f035e6code_foldedäcodemd"## Masked Attention"$a5b20939-9afa-48c0-aa67-cbca6bc99804metadatadisabled©show_logsîskip_as_script§cell_id$a5b20939-9afa-48c0-aa67-cbca6bc99804code_foldedäcodemd"## Cost of LLMs"$91abc03b-fef7-4f93-96fc-13f1cf654f0dmetadatadisabled©show_logsîskip_as_script§cell_id$91abc03b-fef7-4f93-96fc-13f1cf654f0dcode_foldedäcodetHAlign(
md"""
See the table below for the size of embeddings of large language models:
$(table(llms, mandatory_columns = ["``d_\\text{emb}``"], included_columns = [
"Name",
"Num params",
"Ref",
"``n_\\text{voc}``",
"``d_\\text{emb}``",
]))
""",
HTML(html(@draw begin
draw_transformer()
highlight(200, -160, 375, -110)
highlight(200, 490, 375, 565)
end 300 400));
)$79e6c4a8-cc1e-40cc-bb09-e9a7a9a8e475metadatadisabled©show_logsîskip_as_script§cell_id$79e6c4a8-cc1e-40cc-bb09-e9a7a9a8e475code_foldedäcodemd"## Transformer variations"$beccf4e8-1b01-4cb2-b23c-bc5db604f21cmetadatadisabled©show_logsîskip_as_script§cell_id$beccf4e8-1b01-4cb2-b23c-bc5db604f21ccode_foldedäcodemd"""
Given a sequence of ``n_\text{ctx}`` past vectors ``x_{-1}, \ldots, x_{-n_\text{ctx}} \in \mathbb{R}^{n}``, "predict" the next ones. Key idea : *receding horizon*:
```math
\begin{align}
& p(x_0, x_1 | x_{-1}, \ldots, x_{-n_\text{ctx}})\\
& = p(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})p(x_1 | x_0, x_{-1}, \ldots, x_{-n_\text{ctx}+1}, \textcolor{red}{x_{-n_\text{ctx}}})\\
& \approx p(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}}) p(x_{1} | x_0, x_{-1}, \ldots, x_{-n_\text{ctx}+1})
\end{align}
```
* **Model** : Probability of next vector ``\hat{p}(x_0 | X)`` where ``X`` concatenates ``x_{-1}, \ldots, x_{-n_\text{ctx}}``.
* **Loss** : Cross-entropy : ``\mathcal{L}_{\hat{p}}(X) \triangleq H(p, \hat{p}) = -\textbf{E}_p[\log(\hat{p})] = -\sum_{x_0} p(x_0 | X) \log(\hat{p}(x_0 | X))``
* Particular case for ``p(x_0 | X) = \delta_y`` : ``\mathcal{L}_{\hat{p}}(X) = -\log(\hat{p}(y | X))``
#### What about Language Models ?
Given "past text", predict the "following text". How to turn text into vectors of ``\mathbb{R}^n`` ?
"""$e41d13ca-1dc1-45ae-9fa6-a83c4101120dmetadatadisabled©show_logsîskip_as_script§cell_id$e41d13ca-1dc1-45ae-9fa6-a83c4101120dcode_foldedäcodebib(["bahdanau2016Neural"])$5058e4eb-c53d-4468-b7ff-4f04ded96418metadatadisabled©show_logsîskip_as_script§cell_id$5058e4eb-c53d-4468-b7ff-4f04ded96418code_foldedäcode@htl("""
Transformers in Large Language Models (LLMs)
Benoît Legat
$(PlutoTeachingTools.ChooseDisplayMode())
$(PlutoUI.TableOfContents(depth=1))
""")$5150d8f3-6e85-43f2-801a-eae5cc3e3095metadatadisabled©show_logsîskip_as_script§cell_id$5150d8f3-6e85-43f2-801a-eae5cc3e3095code_foldedäcodeHAlign(
md"""
`softmax` is then applied to each **column**:
```math
\text{softmax}(K^\top Q/\sqrt{d_k})
```
Division by ``\sqrt{d_k}`` scales the input of softmax to
preferable regions $(cite("vaswani2017Attentiona", "Secton 3.2.1")).
Illustrated on the right from $(cite("bahdanau2016Neural", "Figure 3(a)")).
```math
\text{Attention}(V, K, Q) = V\text{softmax}(K^\top Q/\sqrt{d_k})
```
""",
img("attention_matrix"),
)$8c27b182-0c3c-4c19-9619-df62b7dd6bf0metadatadisabled©show_logsîskip_as_script§cell_id$8c27b182-0c3c-4c19-9619-df62b7dd6bf0code_foldedäcodeMHAlign(
md"""
💡 **Key idea** In the model for ``\hat{p}(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})``, incorporate sub-models
```math
\begin{align}
\bar{p}(&x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})\\
\bar{p}(&x_{-1} | x_{-2}, \ldots, x_{-n_\text{ctx}})\\
& \quad\qquad\vdots\\
\bar{p}(&x_{-n_\text{ctx}+1} | x_{-n_\text{ctx}}).
\end{align}
```
""",
md"""
Mask prevents ``\hat{p}`` to look at inputs in the future:
```math
M
=
\begin{bmatrix}
0 & 0 & \cdots & 0\\
-\infty & 0 & \ddots & \vdots\\
\vdots & \ddots & \ddots & 0\\
-\infty & \cdots & -\infty & 0
\end{bmatrix}
```
""",
)$9a8eef1b-27c0-4d57-a389-53708ade9058metadatadisabled©show_logsîskip_as_script§cell_id$9a8eef1b-27c0-4d57-a389-53708ade9058code_foldedäcodemd"""
Let ``\hat{Y}_{i}`` be the intermediate output of ``i \in \{1, \ldots, N\}``.
The columns of the matrix ``\text{softmax}(C^\top \hat{Y}_i)`` (column-wise softmax) can be thought as intermediate probabilities that we denote ``\hat{p}_i``:
```math
(\hat{p}_i(x_{-n_\text{ctx}+1} | x_{-n_\text{ctx}}), \ldots, \hat{p}_i(x_{-1} | x_{-2}, \ldots, x_{-n_\text{ctx}}), \hat{p}_i(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}}))
```
and we predict the next token using ``\hat{p}_N(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})``.
"""$f39305ea-f7f5-440e-ac55-c83e27f6e7fcmetadatadisabled©show_logsîskip_as_script§cell_id$f39305ea-f7f5-440e-ac55-c83e27f6e7fccode_folded¤codellms = load_llms()$f7ca738d-5215-4e91-a2f3-a5ff10911313metadatadisabled©show_logsîskip_as_script§cell_id$f7ca738d-5215-4e91-a2f3-a5ff10911313code_foldedäcodebib("sutskever2014Sequence")$c7f318b9-30e6-4b79-b7da-52f70904d246metadatadisabled©show_logsîskip_as_script§cell_id$c7f318b9-30e6-4b79-b7da-52f70904d246code_folded¤code٠function substitute(text::String, pair::Tuple{Char,Char})
new_char = min('Z' + 1, minimum(text)) - 1
return replace(text, prod(pair.first) => pair.second)
end$4dd7083a-e730-4f4b-bde8-fc1a5b08ebfcmetadatadisabled©show_logsîskip_as_script§cell_id$4dd7083a-e730-4f4b-bde8-fc1a5b08ebfccode_foldedäcode@bib(["he2016Identity", "radford2019Language", "su2023RoFormer"])$8b78360a-21cb-4574-a84d-46ea4d0cedb1metadatadisabled©show_logsîskip_as_script§cell_id$8b78360a-21cb-4574-a84d-46ea4d0cedb1code_foldedäcodeimg("sutskever2014Sequence")$95ec4140-9147-11ef-2af4-5528bad0e6f5metadatadisabled©show_logsîskip_as_script§cell_id$95ec4140-9147-11ef-2af4-5528bad0e6f5code_foldedäcode"md"# Large Language Models (LLMs)"$77f446ac-6030-48f2-9bea-93c427f9fcb9metadatadisabled©show_logsîskip_as_script§cell_id$77f446ac-6030-48f2-9bea-93c427f9fcb9code_folded¤codeٻfunction softmax_lookup(dict, query)
ks = keys(dict)
α = softmax([dot(query, key) for key in keys(dict)])
@show α
return sum(α * value for (α, value) in zip(α, values(dict)))
end$d05e6f0f-0081-4fb6-91e9-ac2f58beda4ametadatadisabled©show_logsîskip_as_script§cell_id$d05e6f0f-0081-4fb6-91e9-ac2f58beda4acode_foldedäcodemd"# Decoder-only transformer"$d54b5390-0ec0-4ff8-ab18-51726482ca46metadatadisabled©show_logsîskip_as_script§cell_id$d54b5390-0ec0-4ff8-ab18-51726482ca46code_foldedäcodemd"## Extensions of RNNs"$f572e113-b36b-4a6b-96c7-c26f100e1ad4metadatadisabled©show_logsîskip_as_script§cell_id$f572e113-b36b-4a6b-96c7-c26f100e1ad4code_foldedäcodemd"## Utils"$c3db7eb2-356a-428f-9777-6369662d8b06metadatadisabled©show_logsîskip_as_script§cell_id$c3db7eb2-356a-428f-9777-6369662d8b06code_foldedäcodeOmd"""
Note that the new tokens can also be part of the most frequence pair!
"""$a21fbc70-9137-4d0e-8c8c-cbdc5269778fmetadatadisabled©show_logsîskip_as_script§cell_id$a21fbc70-9137-4d0e-8c8c-cbdc5269778fcode_foldedäcodemd"""
Recently, Mamba suggests a solution to the complexity issue $(cite("gu2024Mamba")). As it scales better with ``n_\text{ctx}``, it is even suggested to get rid of the tokenizer : $(cite("wang2024MambaByte")).
"""$9e898325-e9e2-45bd-af74-3dd86f00f7b5metadatadisabled©show_logsîskip_as_script§cell_id$9e898325-e9e2-45bd-af74-3dd86f00f7b5code_foldedäcode md"""
Consider one-hot encoding with vocabulary size ``n_\text{voc}`` and a *bigram model*
```math
\hat{p}(x_0 | x_{-1}) = \text{softmax}(W_d \tanh(\cdots\tanh(W_1 x_{-1})\cdots)
```
The matrix ``W_d`` has ``n_\text{voc}`` rows and ``W_1`` has ``n_\text{voc}`` columns → issue if ``n_\text{voc}`` is large
**Embedding** : Use vectors ``c_1, \ldots, c_{n_\text{voc}} \in \mathbb{R}^{d_\text{emb}}`` with *embedding size* (aka *hidden size*) ``d_\text{emb} \ll n_\text{voc}``.
Equivalently, we still use one-hot encoding but we add an encoder
``C \in \mathbb{R}^{d_\text{emb} \times n_\text{voc}}`` and decoder ``D \in \mathbb{R}^{n_\text{voc} \times d_\text{emb}}``
```math
\hat{p}(x_0 | x_{-1}) = \text{softmax}(D W_d \tanh(\cdots\tanh(W_1 C x_{-1})\cdots)
```
"""$97463c54-7cc7-4497-a8a6-6422f5f582bdmetadatadisabled©show_logsîskip_as_script§cell_id$97463c54-7cc7-4497-a8a6-6422f5f582bdcode_foldedäcodeٵbib(["team2024Gemini", "team2024Geminia", "team2024Gemma", "team2024Gemmaa", "sennrich2016Neural", "radford2019Language", "brown2020Language", "touvron2023Llama", "yu2023MEGABYTE"])$8eafcfed-9771-4d99-b0c5-bd75a6dab012metadatadisabled©show_logsîskip_as_script§cell_id$8eafcfed-9771-4d99-b0c5-bd75a6dab012code_foldedäcodelbib(["cho2014Properties", "graves2014Generating", "goodfellow2016Deep", "gu2024Mamba", "wang2024MambaByte"])$89305cae-098f-4644-9109-d00f1e3bc04cmetadatadisabled©show_logsîskip_as_script§cell_id$89305cae-098f-4644-9109-d00f1e3bc04ccode_folded¤codefunction pair_stats(text::String)
stats = Dict{Tuple{Char,Char},Int}()
for i in eachindex(text)
j = nextind(text, i)
if j > lastindex(text)
break
end
a = text[i]
b = text[j]
stats[(a, b)] = get(stats, (a, b), 0) + 1
end
return stats
end$bcf7667f-f99b-4d10-af84-5d3879f1db5dmetadatadisabled©show_logsîskip_as_script§cell_id$bcf7667f-f99b-4d10-af84-5d3879f1db5dcode_foldedäcodeqa(
html"What difference do you expect with respect to the previous model ?",
md"""
The products ``W_1C`` and ``DW_d`` have the same dimension as the matrices ``W_1`` and ``W_d`` of the previous model. So the expressive power of the model was not improved while we increased the number of parameters and we potentially made the loss function "even more nonconvex".
If the hidden dimension (i.e., the number of rows of ``C`` / columns of ``W_1`` or the number of rows of ``W_d`` / columns of ``D``) is much smaller than ``n_\text{voc}``, then it's faster to compute ``W_1(Cx)``. Moreover, we are forcing the matrix ``W_1C`` to have a low rank compared the model without ``C``. This means less expressivness but it might also prevent overfitting so the case isn't so clear.
The case become clearer when the input embedding ``C`` is shared between more than one character, i.e., ``n_\text{ctx} > 1``.
Same for the output embedding, ``D`` is useful when it is not preceded by a linear with which it can just be merged.
""")$25b79953-fd7c-46c1-b760-d57c09910981metadatadisabled©show_logsîskip_as_script§cell_id$25b79953-fd7c-46c1-b760-d57c09910981code_foldedäcode+qa(md"""
How does the number of parameters of transformers compare with $(cite("bengio2000Neural")) or RNNs for large ``n_\text{ctx}`` ?
""",
md"""
* The number of parameters of the transformer does **not** depend on ``n_\text{ctx}``.
* The number of parameters of $(cite("bengio2000Neural")) depends linearly with ``n_\text{ctx}``. Assuming that the number of hidden neurons scales proportionally with ``n_\text{ctx}``, the number of parameters even scales quadratically with ``n_\text{ctx}``!
* For RNNs, if the dimension of the internal state scales proportionally with ``n_\text{ctx}``, the number of parameters is also proportional with ``n_\text{ctx}``! If the dimension of the internal state is kept too small, increasing the context won't be so helpful, due to *encoder bottleneck*, see next slide.
""")$c032b3ff-c539-4e38-81d0-39b28b3a8076metadatadisabled©show_logsîskip_as_script§cell_id$c032b3ff-c539-4e38-81d0-39b28b3a8076code_foldedäcode4bib(["bahdanau2016Neural", "vaswani2017Attentiona"])$45efc71d-d5f8-474e-9b89-e72fac7110fdmetadatadisabled©show_logsîskip_as_script§cell_id$45efc71d-d5f8-474e-9b89-e72fac7110fdcode_foldedäcodebib("bengio2000Neural")$d050a7ee-3aa7-4539-a236-5b6446599dedmetadatadisabled©show_logsîskip_as_script§cell_id$d050a7ee-3aa7-4539-a236-5b6446599dedcode_folded¤code@struct BPE
text::String
pairs::Dict{Tuple{Char,Char},Char}
end$579a203b-e6f7-4190-b874-18b00a5c3f77metadatadisabled©show_logsîskip_as_script§cell_id$579a203b-e6f7-4190-b874-18b00a5c3f77code_folded¤codeAfunction load_llms()
llms = DataFrame(CSV.File("llms.csv"))
rename!(llms, "Embedding dimension" => "``d_\\text{emb}``")
rename!(llms, "Vocabulary size" => "``n_\\text{voc}``")
rename!(llms, "Context window" => "``n_\\text{ctx}``")
rename!(llms, "Feed-Forward hidden dimension" => "``d_\\text{ff}``")
return llms
end$570fa160-3adb-463e-99b8-b7dd05076908metadatadisabled©show_logsîskip_as_script§cell_id$570fa160-3adb-463e-99b8-b7dd05076908code_folded¤code7function softmax(x)
y = exp.(x)
return y / sum(y)
end$9cb90e76-3bb5-41ff-bc79-c4949400d904metadatadisabled©show_logsîskip_as_script§cell_id$9cb90e76-3bb5-41ff-bc79-c4949400d904code_foldedäcodemd"""
With ``n_\text{ctx} > 1``, the encoder ``C`` is shared by all tokens:
See for instance the network below taken from $(cite("bengio2000Neural", "Figure 1")), the first popular application of neural nets for languages:
"""$75ca478c-916f-464a-9435-8208ee726d50metadatadisabled©show_logsîskip_as_script§cell_id$75ca478c-916f-464a-9435-8208ee726d50code_foldedäcodeSbib(["team2024Gemma", "team2024Gemmaa", "radford2019Language", "touvron2023Llama"])$b9caae1a-38aa-4d01-9cda-3d6782fb0e03metadatadisabled©show_logsîskip_as_script§cell_id$b9caae1a-38aa-4d01-9cda-3d6782fb0e03code_foldedäcodeHAlign(md"""
*Self-Attention* with embedding ``C`` is:
```math
\text{Masked-MultiHead}(CX, CX, CX)
```
The embedding vectors ``CX`` take then different projections
for value, key, query and also for different heads!
```math
\text{head}_j = \text{Masked-Attention}(W_j^VCX, W_j^KCX, W_j^QCX)
```
""",
HTML(html(@draw begin
draw_transformer()
highlight(200, 250, 375, 350)
end 300 400)),
)$9ff95a9a-192b-4a12-8e2e-7acd6659c066metadatadisabled©show_logsîskip_as_script§cell_id$9ff95a9a-192b-4a12-8e2e-7acd6659c066code_foldedäcodemd"""
```math
\begin{align}
Q & = \begin{bmatrix}
q_1 & \cdots & q_{n_\text{ctx}}
\end{bmatrix} &
K & = \begin{bmatrix}
k_1 & \cdots & k_{n_\text{ctx}}
\end{bmatrix} &
K^\top Q & =
\begin{bmatrix}
\langle k_1, q_1 \rangle & \cdots & \langle k_1, q_{n_\text{ctx}} \rangle\\
\vdots & \ddots & \vdots\\
\langle k_{n_\text{ctx}}, q_1 \rangle & \cdots & \langle k_{n_\text{ctx}}, q_{n_\text{ctx}} \rangle
\end{bmatrix}
\end{align}
```
"""$f95a6de6-5e02-4237-88ba-ec44ef3d38c3metadatadisabled©show_logsîskip_as_script§cell_id$f95a6de6-5e02-4237-88ba-ec44ef3d38c3code_foldedäcodeKHAlign(
md"""
Different weights
``W_1 \in \mathbb{R}^{d_\text{ff} \times d_\text{emb}}``, ``W_2 \in \mathbb{R}^{d_\text{emb} \times d_\text{ff}}`` for each layer:
```math
x \mapsto W_2\max(0, W_1x + b_1) + b_2
```
Expansion factor ``d_\text{ff} / d_\text{emb}`` is typically 4× like suggested in $(cite("vaswani2017Attentiona")) (but not for Gemma)
$(table(llms, mandatory_columns = ["``d_\\text{ff}``"], included_columns = [
"Name",
"Ref",
"``d_\\text{emb}``",
"``d_\\text{ff}``",
]))
""",
HTML(html(@draw begin
draw_transformer()
highlight(200, -45, 375, 25)
end 300 400)),
)$ed5b5702-4cca-4116-a70f-4a562178f490metadatadisabled©show_logsîskip_as_script§cell_id$ed5b5702-4cca-4116-a70f-4a562178f490code_foldedäcodemd"""
> **Challenging tradeoff**: Encode text to **increase** length of "past text" while keeping ``n_\text{ctx}`` and ``n`` **small** enough.
Length of "past text" increases with vocabulary size ``n_\text{voc}`` and context window ``n_\text{ctx}``.
"""$736920df-e4bb-4535-b982-e397aa0a782dmetadatadisabled©show_logsîskip_as_script§cell_id$736920df-e4bb-4535-b982-e397aa0a782dcode_folded¤codeiter_2 = new_token(iter_1)$55a09acc-84da-491c-86ba-9a66f4ea52femetadatadisabled©show_logsîskip_as_script§cell_id$55a09acc-84da-491c-86ba-9a66f4ea52fecode_foldedäcodeHAlign(
md"""
```math
\begin{align}
h^{(t+1)} & = \tanh(Wh^{(t)} + Ux^{(t+1)} + b)\\
o^{(t)} &= Vh^{(t)} + c\\
\hat{y}^{(t)} &= \text{softmax}(o^{(t)})
\end{align}
```
Illustrated on the right $(cite("goodfellow2016Deep", "Figure 10.3")).
RNNs as language model showcased in $(cite("mikolov2010Recurrent")).
**Issue**: Training time and space complexity is proportional to ``n_\text{ctx}`` and **cannot parallelize** to speed up.
""",
img("RNN")
)$d558636d-c714-4033-ae73-5b92c3cdedf3metadatadisabled©show_logsîskip_as_script§cell_id$d558636d-c714-4033-ae73-5b92c3cdedf3code_folded¤code0dict = Dict([1, 0] => [1, 1], [0, 1] => [-1, 1])$8d231f2c-4b0c-4c37-a746-16e98d4cafc8metadatadisabled©show_logsîskip_as_script§cell_id$8d231f2c-4b0c-4c37-a746-16e98d4cafc8code_foldedäcodemd"## Attention head"$f1afaf8c-d9ad-446a-9826-9c4cda19993fmetadatadisabled©show_logsîskip_as_script§cell_id$f1afaf8c-d9ad-446a-9826-9c4cda19993fcode_folded¤code6new_token(text::String) = new_token(BPE(text, Dict()))$f7ca3ff7-b5cf-452b-b955-7219e7397324metadatadisabled©show_logsîskip_as_script§cell_id$f7ca3ff7-b5cf-452b-b955-7219e7397324code_folded¤code!iter_1 = new_token("aaabdaaabac")$5f05e717-a51a-4a99-bb11-cc493217f93fmetadatadisabled©show_logsîskip_as_script§cell_id$5f05e717-a51a-4a99-bb11-cc493217f93fcode_foldedäcoderHAlign(
md"""
Norm of gradient increases exponentially with depth.
Issue for deep neural net.
Consider output
```math
\begin{bmatrix}
y_{1,1} & \ldots & y_{1,d_\text{emb}}\\
\vdots & \ddots & \vdots\\
y_{d_\text{batch},1} & \ldots & y_{d_\text{batch},d_\text{emb}}
\end{bmatrix}
```
Normalization : ``y_{i,j} \mapsto g(y_{i,j} - \mu_{i,j})/\sigma_{i,j}`` for gain ``g``, mean ``\mu`` and standard deviation ``\sigma``.
* Batch normalization : ``\sigma_{i,j} = \sigma_{j}`` $(cite("ioffe2015Batch"))
* Layer normalization : ``\sigma_{i,j} = \sigma_{i}`` $(cite("ba2016Layer"))
Batch norm depends on the batch hence [is tricky to implement](https://www.youtube.com/watch?v=P6sfmUTpUmc). Layer normalization is used in $(cite("vaswani2017Attentiona")).
""",
HTML(html(@draw begin
draw_transformer()
highlight(290, -85, 360, -45)
highlight(290, 210, 360, 250)
end 300 400))
)$b56e9e56-e74a-401b-b4b5-f36bb33341d5metadatadisabled©show_logsîskip_as_script§cell_id$b56e9e56-e74a-401b-b4b5-f36bb33341d5code_foldedäcodebib(["he2015Deep"])$57c2c944-0d91-489d-8ad7-f5520e71ef3emetadatadisabled©show_logsîskip_as_script§cell_id$57c2c944-0d91-489d-8ad7-f5520e71ef3ecode_foldedäcodemd"## Byte Pair Encoding"$bf563783-9784-4c74-a7b1-6d7a3ed618c5metadatadisabled©show_logsîskip_as_script§cell_id$bf563783-9784-4c74-a7b1-6d7a3ed618c5code_foldedäcodemd"## Matrix form of attention"$f8330700-e964-4e19-9c55-2b11df45789emetadatadisabled©show_logsîskip_as_script§cell_id$f8330700-e964-4e19-9c55-2b11df45789ecode_foldedäcodemd"## Embedding sizes in LLMs"$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0ecmetadatadisabled©show_logsîskip_as_script§cell_id$8d6ec2b3-997e-4df5-a3b2-c1dffa53d0eccode_foldedäcodeqa(
md"What is the time complexity of inference with respect to ``d_\text{emb}``, ``n_\text{voc}``, ``n_\text{ctx}``, ``d_\text{ff}``, ``h`` and ``N`` ?",
HAlign(
md"""
| Input | Parameters | Time |
|-------|------------|------|
| ``CX + P \in \mathbb{R}^{d_\text{emb} \times n_\text{ctx}}`` | ``W_j^V \in \mathbb{R}^{d_v \times d_\text{emb}}`` | ``O(d_v d_\text{emb} n_\text{ctx})`` |
| ``CX + P \in \mathbb{R}^{d_\text{emb} \times n_\text{ctx}}`` | ``W_j^K, W_j^Q \in \mathbb{R}^{d_k \times d_\text{emb}}`` | ``O(d_k d_\text{emb} n_\text{ctx})`` |
| ``K, Q \in \mathbb{R}^{d_k \times n_\text{ctx}}`` | | ``O(d_k n_\text{ctx}^2)`` |
| ``V \in \mathbb{R}^{d_v \times n_\text{ctx}}, ... \in \mathbb{R}^{n_\text{ctx} \times n_\text{ctx}}`` | | ``O(d_v n_\text{ctx}^2)`` |
| ``... \in \mathbb{R}^{d_v \times n_\text{ctx}}`` | ``W^O \in \mathbb{R}^{d_\text{emb} \times d_v}`` | ``O(d_\text{emb} d_v n_\text{ctx})`` |
| ``... \in \mathbb{R}^{d_\text{emb} \times n_\text{ctx}}`` | ``W_1 \in \mathbb{R}^{d_\text{ff} \times d_\text{emb}}`` | ``O(d_\text{emb} d_\text{ff} n_\text{ctx})`` |
| ``... \in \mathbb{R}^{d_\text{ff} \times n_\text{ctx}}`` | ``W_2 \in \mathbb{R}^{d_\text{emb} \times d_\text{ff}}`` | ``O(d_\text{emb} d_\text{ff} n_\text{ctx})`` |
So for ``N`` layers (ignoring the complexity of the embedding):
```math
O(Nn_\text{ctx}(n_\text{ctx}(d_v + d_k) + d_\text{emb}(d_v+d_k+d_\text{ff})))
```
Assuming that ``d_v, d_k, d_\text{ff}`` has the same scale as ``d_\text{emb}``:
```math
O(Nn_\text{ctx}^2d_\text{emb} + Nn_\text{ctx}d_\text{emb}^2)
```
""",
HTML(html(@draw begin
draw_transformer()
translate(-10, 150)
scale(0.6)
Luxor.placeimage(readpng("images/multi-head.png"), centered = true)
end 300 400))
)
)$d1ba8da3-add8-4dbe-9ebf-9a32fa5cd5ddmetadatadisabled©show_logsîskip_as_script§cell_id$d1ba8da3-add8-4dbe-9ebf-9a32fa5cd5ddcode_foldedäcodeHAlign(
md"""
*Pre-activation* for residual neural networks introduced in $(cite("he2016Identity")) and used in GPT-2 $(cite("radford2019Language")). See figure on the right.
*Rotary Positional Encoding* $(cite("su2023RoFormer")) replaces
``W^K(Cx_i + p_i)`` and ``W^Q(Cx_i + p_i)``
by ``R^i W^KCx_i`` and ``R^i W^QCx_i`` where ``R`` is a rotation matrix.
Advantage : ``\langle k_i, q_j \rangle`` contains ``R^{i - j}`` → **relative** difference of position.
""",
HTML(html(@draw begin
draw_transformer()
sethue("blue")
scale(2, 2)
arrow(Point(175, -36), Point(180, -43), Point(170, -48), Point(145, -53), :stroke, startarrow=false, finisharrow=true)
arrow(Point(175, -30), Point(190, -10), Point(195, 10), Point(145, 17), :stroke, startarrow=false, finisharrow=true)
arrow(Point(175, 120), Point(190, 130), Point(195, 150), Point(145, 192), :stroke, startarrow=false, finisharrow=true)
end 300 400)),
)$1d5b1b7c-828c-4a16-b446-cff21b015d45metadatadisabled©show_logsîskip_as_script§cell_id$1d5b1b7c-828c-4a16-b446-cff21b015d45code_folded¤codebiblio = load_biblio!()$a14e505e-2e4a-4c73-8133-7560ba58916bmetadatadisabled©show_logsîskip_as_script§cell_id$a14e505e-2e4a-4c73-8133-7560ba58916bcode_foldedäcodemd"## Key-Value (KV) cache"$2a7e5096-1e8d-4506-96d2-86de0a7d39aametadatadisabled©show_logsîskip_as_script§cell_id$2a7e5096-1e8d-4506-96d2-86de0a7d39aacode_foldedäcodeٖmd"""
Forcing ``D = C^\top`` appears to work well in practice $(cite("press2017Using")), this is what is used in $(cite("vaswani2017Attentiona")).
"""$6712c883-b407-47e1-a666-4de05f8f8d6emetadatadisabled©show_logsîskip_as_script§cell_id$6712c883-b407-47e1-a666-4de05f8f8d6ecode_foldedäcodeHAlign(
md"""
```math
\begin{multline}
\hat{p}(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}}) = \\
\text{softmax}(W_2 \tanh(W_1
\begin{bmatrix}
C x_{-1}\\
\vdots\\
C x_{-n_\text{ctx}}
\end{bmatrix}
))
\end{multline}
```
""",
img("bengio2000Neural", :width => 250),
)$af8194a1-a358-4cf7-b446-6b377cb76687metadatadisabled©show_logsîskip_as_script§cell_id$af8194a1-a358-4cf7-b446-6b377cb76687code_foldedäcode md"The feed-forward network is implemented **independently** for the output of each query so each query can be processed independently through each **layer**. The next layer allows each queries to then look at the results of the previous layer for **past** (because of the mask) queries."$04e9b912-6712-4290-acc4-f24bb27a1469metadatadisabled©show_logsîskip_as_script§cell_id$04e9b912-6712-4290-acc4-f24bb27a1469code_foldedäcodemd"## Machine translation"$d014e6aa-92f6-4ca1-be47-516565d1bb20metadatadisabled©show_logsîskip_as_script§cell_id$d014e6aa-92f6-4ca1-be47-516565d1bb20code_foldedäcodeHAlign((
md"""
Heads focus on different aspects. Their outputs are **combined** with ``W^O \in \mathbb{R}^{d_\text{emb} \times hd_v}``:
```math
\begin{align}
\text{head}_j & = \text{Attention}(W_j^VV, W_j^KK, W_j^QQ)\\
\text{MultiHead}(V, K, Q)
& =
W^O\text{vcat}(\text{head}_1, \ldots, \text{head}_h)
\end{align}
```
See $(cite("vaswani2017Attentiona", "Figure 2")) on the right.
Similarly, in the masked case:
```math
\begin{align}
\text{head}_j & = \text{Masked-Attention}(W_j^VV, W_j^KK, W_j^QQ)\\
\text{Masked-MultiHead}&(V, K, Q)
=
W^O\text{vcat}(\text{head}_1, \ldots, \text{head}_h)
\end{align}
```
""",
img("multi-head", :width => 250)),
[70, 30],
)$4df0a18d-cb14-41b1-ba40-fd6bfcbb0b03metadatadisabled©show_logsîskip_as_script§cell_id$4df0a18d-cb14-41b1-ba40-fd6bfcbb0b03code_foldedäcode4bib(["sennrich2016Neural", "kudo2018SentencePiece"])$e2eca085-9f99-4e3a-9db4-e7f692aedd34metadatadisabled©show_logsîskip_as_script§cell_id$e2eca085-9f99-4e3a-9db4-e7f692aedd34code_foldedäcode-md"## Text to vectors : step 2 → embedding"$95504a74-d5ef-4fb7-83a0-88914c7cbc59metadatadisabled©show_logsîskip_as_script§cell_id$95504a74-d5ef-4fb7-83a0-88914c7cbc59code_folded¤code"numerical_lookup(dict, [0.8, 0.2])$453544fc-0e3e-4e04-8c0c-192f3a038884metadatadisabled©show_logsîskip_as_script§cell_id$453544fc-0e3e-4e04-8c0c-192f3a038884code_foldedäcodemd"## Positional encoding"$0583ee0c-3802-4e81-b179-a80a82493b43metadatadisabled©show_logsîskip_as_script§cell_id$0583ee0c-3802-4e81-b179-a80a82493b43code_foldedäcodemd"""
Byte Pair Encoding algorithm $(cite("sennrich2016Neural")) greedily merges the most frequent pair of tokens over the dataset into a new token.
Most used implementations are `SentencePiece` $(cite("kudo2018SentencePiece")) and `tiktoken` (play with it [here](https://tiktokenizer.vercel.app/)). For instance, on [this example](https://en.wikipedia.org/wiki/Byte_pair_encoding), the pair `('a', 'a')` is the most frequent so we substitute it by a new token, say `'Z'`:
"""$728f5fdf-77a5-46c7-b3ee-01064ef1b7e2metadatadisabled©show_logsîskip_as_script§cell_id$728f5fdf-77a5-46c7-b3ee-01064ef1b7e2code_foldedäcodeqa(md"Should we discard all these intermediate ``\hat{Y}_i`` we computated or can we reuse it for the following token ?",
md"""
For the next token, the corresponding intermediate probabilities would be:
```math
(\hat{p}_i(x_{-n_\text{ctx}+2} | x_{-n_\text{ctx}+1}), \ldots, \hat{p}_i(x_{0} | x_{-1}, \ldots, x_{-n_\text{ctx}+1}), \hat{p}_i(x_1 | x_{0}, \ldots, x_{-n_\text{ctx}+1}))
```
Note that
```math
\begin{align}
\hat{p}_i(x_{-n_\text{ctx}+2} | x_{-n_\text{ctx}+1})
& \approx
\hat{p}_i(x_{-n_\text{ctx}+2} | x_{-n_\text{ctx}+1}, x_{-n_\text{ctx}})\\
\hat{p}_i(x_{0} | x_{-1}, \ldots, x_{-n_\text{ctx}+1})
& \approx
\hat{p}_i(x_0 | x_{-1}, \ldots, x_{-n_\text{ctx}})
\end{align}
```
So for any ``j < n_\text{ctx}``, the ``j``th column of the ``\hat{Y}_i'`` that should be computed for the new token is approximately equal to
the ``(j+1)``th column of ``\hat{Y}_i`` that we already computed for the previous token.
What's more, the column of ``\hat{Y}_i`` was computed with one more token as context compared to what we need to compute in ``\hat{Y}_i'``.
So even though it's not equal, reusing what we computed in ``\hat{Y}_i`` should provide better result, assuming the trained transformers using this auto-regressive structure in his layers.
""")$01372b00-ecb2-42bd-b408-13234717d969metadatadisabled©show_logsîskip_as_script§cell_id$01372b00-ecb2-42bd-b408-13234717d969code_folded¤codeٰfunction new_token(bpe::BPE)
stats = pair_stats(bpe.text)
pair = findmax(stats)[2]
new_char = min('Z' + 1, minimum(bpe.text)) - 1
return add_pair(bpe, pair => new_char)
end$f4366cf6-2be0-42b8-96c4-120be3f5c25emetadatadisabled©show_logsîskip_as_script§cell_id$f4366cf6-2be0-42b8-96c4-120be3f5c25ecode_foldedäcodemd"""
### References
* Recurrent neural networks : $(cite("goodfellow2016Deep", "Chapter 10")) and Section 4.7 of [The Elements of Differentiable Programming book](https://diffprog.github.io/)
* Transformers : $(cite("vaswani2017Attentiona")) and Section 4.8 of [The Elements of Differentiable Programming book](https://diffprog.github.io/)
* [Neural Networks: Zero to Hero](https://karpathy.ai/zero-to-hero.html) by Andrej Karpathy
"""$c8923675-e73e-4621-82b9-966d8b003b97metadatadisabled©show_logsîskip_as_script§cell_id$c8923675-e73e-4621-82b9-966d8b003b97code_foldedäcode!md"# Encoder-decoder transformer"last_hot_reload_time shortpathtransformers.jlnbpkgbusy_packages,waiting_for_permission_but_probably_disabled§enabledðterminal_outputsHypertextLiteral
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...MathTeXEngine
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...Luxor
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...PrettyTables
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...LaTeXStrings
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...DocumenterCitations
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...nbpkg_sync
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...CSV
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...Logging
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...PlutoUI
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...LinearAlgebra
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...DataFrames
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...PlutoTeachingTools
[0m[1mResolving...[22m
[90m===[39m
[36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Project.toml`
[36m[1m Manifest[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ctnkygpefy/Manifest.toml`
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mPrecompiling...[22m
[90m===[39m
Waiting for notebook process to start... Done. Starting precompilation...waiting_for_permission·restart_recommended_msgrestart_required_msginstalled_versionsHypertextLiteral1.0.0MathTeXEngine0.6.9DataFrames1.8.2PrettyTables3.4.8LaTeXStrings1.4.1!__internal_julia_manifest_version1.13.0DocumenterCitations1.5.0CSV1.0.0LoggingstdlibPlutoUI0.7.83LinearAlgebrastdlib__internal_julia_version1.13.0Luxor4.5.0PlutoTeachingTools0.4.7install_time_ns0instantiatedípluto_versionv1.0.3 
persist_js_state$95ec4140-9147-11ef-2af4-5528bad0e6f5running§runtime depends_on_skipped_cellsµpublished_object_keyserrored§cell_id$95ec4140-9147-11ef-2af4-5528bad0e6f5depends_on_disabled_cells¦queued¤logsoutputmimetext/htmlrootassigneelast_run_timestampAڪ:has_pluto_hook_features¤bodyt
