Upper-bound approximations for dynamic pruning