Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for generating candidate future trajectories for agents. One of the methods includes obtaining scene data characterizing a scene in an environment at a current time point; for each of a plurality of lane segments, processing a model input comprising (i) features of the lane segment and (ii) features of the target agent using a machine learning model that is configured to process the model input to generate a respective score for the lane segment that represents a likelihood that the lane segment will be a first lane segment traversed by the target agent after the current time point; selecting, as a set of seed lane segments, a proper subset of the plurality of lane segments based on the respective scores; and generating a plurality of candidate future trajectories for the target agent.