Algoritmo de recomendação do Twitter/X (código aberto)

01 · CONTEXTO

Do oceano de Tweets ao feed

O Twitter descreve o desafio como destilar cerca de 500 milhões de Tweets publicados por dia até um punhado de Tweets no feed For You. O post de engenharia é de 31 de março de 2023 e foca esse feed da timeline home.

O post organiza o pipeline em três estágios: buscar os melhores Tweets em diferentes fontes (candidate sourcing), ranquear cada Tweet com um modelo de aprendizado de máquina e aplicar heurísticas e filtros, como remover Tweets de usuários bloqueados.

Quem monta o feed é o Home Mixer, um serviço construído sobre o Product Mixer, um framework em Scala do próprio Twitter para montar feeds de conteúdo. Ele conecta fontes de candidatos, funções de pontuação, heurísticas e filtros.

02 · O PIPELINE

Uma requisição de ponta a ponta

Por requisição, o sistema tenta extrair os melhores 1500 Tweets de um conjunto de centenas de milhões. Em média, o For You tem 50% de Tweets de quem o usuário segue e 50% de fora da rede, mas isso varia por usuário.

1. O app pede o feed For You ao Home Mixer, o serviço principal que constrói e serve as timelines home.

2. O Home Mixer busca candidatos em fontes diferentes: o índice de busca, o grafo de interações em memória e o SimClusters ANN.

3. Os candidatos vêm de dois grupos: quem o usuário segue e quem ele não segue.

4. Os candidatos reunidos são pontuados pelo heavy ranker, sem considerar de qual fonte vieram.

5. Depois da pontuação, o Home Mixer aplica heurísticas e filtros, como diversidade de autor e filtragem de visibilidade.

6. Por fim, o feed é misturado com anúncios, recomendações de quem seguir e prompts, e devolvido ao app.

03 · FONTES DE CANDIDATOS

Dentro e fora da rede

A fonte In-Network é a maior e busca os Tweets mais relevantes e recentes de quem o usuário segue. Ela ordena esses Tweets com um modelo de regressão logística, e o componente mais importante desse ranqueamento é o Real Graph, que prevê a probabilidade de engajamento entre dois usuários.

No repositório, o índice de busca aparece como a fonte dos posts da rede, e a documentação diz que cerca de metade dos posts vem dela; o índice (Earlybird) usa um light ranker para ranquear posts. O post também relata que o time deixou de usar o Fanout Service, de 12 anos, que fornecia Tweets da rede a partir de um cache por usuário.

Fora da rede, o problema é mais difícil: como saber se um Tweet será relevante se o usuário não segue o autor? O post descreve duas abordagens. A primeira percorre o grafo de engajamentos e follows, perguntando quais Tweets as pessoas que o usuário segue engajaram há pouco e quem curte Tweets parecidos com os dele.

Para executar essas travessias, o time desenvolveu o GraphJet, que mantém em tempo real um grafo de interações entre usuários e Tweets. Segundo o post, essas heurísticas servem cerca de 15% dos Tweets da home, e as abordagens por embeddings se tornaram a maior fonte fora da rede.

04 · SIMCLUSTERS

Comunidades como embeddings

O SimClusters descobre comunidades ancoradas em usuários influentes, com um algoritmo próprio de fatoração de matriz. O post fala em 145k comunidades, atualizadas a cada três semanas. Usuários e Tweets são representados no espaço de comunidades e podem pertencer a várias; quanto mais usuários de uma comunidade curtem um Tweet, mais ele se associa a ela.

A documentação do SimClusters mostra que o grafo de follows pode ser visto como um grafo bipartido entre produtores, que são os usuários seguidos, e consumidores. As representações alimentam a recomendação de Tweets por meio do serviço online SimClusters ANN.

1. A partir do grafo de follows, a similaridade entre produtores é medida por cosseno entre seus seguidores, e uma detecção de comunidades por amostragem de Metropolis-Hastings atribui uma comunidade a cada produtor.

2. Em produção, o conjunto Known For cobre os 20M principais produtores e cerca de 145000 comunidades.

3. Os embeddings de usuários e Tweets são construídos sobre as comunidades inferidas, e um job mantém o mapeamento entre comunidades e Tweets, guardando os de maior pontuação.

4. Na hora da requisição, o Home Mixer chama o SimClusters ANN, que devolve candidatos de Tweets dado um embedding de SimClusters.

5. O algoritmo tradicional buscaria 15,000 embeddings por chamadas de API; o cosseno aproximado reduz as operações de I/O para economizar tempo de resposta.

05 · RANQUEAMENTO E FILTROS

Heavy ranker e soma ponderada

Com cerca de 1500 candidatos, a pontuação prevê diretamente a relevância de cada Tweet e é o principal sinal de ranqueamento. Nesse ponto todos os candidatos são tratados igualmente, sem considerar a fonte.

O ranqueamento usa uma rede neural de cerca de 48M de parâmetros, treinada continuamente sobre interações com Tweets para otimizar engajamento positivo. Ela considera milhares de atributos e produz dez rótulos, cada um a probabilidade de um tipo de engajamento.

O README do heavy ranker explica que as saídas são combinadas em uma nota final por soma ponderada das probabilidades. Os pesos vêm de um arquivo de configuração e podem ser ajustados a qualquer momento; a tabela mostra alguns valores de 5 de abril de 2023.

1. Antes de pontuar, o Home Mixer busca cerca de 6000 atributos necessários ao ranqueamento.

2. O heavy ranker recebe atributos do Tweet e do usuário para quem ele está sendo recomendado.

3. As saídas do modelo são combinadas em uma nota final por soma ponderada, com pesos vindos de um arquivo de configuração lido pela camada de serving.

4. O heavy ranker é um dos estágios finais do funil, sucedido principalmente por heurísticas de filtragem.

5. Se o pipeline de Tweets pontuados falhar, existe um pipeline de reserva em ordem cronológica reversa.

Depois da pontuação, filtros e heurísticas equilibram o feed: evitam Tweets consecutivos demais do mesmo autor, equilibram Tweets da rede e de fora dela e excluem Tweets de fora da rede sem conexão de segundo grau, como salvaguarda de qualidade.

06 · ESCALA E LIÇÕES

Custo de produção e limites do código aberto

O post informa que o pipeline roda aproximadamente 5 bilhões de vezes por dia e leva em média menos de 1,5 segundo. Cada execução consome 220 segundos de CPU, quase 150 vezes a latência que o usuário percebe no app.

O Navi, servidor de modelos escrito em Rust, é descrito como de alto desempenho, e sua variante para ONNX é usada na recomendação da home. O README do Navi diz que o código de teste e benchmark e vários arquivos de configuração não foram incluídos, por segurança de dados.