When Is Enough Not Enough? Illusory Completion in Search Agents

Recent search agents interleave multi-turn reasoning with tool calls to achieve strong performance on multi-hop and long-horizon benchmarks. Yet it remains unclear whether they reliably reason and verify across all of a question's requirements. We study this in the multi-constraint setting, where a valid answer must satisfy several constraints simultaneously. Here, agents frequently exhibit illusory completion: they believe a task is complete despite unresolved or violated constraints, producing underverified answers. To diagnose this behavior, we introduce the Epistemic Ledger, an evaluation framework that tracks evidence retrieved and the agent's stated belief for each constraint across turns. This reveals four recurring failure patterns: bare assertions, overlooked refutations, stagnation, and premature exit. Building on this diagnosis, we propose LiveLedger, a lightweight 4B-parameter tracker that surfaces constraint states to the agent at inference time. It improves the accuracy of a 30B-trained policy by 12.7%p and of a 120B-prompted agent by 13%p, while reducing underverified answers by 6.5%p and 11.1%p, respectively.