Implicit in the question is the assumption that the examples of the animals you mention somehow would outperform species (with brains) of similar size. Comparing intelligence between different species, no matter how you define it, is going to be challenging.
I would argue that it is impossible to devise a single task with which to compare such different species as ants, octopi, crows, and rats. However some correlations between cognitive capacity and some anatomical features of the brain have been investigated.
Brain-to-body mass ratio
The scaling of the ratio of total brain-to-body mass is not linear. It rather follows a power law relationship, typical to allometric scaling.
$$ m_{(brain)} = \alpha \times m_{(body)} ^R $$
It is convenient to log-transform the mass variables in order to work on the following linear relationship:
$$ log(m_{(brain)}) = R \times log(m_{(body)}) + log(\alpha) $$
The following plot from wikipedia displays this relationship for a number of different species. The slope of this line is $R$, and the intercept $log(\alpha)$. H. Jerrison proposed that the distance of a species from this line could provide an estimate of cognitive capacity. He called that measure encephalisation quotient. The reasoning behind this idea is that of course the brain of bigger animals will be bigger and that of small animals smaller, but is it bigger or smaller than expected from this simple universal model? If so, that may provide a clue for more advanced cognitive skills.
[CC BY-SA 4.0], via Wikimedia Commons
Indeed, we can see as examples that humans and dolphins diverge from this line quite distinctly, which matches with our intuition about these species' cognitive abilities, but so do some species of mice. Is this metric good enough to predict cognitive abilities overall? Given the primitive functions that many brain areas are associated with, such as the brainstem, it is not straightforward that a simple overall increase of brain size above what this simple model would predict, would confer any benefit to the overall cognitive capacity of an animal. At least when attempting to correlate cognitive capacity with several measures based on brain anatomy of non-human primates, it was found that overall (log)brain size or (log)neocortex size are better predictors than the encephalisation quotient. The proportion of brain volume that the neocortex occupies is also able to distinguish the brains of primates from those of insectivores or carnivores. Given the high-level functions that the neocortex is involved with, these results are not surprising.
Neuron size and density
Scaling of the whole brain or the neocortex can be due to a number of things. Either more cells are added, the cells become bigger, more glial cells are added etc. So which is it? According to a 2014 paper by the Kaas group more neurons are added in the cerebral cortex and the cerebellum. This results in a decrease in neuronal density in all species studied except primates, where neuronal density appears to remain relatively stable with the number of neurons. The authors conclude from this result that neuronal size (including axons and dendrites) must have remained stable in primates.
To answer your question, if we take overall brain size or neocortex size as a proxy for the cognitive capacity of an animal, we can conclude that the relationship indeed is not linear, as you predicted. However, we have no reason to believe that some species are exceptionally more endowed than what would be expected of them based on brain size given this non-linear relationship, except perhaps primates. Of course comparing mammals to invertebrates based on this evidence is a non-starter as they lack a centralised brain and/or neocortex.
Although we may be surprised by the remarkable things some species can do, this may only mean that we have not looked close enough at the capabilities of other yet unsuspected species. Conversely, our amazement may simply be because of the fact that we underestimate the capabilities of animals that are not similar to us.
Further reading: Evolution of the brain and intelligence, G. Roth and U. Dicke, TICS, 2005.10.1016/j.tics.2005.03.005
Related questions in Biology SE: