The default heuristics applied when encoding paletted images is to use as few bits per pixel as possible. However, it is not uncommon for a bigger number of bits per pixels (usually, 8) to be a better choice, even when a smaller number is also possible to be used. The reason relies on the deflate compression, which is designed to encode 8bit values best.
More precisely, the LempelZiv algorithm encodes sequences of 8bit values. Further, the Huffman algorithm might compress a certain number of values better than twice as few, but twice as long values which might be perceived as noise. For example, the sequence 1, 2, 3, 2, 2, 1 has more redundancy than the sequence of pairs (1, 2), (3, 2), (2, 1).
The example below (640 x 480, 16color paletted image) is better compressed
at 8bpp than at 4bpp. On the other hand, if interlaced, the same example
is better compressed at 4bpp. The example was compressed using the best
deflate compression and no filtering.















It can be noticed that Z_FILTERED is better when the higher bit depth is chosen.
The test image is here: