In magnesium alloys with multiple substitutional elements, solute segregation at grain boundaries (GBs) has a strong impact on many important material characteristics, such as GB energy and mobility, and therefore, texture. Although it is well established that GB segregation is inhomogeneous, the variation of GB solute composition for random boundaries is still not understood. In the current study, atomic-scale experimental and simulation techniques were used to investigate the compositional inhomogeneity of six different GBs. Three-dimensional atom probe tomography results revealed that GB solute concentration of Nd in Mg varies between 2 to 5 at.%. This variation was not only seen for different GB orientations but also within the GB plane. Correlated atomistic simulations suggest that the inhomogeneous segregation behavior observed experimentally stems from local atomic rearrangements within the GBs and introduce the notion of potential excess free volume in the context of improving the prediction of per-site segregation energies.