A Continuous-Time Markov Chain Framework for Insertion Language Models

Resumo Técnico: Um Framework de Cadeia de Markov de Tempo Contínuo para Modelos de Linguagem de Inserção

Declaração do Problema

Modelos de linguagem autorregressivos (ARMs) geram sequências estritamente da esquerda para a direita, o que limita sua flexibilidade para tarefas que exigem geração não sequencial, como planejamento e preenchimento baseado em submetas (infilling). Embora os Modelos de Difusão Mascarada (MDMs) permitam ordens de geração arbitrárias e passos de múltiplos tokens, eles frequentemente enfrentam dificuldades com sequências de comprimento variável, pois tratam tokens de preenchimento (padding) como itens comuns do vocabulário, impactando a qualidade da geração e restringindo a amostragem a procedimentos de bloco baseados na esquerda para a direita.

Os atuais Modelos de Linguagem de Inserção (ILMs) abordam essas limitações inserindo iterativamente tokens em posições arbitrárias, lidando naturalmente com comprimentos variáveis e restrições de ordenação relativa. No entanto, as formulações atuais de ILM dependem de objetivos de treinamento e procedimentos de amostragem ad-hoc que carecem de um fundamento probabilístico rigoroso. Além disso, os ILMs existentes frequentemente lutam com o desafio de determinar quando interromper a geração.

Metodologia

Os autores propõem os Modelos de Linguagem de Inserção Baseados em Difusão (DILMs), um framework principado derivado de primeiros princípios usando uma Cadeia de Markov de Tempo Contínuo (CTMC) no espaço de sequências de comprimento variável.

1. O Processo de Ruído (Noising Process)

O processo de ruído direto é formulado como uma CTMC que deleta tokens de uma sequência de verdade fundamental ($x_0$) uniformemente ao acaso sobre um intervalo de tempo $[0, T]$.

• Espaço de Estados: O espaço de estados inclui tanto o conteúdo da sequência quanto seu comprimento.
• Mecanismo de Deleção: Tokens são removidos um por um (ou via taxas independentes) com uma taxa dependente do tempo $\sigma_t$.
• Duas Variantes:
  • Ruído Conjunto (Joint Noising): As deleções ocorrem como um único evento, onde o número de tokens removidos segue uma distribuição de Poisson, e as posições são escolhidas uniformemente.
  • Ruído Independente (Independent Noising): Cada posição possui uma taxa de deleção independente, modelada via uma distribuição Binomial.

2. O Processo Generativo (Reverse CTMC)

O processo generativo é o reverso temporal do processo de ruído, construindo uma sequência através da inserção de tokens. Os autores derivam um Limite Inferior de Evidência (ELBO) para a log-verossimilhança dos dados sob este processo reverso. Eles propõem duas parametrizações para a matriz de taxa reversa $\hat{R}^\theta_t$:

• DILM-S (Inserção Única): Modela a probabilidade conjunta de um local de inserção e um item do vocabulário, bem como o "comprimento restante" (o número de tokens restantes para serem inseridos). Esta parametrização prevê uma inserção por vez.
• DILM-M (Múltipla Inserção): Modela taxas de inserção independentes por posição. Isso permite que o modelo amostre múltiplas inserções simultaneamente em diferentes lacunas (gaps) em um único passo.

Ambas as variantes utilizam um backbone Transformer com normalização de camada adaptativa (AdaLN) condicionada ao tempo $t$. Para lidar com a condição de parada, os modelos preveem o comprimento restante (ou tamanhos das lacunas), permitindo que a geração termine quando a taxa de inserção prevista cai para zero, em vez de depender de um classificador de parada separado ou hiperparâmetros.

3. Amostragem

A amostragem é realizada via discretização de Euler (para DILM-S) ou um procedimento de $\tau$-leaping restrito (para DILM-M). Esses métodos permitem um compromisso entre a qualidade da amostra e o número de passagens de ida (passos de amostragem), uma flexibilidade não presente nos ILMs padrão.

Principais Contribuições

1. Framework Principado: O artigo deriva um objetivo de denoising estilo difusão para geração baseada em inserção a partir de primeiros princípios usando um framework de CTMC, indo além de formulações ad-hoc.
2. Unificação: Os procedimentos de amostragem propostos unificam as formulações existentes de ILM, mostrando que elas são casos especiais deste framework mais amplo.
3. Duas Parametrizações: Os autores introduzem duas variantes (DILM-S e DILM-M) que diferem na forma como modelam as taxas de inserção (conjunta vs. independente), oferecendo flexibilidade na eficiência de amostragem e na geração de múltiplos tokens.
4. Fundamentação Teórica: O trabalho fornece uma derivação rigorosa do ELBO e discute considerações computacionais para treinamento e amostragem.

Resultados Empíricos

Os autores avaliam os DILMs em tarefas de planejamento sintético e benchmarks de modelagem de linguagem.

• Planejamento Sintético (Tarefas de Grafo Estrela): Em tarefas de planejamento de comprimento variável onde ARMs e MDMs falham, DILM-S e DILM-M alcançam precisão quase perfeita (comparável aos ILMs existentes), demonstrando que a abordagem baseada em difusão retém os benefícios da geração baseada em inserção para tarefas estruturais complexas.
• Modelagem de Linguagem (LM1B e OpenWebText):
  • No benchmark LM1B, DILM-S e DILM-M são competitivos com os ILMs e MDMs existentes em termos de log-verossimilhança negativa por token (NLL).
  • No OpenWebText, as variantes DILM superam as linhas de base de ILM e MDM.
  • Flexibilidade de Amostragem: Uma descoberta fundamental é a capacidade de trocar a qualidade da geração pelo número de passos de amostragem. Ao contrário dos ILMs existentes, que mostram curvas de perplexidade planas ou erráticas, os DILMs exibem uma melhoria suave na perplexidade generativa conforme os passos de amostragem aumentam.

Significância e Alegações

O artigo afirma que os DILMs oferecem uma alternativa probabilisticamente principada aos modelos de inserção existentes, fornecendo um objetivo de treinamento e um procedimento de amostragem rigorosos. O framework retém as vantagens centrais dos ILMs — ordem de geração flexível e tratamento natural de comprimento variável — enquanto aborda as limitações de critérios de parada ad-hoc e falta de fundamentação teórica.

Os autores observam que, embora o DILM-M permita múltiplas inserções, ele é atualmente restrito a um token por lacuna, limitando a modelagem de correlações de spans contíguos de tokens. Eles identificam a inserção de spans de múltiplos tokens e o escalonamento para modelos maiores como direções para trabalhos futuros. O trabalho estabelece uma base para tratar a geração baseada em inserção como um processo de difusão de tempo contínuo, unificando abordagens heurísticas anteriores sob um único guarda-chuva teórico.