The invention improves query response latency in a peer-to-peer network. The invention augments core neighbors included in a neighbor list of a peer node by selecting auxiliary neighbors for inclusion in the neighbor list of the peer node of a peer-to-peer network. In one embodiment, a method includes maintaining query frequency information associated with each of a plurality of peer nodes of the peer-to-peer network, selecting at least one of the peer nodes of the peer-to-peer network as an auxiliary neighbor using the query frequency information, and updating a neighbor list to include the at least one peer node selected as the at least one auxiliary neighbor. The core neighbors stored at a peer node attempt to minimize the worst-case query latency for that peer node. The auxiliary neighbors stored at the peer node attempt to reduce the average query latency for that peer node. The auxiliary neighbors may be used in any peer-to-peer system, such as Pastry, Tapestry, Chord, SkipGraph, and the like.