Methods, systems, and apparatus, including computer programs encoded on computer storage media, for searching an autonomous vehicle sensor data repository. One of the methods includes maintaining a collection of sensor samples and one or more embeddings of each sensor sample. Each sensor sample is generated from sensor data at multiple time steps and characterizes an environment at each of the multiple time steps. Each embedding corresponds to a respective portion of the sensor sample and has been generated by an embedding neural network. A query specifying a query portion of a query sensor sample is received. A query embedding corresponding to the query portion of the query sensor sample is generated through the embedding neural network. A plurality of relevant sensor samples that have embeddings that are closest to the query embedding are identified as characterizing similar scenarios to the query portion of the query sensor sample.