Many personalization tasks have their best answer right at the edge of what a person will accept. Examples are "make this photo of my dog as painterly as possible while it still looks like my dog" and "make this alert sound as attention-grabbing as possible before it becomes irritating." Two research communities each own half of this problem, and neither has the whole of it. Constrained Bayesian optimization (a family of methods that fits a probabilistic model to a few expensive evaluations and uses it to choose the next one) has shown that standard methods stall safely inside the feasible region, and that one must deliberately probe beyond the edge to locate it. Interactive evolution and human-in-the-loop optimization have shown that people tire within a few dozen judgments, and that showing them broken artifacts is the fastest way to exhaust them. Probing the boundary is necessary to find the optimum, but in a human loop every probe costs the user attention.
We propose to dissolve this conflict through query design rather than better modeling alone. Each screen shows the user a short "boundary ladder": a row of candidates spaced along one direction, chosen so that the row crosses the model's predicted acceptability edge near the predicted best point. The user makes one gesture with two parts. They mark the last acceptable rung and they pick their favorite. That single response gives a boundary location along that direction, which works like a multi-way bisection. It also gives a preference judgment. Unacceptable rungs are confined to the end of an ordered row, where they read as "too far" rather than as random garbage. Our claim is that ladders let a fast, single-step optimizer capture most of the benefit of slow multi-step lookahead. They should reach boundary-proximal optima in markedly fewer screens than unconstrained preference optimization, while showing users fewer unacceptable artifacts than standard boundary-exploration methods.
Core Claim
The automated constrained-optimization literature motivates the problem. Lookahead Bayesian Optimization with Inequality Constraints uses dynamic-programming rollout. Two-step lookahead Bayesian optimization with inequality constraints uses two-step lookahead with score-function gradients. Both show that greedy expected improvement weighted by feasibility probability stalls in the interior. Both also show that deliberately sampling an infeasible point and then exploiting along the revealed edge breaks the plateau. Their mechanism is temporal: sacrifice now, exploit later. That is also their weakness for interactive use, since the two-step method needs 25 to 30 minutes to plan a batch of five points.
Our observation is that a human screen already holds several candidates. If those candidates are ordered along a line that crosses the edge, the probe and the near-edge exploitation happen within the same round. Lookahead is replaced by spatial structure inside one query, so planning cost stays at a single-step level of a few seconds.
The second ingredient addresses an assumption we reject. Boundary Exploration for Bayesian Optimization With Unknown Physical Constraints (BE-CBO) supplies the constraint model we reuse. It uses a deep ensemble classifier, which captures sharp edges better than a smooth Gaussian process, and an uncertainty-dependent threshold that permits probing across the predicted boundary. It also assumes that infeasible points reveal nothing about the objective. For a human judge this is false. An over-stylized dog that no longer looks like the user's dog still ranks against its neighbors, so the ladder's preference signal is used across all rungs.
Research Program
Let $x$ be a point in a low-dimensional edit space. Following Personalized Image Generation via Human-in-the-loop Bayesian Optimization (MultiBO), this space consists of geometric warps of self-attention features in FLUX or Stable Diffusion, plus an edit-strength axis. We fit two models.
The first is a preference model for the user's objective $f$. It is MultiBO's multinomial-logit Gaussian process, which learns from "pick N of K" choices. We feed it the favorite-pick from every ladder.
The second is an acceptability classifier $c(x)$, a deep ensemble as in BE-CBO. Its training data come from the user's "last acceptable rung" mark: every rung up to the mark is labeled acceptable and every rung beyond it unacceptable. A single click therefore produces K labels, under the assumption that acceptability changes once along a short, roughly monotone ladder. We test this assumption directly, as described below.
Each round, the optimizer chooses an anchor $x_0$ near the predicted constrained optimum and a direction $d$ along which the objective model predicts improvement. It then places rungs $x_k = x_0 + t_k d$ for $k = 1,\dots,K$, spanning the band where the ensemble is uncertain. Anchor, direction and spacing are chosen to maximize the expected reduction in uncertainty about the value of the best acceptable point. This is the targeted-boundary idea of COBALT (Chen et al.) and of the adaptive constraint learning in Interactively Learning Preference Constraints in Linear Bandits: map the edge only where it matters for the optimum. The choice is subject to a fatigue cap,
$$\sum_{k=1}^{K} \big(1 - \hat p(x_k)\big) \le m,$$
where $\hat p(x_k)$ is the ensemble's predicted acceptability of rung $k$ and $m$ is the expected number of unacceptable images a user tolerates per screen. The cap makes the "value of infeasibility" an explicit, tunable budget instead of something ignored (as in BE-CBO) or forbidden (as in MultiBO's implicit validity).
Our work differs from Lindner et al. in three ways. They learn a single linear preference constraint from noisy absolute ratings over a fixed set of arms and allow violations freely. We learn a nonlinear edge from ordinal ladder marks over a continuous generative space, and we budget violations.
To handle drift, we follow Improving the Performance of Predicting Users' Subjective Evaluation Characteristics to Reduce Their Fatigue in IEC, which models evaluation characteristics that change during a session. We down-weight older boundary marks, and we test whether users' acceptability edges shift within a session.
Baselines
The naive reference point is MultiBO run unconstrained, with K candidates per screen chosen by its own acquisition function and no acceptability model. The user simply avoids picking unacceptable images. This is also the strongest existing human-in-the-loop system. It reports a 70.82% volunteer win rate against DiffusionDPO, IterComp and DEMON, target alignment of CLIP-I 0.9364 and LPIPS 0.5497, and convergence in 32 to 50 iterations, about 20 minutes. All of these figures are on its own personalization task, not on boundary-seeking tasks. We will run it on our edit space with identical K, generator, prompts and screen budget. Beating it means reaching the same final satisfaction in at most half as many screens on boundary-proximal tasks, with no loss on tasks whose optimum lies in the interior.
The strongest constrained competitor is BE-CBO. We adapt it to humans by showing K points chosen by its acquisition function and collecting per-image accept or reject flags plus a favorite pick, so its information per screen is comparable. On its synthetic and engineering suites it outperformed SCBO and constrained expected improvement in nearly all problems, but the file gives no specific values, and there is no reported result found on Lacuna for BE-CBO in a human or preferential setting. Beating it means matching its simulated regret while showing at least 40% fewer unacceptable artifacts per session. A second constrained competitor is greedy expected improvement weighted by feasibility probability on the same two models. The two-step lookahead method reports reaching a utility gap of $10^{-5}$ in 27 evaluations where this greedy method stalls at $10^{-3}$. On simulated users we will also run the two-step method itself, offline and without the latency limit, as an upper reference for what lookahead buys.
Two ablations isolate the key ingredient. The first keeps the same models, cap and single gesture but replaces the ordered ladder with K points chosen independently by the same acquisition function. This separates the effect of spatial structure from the effect of the models. The second drops preference information from rungs beyond the mark, BE-CBO style, to measure the value of learning from infeasible rungs. All methods share hyperparameter search budgets tuned on simulated users that are held out from evaluation users.
Why not just…?
Why not just use an automated realism or identity score as the constraint? This is a genuine threat. If CLIP-image similarity to the reference predicts where each person's "still my dog" edge lies, a proxy threshold beats any human query. The MultiBO paper reports that optimizing automated scores invites reward hacking with high-frequency artifacts, and Pick-a-Pic shows that common metrics can anticorrelate with human preference. Neither paper tests acceptability thresholds specifically, however. We will measure, across users, how much of the variance in human-marked edges a proxy threshold explains. If a single proxy threshold explains most of it, the method reduces to using the proxy as the classifier's prior, and we will report that. Proxy-as-prior with ladder correction is included as an arm in any case.
Why not just let preference optimization absorb the constraint, since users won't pick unacceptable images? Choice feedback says only that the favorite beats the others. It does not say where acceptability ends, so an unconstrained optimizer keeps proposing over-the-edge images at an unknown rate. The unconstrained MultiBO baseline measures exactly this, both in screens to optimum and in count of unacceptable images shown.
Why not just use a penalty term? Lindner et al. show in driving simulations that the right penalty weight varies widely across scenarios, while learned constraints transfer. We test the penalty version with weights tuned on held-out simulated users, then evaluate it on users whose edges differ.
Why not just prune the space offline from a pilot study? Acoustical and behavioral heuristics for fast interactive sound design pruned 4,096 sound settings to 64 using data from 28 pilot subjects and halved the iterations users needed. Pruning works when edges are shared across people and fails when they are personal. Our heterogeneity measurement determines which regime holds. We also include a pruned-space arm built from a pilot cohort disjoint from the evaluation users.
Proposed Experiments
We start with simulated users. Each simulated user has an objective (a stylization score) and a personal acceptability edge defined by a threshold on CLIP-image similarity to a reference image. The threshold is sampled per user. Prompts and references come from Pick-a-Pic, and PickScore serves as a stylization-agnostic quality term. Choice noise and marking noise grow with round number to mimic fatigue. To check that conclusions do not depend on image generators, we embed the Townsend, Simionescu and LSQ constrained functions from the BE-CBO suite in the same simulated-oracle wrapper.
The metrics are regret at a fixed screen budget of 10, 20 and 30 screens, the number of unacceptable items shown, and planning latency, which must stay under two seconds per screen. The decisive simulated check is the ordered-versus-unordered ablation. If ordered ladders do not beat independent K-point screens at an equal fatigue cap, the central claim fails.
We then run a human study of about 30 participants on two tasks. In the image task, users stylize a personal reference photo with FLUX attention warps. In the sound task, users tune a reconstruction of the six-parameter additive synthesis space from Souaille et al. for maximal detectability without irritation. Each participant runs the ladder method and MultiBO in counterbalanced order with a 20-screen budget. Outcomes are final-choice satisfaction, blind pairwise comparison of end results, and a NASA-TLX-style workload rating. We also log ladder-monotonicity violations, meaning cases where a user marks a rung acceptable after one marked unacceptable, which happens when re-shown in shuffled order. Frequent violations would undercut the one-click labeling assumption.
Finally, we test the proxy-heterogeneity question. Each participant marks edges on fixed probe ladders, and we measure how much of the cross-user variance in those edges a proxy threshold explains. This tells us whether a human needs to be in the loop for the boundary at all.
References
- Lookahead Bayesian Optimization with Inequality Constraints
- Two-step lookahead Bayesian optimization with inequality constraints
- Boundary Exploration for Bayesian Optimization With Unknown Physical Constraints
- Personalized Image Generation via Human-in-the-loop Bayesian Optimization
- Constrained Bayesian Optimization with Adaptive Active Learning of Unknown Constraints
- Interactively Learning Preference Constraints in Linear Bandits
- Improving the Performance of Predicting Users' Subjective Evaluation Characteristics to Reduce Their Fatigue in IEC
- Pick-a-Pic: An Open Dataset of User Preferences for Text-to-Image Generation
- Acoustical and behavioral heuristics for fast interactive sound design