One source of computational overhead in the URE is the unification between rule conclusions and targets when going backward, or rule premises and sources when going forward.
Often the same unification operation is carried over. Add to that, unification is stateless. Thus is a perfect candidate for memoization.