As the increasing popularity of superpixel-based applications, measuring superpixel-level similarity becomes an important and commonly required problem. In this paper, we propose a general bag of squares (BoS) model for such particular purpose. Compared to existing methods, our approach provides a full scheme to both invariantly represent superpixels and accurately measure their pairwise similarities. In order to handle the split-and-merge variety of superpixels of same objects in different scenes, our model is based on superpixel pyramid. As a result, the BoS model of a superpixel is built upon a group of subregions consisting of the superpixel itself and its children subregions in the pyramid. For each subregion, we extract a proper number of maximum squares via distance transform, and then use a fast self-validated approach to clustering them into a small number of dominant squares, which together with a rotation and scale invariant square descriptor, jointly compose the BoS model for the particular superpixel. Finally, we measure the similarity between a pair of superpixels by the closeness of their BoS models. Experiments on interactive object segmentation and co-saliency detection show that the proposed BoS model can reliably capture the delicate differences among superpixels, thus always producing better segmentation results, especially for segmenting highly variant objects in clutter scenes.