我对滑动窗口的 PPL 以及重新计算有点困惑
作者: coderwayne3025创建于 2024年10月11日更新于 2024年10月11日
- 滑动窗口重新计算过程假设：• 滑动窗口的大小为 L，这意味着它可以存储最多 L 个 token。• 生成的 token 的总数为 T。• 目标：生成长度为 T 的序列，并且每次生成新的 token 时，只考虑最近的 L 个 token。2. 滑动窗口重新计算中的两个步骤a. 重新计算 Key 和 Value• 在生成新的 token 时，滑动窗口向前移动，导致窗口内的 token 发生变化，因此 token 的位置编码也会相应更新。• 由于位置编码的变化，每个 token 的 Key 和 Value 必须重新计算，以确保它们正确地表示当前上下文中的信息。• 复杂度：滑动窗口中有 L 个 token，需要重新计算它们的 Key 和 Value。重新计算每个 token 的 Key 和 Value 都涉及线性变换，每个 token 的复杂度为 O(1)。因此，重新计算所有 L 个 token 的 Key 和 Value 的复杂度为 O(L)。b. 注意力计算• 计算查询与 Key 之间的相似性• 对于每个新生成的 token，模型生成一个查询 (Q)，然后计算查询与滑动窗口中所有 L 个 token 的 Key 之间的相似性。• 对于每个新生成的 token，需要将每个查询与所有 L 个 token 的 Key 进行比较，总共 L 个 token，每个相似性计算的复杂度为 O(d)，其中 d 是 Key 和查询的维度。因此，对于 L 个 token 的相似性计算的复杂度为 O(L)。忽略维度的影响，可以近似为 O(L)。• 值的加权和• 计算注意力分数后，这些分数用于对滑动窗口中的每个 token 的 Value (V) 进行加权和。• 加权和也涉及 L 个 token，复杂度为 O(L)。因此，加权和的复杂度也为 O(L)。c. 生成新 token 的总复杂度• 重新计算 Key 和 Value：O(L)。• 注意力计算（包括相似性计算和加权和）：O(L)。• 总复杂度：这两个步骤是顺序执行的，因此总复杂度为：O(L) + O(L) = O(2L)• 对于每次新 token 的生成，总复杂度为 O(L)。由于此过程涉及对滑动窗口内所有 token 的操作，因此可以理解为线性增加。3. 总体时间复杂度计算• 我们需要生成 T 个 token，每次生成新 token 时，模型需要完成 Key 和 Value 的重新计算，以及执行注意力计算…
内容来源: mit-han-lab/streaming-llm