Accurate flow-level measurement is highly desirable in networking products. As network speed increases, the direct approach of dynamically assigning per-flow counters requires a large amount of fast memory, which is prohibitively expensive. We observe that measurement with limited memory inherently benefits from source coding, and propose "Counter Braids", an architecture that compresses as it counts. The counts are decompressed offline using a novel message passing algorithm, which also has implications for the area of compressed sensing.