Sample, Predict, then Proceed: Self-Verification Sampling for Tool Use of LLMs

We thank the reviewer for recognising both the importance and the practical value of our work. We also appreciate the thoughtful suggestions and questions that will help us further improve the paper. Our point‑by‑point responses follow.

---

1. From single-step, single-turn to multi-step, multi-turn (common reply)

We appreciate the reviewer’s acknowledgement that single‑turn interactions are a reasonable starting point. We agree that multi-turn and multi-step tool-use is certainly attractive. However, we believe that proving and understanding the effectiveness of single-turn is a necessary prerequisite for extending the proposed method. Therefore, we chose to maintain a clean setup to deeply understand the capability of LLMs to model the single-step environments.

• Multi-turn: Modelling a multi‑turn conversation requires an LLM to represent not only the environment but also the users. This dual modelling problem is almost unexplored, so isolating environment modelling first allows clearer insight.

• Multi-step: Multi‑step interactions arise when an LLM must perform several successive actions in response to a single user prompt. Because these tasks decompose into a sequence of single steps, a firm grasp of the single‑step setting is essential. In the meantime, extending our method to multi-step settings requires an abstract, not exact, state representation. During long-horizon planning, overly specific or slightly incorrect details in a predicted state can actually hinder the model, thus predicting the state type might be enough. In fact, we believe that humans act the same way: when we plan a long-horizon task, we picture a coarse pipeline rather than every concrete intermediate results. How to build such abstract/coarse representations for LLMs is still a largely unexplored challenge. Moreover, multi‑step scenarios also introduce orthogonal methods such as ReAct, Reflexion, Self‑Refine, and Tree of Thoughts. Given our limited time and resources, we focused on a narrower scope that still provides actionable insights for the community.

• Planned updates: We will expand Section 5 with a discussion of current limitations and outline future works on multi‑turn, multi‑step extensions to address the reviewer’s concerns more fully.

---

2. Objective of Section 4.2

Thanks for pointing this out. We just realised that the definition of $z$ in Section 3.1 is a bit misleading, and we’ll update the text to fix the problem.

Let’s first review the representation of $z$ in our setup. As we stated in line 179 and Appendix A.2, a $z$ is constituted by (i) the special pass/error token, and (ii) the exact result message returned from the tool engines. This aligns with the definition of environment in RL framework, i.e. a joint distribution over states and rewards conditioned on a given pair of state and action.

The first experiment is aimed to evaluate how accurately the models predict subsequent states. We considered several alternatives. For example, we could require an exact string match between the predicted state and the ground truth. However, this approach is inappropriate for successful tool calls, particularly in the executable category, because the ground truth results come from live Python functions or REST calls can vary over time. In effect, we would be measuring hallucination on outputs. As stated in the above reply about multi-step setup, measuring the state prediction capability requires an abstract state representation which is unexplored so far within LLM community.

We therefore returned to the role of the internal environment model within SVS. Because SVS ultimately relies on binary rewards, we framed the evaluation as a binary classification task. This setup also reveals how much the generation ability of an LLM can improve by leveraging its discrimination capability.

We hope this clarifies the objective of the experiments in Section 4.2.

---

3. Minor issues

Thank you for collecting these detailed comments. Each will help us raise the overall quality of the paper.

• Line 105: The original sentence was unclear due to several typos. New text: "Note that certain prompts require no tool-use in categories designed to measure hallucination."

• Line 136: We'll add more details about the reward function we adapted from the BFCL work. Briefly, the scores are always binary. For the executable category, a score of $1$ is given only if running the model’s tool call yields exactly the same result as running the ground truth call. For all other categories, a score of $1$ is given only if the model’s tool call is identical to the ground truth call. In those cases, whether parameter order matters depends on the fine-grained category. Further information can be found in the original BFCL blog post.

• Line 139: Thank you for the suggestion. We've corrected it to more rigorous expression. Your proposal is clearer; indeed the objective is “minimising the additive loss of the two objectives.”

• Line 184: We ensured that user questions in the validation set never appear in the training set. Tools in the validation set may appear, but only paired with different user questions. This design allows the models to learn tool dynamics rather than memorise specific prompts.

• Line 305: Line 305 and Figure 5 address test‑time compute rather than training. They show the effect of increasing the number of generated candidates. We'll put the results of comparing the refuse rates over categories at $k=1$ and $k=64$ into appendix. We hope these results will shed light on model's refusal behaviour.

Please let us know if any further clarification would be helpful.

Thank you for further engagement in the discussion. We feel that it would be helpful to further clarify the following two issues: (i) what we mean by “user modelling” in this work, and (ii) why our setup is a legitimate RL problem in one-step MDP (a.k.a. contextual MAB), thus not an analogy, along with evidence from existing works.

---

I. User modelling in our setting

Appendix A.1 gives Example 1, which shows how we organise multiple turns into a single token sequence and clarifies the boundary between the user and the system. The sequence begins with a system preamble, followed by a human user prompt. The system then calls the LLM to produce a completion. If the completion is a tool call, the system executes the call internally rather than returning it to the user.

In this paper, a “user” is a human interacting with our system, thus by no means an LLM. “User modelling” in our previous reply therefore means modelling how human users would react to the final system output. Note that an LLM completion is not necessarily a final output, because the next turn may be an internal interaction between the LLM and the tool engine.

---

II. Formulate our setup as RL

We would like to clarify that our setting is a valid one-step MDP rather than an analogy. A precise formulation is as follows.:

1. Sample an initial state $s_0\sim\mu$, where $\mu$ is an unknown distribution over initial states induced by human users outside the system. In our notation, $s_0$ corresponds to the rendered user prompt $x$;

2. The policy LLM produces an action $y\sim\pi_\theta(\cdot|x)$. Heret $y$ is a complete response not a single token;

3. The environment returns a subsequent state and a reward, i.e. $z=(r,s_1)\sim\mathcal{E}(x,y)$. The environment function here can be decomposed into a transition function $s_1\sim p(\cdot|x,y)$ and a binary reward function $r(x,y)\in\\{0,1\\}$;

4. For every pair $(x,y)$, the state $s_1$ is terminal.

If we ignore the variability among terminal states, this reduces to a contextual bandit. A contextual bandit is a special case of an MDP in which the process terminates immediately after one action. This view aligns with the RLHF work. Specifically, Ouyang et al. [1] describe their method as RLHF in a bandit environment (Section 3.4). More detailed discussion about token-level actions versus response-level actions appears in Sections 2.1 and 2.2 of the RLOO paper [2].

In the last, we feel necessary to clarify that our method is not model-based RL. Model-based RL trains the policy by interacting with an internal environment model. However, in our experiments, the policy LLM is trained by interacting with the oracle environment. So, policy learning in our work is model-free. This is why we used “planning algorithms from the RL community” in line 368.

We hope these clarifications further specify the scope and positioning of our contribution. In addition, we will revise Section 3.1 to present a clearer formulation of our method within the RL framework.

[1] Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., ... & Lowe, R. (2022). Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35, 27730-27744.

[2] Ahmadian, A., Cremer, C., Gallé, M., Fadaee, M., Kreutzer, J., Pietquin, O., ... & Hooker, S. (2024). Back to basics: Revisiting reinforce style optimization for learning from human feedback in llms. arXiv preprint arXiv:2402.14740.

Thanks to the authors for the clarifications. Sorry for the misunderstanding of "user" - your response clears it up. I agree that considering the human user's reactions and responses is a very challenging problem and is well out of scope.

To clarify on my own end, my understanding is that there are sometimes cases when a single human user's request would require multiple tool use invocations. Suppose a human user wants their LLM agent to plan travel accommodations. This would perhaps require (1) tool use to book flights, then (2) using the results of step 1 to book lodging that is compatible with the time constraints of the flight, and so forth. So here, a policy that is invoking different tool use calls will have to also model the results of these calls so that they can be used in future steps. I believe this is what you mean by "Note that an LLM completion is not necessarily a final output, because the next turn may be an internal interaction between the LLM and the tool engine."

I appreciate the precision of the contextual MAB formulation you've presented here. Can you include this somewhere in section 3 (probably 3.1)?

Model-based RL trains the policy by interacting with an internal environment model. However, in our experiments, the policy LLM is trained by interacting with the oracle environment. So, policy learning in our work is model-free.

So I'm a bit confused here - model-based RL indeed learns an internal environment model (and a policy, although the policy is often just following a learned value function), but it of course interacts with the ground-truth environment in order to learn an accurate representation of the internal environment model. The LLM is trained by interacting with the ground-truth environment, which is what I assume you mean by "the oracle environment", but it is trained to model the oracle environment, no? I agree that the lines between model-free and model-based blur a bit here, because the internal environment model is not explicitly used to conduct a policy. But the "environment's dynamics", so to speak, are indeed being learned, if I understand the core contribution correctly.

Sorry for being a bit pedantic here - it's not my intention to be a stickler and I do still think the paper is worthy of acceptance. But I think the impact of the paper can be strengthened by making sure the technical precision is as sharp as possible so that future readers can build off the foundation when extending the work (such as to multi-step interactions.)

Thank you for further engaging in the discussion. We are glad our previous responses have helped move the discussion forward. We have also observed a gap between the NLP and conventional RL communities, and we believe a tutorial on RL for LLMs from a conventional RL perspective would benefit the broader community. We respond to your points below.

---

1. One-step MDP setup

Your interpretation of the travel planning example is very well aligned with our intent. We will incorporate a brief one-step MDP formulation into Section 3.1 and provide a more formal treatment in an appendix that states assumptions and notation explicitly.

---

2. Our Method vs Model-based RL

We agree that the boundary between model-free and model-based methods can blur. Our aim is to be precise about how our approach uses the learned world model.

Model-based RL typically improves the policy using simulated experience from an internal environment model, for example through rollouts, planning, or value learning on trajectories predicted by the model. A representative example could be the Dreamer V3 paper [1]. In its Section 2.2 “Critic learning”, the policy networks “learn behaviours purely from abstract trajectories of representations predicted by the world model.” In addition, Section 8.1 of Sutton’s book also describes the core idea of model based RL as updating the policy with “simulated experience.”

On the other hand, while our LLM learns an internal environment model, the policy induced by the same LLM is trained only on transitions from the ground-truth environment. As illustrated in our Section 3.2, the policy is never updated using samples generated by the internal model and is not improved via simulated rollouts. The internal model is used only for one-step planning during inference time, while policy learning remains model-free.

We hope this clarifies the distinction between our method and model-based RL.

[1] Hafner, D., Pasukonis, J., Ba, J., & Lillicrap, T. (2023). Mastering diverse domains through world models. arXiv preprint arXiv:2301.04104.

We thank the reviewer for recognizing both the novelty of our method and the convincingness of our experiments.

---

1. Application of the proposed in other scenarios

Thank you for highlighting the need to discuss future directions. We are eager to apply our approach to more general tasks, since we believe it can serve as a versatile component of LLM post training. We will further elaborate on potential future work regarding the broader application of our method in the Discussion section.

---

2. Training more LLMs

Because our resources were limited, we focused on analysing the method in depth so that the NeurIPS community would gain clear insights and solid evidence. Rather than exploring more models, we provided a comprehensive analysis of one. Given the simplicity of our approach, we look forward to seeing other LLM teams integrate it into their post training pipelines.

---

3. Figures 1 and 2

We have redesigned Figures 1 and 2 to improve clarity and readability. We'll update the paper to include them once the revision portal becomes available.

---

4. Minor issues

Thank you for drawing attention to these details.

• Line 35: We will revise the sentence to make the meaning clearer.
• Hyphens: We will review the entire manuscript and ensure consistent usage.
• Type in line 209: thank you for reading our paper so carefully. We'll update the paper to correct this typo.
• Figure 3&4&5: All three figures have been updated. We'll update the paper once the revision portal becomes available.
• Appendix: We will run a full spell check and put an extended discussion section.

Please let us know if any additional clarification would be helpful.

Thank you for engaging positively with our work.

Regarding future extensions, we initially considered an autonomous coding agent built on our method. We soon realised that, for resource-rich languages such as Python and Java, the abundance of existing examples would require an impractically massive dataset to show a clear improvement. A more promising direction is to apply our technique to low-resource languages like Fortran or COBOL, where each new data point can yield significant gains.

We are also experimenting with training an internal world model on Android emulators. As noted in our common reply, this setting demands abstract state representations. To achieve this, we must ablate raw API outputs from the state descriptions, which is a challenge that remains underexplored.

Beyond these software domains, our method could benefit self-driving vehicles. A textual world model might improve motion prediction of surrounding traffic participants, which offers as a solution of interpretability for self-driving models. The EMMA: End-to-End Multimodal Model for Autonomous Driving paper has explored multimodal models for driving, yet translating those ideas into a language-based world model offers fertile ground for research.

Similarly, robots could use a textual world model for high-level planning. Humans perform mental simulations of complex, long-horizon tasks before acting; equipping robots with this capability would enhance planning over intricate sequences. However, achieving this will depend on abstracting away low-level dynamics to capture only the essential high-level state transitions.

We thank the reviewer for noting both the novelty and the strong empirical performance of our work. We address your concerns point by point.

---

1. Benchmark insufficiency

The core of the problem is the experiment setup or benchmark itself, BFCLv2. This benchmark only contains an evaluation of single-step function calls, i.e., given an instruction and a set of function definitions, the task is to generate single or parallel function calls in one go. In other words, it does not involve any agent-environment interaction, which is necessary for a canonical definition of an environment.

First, BFCL has become a standard benchmark for agentic and tool‑use tasks, as shown by recent technical reports from Llama 3 (Section 5.2.7), Qwen 3 (Section 4.6), Command‑A (Section 4.2), and Gemini‑1.5 (Section 6.1.5).

Next, we show how our experimental setup meets the canonical definition of an environment within RL, in two steps: (i) a multi‑armed bandit is already recognised as a legitimate environment; (ii) our setting is strictly richer than a bandit, and therefore qualifies as an environment as well.

i. Bandit as environment: Section 1.1 of Bandit Algorithms calls a bandit problem “a sequential game between a learner and an environment,” where the environment merely “reveals a reward” for a given action. The preamble to Part I of Reinforcement Learning: An Introduction likewise states that bandit problems correspond to the special case with a single state (“for the special case of the reinforcement learning problem in which there is only a single state, called bandit problems.”). Both sources regard a bandit as the simplest possible environment.

ii. Why our setup is richer: A bandit has only one state, whereas our setting contains many. As defined in line 107, we treat the entire prompt x as an input state, combining the available tool list with the user request. Even for the same request, the tool set may change, so the input state varies. The resulted states vary as well. Because our setup generalises the bandit by allowing a nontrivial state space, it fits properly within the RL notion of an environment.

Fun fact: we asked several leading LLMs including ChatGPT, Grok, Claude, and Gemini whether a bandit counts as an environment, and they all answered yes, describing it as a trivial one.

---

2. The single‑turn, single‑step setup (common reply)

We agree that multi-turn and multi-step tool-use is certainly attractive. However, we believe that proving and understanding the effectiveness of single-turn is a necessary prerequisite for extending the proposed method. Therefore, we chose to maintain a clean setup to deeply understand the capability of LLMs to model the single-step environments.

• Multi-turn: Modelling a multi‑turn conversation requires an LLM to represent not only the environment but also the users. This dual modelling problem is almost unexplored, so isolating environment modelling first allows clearer insight.

• Multi-step: Multi‑step interactions arise when an LLM must perform several successive actions in response to a single user prompt. Because these tasks decompose into a sequence of single steps, a firm grasp of the single‑step setting is essential. In the meantime, extending our method to multi-step settings requires an abstract, not exact, state representation. During long-horizon planning, overly specific or slightly incorrect details in a predicted state can actually hinder the model, thus predicting the state type might be enough. In fact, we believe that humans act the same way: when we plan a long-horizon task, we picture a coarse pipeline rather than every concrete intermediate results. How to build such abstract/coarse representations for LLMs is still a largely unexplored challenge. Moreover, multi‑step scenarios also introduce orthogonal methods such as ReAct, Reflexion, Self‑Refine, and Tree of Thoughts. Given our limited time and resources, we focused on a narrower scope that still provides actionable insights for the community.

• Planned updates: We will expand Section 5 with a discussion of current limitations and outline future works on multi‑turn, multi‑step extensions to address the reviewer’s concerns more fully.

---

2. Executable functions

Table 1 shows that we cover the “Exec” category, which includes real‑time Python execution and real‑time REST API calls. For the exact data composition, please see the original BFCL-V1 and BFCL-V2 blog posts. As you noted, "a small portion that involved executable APIs was recently removed", which actually confirms that our dataset does contain executable functions.

---

3. Evaluation function v.s. environment function

We are not certain what is meant by “evaluation function” and “previous efforts” in this context. Could you specify how you define these terms? A precise definition of “evaluation function” and “environment function” would greatly help our communication.

As further support, Ouyang et al. [1] explicitly describe their approach as RL in a “bandit environment,” a framing that has been widely accepted and adopted by the community.

[1] Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., ... & Lowe, R. (2022). Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35, 27730-27744.

We thank the reviewers for highlighting the soundness, originality, and especially the scalability of our work, which makes it a natural fit for modern LLM development. Our point‑by‑point responses are as follows.

---

1. Applying the proposed method in more complex environments

Thanks for asking this question. We'd like to start from the key element of modern LLMs' success: scaling! Over the past three years the community has systematically scaled up: (i) the volume of training data, (ii) the number of parameters, and (iii) test‑time computes. Future work will surely introduce new axes, but these three already illustrate why our method scales well.

i. Data: Production systems continuously accumulate run‑logs. As argued in the paper, these logs form a valuable training corpus for an LLM’s internal world model. In a complex environment, we believe our method would still keep effective, as it benefits from the accumulated run-log data which the environment keeps generating. In complex environments, producing annotated/synthesised gold trajectories for supervised learning grows increasingly difficult. By contrast, our approach can benefit from failed trials to refine internal world models, a capability that constitutes one of its key advantages.

ii. Model size: An 8 B‑parameter model trained with our approach already achieves a strong success rate. It’s predictable that larger models can be expected to perform even better. Resource limits prevented us from training a bigger model for this study, yet virtually every domain has shown a clear benefit from parameter scaling, and our method is fully compatible with it. We’re happy to put discussion about model scaling as part of future work in Section 5.

iii. Test‑time computes: Our SVS method is exactly designed to increase test‑time computes, so the method is inherently aligned with this scaling axis.

To sum up from the above, we believe that more data, larger models, and more test‑time computes all reinforce the effectiveness of our approach in high‑complexity environments.

---

2. From single-step, single-turn to multi-step, multi-turn (common reply)

We appreciate the reviewer’s acknowledgement that single‑turn interactions are a reasonable starting point. We agree that multi-turn and multi-step tool-use is certainly attractive. However, we believe that proving and understanding the effectiveness of single-turn is a necessary prerequisite for extending the proposed method. Therefore, we chose to maintain a clean setup to deeply understand the capability of LLMs to model the single-step environments.

• Multi-turn: Modelling a multi‑turn conversation requires an LLM to represent not only the environment but also the users. This dual modelling problem is almost unexplored, so isolating environment modelling first allows clearer insight.

• Multi-step: Multi‑step interactions arise when an LLM must perform several successive actions in response to a single user prompt. Because these tasks decompose into a sequence of single steps, a firm grasp of the single‑step setting is essential. In the meantime, extending our method to multi-step settings requires an abstract, not exact, state representation. During long-horizon planning, overly specific or slightly incorrect details in a predicted state can actually hinder the model, thus predicting the state type might be enough. In fact, we believe that humans act the same way: when we plan a long-horizon task, we picture a coarse pipeline rather than every concrete intermediate results. How to build such abstract/coarse representations for LLMs is still a largely unexplored challenge. Moreover, multi‑step scenarios also introduce orthogonal methods such as ReAct, Reflexion, Self‑Refine, and Tree of Thoughts. Given our limited time and resources, we focused on a narrower scope that still provides actionable insights for the community.

• Planned updates: We will expand Section 5 with a discussion of current limitations and outline future works on multi‑turn, multi‑step extensions to address the reviewer’s concerns more fully.