Nanostructurization in three types of tetra-arsenic tetra-sulfide As4S4 polymorphs composed by (1) preferential β -As4S4, (2) realgar α-As4S4 and (3) admixture of As4S4 in the form of β -realgar, pararealgar and intermediate c-phase subjected to mechanochemical ball milling in a water solution of poly-vinylpyrrolidone (PVP) are characterized with multiexperimental structure-sensitive probes. Void structure of pelletized As4S4-PVP nanocomposites is probed by positron annihilation lifetime spectroscopy complemented with atomic-sensitive techniques such as X-ray powder diffraction, Raman scattering and scanning electron microscopy with energy-dispersive X-ray spectroscopy. Appearance of arsenolite As2O3 crystallites is character for all As4S4 polymorphs affected by wet milling. Positron annihilation lifetime data considered in terms of substitution positron-positronium trapping confirm complicated nature of nanocomposites. Modified x3-x2-coupling decomposition algorithm developed in addition to unconstrained x3-term fitting procedure is applied to parameterize annihilation channels in these nanocomposites. Interfacial free-volume voids between neighboring nanoparticles in PVP environment are defined as most favorable trapping sites, they being rather loosely composed by As4S4 crystallites in full respect to variety of crystallographic polymorphs used for milling. Detected annihilation channels are ascribed preferentially to intrinsic free-volume voids insensitive to trapping states at the surface of oxidized nanocomposites.