Extensive cognitive research has been devoted to the sensitivity of the visual system to invariant statistical information. For example, many studies have shown that performance improves when a visual display is presented repeatedly. But what allows humans to connect the current visual input to previous memory? Is the connection made only when the entire incoming display matches with a previous memory, or can retrieval rely on an incomplete match between the input and a learned display? Using a visual search task, we show that (1) once a repeated display is learned, subjects can retrieve it even when an incoming display only matches it in 3-4 locations; (2) however, early during learning, repetition of a small proportion of a display is not enough to establish a strong memory trace for the repeated locations. We suggest that the retrieval of a well-established visual memory can proceed even if an incoming display partly matches the previous memory.