Computer vision for unsuccessful queries and iterative search is described. The described system leverages visual search techniques by determining visual characteristics of objects depicted in images and describing them, e.g., using feature vectors. In some aspects, these visual characteristics are determined for search queries that are identified as not being successful. Aggregated information describing visual characteristics of images of unsuccessful search queries is used to determine common visual characteristics and objects depicted in those images. This information can be used to inform other users about unmet needs of searching users. In some aspects, these visual characteristics are used in connection with iterative image searches where users select an initial query image and then the search results are iteratively refined. Unlike conventional techniques, the described system iteratively refines the returned search results using an embedding space learned from binary attribute labels describing images.