Missing Token

The problem in brief

An alien transmission uses an alphabet of 30 symbols (holk, zyr, plorg...), and each message is 7 to 20 symbols long. In every damaged message exactly one symbol has been removed. You know which symbol is missing but not where it was. From 1 500 training messages, given with the true position, you must predict the position of the missing symbol in 500 test messages. It is a Kaggle simulation from the first training camp (Pelatnas 1) of Indonesia's IOAI 2026 team selection. The statement hints that a hidden "grammar" orders the symbols.

How you are scored

The metric is the mean absolute error between predicted and true positions:

$$\text{MAE} = \frac{1}{n}\sum_{i=1}^{n} \left|\hat k_i - k_i\right| .$$

The notebook's baseline predicts the middle of the message. The Kaggle leaderboard needs a login, so neither the test labels nor the leaderboard scores are available to us. We evaluate by 5-fold cross-validation on the training set.

First look at the data

Rebuild the complete training messages by inserting the missing symbol at its labelled position, then ask: where does each symbol tend to appear? The answer is striking.

• Each symbol has a typical place: holk is almost always first, sark second, ..., orp and groxx last. Sorting the symbols by their mean relative position gives a single hidden total order of the alphabet.
• A message is a subset of the alphabet written roughly in that order. No symbol repeats inside a message.
• The order is not perfect. Only 17 % of messages are perfectly sorted, about 13 % of adjacent pairs are swapped, and the violations are local: two thirds of the swapped pairs are within 2 places of each other in the hidden order, and 80 % of messages have no inversion between non-adjacent positions. The right panel shows this: certainty far from the diagonal, uncertainty only next to it.

So the "grammar" is simply sort the symbols, then add a little local noise.

A first baseline

approach	CV MAE	exact position
middle of the message (official baseline)	3.365	8.1 %
relative position of the symbol x message length	0.868	36.7 %

Even the crude second rule, "symbol m usually sits at a fraction $r_m$ of the message, so predict $r_m \cdot L$", divides the error by four. But it ignores the information that matters most: which symbols are actually present in this message.

The key idea

Use the other tokens of the message as landmarks. If the hidden order were exact, the missing symbol would go right after every present symbol that precedes it in the order, so its position would be

$$\hat k = \#\{\, t \in \text{message} : \text{rank}(t) < \text{rank}(m) \,\} .$$

This alone gives CV MAE 0.274, with the exact position in 74 % of cases.

To handle the noise in a principled way, treat it as a probabilistic model. From the training messages estimate, for every pair of symbols, $P(a \prec b)$, the probability that $a$ appears before $b$ (pair counts with add-one smoothing). Inserting $m$ at slot $k$ claims that $m$ comes after the $k$ tokens on its left and before the others, so under a pairwise-independence approximation

$$\log p(k) = \sum_{j < k} \log P(s_j \prec m) + \sum_{j \ge k} \log P(m \prec s_j) + \text{const} .$$

Normalising gives a posterior over the $L+1$ slots. For an absolute-error metric the best point prediction is the median of this posterior, not its mode (the mean would minimise squared error instead). In practice the posterior is sharply peaked, so the median, the mode and the counting rule almost always agree.

Why can we not do much better? When two neighbouring symbols are swapped in the original message, there is no evidence in the message for which of the two slots next to them the missing symbol occupied. Of the counting rule's errors, 96 % are off by exactly one position. They are the unavoidable cost of the local noise.

The full solution

1. Rebuild the complete training messages by inserting missing_unit at label.
2. Count, over all pairs of positions in every message, how often each symbol precedes each other, and turn the counts into smoothed probabilities $P(a \prec b)$.
3. For each damaged message, compute the slot log-likelihoods above, normalise them and take the median slot.

def posterior(s, m, P):
    ll = np.array([sum(np.log(P(t, m)) for t in s[:k]) + sum(np.log(P(m, t)) for t in s[k:])
                   for k in range(len(s) + 1)])
    p = np.exp(ll - ll.max()); return p / p.sum()

predict = lambda s, m, P: int(np.searchsorted(np.cumsum(posterior(s, m, P)), 0.5))   # median

The whole model is a $30 \times 30$ table of counts, which fits in seconds and is fully interpretable.

Results

5-fold cross-validation on the 1 500 training messages (the official test labels are private):

approach	CV MAE	exact position
middle of the message (baseline)	3.365	8.1 %
relative position x length	0.868	36.7 %
count present tokens ranked before $m$	0.274	73.8 %
pairwise-order posterior, argmax	0.274	74.5 %
pairwise-order posterior, median (final)	0.274	74.5 %
Mallows-style posterior (penalty per inversion, $\theta = 1.5$)	0.271	74.3 %

The Mallows variant, which scores each slot by $e^{-\theta \cdot \#\text{inversions}}$, is the same idea with a single noise parameter. Its gain of 0.003 is within cross-validation noise, so we keep the parameter-free pairwise model. We started a learned re-ranker (gradient boosting on slot features such as neighbour ranks and pairwise log-probabilities) but did not pursue it: with 96 % of the remaining errors being off-by-one ambiguities created by the noise itself, there is little left for a heavier model to find.

What to remember

• Rebuild the clean objects and look for structure first. Box plots of positions revealed a hidden total order in minutes; no sequence model was needed.
• Use the context as landmarks. The other tokens of the message pin the missing one down far better than its average position does.
• Turn a heuristic into a probabilistic model (pairwise order probabilities, posterior over slots). It handles noise gracefully and makes the uncertainty explicit.
• Pick the point estimate that matches the metric: the median for MAE, the mean for MSE, the mode for exact-match accuracy.
• Analyse residual errors before adding complexity: when every remaining error is an irreducible off-by-one, stop.