解题思路

长序列下，将历史 token 划分为固定大小的空间连续块，每块做均值池化后经一个两层 MLP 压缩成向量，再用固定查询向量 $q=\mathbf{1}$ 与压缩结果做打分。得到的压缩分数序列 $A=(a_1,\dots,a_m)$ 之后，需要将其划分为恰好两个连续非空子数组，使两段和的最小值最大。整体可分为两部分：

数值构造：分块 + 池化 + MLP + 打分

设序列长度为 $n$ 、维度为 $d$ 、块大小为 $b$ ，块数 $m=\lceil n/b\rceil$ 。
第 $k$ 个块的均值池化

P4275.第3题-基于空间连续块的稀疏注意力机制

1000ms

Tried: 630

Accepted: 137

Difficulty: 6

所属公司 : 华为

算法与标签>前缀和

题目内容

在大语言模型推理过程中，随着上下文长度增加，标准 $Attention$ 的计算开销以 $O(n^2)$ 增长，成为性能瓶颈。为提升长序列处理效率，提出一种基于空间连续块的稀疏注意力机制。

具体流程如下：

一个长度为 $n$ 的历史 $token$ 序列，每个 $token$ 表示为 $1$ 个 $d$ 维特征向量 $\mathbf{x}_j \in \mathbb{R}^d$

。按固定块大小 $b$ ，将序列划分为 $m = ceil(n/b)$ 个空间连续块（最后一个块可不满）

$B_1, B_2, ..., B_m$ ，其中： $B_k = [x_{(k-1)b}, ..., x_{min(kn)-1}]$
对每个块 $B_k$ ：

(1) 计算平均池化向量： $\mathbf{h}_k = \frac{1}{B_k} \sum_{x \in B_k} \mathbf{x}$

(2) 使用一个两层多层感知机（ $MLP$ ）进行非线性压缩（隐藏维度 $d_l = 1$ ）： $\mathbf{c}_k = W_2 \cdot \sigma(W_1 \cdot \mathbf{h}_k + b_1) + b_2$

其中：

① $W_1 \in \mathbb{R}^{1 \times d}$ ， $W_2 \in \mathbb{R}^{d \times 1}$ ，输出 $\mathbf{c}_k \in \mathbb{R}^d$

② $b_1 = 2$ ， $b_2 = 1$

③ $\sigma(x) = max(0, x)$ （即 ReLU 激活函数）
给定查询向量 $\mathbf{q} \in \mathbb{R}^d$ （题目中固定为全 $1$ 向量： $q_i = 1$ ），计算每个压缩块的注意力得分：

$a_k = \frac{\mathbf{q} \cdot \mathbf{c}_k}{\sqrt{d}}$

得到压缩块注意力得分序列 $A = (a_1, a_2, ..., a_m)$
将序列 $A$ 划分为恰好 $2$ 个连续非空子数组，目标是最大化这两个子数组和中的最小值 $S$ 。
最终输出该最大化的最小值 $S$ 的整数化得分，该子数组对应的 $token$ 块将跳过细粒度 $attention$ 计算，实现稀疏推理。

其中，整数化得分即 $S$ 乘以 $100$ 后四舍五入得到的整数，以实现保留两位小数精度的整数化表示：

$round(100 \cdot S)$

输入描述

第 $1$ 行： $n$ $d$ $b$ ，以空格分隔，分别为序列长度、 $token$ 向量维度、块大小

接下来 $n$ 行：每行 $d$ 个数，以空格分隔，表示 $x_i$

倒数第 $2$ 行： $d$ 个数，以空格分隔，表示 $W_1$

最后 $1$ 行： $d$ 个数，以空格分隔，表示 $W_2$

约束条件：

$1 \leq n\leq 1000$

$1 \leq b\leq n$

$1 \leq d \leq 100$

所有向量非零

输出描述

返回一个整数，即上述步骤 $5$ 的整数化得分

样例1

输入

输出

说明

①分块： $B_1 = [2.0]$ ， $B_2 = [4.0]$ ， $B_3 = [6.0]$

②平均池化： $h_1 = [2.0]$ ， $h_2 = [4.0]$ ， $h_3 = [6.0]$

③ $MLP$ 压缩： $c_1 = [9.0]$ ， $c_2 = [13.0]$ ， $c_3 = [17.0]$

④注意力得分： $A=[9,13,17]$

⑤划分为 $2$ 个连续非空子数组，最大化 $min(sum)$ ：

$[9]|[13,17]$ $→$ 和： $9, 30 → min = 9$

$[9,13]|[17]$ $→$ 和： $22, 17 → min = 17→ S=17$ ，输出 1700

样例2

输入

3 2 1
2.0 1.0
3.0 2.0
4.0 3.0
1.0 0.5
2.0 1.0

输出

说明

①分块： $B_1 = [2.0, 1.0]$ ， $B_2 = [3.0, 2.0]$ ， $B_3 = [4.0, 3.0]$

②平均池化： $h_1 = [2.0, 1.0]$ ， $h_2 = [3.0, 2.0]$ ， $h_3 = [4.0, 3.0]$

③ $MLP$ 压缩： $c_1 = [10.0, 5.5]$ ， $c_2 = [13.0, 7.0]$ ， $c_3 = [16.0, 8.5]$

④注意力得分： $A = [\frac{15.5}{\sqrt{2}}, \frac{20.0}{\sqrt{2}}, \frac{24.5}{\sqrt{2}}]$

⑤划分为 $2$ 个连续非空子数组，最大化(min(sum))：

$[\frac{15.5}{\sqrt{2}}] ， [\frac{20.0}{\sqrt{2}}, \frac{24.5}{\sqrt{2}}] →$ 和： $\frac{15.5}{\sqrt{2}}$ ， $\frac{44.5}{\sqrt{2}}$ $→ min =$ $\frac{15.5}{\sqrt{2}}$

$[\frac{15.5}{\sqrt{2}}, \frac{20.0}{\sqrt{2}}] ， [\frac{24.5}{\sqrt{2}}] →$ 和： $\frac{35.5}{\sqrt{2}}$ ， $\frac{24.5}{\sqrt{2}}$ $→ min = \frac{24.5}{\sqrt{2}}→ S = \frac{24.5}{\sqrt{2}}$ ，输出 1732

输入

预期输出（选填）

解题思路

P4275.第3题-基于空间连续块的稀疏注意力机制

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About