COMP10002 算法基础

作业 1

本作业规范的网页优先版本。你可以直接从头到尾阅读本页面；链接的说明文档仅在你需要更多直觉理解时参考。如果本主页与链接的说明文档之间存在任何不一致，本页面很可能是正确信息，因此除非另有说明，请将其他页面视为补充材料。

2026 年第一学期截止时间：2026 年 4 月 27 日（周一）澳大利亚东部标准时间下午 6 时版本：1.1

重要声明

本翻译版本内容版权来自墨尔本大学仅提供给Shaanan Cohney 的26S1届 Foundations of Algorithms (COMP10002) 学生使用
原版链接:https://gateway.cohney.info/foa/2026s1/assignment1
感谢支持！部分中文翻译没有人工审查可能有误

更新日志

V1.1：明确说明复杂度分析应以 n 、 d 、 g 和 text_len 为单位进行表述。
V1.0：初始发布

重要说明

提交单个文件： a1.c ，通过 gradescope 提交。
从 Edstem 上提供的可下载模板开始，填写 TODO 函数。
不要更改阶段标题行或打印辅助函数。
不要添加额外的 printf 调试输出。
您的代码必须能在评分系统上编译，否则测试用例部分将无法运行。

编译错误至关重要

由于测试用例的Score是自动评分的，您的程序必须能在评分系统上成功编译。如果无法编译，程序将无法运行，您的正确性得分将为零。

如何使用本页面

你可以像阅读作业说明书一样从上到下阅读本页面。如果遇到 softmax、projection 或 KV cache 等术语让你感到困惑，可以点击内联链接获取更深入的解释，然后再回到这里继续阅读。

可下载的 PDF

更喜欢可打印的版本？下载编译好的项目规格 PDF。它将本主规格、概念解释器以及可选的支持页面作为附录整合在一起。

这道作业是关于什么的？

本次作业的灵感来源于现代大型语言模型（LLMs）（如聊天机器人）的工作原理。

LLM 被训练用于预测序列中的下一个Token（token）。从概念上讲，给定一个Prompt，

{token}_{0}, {token}_{1}, \dots, {token}_{n - 1},

模型会为下一个Token ${token}_{n}$ Generate一个概率分布。

把它想象成自动补全：根据你目前输入的内容，接下来最可能出现的是什么？

真实 LLM 在高层次上会做什么

你不需要了解精确的机器学习细节，但真实的 LLM 大致会：

将文本分词为Token ID
查找TokenEmbedding
运行多个 Transformer 层
在这些层内使用注意力机制
在词汇表上GenerateScore
选择下一个Token，将其追加，然后重复此过程

本次作业的实际内容

你并非在实现一个完整的聊天机器人，而是在实现其内部使用的核心组件：一个简化的单头自注意力模块，以及最终的 KV cacheGenerate步骤。

如果你想在深入循环代码之前，先用通俗易懂的语言了解注意力机制的原理，请阅读注意力机制解析。

为使编程重点突出且便于测试：

你将从一个小型的第一阶段表示练习开始，将Token列表转换为独热Vector
后续的注意力阶段将直接使用所提供的Prompt和Generate的EmbeddingVector作为数值行
参数Matrix Wq 、 Wk 和 Wv 将直接以数值形式提供给你
你精确地计算注意力Score、权重和输出
你应用Mask规则和稳定的 softmax
你不需要预测英语单词

如果数学部分仍然感觉抽象，没关系。具体的实现要求将在下方明确说明，附带的解释页面会在你需要时帮助你建立直觉理解。

本次作业中数字的来源

真实的语言模型从文本开始，而非Matrix。大致流程如下：

将文本分割为Token（token）
将每个Token转换为EmbeddingVector
对这些Vector执行注意力机制，以构建具有上下文感知能力的输出
使用最终Vector来帮助预测下一个应出现的Token

本次作业仍做了大量简化，但它让你能够将表示思想与后续的注意力数学分开单独练习。你无需实现完整的分词器、Embedding表查找、词汇评分层或训练过程。

因此，本项目包含两个相关但独立的"注意力之前"部分：

在第一阶段中使用的一个简短Token列表，用于构建并打印独热编码Embedding表
后续注意力阶段所使用的Prompt及Generate的Embedding行

这意味着第一阶段是针对Token的热身表示练习，而第二至第六阶段则基于所提供的数值EmbeddingMatrix进行操作。

这意味着：

提示Matrix的每一行对应一个TokenEmbedding
n 是Prompt（prompt）的Token（token）数量
d 是每个EmbeddingVector（embedding vector）中的分量数量
Prompt中的各个位置仍然存在顺序关系，因此"较早的Token"和"较晚的Token"之间的区别是有意义的

注意力机制的核心任务是：对于某一位置，回顾所有允许查看的更早位置，判断哪些位置最为重要，并将这些位置的信息融合到一个新的输出行中。

一次完成全部任务

你的程序遵循一条连续的流水线：

从输入文件中读取Token列表、Mask、Embedding行以及参数Matrix
根据Token列表构建并打印第一阶段的独热编码Embedding
将提供的提示Embedding投影到查询Matrix、键Matrix和值Matrix中
将Prompt查询与Prompt键进行比较，以获得注意力Score
通过Mask和稳定 softmax 将这些Score转换为注意力权重
使用这些权重将值Vector混合为Prompt输出
将相同的逻辑扩展到Generate的Token，同时复用缓存的键和值

如果你牢记这条流水线，后续的各阶段描述应当被理解为一个算法的逐步构建过程，而非互不相关的独立任务。

各阶段的心智模型

在阅读各阶段内容时，请牢记以下思维模型：

一个Prompt位置最初只是"该Token的EmbeddingVector"
到第 5 阶段结束时，该行已变为"该Token，根据对其有意义的前序行重写后的结果"
第 6 阶段在Generate过程中应用相同的注意力机制，但复用已缓存的键和值，而非重新计算已有的工作

如果你在编写代码时迷失了方向，请回到这两个问题：

这个位置允许使用哪些之前的行？
每个允许使用的行对新输出行的贡献应该是多少？

在完整的模型中，这个模块周围还会有更多的机制，例如分词、Embedding查找、多个重复层以及最终的词汇评分步骤。在这里，你只需实现中间的注意力部分。

可选背景知识与视觉说明

如果你想了解更多背景知识、实例讲解或可视化说明，以下页面会对你有所帮助：

关于注意力机制、投影、Mask、softmax 及相关概念的解释
Transformer 解释器，提供对整体模型架构的单页概览
涵盖必读解释器以及可选演示、工具和背景页面的相关概念
《图解 Transformer》，以可视化方式介绍模型结构
《Attention Is All You Need》，即 Transformer 的原始论文

上述页面为本规范提供支持，无需提前阅读。

术语表与符号说明

本节汇集了帮助你阅读本作业所需的词汇和符号说明，供你在深入了解各阶段实现细节之前参考。提醒：所有术语没有汉化，所有的术语全部用英语避免歧义。

术语表

术语	含义
Token	一段文本，有时是一个完整的单词，有时是单词的一部分。
Prompt	在Generate新Token之前，您已有的起始Token。
Generate	在Prompt之后逐个Generate新Token。
Vector	一个固定长度的数字列表。在 C 语言中，是一个 `double` 的一维数组。
Matrix	一个数字表格。在 C 语言中，是一个 `double` 的二维数组。
Embedding	将Token表示为数字的Vector。
Dot product	将对应位置相乘后求和。
Score	一个表示一个Token与另一个Token相关程度的数值。
Softmax	将Score转换为总和为 1 的权重的函数。
Mask	一条表示"忽略此位置"的规则。
Causal mask	阻止第 `i` 行使用任何未来位置 `j > i` 的Mask。
Padding mask	忽略被标记为填充的提示位置的Mask，通常在 `mask[j] == 0` 处。
KV cache	Generate过程中存储的历史键值对。

符号与约定

在本规范中：

我们在描述数组时从 0 开始对标记编号，因此Prompt的索引为 $0, 1, \dots, n - 1$ 。
长度为 d 的Vector具有分量 $0, \dots, d - 1$ 。为清晰起见，我们将用粗体加箭头的形式表示Vector，并使用圆括号。
例如 $\vec{v} = (\begin{matrix} 1 & 2 \end{matrix})$ ，在 C 语言中对应的是 double v[] = {1 , 2} 。
为清晰起见，我们将用粗体表示Matrix，并使用方括号书写。
例如， $M = [\begin{matrix} 1 & 2 \end{matrix}]$ 在 C 中写作 double M[][] = { {1 , 2} } 。如果我们写 ${\vec{M}}_{i}$ ，表示 $M$ 中第 i 行对应的Vector，在 C 中即为 M[i] 。
” $\sum$ ” means “add up a bunch of terms” (like a loop). For example, $\sum_{t = 0}^{d - 1} a [t] \cdot b [t] = a [0] b [0] + \dots + a [d - 1] b [d - 1]$ means “for each t, multiply, then add the results”.
Matrix $Q$ 的下标 $Q i,t$ 表示"第 i 行，第 t 个分量"。在 C 中，即为 Q[i][t] 。
Masked 表示"视为不存在"：其权重必须为 0.0 ，在附加阶段 5 中，你不得为其计算Dot product。

Dot product、Vector与Matrix

若我们有Vector $\vec{a} = (\begin{matrix} 1 & 2 \end{matrix})$ 和 $\vec{b} = (\begin{matrix} 3 & 4 \end{matrix})$ ，则Dot product定义为

\vec{a} ∙ \vec{b} = (\begin{matrix} 1 & 2 \end{matrix}) ∙ (\begin{matrix} 3 & 4 \end{matrix}) = 1 \cdot 3 + 2 \cdot 4 = 11.

由于我们将使用Matrix进行运算，若能将Dot product定义为两个Matrix之间的Matrix乘法，将会更加便捷。Matrix乘法有意义的前提是：第一个Matrix的列数必须等于第二个Matrix的行数。所得Matrix的维度为第一个Matrix的行数乘以第二个Matrix的列数。在下面的情形中，结果为 1×1（即一个标量，恰好符合VectorDot product的要求）。

\vec{a} ∙ \vec{b} = a b^{T} = [\begin{matrix} 1 & 2 \end{matrix}] [\begin{matrix} 3 \\ 4 \end{matrix}]

根据Matrix乘法的标准规则，这与我们的Dot product结果相同。因此，这等价于第一个Matrix对应行Vector与第二个Matrix对应列Vector之间的Dot product。

在 C 语言中，我们的Matrix $a$ 和 $b$ 将分别是 double a_matrix[][] = { {1, 2} } 和 double b_matrix[] = { {3, 4} } 。那么 $b^{T}$ 就是二维Matrix double bT_matrix[][] = { {3}, {4} } 。这里 $b^{T}$ 表示 $b$ 的转置，转置的意思是"沿对角线翻转，使行变为列，列变为行"，这是确保Matrix乘法有意义所必需的。

请注意，我们无法像提取行Vector那样（例如使用 a_matrix[0] ）直接从 bT Matrix中提取"列Vector"，因此用Matrix运算来处理会更加方便。

在本次作业中，Dot product出现在Matrix形式的计算中，因此记住以下一点很有用：投影中的每个输出分量都是"一行与一列的Dot product"。

如果你需要帮助理解 Transformer 论文及后续论文中使用的紧凑符号表示，请阅读论文符号说明。如果你想了解行Vector乘以Matrix的可视化解释，请阅读投影说明。

入门指南

本节是快速设置说明：你拥有什么、模板已经完成了什么，以及在开始编码之前需要注意哪些约束条件。首先在 Edstem 上下载提供的模板。

你已获得

一个模板 a1.c ，其中包含可用的 main 和 TODO 函数
示例输入在 test_data/ 中
与 test_data/ 中的预期输出匹配

模板已经

打印所需的阶段标题和行格式
按正确顺序调用您的函数
以安全的最大尺寸分配数组

您应该

仅填写标有 /* TODO: ... */ 的函数
将所有数组保持在规定的最大容量以内
使用 double 进行计算
包含 <math.h> 并使用 -lm 进行编译

你不得

更改阶段标题行
添加额外输出
修改 print_vector

先检查模板代码

在开始编写代码之前，花一些时间熟悉 a1.c ：

已经存在哪些数组
每个函数的预期计算内容是什么
打印的内容

如何开始

首先阅读 a1.c ，然后按顺序实现各个阶段。

从 read_input(...) 开始 ，因为后续每个阶段都依赖于正确存储的输入。然后依次完成第 1 阶段的Embedding输出、第 2 阶段的投影计算、第 3 阶段的得分计算、第 4 阶段的权重计算、第 5 阶段的输出计算，最后是带有 KV cache的第 6 阶段Generate。

每完成一个阶段后，先编译并运行 test0 ，再继续下一阶段。

如果在编写代码时需要更多直觉性理解，请在相关内容出现时参阅对应的说明链接：Stage 1 对应独热编码，输入故事对应Token与Embedding，Stage 2 对应投影，Stage 3 对应Dot product与Mask，Stage 4 对应 softmax，Stage 5 对应注意力输出，Stage 6 对应 KV cache。

如果直接阅读 a1.c 本身会拖慢你的进度，请使用带注释的模板。函数会引入下方各阶段的章节内容，可直接跳转至对应的模板章节。

阶段描述

阅读本节最有效的方式，是将其视为一个按顺序展开的算法。第零阶段加载Token列表和数值快照。第一阶段构建并打印独热编码Embedding。第二阶段将提供的提示Embedding转换为 Q 、 K 和 V 。第三阶段至 5 对提示执行注意力计算。阶段 6 则在Generate过程中利用缓存应用相同的思路。

每个阶段都会指明当存在模板函数时，你应首先实现哪个函数。第一阶段是现在位于注意力流水线前端的小型Embedding构建阶段。

第 0 阶段：读取输入

如果你想在阅读格式规则之前先了解真实输入文件的样子，请打开"输入文件示例"。

请先实现这个模板函数： read_input(...) . 后续的每个阶段都依赖于正确存储输入快照。

按以下顺序从 stdin 中读取：

n d g text_len 。三个注意力大小，后跟第一阶段文本中的Token数量。
text_len 个以空白符分隔的Token。这是第一阶段文本，你需要将其转换为独热编码表。
n 个整数，对应 mask 。这些整数表明哪些提示位置是真实的，哪些是填充的。
n 个长度为 d 的PromptEmbeddingVector。这些行是后续注意力阶段使用的数值提示Matrix。
g 个长度为 d 的GenerateEmbeddingVector。这些行将在后续的Generate阶段中使用。
d 行，对应 Wq 查询投影Matrix。
d 行，对应 Wk 键投影Matrix。
d 行用于 Wv 值投影Matrix。

边界

符号	含义	范围
`n`	Prompt令牌数量	`1 <= n <= 64`
`d`	Embedding维度	`1 <= d <= 64`
`g`	Generate的Token数量	`0 <= g <= 32`
`text_len`	第一阶段文本中的Token数量	`1 <= text_len <= 64`

使用 scanf 。请勿在您的 C 程序中打开文件。

以空白符分隔的输入意味着空格和换行符对于 scanf 是等效的。

第一阶段：创建EmbeddingVector

本阶段是注意力计算开始前的小型表示练习。你需要获取输入文本，将每个以空白字符分隔的部分视为一个Token（token），构建唯一Token列表，按字典序排序，然后为该排序列表中的每个Token打印一个独热（one-hot）Vector。

本阶段的模板函数为 create_embeddings(...) 如果你使用 qsort(...) ，比较辅助函数就紧挨着它放在模板代码中。

本阶段的核心任务是：

将第 0 阶段存储的Token数组按字典序排序
从已排序的数组中删除重复的Token
根据在已排序数组中的索引，为每个Token赋予一个除某一位为 1 外其余全为零的Vector
按照输出格式，将Token与其独热编码一同打印输出

这就是独热编码的思想。它是从类别到数字的简单桥梁，独热编码解释器会以可视化方式展示这一过程。

如果你在原理上理解了这个阶段，但还没有真正使用过 C 字符串，请参阅《C 中的字符串》。它是一个简短的速成课程，介绍本阶段所依赖的字符串操作。

本阶段是Token表示的简单练习版本。

重要的第一阶段差异

Stage 1 的Vector长度是排序列表中唯一Token的数量，而非后续注意力阶段中使用的提示Embedding维度 d 。

在词典序排序步骤中，你可以使用 qsort(...) 或自己编写的排序代码。

本阶段与后续注意力阶段的关系

后续的注意力阶段不依赖第一阶段的Vector作为输入。设置这一阶段的目的，是在作业的其余部分切换到所提供的数值EmbeddingMatrix之前，将"文本转化为Vector"这一概念具体呈现出来。

重要的表示规则是：

已排序的唯一Token数组即为Embedding表
Token在该排序数组中的位置决定了 1 的放置位置
Embedding中的其他所有位置均为 0

这意味着该阶段的Embedding维度为"排序列表中唯一标记的数量"。

示例演练：一个简单的Embedding表

如果已排序的Token列表是

algorithms, best, foundations, of, subject, the, to, welcome

独热Vector为：

algorithms

best

welcome

这并非现代训练模型通常构建EmbeddingVector的方式，但这是一种简洁的方法，可以展示文本在注意力机制开始之前如何转化为Vector。

对于一个较小的三Token情形，打印输出如下所示：

Stage 1: Create Embeddings
"algorithms" -> (1 0 0)
"subject" -> (0 1 0)
"the" -> (0 0 1)

第二阶段：投影

在 LLM 中，提示文本经过分词处理后，将被表示为一系列EmbeddingVector。

在本阶段，我们直接提供与分词后的提示相对应的EmbeddingVector序列，而不依赖前一阶段，以保持两者相互独立。如果我们使用前一阶段的结果，对于给定的提示，你需要查找每个Token的Embedding，并将这些Embedding组成的数组传递到本阶段。值得注意的是，无论Token在提示中处于何处，其Embedding都是相同的——尽管词语所处的位置不同，与其他词语的关系也会改变其含义。这正是注意力机制发挥作用的地方！

一旦输入存储完毕，我们实现注意力机制的第一步计算是构建Prompt的查询（query）、键（key）和值（value）Matrix。

在继续阅读之前，请确保你已熟悉相关符号表示。

输入Prompt的EmbeddingVector构成Matrix $X$ 的各行。为了得到查询、键和值，你需要用三个不同的Matrix对同一个PromptMatrix进行三次投影：

Q = X W_{q} K = X W_{k} V = X W_{v}

Q、K、V 分别是什么，以及为什么需要三个Matrix。

这些Matrix与 C 框架有何关联？

$X$ 是PromptEmbeddingMatrix： prompt 。Matrix的每一行对应一个Prompt标记的EmbeddingVector。
$W_{q}, W_{k}, W_{v}$ 是权重Matrix。在 C 语言中，它们以二维数组的形式存储为 Wq 、 Wk 、 Wv 。
$Q, K, V$ 是提示投影VectorMatrix。在 C 语言中，它们以二维数组的形式存储为 q_matrix 、 k_matrix 、 v_matrix 。

实现此阶段的模板函数： compute_projection(...) .

如果 $X$ 是输入Matrix， $W$ 是其中一个投影Matrix， $Y$ 是投影后的输出Matrix，则：

Y_{i, j} = \sum_{u = 0}^{d - 1} X_{i, u} W_{u, j} Y = [\begin{matrix} Y_{0, 0} & \dots & Y_{0, d - 1} \\ ⋮ & ⋱ & ⋮ \\ Y_{n - 1, 0} & \dots & Y_{n - 1, d - 1} \end{matrix}]

注意每次计算输出分量时都要将累加和重置为 0 。

该函数被调用三次，分别用于计算Prompt的 $Q$ 、 $K$ 和 $V$

示例演算：单个TokenEmbeddingVector

对于长度为 d 的单个TokenVector $\vec{x}$ ，投影Vector y→ 逐分量定义为：

\vec{x} = (\begin{matrix} x_{0} & \dots & x_{d - 1} \end{matrix}), y_{j} = \sum_{u = 0}^{d - 1} x_{u} W_{u, j}, \vec{y} = (\begin{matrix} y_{0} & \dots & y_{d - 1} \end{matrix}) .

以举例说明，对于 d = 2 ，我们可以等价地将逐元素求和写成Matrix乘法的形式。我们定义Matrix $X = [\begin{matrix} \vec{x} \end{matrix}]$ ，从而可以用Matrix乘法来表达：

X = [\begin{matrix} x_{0} & x_{1} \end{matrix}] W = [\begin{matrix} W_{0, 0} & W_{0, 1} \\ W_{1, 0} & W_{1, 1} \end{matrix}]

则

\begin{aligned} Y & = [\begin{array}{c} x_{0} & x_{1} \end{array}] [\begin{array}{c} W_{0, 0} & W_{0, 1} \\ W_{1, 0} & W_{1, 1} \end{array}] = [\begin{array}{c} [\begin{matrix} x_{0} & x_{1} \end{matrix}] [\begin{matrix} W_{0, 0} \\ W_{1, 0} \end{matrix}] & [\begin{matrix} x_{0} & x_{1} \end{matrix}] [\begin{matrix} W_{0, 1} \\ W_{1, 1} \end{matrix}] \end{array}] \\ = [\begin{array}{c} (\begin{matrix} x_{0} & x_{1} \end{matrix}) ∙ (\begin{matrix} W_{0, 0} & W_{1, 0} \end{matrix}) & (\begin{matrix} x_{0} & x_{1} \end{matrix}) ∙ (\begin{matrix} W_{0, 1} & W_{1, 1} \end{matrix}) \end{array}] \\ = [\begin{array}{c} (x_{0} \cdot W_{0, 0} + x_{1} \cdot W_{1, 0}) & (x_{0} \cdot W_{0, 1} + x_{1} \cdot W_{1, 1}) \end{array}] \end{aligned}

这与你的代码对提示Matrix每一行所使用的循环模式相同。

示例演练：两个TokenEmbeddingVector

在前面的例子中，我们将一个输入Vector视为Matrix的一行，但我们可以将其扩展为多个输入Vector，每个Vector作为不同的行，Matrix乘法仍然成立，只是结果Matrix会有更多的行！

为了获得查询、键和值的TokenMatrix，我们将使用三个不同的权重Matrix对该投影操作执行三次：

Q = X W_{q}, K = X W_{k}, V = X W_{v} .

现在我们可以一次性考虑一整个由 n 个提示EmbeddingVector组成的Matrix（每个Vector是 $X$ 的一行），其维度为 d = 2

\begin{aligned} Y & = X W = [\begin{array}{c} X_{0, 0} & X_{0, 1} \\ X_{1, 0} & X_{1, 1} \end{array}] [\begin{array}{c} W_{0, 0} & W_{0, 1} \\ W_{1, 0} & W_{1, 1} \end{array}] = [\begin{array}{c} [\begin{matrix} X_{0, 0} & X_{0, 1} \end{matrix}] [\begin{matrix} W_{0, 0} \\ W_{1, 0} \end{matrix}] & [\begin{matrix} X_{0, 0} & X_{0, 1} \end{matrix}] [\begin{matrix} W_{0, 1} \\ W_{1, 1} \end{matrix}] \\ [\begin{matrix} X_{1, 0} & X_{1, 1} \end{matrix}] [\begin{matrix} W_{0, 0} \\ W_{1, 0} \end{matrix}] & [\begin{matrix} X_{1, 0} & X_{1, 1} \end{matrix}] [\begin{matrix} W_{0, 1} \\ W_{1, 1} \end{matrix}] \end{array}] \\ = [\begin{array}{c} (X_{0, 0} \cdot W_{0, 0} + X_{0, 1} \cdot W_{1, 0}) & (X_{0, 0} \cdot W_{0, 1} + X_{0, 1} \cdot W_{1, 1}) \\ (X_{1, 0} \cdot W_{0, 0} + X_{1, 1} \cdot W_{1, 0}) & (X_{1, 0} \cdot W_{0, 1} + X_{1, 1} \cdot W_{1, 1}) \end{array}] \end{aligned}

在此示例中，我们的TokenEmbeddingMatrix中存储了 n = 2 个TokenEmbeddingVector： $(\begin{matrix} X_{0, 0} & X_{0, 1} \end{matrix})$ 和 $(\begin{matrix} X_{1, 0} & X_{1, 1} \end{matrix})$ 。可以看到，在输出Matrix中，每一行对应于输入中该行TokenEmbeddingVector的投影Vector。每行的计算与其他行相互独立，因此我们可以分别计算每行的结果，但将Vector存储为Matrix的行在符号表示上更为紧凑，在编程实现时也更为便捷！

第三阶段：注意力Score（Prompt）

在获得 $Q$ 和 $K$ 之后，下一步是衡量与PromptToken $j$ 对应的每个键Vector应对与PromptToken $i$ 对应的每个查询Vector的关注程度。在此任务中，你需要利用上一阶段的投影结果来计算 $score$ Matrix。

你需要实现模板函数： compute_attention_scores_or_weights_prompt(...)

对于与提示Token $i$ （ $\vec{Q_{i}}$ ）对应的每个查询Vector，以及与提示Token $j$ （ $\vec{K_{j}}$ ）对应的键Vector，我们计算一个注意力Score。该Score是一个缩放Dot product：

{score}_{i, j} = \frac{\vec{Q_{i}} ∙ \vec{K_{j}}}{\sqrt{d}} = \frac{\sum_{u = 0}^{d - 1} Q_{i, u} K_{j, u}}{\sqrt{d}} score = \frac{Q K^{T}}{\sqrt{d}} = [\begin{matrix} {score}_{0, 0} & \dots & {score}_{0, n - 1} \\ ⋮ & ⋱ & ⋮ \\ {score}_{n - 1, 0} & \dots & {score}_{n - 1, n - 1} \end{matrix}]

在计算Score时，您应该应用两种不同的Mask：

Causal mask：如果 j > i ，通过将Score设置为 − $\infty 来掩盖该位置$
Padding mask：
- 如果 mask[i] == 0 ，整行Score变为 $- \infty$ 。
- 如果 mask[j] == 0 ，则通过将Score设置为 $- \infty$

在 C 中， $- \infty$ 的Score将使用 <math.h> 中定义的 INFINITY 常量以 -INFINITY 的形式存储。

为什么被屏蔽的Score是

- \infty

？

我们将Score设置为 $- \infty$ ，因为Score是两个Vector之间的Dot product，而较小的Dot product意味着这两个Vector差异很大。通过将Score设置为 $- \infty$ ，当我们在下一阶段计算权重时，这些被Mask的值的权重将为 0.0。

为什么两个维度使用相同的Mask？

我们对两个维度使用相同的Padding mask，因为两个维度都代表相同的Token，只是对应不同的重混合Vector！

评分公式究竟在做什么？

如果你想了解更慢节奏的推导过程、小型示例以及Mask存在原因的可视化说明，请使用Dot product解释器和Mask解释器。

详解示例：单个注意力Score

让我们考虑一个关于 n = 3 和 d = 2 的例子：

Q = [\begin{matrix} Q_{0, 0} & Q_{0, 1} \\ Q_{1, 0} & Q_{1, 1} \\ Q_{2, 0} & Q_{2, 1} \end{matrix}] K = [\begin{matrix} K_{0, 0} & K_{0, 1} \\ K_{1, 0} & K_{1, 1} \\ K_{2, 0} & K_{2, 1} \end{matrix}]

这里， $Q$ 和 $K$ 的每一行 $Q i→$ 和 Kj→ 对应一个由TokenEmbeddingVector投影得到的Vector。假设前一部分中 X 第 0、1、2 行的原始TokenEmbeddingVector分别表示Token Foundations 、 of 和 Algorithms ，那么 Q 和 K 的各行所表示的内容也与之相同。

例如，若我们计算 ${score}_{1, 0}$ ，这是查询Vector 1 of 与键Vector 0 Algorithms 的注意力Score，更准确地说，是键Vector 0 对查询Vector 1 的关注程度。

{score}_{1, 0} = \frac{[\begin{matrix} Q_{1, 0} & Q_{1, 1} \end{matrix}] ∙ [\begin{matrix} K_{0, 0} & K_{0, 1} \end{matrix}]}{\sqrt{2}} = \frac{Q_{1, 0} \cdot K_{0, 0} + Q_{1, 1} \cdot K_{0, 1}}{\sqrt{2}}

与上一题相同，我们也可以通过Matrix乘法来计算ScoreMatrix（为符号表示方便起见）。此处我们需要对第二个Matrix进行转置，从而得到一个有意义的Matrix乘法，其中第一个Matrix的列数必须等于第二个Matrix的行数。从数学角度来看，这两种表示方式是等价的，研究论文通常也会采用这种方式来表示该运算，但在实际编写代码时，你可能会发现其中某一种方式更易于理解和实现。

score = \frac{Q K^{T}}{\sqrt{d}} = \frac{1}{\sqrt{d}} [\begin{matrix} Q_{0, 0} & Q_{0, 1} \\ Q_{1, 0} & Q_{1, 1} \\ Q_{2, 0} & Q_{2, 1} \end{matrix}] [\begin{matrix} K_{0, 0} & K_{1, 0} & K_{2, 0} \\ K_{0, 1} & K_{1, 1} & K_{2, 1} \end{matrix}]

第四阶段：注意力权重（提示）

第三阶段的Score并非最终答案，还需将其归一化为权重。

在此阶段，你需要修改第 3 阶段中的模板函数 compute_attention_scores_or_weights_prompt(...) 以便应用 softmax。

因此，当 apply_softmax 为 1 （此阶段）时，你应该对输出Matrix中的每一行取得Score并应用稳定 softmax。

weight = [\begin{matrix} {weight}_{0, 0} & \dots & {weight}_{0, n - 1} \\ ⋮ & ⋱ & ⋮ \\ {weight}_{n - 1, 0} & \dots & {weight}_{n - 1, n - 1} \end{matrix}] = [\begin{matrix} softmax ({\vec{score}}_{0}) \\ ⋮ \\ softmax ({\vec{score}}_{n - 1}) \end{matrix}]

{weight}_{i, j} = \frac{e^{{score}_{i, j} - max ({\vec{score}}_{i})}}{\sum_{u = 0}^{n - 1} e^{{score}_{i, u} - max ({\vec{score}}_{i})}}

如果某一行没有未被遮蔽的列，则对该行中的每个权重输出 0.0 ，不要进行除零操作！

已解决示例：Score转化为权重

如果一行未遮蔽的Score为

(2, 0, -1)

然后 softmax 将该行转换为大致如下的权重

(0.84, 0.11, 0.05)

最大的Score变成最大的权重，但每个未被遮蔽的位置仍然获得一个非负的份额。稳定 softmax 与普通 softmax 产生相同的最终权重；它只是先减去行最大值，使指数运算在数值上保持安全。

第 5 阶段：注意力输出（Prompt）

获得注意力权重后，即可计算实际的Prompt输出。请实现以下模板函数： compute_attention_output_prompt(...) .

使用以下公式，将每个Prompt标记的注意力输出Vector计算为Matrix $output$ ：

{output}_{i, j} = {\vec{weight}}_{i} ∙ {\vec{(V^{T})}}_{j} = \sum_{u = 0}^{n - 1} {weight}_{i, u} V_{u, j} output = (weight) V = [\begin{matrix} {output}_{0, 0} & \dots & {output}_{0, d - 1} \\ ⋮ & ⋱ & ⋮ \\ {output}_{n - 1, 0} & \dots & {output}_{n - 1, d - 1} \end{matrix}]

请注意， ${\vec{(V^{T})}}_{j}$ 的含义是取Matrix $V$ 第 $j$ 列对应的Vector。而 $V→ j$ 则表示第 j 行。先进行转置操作，会将列变为行，这样我们就可以提取第 j 行，从而得到对应于该列的Vector。

这是使用你刚刚计算出的注意力权重对值Vector进行的加权求和。

工作示例：三个TokenEmbedding二维空间

包含 $n = 3$ 和 $d = 2$

weight = [\begin{matrix} {weight}_{0, 0} & {weight}_{0, 1} & {weight}_{0, 2} \\ {weight}_{1, 0} & {weight}_{1, 1} & {weight}_{1, 2} \\ {weight}_{2, 0} & {weight}_{2, 1} & {weight}_{2, 2} \end{matrix}] V = [\begin{matrix} V_{0, 0} & V_{0, 1} \\ V_{1, 0} & V_{1, 1} \\ V_{2, 0} & V_{2, 1} \end{matrix}]

使用与之前相同的示例，假设 $X$ 中第 0、1、2 行的原始TokenEmbeddingVector分别表示Token Foundations 、 of 和 Algorithms 。 $weight$ Matrix为 3 行 3 列，值 $V$ Matrix为 3 行 2 列。

Token 2 的输出Vector直接在Embedding中融入了其前面提示Token的上下文，其计算结果为：

\begin{aligned} {\vec{output}}_{2} & = (\begin{array}{c} [\begin{matrix} {weight}_{2, 0} & {weight}_{2, 1} & {weight}_{2, 2} \end{matrix}] [\begin{matrix} V_{0, 0} \\ V_{1, 0} \\ V_{2, 0} \end{matrix}] & [\begin{matrix} {weight}_{2, 0} & {weight}_{2, 1} & {weight}_{2, 2} \end{matrix}] [\begin{matrix} V_{0, 1} \\ V_{1, 1} \\ V_{2, 1} \end{matrix}] \end{array}) \\ = (\begin{array}{c} ({weight}_{2, 0} V_{0, 0} + {weight}_{2, 1} V_{1, 0} + {weight}_{2, 2} V_{2, 0}) & ({weight}_{2, 0} V_{0, 1} + {weight}_{2, 1} V_{1, 1} + {weight}_{2, 2} V_{2, 1}) \end{array}) \end{aligned}

若某个权重接近 1，则输出将与该值Vector非常相似；若权重分散，则输出为各Vector的混合。

与前面的部分类似，我们也可以使用Matrix乘法将此计算非常紧凑地表示出来，从而得到一个Matrix 其中每一行对应给定Token的输出Vector

output = (weight) V = [\begin{matrix} {weight}_{0, 0} & {weight}_{0, 1} & {weight}_{0, 2} \\ {weight}_{1, 0} & {weight}_{1, 1} & {weight}_{1, 2} \\ {weight}_{2, 0} & {weight}_{2, 1} & {weight}_{2, 2} \end{matrix}] [\begin{matrix} V_{0, 0} & V_{0, 1} \\ V_{1, 0} & V_{1, 1} \\ V_{2, 0} & V_{2, 1} \end{matrix}]

如何解读输出Vector？

这就是注意力机制的核心所在：一个PromptToken的输出Vector，是根据哪些键Vector与给定查询Vector的匹配程度最高，对相应的值Vector进行加权融合后得到的结果。

如果某个权重占主导地位，输出结果将与某个值Vector非常相似。如果多个权重都起作用，输出结果则会成为多个Vector的混合。注意力机制解释器对此有更直观的展示。

第六阶段：使用 KV cacheGenerate输出

在本任务中，你将使用Prompt和已Generate的Token（作为输入的一部分提供），以及 KV cache来计算注意力输出。你无需自行GenerateToken，因为这些Token已作为输入提供。

这与完整的 LLM 有何关联？

在完整的 LLM 中，我们首先会对所有Prompt（prompt）的 token 计算注意力（attention）。然后将其传递给 LLM 内部的其他组件，这些组件将利用它来Generate下一个 token。一旦Generate了新的 token，我们需要再次计算注意力并将其传递下去，从而Generate新的 token，如此循环往复，直到达到所需次数。因此，尽管我们在你的代码中已将所有Generate的 token 作为输入一并提供，但在真实系统中，我们每次只能获得一个 token。

最后阶段在Generate过程中应用相同的注意力逻辑，但此时程序通过缓存复用过去的键和值。

实现以下模板函数： compute_generation_with_cache(...) .

对于每个Generate的Token $t$ （跟随在 $n$ 个提示Token之后），你需要计算：

${\vec{Q}}_{n + t}$ ：编号为 $n + t$ 的Token的查询Vector。
${\vec{K}}_{n + t}$ 和 ${\vec{V}}_{n + t}$ ：编号为 $n + t$ 的Token的键Vector和值Vector，应将其追加到 KV cache中。
将新查询 ${\vec{Q}}_{n + t}$ 与所有缓存的键 ${\vec{K}}_{i}$ 进行评分，计算范围为 $0 \leq i \leq n + t$ ，同时记得屏蔽提示缓存条目（ $0 \leq i < n$ ），其中 mask[i] == 0 （与第 3 阶段的某一行相同）
对缓存的Score应用稳定 softmax，将其转换为权重（与第 4 阶段的某一行相同）
将缓存的值进行加权求和，计算输出结果（与第 5 阶段的某一行相同）

第 6 阶段不需要单独的未来TokenCausal mask，因为缓存中只包含过去的条目以及当前Generate的Token。当前Generate的Token已被包含在内，因此它可以关注自身。

已计算Dot product

你还必须报告每个GenerateToken所计算的Dot product的确切数量。

在本阶段，将"一次Dot product计算"定义为：对任意两个Vector之间计算Dot product（包括Matrix乘法中任意行Vector与列Vector之间的乘法），适用于任意权重Matrix，以及任意未被Mask的提示Token或任意GenerateToken的EmbeddingVector或投影Vector。

这意味着：

对于每个Generate的Token，你应该对每个未被遮蔽的Score恰好计算一次（将其存储在数组中，并在求最大值和分母时复用）。
你返回的总计数应等于所有GenerateToken中处理过的未被遮蔽的缓存键位置的总数。
如果某个提示缓存条目被遮蔽（ mask[j] == 0 ），则其对计数的贡献为 0。

已解答示例：第 6 阶段Dot product计数

In the visible test0.txt case, the prompt mask is 1 1 0, d = 2, and there are two generated tokens (g = 2).

3d = 6 dot products compute the new query, key, and value vectors
3 dot products score against unmasked cached keys
d = 2 dot products compute the output vector

So the printed count is 11.

For the second generated token:

6 dot products compute the new query, key, and value vectors
4 dot products score against unmasked cached keys
2 dot products compute the output vector

So the printed count is 12.

为什么缓存在这里有帮助？

缓存的存在是为了避免在Generate过程中反复重新计算旧的键和值。KV cache解释器会逐步展示缓存的增长过程，并说明如何理解每个GenerateToken的Dot product计数。

想要一个具体的端到端示例？

现在你已经了解了整个流程，玩具演示是一个很好的方式来加深理解。

它允许你从真实文本Generate一个小型数字输入，在其上运行你的程序，然后以Token级别的解释形式读取所得到的注意力权重。这是可选的，但它可能有助于你将各个阶段与更易于人类阅读的内容联系起来。

结构化版本还使用了一个小型独热编码区域来表示实体身份，这也是为什么一些玩具Vector看起来特别易于解读的原因。

测试、评分与输出规则

本节汇总了规范中在检查作业时直接有用的部分：测试方法、常见失败模式、评分标准以及精确的输出规范。

评分与反馈

本次作业包含：

一个自动评分测试用例组件
人工评分的代码风格与代码结构/方法部分
简短的书面复杂度分析

作业说明中的阶段划分如下：

阶段	测试用例	代码风格	结构/方法	复杂度分析	总计
1	0.5	0.5	0.5	0.5	2
2	1	0.5	1	0.5	3
3	2	0.5	1	0.5	4
4	1	0.5	1	0.5	3
5	2	0.5	1	0.5	4
6	2	0.5	1	0.5	4

代码风格要求

在使用前定义常量，而不是依赖魔法数字或字符串
`#define` 名称保持大写
为所有函数添加函数原型声明
为变量和函数使用具有描述性的命名
对代码各部分背后的思路进行注释，而非重复语法本身已清晰表达的内容
保持括号位置、缩进和空格的一致性
使用空行分隔各部分以提高可读性
保持每行代码不超过 100 个字符

代码结构要求

避免重复的代码段
通过将数据传入函数来避免不必要的全局变量
在有助于改善代码结构的地方使用辅助函数
保持函数长度适中，避免过于复杂
选择一种简单直接的算法方法
避免不必要的数据重复
尽量避免深层嵌套的控制流

复杂度分析

填写 Complexity Analysis 文件顶部附近的 a1.c 代码块。

用简明的语言，以 n 、 d 、 g 和 text_len 为变量，给出以下内容的大 O 时间复杂度：

第一阶段创建EmbeddingVector
第二阶段投影
第三阶段提示注意力Score
第四阶段提示注意力权重
第 5 阶段提示注意力输出
第 6 阶段带缓存的Generate

只需统计主导循环的工作量，忽略常数因子。无需分析内存使用情况。重要的不仅仅是给出大 O 表示，还需简要说明推导过程。分析你实际编写的代码，而非你本可以编写的更优化版本。

测试你的代码

在构建过程中，请使用这些示例测试来检验您自己的 a1.c 。

在提供的压缩包中，您有：

test_data/test0.txt ，预期输出为 test_data/test0-out.txt
test_data/test1.txt ，预期输出为 test_data/test1-out.txt
test_data/test2.txt ，预期输出为 test_data/test2-out.txt
test_data/test3.txt 附带预期输出 test_data/test3-out.txt ，用于更大规模的端到端练习案例

编译：

clang -Wall -Wextra -Wno-newline-eof -Wno-unused-parameter -pedantic -std=c17 -lm -o a1 a1.c

运行测试：

./a1 < test_data/test0.txt

比较输出：

./a1 < test_data/test0.txt > myout.txt
diff -u test_data/test0-out.txt myout.txt

常见陷阱

在第 3 至第 5 阶段忘记应用Causal mask。对于第 i 行，位置 j > i 必须被Mask。
在第 3 至第 5 阶段忘记Padding mask。
忘记如果 mask[i] == 0 ，则整个位置 i 在后续阶段应贡献一个零Vector。
未使用稳定的 softmax。
当所有列均被Mask时出现除以零的情况。
在第 6 阶段，Dot product计数不正确。

精确输出格式

你必须按顺序精确打印以下阶段标题和数据：

第一阶段：对排序后的唯一Token进行独热编码Embedding
第二阶段：Prompt的 Q 、 K 和 V 投影，每个均为 n x d 表
第三阶段：Prompt的注意力Score，为 n x n 表
第四阶段：Prompt的注意力权重，为 n x n 表
阶段 5：Prompt的注意力输出，一个 n x d 表格
阶段 6：每个Generate的Token对应一行Generate输出行和一行Dot product计数行

各阶段的精确标题行如下：

Stage 1: Create Embeddings
Stage 2: Projections
Stage 3: Attention Scores (Prompt)
Stage 4: Attention Weights (Prompt)
Stage 5: Attention Output (Prompt)
Stage 6: Generated Outputs

第二阶段的块格式为：

Q Projection:
<n lines of d numbers>
K Projection:
<n lines of d numbers>
V Projection:
<n lines of d numbers>

第六阶段的行格式为：

Gen 0: <d numbers>
Dot products computed: <an integer>
Gen 1: <d numbers>
Dot products computed: <an integer>
...

数字必须精确打印到小数点后三位，各数字之间用单个空格分隔。行尾不得有多余空格，任何地方均不得有多余的调试输出。

模板的打印函数还会将极小值截断为 0.000 。这是预期输出行为的一部分，因此最安全的做法是不要修改所提供的打印代码。

作业 1

重要声明

更新日志

重要说明

编译错误至关重要

如何使用本页面

可下载的 PDF

这道作业是关于什么的？

真实 LLM 在高层次上会做什么

本次作业的实际内容

本次作业中数字的来源

推荐的可视化入门资源

一次完成全部任务

术语表与符号说明

在本规范中：

Dot product、Vector与Matrix

入门指南

你已获得

模板已经

您应该

你不得

先检查模板代码

如何开始

阶段描述

第 0 阶段：读取输入

边界

第一阶段：创建EmbeddingVector

重要的第一阶段差异

第二阶段：投影

第三阶段：注意力Score（Prompt）

第四阶段：注意力权重（提示）

第 5 阶段：注意力输出（Prompt）

第六阶段：使用 KV cacheGenerate输出

已计算Dot product

For the second generated token:

想要一个具体的端到端示例？

测试、评分与输出规则

代码风格要求

代码结构要求

复杂度分析