We study peer-to-peer service networks consisting of autonomous agents who seek and provide information services. Agents potentially help each other by giving referrals to guide the search. Each agent autonomously decides whom to contact for a service and whom to provide a service or a referral. Service networks evolve as the agents change their neighbors to improve how their needs are fulfilled. If an agent autonomously decides to, it may cache some responses from other (information) services. We observe that even a small cache improves agents? success in discovering needed services and enables a few initial service providers to serve the information needs of many. Caching induces clustering of agents based on interest.