The present invention extends to methods, systems, and computer program products for scalable differential compression for network data. Network data exchanged between Wide Area Network ("WAN") acceleration devices is cached at physical recordable-type computer-readable media having (potentially significantly) larger storage capacities than available system memory. The cached network data is indexed through features taken from a subset of the cached data (e.g., per segment) to reduce overhead associated with searching for cached network data to use for subsequent compression. When a feature match is detected between received and cached network data, the cached network data can be loaded from the physical recordable-type computer-readable media into system memory to facilitate data compression between Wide Area Network ("WAN") acceleration devices more efficiently.