A method for data storage includes, in a first programming phase, storing first data in a group of memory cells by programming the memory cells in the group to a set of initial programming levels. In a subsequent second programming phase, second data is stored in the group by identifying the memory cells in the group that were programmed in the first programming phase to respective levels in a predefined partial subset of the initial programming levels, and programming only the identified memory cells with the second data, so as to set at least some of the identified memory cells to one or more additional programming levels that are different from the initial programming levels. The memory cells to which the second data was programmed are recognized by reading only a partial subset of the first data. The second data is read from the recognized memory cells.