Certified Twenty Questions: Separating Agent Failure from Task Infeasibility Across Five Domains

When a language agent fails an interactive task, it is usually impossible to tell whether the agent chose badly or the task was unwinnable. We remove that ambiguity by construction. Cert20Q is a benchmark of 412 finite identification environments across five domains (molecules, fragrances, animal species, software defects, and countries) in which exact search proves, before any agent is run, that one target-blind policy identifies all 16 candidates within four questions. An environment that cannot be certified is never released, so no failure can be blamed on the absence of a legal four-question solution. The certificates make a sharp comparison possible. Over all 6,592 episodes a model-free greedy information-gain policy averages 98.5% across domains (97.8% weighting every episode equally) and uniform-random collapses to 14–27%, which brackets the task. Evaluating two language models on 500 episodes each separates them sharply against it. Replaying greedy on the very episodes each agent played, a smaller model falls 19.6 points short of it (95% CI [-25.2, -14.3], pool-clustered) while a frontier model is indistinguishable from it (-2.0 [-4.6, +0.4]) and, given split counts, reaches 100% on every episode, which is +1.2 above greedy but cannot exclude equality with it. Those counts carry no information the agent lacked; they aggregate the table already in its prompt. Supplying them is nonetheless worth +8.4 points to the smaller model (95% CI [+1.9, +15.3]) and only +3.2 to the larger, counting every episode attempted. That closes about a third of the distance between the two; what the remainder consists of, this design does not say. Because every pool carries a proof of solvability before it ships, none of the gap can be charged to an environment that could not be won.