This study investigated how target-relevant attribute categories and information valence affect information search during impression formation. Equal numbers of male and female participants (N=270) formed a likability impression of a male or female target person by accessing positive and/or negative information about the target person's appearance and/or traits. The information environment permitted either unicategorical (appearance or trait) or bicategorical (appearance and trait) searches and the information items were either univalent (all positive or all negative) or bivalent (half positive and half negative). As predicted, perceivers accessed more appearance than trait attributes in the unicategorical searches and more trait than appearance attributes in the bicategorical searches (p < .0001). Univalent negative searches were shorter than univalent positive searches (p < .0001), confirming a negativity effect. Bivalent searches restored search length compared to univalent negative searches, with this effect occurring only for traits in unicategorical searches (p < .0001). Results were interpreted in terms of a fundamental preference for more stable trait information, with appearance information used primarily to enable a trait inference.