Protection against infection hinges on a close interplay between the innate immune system and the adaptive immune system. Depending on the type and context of a pathogen, the innate system instructs the adaptive immune system to induce an appropriate immune response. Here, we hypothesize that the adaptive immune system stores these instructions by changing from a naive to an appropriate memory phenotype. In a secondary immune reaction, memory lymphocytes adhere to their instructed phenotype. Because cross-reactions with unrelated Ags can be detrimental, such a qualitative form of memory requires a sufficient degree of specificity of the adaptive immune system. For example, lymphocytes instructed to clear a particular pathogen may cause autoimmunity when cross-reacting with ignored self molecules. Alternatively, memory cells may induce an immune response of the wrong mode when cross-reacting with subsequent pathogens. To maximize the likelihood of responding to a wide variety of pathogens, it is also required that the immune system be sufficiently cross-reactive. By means of a probabilistic model, we show that these conflicting requirements are met optimally by a highly specific memory lymphocyte repertoire. This explains why the lymphocyte system that was built on a preserved functional innate immune system has such a high degree of specificity. Our analysis suggests that 1) memory lymphocytes should be more specific than naive lymphocytes and 2) species with small lymphocyte repertoires should be more vulnerable to both infection and autoimmune diseases.