The arbitrariness of a signal has long been seen as a theoretically important but difficult to pin down notion. In this article, we suggest there are at least two different notions of arbitrariness at play in philosophical and scientific debates concerning the use of arbitrary signals, and work towards improved analyses of both. We then consider how these different types of arbitrariness can co-occur and come apart. Finally, we examine the connections between these two types of arbitrariness and the cognitive complexity of signal users with an eye towards better evaluating one possible form of human-nonhuman communicative continuity. We show that each type of arbitrariness bears its own nuanced relationship to cognitive complexity, demonstrating the theoretical importance of keeping these two notions separate.