In many group-living animal species, interactions take place in changing social environments, increasing the information processing necessary to optimize social decision-making. Communities with different levels of spatial and temporal cohesion should differ in the predictability of association patterns. While the focus in this context has been on primate species with high fission-fusion dynamics, little is known about the variability of association patterns in species with large groups and high temporal cohesion, where group size and the environment create unstable subgroups. Here, we use sooty mangabeys as a model species to test predictability on two levels: on the subgroup level and on the dyadic level. Our results show that the entirety of group members surrounding an individual is close to random in sooty mangabeys; making it unlikely that individuals can predict the exact composition of bystanders for any interaction. At the same time, we found predictable dyadic associations based on assortative mixing by age, kinship, reproductive state in females, and dominance rank; potentially providing individuals with the ability to partially predict which dyads can be usually found together. These results indicate that animals living in large cohesive groups face different challenges from those with high fission-fusion dynamics, by having to adapt to fast-changing social contexts, while unable to predict who will be close-by in future interactions. At the same time, entropy measures on their own are unable to capture the predictability of association patterns in these groups. © 2020 The Author(s)