Memory-Efficient FastText: A Comprehensive Approach Using Double-Array Trie Structures and Mark-Compact Memory Management

Problema

O artigo aborda a "barreira de memória de subpalavras" (subword memory wall) inerente às implementações de FastText em escala industrial. Embora o FastText seja valorizado por sua capacidade de gerar vetores para palavras fora do vocabulário (OOV) via n-gramas de caracteres, sua implementação padrão depende de baldes de hash (hash buckets) para mapear n-gramas para linhas de embedding. Essa abordagem força duas concessões de engenharia:

1. Colisões Arbitrárias: N-gramas não relacionados são forçados a compartilhar a mesma linha de parâmetro, criando representações que não são fiéis a nenhum n-grama específico nem facilmente depuráveis.
2. Escalabilidade de Memória: Para reduzir colisões, o número de baldes de hash deve ser aumentado, o que infla linearmente a pegada de memória da matriz de entrada.

Para vocabulários grandes (ex: dezenas de milhões de palavras), o número de n-gramas distintos pode atingir centenas de milhões. Armazenar uma matriz exata e livre de colisões é frequentemente inviável devido às restrições de RAM, mas a alternativa (hashing) introduz ruído semântico incontrolável. O artigo argumenta que o hashing arbitrário é uma política de compressão evitável e que sistemas de subpalavras devem ser capazes de auditar por que as linhas são compartilhadas.

Metodologia: O Princípio "Exato-Depois-Comprimir"

A solução proposta inverte o fluxo de trabalho padrão. Em vez de comprimir via hashing antes do treinamento, o método estabelece primeiro identidades exatas para todas as subpalavras e, em seguida, aplica uma compressão estruturada. O pipeline consiste em quatro etapas principais:

1. Indexação Livre de Colisões (Double-Array Tries):
   Os autores substituem os baldes de hash por Double-Array Tries (DA-tries) tanto para palavras quanto para n-gramas. Um DA-trie é uma representação de array compacta que suporta busca determinística em tempo linear. Isso garante que cada n-grama observado receba uma identidade única e explícita (ID de linha) antes que qualquer compressão ocorra. A implementação é compatível com UTF-8, tratando caracteres de múltiplos bytes como unidades únicas.

2. Compartilhamento de Linhas Restrito à Estrutura:
   Uma vez estabelecidas as identidades exatas, o método explora uma regularidade linguística: n-gramas que compartilham prefixos ou sufixos longos frequentemente exibem alta similaridade de cosseno em seus vetores aprendidos.

• Fusão de Prefixo/Sufixo: O algoritmo realiza duas passagens. Primeiro, percorre o trie de prefixos para encontrar vizinhos estruturalmente relacionados. Segundo, inverte as strings e percorre um trie de sufixos.
• Limiar de Similaridade: A fusão é estritamente condicional. Duas linhas são fundidas apenas se sua similaridade de cosseno exceder um limiar alto (ex: $\tau = 0,999$). Isso garante que o compartilhamento seja baseado em evidências auditáveis em vez de colisões arbitrárias.

3. Gerenciamento de Memória Mark-Compact:
   Após a fusão, a matriz de embedding contém linhas "mortas" (aquelas que não são mais referenciadas por nenhum n-grama) e lacunas. Os autores adaptam uma estratégia de coleta de lixo mark-compact:

• As linhas vivas são identificadas e recebem novos IDs densos e contíguos.
• As linhas são movidas para frente para eliminar lacunas.
• Os valores terminais do DA-trie são atualizados para apontar para os novos IDs densos.
  Isso resulta em um layout de matriz denso e amigável ao cache.

4. Layout de Servimento (Serving Layout):
   O modelo final é serializado em um único arquivo binário contendo metadados, os DA-tries e a matriz de embedding compacta. Este arquivo suporta carregamento via memory-mapped (mmap), permitindo que o SO compartilhe páginas entre processos trabalhadores e possibilitando a reconstrução rápida e de baixa latência de vetores de palavras através da média das linhas exatas de palavra e subpalavra.

Principais Contribuições

• Pipeline Exato-Depois-Comprimir: Um design inovador que separa o mapeamento de identidade (DA-tries), o compartilhamento de parâmetros (fusões limitadas por similaridade) e o layout de servimento (mark-compact) para eliminar colisões de hash arbitrárias.
• Integração de DA-Trie: A formulação de indexação FastText livre de colisões usando DA-tries para ambos os casos (palavras e n-gramas), incluindo enumeração compatível com UTF-8.
• Algoritmo de Compressão de Duas Passagens: Um algoritmo de compartilhamento de linhas de prefixo e sufixo que utiliza a estrutura linguística para encontrar oportunidades de compressão seguras, evitando buscas globais de vizinho mais próximo dispendiosas.
• Implementação Pronta para Produção: Um protótipo estendido do FastText em C++ que suporta servimento via memory-mapped, fornecendo uma camada de memória lexical determinística para sistemas de recuperação híbrida.

Resultados Experimentais

O método foi avaliado em um benchmark de vocabulário chinês de grande escala contendo 30,1 milhões de palavras únicas e 287,4 milhões de n-gramas distintos.

• Redução de Memória: O modelo comprimido reduziu o uso de memória de 145,2 GB (FastText Original com Hash-Bucket) para 28,9 GB. Isso representa uma redução de 5,0× em comparação ao FastText original e uma redução de 9,9× em comparação a uma linha de base livre de hash totalmente não comprimida.
• Velocidade de Carregamento: O tempo de carregamento a frio (cold load) melhorou de 12,3 minutos para 3,2 minutos devido ao tamanho de arquivo menor e contíguo e à redução de falhas de página.
• Preservação de Qualidade: O modelo comprimido preservou a qualidade downstream dentro de 0,3 pontos do modelo livre de hash não comprimido em tarefas de similaridade de palavras, analogia, classificação de texto e Reconhecimento de Entidades Nomeadas (NER). Notavelmente, superou a linha de base original de hash-bucket em todas as tarefas, validando que eliminar colisões arbitrárias é mais benéfico do que reter cada parâmetro.
• Desempenho de Servimento: Em um benchmark de estilo produção, o modelo proposto alcançou uma redução de 34% na latência p95 (47ms para 31ms) e um aumento de 58% no throughput (850 para 1340 requisições/seg).

Significância e Alegações

O artigo posiciona este trabalho não como um substituto para os embeddings modernos de Grandes Modelos de Linguagem (LLMs), mas como um componente de infraestrutura complementar para a "era dos LLMs".

• Camada de Memória Lexical: Os autores argumentam que tabelas de subpalavras compactas e livres de colisões servem como uma camada de memória lexical determinística, inspecionável e barata. Esta camada é ideal para recuperação de primeira etapa, geração de características e tratamento de entidades de cauda longa (nomes, erros de digitação, identificadores) que grandes codificadores podem tratar de forma inconsistente.
• Auditabilidade: Ao substituir colisões de hash opacas por identidades explícitas, o sistema permite que engenheiros rastreiem exatamente por que duas linhas foram fundidas, tornando o processo de compressão mensurável e replicável.
• Recuperação Híbrida: O método preenche uma lacuna específica em pipelines de Geração Aumentada por Recuperação (RAG): fornecer um substrato lexical multilingue, pequeno e previsível que pode ser combinado com recuperadores densos e modelos de expansão esparsa sem os altos custos de atualização ou a sobrecarga de memória de grandes índices de embedding.

O artigo conclui que, para sistemas de NLP industrial, o padrão de "substituir colisões opacas por identidades explícitas, depois comprimir usando estrutura exposta" oferece um caminho prático para o deployment econômico e cobertura robusta de cauda longa.