Phase-change optical memories are based on the astonishingly rapid nanosecond-scale crystallization of nanosized amorphous 'marks' in a polycrystalline layer. Models of crystallization exist for the commercially used phase-change alloy Ge(2)Sb(2)Te(5) (GST), but not for the equally important class of Sb-Te-based alloys. We have combined X-ray diffraction, extended X-ray absorption fine structure and hard X-ray photoelectron spectroscopy experiments with density functional simulations to determine the crystalline and amorphous structures of Ag(3.5)In(3.8)Sb(75.0)Te(17.7) (AIST) and how they differ from GST. The structure of amorphous (a-) AIST shows a range of atomic ring sizes, whereas a-GST shows mainly small rings and cavities. The local environment of Sb in both forms of AIST is a distorted 3 + 3 octahedron. These structures suggest a bond-interchange model, where a sequence of small displacements of Sb atoms accompanied by interchanges of short and long bonds is the origin of the rapid crystallization of a-AIST. It differs profoundly from crystallization in a-GST.