Carbon allotropes have been explored intensively by ab initio crystal structure prediction, but such methods are limited by the large computational cost of the underlying density functional theory (DFT). Here we show that a novel class of machine-learning-based interatomic potentials can be used for random structure searching and readily predicts several hitherto unknown carbon allotropes. Remarkably, our model draws structural information from liquid and amorphous carbon exclusively, and so does not have any prior knowledge of crystalline phases: it therefore demonstrates true transferability, which is a crucial prerequisite for applications in chemistry. The method is orders of magnitude faster than DFT and can, in principle, be coupled with any algorithm for structure prediction. Machine-learning models therefore seem promising to enable large-scale structure searches in the future.