Calling beam search 'AI' is doing a lot of heavy lifting here. This is just superoptimization with a very expensive heuristic function.
The expense calculation might be
expense of improvement = (time taken per optimization step * cost of unit time ) / ( speedup - 1)
The expensive heuristic function is saving wall time well also being cheaper in cost of unit time. And as the paper shows the speed up provided for each unit time multiplied by unit cost of time is large.