We present a study of mechanisms for surface hole formation during heterogeneous, metal-on-metal epitaxial growth of surface alloy systems. We consider specifically the system Rh/Ag(001) for which a detailed STM study of the structures formed during epitaxy at room temperature is available.@footnote 2@ Three mechanisms are proposed and investigated via a kinetic Monte Carlo simulation based on a simple model for the atomic-level energetics. It is found that the dominant mechanism of hole formation in this system involves the growth of vacancy islands via an upward exchange diffusion move. First principles total energy computations using the VASP suite of programs confirm the plausibility of the explanation. Our simulation also accounts, via the same mechanism, for the observation of the growth of Ag islands on top of deposited material. An alternative mechanism for hole formation, coalescence of point vacancies, is found not to contribute appreciably to formation of vacancy clusters, but point vacancies do catalyze structure formation by other means. The mechanism identified in the present study should be applicable to other soft substrate surface alloy systems. L.D.R. thanks the DOE for supporting a visit to Sandia Livermore in order to carry out the VASP calculations.. @FootnoteText@ @footnote 1@Funded by the NSF via grant DMR - 9974545 @footnote 2@S.-L. Chang, et al., Phys. Rev. B53, 13747 (1996).