Cube Pruning is a fast method to explore the search space of a beam decoder. In this paper we present two modifications of the algorithm that aim to improve the speed and reduce the amount of memory needed at execution time. We show that, in applications where Cube Pruning is applied to a monotonic search space, the proposed algorithms retrieve the same K-best set with lower complexity. When tested on an application where the search space is approximately monotonic (Machine Translation with Language Model features), we show that the proposed algorithms obtain reductions in execution time with no change in performance.