Search Pathology Diagnosis for Automated Discovery

Automated Discovery Systems (ADSes) search for solution artifacts that optimize a task-specific metric. They are usually compared on the score of their best artifact. However, such a comparison reveals little about pathologies in the search. Analyzing the search trace in addition to the score can motivate targeted improvements to the system, and retrospectively explain if changes helped. We therefore introduce the provenance hypergraph, a system-agnostic abstraction for ADS search traces. A node is a generated solution, and a directed hyperedge points from a set of prior solutions to the new solution they could have influenced. On this hypergraph, we define detectors for two search pathologies: redundant rediscovery (RR), an exploration failure, and poorly grounded next steps (PGNS), an exploitation failure. Both detectors report where and how frequently the pathologies occur. We release five meta-evaluation datasets that enable the grading of detector implementations, and nanodiscover, an open-source re-implementation of TTT-Discover. Finally, we apply our detectors to nanodiscover on the Erdős minimum overlap problem, use the readings to design a memory intervention that helped, and diagnose one that did not.