Active Task Disambiguation with LLMs

Thank you for taking the time to review our paper. Below we address the questions and concerned raised.

Example of task ambiguity in the main text. Thank you for this excellent suggestion. We agree that a small example at the beginning of the paper would help the readers grasp the key concepts discussed more easily. UPDATE: We included a concrete example of an ambiguous problem statement as a continuation of Example 1 in the context of code generation.

Figure 3 ranks. The measure of efficacy of a set of collected requirements until iteration $t$ should be the likelihood of the problem-solving agent (here an LLM) in generating the ground-truth solution $h^*$ given the set of requirements $\mathcal{R}^t$. In the context of natural language responses, this metric is non-trivial to estimate empirically due to the inherent randomness of LLM generations. In such contexts, it is standard to use the pass@k score, which indicates the accuracy of the LLM-generated responses, if it the LLM is allowed to make up to $k$ distinct guesses. If we were to evaluate only the first, most likely response generated by the model, (this is equivalent to the pass@1 metric commonly used in the code-generation contexts), only very few runs would result in a non-zero accuracy, requiring potentially far more iterations to observe statistically significant results. Instead of providing the value of the pass@k metric for an arbitrarily fixed $k$, we instead provide the ranking of a candidate solution $h^*$ in the list of 10 candidate solutions ordered from least to most likely, which we believe is an easy to interpret score and can also be used to approximate the pass@k metric. I.e. if for the given run, the rank of $h^*$ is greater than $10-k$, it would contribute positively to the computation of the pass@k metric.

IG in Eq. (2). Yes, the IG in equation (2) denotes the information gain. Thank you for noticing that this abbreviation has not been properly introduced in the text. We have now addressed this and updated the manuscript accordingly.

The meaning of c(q). We denote by $c(q)$ the cost of obtaining the oracle answer if we were to ask the question $q$. In our presentation we keep this abstract to allow for multiple interpretations depending on the specific application contexts. This cost can stand for the costs associated with obtaining an answer from the user in a text format (e.g. the expected length of their response), or the expected cost of running a computational experiment (e.g. number of FLOPs, GPU usage, etc.). In our experiments, for simplicity, we set $c(q)$ to a constant value, assuming that all candidate questions are equally difficult to answer by the oracle.

We stress that this cost, however, is not the cost of generating the question or evaluating its utility. At the point of utility estimation, all of the candidate questions must have been already generated, and the associated costs incurred. In this work, we follow the principles of Bayesian Experimental Design (Rainforth et al.), wherein the costs associated with eliciting a good questions are marginal in comparison to the costs associated with providing an answer to this question. Consequently, the goal of our framework is to find a question that maximises the expected information gain, while minimising the costs of obtaining the answer from the oracle.

UPDATE: Thank you for bringing this point to our attention. We have provided additional clarifications on the meaning of $c(q)$ in the revised version of our manuscript. Additionally, we have included a short discussion on the computaitonal costs associated with the different question-elicitation strategies discussed in this work in Appendix E of the updated manuscript.

Reference

Rainforth, Tom, Foster, Adam, Ivanova, Desi R., & Bickford Smith, Freddie. "Modern Bayesian experimental design." Statistical Science, vol. 39, no. 1, 2024, pp. 100–114. Institute of Mathematical Statistics.

We appreciate the time and effort you’ve dedicated to reviewing our paper. We hope that the our answers and proposed changes to the manuscript address your concerns satisfactorily.

Thank you again for helping us improve the quality of this work.

The authors of submission #11335

We thank the reviewer for their insightful comments and constructive feedback. Below, we address the questions and concerns raised by the reviewer.

Weaknesses

W1) More challenging benchmarks

Thank you for raising this point. We would like to highlight that the primary focus of this paper is task disambiguation, specifically addressing uncertainty about the value of the ground-truth solution $h^∗$ that arises from the inherent ambiguity of the initial problem statement $\mathcal{S}^0$, rather than from the LLMs’s skill in solving a given class of problem. This distinction is clarified in the blue box before Section 2.1 of the manuscript. Ambiguity of a problem is defined with respect to the objective indicator function $1\\{h \vdash \mathcal{R}\\}$. A high uncertainty of the solution-generating distribution, $p_{\phi_h}$ does not indicate that the initial problem statement is itself ambiguous. Uncertainty of $p_{\phi_h}$ may arise both due to problem ambiguity and the problem solving agent's lack of skill in generating the correct answer to a well-specified problem.

The benchmarks used in this paper have been carefully selected to balance the complexity of the problem-solving task with the degree of ambiguity in the problem statements, ensuring they are well-aligned with the research objectives:

• 20 questions game: While the problem-solving difficulty is intentionally low (the task is to identify an animal based on progressively refined characteristics), the ambiguity $\mathcal{S}^0$ is extremely high—any animal in the entire animal kingdom could initially be a valid solution. This setting emphasizes the core challenge of our work: resolving ambiguity through effective question generation.
• HumanEval Benchmark: The problem-solving complexity is moderate, as the benchmark predominantly consists of simple coding problems**.** At the same time, the ambiguity of these problems is significantly lower—for most problems, there exist only one of the problem statement $\mathcal{S}^0$. However, as it has been demonstrated by Liu et al., some level of impreciseness of the problem statements is still present in this benchmark, leading to a few possible interpretations for a subset of these problems. We identify some of them in the Appendix, Table 4. This makes HumanEval an appropriate benchmark for demonstrating the capabilities of our method in a domain where ambiguity and problem-solving complexity coexist.

Regarding SWE-bench, while it is true that this benchmark is highly challenging, its design focuses on problem-solving difficulty rather than the ambiguity of problem statements. The majority of issues in SWE-bench are well-documented and precise, meaning the uncertainty in solving these tasks stems primarily due to the agent’s inability to solve complex problems. Out-of-the box LLM’s fail on this benchmark for ~95% of issues. The design of a sufficiently powerful solution generator ($h_i \sim p_{\phi_h}(\cdot \vert \mathcal{S})$) for this benchmark, is outsied of the scope of our work. That said, our method is general, and given a sufficiently powerful solution generator, $h_i \sim p_{\phi_h}(\cdot \vert \mathcal{S})$, it has the potential to improve question/query/test-case generation for a variety of problem-solving scenarios.

UPDATE: To test this claim, we have conducted a new set of experiments on the more challenging coding benchmark: APPS, which contains competition-level coding problems. We have selected a subset of problems which do not contain any input-output examples in their initial problem statement to ensure a sufficient level of ambiguity is present. Further, we have filtered this subset to only those on which GPT-4o-mini does not produce a correct solution zero-shot.

Detailed results of these experiments are presented in Appendix D.2.1. Notably, the selected APPS subset has an average zero-shot accuracy of only ~35% with GPT-4o-mini, significantly lower than the ~70% on HumanEval, confirming that these problems are considerably more challenging. Despite this increased complexity, our EIG-based strategies consistently outperformed their non-EIG counterparts, with a substantial improvement of over 10 percentage points in accuracy. This demonstrates that our method remains effective even in more complex settings and underscores its robustness across varying levels of task difficulty and ambiguity. Thank you for your feedback, which enabled us to strengthen the validity and generality of our results.

Reference:

Liu, J., Xia, C., Wang, Y., & Zhang, L. (2023). Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation. https://arxiv.org/pdf/2305.01210

Thank you for your detailed and thoughtful feedback. We greatly appreciate your positive assessment of our work's quality, significance, originality, and clarity. Below, we address the weaknesses and questions you raised and clarify points that may have been unclear.

Empirical gains vs. cost. Thank you for bringing up the point on computational costs vs. empirical gains. UPDATE: To address this part, we have included a new section in the Appendix of the manuscript (Appendix E), where we provide a detailed comparison of the LLM sampling costs associated with the competing question generating strategies. Indeed, the EIG-based strategies incur a much higher costs than other approaches. However, in the context of BED (Rainforth et al.), this trade-off is often justified. Obtaining the result of an experiment (here the answer to a question) is typically assumed to incur a much higher cost than the computational effort required to select the experiment (or question) itself.

Reference:

Rainforth, Tom, Foster, Adam, Ivanova, Desi R., & Bickford Smith, Freddie. "Modern Bayesian experimental design." Statistical Science, vol. 39, no. 1, 2024, pp. 100–114. Institute of Mathematical Statistics.

Baseline clarity. Indeed, we refer to the ToT baseline as a variation of a tree-of-thought, with “trees” of depth of one, where all questions are generated by the LLM and subsequently selected based on the LLM's own judgement. We have now included the corresponding citation.

Additional references. Thank you for highlighting these references. We have incorporated them throughout the manuscript and in the Related Work section of the updated version.

Thank you again for your detailed and valuable feedback. We have made the relevant updates to our manuscript which we hope improve its overall clarity and presentation clarity.

Kind regards, The authors of submission #11335