先侦察再注意：用于高效LLM推理的Sketch-and-Walk稀疏注意力

自注意力机制在长上下文LLM推理中占据了大量的计算和内存成本，无论是在预填充阶段还是解码阶段。为了解决这一问题，我们引入了Sketch&Walk注意力，这是一种无需训练的稀疏注意力方法，通过轻量级的草图和确定性遍历机制来决定稀疏性。Sketch&Walk应用Hadamard草图技术，以较低的成本获得注意力分数的近似值，然后通过遍历机制跨层聚合这些估计值，捕捉超出标记直接交互的注意力影响。累积的遍历分数用于选择top-k注意力块，从而实现动态稀疏性，且该算法适用于预填充和解码阶段，并结合了定制的稀疏注意力内核。在广泛范围的模型和任务中，Sketch&Walk在20%的注意力密度下保持接近无损的准确性，并在某些情况下略微优于密集注意力，同时实现了高达6倍的推理加速。