acceptodds
Under review as a conference paper at ICLR 2027

When LLMs Answer with Ranges: Sample-Optimal Selection under Interval-Valued Responses

Abstract

Large language models (LLMs) are increasingly used as stochastic simulators to support selection from large sets of candidate designs and products. In many applications with high uncertainty, LLMs are more likely to return a numerical interval rather than a scalar. Motivated by the potentially vast number of candidates, we study large-scale selection under interval-valued responses. The objective is lexicographic: maximize the expected midpoint and, among alternatives that tie on midpoint, minimize the expected radius. We introduce nterval-esponse nterlaced election (IRIS) with two greedy algorithms. F-IRIS uses a ixed midpoint tolerance as an oracle benchmark; A-IRIS replaces it with an daptive candidate set. Theoretically, we prove that F-IRIS and A-IRIS are both sample optimal, that is, a budget linear in the number of alternatives achieves a positive probability of correct selection. By choosing larger finite initialization and budget coefficients, both methods can achieve any pre-specified accuracy. Experiments with Gaussian, uniform, and skewed midpoint noise support the asymptotic results. A study based on repeated Llama queries shows when interval information improves over midpoint-only selection.

Primary area:
optimization
Keywords:
LLMs, Best Arm Identification, Ranking & Selection, Interval Data, Simulation Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_67tCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies a ranking and selection problem. Each of the candidates will output an interval, the paper aim to identify those candidates with the largest expected median of output intervals. If expected medians are tied, pick the one with the smallest expected interval length.

Critical strengths

I think that, for the problem formulated in this paper, the authors provide a solution along with some theoretical guarantees. The distributional assumptions are also relatively weak, and there is a fairly clear correspondence between the algorithmic mechanisms and the proofs.

Critical weaknesses

1.I think the motivation behind the problem formulation is really weak. When does an LLM actually output an interval? Personally, I have not seen this in practice.

  1. The ranking criterion also seems somewhat strange. Have these intervals been calibrated? On what basis should we compare their midpoints first and then their lengths? What is the rationale behind this criterion? Suppose an interval is extremely wide, but its midpoint is only slightly higher than that of another, much narrower interval. Would we really want to select the wider one? I do not quite understand this choice, and I do not think it is well justified in the paper.

  2. I feel that this paper has very little to do with LLMs. The LLM framing feels like a gimmick and is really a distraction.

Questions for authors

Could the authors further justify their ranking criterion? In particular, what is the rationale for comparing the midpoints first and then the interval lengths?

4 comments

Thank you for your reviews and comments. The comments identify three questions that our motivation should answer more clearly: whether interval responses occur in practice, why midpoint and radius should be ordered this way, and what role LLMs play in the contribution. We address them in the order of the comments, combining Critical Weakness 2 and the corresponding Question for Authors.

1. Do LLMs actually return intervals?

We hope to answer this question through both prior literature and empirical evidence. We find the work Using LLMs for Market Research by Brand, Israeli, and Ngwe has reported that asking GPT for maximum willingness to pay can produce an explanatory answer or a price range, whereas explicitly requesting a single price leads to a point response. This observation suggests that the response format depends on how the question is posed: when no particular format is specified, a model may express its valuation as a range.

In our original laptop-screening experiment, 53.68%-63.00% of valid responses are nondegenerate intervals (please see the table below). Each configuration contributes 4,000 valid responses under a prompt that permits both formats and favors ranges when multiple prices seem plausible. We have added these results to Appendix D.1.

Table 1. Range occurrence under the original prompt.

Number of configurations (KK)Valid responsesInterval proportion
36144,00053.68%
3601,440,00056.03%
1,0804,320,00058.19%
3,24012,960,00063.00%

Note that the original prompt required either a price or a range output and expressed a preference for a range when several prices were plausible. To check whether the restriction was necessary for intervals to appear, we conducted an additional experiment with a neutral question without any output format restriction:

Neutral Prompt: The customer is asked: What is the maximum price you would be willing to pay for [laptop configuration]?

This additional experiment contains the attributes of the candidate laptop in our main paper. We neither request an interval nor require a scalar answer, thus LLMs output in a text format with numbers. Using Llama-3.2-3B-Instruct, we collected 200 responses per configuration across four design spaces, for 943,200 responses in total. The results are shown in Table 2.

Table 2. Range occurrence under the neutral prompt.

Number of configurations (KK)Total responsesResponses containing a price range
367,20080.72%
36072,00082.89%
1,080216,00081.80%
3,240648,00081.92%

Even under a neutral prompt that does not request an interval, 80.72%-82.89% of responses contain at least one explicit price range across the four settings. Thus, price ranges occur frequently in this task without explicit instructions to provide them. For a concrete example, one complete response in the K=360K=360 experiment was:

The specs sound quite good. For a mid-to-high-end laptop with those specs, I would say my maximum price would be around $900-$1000.

Thus, an explicit request for a range is not necessary for an LLM to produce a WTP interval in this setting. The original prompt avoids text responses and thus simplifies the numeric analysis.

In conclusion, through both literature and experiments, we find the response format depends on the prompt and in our WTP problem the interval output is possible, which motivates our study.

2. Why compare midpoint first and radius second?

We agree that two distinct arguments are needed: why width carries useful information, and why a decision maker would give midpoint priority. Neither follows automatically from the other. Also, our primary quantity is the expected midpoint, not the median of a response distribution.

The intervals are LLM responses, not calibrated uncertainty intervals. In our motivating example, they are reported price ranges, not 95% confidence or prediction intervals. Our reason for retaining width comes from research on valuation ranges. Wang et al. (Journal of Marketing Research, 2007) used willingness-to-pay (WTP) intervals to represent uncertainty about consumers' preferences and product knowledge. Maier et al. (Marketing Letters, 2015) found that consumers who were more certain reported narrower WTP ranges. These studies suggest that both the price level and the precision of a reported valuation can be useful. When LLMs are used to simulate consumer responses, their price ranges may similarly express uncertainty about valuations. A single price can also be treated as an interval with zero width, expressing certainty to some extent. Thus we retain interval width in our selection problem. (To make this motivation more clear, we also revise the introduction in our main paper.)

The priority reflects a screening preference, not a rule for all interval data. A decision maker may first seek the highest expected valuation and then prefer narrower responses for which responses are more precise, among alternatives with the same expected valuation. Selecting by midpoint alone ignores response width, while selecting by width alone may favor an alternative with a low valuation. Lexicographic selection follows this order directly, without choosing a weight to trade off valuation against width.

This lexicographic ordering also appears in earlier work. The interval-ordering rule reviewed by Karmakar and Bhunia (Reliable Computing, 2012) favors larger centers and, when centers are equal, smaller radii. Kohli and Jedidi (Marketing Science, 2007) studied lexicographic preference models using data on personal-computer choices. Skalse et al. (IJCAI, 2022) studied objectives with different priorities in reinforcement learning. These studies support the use of explicit priorities in decision problems. Other preferences may call for different selection rules, but adapting our algorithms to those rules would require further analysis.

Your example motivates allowing an explicit midpoint tolerance. Thank you for this example. We have extended our algorithms to allow a decision maker to specify a midpoint tolerance. The extended algorithms and their theoretical guarantees are presented in the new Appendix G. For an externally specified tolerance τ≥0\tau\ge0, the selection target is

G_\tau=\{k:\mu_k^m\ge\mu_*^m-\tau\},\ k_\tau^*=\arg\min_{k\in G_\tau}\mu_k^r.$$ Here, $\mu_k^m$ and $\mu_k^r$ are the expected midpoint and expected radius. A narrower alternative whose expected midpoint is slightly lower can now be selected, provided the loss is at most $\tau$. Setting $\tau=0$ recovers the original target in the main paper. The extension changes only the candidate-set rules. F-IRIS uses an empirical midpoint allowance $\tau+\epsilon$, and A-IRIS retains candidates satisfying $U_k+\tau\ge\max_iL_i$, where $(L_i,U_i)$ are midpoint confidence bounds. The interlaced sampling and modal recommendation remain unchanged. Setting $\tau=0$ recovers the original algorithms in the main paper. Appendix G establishes linear-budget sample optimality and prescribed-accuracy consistency under positive separation between its boundary and excluded alternatives. This extension addresses the trade-off raised in your example, that is, the decision maker can specify how much expected valuation they are willing to give up for a smaller expected radius.

3. What is the connection to LLMs?

LLMs provide an application of our methods. Our study considers how individuals and businesses can use repeated LLM responses to choose among candidate products or designs under a limited query budget. With stochastic decoding, the same query can produce different answers, so repeated queries help assess the model's response to each candidate. These answers may also contain ranges rather than single values. Our neutral-prompt experiment shows that such ranges occur even when the prompt does not explicitly request them. This motivates studying selection with stochastic interval-valued responses.

Why LLMs produce ranges, and when they are more likely to do so, remain open questions. One possible explanation is that their training data contain numerical ranges, which the models learn to generate in similar contexts. This is a possible explanation rather than a mechanism established by our study. Prompt wording also affects the form of the response, as our experiments show. Understanding how prompt design affects interval responses and subsequent selection decisions is a direction for future work.

Thank you for your response. However, my main concerns remain. The motivation for the problem and the proposed selection objective is still unclear to me. In particular, it remains unclear what these intervals actually mean. A shorter interval does not necessarily indicate a more reliable valuation, and LLMs can be very confidently wrong.

In my view, this is a fundamental concern about the paper. I do not think this concern can be resolved through a simple modification to the selection rule. While I appreciate the authors’ efforts to address my comments, I remain unconvinced and therefore maintain my original score of Weak Reject.

Reviewer_3k3XOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes an algorithm for selecting an option among K, when each query returns a range of values. The goal is to return the option whose interval has the smallest midpoint, and among options with the global minimum midpoint, choose the option with with the smallest interval radius. The paper proposes an algorithm for doing this selection, and it shows that the algorithm requires only a linear number of queries in K to achieve positive probability of selecting the true global optimum. The algorithm is validated on synthetic and real datasets.

Critical strengths
  • Understanding how to draw conclusions from range-valued responses is an interesting question
  • Empirical results suggest that the proposed algorithm is superior to prior work in terms of the studied metric
Critical weaknesses
  • Paper is not very precisely or cleanly written, making it difficult to understand the results and model
  • Not much motivation for when LLMs give range results… this could be motivated more strongly with real examples (not just hypotheticals)

Much of the paper (particularly the exposition) is quite difficult to read, with undefined or loosely-defined terms, making it difficult for the reader to understand. The abstract made very little sense to me; what does “uses a fixed-midpoint tolerance as an oracle benchmark” mean? And what does “sample optimal, that is, a budget linear in the number of alternatives achieves a positive probability of correct selection” mean? Are you saying a linear budget is a lower bound for having positive probability of correct selection? This statement doesn’t make sense without more explanation, which comes later in the paper, albeit not fully satisfactorily. Please try to make the abstract self-contained. (These sentences mostly make sense after reading the paper, but your abstract should mostly make sense before reading the paper!)

The introduction is equally confusing. What does “selects one alternative with maximum population mean” mean? What population are you referring to, and how could you possibly get a population mean from empirical queries? What does “This modal recommendation reduces unrobustness near the end of the sampling process” mean? What is a modal recommendation? You write, “F-IRIS uses a fixed tolerance smaller than the unknown population midpoint gap.” What does population midpoint gap mean? Please provide a more precise problem statement in your introduction---it is not clear where intervals are coming from, what K means exactly when you talk about it, how the budget can be used, etc. I understand the full problem formulation does not come until section 3, but right now the introduction is quite confusing.

The related work is similarly full of sentences with undefined terms.

In Section 3, I don’t understand the problem formulation. You define μkm\mu_k^m as an expectation, but it is not clear if the upper and lower bounds are even random to begin with. What are you assuming about the ranges being returned? Are you assuming they are random, coming from some distribution? (This assumption is never clearly stated, even later!) If so, what sample space are they defined over? Do they admit densities? If so, the probability of observing a tie in the empirical midpoints is zero. If you instead assume that upper and lower bounds can only be discrete, then what happens if you have a tie on the empirical midpoint and radius?

Assumption 3 says “Radii in Gm are nonnegative and integrable” What precisely do you mean here? Do you mean that the radius is an integrable random variable? (You already stated that the radius has an expectation, so there are implicit statements suggesting this, but again, it would be easier to understand the model if all assumptions are stated explicitly at the outset.

Definition 1 describes a sample optimal policy, but you never explain why this definition implies sample-optimality. It would be worth stating/showing explicitly that to get nonzero probability of success under your problem setting, the budget must grow as Ω(K)\Omega(K). Li et al show that a linear budget is sufficient for a slightly different problem, as you already state in the related work, but you don’t establish the necessity of scaling with KK, which is needed to establish that an O(K)O(K) budget is optimal.

In addition to the problem statement not being very crisply or cleanly-posed, I am also not convinced that the problem statement is a sufficiently interesting jump over the work of Li et al. The main difference in problem formulation is that the main optimum can be nonunique, but the paper assumes that the number of candidates is a fixed constant as K→∞K\to \infty, so this seems functionally similar to the setting of Li et al. I would like to understand how the proof techniques and main resultd differ… what changes?

In Algorithm 1, why do you take the smallest index (min arg min) in line 225? Are you using Assumption 1, i.e., is Alg 1 steering the solution using knowledge that the smallest radius is at index 1? If so, it seems like the algorithm is not fully general.

The paper says, “At each radius epoch, the algorithm restricts attention to the current candidate set and greedily samples the alternative with the smallest empirical mean radius, allowing an inferior radius leader caused by sampling noise to be corrected as additional observations are collected.” I didn’t quite follow why this is the right thing to do… it seems like you are only taking exploit steps when you sample based on radius, with no further “explore” steps—is that correct?

In Line 240, should the first sup and the final inf be over n≥Knen \geq Kn_e? Isn’t nen_e a small constant, and you want the probabilities to be bounded after you’ve sampled all KK candidates nen_e times?

In the empirical results, it would be interesting to see how quickly the algorithms converge to the minimum midpoint and radius separately. (Your guarantees are in terms of PCS, but it would be useful to understand tradeoffs between computation, error on minimum midpoint, and error on minimum radius among items in the minimizing set. These are all presumably quantities that a user would care about, in addition to PCS.

Questions for authors

See above

3 comments

Thank you for your review and detailed comments. We agree that some definitions and explanations were too brief. In particular, we should have made the difference between expectations and sample averages clearer and explained why a linear budget is both sufficient and necessary. We respond in the order of your original review, starting with the two points listed under Critical Weaknesses and then following the detailed comments paragraph by paragraph.

1. Critical Weaknesses, first point: overall clarity

We rewrite part of our paper to make some descriptions more clear. The replies below give explanations in the order of your comments.

2. Critical Weaknesses, second point: examples of LLM interval responses

We first count the frequency of interval-valued responses in our empirical experiment (see Table 1 below).

Table 1. Range occurrence under the original prompt.

Number of configurations (KK)Valid responsesInterval proportion
36144,00053.68%
3601,440,00056.03%
1,0804,320,00058.19%
3,24012,960,00063.00%

Our original prompt asks for either a range or a single value. This makes the responses easier to analyze, but may differ from everyday use. We therefore ran an additional experiment with a neutral willingness-to-pay (WTP) question that did not specify the answer format, allowing the model to respond freely. We queried Llama-3.2-3B-Instruct 200 times for each laptop configuration. We kept all responses without retrying based on their format, resulting in text responses with numbers.

Table 2. Range occurrence under the neutral prompt.

Number of configurations (K)Total responsesResponses containing a price range
367,20080.72%
36072,00082.89%
1,080216,00081.80%
3,240648,00081.92%

Even under a neutral prompt that does not request an interval, 80.72%-82.89% of responses contain at least one explicit price range across the four settings. Thus, price ranges occur frequently in this task without explicit instructions to provide them.

3. Abstract: oracle benchmark and sample optimality

Thank you. We agree that the abstract should be understandable before reading the main text. We have replaced "oracle benchmark" with a direct description of the gap information required by F-IRIS and explained how A-IRIS avoids this requirement. We have also clarified the definition of sample optimality and consistency.

4. Introduction: population means, recommendations, and the budget

Each alternative, such as a laptop configuration, has a response distribution under a fixed prompt and decoding setup. The population mean is the expectation under this distribution. It is unknown to the algorithm and is estimated from repeated queries. Each query returns both endpoints, so it gives both a midpoint and a radius and costs one unit of the budget BKB_K.

The modal recommendation is the alternative recommended with the highest frequency at the radius-sampling steps. It is not the mode of the response distribution. We record one recommendation at each such step and return the alternative with the largest count. If fewer than half of these recommendations are wrong, the final choice must be correct. Selecting the single alternative recommended at the last step may cause a wrong selection. Our proof bounds the total number of wrong recommendations rather than requiring the last one to be correct. We will use this explanation instead of the phrase "reduces unrobustness."

The population midpoint gap is the gap in expected midpoint between the optimal set and the remaining alternatives. We will explain these terms more carefully in the introduction before presenting the full problem formulation.

5. Related work: undefined terms

We will explain the terms before using them in comparisons. Best-arm identification aims to select an alternative with the largest expected response. Pure exploration uses queries to improve the final choice, rather than to maximize the rewards collected during sampling. Lexicographic selection gives one objective priority and uses a second objective to choose among alternatives tied on the first. We will use these explanations before introducing abbreviations.

6. Section 3: random endpoints and ties

Our objective is to maximize the expected midpoint and then minimize the expected radius among midpoint-optimal alternatives. We should have stated this more clearly.

Each query to alternative kk returns random finite endpoints (Lk,ℓ,Uk,ℓ)(L_{k,\ell},U_{k,\ell}) with Lk,ℓ≤Uk,ℓL_{k,\ell}\le U_{k,\ell}. Their joint distribution is unknown. It can be discrete, continuous, or a mixture, so a density is not required. We assume that repeated observations of each alternative are i.i.d. and that sampling sequences are independent across alternatives. The midpoint and radius within a response may be dependent.

The midpoint and radius are Mk,ℓ=(Lk,ℓ+Uk,ℓ)/2M_{k,\ell}=(L_{k,\ell}+U_{k,\ell})/2 and Rk,ℓ=(Uk,ℓ−Lk,ℓ)/2R_{k,\ell}=(U_{k,\ell}-L_{k,\ell})/2. Their population means are expectations under the response distribution. The algorithm does not know these expectations and estimates them using sample averages. One query gives both quantities and costs one unit of the budget.

The target is

k^*=\arg\min_{k\in G_m}\mathbb E[R_{k,1}].$$ We assume that the radius minimizer within $G_m$ is unique. The ties here are between expectations, not sample averages. Two alternatives can have continuous midpoint distributions with the same mean but different expected radii, even though their sample midpoint averages almost surely differ. We also develop a method in Appendix G allowing the expectations to be non-identical and have a tolerance. ## 7. Assumption 3: integrable radii Yes. For $k\in G_m$, we assume $R_{k,1}\ge0$ almost surely and $\mathbb E[|R_{k,1}|]<\infty$. For alternatives outside $G_m$, the proofs do not require a finite expected radius. Each observed radius is finite, but its expectation may be infinite. We will state this distinction explicitly. ## 8. Definition 1: why a linear budget is order-optimal We agree that we should also explain why a budget of smaller order, i.e., $B=o(K)$, cannot give the same general guarantee. Consider $K$ candidates with a best alternative $J$. Every radius is always one. The midpoint is $\gamma_1$ for alternative $J$ and zero for all others. These problems satisfy our assumptions with $K_1=1$. Since $J$ is unknown, we can view $J$ as a uniform random variable over the $K$ candidates. Suppose the noise of output is zero. Until the algorithm queries $J$, all its observations are the same. When $K$ is sufficiently large, with $B<K$ queries it can check at most $B$ distinct alternatives and then make one final guess among those it has not queried. Therefore, any adaptive algorithm, including a randomized one, satisfies $$\frac1K\sum_{j=1}^K\Pr_j(\widehat k=j)\le\frac{B+1}{K}\rightarrow 0.$$ Thus, a sublinear budget cannot keep success bounded away from zero across all possible labels of the best alternative, even without observation noise. [Hong, Jiang, and Zhong (*INFORMS Journal on Computing*, 2022)](https://doi.org/10.1287/ijoc.2022.1221) also point out that to ensure an asymptotically nonzero PCS, the total budget has to grow at least linearly in $K$. Therefore, a linear budget is sufficient under the stated assumptions. This explains the term sample optimality. ## 9. Differences from Li et al. Our work builds on the explore-first greedy approach of Li et al. and applies to a two-objective problem. The added difficulty is that we do not know which alternatives have the highest expected midpoint or how many there are. Radius matters only within this unknown set. An alternative outside the set may have a very small radius. The work of Li et al. cannot apply to our problem. Midpoint-only selection cannot use radius to distinguish alternatives with identical midpoint distributions. Radius-only selection may choose an alternative outside $G_m$. Using an estimated candidate set $\hat{G}_m$ therefore requires controlling errors in that set while comparing radii. IRIS addresses this by alternating midpoint and radius sampling and updating the candidate set throughout the run. Li's work recommends the alternative which wins in the last step, while the interlaced procedure in our work requires a modal recommendation since one single step has a probability of selecting wrong candidates. The proof bounds how many wrong radius recommendations these candidate-set errors can cause and thus is new compared with Li's work. In conclusion, the algorithms and theoretical proofs are quite different from Li et al., which composes our contribution.

10. Algorithm 1, line 225: smallest-index tie-breaking

The outer minimum in min⁡arg⁡min⁡\min\arg\min only breaks exact empirical ties, which rarely occur in numerical experiments because of sample randomness. The algorithm does not know which alternative is best. We write k∗=1k^*=1 to simplify the proof, not to give the algorithm this information. On the success event used in the proof, the best alternative has a strictly smaller empirical radius than the other members of GmG_m and receives a strict majority of the final votes. The guarantee therefore does not depend on breaking ties in favor of label 1. Any other fixed, data-independent tie-breaking rule can be used.

11. Radius epochs: why sampling is greedy

Yes. After sampling every alternative during initialization, the radius steps are greedy. Hence, the radius sampling is explored during initialization. We do not add an extra exploration step. This greedy strategy helps use less budget than sampling all candidates in the midpoint candidate set estimate G^m\hat{G}_m because G^m\hat{G}_m is dynamic in the early stage and it may contain bad candidates. Our proof uses an event on which the empirical radius means within GmG_m stay correctly separated after initialization. Under the integrability assumption, the probability of this event approaches one as the initialization size grows. The midpoint steps control errors caused by alternatives outside GmG_m.

12. Line 240: sup and inf over n>nen>n_e

We understand this may cause some confusion. By the definition in Section 3, Xˉkm(n)=n−1∑l=1nXk,lm\bar{X}_k^m(n)=n^{-1}\sum_{l=1}^nX_{k,l}^m. Here, nn counts observations of alternative kk, not total queries across all alternatives. The supremum and infimum therefore range over n≥nen\ge n_e, while the total initialization cost is KneKn_e. The supremum controls the empirical radius average of alternative 1, while the infimum controls the empirical radius average of alternatives 2,...,K12,...,K_1. Each alternative is initialized by nen_e samples. After initialization, alternatives can have different sample counts. Some may still have only nen_e observations. The event in the proof must cover all these counts, so replacing nen_e by KneKn_e would miss relevant cases. We will make the distinction between the per-alternative count and the total query count explicit.

13. Experiments: separate midpoint and radius performance

Thank you for this suggestion. We have added separate midpoint and radius loss curves in Appendix C.1 for Experiment 2 under Gaussian, uniform, and skewed Beta noise. The figures cover both K1=4K_1=4 and 88, all three values of KK, and nine query budgets, with 200 macro-replications per setting. For the final recommendation k^B\widehat k_B, we report

L_r(B)=\mathbb E[\mu_{\widehat k_B}^r-\mu_{k^*}^r\mid\widehat k_B\in G_m].$$ The midpoint loss is averaged over all runs. The radius loss is averaged only over runs that select within the true midpoint-optimal set. We omit the conditional estimate when no run selects within $G_m$ and use hollow markers when fewer than 20 runs do so. The curves show that EFG can achieve a small midpoint loss while retaining a positive radius loss. F-IRIS reduces both losses as the budget becomes sufficiently large. A-IRIS needs a larger budget to reduce midpoint loss, but its radius loss is close to zero among runs that select within $G_m$. At the largest tested budget, both IRIS methods have zero empirical loss on both objectives in every displayed setting. The same overall pattern appears under all three noise distributions.
Reviewer_wwk1OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies a fixed-budget ranking and selection (or best-arm-identification) problem with stochastic interval-valued responses. "Arms" are ordered according to the following rule: those with higher expected midpoints are better, and after that, those with lower expected radius are better. The authors propose two algorithms, F-IRIS and A-IRIS. Both alternate between two sampling steps. The first samples the arm with the highest empirical midpoint. The second samples the arm with the smallest empirical radius among a set of candidates whose midpoints are close to the best, and this set is recomputed as data accumulate. As the number of arms K grows with a proportional budget, and with fixed positive gaps and a fixed number of midpoint-optimal arms, both algorithms keep the probability of correct selection bounded away from zero (i.e., sample optimality) and can reach any target accuracy with settings that do not depend on K (i.e., consistency).

Critical strengths

The lexicographic formulation is clean and subsumes best-arm identification (BAI) as a special case. In this sense, this paper makes some technical contributions as a follow-up work. The proofs appear correct.

Critical weaknesses

The conceptual and methodological contributions appear marginal, since they look similar to Li et al.'s works.

I would not view that as a deal breaker, though. My biggest concern is that to view it as an "LLM" paper seems a bit stretch. After all, this is essentially based on a general abstract form of simulator. I do not quite see the elements specific to LLM.

Questions for authors
  1. Why propose two different algorithms with the same performance guarantee? It would be nice to give clear prescriptive guidelines of which algorithm to use, and when.

  2. What, if anything, is specific to LLMs in this paper? What is the loss of purely viewing it as an abstract ranking and selection problem?

2 comments
AuthorsOpenReview ↗

Clarifying IRIS’s contributions and when to use each algorithm

Thank you for your reviews and comments. Your comments point to three issues that we should explain more clearly: the contribution beyond Li et al., when to use each IRIS variant, and the role of LLMs. We address these below.

1. What does IRIS add to the work of Li et al.?

Our work builds on the explore-first greedy approach and boundary-crossing analysis of Li et al. Their scalar selection work studies selection by one expected response, while their virtual-screening work selects top-mm alternatives according to that response. However, complex decision tasks may concern a second objective. Our contribution is to extend this approach to a problem in which the second objective matters within an unknown set defined by the first objective. This extension is nontrivial and the challenges are as follows.

The algorithm must learn the eligible set of the first objective while selecting within it. Neither the identities nor the number of midpoint-optimal alternatives are given. A midpoint-inferior alternative may look best in radius, so radius sampling cannot simply be applied to all alternatives. Conversely, selecting any midpoint maximizer does not necessarily identify the one with the smallest expected radius. A direct two-stage use of the greedy top-mm screening and radius selection would need a way to choose the unknown set size and control errors in the first stage. Our proposed IRIS algorithms address this challenge by adding interlaced sampling and recommendation procedures.

The proof must connect these two sources of error. IRIS alternates midpoint and radius sampling while updating the midpoint candidate set. The main proof challenge is to show that errors in the candidate set do not lead to too many wrong recommendations. We control these errors within a budget proportional to KK, so the correct alternative receives a majority of the radius recommendations with the stated probability. A-IRIS extends this argument to a candidate set built from confidence bounds and is more feasible than F-IRIS. The new Appendix G also extends the target to alternatives within a user-specified midpoint tolerance.

2. Why propose two algorithms with the same guarantees, and when should each be used?

Table 1. The two algorithms require different prior information. F-IRIS uses a fixed tolerance 0<ϵ<γ10<\epsilon<\gamma_1, where γ1\gamma_1 is the gap separating the midpoint-optimal set from the remaining alternatives. A-IRIS replaces this tolerance with confidence bounds and does not require a supplied midpoint gap.

Available informationRecommended choice
A credible positive lower bound g0≤γ1g_0\le\gamma_1 is availableF-IRIS with 0<ϵ<g00<\epsilon<g_0
No credible lower bound on the midpoint gap is availableA-IRIS

We recommend A-IRIS when reliable gap information is unavailable, and F-IRIS when such information can be specified by decision makers. A-IRIS is not parameter-free since it needs to estimate the midpoint sub-Gaussian scale bound. Thus A-IRIS does not always perform better than F-IRIS, especially when γ1\gamma_1 is known. The role of A-IRIS is to remove the supplied-gap requirement while retaining linear-budget guarantees.

AuthorsOpenReview ↗

IRIS's practical connection to LLMs

3. What is the connection to LLMs, and why not view the paper as a general selection problem?

The general selection formulation is the right description of our theory. LLMs provide a concrete application in which we choose among candidate products or designs using repeated, stochastic model responses under a limited query budget. Each alternative is described in a prompt, and the decision is which alternative to query next and ultimately retain. Our contribution concerns how to use model responses for selection, rather than a change to model architecture or training.

The LLM setting motivates the observation format. A product description can lead to a price range as well as a single price, and the same prompt can produce different answers under stochastic decoding. Replacing an interval by its midpoint would discard its reported width. This behavior is also noted by Brand, Israeli, and Ngwe in Using LLMs for Market Research, whose work discusses price ranges in responses to open WTP questions.

We have added a neutral-prompt experiment to test whether interval-valued answers exist, using the question:

The customer is asked: What is the maximum price you would be willing to pay for [laptop configuration]?

Using Llama-3.2-3B-Instruct, we collected 200 first responses per configuration across the four design spaces, totaling 943,200 outputs, without requesting ranges or retrying answers because of their format. The results are shown below.

Table 2. Range occurrence under the neutral prompt.

Number of configurations (K)Total responsesResponses containing a price range
367,20080.72%
36072,00082.89%
1,080216,00081.80%
3,240648,00081.92%

Even under a neutral prompt that does not request an interval, 80.72%-82.89% of responses contain at least one explicit price range across the four settings. Thus, price ranges occur frequently in this task without explicit instructions to provide them. For example, one complete response in the K=360K=360 experiment was:

The specs sound quite good. For a mid-to-high-end laptop with those specs, I would say my maximum price would be around $900-$1000.

In conclusion, this paper can be viewed as an abstract ranking-and-selection problem, and the LLM application gives it a practical purpose. Individuals and businesses may use LLMs to compare candidate products or designs, but querying every candidate many times can be costly. Our methods decide which candidates to query again and which one to select under a limited query budget, using both the midpoint and width of the reported valuations. The new neutral-prompt experiment shows that price ranges can arise without an explicit request, motivating our study in interval-valued methods.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.