acceptodds
Under review as a conference paper at ICLR 2027

Persistent Preference Inference for Query-Efficient Interactive Multi-Objective Optimization

Abstract

Interactive multi-objective optimization uses decision-maker feedback to steer search. However, repeated consultations become costly as candidate populations evolve during optimization. We ask whether earlier comparisons can reduce the decision-maker feedback required to select preferred candidates from subsequent populations. We introduce Persistent Preference Inference (PPL), a persistent preference inference framework that uses linear programming to certify pairwise relations over a feasible preference region maintained across consultations and compatible with historical comparisons. Only comparisons that cannot be resolved using previously elicited feedback require new queries. We prove an expected upper bound on the number of explicit queries required by PPL to infer a preference-aligned ranking. We further evaluate its practical query efficiency by constructing preference-aligned model leaderboards from pairwise comparison data on Chatbot Arena. In this setting, PPL achieves ranking quality comparable to the baseline with fewer target-user queries. When integrated into multi-objective optimization to guide search, PPL improves preference-region alignment over competing interactive methods under matched cumulative query budgets across 36 benchmark configurations and an RfaH protein sequence design task. These improvements are achieved while resolving more than of processed pairwise comparisons through inference from previously elicited preference feedback. The results demonstrate that reusing preference information across evolving populations can substantially reduce interaction without compromising preference-guided search.

Primary area:
optimization
Keywords:
Preference Learning, Active Learning, Pairwise Comparisons, Interactive Optimization, Multi-Objective Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_6id9OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Persistent Preference Inference (PPL) for query-efficient interactive multi-objective optimization. PPL maintains a feasible region of aspiration points consistent with historical pairwise feedback, uses LP-based certification and transitive propagation to infer pairwise relations without additional user queries, and queries the decision maker only for unresolved comparisons. The inferred preference is integrated into NSGA-II, MOEA/D, and IBEA. The paper also provides a conditional query-complexity analysis and evaluates the method on 36 multi-objective benchmark configurations, RfaH protein sequence design, and standalone preference-learning tasks based on Chatbot Arena.

Critical strengths
  1. The paper addresses an important practical limitation of interactive optimization: previously collected preference feedback is often underused as the candidate population changes. Maintaining a persistent feasible preference region provides a clean and intuitive way to reuse this information across consultations.

  2. The empirical evaluation is relatively comprehensive. PPL is tested with three different evolutionary optimization frameworks, multiple benchmark families, a protein-design task, and standalone preference-learning experiments. The ablations are also useful in showing that persistent memory, rather than transitive propagation alone, is a major source of the query savings.

Critical weaknesses
  1. The theoretical query-complexity result is fairly conditional. The O(m log N) bound requires both persistent realizability and an η-splitting assumption on the comparisons actually queried. Importantly, the proposed median-insertion procedure does not itself guarantee this splitting property. Therefore, the result does not establish O(m log N) query complexity for PPL in general candidate populations, which makes the headline theoretical guarantee somewhat weaker than it initially appears.

  2. Much of the end-to-end evaluation uses a fixed aspiration-point preference oracle that closely matches PPL’s modeling assumptions. The paper includes a linear-utility mismatch experiment, but only in a relatively limited setting. In addition, the reported 98.9% query reduction on Chatbot Arena should be interpreted cautiously: the shared query-free capability initialization already achieves approximately the final ranking accuracy, and many PPL runs therefore require no additional query. This makes it difficult to separate the contribution of persistent preference inference from the strength of the initialization and stopping mechanism.

Questions for authors
  1. Can the authors empirically measure the version-space reduction or effective η for the comparisons actually queried by PPL? This would help establish whether the splitting assumption underlying the O(m log N) result typically holds in the reported experiments.

  2. For the Chatbot Arena experiment, how much of the 98.9% query reduction remains when PPL and the strongest baselines are compared under exactly the same initialization and stopping criterion, or at matched numbers of target-user queries? The current results suggest that much of the ranking accuracy is already present before any target-user query.

  3. Can the authors provide broader end-to-end experiments under preference-model mismatch, beyond the single linear-utility setting, for example with nonlinear or changing preferences? This would materially strengthen the practical case for persistent reuse of historical comparisons.

5 comments
AuthorsOpenReview ↗

Ranking-Space Diagnostics, Controlled Query Savings, and Preference Robustness

Q1: Measures for Version Space Reduction

We measured ranking-space splits in 20 additional diagnostic optimization trajectories (10 each for ZDT1/DTLZ2). We counted 1044/1298 paid queries at generations 25/100/175/225; 254 queries at other generations remain uncounted. Of counted queries, 587 have exact η; 457 involve count sampling.

Entries: ZDT1/DTLZ2 (candidate N=196–200/122–128). Cumulative Q is a trajectory mean; query counts are totals at t. S_± count feasible strict rankings; η_q=min(S_+,S_-)/(S_++S_-). No-query η=NA.

tCumulative QCounted queriesMinimum ranking η
2539.6/59.6396/596~1.37e-04† / ~3.07e-09†
10052.0/71.612/161/5/1/4
17553.1/74.53/81/2/1/3
22554.1/75.74/91/3/1/4

† includes count sampling. Simultaneous 95% bounds for t=25 minima: [1.36612,1.36613]e-4/[2.89886,3.24180]e-9, quantifying counting error on recorded trajectories. Later minima are exact.

Measured-query η has median≈0.243/0.213 and fifth percentile 0.0109/0.00411. These query-weighted descriptive summaries include count estimates; 95% of measured queries are at t=25, so stages are unequally represented. Typical measured splits are more balanced than the minima, but some actual splits are extremely uneven. Positive, instance-dependent η establishes neither an N,m-independent lower bound nor the general O(mlog⁡N)O(m\log N) specialization. Auxiliary parameter-volume results cannot replace ranking counts. We will add full diagnostics/counting protocol to Appendix L and clarify query-bound scope in §4.

Q2: Controlled Arena Query Savings

With original strong-background capability initialization, aligned initial predictions and common stopping, PPL uses 82.97% fewer target-user queries than controlled AMPLe (descriptive paired-user 95% CI [73.1159, 87.5390]%). Completed replay: 44 users×5 folds×10 seeds (2,200 runs/method). We retain features, query pools and method-specific acquisition/inference, aligning analytic uniform predictions and first-MH initial means. Checks run at q=0 and after each response. Runs stop when no unresolved pair has an available vote (certification/inference or missing/exhausted pair-specific votes); ranking correctness is not guaranteed. No run is budget-censored.

Table R2. Original full-background Arena: mean actual queries/run (total over 2,200 runs); final strict user-macro PairAcc.

SettingPPL queriesAMPLe queriesPPL PairAccAMPLe PairAccReduction
Native pipelines0.7091 (1,560)64.8000 (142,560)76.4266%76.4496%98.91%
Historical common-stop audit; numerical initialization differs0.7091 (1,560)4.1627 (9,158)76.4266%76.4496%82.97%
New aligned initialization + common stopping0.7091 (1,560)4.1627 (9,158)76.4266%76.4496%82.97%
Shared zero-target-query baseline0076.4496%76.4496%—

The shared zero-query baseline's 76.4496% matches AMPLe's final accuracy and slightly exceeds PPL's 76.4266%. Final PPL–AMPLe difference: −0.0230 percentage points (paired 95% CI [−0.0599, 0.0000]). This cost gap establishes neither personalization accuracy gains nor quality equivalence. 98.91% is for native pipelines; 82.97% is for strong-background initialization with common stopping. PairAcc is final, not AULC; intervals are descriptive on previously used development data.

Paired logs show unchanged query sequences/stops: alignment preserves ranking order, and saved posterior means agree after non-tied feedback. We will qualify the Abstract, Introduction and §6.3 accordingly.

Q3: Preference Robustness and Historical Reuse

Fixed-target historical reuse reduces paid queries by 82.6%/82.7% on ZDT1/DTLZ2, with close final quality means. Entries (means over 10 paired seeds) are persistent PPL/an ablation clearing historical comparisons at each consultation; lower quality metrics are better.

ProblemMean Euclidean distanceD(S)D(S)Actual queries
ZDT10.0887/0.08860.1375/0.137559.9/344.0
DTLZ20.1792/0.17830.2319/0.230374.7/432.2

Without an equivalence test, close means do not establish statistical equivalence.

We extended end-to-end NSGA-II experiments to quartic, bimodal, abrupt and gradual preferences. For bimodal DTLZ2, retaining history reduces mean paid queries (278.8→28.4) but increases final population mean true loss (0.0253→0.0811). Thus, fewer queries can accompany worse preference quality.

Under a strong abrupt DTLZ2 change, resetting preference state and reopening consultation after external notification improves mean final D(S)D(S) (0.5298→0.1563), while mean paid queries rise (73.8→199.3). The notice supplies no target coordinates or preference answers. This evaluates externally signaled adaptation with extra feedback, not automatic detection or history clearing alone.

Appendix M will give full protocols, metric definitions and nonlinear/bimodal/changing-preference results; §6.2 will summarize quality–query trade-offs.

Thank you for the detailed rebuttal and additional experiments. The new results clarify the method's limitations.

The theoretical query bound remains conditional, with extremely small splitting factors observed in practice. Although PPL achieves substantial query savings under controlled settings, the zero-query initialization already provides comparable accuracy. More importantly, the bimodal experiments show that fewer queries can lead to worse optimization quality, highlighting the limitations of the fixed aspiration-point assumption.

I appreciate the authors' efforts, but my main concerns remain. I therefore maintain my rating.

AuthorsOpenReview ↗

Response to Reviewer 6id9

Thank you for considering the additional evidence.

We agree that the extremely small observed splitting factors limit the practical informativeness of the conditional bound, and that the bimodal results demonstrate a meaningful limitation. We would like to clarify two points about the empirical contribution.

  1. Historical reuse provides a measurable benefit under stable, model-compatible preferences. Compared with clearing history at each consultation, retaining history reduces mean paid queries from 344.0 to 59.9 on ZDT1 and from 432.2 to 74.7 on DTLZ2, which are approximately 83% in both cases. Final mean D(S)D(S) is unchanged at 0.1375 on ZDT1 and is 0.2319 versus 0.2303 on DTLZ2 (persistent versus reset; ten paired seeds; lower is better). These are close observed means, not a claim of statistical equivalence. This ablation directly tests the benefit of retaining earlier comparisons.

  2. The zero-query finding depends on the initialization setting. Under strong initialization, we agree that query savings do not establish personalization gains. With 29 background votes, however, the shared zero-query pairwise accuracy is 63.08%; PPL reaches 65.94%, compared with 64.42% for controlled AMPLe, using 5.73 versus 6.50 queries under the same eight-query cap. These exploratory results, obtained on 44 users previously used for development, show an incremental benefit in the weakest tested initialization setting.

The bimodal failures limit applicability and should remain explicit. Our claim is therefore restricted to reducing repeated elicitation under the studied preference model. Could you please clarify whether your remaining concern is primarily the restricted preference class, or whether you also find the evidence for the benefit of historical reuse within that setting insufficient?

Reviewer_RgiiOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

PPL reuses historical preference constraints across evolving candidate populations, combining linear-programming certification and transitive inference to reduce queries in interactive multi-objective optimization.

Critical strengths

The method addresses a practical problem through an interpretable inference mechanism with conditional correctness guarantees. Multiple optimizer integrations, diverse benchmarks, and component ablations provide useful empirical support.

Critical weaknesses
  1. The fixed aspiration-point model restricts preference expressiveness, while the query bound requires a splitting assumption not guaranteed by the algorithm.
  2. Strong initialization limits the generalizability of the reported 98.9% query reduction.
  3. Predominantly simulated interactions and query-count metrics leave real-world user burden and advantages over agent-based approaches unclear.
Questions for authors
  1. How can PPL detect and adapt to contextual or changing preferences, and how would it compare with natural-language agents or agent–PPL hybrids under matched interaction costs?
  2. Does the actual query policy satisfy the splitting assumption required by the theoretical bound?
  3. How do query savings and ranking quality change under weaker initialization?
1 comment
AuthorsOpenReview ↗

Additional Experiments and Theoretical Clarifications on Preference Changes, Query Complexity, and Weak Initialization

Q1: changing preferences and Agent comparison

The current method has no automatic mechanism for detecting preference changes or contextual shifts. Under a strong abrupt change on DTLZ2, clearing historical preference state and reopening consultation after an external notification reduces mean final D(S)D(S) from 0.5298 to 0.1563, while mean actual paid queries increase from 73.8 to 199.3 (ten paired seeds). Thus, quality after a target change can improve with additional feedback. This experiment does not evaluate automatic detection or isolate the effect of clearing history from renewed consultation and additional feedback.

We also ran an exploratory three-seed comparison of PPL, a language agent, and their hybrid in synthetic housing selection; observed performance depended on the scenario and information condition, with no method best across all tested conditions (see the supplementary agent study). All three receive the same agent-selected comparisons within each trajectory, so the study evaluates selection under shared feedback; it does not compare independent query policies or total interaction costs.

Q2:explanation of assumption

The splitting condition in Assumption 4.3 is an additional assumption on the issued queries, rather than a guarantee of the median-selection rule, as already noted in Sec. 4 and Appendix D.1. The rule balances insertion positions, which need not balance the number of feasible rankings; Appendix D.1 provides a counterexample.

Under Assumption 4.1 (realizable preferences and no ties), completion in HARD mode returns the true full ranking without requiring the splitting assumption. Separately, under Assumptions 4.1 and 4.3, Theorem 4.4 gives an expected per-consultation query bound of O(mlog⁡N/η)O(m\log N/\eta). Its O(mlog⁡N)O(m\log N) specialization requires a positive lower bound on η independent of N,m. The unconditional bound is Q≤min⁡{B,AN}Q\le\min\{B,A_N\}.

The experiments used the same median-selection rule. We measured η_q=min(S_plus,S_minus)/S_before on the issued queries; Assumption 4.3 at a given η requires every paid query to satisfy η_q≥η:

ProblemCounted queriesZero splitsMinimum η_q†
ZDT14150~1.37e-04†
DTLZ26290~3.07e-09†

These cover ten trajectories/problem at t=25/100/175/225; 254 other queries remain uncounted. No-query η=NA. † combines exact counts and count sampling, with simultaneous 95% counting bounds [1.36612,1.36613]e-4 / [2.89886,3.24180]e-9 (ZDT1/DTLZ2).

The evaluated queries exhibit positive, instance-dependent splitting. This finite test establishes neither Assumption 4.3 almost surely over insertion orders nor a lower bound independent of N,m. We will revise the abstract and Sec.4.

Q3: results of weak initialization

Under weaker initialization, absolute ranking accuracy falls, while target-user feedback provides a clearer incremental gain at the weakest tested level. Comparing 10% with 0.1% background data, PPL’s query savings relative to controlled AMPLe narrow from 38.99% to 11.84% under the same eight-query cap; savings do not change monotonically across all five levels.

With 29 background votes, the shared zero-query accuracy is 63.08%; PPL reaches 65.94% and controlled AMPLe 64.42%, using 5.73 vs. 6.50 queries per fold. PPL gains 2.86 percentage points over zero queries (descriptive 95% CI [1.90, 3.89]) and exceeds AMPLe by 1.52 points [0.82, 2.25].

At the other four levels, the PPL–AMPLe accuracy-difference intervals all include zero. These are exploratory results on 44 users previously used for development, with paired-user bootstrap intervals and no multiple-comparison correction. Some runs remain unresolved at eight queries, so savings describe within-cap costs.

Table R1. Reduced-background results: strict user-macro PairAcc and actual queries per fold.

Background votesShared zero-query accuracyPPL accuracyAMPLe accuracyPPL actual queries/foldAMPLe actual queries/foldQuery reduction within cap
29 (0.1%)63.0780%65.9392%64.4241%5.72886.498511.84%
146 (0.5%)70.2553%70.3543%70.3740%3.97275.650029.69%
292 (1%)73.4871%74.1280%73.6476%3.95915.772731.42%
876 (3%)75.6639%75.9962%75.8113%2.91214.010627.39%
2,921 (10%)75.8491%76.0655%76.0348%2.17883.571238.99%

Table R1 setup: All five prespecified levels; five folds and three paired seeds. Background votes exclude the target user; BT capabilities are fitted separately at each level. Both methods share the exact uniform initial prediction, aligned first-MH initial mean and certification stopping checker.

Reviewer_oBivOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces PPL, a persistent preference inference framework for preference-based evolutionary multi-objective optimization (PBEMO). PPL uses linear programming to infer pairwise comparisons over evolving candidate populations, leveraging historical queries by representing pairwise feedback as halfspace constraints over an aspiration-point region. Under a realizable aspiration-point model and an informative-query assumption, the paper establishes an expected O(mlog⁡N)\mathcal{O}(m \log N) upper bound on explicit queries required by PPL to infer a preference-aligned ranking over a candidate set. The authors instantiate PPL in three representative EMO frameworks, and the empirical results on the tested tasks show that PPL improves preference alignment under matched query budgets and can substantially reduce explicit queries while maintaining comparable ranking quality.

Critical strengths
  • The persistent preference inference framework is clearly designed: pairwise feedback from historical populations is translated into linear halfspace constraints, which can be leveraged for preference inference in later populations, thereby reducing explicit feedback queries.
  • The LP-based certification provides guaranteed-correct comparisons under the assumptions.
Critical weaknesses

The algorithm’s theoretical query efficiency, i.e., the upper bound, is built upon strong assumptions, especially the conditional η\eta-splitting assumption.

Questions for authors

Under which preference structures does the LP-based certification become unreliable? For example, how does PPL behave when the decision maker’s preferences are multimodal?

2 comments
AuthorsOpenReview ↗

Reliability under multimodal preferences

Under the tested bimodal preferences, we observe incorrect direct LP inferences even with noiseless feedback. On shared feasible batches of 32 candidates, ZDT1 / DTLZ2 direct LP error rates are 0.00% / 0.00% for the fixed-reference-point control and 30.18% / 28.67% for the bimodal condition. These are equal-weight means over ten paired seeds; each run's denominator contains only comparisons with strict true preferences decided directly by the LP throughout that run, excluding transitive inferences and explicit queries.

The bimodal loss is min⁡{∥f−c1∥22,∥f−c2∥22}\min\{\|f-c_1\|_2^2,\|f-c_2\|_2^2\}, with two distinct preferred centers. In separate end-to-end DTLZ2 experiments, retaining history reduces mean paid queries from 278.8 to 28.4 relative to the no-history ablation, while increasing the final population's mean true loss from 0.0253 to 0.0811 (ten paired seeds; lower loss is better). Fewer queries can therefore accompany worse preference quality.

The certification guarantee assumes preferences realizable by a fixed reference-point model; bimodal preferences can violate this premise. We withdraw Appendix M's utility-form-independent claim: success with a linear oracle does not establish reliability for arbitrary utilities. Zero errors in the fixed control are finite observations; this bimodal case does not cover all multimodal preferences.

Thank you for the additional experiments. The bimodal preferences results answer my question directly and clarify the method’s scope: when the preferences cannot be realized by a fixed reference point, the LP-based certification becomes unreliable. Overall, I find the solution interesting and verifiable within the assumed scope. However, the assumption on the preference structure also limits its applicability.

Comments on the paper

1 comment

Dear Reviewers,

We are nearing the end of the discussion phase. If you haven't already done so, please read the authors' responses, reply to acknowledge their feedback, and indicate whether your initial concerns have been addressed (along with any score adjustments, if warranted).

Thank you for your dedicated efforts and valuable insights!

Best,

Your AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.