A computer system can compress or decompress a type-length-value (TLV) component in a message. During operation, the computer can select a compression table associated with a network interface used to send and/or to receive the message, and can search the compression table for an entry that includes a prefix of a value from type-length-value (TLV) component being compressed or decompressed. If compressing the message, the computer may generate a compressed block that corresponds to a compressed version of the TLV component, such that the compressed block includes the compression encoding in place of the prefix in the TLV component's value. The computer can also generate a compressed message that includes the compressed block in place of the TLV component, without a compression table.