In Kurt Vonnegut's novel Galapagos, a certain mammal species, due to drastic and peculiar environmental changes, evolves (among other features) a smaller and smaller brain.
Has this ever happened? Are we aware of any species whose ancestors had remarkably bigger brains?
Brain size vs intelligence
Of course brain size and intelligence are two very different things. Sure these two characteristics are correlated (assuming we manage to define intelligence in any intelligible way). The sperm whale has a brain that is 8 times larger than the human brain for example and the Brown thrasher (small bird) can learn thousands of songs while other birds can memorize the location of thousands of seeds. So really size is not the only thing that matters.
You might want to read about brain-to-body mass ratio and the encephalzation quotient.
Evolution toward smaller brain size
I am pretty sure such examples should exist but it might be hard to come up with good citation on the subject because
Someone might well come up with good answers. Of course, most examples of evolution toward smaller size (such as through insular isolation as pointed out by @user137) will result is reduction in brain size however, I am not sure these example would satisfy your needs/curiosity.
Evidence of metabolic cost of brains
In the meantime, I would like to point to a few among many evidences that brain comes at a fitness cost (that might be compensated by benefits of learning and other "brain abilities"). Those evidence mainly comes from experimental evolution in labs but some comes from comparative genomics as well. In short:
Brain consumes a lot of energy (Magistretti 2013). There are evidences in Drosophila (Mery and Kawecki 2003), birds (in this review I think: Nowcki et al. 2001) and guppy (Kotrshal et al. 2013) that evolution of learning abilities comes at an important metabolic cost. Johnston (1982), and more recently Snell-Rood et al. (2009) made reviews on the cost and benefits of learning abilities that you might want to have a look at.
The acanthonus armatus is famous for its small brain. As a deep-sea fish it is required by its environment to consume very little energy, and so it is at least plausible that this is an adaptation to its environment. It's hard to compare it to the fossil record because brain size is usually estimated by the size of the cranial cavity, but a. armatus has a fairly ordinary cranial cavity .It is very nearly empty, with the small brain filling only a small fraction (dwarfed by the semicircular canals). The authors of the paper linked above weighed a number of brains, the largest of which was 48.7 mg in a 180 g fish.
