acceptodds
Under review as a conference paper at ICLR 2027

Rewards for budget-aware multi-turn agents that dynamically adapt to arbitrary test-time constraints

Abstract

Large language model agents may be given an inference budget and asked to maximise success within it. Budget-aware training has largely focused on controlling the cost of a single model generation at a single budget setting. However, multi-turn agents face a different problem, as a shared budget must be allocated across multiple environment interactions. This allocation is often managed by an external harness, adding inference-time complexity while leaving open whether the agent itself can learn to manage its own resources. We ask whether agents can be trained to reason about user-specified budgets and adapt when and how much they spend to maximise task success within them.We adapt existing length penalties to the multi-turn setting, propose new alternatives, and systematically study which objectives best teach agents to manage their resources effectively. We train Qwen3.5 models at 4B and 9B on AppWorld with budgets over tokens, API calls, and environment interactions, and evaluate generalisation to unseen budgets, to distribution shift, and to a second agentic benchmark. Training substantially improves both within-budget success and budget compliance over untrained models, and a single policy generalises this behaviour zero-shot to budgets, shifted distributions, and environments it never trained on, adjusting how much it spends to both the stated budget and the difficulty of the task. Simple gating, which withholds reward past the budget without pricing overspend magnitude, is highly competitive, suggesting that precise reward-shaping is not required for controlling overspend severity. Budgeting across multi-turn interactions can therefore be learned by the policy itself, without the external harnesses, predictors, or routers that prior approaches rely on.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Budgeting, agents, post-training

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_J3AJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies budget-aware RL training for multi-turn LLM agents. The authors compare different reward functions to improve task success and budget compliance under dynamically specified resource constraints. Experiments show generalization to unseen budgets and out-of-domain tasks, with simple gating rewards achieving competitive performance.

Critical strengths
  1. Important and practical problem. Budget-aware training for multi-turn agents is an important and practical problem that remains relatively underexplored compared to single-turn reasoning efficiency.
  2. Systematic comparison of reward designs. The paper provides a comprehensive evaluation of different reward objectives, with the finding that simple gating can achieve competitive performance being particularly interesting.
Critical weaknesses
  1. Lack of a stronger RL baseline. The improvements over the base model may partly come from general RL fine-tuning on AppWorld rather than budget-aware training. A standard RL baseline without budget penalties would help isolate the contribution.
  2. Limited generalization to arbitrary constraints. Separate policies are trained for each resource type, and only a limited range of unseen budgets is evaluated, weakening the claim of generalization to arbitrary test-time constraints.
  3. Weak budget adaptation for API calls. Figure 3(a) shows that API-call usage changes little across different budgets, suggesting that the model may learn a relatively fixed tool-use strategy rather than dynamically adapting to the given budget.
  4. Presentation needs improvement. The notation in Section 3.1 is confusing and difficult to follow. A clearer and more consistent presentation would improve readability.
Questions for authors

See Weaknesses

3 comments

Thank you for recognising the practical importance of the paper and the value of our reward comparisons. Your comments have been very useful in strengthening the paper, and we have added experiments and improved the presentation to address your concerns.

W1: Standard RL baseline. We have added GRPO-Std, trained with the same setup as our budget-aware objectives, but rewarding task success regardless of budget compliance. While GRPO-Std improves over Base, the strongest budget-aware objectives achieve substantially higher within-budget utility and natural compliance, particularly at tighter budgets (revised Fig. 3). This demonstrates the additional benefit of budget-aware training over standard RL post-training, addressing the important distinction you raised between budget-aware learning and general improvements in task-solving ability from simply being exposed to the environment.

W2: Generalisation. We would like to clarify that our existing experiments already demonstrate both interpolation and extrapolation to budgets above and below those seen during training (revised Fig. 3). Our existing evaluations on AppWorld test-challenge and ASTRA provide further evidence under distribution shift, with harder tasks requiring more steps and a different task and tool domain with very different budget ranges, respectively. We have now added GRPO-Std comparisons to both evaluations, showing that the stronger budget-aware objectives retain higher within-budget utility and natural compliance than Base and standard RL training, even under these shifts, at these unseen budgets (revised Fig. 5).

We have also trained and evaluated on BabyAI, adding a fourth budget setting—turn budgets—in a different environment from the API-based tasks in AppWorld and ASTRA, where agents must balance batching navigation moves against the risk of mistakes. We observe similar benefits from budget-aware training over standard RL at both model scales (revised Fig. 3), further strengthening our evidence for generalisation.

Finally, our focus is on establishing whether agents can learn to manage dynamically specified budgets for different resources, which was not clear a priori, particularly for token budgets, and comparing which rewards best teach this behaviour. Training a single policy across resource types is an interesting and important extension that our framework could accommodate by conditioning on the resource type. However, this introduces further choices about which resources to train on, whether to specify one budget at a time or impose multiple constraints simultaneously, and how to sample budgets effectively during training. These choices depend on the downstream application, and learning to budget across multiple resource types could require significantly more training and compute. Given the scope of our experiments and space constraints, we believe this deserves a more thorough investigation than we can provide here. We thank the reviewer for this valuable suggestion and have highlighted it as an important direction for future work. We have also clarifed the scope of our claims in the final title of the paper which is now changed to ``Rewards for budget-aware multi-turn agents that adapt to dynamically specified budgets’’’ to reflect this.

W3: API-call adaptation. It is correct that Fig. 4(a) shows that API-call spending varies more strongly with task difficulty than with the stated budget. However, the same figure also shows that step and token spending increase with the permitted budget, even within each difficulty group. One possible explanation is that API calls are less flexible to budget, since tasks may require a minimum number of API interactions depending on their difficulty, whereas token and step usage can be reduced more flexibly through concise reasoning or batching. Regardless, budget-aware training still achieves higher within-budget utility and natural compliance than both Base and the newly added GRPO-Std baseline under API-call constraints (revised Fig. 3), demonstrating meaningful benefits over standard RL training even when API-call spending is less responsive to the stated budget.

W4: Presentation. We have addressed your concerns about Section 3.1 by revising and simplifying the mathematical notation and presentation of the framework. In addition, we have improved the notation table in Appendix A and added a new diagram of the budget-augmented POMDP (Fig. 2), providing an easy at-a-glance overview of how the agent interacts with the environment and receives budget feedback. We would be very happy to clarify anything else that remains unclear.

We thank the reviewer again for their constructive comments. We hope the new GRPO-Std comparisons and BabyAI experiments address the main concerns about budget-aware learning and generalisation, while the additional analysis and presentation changes help clarify our methodology and results. We are very happy to respond to any comments.

AuthorsOpenReview ↗

Follow-up on new baselines and generalisation results

Thank you again for your constructive feedback. Your comments have been very helpful in strengthening the paper, and we've made significant additions and revisions in response your feedback.

In particular, your concern about distinguishing budget-aware learning from general RL improvements was important, and we've now addressed this directly with the new standard RL baseline (revised Fig. 3). The results provide stronger evidence for the benefits of budget-aware training, particularly under tighter budgets. We've also added BabyAI experiments and further out-of-distribution comparisons (revised Figs. 3 and 5) which include the new standard RL baseline in this context, improved the mathematical presentation, and clarified the scope of our claims.

We hope these additions help address your main reservations, and we'd be very interested to hear whether they have changed your assessment of the paper. We are very happy to clarify any remaining concerns and greatly appreciate your time and consideration in the review process.

AuthorsOpenReview ↗

Follow-up as the reviewer–author discussion period comes to a close

We appreciate the time you've taken to review our paper and for your helpful comments. As the reviewer–author discussion period draws to a close, we wanted to share a brief update with you. Following a suggestion from Reviewer txUo, we've now highlighted the revisions, additions, and new experiments in red throughout the updated manuscript on OpenReview to make them easier to locate and assess. Hopefully this makes checking our additions based on your suggestions easier now.

In particular, in response to your comments, we've added a standard RL baseline demonstrating the benefits of budget-aware training beyond general RL fine-tuning, particularly under tighter budgets (Fig. 3). We've strengthened the generalisation evidence with new BabyAI experiments introducing a different budgeted resource (turn budgets) and further out-of-distribution comparisons (Figs. 3 and 5). We've also expanded the analysis of API-call budgeting, showing improved within-budget utility and compliance over standard RL GRPO training despite API spending being somewhat less responsive to the stated budget and more closely tied to task difficulty, and discussing why this may be the case (Figs. 3, 4, and Section 4.1). Finally, we've simplified the notation and presentation in Section 3.1 and added a new diagram (Fig. 2) to provide a clearer overview of our setup.

We hope these additions help address the concerns in your initial assessment. We'd greatly value your updated thoughts on the paper and would be very happy to clarify any remaining points. Thank you once again for your time and consideration.

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

The paper studies how to train a single multi-turn LLM agent to maximise task success under a user-specified, episode-level budget, where the total and remaining budget are written into the agent's observations. The setting is formalised as a budget-augmented POMDP, and the authors compare six cost-conditioned rewards: Trunc, Gate, Gate-Neg, Linear-Mag (DAPO's overlong penalty generalised to a normalised cost), Rate (a per-budget Lagrangian price on the overspend rate) and Dual (Rate + Linear-Mag). Qwen3.5-4B and 9B are trained with GRPO on AppWorld under step, token and API-call budgets, and evaluated on AppWorld test-normal, test-challenge and ASTRA (the last two with step budgets only). The main findings are that training improves budget utility and compliance over the untrained model, that a single policy generalises to unseen budgets and to distribution shift, and that simply withholding reward past the budget (Gate) is competitive with explicit magnitude shaping.

Critical strengths
  • Allocating a shared budget across turns and across resource types, inside the policy rather than in an external harness, is a practical and under-studied problem. The observation that a simple gate is competitive with magnitude-shaped penalties is useful for practitioners.
  • I definitely appreciate the theory section. The per-budget chance constraint with importance-weighted prices (App. D.3) and the group-advantage decomposition (Eq. 24) give a clear account of what each penalty term contributes to the gradient.
  • Systematic experiments with detailed behavioural analysis presented in the experiments with in-domain, distribution-shift (test-challenge) and out-of-domain (ASTRA) evaluation and generalisation to budgets between and beyond the training grid is shown directly (Fig 2). Further, spend split by task difficulty (Fig. 3a), overspend magnitude (Fig. 3b) and success against spend (Fig. 4) show that policies are not simply learning to spend less.
  • Well written paper that is easy to follow with appropriate visualizations.
Critical weaknesses
  • I definitely appreciate the theory section, but it has unfortunately been shoved to the appendix. The main text ends on page 8, so there appears to be room for a condensed version, including Eq. 24, which is the most informative piece.
  • The experiments seem moderately exhaustive, but I would still like to see more datasets. All training is on AppWorld, and out-of-domain transfer is tested only with step budgets on ASTRA (App. G). Since a central contribution is the ranking of objectives, it is important to check that the ranking holds when training on a second domain, not only when evaluating on one. Token and API-call transfer out of domain, and a second model family, would also strengthen the claims.
  • A key missing baseline is GRPO on AppWorld with the binary task reward and no budget in the prompt or reward, evaluated with the same budget prompts and truncation. A policy trained at a single budget, and an inference-time harness (e.g. the budget tracker of Liu et al., 2025b) on top of Base or the trained policy, would further support the motivation that the policy can replace external machinery.
Questions for authors
  • Could one policy be trained over a mixture of cost units, with the unit stated in the prompt? This seems like the natural test of adapting to arbitrary constraints. The title and the abstract's claim that the policy adjusts its spend to the stated budget should be qualified accordingly.
1 comment

Thank you for your encouraging and constructive feedback. Your suggestions have been useful in strengthening the paper, and we have expanded our experiments and analysis in response to your comments, which we address below.

W1: Theoretical presentation. Given the space constraints, we have summarised the key theoretical insight from eq 24 in the main text, highlighting how they motivate reward objectives such as Dual, with clearer references to the full derivations in the appendix. This should make the theory more accessible to the reader.

W2: Additional environments and reward comparisons. In response to your suggestion, we have now trained and evaluated our reward objectives on BabyAI at both model scales, a text-based gridworld substantially different from AppWorld's API-based tasks. Here, agents have a turn budget and can batch multiple navigation moves without intermediate observations. An invalid move causes the entire batch to fail while still consuming the turn, requiring agents to balance efficient batching against the risk of mistakes. We observe similar benefits from budget-aware training (revised Fig. 3), with Gate-Neg again achieving the strongest natural compliance, consistent with our AppWorld findings. We now compare reward objectives across eight settings spanning AppWorld and BabyAI (revised Table 2). This allows us to assess the reward objectives after training in a second environment, rather than relying only on zero-shot transfer.

W3: Standard RL baseline and external controllers. We have added GRPO-Std, trained with the same budget prompts and RL setup as our budget-aware objectives, but rewarding task success irrespective of budget compliance. The strongest budget-aware objectives achieve substantially higher within-budget utility and natural compliance than GRPO-Std, particularly at tighter budgets (revised Fig. 3). This provides stronger evidence that the improvements come from budget-aware rewards rather than simply additional RL training. While GRPO-Std differs from the suggested baseline by retaining the same budget prompts and environment setup as our budget-aware methods, its reward depends only on task success, regardless of whether this occurs within budget. Together with the poor budget compliance of Base despite receiving budget feedback at test time, these results suggest that budget prompting alone, without budget-aware training objectives, is insufficient for effective budget-aware behaviour.

We also believe that more sophisticated inference-time controllers could complement budget-aware training. Investigating how best to combine these approaches would be an interesting direction, but would require additional experimental comparisons and a more detailed evaluation than we can provide here, given the additional experiments we have now included, such as BabyAI and the expanded reward comparisons. We thank the reviewer for this suggestion and have highlighted it as an important direction for future work in the final manuscript.

Q: Mixture of cost units. Our focus is on establishing whether agents can learn to manage dynamically specified budgets for different resources, which was not clear a priori, particularly for token budgets, and comparing which rewards best teach this behaviour. Training a single policy across resource types is an interesting and important extension that our framework could accommodate by conditioning on the resource type. However, training a single policy across resource types raises additional choices about how to sample and balance different budgets during training. Imposing multiple resource constraints simultaneously would introduce further design choices that depend on the downstream application. Our current focus is on establishing budget adaptation within each resource type, leaving joint training across resources as an interesting direction for future work. We have also clarified the scope of our claims in the abstract and final title which has been changed to ``Rewards for budget-aware multi-turn agents that adapt to dynamically specified budgets’’’ to reflect this.

We thank the reviewer again for their constructive comments. We hope the additional experiments, baselines, and clarifications address your concerns and strengthen the paper. We would welcome any further questions or comments.

Reviewer_txUoOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether an LLM agent can learn to maximise task success within a user-specified budget over a multi-turn interaction, where the budget is given in one of three units (steps, tool calls, or tokens). Building on the standard POMDP formulation, the authors formally define a budget-augmented POMDP, a budget-conditioned policy, and cost-conditioned rewards, and compare a range of reward designs for training a single policy across multiple budgets. The main finding was interesting that even relatively simple reward objectives remain highly competitive.

Critical strengths

[S1] Interesting problem setting that is important in real-world scenarios.

Controlling inference cost is a long-term concern when deploying LLM agents in practice. In this regard, formulating the problem by augmenting the POMDP, the policy, and the reward with budget terms seems to be a valuable contribution.

[S2] Comparison of multiple reward objectives & Interesting empirical findings.

Comparing various reward designs helps understanding the performance and limitations of each. The finding that simple gating-based rewards remain competitive was valuable and well aligned with the paper’s focus.

Critical weaknesses

[W1] Limited novelty.

I think the positioning of this paper is ambiguous. It is hard to regard it as a framework paper, since apart from a few new objectives (e.g., Gate, Rate, and Dual), the work mainly compares reward designs, which makes it unclear what is newly built. At the same time, as an analysis paper, it lacks sufficient insight. To support the authors’ claim that LLMs become aware of the budget, I believe the paper should at least provide an analysis of internal representations or a more detailed behavior analysis. Currently, the paper mainly shows that budget-aware training is possible and that it generalizes, while the existing analyses (Figure 3 and Table 1) remain at an aggregate level.

[W2] Missing standard RL baseline.

All trained methods use budget-aware rewards, and the only reference point is the Base model, which has not been trained on AppWorld (as the authors note in Section 4.1). Without a conventional RL baseline trained only on task success, it is difficult to tell how much of the improvement in budget utility comes from budget awareness rather than from improved task-solving ability on AppWorld.

[W3] Limited generalization evaluation.

Although the paper emphasizes generalization as a contribution, the out-of-distribution evaluations (AppWorld test-challenge and ASTRA) only report results under step budgets. Since step-budget utility is likely to increase naturally as task performance improves, this issue is also connected to the lack of a standard RL baseline (W2). I wonder whether the generalization also holds for the other budget types.

Questions for authors

[Q1] When successful within-budget trajectories are rare, how does Gate provide sufficient learning signal compared to magnitude-based reward shaping?

5 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/2)

Thank you for your feedback and comments, which have been very useful for strengthening the paper further. We have expanded the experiments and analysis to carefully address each of your concerns and have added these to our revised draft that has now been uploaded. We have split our response into two comments to address all of your comments thoroughly while staying within the comment length limit and without missing anything out.

W2: Standard RL baseline. We agree this is an important baseline for separating budget-aware learning from general improvements in task-solving ability. We have therefore added GRPO-Std, trained with the same setup as our budget-aware objectives, but rewarding task success irrespective of budget compliance (normal GRPO for task success only post-training). While GRPO-Std improves over Base, the strongest budget-aware objectives achieve substantially higher within-budget utility and natural compliance, particularly at tighter budgets (revised Fig. 3). This demonstrates the additional benefit of budget-aware training objectives over standard RL post-training.

W1: Novelty, contributions and behavioural analysis. We first want to emphasise that we believe our work makes two complementary contributions: (1) A framework for training multi-turn agents to internalise resource allocation and budgeting, without external inference-time routers or controllers; (2) A systematic investigation of which reward objectives best teach this behaviour. To our knowledge, neither has been systematically studied in this multi-turn, dynamically budgeted setting, and we believe both would provide useful guidance for the community. We have revised the introduction to clarify these contributions and reorganised the results section with clearer takeaways and further analysis of the trade-offs between reward objectives, alongside the additional behavioural evidence below.

  • Reward comparisons. Frontier models use different, often ad hoc penalties for going over inference budgets, but which work best for multi-turn agents remains unclear. We have expanded our comparison with Linear-Cost, adapted from DeepSeek-V4.1-Flash, to investigate the effect of penalising spending from the start, alongside the existing DAPO and Kimi K3 (Gate-Neg) objectives. We also introduce Sigmoid and Sigmoid-Gate to investigate smooth cost penalties and nonlinear overspend penalties, respectively. This allows reward choices often made separately across papers to be compared under the same training setup. We have also added win-rate and regret statistics to compare the methods more systematically (revised Table 2). These show that Sigmoid-Gate wins most often, Dual has the lowest mean regret, Gate-Neg achieves strong natural compliance, and simple Gate remains generally competitive, while DAPO-style Linear-Mag performs considerably worse. These differences are also consistent with the reward formulations: Gate-Neg strongly discourages any overspending, while Dual combines penalties for violation frequency and magnitude (Section 3.3). We believe these comparisons provide useful guidance for the community about which method to use and when and have highlighted these findings more clearly in the updated text.

  • Behavioural evidence. Revised Fig. 4(a) shows that policies trained with budget-aware rewards adjust their step and token spending in response to both the stated budget and task difficulty, particularly for harder tasks, whereas the newly added GRPO-Std baseline spends relatively uniformly across budgets. Our analysis of overspend magnitude (revised Fig. 4(b)) also shows that Gate and Gate-Neg generally have comparatively small overruns despite not explicitly penalising their magnitude. Under a tight step budget (B=10), Gate also batches 1.93 API calls per turn versus 1.02 for GRPO-Std (Table 1). We have added example trajectories showing explicit budget planning and action batching (Appendix G.5). Together, these results provide further evidence that budget-aware training teaches agents to adapt their strategies to the stated budget, rather than simply reducing resource use.

AuthorsOpenReview ↗

Official Comment by Authors (2/2)

W3: Generalisation. Our existing zero-shot evaluation on ASTRA already provides evidence that budget-aware behaviour transfers to a different task and tool domain. To strengthen this, we have additionally trained and evaluated on BabyAI, which introduces a different environment and budgeting setting. Agents have a turn budget and can batch multiple navigation moves into one turn without intermediate observations. An invalid move causes the entire batch to fail while still consuming the turn, requiring agents to balance efficient batching against the risk of mistakes and the need for further observations. We observe similar benefits from budget-aware training at both model scales (revised Fig. 3). The new GRPO-Std comparisons on ASTRA and AppWorld test-challenge also show that these gains persist beyond standard RL training under zero-shot distribution shift (revised Fig. 6, step budgets).

Q1. Gate's learning signal. An important difference is the strength of the learning signal at the budget boundary. Gate assigns rewards of 1 and 0 to successful trajectories just within and just over budget, whereas magnitude penalties such as Linear-Mag give very similar rewards in these cases. Under GRPO, this can give Gate a much stronger contrast between task attempts within the same group, which may help to explain its strong compliance despite having a sparser reward. Gate provides no signal when all rewards are zero, but as we train across a range of budgets, within-budget successes are more common at larger budgets and still contribute to training the same policy. We thank the reviewer for raising this point and have made this explanation clearer in the results section.

Thank you again for these constructive suggestions, which have helped us strengthen the experimental evidence and clarify our contributions. We hope the revisions and additional experiments address your concerns and welcome any followups if there are any.

AuthorsOpenReview ↗

Follow-up on additional experiments and behavioural analysis

Thank you again for your thoughtful and constructive comments on our paper. Your feedback has been particularly valuable in strengthening the work, adding substantial additional experiments, analysis, and making the positioning of our contributions clearer.

In particular, we've expanded our reward comparisons to include penalties used by frontier models (including DeepSeek-V4.1-Flash) and new variants of our own (Sigmoid and Sigmoid-Gated), alongside further analysis of which objectives work best and why (revised Table 2). We've also added detailed behavioural evidence of budget adaptation (revised Fig. 4, Table 1, and Appendix G.5), a standard RL baseline and new BabyAI experiments (revised Fig. 3), and further out-of-distribution comparisons (revised Fig. 5).

We hope these additions help address your main comments, particularly regarding the contributions and insights of the work. We'd be very interested to hear whether they've changed your assessment of the paper, and would be happy to clarify any remaining concerns. We greatly appreciate your time and consideration in helping to review our paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.