The number of innovations (novel foraging techniques) a species has is considered an indicator of complex cognition because it positively correlates with relative brain size (corrected for body size). However, smaller-brained species are rarely tested for complex cognition, therefore our understanding of the relationship between complex cognition and relative brain size is incomplete. Here I compare innovative New Caledonian crows and great-tailed grackles (who both have broad diets) with the less innovative Western Scrub-jays (who have specialized diets) on a series of Aesop’s Fable water displacement experiments. This comparison tests whether innovative species perform better on a task requiring general problem solving abilities, which are another potential indicator of complex cognition in addition to innovation. Crows and grackles preferred functional options in tasks, while scrub-jays did not. These results support the hypothesis that innovativeness indicates complex cognition. However, innovativeness does not track brain size because the smaller-brained but innovative grackles performed similarly to large-brained, innovative crows, while the large-brained yet less innovative scrub-jays performed poorly. Since scrub-jays exhibit general problem solving abilities in a caching context, this demonstrates that there are multiple pathways to complex cognition and reliance on only one indicator can lead to misclassifications.