The way animals respond to a stimulus depends largely on an internal comparison between the current sensation and the memory of previous stimuli and outcomes. We know little about the accuracy with which the physical properties of the stimuli influence this type of memory-based discriminative decisions. Research has focused largely on discriminations between stimuli presented in quick succession, where animals can make relative inferences (same or different; higher or lower) from trial to trial. In the current study we used a memory-based task to explore how the stimulus' physical properties, in this case tone frequency, affect auditory discrimination and generalization in mice. Mice performed ad libitum while living in groups in their home quarters. We found that the frequency distance between safe and conditioned sounds had a constraining effect on discrimination. As the safe-to-conditioned distance decreased across groups, performance deteriorated rapidly, even for frequency differences significantly larger than reported discrimination thresholds. Generalization width was influenced both by the physical distance and the previous experience of the mice, and was not accompanied by a decrease in sensory acuity. In conclusion, memory-based discriminations along a single stimulus dimension are inherently hard, reflecting a high overlap between the memory traces of the relevant stimuli. Memory-based discriminations rely therefore on wide sensory filters.