Techniques for checking the compressibility of a memory page that is allocated to a virtual machine (VM) running on a host system are provided. In one embodiment, the host system can determine a compression ratio for the memory page by compressing the memory page using a first compression algorithm. The host system can then compare the compression ratio to a threshold. If the compression ratio does not exceed the threshold, the host system can predict that the memory page is compressible by a second compression algorithm that is distinct from the first compression algorithm. On average, the second compression algorithm can be slower, but achieve a lower compression ratio, than the first compression algorithm.