Incremental utility elicitation (IUE) is a decision-theoretic framework in which tools simultaneously make suggestions to a human decision maker based on an incomplete model of the decision maker’s utility function, and update the model based on feedback from the user. Most systems that perform IUE construct and ask questions about a small number of alternatives in order to build a model of the user’s preferences. We describe a system called VEIL that is based on visual exploration of the available alternatives and provides visual cues about their estimated utility based on IUE. VEIL uses a linear programming formulation to make fast updates to the utility estimate based on the user’s expressed preferences between pairs of alternatives. In experiments, VEIL’s update method converges quickly to make good suggestions and help the user form an overall impression of the space of alternatives.