From theory to practice: S*-guided search solves planted motif identification on intractable instances

The Bayes-optimal scoring function S* for the planted (l, d)-motif identification problem was recently derived and shown to achieve 92.8% accuracy on exact-enumerated (13, 4) instances (Wijaya, 2026). That work left an open problem: on intractable instances where exact enumeration is infeasible, the heuristic search pipeline does not benefit from S*. We diagnose the bottleneck as a refinement trap and replace the post-EM refinement stack with motif-space hill climbing under S*. The resulting pipeline solves (15, 5) at 10 of 10, matches the exact-enumeration ceiling on (13, 4) at 19 of 20 in heuristic mode, and achieves 140 of 140 on the standard benchmark with zero regressions.