Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating a spatio-temporal embedding of a sequence of point clouds. One of the methods includes obtaining a temporal sequence comprising a respective point cloud input corresponding to each of a plurality of time points, each point cloud input comprising point cloud data generated from sensor data captured by one or more sensors of a vehicle at the respective time point; processing each point cloud input using a first neural network to generate a respective spatial embedding that characterizes the point cloud input; and processing the spatial embeddings of the point cloud inputs using a second neural network to generate a spatio-temporal embedding that characterizes the point cloud inputs in the temporal sequence.