Resumo Técnico: Sensibilidade Polinomial à Truncagem de Contexto em Modelos de Linguagem Autoregressivos

1. Declaração do Problema

O artigo aborda os limites teóricos da compressão online de cache KV (Chave-Valor) em modelos de linguagem autoregressivos (LLMs). À medida que os comprimentos de contexto aumentam, o crescimento linear do cache KV torna-se um gargalo primário para a inferência. Embora existam inúmeros esquemas empíricos de compressão (por exemplo, evicção de "heavy-hitter", janelas deslizantes, sumidouros de atenção, quantização), há uma falta de limites teóricos quantitativos sobre o que é alcançável para o problema de compressão online.

A questão central é: Quanta memória (tamanho da janela) é necessária para manter um nível específico de distorção (precisão) na distribuição do próximo token ao comprimir o contexto?

A teoria da informação clássica frequentemente assume mistura geométrica (ou $\rho$-mistura), onde a influência de tokens passados distantes decai exponencialmente ($C\rho^w$). Sob essa suposição, um tamanho de janela de $O(\log(1/\epsilon))$ é suficiente para uma precisão de $\epsilon$. No entanto, essa suposição não é derivada da configuração de modelagem de linguagem e pode não se manter para LLMs treinados.

2. Metodologia e Estrutura

2.1 Formulação Sequencial de Wyner–Ziv

Os autores formulam a compressão de cache KV como um problema de codificação de fonte sequencial de Wyner–Ziv.

• Fonte: A sequência de tokens $X_{1:t-1}$ gerada pelo modelo.
• Codificador: Um codificador online causal $\phi_t$ que mapeia tokens passados para um código comprimido $\hat{C}_t$.
• Informação Lateral do Decodificador: O vetor de consulta do próximo passo $Q_t$ (calculado pelo modelo não comprimido) serve como informação lateral no decodificador.
• Objetivo: Reconstruir a distribuição do próximo token $\tilde{p}_t$ a partir de $(\hat{C}_{\le t}, Q_t)$ de modo que a divergência KL esperada $E[D_{KL}(p_t \| \tilde{p}_t)]$ seja minimizada para uma dada taxa.

2.2 Caracterização Empírica da Sensibilidade à Truncagem

Em vez de assumir mistura geométrica, os autores medem empiricamente a sensibilidade à truncagem de modelos treinados. Eles definem a sensibilidade $d_{TV}^w$ como a distância de Variação Total (TV) entre a distribuição do próximo token com contexto completo e a distribuição condicionada apenas aos $w$ tokens mais recentes:
$$d_{TV}^w := TV(p_\theta(\cdot | X_{1:t-1}), p_\theta(\cdot | X_{t-w:t-1}))$$

Principal Descoberta Empírica: Em quatro modelos (Qwen2.5-0.5B/1.5B/3B, SmolLM2-1.7B) e dois domínios (Linguagem Natural, Código), o decaimento de $d_{TV}^w$ segue uma lei de potência em vez de um decaimento exponencial:
$$d_{TV}^w \propto w^{-\alpha}$$

• Expoentes medidos: $\alpha_{\text{nat}} \approx 0.44$ (Linguagem Natural) e $\alpha_{\text{code}} \approx 0.38$ (Código).
• Ajustes de lei de potência superam significativamente os ajustes exponenciais na extrapolação (melhoria de log-RMSE de 2–2,5$\times$).
• Essa propriedade é verificada como livre de artefatos de codificação posicional por meio de uma ablação que preserva a posição.

3. Principais Contribuições e Resultados Teóricos

Com base na observação empírica da sensibilidade à truncagem polinomial $\alpha$, o artigo desenvolve uma estrutura de teoria da informação com os seguintes resultados centrais:

C1: Conversa Sequencial de Wyner–Ziv (Limite Inferior)

Os autores estabelecem um limite inferior fundamental na taxa necessária para atingir uma distorção alvo $D$. Para qualquer esquema online causal:
$$\liminf_{n \to \infty} E[R_n] \ge R^\star(D)$$
Este limite vale sem assumir condições específicas de mistura, dependendo apenas da estrutura do problema sequencial de Wyner–Ziv.

C2: Escalonamento de Janela para Políticas Apenas de Sufixo

O artigo caracteriza os requisitos de memória para políticas apenas de sufixo (esquemas onde a reconstrução depende apenas dos $w$ tokens mais recentes, por exemplo, janelas deslizantes).

• Limite Superior: Um esquema de janela deslizante atinge distorção TV $\epsilon$ com tamanho de janela $w = O(\epsilon^{-1/\alpha})$.
• Limite Inferior (Conversa): Sob uma condição adicional de "risco bayesiano bilateral" (Definição 4.4), qualquer política apenas de sufixo requer $w = \Omega(\epsilon^{-1/\alpha})$.
• Resultado: O requisito de memória por token para políticas apenas de sufixo é apertado: $\Theta(\epsilon^{-1/\alpha})$.
  • Contraste com Mistura Geométrica: Sob mistura geométrica, $w = O(\log(1/\epsilon))$. Com $\alpha \approx 0.5$, o tamanho da janela escala polinomialmente (por exemplo, $w \sim 10^2$ para $\epsilon=0.01$), explicando por que esquemas implantados exigem janelas muito maiores do que a mistura geométrica preveria.

C3: Esquema de Realização Explícito

Os autores propõem um esquema explícito de codificação aleatória em bloco-Markov que atinge os limites teóricos.

• Tamanho da Janela: $w_n = \lceil n^{1/(\alpha+1)} \rceil$.
• Convergência: O esquema atinge distorção dentro de $O(n^{-\alpha/(\alpha+1)})$ do alvo.
• Convergência de Taxa:
  • Em expectativa, a taxa converge com expoente $\alpha/(\alpha+1)$.
  • Com alta probabilidade, o expoente é $\alpha/(2(\alpha+1))$ sem suposições adicionais.
  • Sob hipóteses adicionais (decaimento de covariância forward, informação inclinada aditiva), o expoente de alta probabilidade corresponde à conversa ($\alpha/(\alpha+1)$).

C4: Implicação da Estratégia de Evicção "Sumidouro Mais Recente"

O artigo analisa a popular estratégia de evicção "sumidouro mais recente" (retenção de sumidouros de atenção + tokens recentes).

• Resultado: Sob sensibilidade polinomial $\alpha$, a lacuna de distorção KL decai como $O(k^{-2\alpha})$, onde $k$ é o orçamento.
• Mecanismo: A duplicação do expoente ($2\alpha$ em vez de $\alpha$) surge de uma relação quadrática local entre a divergência KL e a distância TV ($KL \le C \cdot TV^2$) no regime de piso limitado, não da desigualdade de Pinsker.
• Validação Empírica: Os expoentes KL medidos ($\alpha_{KL} \approx 1.04$ para Natural, $0.74$ para Código) são aproximadamente o dobro dos expoentes TV ($0.44$e$0.38$), confirmando a previsão teórica.

4. Resultados Empíricos

O artigo valida a estrutura no Qwen2.5 (0.5B, 1.5B, 3B) e SmolLM2 (1.7B):

1. Decaimento Polinomial: Ajustes de lei de potência para o decaimento TV são superiores aos ajustes exponenciais em todos os modelos e domínios.
2. Consistência dos Expoentes: A razão $\alpha_{KL} / \alpha_{TV}$ abrange consistentemente o fator previsto de 2 (razões observadas: 1,93 a 2,38).
3. Degradação de Política: Políticas baseadas em recência (janela deslizante, sumidouro mais recente) suprimem a distorção em aproximadamente duas ordens de grandeza em comparação com a retenção aleatória de tokens em orçamento igual.
4. Diferenças de Domínio: A linguagem natural exibe um decaimento mais rápido da sensibilidade à truncagem ($\alpha \approx 0.44$) do que o código ($\alpha \approx 0.38$), sugerindo que o código retém dependências estruturais de longo alcance (escopos, importações) com mais força.
5. Robustez: A lei de potência vale até tamanhos de janela de $w=8192$, muito além da faixa típica de implantação de 4k, e é robusta a artefatos de codificação posicional.

5. Significado e Alegações

O artigo alega o seguinte significado:

• Fundação Teórica: Fornece a primeira caracterização quantitativa taxa-distorção para compressão de cache KV baseada na sensibilidade polinomial à truncagem empiricamente observada em LLMs, substituindo a suposição não verificada de mistura geométrica.
• Explicação de Práticas Empíricas: A lei de escalonamento polinomial ($\Theta(\epsilon^{-1/\alpha})$) explica por que sistemas implantados (por exemplo, Mistral com $w=4096$, StreamingLLM) exigem janelas significativamente maiores do que a mistura geométrica sugeriria.
• Optimalidade de Políticas Apenas de Sufixo: Estabelece que, para a classe de políticas apenas de sufixo, o escalonamento de memória é apertado. Se resumos recorrentes ou propagantes mais complexos possam superar esse escalonamento permanece um problema em aberto.
• Validação de "Sumidouro Mais Recente": Fornece uma justificativa teórica para o desempenho da evicção "sumidouro mais recente", vinculando o decaimento observado $k^{-2\alpha}$ à sensibilidade polinomial subjacente e à relação local quadrática KL-TV.

Limitações Reconhecidas pelos Autores:

• A análise é restrita a modelos com $\le 3B$ parâmetros devido a restrições computacionais; modelos maiores (7B–8B) são deixados para trabalhos futuros.
• A condição de "risco bayesiano bilateral" e as hipóteses de decaimento forward necessárias para limites apertados de alta probabilidade não são implicadas pela sensibilidade à truncagem sozinha e são tratadas como suposições adicionais.
• A estrutura assume arquiteturas Transformer padrão; modelos de espaço de estado (por exemplo, Mamba) não são analisados.
• O artigo não alega derivar o expoente $\alpha$ a partir de parâmetros arquitetônicos, mas sim medi-lo empiricamente.

Em resumo, o artigo argumenta que a sensibilidade polinomial à truncagem de contexto é uma propriedade fundamental de LLMs treinados que dita o trade-off memória-taxa, necessitando de janelas com escalonamento polinomial para compressão de alta precisão e fornecendo uma base teórica para a eficácia de estratégias de evicção baseadas em recência.