The nucleation and growth of carbon on catalytically active metal surfaces is one of the most important techniques to produce nanomaterials such as graphene or nanotubes. Here it is shown by in situ electron microscopy that fullerene-like spherical clusters with diameters down to 0.4 nm and thus much smaller than C60 grow in a polymerized state on Co, Fe, or Ru surfaces. The cages appear on the surface of metallic islands in contact with graphene under heating to at least 650 °C and successively cooling to less than 500 °C. The formation of the small cages is explained by the segregation of carbon on a supersaturated metal, driven by kinetics. First principles energy calculations show that the clusters polymerize and can be attached to defects in graphene. Under compression, the polymerized cages appear in a crystalline structure.