Embodiments of the present invention provide hints for page stealing by prioritizing pages based on the number of residences. Receiving a plurality of pages to be hinted to a hypervisor for page stealing. Determining at least two page types of the plurality of pages. Determining whether any of the at least two page types has a total number of residences less than a total number of potential residences in the virtual environment for all page types and have a total number of residences less than a threshold. Responsive to determining a first page type of the at least two page types has a total number of residences less than a total number of potential residences for all page types and has a total number of residences less than a threshold, notifying the hypervisor of at least one page from the plurality of pages that is the determined first page type.