Phase-change optical memories are based on the astonishingly rapid nanosecond-scale crystallization of nanosized amorphous marksgin 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 Ag3.5 In 3.8 Sb 75.0 Te17.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.