is paged attention an exact attention

[CharlesJu1]

For the blockwise computation of paged attention as in the above equation, it is not an exact attention. In an exact attention, all the attention scores sum up to 1. Here the attention scores in each block sum up to 1. So is it correct to say that paged attention is not an exact attention?

[hongboshi1234]

Yes, it is exact attention.

For prefilling stage. say if you have prompt of len 10. then you need to compute those self attention scores.

a11, a21, a22, a31, a32, a33. .... A1010. So you need to compute those (1+10)*10/2 = 55 combinations right?

for i=5, you need to compute a61, a62, a63, a64, a65 , a66 . Without page attetnion. you can simply do things in a sinlge block
Now with page attetnion, you might devide token 1,2,3 to one block, and 4,5,6 to another block.

The equation above means. B means block size, which is 3 in this example. Then j is block index, which goes from 1 to 3

block j=1 stores token 1,2,3
block j=2 stores token 4,5,6
block j=3 stores token 7,8,9
block j=4 stores token 10

so without page attention, you want to compute (a61, a62, a63, a64, a65 , a66) . then with page attention. you are computing
A61 = {a61, a62, a63} and A62 = {a64, a65, a66} . You will get the same attetnion matrix with or without page attention. The only difference is the way how KV cache is being stored for each token in the memory system(with or without blocks)

[CharlesJu1]

ok, I got it. The denominator summation index goes from the beginning of all the blocks before index i。 Previously somehow I read it as going through only the 'current' block.

[si-yu-aa]

But why is the denominator exp(q^T K 1) rather than exp(q^T K)1？

[si-yu-aa]

exp(q^TK1)=exp (q^T *K_1+q^T K_2 + ...) ，而 exp(q^TK)*1=exp (q^T *K_1)+exp(q^T *K_2 )+ ..., it appears that the latter is the correct calculation method