A method includes dividing a group of analog memory cells into multiple subsets. The memory cells in the group are sensed simultaneously by performing a single sense operation, while applying to the subsets of the memory cells respective different sets of read thresholds, so as to produce respective readout results. An optimal set of the read thresholds is estimated by processing the multiple readout results obtained from the respective subsets using the different sets of the read thresholds.