# Atenção paginada

Esta página documenta a função de atenção paginada usada no [loteamento contínuo](./continuous_batching).

## Caminho Varlen

O kernel `flash_attn_varlen_func` processa lotes com comprimento variável. Este caminho é recomendado para lotes com um grande número de solicitações no prefill.

### Comportamento do cache

Este kernel não possui mecanismo para interagir diretamente com o cache paginado, portanto, o cache é lido e gravado manualmente usando o método `~PagedAttentionCache.update`. Isso pode se tornar um gargalo quando o comprimento da sequência aumenta consideravelmente.

### Mecanismo de indexação

O kernel usa o comprimento máximo da sequência (`max_length_q`, `max_length_k`) e os comprimentos cumulativos das sequências (`cu_seq_lens_q`, `cu_seq_lens_k`) para calcular a atenção de cada sequência.

### Exemplo

Considere um lote de 3 sequências com comprimentos de consulta `[10, 3, 1]` e comprimentos de chave `[0, 1, 7]`:

```
cu_seq_lens_q = [0, 10, 13, 14]
cu_seq_lens_k = [0, 0, 1, 8]
max_length_q = 10
max_length_k = 7
```

Formas de entrada:

```
Q:      [1, 10+3+1, num_heads, head_dim] = [1, 14, num_heads, head_dim]
K or V: [1, 0+1+7, num_kv_heads, head_dim] = [1, 8, num_kv_heads, head_dim]
```

O kernel atribui cada token de consulta e de chave/valor a uma sequência usando os comprimentos cumulativos das sequências:

```
Q request index: [r0, r0, r0, r0, r0, r0, r0, r0, r0, r0, r1, r1, r1, r2]
cu_seq_lens_q:   0____________________________________10__________13__14

K request index: [r1, r2, r2, r2, r2, r2, r2, r2]  (r0 has 0 K tokens)
cu_seq_lens_k: 0,0_1_______________________8
```

## Caminho de decodificação

O kernel `flash_attn_with_kvcache` processa lotes apenas de decodificação, nos quais cada sequência possui exatamente um token de consulta. Isso é mais eficiente que o caminho varlen, mas não consegue lidar com lotes que contenham solicitações de pré-preenchimento.

### Comportamento do cache

Este kernel interage com o cache paginado usando uma `block_table` para indexar o cache e atualizá-lo in-place. A tabela de blocos tem a forma `(batch_size, max_blocks_per_seq)`, em que cada linha contém as localizações físicas dos blocos de cache de uma solicitação no tensor de cache KV.

### Mecanismo de indexação

O kernel usa `cache_seqlens` para recuperar o comprimento do cache de cada sequência. Ele assume que cada token de consulta pertence a uma sequência diferente (um token por sequência).

### Exemplo

Considere um lote de 3 sequências com comprimentos de consulta `[1, 1, 1]` e comprimentos de chave `[30, 32, 70]`. O tamanho do bloco de cache é 32 e o número máximo de blocos por sequência é 4.

Os comprimentos das sequências de cache são simplesmente os comprimentos das chaves:

```
cache_seqlens = [30, 32, 70]
```

A forma da tabela de blocos é `(3, 4)`. Usando endereços de exemplo:

```
block_table = [[2, -1, -1, -1],
               [0,  1, -1, -1],
               [3,  5,  6, -1]]
```

Valores de `-1` indicam blocos não alocados.

- **Sequência 0** (30 tokens em cache): cache em `KV_cache[2]`. O novo token cabe (30 + 1 = 31 < 32).
- **Sequência 1** (32 tokens em cache): cache em `KV_cache[0]` e `KV_cache[1]`. Um segundo bloco é necessário, pois 32 + 1 > 32.
- **Sequência 2** (70 tokens em cache): cache em `KV_cache[3]`, `KV_cache[5]` e `KV_cache[6]`. Observe que os blocos não são necessariamente contíguos, o que é a principal vantagem do cache paginado. O novo token cabe no terceiro bloco.