This specification describes techniques for verifying location information. One example method includes identifying location information associated with a particular entity; determining, based on the location information, a candidate entity set including a plurality of candidate entities, wherein each candidate entity is different than the particular entity, and wherein the candidate entity set includes a correct set including candidate entities that satisfy candidate location criteria; sending the candidate entity set and the candidate location criteria to the particular entity; receiving a selected entity set including one or more of the candidate entities; determining that the selected entity set includes a number of candidate entities from the correct set satisfies a location verification threshold; and in response determining that the selected entity set includes the number of candidate entities from the correct set that exceeds the location verification threshold, determining that the location information of the particular entity is verified.