Methods, devices, systems and computer program products improve the detection of watermarks that are embedded in a host content by providing information indicative of a ranking of watermark payloads to watermark extractors. A watermark extractor device obtains information indicative of a ranking of a plurality of watermark payload values, where such information designates each watermark payload value within a first subset of the plurality of watermark payload values as having an associated rank value. Based at least in-part on the information indicative of the ranking, the watermark extractor device is configured to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset. The watermark extractor then extracts a payload value, designated as belonging to the first subset, from one or more watermarks embedded in the host content.