Several obligate associate crabs and shrimps species may co-occur and interact within a single coral host, leading to patterns of associations that can provide essential ecological services. However, knowledge of the dynamics of interactions in this system is limited, partly because identifying species involved in the network remains challenging. In this study, we assessed the diversity of the decapods involved in exosymbiotic assemblages for juvenile and adult Pocillopora damicornis types α and β on reefs of New Caledonia and Reunion Island. This approach revealed complex patterns of association at regional and local scales with a prevalence of assemblages involving crab-shrimp partnerships. Furthermore, the distinction of two lineages in the snapping shrimp Alpheus lottini complex, rarely recognized in ecological studies, reveals a key role for cryptic diversity in structuring communities of mutualists. The existence of partnerships between species that occurred more commonly than expected by chance suggests an increased advantage for the host or a better adaptation of associated species to local environmental conditions. The consideration of cryptic diversity helps to accurately describe the complexity of interaction webs for diverse systems such as coral reefs, as well as the functional roles of dominant associated species for the persistence of coral populations. Mutualistic interactions are diverse, widespread and central to the structure and function of both terrestrial and marine ecosystems 1-3. Tropical coral reefs, one of the most diverse ecosystem on Earth 4 , are particularly renowned for depending on complex networks of mutualistic relationships for their establishment and maintenance 3,5. The collection of partnerships of scleractinian corals with other organisms represents one of the most complex interactive networks, in which multiple endo-(in situ) and exo-(ex situ) mutualistic species promote the growth, survival and reproduction of the coral host, which in turn provides crucial food and shelter. While the association between corals and their endosymbiotic zooxanthellae is the best studied 5-7 , the importance of the partnerships between corals and larger epifaunal macro-invertebrates 8 , mostly represented by decapod crustaceans 8,9 is increasingly recognized. These understudied coral dwellers, also called exosymbionts, are either obligate or facultative (i.e., opportunistic) associates 10. Some obligate exosymbionts are well known for their key contribution to coral host survival, among the most notable being the crabs in the genus Trapezia and the snapping shrimp Alpheus lottini (Guérin Méneville 1829). These exosymbionts are both exclusively associated with pocilloporid corals 8,11,12 and provide various cleaning 11,13 , physiological 14 and defense services 12,15,16 to their host, such as the removal of sediments and the deter-rence of large corallivorous predators (e.g., Acanthaster planci).