Approaches for staged data compression are provided, where each stage reflects a progressive increase in granularity, resulting in a scalable approach that exhibits improved efficiency and compression performance. The first stage comprises a long-range block-level compressor that determines redundancies on a block-level basis (based on entire data blocks, as opposed to partial segments within data blocks). The second stage comprises a long-range byte-level compressor that compresses an uncompressed block based on byte segments within the block that match previously transmitted segments. The duplicate segments are replaced with pointers to matching segments within a decompressor cache. Nonmatching segments of the data block are left uncompressed and passed to a third stage short-range compressor (e.g., a grammar-based compressor). The staged progression in granularity provides advantages of maximizing the compression gain while minimizing processing and storage requirements of the compressor and decompressor.