A method for updating a message template based on receiving a plurality of common deltas. At a first device, the method detects a first compressed message that includes a first delta and that references a first message template and stores an indication of having received the first delta. The first delta is combinable with the first message template to reconstruct a decompressed message. The first device receives at least one subsequent compressed message that includes the first delta and that references the first message template, and stores an indication of each subsequent time the first delta is received. Based on the stored indications, the first device determines that the first delta was received in accordance with at least one predetermined threshold factor, and in response thereto, initiating a procedure to generate a superseding message template, which updates the first message template by including the first delta.