A system that encodes a sequence of integers using a variable-length compression technique is described. During operation, the system scans the sequence of integers and observes the sizes of the integers to determine a threshold value K from the observed sizes. For a given integer which is N bits in length, if N−K is greater than or equal to zero, the system generates a tag for the encoded integer which comprises a sequence of N−K zeros followed by a one, and generates a set of remaining bits for the encoded integer as a sequence of the N bits which make up the integer. Otherwise, if N−K is less than zero, the system generates a tag for the encoded integer as a single one, and generates a set of remaining bits for the encoded integer by padding the N bits which make up the integer with zeros so that the set of remaining bits is K bits in length.