Pragmatic theories and computational models of reference must account for people’s frequent use of redundant color adjectives (e.g., referring to a single triangle as ‘the blue triangle’). The standard pragmatic view holds that the informativity of a referential expression depends on pragmatic contrast: color adjectives should be used to contrast competitors of the same kind to preempt an ambiguity (e.g., between two triangles of different colors), otherwise they are redundant. Here we propose an alternative to the standard view, the incremental efficiency hypothesis, according to which the efficiency of a referential expression must be calculated incrementally, over the entire visual context. This is the first theoretical account of referential efficiency that is sensitive to the incrementality of language processing, making different cross-linguistic predictions depending on word order. Experiment 1 confirmed that English speakers produced more redundant color adjectives (e.g., ‘the blue triangle’) than Spanish speakers (e.g., ‘el triángulo azul’), but both language groups used more redundant color adjectives in denser displays where it would be more efficient. In Experiments 2a and 2b, we used eye tracking to show that pragmatic contrast is not a processing constraint. Instead, incrementality and efficiency determine that English listeners establish color contrast across categories (BLUE SHAPES > TRIANGULAR ONE), whereas Spanish listeners establish color contrast within a category (TRIANGLES > BLUE ONE). Spanish listeners, however, reversed their visual search strategy when tested in English immediately after. Our results show that speakers and listeners of different languages exploit word order to increase communicative efficiency.