Copy-as-Decode: Grammar-Constrained Parallel Prefill for LLM Editing

Título: Copy-as-Decode: Prefill Paralelo Restrito por Gramática para Edição de LLMs

1. O Problema

Os Grandes Modelos de Linguagem (LLMs) atuais editam texto e código regenerando a saída completa de forma autoregressiva (token por token), mesmo quando a grande maioria dos tokens da saída é idêntica à entrada (ex: 74–98% do conteúdo em edições típicas).

• Ineficiência: Essa abordagem desperdiça recursos computacionais, pois o modelo gasta passos de inferência para "regerar" conteúdo que já está presente no prompt.
• Latência: O tempo de resposta escala com o comprimento total da saída, não com o tamanho da edição real.
• Risco de Alucinação: Ao regenerar tokens que deveriam ser fixos, o modelo pode introduzir erros ou desvios indesejados.

2. Metodologia: Copy-as-Decode

O artigo propõe um mecanismo de camada de decodificação chamado Copy-as-Decode, que transforma a geração de edições em um processo de decodificação estruturada sobre uma gramática de duas primitivas, combinada com uma otimização de nível de sistema (KV Cache).

A. Gramática e Restrições

O modelo não gera texto livre, mas sim um "programa" de edição definido por uma gramática estrita:

• <copy lines="i-j"/>: Copia um intervalo de linhas (i a j) do documento de entrada original.
• <gen> ... </gen>: Gera novo conteúdo livremente.
• Máquina de Estados Finita (FSM): Um FSM em nível de token garante que o modelo siga estritamente essa gramática, restringindo os logits do modelo para que apenas tokens válidos (como números de linha dentro de uma tag <copy>) sejam emitidos. Isso garante uma taxa de parse de 100%.

B. O Mecanismo de "Splice" (Junção) via Prefill Paralelo

Esta é a inovação central de sistema:

1. Quando o modelo decide executar uma operação <copy lines="i-j"/>, os tokens correspondentes já são conhecidos (são literais da entrada).
2. Em vez de gerar esses tokens um por um (decodificação autoregressiva), o sistema realiza um prefill paralelo único.
3. Os tokens das linhas i a j são injetados diretamente no KV Cache (Cache de Chave-Valor) do modelo em uma única passagem forward.
4. Isso substitui $N$ passos de decodificação autoregressiva por 1 passo de prefill, acelerando drasticamente a operação.

C. Resolver Determinístico

Um resolver externo e determinístico processa o programa gerado pelo modelo e o documento original para produzir o documento editado final. Isso garante que a lógica de aplicação da edição seja perfeita, isolando falhas apenas na seleção dos intervalos (spans) pelo modelo.

3. Contribuições Principais

O artigo não propõe apenas um novo modelo, mas um mecanismo com três propriedades mensuráveis que não dependem do treinamento do modelo base:

1. Aceleração de Kernel (Speedup): Demonstra que copiar tokens via prefill paralelo é 6.8x a 303x mais rápido do que a decodificação autoregressiva para intervalos de 8 a 512 tokens em GPUs A100.
2. Teto de Cópia (Copy Ceiling): Analisa dados reais e mostra que 74% a 98% dos tokens de ouro (edições corretas) podem ser cobertos por primitivas de cópia de nível de linha.
3. Perda de Pipeline Nula (Losslessness): Com programas "oráculo" (perfeitos), o resolver reproduz a edição correta em 100% dos casos (482/482), provando que o mecanismo em si não introduz erros; falhas futuras seriam apenas devido à seleção imperfeita de intervalos pelo modelo.

4. Resultados Quantitativos

• Aceleração de Kernel:

  • Em modelos Qwen2.5 (1.5B e 7B), copiar 512 tokens via prefill paralelo é até 303x mais rápido (no modelo 1.5B) do que gerar autoregressivamente.
  • A aceleração cresce linearmente com o tamanho do intervalo em regimes dominados por overhead e satura em regimes limitados por computação.

• Limites Teóricos de Desempenho ($bnd_{exact}$):

  • Combinando a aceleração do kernel com a cobertura de dados reais, o artigo calcula um limite superior de velocidade de parede (wall-clock):
    • ProbeEdit (Texto curto): Até 29.0x mais rápido.
    • HumanEvalPack-Fix (Python): Até 3.45x mais rápido.
    • HumanEvalPack-Fix (JavaScript): Até 4.18x mais rápido.
    • Média Ponderada: 13.0x de aceleração potencial.

• Sensibilidade à Seleção de Intervalos:

  • O mecanismo é extremamente sensível a erros de seleção. Um ruído de apenas 1 linha nos índices de início/fim faz a taxa de acerto (EM) cair de 100% para 15.48% (em média). Isso define um alvo rigoroso para o treinamento de futuros selecionadores.

• Pilot de Treinamento (SFT):

  • Um piloto de Supervised Fine-Tuning (SFT) no Qwen2.5-Coder-1.5B aumentou a taxa de acerto (EM) de 0% (base não treinada) para 12–17% em um conjunto de teste. Embora baixo para produção, isso valida a aprendizabilidade do mecanismo.

• Comparação com Formatos Existentes:

  • O formato "Copy-as-Decode" supera o "Search/Replace" (usado em ferramentas como Aider) em fidelidade (evita ambiguidade de âncora) e supera o "Unified Diff" em eficiência de tokens (menor overhead de cabeçalho).

5. Significado e Implicações

• Mudança de Paradigma: O trabalho desafia a ideia de que a edição deve ser uma geração livre. Ao tratar a edição como um programa de cópia e geração, alinha a estrutura de saída com a otimização de hardware (KV Cache).
• Eficiência sem Treinamento Massivo: O mecanismo oferece ganhos de velocidade imediatos e garantidos apenas pela mudança de formato de saída e implementação de sistema, sem necessidade de re-treinar o modelo base para a tarefa de edição em si (o ganho de velocidade é independente da qualidade do modelo).
• Caminho para o Futuro: O artigo identifica que o gargalo atual não é a velocidade de cópia, mas a precisão do modelo em selecionar os intervalos corretos. O trabalho abre caminho para:
  • Extensões para nível de token (não apenas linha).
  • Integração com servidores de inferência modernos (vLLM, SGLang).
  • Treinamento de selecionadores especializados para atingir o teto de desempenho teórico.

Em resumo, Copy-as-Decode oferece uma via para tornar a edição de LLMs drasticamente mais rápida e precisa, transformando a regeneração de conteúdo em uma operação de "copiar e colar" otimizada a nível de hardware, desde que o modelo consiga identificar o que copiar.