The ability to remember previously encountered situations and the ability to give a subjective judgment on the accuracy of a decision are two fundamental aspects of adaptive behavior. Memory allows an individual to decouple actions from momentary percepts, while confidence provides graded degrees of belief that enable choosing between competing alternatives. Humans possess the ability to know when to trust recalled memories (high confidence) and when to doubt them (low confidence). However, despite the evolutionary advantage of being able to assign appropriate levels of confidence to memory recall, the accuracy of such confidence reports have been questioned. In fact, previous studies have found positive, null or even negative correlations between confidence and recall accuracy. Here we present a framework that resolves the apparent paradox of negative correlations. We define a decision variable that assigns a distinct difficulty level for each memory recall decision. We show that within our framework the confidence reports in memory recall follow the signatures of a statistical definition of decision confidence. The apparent paradox can be explained as a difference between the objective and subjective category of the stimuli.