Potato

The problem in brief

A judge secretly picks one word out of a fixed list of 1602 English words. You never see a score or a distance: each turn the judge only tells you which of two words is semantically closer to the secret. The game always opens with lamp against potato; after that, you propose one word per turn, and it is compared with the current "champion" (the word that won the previous comparison). You win the moment you propose the secret itself, and you have 30 proposals. The catch: the judge measures closeness with its own private embedding model, while you only get a different, public set of embeddings (and two small embedding models you may run offline). Your program plays 120 games in a row, all within 10 minutes.

How you are scored

A game won on turn $t$ is worth

$$\text{game}(t) = 1 - 0.02\,\max(0,\ t-10), \qquad \text{game}(\text{lost}) = 0,$$

so turns 1 to 10 are worth full marks, turn 20 is worth 0.8, turn 30 is worth 0.6. The task score is $100 \times$ the mean over the 120 games. Leaderboard A was shown live during the contest; leaderboard B (120 other words) decided the final ranking.

What is a good score? From the official results table (ioai-official.org, "Results 2026"), Potato was brutal: about two thirds of the contestants scored 0, only about 20 of the roughly 380 listed scored above 50, and the best score was 85.5 (Artem Gorokhov, the overall winner). The 99th percentile was about 75. That 85.5 is the target we compare against.

First look at the data

How many questions do we need? Finding one word among 1602 needs $\log_2 1602 \approx 10.6$ bits. Each verdict is a single bit at best, so even a perfect strategy needs about 11 turns, and full marks (turn $\le 10$) is out of reach for most secrets. Realistic goal: find most secrets between turn 10 and 20.

The bits are noisy. The judge's embedding space is not ours. After the contest the organisers published the private embeddings (4096 dimensions) on Hugging Face, so we can measure what contestants could only guess: for a random triple (secret, word $a$, word $b$), the public embeddings predict the judge's verdict correctly only 81 % of the time. During the contest you could estimate this with what you had: the public embeddings and the provided Qwen3-Embedding-0.6B agree on only 73 % of triples, a clear warning that "the judge thinks like my embeddings" is false.

The left panel teaches two things. When our embeddings predict a large margin, the judge almost always agrees; when the margin is small, the verdict is close to a coin flip. And the curve is matched almost perfectly by a simple model, $\Phi\big(\Delta / (\sigma\sqrt 2)\big)$ with $\sigma = 0.5$ (similarities measured in z-units, see below). That $\sqrt 2$ is the hint for the key idea.

The test words are not like the public words. test_public.json contains concrete nouns (shovel, elephant, banana...) taken from the end of the vocabulary. The hidden leaderboards contain words from everywhere, including abstract ones (criticism, series, let, intention). There is no training split. So: assume a uniform prior over all 1602 words, and do not tune anything on test_public alone (our final solution scores 83.7 there but 70.85 on the final leaderboard).

A first baseline

The official baseline proposes, each turn, the unused word most similar (in public embeddings) to the current champion. It climbs towards the secret like a hill climber and wastes most of its turns on near-synonyms of the champion.

baseline, judged by...	test_public	leaderboard A	leaderboard B
public embeddings (what local_test.py does)	36.0	28.9	32.2
the real private judge	28.2	15.0	17.1

Note the first row: the local tester shipped with the task uses the public embeddings as the judge, so it is systematically optimistic. This becomes dramatic for smarter strategies (see below).

Second attempt: Bayesian elimination. A much better plan is to keep a probability $p(c)$ for every candidate secret $c$ and update it after each verdict. If $Z_{cj}$ is our similarity between $c$ and word $j$, the natural model of a noisy verdict "$a$ beat $b$" is a logistic (or probit) function of the predicted margin:

$$P(a \text{ beats } b \mid c) = \Phi\!\left(\frac{Z_{ca} - Z_{cb}}{\sigma\sqrt2}\right), \qquad p(c) \leftarrow p(c)\, P(\text{verdict} \mid c).$$

The next word is chosen to maximise the expected information of its verdict (details below). With the public embeddings as judge this scores about 97: it almost always wins in about 10 turns. Against the real judge it falls to 55 to 64. Tuning the noise level helps a little; nothing closes the gap. Something in the model is wrong.

The key idea

Look at which comparisons a game actually produces. The champion stays in place until it is beaten, so the same word appears in many comparisons: champion $a$ against $x_1$, then $a$ against $x_2$, then $a$ against $x_3$... Now suppose the judge happens to find $a$ much closer to the secret than our embeddings do (the right panel of the figure shows such word-level errors are real and large). Then $a$ wins all those comparisons, and each one looks surprising to the true candidate. The model above treats the verdicts as independent noisy bits, so it multiplies the surprise $k$ times, and after a few turns the true secret has a tiny probability and is never proposed again. The pairwise model is overconfident because the noise is not attached to comparisons, it is attached to words.

So model the noise where it lives (this is Thurstone's classical model of paired comparisons). Given a candidate secret $c$, let $y_j$ be the judge's (unknown) similarity between $c$ and word $j$:

$$y_j = Z_{cj} + \varepsilon_j,\qquad \varepsilon_j \sim \mathcal N(0, \sigma^2) \text{ independent per word.}$$

A verdict is no longer noisy: it is the exact statement $y_{\text{winner}} > y_{\text{loser}}$. The noise lives in the $y$'s, and a word that appears in five comparisons has one $\varepsilon$, not five. (Two independent words give a margin error of standard deviation $\sigma\sqrt2$: that is the $\sqrt2$ in the calibration curve.)

The likelihood of a candidate integrates the unknown $y$'s out. The structure of the game makes this easy. The constraints form a chain: champions $k_1, k_2, \dots, k_m$ with $y_{k_1} < y_{k_2} < \dots < y_{k_m}$, and each loser $\ell$ hangs below the champion it lost to. Integrating each loser out is a single factor $P(y_\ell < y_k) = \Phi\big((y_k - Z_{c\ell})/\sigma\big)$, and the champions are handled by a one-dimensional forward pass, exactly like a hidden Markov model on a grid of values $y$:

$$f_1(y) = \varphi\!\left(\tfrac{y - Z_{ck_1}}{\sigma}\right) \prod_{\ell \in L_1} \Phi\!\left(\tfrac{y - Z_{c\ell}}{\sigma}\right),\qquad f_{i+1}(y) = \varphi\!\left(\tfrac{y - Z_{ck_{i+1}}}{\sigma}\right) \prod_{\ell \in L_{i+1}} \Phi\!\left(\tfrac{y - Z_{c\ell}}{\sigma}\right) \int_{-\infty}^{y} f_i(u)\,du,$$

and $P(\text{all verdicts} \mid c) = \int f_m(y)\,dy$. On a grid of 130 values of $y$ the integral is a cumulative sum, and all 1602 candidates are processed at once with NumPy. As a bonus, $f_m$ normalised is the posterior distribution of the current champion's judge similarity $y_{k_m}$, with mean $\mu_c$ and variance $v_c$, which is exactly what we need to predict the next verdict.

The figure below shows the effect on real games. With per-comparison noise (dashed), the probability of the true secret can sink below $10^{-6}$ and the game is lost; with per-word noise (solid) it climbs steadily.

Choosing the next word. For a proposal $x$, the probability that it beats the champion if the secret is $c$ is

$$M_{cx} = \Phi\!\left(\frac{Z_{cx} - \mu_c}{\sqrt{\sigma^2 + v_c}}\right), \qquad q_x = \sum_c p(c)\, M_{cx}.$$

The expected information gained by proposing $x$ is the mutual information between the verdict and the secret,

$$I(x) = H(q_x) - \sum_c p(c)\, H(M_{cx}),\qquad H(t) = -t\log_2 t - (1-t)\log_2(1-t).$$

The first term rewards questions whose answer is uncertain (a 50/50 split); the second term penalises questions whose answer is noisy even if we knew the secret (tiny margins). Finally, a proposal may simply win: we pick

$$x^\star = \arg\max_x\ \big(1 - p(x)\big)\, I(x) + p(x),$$

which asks informative questions early and switches naturally to "guess the most likely word" once the posterior is concentrated. Every proposal that does not win also eliminates itself exactly ($p(x) = 0$ afterwards).

A better proxy for free. The judge's model is unknown, but averaging our similarity matrices averages out part of their errors. Standardise each cosine matrix to z-units (subtract the mean, divide by the standard deviation of the off-diagonal entries) so that they are comparable, then mix: $Z = 0.8\,Z_{\text{public}} + 0.2\,Z_{\text{Qwen3-0.6B}}$. This lifts the agreement with the judge from 81.1 % to 82.1 %, which sounds small but is worth 3 points on leaderboard A and 12 on leaderboard B with the word-level model, because a game chains many such comparisons. The other provided model, bge-m3, is a poor judge of single words (60 % agreement) and only hurts.

The full solution

1. Prepare (about 10 s). Load the public embeddings, embed the 1602 words with the local Qwen3-Embedding-0.6B (plain text, no instruction prompt), build both cosine matrices in z-units and mix them 0.8 / 0.2. Set the diagonal to a large value (a word is maximally similar to itself).
2. Each game. Keep the chain of champions and their losers, plus the set of words already proposed.
3. Each turn. Append the new verdict to the chain; run the forward pass for all candidates; zero out the candidates already proposed; compute $M$, $q$, $I(x)$ and propose $x^\star$.

The heart of the code is the forward pass over the chain:

for champ, losers in self.chain:
    lp = -0.5 * ((g - Z[:, champ][:, None]) / SIGMA) ** 2        # prior of y_champ, all candidates
    for l in losers:
        lp += log_ndtr((g - Z[:, l][:, None]) / SIGMA)           # each loser is below its champion
    if logf is not None:                                          # previous champion is below this one
        m = logf.max(1, keepdims=True)
        cum = np.cumsum(np.exp(logf - m), 1)
        lp += np.log(np.concatenate([np.zeros((N, 1)), cum[:, :-1]], 1) + 1e-300) + m
    logf = lp

Everything is in log space to avoid underflow. 120 games take about 400 s on two CPU threads of a laptop, inside the 10-minute budget; on the contest machine (more cores, plus a GPU for the matrix products) there is comfortable margin, and a cheap safety valve is to evaluate $M$ only for the 300 most probable candidates. The two hyperparameters ($\sigma = 0.5$ and the 0.2 mixing weight) were chosen on leaderboard A, the only hidden feedback contestants had, and the final number is reported on leaderboard B.

Results

All scores below are computed with an exact replica of the official judge (play_single_game in the official grader.py) using the private embeddings published after the contest. "A" was available to contestants as a live leaderboard; "B" is the official final test.

approach	leaderboard A	leaderboard B
official baseline: closest unused word to the champion	15.0	17.1
pairwise Bayes, public embeddings, judged by the public embeddings (the local tester's illusion)		97.0
pairwise Bayes, public embeddings, real judge, best noise level	55.9 to 58.8	54.5 to 57.9
pairwise Bayes + 0.8 / 0.2 ensemble	64.3	55.8
pairwise Bayes + ensemble + robust likelihood (3 % "lying judge" floor)	58.0	49.8
word-level (Thurstone chain) model, public embeddings only	69.8	58.6
word-level model + 0.8 / 0.2 ensemble, $\sigma = 0.5$ (final, solution.py)	72.80	70.85
same, $\sigma = 0.35$ / $\sigma = 0.65$	74.1 / 70.7	67.0 / 67.4
same, win bonus 0.5 / 2 instead of 1	71.4 / 73.3	68.9 / 69.6
same, ensemble weight 0.3 instead of 0.2	68.9	63.7
learning per-word offsets across games (unfinished, numerically unstable)

On test_public the final solution scores 83.7. On leaderboard B it finds 97 secrets out of 120 (median turn 15, 22 of them within the 10 free turns) against 25 for the baseline.

Honest verdict. 70.85 on the final leaderboard would have been one of the top six Potato scores of IOAI 2026, but it does not reach the best contestant's 85.5. Differences of 2 or 3 points between rows are within the noise of 120 games (one extra lost game costs 0.5 to 0.8 points, one game found 5 turns later costs about 0.1). The idea we did not finish is promising: once a game is won, the secret is known, so all its verdicts become labelled data about the judge. Since the judge's errors are largely a property of each word (right panel of the first figure), learning a per-word offset $b_j$ across the 120 games is legitimate within the rules (the program runs once for all games) and, with perfectly known offsets, would raise the agreement with the judge from 81 % to 88 %. Our first implementation of that update diverged and was not kept.

What to remember

• Model the noise where it is produced. Here the error belongs to each word's similarity, not to each comparison. Treating correlated observations as independent makes a Bayesian model overconfident, and an overconfident posterior throws away the right answer. Thurstone's model plus a forward pass on a grid fixed this and was worth more than any tuning.
• Your local judge lies to you. A tester that uses your own embeddings as the judge reports 97 for a strategy that scores 55 for real. Always build a harsher simulation (for example, let a different model play the judge) and measure how much two models agree before trusting any score.
• Ask the most informative question. Maximising the mutual information $H(q) - \mathbb E[H(M)]$ prefers questions that split the candidates evenly and whose answer is reliable; mixing in $p(x)$ turns questioning into guessing at the right moment.
• Ensembles are cheap robustness. Averaging two standardised similarity matrices cancels part of each model's idiosyncratic errors; standardise first, and check each member: a weak member (bge-m3 here) hurts.
• Know the size of the problem. $\log_2 1602 \approx 10.6$ bits told us from the start that full marks are impossible on most games and that the real battle is between turns 10 and 20.