We show that Au nanoparticles spontaneously move across the (001) surface of InP, InAs, and GaP when heated in the presence of water vapor. As they move, the particles etch crystallographically aligned grooves into the surface. We show that this process is a negative analogue of the vapor-liquid-solid (VLS) growth of semiconductor nanowires: the semiconductor dissolves into the catalyst and reacts with water vapor at the catalyst surface to create volatile oxides, depleting the dissolved cations and anions and thus sustaining the dissolution process. This VLS etching process provides a new tool for directed assembly of structures with sublithographic dimensions, as small as a few nanometers in diameter. Au particles above 100 nm in size do not exhibit this process but remain stationary, with oxide accumulating around the particles.