In this paper, we propose an efficient technique for improving the performance of automatic and cooperative compositions in P2P unstructured networks during service discovery. Since the adoption of flooding to exchange queries and partial solutions among the peers of unstructured networks generates a huge amount of messages, the technique exploits a probabilistic forwarding algorithm that uses different sources of knowledge, such as network density and service grouping, to reduce the amount of messages exchanged. The technique, analyzed in several network configurations by using a simulator to observe resolution time, recall and message overhead, has shown good performances especially in dense and large-scale service networks.