Resumo Técnico: Estimativa de Distância de Variação Total em Modelos Autorregressivos

1. Declaração do Problema

As implementações modernas de Large Language Models (LLMs) frequentemente envolvem escolhas de implementação e otimizações de inferência (ex: batching, kernels customizados, quantização, decodificação especulativa) que podem fazer com que dois motores que servem "o mesmo modelo" produzam distribuições de saída significativamente diferentes. Embora trabalhos anteriores tenham focado em medir essas diferenças via divergência de Kullback-Leibler (KL), o artigo argumenta que a KL é frequentemente inadequada para essa tarefa. A divergência de KL é ilimitada quando as distribuições possuem suportes disjuntos (uma ocorrência comum devido ao truncamento top-$k$ ou bugs), tornando impossível estimá-la com precisão $\epsilon$ a partir de amostras finitas sem a recuperação do suporte.

Em contraste, a distância de Variação Total (TV) é limitada no intervalo $[0, 1]$, interpretável e robusta a pequenas diferenças de implementação que alteram o suporte. O artigo aborda o problema de estimar a distância TV entre duas distribuições autorregressivas de comprimento $n$, $\pi$ e $\mu$, sobre um alfabeto de tokens $\Sigma$ (tamanho $m$), para um erro aditivo $\epsilon$. O estudo considera três modelos distintos de acesso a essas distribuições:

1. Acesso por Amostragem (Sample Access): Consultar um prefixo e receber uma amostra da distribuição do próximo token.
2. Acesso por Logit (Logit Access): Consultar um prefixo e receber o vetor completo de log-probabilidades do próximo token (exato).
3. Acesso por Logit Ruidoso (Noisy Logit Access): Consultar um prefixo e receber um estimador não enviesado da distribuição do próximo token com variância relativa $\sigma^2$ limitada.

2. Metodologia e Resultados Teóricos

O artigo fornece algoritmos e limites inferiores para a estimativa de TV sob cada modelo de acesso, formalizando os compromissos entre complexidade de consulta, comprimento da sequência $n$, tamanho do suporte $K$ e nível de ruído $\sigma$.

A. Acesso por Logit (Exato)

Metodologia: Os autores observam que $O(n)$ consultas a oráculos de logit de prefixo permitem o cálculo exato da razão de verossimilhança $\pi(x)/\mu(x)$ para qualquer sequência $x$. Eles adaptam um estimador de razão de verossimilhança de [CR14], que estima a distância TV amostrando sequências de uma distribuição e avaliando a razão de verossimilhança sob a outra.
Resultado (Teorema 2): Existe um algoritmo que estima a distância TV com erro $\epsilon$ usando $O(n/\epsilon^2)$ consultas. Este limite é mostrado como sendo apertado (até fatores constantes) via uma construção de limite inferior que reduz a estimativa de TV ao aprendizado de um parâmetro de Bernoulli oculto $p$, onde revelar uma única amostra de $p$ requer $\approx n$ consultas.
Significância: Esta é a primeira formalização da estimativa de distância TV sob acesso por logit, oferecendo uma dependência linear em relação ao comprimento da sequência $n$ e eliminando a dependência do tamanho do alfabeto $m$ ou do tamanho do suporte $K$.

B. Acesso por Amostragem

Metodologia: Sob acesso por amostragem, o algoritmo não pode calcular diretamente as razões de verossimilhança. O artigo propõe um estimador que melhora o estado da arte de $O(n^3 m / \epsilon^5)$ de [MKP25]. A nova abordagem evita "domar" distribuições (preenchimento com ruído uniforme), o que anteriormente introduzia dependência do tamanho total do alfabeto $m$. Em vez disso, ela aproveita a estrutura específica dos modelos autorregressivos e o tamanho máximo de suporte $K$ das distribuições do próximo token.
Resultado (Teorema 1): O algoritmo proposto estima a distância TV com erro $\epsilon$ usando $\tilde{O}(n^2 K / \epsilon^2)$ consultas. Um limite inferior correspondente de $\Omega(n K / \epsilon^2 \log K)$ é fornecido.
Significância: Isso melhora a dependência de $n$ de cúbica para quadrática, de $\epsilon$ de $1/\epsilon^5$ para $1/\epsilon^2$, e substitui o tamanho do alfabeto $m$ pelo tamanho do suporte $K$, que é muito menor na prática (ex: amostragem top-$k$).

C. Acesso por Logit Ruidoso

Metodologia: Reconhecendo que os motores de inferência do mundo real introduzem ruído (devido a batching, variações de kernel ou problemas de precisão), os autores modelam o acesso como um estimador não enviesado com variância relativa $\sigma^2$. Eles empregam um esquema de redução de variância de Monte Carlo de Múltiplos Níveis (MLMC).

1. Eles constroem uma soma telescópica de estimadores $Z_\ell$ em diferentes níveis de precisão (controlados pelo número de repetições $r_\ell$).
2. Ao acoplar as amostras entre os níveis (usando a mesma trajetória $X$ para níveis adjacentes), eles garantem que a variância do estimador de diferença decaia geometricamente.
3. Isso permite trocar consultas mais baratas e de alta variância em níveis grosseiros por consultas mais caras e de baixa variância em níveis finos.
   Resultado (Teorema 3): O algoritmo estima a distância TV com erro $\epsilon$ usando $\tilde{O}((n + n^2 \sigma^2)/\epsilon^2)$ consultas.
   Significância: Este resultado interpola suavemente entre o limite de acesso por amostragem (onde $\sigma^2 \approx K$) e o limite de acesso por logit (onde $\sigma^2 = 0$). Demonstra que, mesmo com oráculos ruidosos, a distância TV permanece estimável onde a divergência KL poderia ser infinita.

3. Avaliação Empírica

Os autores validam suas descobertas teóricas através de experimentos comparando dois motores de inferência de produção, vllm e sglang, servindo pesos idênticos do Qwen3-0.6B.

• Caracterização de Ruído: Eles mediram o desvio padrão relativo $\sigma$ das log-probabilidades através de diferentes backends (cuDNN, FlashAttention-2) e condições de batching. Constataram que, embora algumas configurações sejam determinísticas isoladamente, as condições de serviço introduzem ruído significativo.
• Estimativa de Distância: A distância TV estimada entre vllm e sglang foi encontrada como substancial (ex: $\approx 0,58$ para comprimento de sequência $n=500$). A distância foi decomposta em um componente de "suporte compartilhado" (diferenças de log-probabilidade) e um componente de "desajuste de suporte" (tokens presentes no top-$k$ de um motor mas não no outro), sendo que este último contribuiu significativamente para a distância total.
• Eficiência MLLC: Os experimentos confirmaram a utilidade do cronograma de múltiplos níveis. Comparado a estratégias de repetição de nível único fixas, o cronograma de múltiplos níveis escolhido via piloto alcançou a mesma precisão com até $1,28\times$ menos consultas ao oráculo. Os resultados também destacaram que a distância estimada é sensível às configurações de serviço (tamanho do batch) e ao conteúdo do prompt.

4. Contribuições Principais e Significância

• Limites Teóricos: O artigo estabelece limites de complexidade de consulta apertados para a estimativa de distância TV em modelos autorregressivos sob três modelos de acesso, resolvendo a dependência em relação ao comprimento da sequência $n$ e ao tamanho do suporte $K$.
• Robustez ao Ruído: Introduz um modelo para acesso por logit ruidoso que captura inconsistências de inferência do mundo real, mostrando que a distância TV pode ser estimada mesmo quando os valores de logit são não-determinísticos.
• Relevância Prática: O trabalho fornece uma ferramenta para auditar provedores de LLM e verificar se otimizações de inferência (como quantização ou diferentes backends) não alteram significativamente a distribuição de saída.
• Limitações da KL: O artigo reforça o argumento de que a distância TV é uma métrica mais prática do que a divergência KL para comparar LLMs, particularmente quando desajustes de suporte (comuns em amostragem top-$k$) tornam a KL infinita ou inestimável.

Os autores concluem que, embora a distância TV seja estimável, a complexidade de consulta depende fortemente do nível de ruído e do modelo de acesso específico, e que a separação entre a dependência linear e quadrática de $n$ para diferentes modelos de acesso permanece como uma questão aberta para trabalhos futuros.