Cessation of flow in yield stress fluids results in a complex stress relaxation which depends on the previous flow, and leads to residual stresses which display a direct dependence on the viscous stress generated during the flow. We have combined experiments and large scale computer simulations of a model jammed suspension of soft repulsive particles, to investigate the microscopic origin of these phenomena, relevant to a broad range of technologies. Using a spatio-temporal analysis of the microscopic particle motion and of the particle packing we identify a first fast relaxation due to the elastic stresses accumulated, during the flow, in large domains of particles, whose size is set by the shear rate. A much slower relaxation process is then due to the underlying reorganization of the particle packing across these domains, and its evolution is set by the constraints initially imposed by the shear flow: the viscous stress determines the morphology of the particle packing that optimizes the energy dissipation during flow, and ends up setting the residual stresses reached upon shear cessation. These findings highlight that flow in yield stress fluids can be seen as a training process during which the material stores the information of the shear rate and of the viscous stress, through the development of correlated domains of microscopic motion and particle packing optimized to sustain the flow. This encoded memory can be read out during shear cessation.