In soft amorphous materials, shear cessation after large shear deformation leads to structures having residual shear stress. The origin of these states and the distribution of the local shear stresses within the material is not well understood, despite its importance for the change in material properties and consequent applications. In this work, we use molecular dynamics simulations of a model dense non-Brownian soft amorphous material to probe the non-trivial relaxation process towards a residual stress state. We find that, similar to thermal glasses, an increase in shear rate prior to the shear cessation leads to lower residual stress states. We rationalise our findings using a mesoscopic elasto-plastic description that explicitly includes a long range elastic response to local shear transformations. We find that after flow cessation the initial stress relaxation indeed depends on the pre-sheared stress state, but the final residual stress is majorly determined by newly activated plastic events occurring during the relaxation process. Our simplified coarse grained description not only allows to capture the phenomenology of residual stress states but also to rationalise the altered material properties that are probed using small and large deformation protocols applied to the relaxed material.