Sequential Permutation-Based Evidence Certification for Adaptive Stopping in Long-Horizon Search Agents

Long-horizon search agents must decide when to stop searching and answer. Stopping too early risks weakly supported answers, while searching after sufficient evidence has been collected wastes computation. Candidate answers evolve during search, and repeated webpages can inflate apparent support without adding new evidence. We introduce Sequential Permutation-based Evidence Certification (SPEC), a training-free controller for frozen search agents. It updates candidate rankings online using the current search context and separately accumulates certification evidence from new sources encountered after each candidate is proposed. It groups repeated pages into source clusters, counting each cluster only once for certification. For candidate comparisons fixed before new evidence arrives, SPEC measures whether each new source provides stronger support than matched retrieval results used as controls. It accumulates this relative support through permutation e-processes, with individual error budgets assigned to dynamically introduced candidates. Certified stopping requires the leading candidate to pass its certification threshold and have a sufficient log-likelihood margin over alternatives. Near the stopping threshold, SPEC checks how much this margin drops when individual sources are removed from a small evidence bundle and raises the required margin when support is concentrated in one source. Under conditional exchangeability of observed and control sources, SPEC bounds the probability of false evidence certification across search steps and dynamically introduced candidates. Experiments on fixed-corpus and open-web search show that SPEC reduces search calls and total cost while maintaining accuracy.