LLM program-search agents are usually judged by the score that drives their search, according to a new arXiv preprint. The authors study LLM-driven search over Python exercise policies for Bermudan options, an optimal stopping problem. They propose auditing the search results using primal-dual certificates rather than relying on the search score alone.
Primal-dual certificates offer a way to verify the quality of a proposed policy independently of the optimization objective. In the Bermudan option setting, this means a trusted evaluator can check whether the exercise policy is genuinely near-optimal. The abstract suggests this approach provides a more robust evaluation of LLM program search.