Submodular Tree Search

The paper formulates tree informativeness as a weighted combination of Coverage, Novelty, and Contrast. The paper states that the components of F are monotone submodular and that greedy expansion has a classical approximation guarantee. A validation study found diminishing returns consistent with submodularity for UUCB marginal gain. UUCB combines backed-up value, exploration, entropy contrast, cost penalty, and depth penalty. Entropy for UUCB excludes copied tool-output spans and only considers tokens that produce the next tool call or final answer.