We have performed oscillatory shear experiments on a bidisperse granular mixture in combination with refractive index matched scanning in order to resolve particle motion in three-dimensions during size-segregation. We find that small particles segregate faster in regions where the large particle concentration is high and large particles segregate slower in regions where the small particle concentration high. This dependency of particle segregation speed on local relative volume fraction results from a fundamental asymmetry in the underlying dynamics of the two species. We observe that this asymmetry affects the segregation behavior of the mixture at both the bulk and particle scale. For example, mixtures containing relatively more small particles take longer to segregate; and during segregation small particles are quicker to reach the bottom of the flow compared to larges particles reaching the top. The predictions of a theoretical model incorporating this asymmetric dependence on volume fraction show a significant improvement compared to the standard model with a symmetric dependence. Besides having repercussions for the understanding of size segregation on a fundamental level, this discovery expands the connections to processes such as traffic flow, sedimentation and particle diffusion, which exhibit similar asymmetric behavior.