LLMs

Bruno recentemente começou a se interessar por grandes modelos de linguagem (os chamados LLMs, sigla do termo em inglês large language models). Uma das primeiras coisas que ele aprendeu foi que um dos componentes mais fundamentais das LLMs é o sistema de predição de tokens (que, por simplicidade, consideraremos como palavras).

A ideia deste tipo de sistema é relativamente simples de explicar: dada uma frase “incompleta”, o sistema deve sugerir a próxima palavra da frase. Tais sistemas se baseiam fortemente em álgebra linear e redes neurais, necessitam de grandes bases de dados de treinamento e possuem no mínimo milhões (muitas vezes bilhões ou até trilhões) de parâmetros, o que torna inviável, para um indivíduo, treinar seu próprio modelo.

Por conta dessas limitações (e também pelo fato de não precisar de um LLM em todo seu potencial), Bruno resolveu testar novas ideias, potencialmente mais baratas em termos computacionais, que precisem de menos dados de entrada e que até eliminem a fase de treinamento. Ele não espera obter algo tão bom quanto os modelos comerciais, mas acha que pode encontrar um modelo muito mais barato e suficientemente bom. Ele precisa de ajuda para testar o sistema de predição de palavras que acabou de conceber.

Seu sistema, batizado de Sistema Bruno de Chat (SBC), começa de forma similar aos LLMs tradicionais: ele recebe como entrada um mapeamento de um conjunto de palavras, chamado de dicionário, em um espaço euclidiano, que tende a codificar palavras similares em pontos próximos. Este dicionário vem ordenado da palavra mais comum para a menos comum, no conjunto de dados utilizado para construí-lo.

Por simplicidade, Bruno projetou este espaço em um plano e arredondou as coordenadas, de forma que cada palavra $p$ seja representada por um ponto (ou vetor) $v(p)$ com coordenadas inteiras em $\mathbb{R}^2$. Além deste mapeamento, Bruno utilizará um texto de entrada como sua “base de conhecimento”, ou seja, a fonte a partir da qual suas perguntas serão respondidas.

Para cada consulta, o sistema tentará prever a próxima palavra. O funcionamento é o seguinte:

1. É escolhido um inteiro $K$, que será o tamanho da janela de contexto.
2. Para as $K$ últimas palavras da consulta, buscamos, na base de conhecimento, onde essas palavras ocorrem exatamente na mesma ordem e de forma consecutiva.
3. Em cada ocorrência, registramos a palavra $c$ que ocorre na base de conhecimento logo após essas $K$ palavras.
4. Repetindo este processo por todo o texto, obtemos uma sequência $c_1, \dots, c_r$ de palavras, chamadas de candidatas.

Em seguida, para cada palavra $d$ do dicionário, calcula-se a similaridade de $d$ com as candidatas. Como as palavras estão associadas a vetores, o produto interno de dois vetores pode ser interpretado como uma medida de similaridade. Assim, para abuso de notação, identificamos cada palavra com seu vetor: $d \equiv v(d)$ e $c_i \equiv v(c_i)$.

O produto interno de dois vetores $v = (v_x, v_y)$ e $w = (w_x, w_y)$ é denotado por $v \cdot w$ e definido como

$$ v \cdot w = v_x w_x + v_y w_y. $$

A similaridade de uma palavra $d$ do dicionário com as candidatas é dada por

$$ S(d) = \sum_{i=1}^{r} d \cdot c_i. $$

O SBC então escolhe a palavra com maior valor de $S(d)$ como a próxima palavra do texto. Em caso de empate, escolhe-se a palavra mais comum, ou seja, a que aparece primeiro no dicionário.

Caso não haja nenhuma palavra candidata, o valor de $K$ é diminuído em uma unidade e o processo é repetido. Se nem mesmo para $K = 1$ houver palavras candidatas, o processo é abortado.

Muito embora todo este processo faça sentido na intuição de Bruno, ele tem dificuldade para implementá-lo e precisa de sua ajuda.

A entrada contém três partes: a primeira descrevendo o dicionário, a segunda a base de conhecimento e a terceira as consultas.

A primeira linha contém um inteiro $N$ ($2 \le N \le 10^3$), o número de palavras do dicionário. As $N$ linhas seguintes contêm cada uma:

• uma palavra $P_i$ composta apenas por letras minúsculas (até 12 caracteres),
• seguida de dois inteiros $X_i$ e $Y_i$ ($-10^3 \le X_i, Y_i \le 10^3$), representando o vetor $(X_i, Y_i)$ associado à palavra $i$.

A linha seguinte contém um inteiro $M$ ($2 \le M \le 10^3$), o número de palavras na base de conhecimento. As próximas linhas contêm a base de conhecimento, com 8 palavras por linha (exceto possivelmente a última linha).

Em seguida, dois inteiros $Q$ ($1 \le Q \le 10$) e $K$ ($1 \le K \le 5$), indicando o número de consultas e o tamanho da janela de contexto. Cada uma das $Q$ linhas seguintes descreve uma consulta: começa com um inteiro $F$ ($K \le F \le 8$), seguido de $F$ palavras.

Para cada consulta, imprima uma linha contendo as palavras da consulta seguido da próxima palavra prevista pelo SBC, se existir, ou seguido de "*" (asterisco) caso contrário.