LLMs

Bruno recently became interested in large language models (the so-called LLMs, acronym for large language models). One of the first things he learned was that one of the most fundamental components of LLMs is the token prediction system (which, for simplicity, we will consider as words). The idea of this type of system is relatively simple to explain: given an “incomplete” sentence, the system must suggest the next word of the sentence. Such systems rely heavily on linear algebra and neural networks, require large training databases and have at least millions (often billions or even trillions) of parameters, which makes it unfeasible for an individual to train their own model.

Due to these limitations (and also because he doesn’t need an LLM at its full potential), Bruno decided to test new ideas, potentially computationally cheaper, that need less input data and even eliminate the training phase. He doesn’t expect to get something as good as commercial models, but thinks he can find a much cheaper and sufficiently good model. He needs help to test the word prediction system he just conceived.

His system, named System for Bruno’s Chat, or, simply, SBC, starts similarly to traditional LLMs: it receives as input a mapping of a set of words, called a “dictionary”, into a Euclidean space, which somehow tends to encode similar words at nearby points. This dictionary comes ordered from the most common to the least common word, in the dataset used to build it. For simplicity, Bruno made a projection of this space onto a plane and rounded the coordinates, so that each word $p$ is represented by a point (or vector) $v(p)$ with integer coordinates in $\mathbb{R}^2$. In addition to this mapping, Bruno will use an input text as his “knowledge base”, that is, the source from which his questions will be answered.

For each query, he will try to predict the next word. To do this, he will look at the last words of the query and, using the mapping and the text, make a prediction of which word should be used.

Bruno’s system works as follows. Initially, an integer $K$ is chosen, which will be the size of the “context window”. For the last $K$ words of the query, we will search, in the knowledge base, where these words occur in the text, exactly in the same order and consecutively. In each occurrence, we record the word c that occurs in the knowledge base right after the last $K$ words. After repeating this process throughout the text, we obtain a sequence $c\_1, \dots , c\_r$ of words, which we will call “candidates”.

Next, for each word d in the dictionary, the similarity of $d$ with the candidates is calculated. Since words are associated with vectors, and the inner product of two vectors can be interpreted as a measure of similarity between them, Bruno decided to use it as a similarity metric. By abuse of notation, we identify each word with its vector: $d ≡ v(d)$ and $c\_i ≡ v(c\_i)$. If a candidate word $c\_i$ is not present in the dictionary, it is represented by the vector $(0, 0)$. The inner product of two vectors $v = (v\_x, v\_y)$ and $w = (w\_x, w\_y)$ is denoted by $v \cdot w$ and is defined as $v \cdot w = v\_xw\_x + v\_yw\_y$. The similarity of a word $d$ in the dictionary with the candidates is given by $S(d) = \displaystyle\sum\_{i=1}^r{d \cdot c\_i}\text{.}$

SBC then chooses the word with the highest value of $S(d)$ and this will be the next word in the text. In case of a tie, SBC will choose the most common word, that is, the one that appears first in the dictionary. If there are no candidate words, the value of $K$ is decreased by one unit and the process is done again. If even for $K = 1$ no candidate words are found, the process is aborted.

Although in Bruno’s intuition this whole process makes sense, he has great difficulty implementing it and needs your help.

The input contains $3$ parts: the first describing the dictionary, the second describing the knowledge base and the third containing the queries.

The first line of input contains an integer $N$ ($2 ≤ N ≤ 10^3$), indicating the number of words in the dictionary. The $i$-th of the following $N$ lines will contain a word $P\_i$ composed only of lowercase letters of the alphabet, with at most $12$ characters, followed by two integers $X\_i$ and $Y\_i$ ($−10^3 ≤ X\_i , Y\_i ≤ 10^3$), which indicate the vector $(X\_i , Y\_i)$ associated with the $i$-th word in the dictionary.

The next line contains an integer $M$ ($2 ≤ M ≤ 10^3$), the number of words in the text corresponding to the knowledge base. The following lines will contain the knowledge base, with $8$ words per line, separated by spaces (except possibly the last line).

Then, two integers $Q$ ($1 ≤ Q ≤ 10$) and $K$ ($1 ≤ K ≤ 5$), indicating the number of queries and the size of the context window. Each of the following lines will describe a query. Each query will contain an integer $F$ ($K ≤ F ≤ 8$), followed by $F$ words.

For each query, a line should be printed containing the words of the query followed by the next word predicted by SBC, if it exists, or followed by “*” (asterisk), otherwise.