research · the task and the optimal agent

post-training llms to write long reasoning traces before answering lifts them to near-human accuracy on hard benchmarks. it is much less clear why extended reasoning helps, and how the traces relate to the computation that actually produces the answer.

we take a page from cognitive science: a task simple enough to model at the algorithmic level, yet demanding enough that frontier models do not trivially solve it. it separates the two halves of a decision under uncertainty: sampling (actively choosing which evidence to collect) and inference (integrating that evidence into a decision).

the task

it's the game on this site. each game has four buttons, A–D:

one button is secretly biased: it shows red 90% of the time. the other three are fair coins (50% red).
for $T \in \{2,\dots,15\}$ sampling rounds you click one button and see its color. between 0 and 3 buttons are occluded on each round.
in a final inference round you name the biased button. only this choice counts: sampling earns nothing by itself.

because sampling carries no reward, we can score how well an agent gathers evidence separately from how well it uses it. humans played the graphical version here (50 people at a live competition; 46 finished all 100 games, 4,600 games in total). llms played an equivalent text version with the same instructions, at least 1,400 games per model and condition.

the optimal agent

inference is easy to make optimal: keep the bayesian posterior over which button is biased and pick its maximum (map). sampling is harder, because you choose what evidence to acquire under random occlusions. solving the problem exactly with dynamic programming shows that, for this task, map is optimal for sampling too: sample the available button you currently believe is most likely biased. that agent wins 67.8% of games, the ceiling we compare everyone against.

$$\mathbf{p}_t = \frac{\mathbf{p}_{t-1} \odot \mathbf{L}_t}{\mathbf{1}^{\top} (\mathbf{p}_{t-1} \odot \mathbf{L}_t)}, \qquad (\mathbf{p}_0)_k = \tfrac{1}{4}$$

bayes: the belief that each button is the biased one, updated with the likelihood $\mathbf{L}_t$ of each new color

$$a_t^{\mathrm{MAP}} = \arg\max_{k \in \{1,\dots,4\}} \, (\mathbf{p}_t)_k$$

map: the final choice, and for this task also the optimal sampling choice among available buttons

this gives a clean decomposition of every agent's shortfall. sampling loss is how much worse map inference does on your samples than the optimal agent. inference loss is how much worse your actual choice does than map inference on those same samples.

$$\underbrace{S^{\star} - S}_{\text{total loss}} \;=\; \underbrace{S^{\star} - S^{\mathrm{MAP}}}_{\text{sampling loss}} \;+\; \underbrace{S^{\mathrm{MAP}} - S}_{\text{inference loss}}$$

$S$: success rate, $S^{\star} = 67.8\%$: optimal agent, $S^{\mathrm{MAP}}$: map inference on the agent's own samples

01the task and the optimal agent

the task

the optimal agent