Methods, computing systems and computer program products implement embodiments of the present invention that include configuring a storage system to store multiple storage entities, and defining, in a memory, a lookup table including multiple entries, each of the entries referencing a unique storage entity. Upon receiving a storage entity to be stored on the storage system, a compressibility of the received storage entity is determined upon detecting that the received storage entity is not identical to any of the unique storage entities referenced by the lookup table, and an entry referencing the received storage entity is added to the lookup table upon meeting a duplication condition based on the determined compressibility.