Cleaning interactions, which involve a cleaner removing ectoparasites and other material from the body of a heterospecific (client), are iconic symbiotic interactions observed on coral reefs worldwide. These small cleaners play a disproportionately large role in the structuring and function of coral reefs, influencing species interaction networks, client health and biodiversity. Cleaning patterns, however, are likely to be context-dependent and highly heterogeneous, and although we have some understanding about their spatial variation, longer-term temporal changes in cleaning interactions have remained understudied. Given that coral reefs are globally threatened and are currently experiencing large shifts in their biodiversity, it is vital ...