Deformations in granular media are described by using a representation of the microkinematics of the underlying assembly through Dirichlet tessellation. Based on a probabilistic analysis of topological rearrangements induced by evolving microstructures in the assembly, homogenization is carried out within a multiscale approach-from deforming individual cells to cell network level-to eventually describe global strain in the granular ensemble. In contrast to other models in the literature, tessellation network properties are directly linked to physical microstructural characteristics of the granular assembly through local coordination number and fabric anisotropy. Because these microstructural variables dictate both strain and stress in a granular medium, this provides a route to establish a stress-strain relationship as an ultimate goal. In this paper, detailed attention is paid to the description of evolving fabric anisotropy and coordination number as a combination of dissipative microstructural rearrangements and nondissipative contact losses and gains. By introducing these two mechanisms, peak response of a dense assembly can be modeled as well as asymptotic behavior such as critical state as commonly known in soil mechanics. Model estimates of the response of granular assemblies compare very well with simulation results obtained from discrete element modeling (DEM) computations. Verification was conducted for a wide range of initial density for shearing under both constant mean stress and biaxial compression.