Shuffled Documents

The problem in brief

Every document in the collection is an Indonesian text of exactly two paragraphs, on topics from Balinese cooking to video games. The first paragraphs are stored in one list and the second paragraphs in another, and the second list has been shuffled. You must write a function that, given both lists, returns for each first paragraph the index of the second paragraph that continues it. A labelled development set of 25 documents is provided; the real test set was only released in the last hour of the contest, without labels.

The statement announces 300 test documents; the published test set (afaji/wikipair-test) actually holds 100. The organisers have since published the answers (afaji/wikipair-test-answer), so we score on the official test set.

How you are scored

Accuracy of the returned list:

$$\text{acc} = \frac{1}{N}\sum_{i=1}^{N} \mathbf{1}\big[\text{answer}_i = \sigma(i)\big],$$

where $\sigma$ is the true pairing. Random guessing gets $1/N$, so 1 % on the test set. Points are relative to the best contestant, with a 0 % baseline:

$$\text{points} = 100 \cdot \frac{\text{acc}}{\text{acc}_{\text{best}}}.$$

The best contestant's accuracy is not published, so there is no fixed target.

First look at the data

Paragraphs are short (about 4 sentences, 470 to 530 characters) and well written. Two things stand out.

1. The second paragraph almost always names its subject again. "Proses pembuatan Bebek betutu dimulai...", "Perkembangan Kecerdasan Buatan bermula...". So the pairs share rare words, and that should make the task easy.
2. The setters planted look-alike topics. The test set contains pairs of documents on nearly the same subject: Lionel Messi and Neymar Jr (both footballers, both at Barcelona), Pemanasan Global (global warming) and Perubahan iklim (climate change), Briyani and Kebab (both spiced meat dishes). These pairs are where all the difficulty lives.

The dev set has none of these traps: every method we tried scores 100 % on dev, so dev cannot tell methods apart. Keep this in mind, it shapes how we choose the final model.

A first baseline

Represent each paragraph by its word TF-IDF vector, compute the cosine similarity of every (first, second) pair, and for each first paragraph pick the most similar second paragraph. On test, this gets 86 %, far above the 1 % of random guessing.

Look at the predictions, though: 12 of the 100 second paragraphs are chosen by two different first paragraphs, which is impossible, since every second paragraph belongs to exactly one document. The baseline throws away a piece of information that the statement gives us for free.

The key idea

The answer is a permutation, so decode it as one. Let $S_{ij}$ be the similarity between first paragraph $i$ and second paragraph $j$. Choosing a partner for each row independently ("greedy") maximises each $S_{i,\pi(i)}$ separately and allows collisions. What we really want is the pairing that is best as a whole:

$$\hat\pi = \arg\max_{\pi \in \text{permutations}} \sum_{i=1}^{N} S_{i,\pi(i)} .$$

This is the classic assignment problem. There are $N!$ permutations, but the Hungarian algorithm solves it exactly in $O(N^3)$ (scipy.optimize.linear_sum_assignment, a millisecond for $N=100$). Why does it help? When two first paragraphs both prefer the same second paragraph $j$, only one of them can have it. The other is forced to its second choice, which is very often its true partner: the collision was caused by a strong confuser, not by a missing partner. One-to-one decoding turns "two near-ties" into "one swap at worst". It adds 6 to 10 points to every scorer we tried.

The second ingredient is the similarity itself, and here the trap topics matter. A bag of words sees that the Messi paragraph and the Neymar paragraph share "Barcelona", "teknik", "visi permainan". A multilingual sentence encoder (we use multilingual-e5-small) maps each paragraph to a vector that represents its meaning, so paraphrases of the same idea land close together even with different words.

Choosing between scorers without labels. The dev set is saturated, and tuning on the test answers would be cheating. But the test texts were available, and we can build a labelled task from them for free: cut every paragraph into its first and second halves (by sentences), and ask each scorer to re-match the halves among the 100 first paragraphs, then among the 100 second paragraphs. The answer to this proxy task is known by construction, and it contains the same look-alike topics. On it, TF-IDF scorers re-match only 53 to 57 % of the halves and e5 re-matches 95 %. So our submission is e5 similarities + Hungarian assignment, chosen before looking at the test answers.

The left panel shows why the task is solvable: the diagonal stands out clearly against an almost uniform background, except for a few bright off-diagonal cells, which are exactly the look-alike pairs.

The full solution

def predict_pair(first_list, second_list):
    E1 = model.encode(["query: " + x for x in first_list], normalize_embeddings=True)
    E2 = model.encode(["query: " + x for x in second_list], normalize_embeddings=True)
    S = E1 @ E2.T                                   # cosine similarities, N x N
    rows, cols = linear_sum_assignment(-S)           # best permutation (maximise total S)
    return cols.tolist()

1. Encode all paragraphs with the same encoder (e5 expects a "query: " prefix for symmetric similarity tasks) and L2-normalise, so the dot product is the cosine similarity.
2. Build the $N\times N$ similarity matrix.
3. Solve the assignment problem on $-S$ (scipy minimises a cost).

It runs in a few seconds on a laptop CPU for 100 documents (plus a one-off 470 MB model download).

Results

Official test set, 100 documents. "Proxy" is the label-free half-paragraph task built from the test texts, the only signal used to choose the scorer.

scorer	dev	proxy (no labels)	test, greedy	test, one-to-one
random	4 %		1 %
word TF-IDF (sublinear tf)	100 %	53 %	86 %	94 %
char 3-5-gram TF-IDF	100 %	54 %	82 %	92 %
word TF-IDF (raw tf)	100 %	57 %	91 %	98 %
e5-small embeddings (submitted)	100 %	95 %	93 %	96 %

Our submission scores 96 %. Its 4 errors are two swapped pairs: Messi with Neymar, and global warming with climate change. Since the assignment is a permutation, errors always come in such cycles.

An honest twist: plain word TF-IDF with raw term frequency reaches 98 %, but the proxy task would not have picked it. Looking at the errors afterwards, the reason is clear. Second paragraphs repeat their subject's name several times ("Neymar" appears 4 times in his second paragraph), and raw term frequency rewards that repetition while the sublinear version $1 + \log \text{tf}$ dampens it. The proxy task cannot see this effect, because a half paragraph rarely repeats a name. That is the limit of a proxy: it is only as good as its resemblance to the real task. Neither method separates Pemanasan Global from Perubahan iklim: the two topics are close to synonyms, and each paragraph mentions its own label only once.

What to remember

• Use the structure of the output. When the answer is a matching, a ranking or a partition, decode it with the right combinatorial solver (Hungarian algorithm, sorting, flows) instead of independent argmaxes. It is free accuracy.
• Sentence embeddings beat word overlap when the confusers share vocabulary; TF-IDF remains a strong, fast baseline when documents repeat rare names.
• When the validation set is saturated or missing, build a proxy task from unlabelled data (split, mask or shuffle the texts you have): it lets you choose a method without touching the test labels.
• Check that your proxy looks like the real task: ours rewarded meaning but could not see name repetition, and missed a slightly better scorer.
• Errors in a permutation come in cycles: one confusion always costs at least two answers.