Methods, computer systems, and apparatus, including computer programs encoded on computer storage media, for performing three-dimensional auto-labeling on sensor data. The system obtains a sensor data segment that includes a temporal sequence of three-dimensional point clouds generated from sensor readings of an environment by one or more sensors. The system identifies, from the sensor data segment, (i) a plurality of object tracks that each corresponds to a different object in the environment and (ii) for each object track, respective initial three-dimensional regions in each of one or more of the point clouds in which the corresponding object appears. The system generates, for each object track, extracted object track data that includes at least the points in the respective initial three-dimensional regions for the object track. The system further generates, for each object track and from the extracted object track data for the object track, an auto labeling output that defines respective refined three-dimensional regions in each of the one or more point clouds.