First, define what you mean by brain. Some people call the nerve ring in c. elegans the brain, defining "brain" functionally.
With something like a starfish or a jellyfish, nearly everyone agrees that there is no central nervous system; they have a distributed "neural net".
On the other side of the nerve bundles in worms, we have insects with appendages that generally require a clear CNS of some sort to integrate sensory signals and motor skills (ants and flies).
Second, define what you mean by small. The general scientific consensus is that we should compare brain size to body size and the ratio is what's significant (so a small brain is defined relative to the body it's in) whereas you may be thinking in absolute terms.