Resumo Técnico: Geração Visual Autorregressiva por Árvore de Abrangência (STAR)

Definição do Problema

Modelos autorregressivos (AR) baseados em Transformers apenas com Decodificador (Decoder-only) alcançaram um sucesso notável na geração de linguagem e estão sendo cada vez mais aplicados à geração visual via predição do próximo patch (próximo fragmento). No entanto, os modelos visuais AR convencionais geralmente dependem de uma ordem de varredura raster (raster-scan) fixa (dependência unidirecional). Embora essa ordem proporcione um alto desempenho de amostragem, ela impõe uma limitação estrutural: o modelo não pode condicionar-se a tokens que não apareçam como prefixos na sequência predefinida. Essa rigidez dificulta a edição nativa de imagens (ex: inpainting), onde regiões arbitrárias de uma imagem devem ser mascaradas e completadas com base no contexto restante.

Para enfrentar isso, abordagens recentes empregam a permutação aleatória de sequências de tokens durante o treinamento para expor os modelos a diversas ordens. Contudo, o artigo observa que treinar com ordens de sequência arbitrárias frequentemente leva a um desempenho de amostragem degradado em comparação com modelos de varredura raster fixa. Isso cria um compromisso (trade-off): ordens fixas oferecem desempenho, mas carecem de flexibilidade, enquanto permutações aleatórias oferecem flexibilidade, mas sacrificam a qualidade de geração e a velocidade de convergência.

Metodologia: Árvore de Abrangência Autorregressiva (STAR)

Os autores propõem o STAR, uma estratégia de randomização estruturada da ordem de sequência que preenche essa lacuna utilizando as ordens de travessia de Árvores de Abrangência Uniformes (UST - Uniform Spanning Trees) no reticulado definido pelas posições dos patches da imagem.

1. Randomização Estrutural via Árvores de Abrangência Uniformes

Em vez de amostrar do espaço de todas as $N!$ permutações, o STAR amostra do espaço de árvores de abrangência em um reticulado de taxicab regular $G=(V, E)$, onde os vértices representam as posições dos patches.

• Seleção da Raiz: Um canto aleatório da imagem é selecionado como o nó raiz $r$. Essa escolha é motivada pela observação de que ordens de varredura raster (começando pelos cantos) costumam ter desempenho superior, provavelmente devido ao viés central (objetos salientes têm menor probabilidade de aparecer nos cantos) e à localidade (patches adjacentes são mais fáceis de prever).
• Ordem de Travessia: A ordem da sequência $\tau$ é determinada por uma travessia de Busca em Largura (BFS - Breadth-First Search) da árvore de abrangência amostrada.
• Base Teórica: Os autores hipotetizam que a vantagem das sequências predefinidas advém da preservação do conhecimento prévio (viés central e localidade). Eles verificam isso medindo a entropia do modelo condicional, mostrando que tokens mais próximos de tokens previamente preditos (em termos de distância na árvore) exibem menor entropia, de forma semelhante ao comportamento da varredura raster. O número de árvores de abrangência cresce exponencialmente ($\sim \exp(N \cdot z_G)$), mas permanece um subconjunto muito menor e mais estruturado do espaço total de permutações.

2. Inferência e Completude de Postfix (Inpainting de Imagem)

Um desafio crítico para modelos AR em inpainting é garantir que uma observação parcial dada (a região não mascarada) apareça como um prefixo na ordem da sequência, permitindo que a região mascarada seja gerada como um postfix.

• Amostragem por Rejeição: Diferente da permutação aleatória, onde a separação prefixo/postfix é trivial, o STAR deve amostrar uma árvore de abrangência onde a travessia BFS coloque naturalmente a região não mascarada antes da região mascarada.
• Algoritmo:
  1. Identificar os limites da região não mascarada.
  2. Selecionar um nó raiz $r$ que seja o mais distante (em distância de Manhattan) do limite mais próximo da região não mascarada para maximizar a probabilidade de a região não mascarada ser visitada primeiro.
  3. Amostrar uma árvore de abrangência na região não mascarada. Se a profundidade máxima da árvore não satisfizer a condição de que todos os vértices de limite sejam visitados antes de qualquer vértice mascarado, a amostra é rejeitada (amostragem por rejeição).
  4. Uma vez encontrada uma árvore válida para a região não mascarada, árvores de abrangência são amostradas para as regiões mascaradas e conectadas aos vértices de limite para completar a árvore global.
• Eficiência: Os autores demonstram que o uso de BFS com a seleção de "raiz mais distante" reduz significativamente o número de tentativas de rejeição em comparação com a Busca em Profundidade (DFS), tornando a inferência eficiente.

3. Arquitetura do Modelo

O STAR requer mudanças mínimas na arquitetura padrão de Transformer apenas com Decodificador. Ele incorpora:

• Máscaras de atenção causal.
• Recursos adicionais para condicionar na posição do próximo token (usando embeddings posicionais aprendíveis), de forma semelhante a métodos anteriores baseados em permutação.
• Não são necessárias mudanças arquiteturais complexas (ex: atenção bidirecional ou tokenizadores especializados).

Principais Contribuições

1. Estratégia de Randomização Estruturada: A proposta do uso da travessia BFS de árvores de abrangência uniformes como uma ordem de sequência para geração visual autorregressiva. Esta estratégia preserva estruturalmente os vieses de imagem (viés central, localidade) enquanto introduz randomização suficiente para flexibilidade.
2. Compromisso Performance-Flexibilidade: A demonstração de que a travessia BFS de USTs é suficiente para alcançar os benefícios da permutação aleatória (diversas ordens de sequência) sem a degradação de desempenho tipicamente associada a permutações arbitrárias. Isso é alcançado sem aumentar a complexidade de treinamento.
3. Suporte Nativo para Edição de Imagem: A introdução de um mecanismo (amostragem por rejeição com BFS) que permite a modificação em nível de região (inpainting) com mudanças arquiteturais mínimas, abordando uma limitação fundamental dos modelos AR convencionais.

Resultados Experimentais

Os autores avaliam o STAR no ImageNet-1k (resolução de 256x256) usando tarefas de geração condicionada por classe e inpainting de imagem.

• Geração de Imagem: Os modelos STAR (STAR-B, L, XL, XXL) alcançam desempenho comparável aos modelos de estado da arte (ex: RAR, DiT, LlamaGen) em termos de FID (Fréchet Inception Distance) e IS (Inception Score). Notavelmente, o STAR-XXL atinge um FID de 1.55, superando o RAR-XXL (1.48) e o RandAR-XXL (2.15), mantendo pontuações competitivas.
• Inpainting de Imagem: O STAR supera significativamente tanto os modelos de ordem fixa (RAR) quanto os modelos de permutação aleatória (RandAR) em tarefas de inpainting.
  • Em várias taxas de mascaramento (0.1 a 0.9), o STAR mantém altos escores de FID e IS.
  • Em contraste, o RAR (varredura raster fixa) mostra uma queda significativa no desempenho de inpainting porque não consegue lidar naturalmente com máscaras arbitrárias como prefixos.
  • O RandAR mantém a capacidade de inpainting, mas sofre de uma qualidade de geração inferior em comparação ao STAR.
• Estudos de Ablação:
  • Localidade: A permutação aleatória falha em superar o STAR, sugerindo que ordens de sequência que violam a localidade são prejudiciais à convergência.
  • Viés Central: A seleção aleatória de cantos como raízes funciona bem para imagens com forte viés central e generaliza melhor do que a permutação aleatória para imagens com viés central mais fraco.
  • Análise de Entropia: Modelos treinados com STAR exibem uma escala mais uniforme de entropia do modelo condicional através das posições dos tokens em comparação com a permutação aleatória, o que se correlaciona com uma melhor convergência.
  • Sobrecarga (Overhead): A sobrecarga computacional para amostrar árvores de abrangência é insignificante (< 0.0004% do tempo total de inferência). A amostragem por rejeição para inpainting é altamente eficiente, tipicamente exigindo menos de 5 tentativas com BFS.

Significância e Alegações

O artigo afirma que o STAR oferece uma solução simples e eficaz para o antigo compromisso entre desempenho de amostragem e flexibilidade de ordem de sequência na geração visual AR. Ao alavancar as propriedades estruturais das árvores de abrangência uniformes, o STAR:

• Preserva a arquitetura Transformer apenas com Decodificador, facilitando a integração em modelos multimodais de fusão precoce.
• Evita a necessidade de estratégias de treinamento complexas como o aninhamento de ordem (alternância de ordens aleatórias para fixas durante o treinamento) ou tokenizadores especializados.
• Fornece suporte nativo para edição de imagem (inpainting) sem sacrificar a qualidade de geração.

Os autores posicionam o STAR como um "bloco de construção básico" para futuros modelos visuais AR, enfatizando que sua simplicidade permite que seja facilmente adotado e estendido para modelos generativos multimodais. O trabalho sugere que o sucesso dos modelos AR depende não apenas da arquitetura do modelo, mas da randomização estruturada da ordem da sequência para alinhar-se com as propriedades intrínsecas dos dados visuais.