Aspects of the disclosure relate to methods for controlling a vehicle having an autonomous driving mode. For instance, sensor data may be received from one or more sensors of the perception system of the vehicle, the sensor data identifying characteristics of an object perceived by the perception system. When it is determined that the object is no longer being perceived by the one or more sensors of the perception system, predicted characteristics for the object may be generated based on one or more of the identified characteristics. The predicted characteristics of the object may be used to control the vehicle in the autonomous driving mode such that the vehicle is able to respond to the object when it is determined that the object is no longer being perceived by the one or more sensors of the perception system.