betaFeedback

WorksComputer Science

Rewards for Budget-Aware Multi-Turn Agents That Adapt to Arbitrary Test-Time Constraints

Abstract

Large language model agents are often given an inference budget and asked to maximise success within it. A multi-turn agent has to allocate this budget across many environment interactions. An external harness can enforce the budget, but it remains unclear whether the agent itself can learn when and how much to spend. We ask whether agents can learn this allocation across dynamically specified budgets and which rewards best teach this behaviour. We adapt existing length penalties to budget constraints spanning multiple resource types, introduce new reward formulations, and compare eleven objectives in a shared training pipeline. We train Qwen3.5 models at 4B and 9B on AppWorld with budgets over tokens, API calls, and environment steps, and on the BabyAI gridworld with turn budgets. We train a separate policy for each environment and resource type, with each policy trained across budget values. Training with rewards that penalise overspending substantially improves within-budget success and natural compliance over untrained models and over training on task success alone, with agents learning to adapt their resource use to stated budgets and task difficulty. These gains extend to unseen budgets and, zero-shot, to a shifted task distribution and a new benchmark. Reward objectives trade off success within budget and natural compliance. A sigmoid penalty for overspending most often achieves the highest within-budget success at an individual budget, while a fixed negative reward for overspending generally yields the strongest natural compliance. Combining penalties for overspend frequency and magnitude gives the smallest average gap to the best method at each budget. Overall, we show that a single agent can learn to allocate resources across turns and adapt its behaviour to user-specified budgets using budget feedback without external budget-allocation controllers.

Introduction

Agents can solve harder tasks by spending more at test time, thinking for longer and taking more actions in an environment ([22, 10, 29]). Current frontier agents give users some control over the effort in terms of generated tokens, tool calls, or environment actions ([16]). To respond to different budgets, an agent needs to adapt its strategy to maximise success under the allowance it receives.

Budget-aware training has largely focused on controlling the cost of a single model generation ([2, 14, 26]). A multi-turn agent instead shares one budget across many turns, and at each turn the policy has to decide when and how much to spend given what remains ([16]). This allocation is usually left to external machinery at inference time, including planners, harnesses, or routers, and is not learned by the policy itself ([30, 16]). That machinery adds complexity at inference, and it remains unclear whether the task-performing policy can learn to allocate these resources itself. Different constraints may also call for different behaviour. This leads to our first question. Can we train a multi-turn agent to maximise task success under dynamically specified budgets, across different inference resources?

We study this through reward shaping. In single-generation tasks, length penalties are often subtracted from rewards when an agent exceeds a token limit. Overlong trajectories are still collected, and they can show how to solve a task, which helps most when successes within budget are rare. Some frontier models use linear penalties ([29, 28]), and others use step functions ([24]). Learned budget penalties draw on constrained optimisation ([3, 23]), while cost penalties have also been used to train budget-aware routers ([30]). It is not clear in advance which objectives best train a single multi-turn policy across dynamically specified budgets and different resource types. This leads to our second question. Which training objectives best teach multi-turn agents to maximise task success while complying with dynamically specified budgets?

To address these two questions, we introduce a framework for training a single policy across dynamically specified episode-level budget values, with a separate policy for each environment and resource type. The policy is told its total and remaining budget in natural language at every turn, so it can learn to allocate resources as the episode goes on. Within this framework, we adapt existing penalised objectives that punish excessive resource use or budget violations to the multi-turn, multi-budget setting and introduce new reward formulations. We then compare these objectives directly to see which ones best teach budget-aware behaviour. We train and evaluate on AppWorld ([25]), with budgets on generated tokens, environment interactions, or tool calls. We test generalisation to budgets not seen during training, distribution shift on AppWorld test-challenge, and zero-shot transfer to ASTRA ([27]). To broaden the evaluation to a different environment and task format, we also train and evaluate on BabyAI ([6]), a text-based gridworld.

Our contributions are as follows:

  • We introduce a framework for training and evaluating multi-turn agents across dynamically specified budgets and resource types, with metrics for task success within budget and natural budget compliance.

  • We adapt existing cost-conditioned objectives to the multi-turn, multi-budget setting and introduce new reward formulations, covering hard success gating, continuous cost shaping, and fixed or learned overspend penalties.

  • We show that the strongest budget-shaped objectives improve within-budget success and natural com-

pliance over untrained models and budget-independent task-reward training across token, tool-call, and environment-step budgets. On AppWorld, learned resource allocation responds to the stated budget and task difficulty and generalises to unseen budget values. Under step budgets, improvements persist on test-challenge and under zero-shot transfer to ASTRA. We also evaluate budget-aware behaviour in BabyAI.

  • We identify distinct trade-offs between budget utility, natural compliance, and overspend severity, with no single objective dominating across all criteria. Dual has the smallest average utility gap to the best method at each budget, Sigmoid-Gate most often achieves the highest utility at an individual budget, and Gate-Neg generally achieves the highest natural compliance.

Related Work

Token budgets. On-policy budget-aware training without an external harness has mostly controlled the length of a single model generation, rather than how resources are allocated across a multi-turn episode. Existing methods optimise adherence to token budgets ([2, 14, 11]) or learn levels of reasoning effort ([4]), largely in mathematical reasoning. In these settings, the model controls resource use within one generation, and tokens are the resource of interest. A multi-turn agent faces a different allocation problem: it must distribute a shared budget across successive generations and environment interactions, deciding how much to spend at each turn to maximise task success. The constrained resource may also be tool calls or environment steps, rather than just tokens.

Wen et al. [26] trains across a curriculum of token budgets and uses control tokens inserted during decoding to signal the remaining budget. DAPO (Yu et al. [29]) introduces an overspend penalty for a fixed generation-length budget. Kimi K3 (Team et al. [24]) handles several effort levels in agentic domains by training a separate expert for each with step-function reward shaping and then distilling them. We study how to train one policy across dynamically specified episode-level budget values, with separate training for each environment and resource type.

Budget feedback and allocation. Budget-aware behaviour can also be added without training it into the task-performing policy. Liu et al. [16] show that raising a search agent’s tool-call budget does not by itself improve results, while reporting the total and remaining budget to the agent can improve scaling for large models when combined with planning and verification strategies. In our evaluation, the untrained 4B and 8B models struggle to succeed within budget despite receiving total and remaining budget feedback (Figure 3). Other approaches predict how much compute a task requires (Damani et al. [8]) or route between cheaper and more expensive models under a budget (Zhang et al. [30]). Li et al. [13] search a value tree at inference time on multi-hop question answering and scale node values by the remaining resource ratio, so the search moves from exploration to exploitation as the budget runs down. These methods all handle allocation in planning, harnesses, or routers at inference time. We instead train the task-performing policy to condition its actions on the total and remaining budget, learning to allocate resources effectively across turns.

Figure 3. In-domain budget utility and compliance. Budget utility U(b)U(b) and natural compliance Comp⁡(b)\operatorname{Comp}(b) against stated budget bb for Qwen3.5-9B and 4B. Rows show AppWorld test-normal under step, token, and API-call budgets, followed by BabyAI under turn budgets. Each policy is trained for one environment and resource type. Vertical dashed lines mark training budgets, with other points unseen during training. Bands show ±1\pm1 standard deviation of the binomial rate estimates.

Constrained decision-making and budgeted MDPs. Constrained Markov decision processes (cMDPs; [3, 1]) typically bound expected cumulative cost and can be optimised using Lagrangian relaxation (Stooke et al. [23]). If the constraints are pooled across the training distribution, a policy can break tight budgets and make up for it on generous ones. Budgeted MDPs (Carrara et al. [5]) extend this to families of budgets by conditioning on the remaining budget allowance, and chance-constrained formulations ([9, 12] (Chow 2017)) bound violation probabilities directly. We carry these formulations over to multi-turn LLM agent training with a separate rate constraint for each budget, so the constrained objective treats every budget separately and does not pool compliance across budgets.

Budget-Aware Policy Optimisation

Preliminaries

We write P(Y)\mathcal{P}(\mathcal{Y}) for the set of probability measures over a set Y\mathcal{Y}, and model a task as a POMDP M=⟨S,A,T,Ω,O,R,γ,μ0⟩\mathcal{M} = \langle\mathcal{S}, \mathcal{A}, \mathcal{T}, \Omega, \mathcal{O}, R, \gamma, \mu_0 \rangle. Here S\mathcal{S}, A\mathcal{A} and Ω\Omega are the state, action and observation spaces. The transition and observation kernels are T:S×A→P(S)\mathcal{T} : \mathcal{S} \times\mathcal{A} \to\mathcal{P}(\mathcal{S}) and O:S×A→P(Ω)\mathcal{O} : \mathcal{S} \times\mathcal{A} \to\mathcal{P}(\Omega), with RR the reward, which § 3.2 specialises to a binary terminal reward, γ∈(0,1]\gamma\in(0, 1] the discount factor and μ0∈P(S)\mu_0 \in\mathcal{P}(\mathcal{S}) the initial state distribution. Tasks x∼pX∈P(X)x \sim p_{\mathcal{X}} \in\mathcal{P}(\mathcal{X}) are drawn from a distribution over the task set X\mathcal{X}. At turn tt, the agent receives the observation history ht:=(o1,a1,…,at−1,ot)h_t := (o_1, a_1, \ldots, a_{t-1}, o_t), comprising previous actions and the resulting environment observations. Writing H\mathcal{H} for the set of all such histories, the agent acts according to a policy π:X×H→P(A)\pi: \mathcal{X} \times\mathcal{H} \to\mathcal{P}(\mathcal{A}).

We optimise policies with Dr. GRPO (Liu et al., [17]), a variant of group relative policy optimisation (GRPO, Shao et al., [21]) that baselines each rollout against its group mean and removes response-length and reward-standard-deviation normalisation (Appendix § 10.6). Removing these normalisers addresses biases that can encourage failed rollouts to grow longer. The practical training pipeline is described in Appendix § 11.6.

Budget-Augmented POMDP

Budget augmentation. We augment the task POMDP M\mathcal{M} of § 3.1 by pairing the environment state sts_t with a scalar remaining budget btb_t, following the state augmentation used in budgeted MDPs (Carrara et al., [5]). This gives the budget-augmented POMDP (Figure 2) M~=⟨S~,A,T~,Ω~,O~,R,γ,μ~0⟩\widetilde{\mathcal{M}} = \langle\widetilde{\mathcal{S}}, \mathcal{A}, \widetilde{\mathcal{T}}, \widetilde{\Omega}, \widetilde{\mathcal{O}}, R, \gamma, \widetilde{\mu}_0 \rangle, with states s~t=(st,bt)\widetilde{s}_t = (s_t, b_t) and state space S~:=S×R\widetilde{\mathcal{S}} := \mathcal{S} \times\mathbb{R}. Resource use is measured by a cost map κ:S×A×S→R≥0\kappa: \mathcal{S} \times\mathcal{A} \times\mathcal{S} \to\mathbb{R}_{\ge0}. Each action is the whole string the policy emits at a turn, including thinking tokens. Its step cost is one, its token cost is its length in tokens, and its API-call cost counts the calls actually executed. These raw costs are independent of the remaining budget. We abbreviate the realised transition cost as κ(at)=κ(st,at,st+1)∈R≥0\kappa(a_t) = \kappa(s_t, a_t, s_{t+1}) \in\mathbb{R}_{\ge0}. The remaining budget informs the policy’s action selection. After each turn, we subtract the realised cost from the remaining budget:

Figure 2. Budget-augmented POMDP. The policy receives the task xx, total budget B0B_0, and remaining budget btb_t alongside the environment observation oto_t. Each action’s cost is deducted from btb_t, and the updated budget bt+1b_{t+1} is appended in natural language to the next observation (§ 3.2).

bt+1=bt−κ(at).(1)b_{t+1} = b_t - \kappa(a_t). \tag*{(1)}

The augmented transition kernel combines the unchanged environment dynamics with this budget update.

T~(st+1,bt+1∣st,bt,at)=T(st+1∣st,at) 1[bt+1=bt−κ(at)].(2)\widetilde{\mathcal{T}}(s_{t+1}, b_{t+1} \mid s_t, b_t, a_t) = \mathcal{T}(s_{t+1} \mid s_t, a_t)\,\mathbb{1}\left[b_{t+1} = b_t - \kappa(a_t)\right]. \tag*{(2)}

Budget-conditioned policy. The initial budget B0∈R>0B_0 \in\mathbb{R}_{>0} and the remaining budget btb_t are written into the text of the observations the agent sees (Appendix § 11.§ 5). At the next turn, the augmented observation is o~t+1=(ot+1,bt+1)∈Ω~:=Ω×R\widetilde{o}_{t+1} = (o_{t+1}, b_{t+1}) \in\widetilde{\Omega} := \Omega\times\mathbb{R}, where bt+1b_{t+1} is given by Equation (1). The observation kernel preserves the task observation and reveals the updated budget exactly.

O~(ot+1,b∣st+1,bt+1,at)=O(ot+1∣st+1,at) 1[b=bt+1].(3)\widetilde{\mathcal{O}}(o_{t+1}, b \mid s_{t+1}, b_{t+1}, a_t) = \mathcal{O}(o_{t+1} \mid s_{t+1}, a_t)\,\mathbb{1}\left[b = b_{t+1}\right]. \tag*{(3)}

An augmented history splits into the history hth_t of M\mathcal{M} and the observed budgets, so the budget-conditioned policy

π(⋅∣x,ht,bt,B0)∈P(A),π:X×H×R×R>0→P(A),(4)\pi(\cdot\mid x, h_t, b_t, B_0) \in\mathcal{P}(\mathcal{A}), \qquad\pi: \mathcal{X} \times\mathcal{H} \times\mathbb{R} \times\mathbb{R}_{>0} \to\mathcal{P}(\mathcal{A}), \tag*{(4)}

can weigh both the allowance left and the fraction bt/B0b_t/B_0 still available against what is needed to continue toward successfully solving a task from a given state. We write Π\Pi for the set of all such policies. Throughout post-training the budget is an explicit input to the policy. Since Equation (4) conditions directly on B0B_0 and btb_t, which are written into the environment observations, a budget outside the training grid needs no change to the policy or to inference, and § 4 shows that budget-aware behaviour carries over to such unseen budgets and to new environments zero-shot.

Episode termination. Each episode draws a task x∼pXx \sim p_X and, independently of it, a budget B0∼pBB_0 \sim p_B from the budget prior defined below, initialising the episode at b1=B0b_1 = B_0 with the opening observation o1o_1 the prompt stating the task and its budget (see Appendix § 11.§ 5 for the prompts in full). Most methods allow bt<0b_t < 0, so the agent can overspend and learn from doing so, possibly with a penalty. In AppWorld and ASTRA, a special complete_task action a⊥∈Aa_\perp\in\mathcal{A} lets the agent end the episode and has cost κ(a⊥)>0\kappa(a_\perp) > 0. An episode can also end through environment termination, as when the agent completes a BabyAI mission, or at a finite horizon Tmax⁡∈Z>0T_{\max} \in\mathbb{Z}_{>0}. Writing τenv\tau_{\mathrm{env}} for the first turn at which the environment terminates, the stopping time is τ:=min⁡(inf⁡{t≥1:at=a⊥},τenv,Tmax⁡)\tau:= \min\left(\inf\{t \ge1 : a_t = a_\perp\}, \tau_{\mathrm{env}}, T_{\max}\right), with unavailable termination conditions assigned +∞+\infty.

Reward and budget penalties. We score the completed trajectory ζ:=(o1,a1,…,oτ,aτ,oτ+1)\zeta:= (o_1, a_1, \ldots, o_\tau, a_\tau, o_{\tau+1}) by a binary task reward R(ζ)∈{0,1}R(\zeta) \in\{0,1\} and transform it into a budget-conditioned return R~(ζ,B0)∈R\widetilde{R}(\zeta, B_0) \in\mathbb{R}. The agent is trained to maximise the expected shaped return

max⁡π∈Π Ex∼pX, B0∼pB, ζ∼π(⋅∣x,B0)[R~(ζ,B0)].(5)\max_{\pi\in\Pi}\ \mathbb{E}_{x \sim p_X,\ B_0 \sim p_B,\ \zeta\sim\pi(\cdot\mid x,B_0)}\left[\widetilde{R}(\zeta,B_0)\right]. \tag*{(5)}

We do not discount, so any pressure to finish early comes from the budget and any overspending shaping or penalties. We fix a finite set of M∈Z>0M \in\mathbb{Z}_{>0} training budgets B={b(1)<⋯<b(M)}⊂R>0\mathcal{B} = \{b^{(1)} < \cdots< b^{(M)}\} \subset\mathbb{R}_{>0} and draw budgets uniformly at random during training. The raw spend C(ζ):=∑t≤τκ(at)∈R≥0C(\zeta) := \sum_{t \le\tau} \kappa(a_t) \in\mathbb{R}_{\ge0} is always the budgeted quantity, e.g. steps, tool calls, or tokens, consumed over the entire multi-step trajectory. Rewards are shaped as a function of this spend as a fraction of the prompted budget B0B_0, the normalised cost

Cˉ(ζ,B0):=C(ζ)B0=1B0∑t≤τκ(at)∈R≥0,(6)\bar{C}(\zeta,B_0) := \frac{C(\zeta)}{B_0} = \frac{1}{B_0}\sum_{t \le\tau}\kappa(a_t) \in\mathbb{R}_{\ge0}, \tag*{(6)}

with Cˉ≤1\bar{C} \le1 within budget and Cˉ>1\bar{C} > 1 over budget.

Cost-Conditioned Rewards

We compare existing reward objectives and new formulations motivated by heuristics, common practice, or constrained optimisation. We organise them into four groups: (a) hard boundary mechanisms that act at the budget limit, (b) within-budget cost pressure that penalises resource use before the limit, (c) gradual post-budget shaping that penalises the amount of overspend, and (d) learned per-budget violation prices that adapt penalties to the overspend rate at each training budget. The objectives also differ in whether overspending can produce negative returns. Figure 1 and Appendix § 8 give their mathematical definitions and further details.

Figure 1. Cost-conditioned rewards. [Left] Return GG against episode cost CC for successful (R=1R=1) and failed (R=0R=0) trajectories across different cost-conditional rewards. Shading marks C>BC > B. Bands illustrate Λb∈[0,1]\Lambda_b \in[0,1] for Rate and Dual. [Right] Reward properties: Budget Cutoff stops rollouts before exceeding BB, Budget Jump denotes a return discontinuity at BB, In-Budget Cost penalises resource use before BB, Overspend Size makes the return depend on the extent of overspending, Failure Return < 0 means failed trajectories can receive negative return, and Learned Price denotes a separate learned violation price for each training budget.

Hard boundary mechanisms. At the budget, these methods either stop the rollout or assign a fixed outcome to a violation.

  • Trunc (Liu et al., [15]) is a baseline that does not permit any overspending. Every rollout is terminated at B0B_0, and the reward is the binary task reward obtained within B0B_0.

  • Gate relaxes this constraint. The policy may overspend, but any rollout that exceeds B0B_0 receives zero reward regardless of task success. This provides a simple objective that rewards only success within budget.

  • Gate-Neg (Team et al., [24]) assigns a reward of −1-1 whenever the policy exceeds B0B_0, regardless of task success. Unlike Gate, it therefore prefers a failure within budget to a failure over budget.

Within-budget cost pressure. These methods begin penalising cost before the budget is exhausted.

  • Sigmoid smooths the hard overspend indicator that Rate and Dual apply as a step into a symmetric sigmoid penalty, which applies pressure to solve successfully within budget from the start of a policy’s rollout.

  • Linear-Cost (Xu et al., [28]) penalises cost linearly from the first action onwards, so the pressure starts well before the budget is reached.

Gradual post-budget shaping. These methods preserve the full in-budget return, then change it continuously with the amount of overspend.

  • Sigmoid-Gate subtracts a sigmoid-shaped penalty only after B0B_0. It leaves the in-budget return unchanged and continuously lowers the return of both successes and failures as overspend grows. Unlike Gate, it can assign negative returns to overspending failures.

  • Linear-Mag has no step at B0B_0 and instead reduces the reward linearly beyond it. It was popularised by DAPO (Yu et al., [29]), and we generalise it to multiple budgets in Appendix § 9.

  • Exp-Mag decays a successful trajectory’s reward exponentially in how far it overspends. Failures always receive a reward of 0, regardless of spend.

Learned per-budget violation prices. These methods learn an overspend price separately at each budget.

  • Rate tracks the overspend rate at each budget and applies a larger penalty the more often the policy exceeds that budget. We derive it from a Lagrangian perspective in Appendix § 8. Its price is capped at 1.0, so an overspending success never scores below a compliant failure.

  • Dual combines a step penalty with a linear one. A learned Lagrangian step penalty prices how often rollouts at the given budget overspend, and a linear penalty prices how much the current rollout overspends. Each term subtracts at most 0.5. We study the dual optimisation in Appendix § 10.7 and why the two penalties are complementary in Appendix § 10.§ 5.

Experiments

We first test whether a single policy can learn to adapt across dynamically specified budget values, including values unseen during training (§ 4.2). We then compare which reward objectives best teach success within budget and natural compliance (Section 4.2). Finally, we test whether the learned behaviour persists under an AppWorld task-distribution shift and transfers to ASTRA without retraining (§ 4.4).

Agents Learn to Adapt Across Dynamically Specified Budgets

Experimental setup. We train 4B and 9B Qwen3.5 models (Qwen Team, 2026) from their post-trained checkpoints (Appendix § 11.6). All trained methods use the same Dr. GRPO pipeline (Liu et al., [17]), prompts, budget grids, and seed within each setting. They differ in the training return, and Trunc additionally stops training rollouts at the budget boundary. We compare against Base, the untrained model, and GRPO-Std, which is trained with the binary task reward RR alone. Like the budget-aware methods, GRPO-Std receives budget information in its prompt during training and evaluation, but its reward is independent of the budget and its rollouts are not cut off at the budget, unlike Trunc. This baseline represents task-reward-only agent training, without a budget-dependent return.

We train and evaluate on AppWorld (Trivedi et al., [25]), an interactive coding-agent benchmark where agents complete requests by writing Python over multiple turns. We evaluate on held-out test-normal tasks, the distribution-shifted test-challenge split, and ASTRA (Xiu et al., [27]), an out-of-domain personal-assistant benchmark. We also evaluate on BabyAI (Chevalier-Boisvert et al., [6]), a text-based gridworld with tasks distinct from code generation (Appendix § 11). Across these settings, we consider budgets over steps (agent turns), tool calls (API calls), and tokens (all generated tokens, including reasoning), as defined by the cost map κ\kappa.

At each budget bb, we measure budget utility U(b)\mathcal{U}(b), the probability of solving a task within budget, and compliance Comp⁡(b)\operatorname{Comp}(b), the probability that the agent terminates within budget when rollouts are not cut off:

U(b):=Ex∼pXtest,ζ∼π(⋅∣x,b)[R(ζ)1[C‾(ζ,b)≤1]],(7)\mathcal{U}(b) := \mathbb{E}_{x \sim p_{\mathcal{X}_{\mathrm{test}}}, \zeta\sim\pi(\cdot\mid x,b)}\left[R(\zeta)\mathbf{1}\left[\overline{C}(\zeta,b) \le1\right]\right], \tag*{(7)}
Comp⁡(b):=Px∼pXtest,ζ∼π(⋅∣x,b)(C‾(ζ,b)≤1),(8)\operatorname{Comp}(b) := \mathbb{P}_{x \sim p_{\mathcal{X}_{\mathrm{test}}}, \zeta\sim\pi(\cdot\mid x,b)}\left(\overline{C}(\zeta,b) \le1\right), \tag*{(8)}

where expectations are over held-out tasks Xtest\mathcal{X}_{\mathrm{test}}. Budget utility counts a success only if the rollout finishes successfully within budget, matching the practical setting in which the agent is cut off at the budget limit. Natural compliance measures whether the rollout finishes within budget regardless of task success, without an external budget cutoff.

Agents Learn to Adapt Across Dynamically Specified Budgets

We first test our first question: whether agents can learn to succeed within dynamically specified budgets and adapt their resource use to the task and available allowance.

Budget-shaped returns improve success within budget and compliance. Figure 3 reports budget utility and natural compliance for Base, GRPO-Std, and the budget-shaped objectives across both model scales, AppWorld’s step, token, and API-call budgets, and BabyAI turn budgets. Despite receiving the same budget information as other methods, Base, the Qwen3.5 checkpoints before our additional training, show poor success within budget and compliance. At a step budget of B=36B = 36, the 9B and 4B Base models reach only 37% and 19% budget utility, respectively, while the 9B Base model complies on fewer than half of episodes across the token-budget range. GRPO-Std improves on Base through standard agent post-training, but its budget-independent return still gives weak compliance and lower budget utility than the leading budget-shaped objectives.

The stronger budget-shaped objectives improve both metrics over these baselines, although not every reward improves on GRPO-Std in every setting. Thus, before looking into differences between the reward functions (which we do in the next section), we can record that budget-shaped post-training, using budget feedback without an external budget-allocation controller, can teach a single agent to use its total and remaining budget to improve success within budget and natural compliance across dynamically specified step, token, and API-call budgets. The BabyAI results show the same overall trends under turn budgets in an environment distinct from AppWorld. At larger budgets, the utility curves of the stronger objectives often converge, indicating that these policies maintain similar task utility once the budget is no longer as binding. No method attains perfect natural compliance across every budget and setting. The objectives yield different trade-offs between success within budget and natural compliance. We compare them in Section 4.2.

Resource use varies with task difficulty and the stated budget. Figure 4(a) shows the mean spend of the 9B AppWorld policies by task difficulty. GRPO-Std spends comparatively uniformly across stated budgets, despite changing its spend with task difficulty. Across the budget-shaped policies, step and token spend generally increase with the stated budget allowance and with task difficulty, most clearly for hard tasks. Under API-call budgets, spend rises sharply with task difficulty but changes comparatively little with the stated allowance, indicating that call use is driven more strongly by task difficulty. Examples from BabyAI and AppWorld in Appendix § 15.§ 4 also show explicit budget planning and action batching in the policies’ reasoning.

Figure 4. Spend by task difficulty and overspend magnitude. AppWorld test-normal under step, token, and API-call budgets. (a) Mean spend by task difficulty for Qwen3.5-9B. (b) Mean relative overspend Eπ[Cˉ/B−1∣Cˉ>B]E_{\pi}[\bar{C}/B - 1 \mid\bar{C} > B] for Qwen3.5-9B and 4B, shown as a percentage of the budget. Horizontal axes show the stated budget BB. Overspend axes are capped at 100%.

Table 1 shows that budget-aware training helps agents use the prompt’s guidance to batch API calls (Prompt 3). All methods receive this guidance, but GRPO-Std uses around one API call per turn across budgets. In contrast, Gate, Sigmoid-Gate, and Dual use around 1.9 calls per turn at B=10B = 10, compared with around 1.5 to 1.6 at B=32B = 32. These averages include successful and failed rollouts completed within budget. The budget-aware policies batch more calls and increase batching under tighter step budgets. Together with their improved within-budget success and natural compliance, these re-

B=10B = 10B=15B = 15B=32B = 32
Base1.65 ± 0.561.45 ± 0.531.46 ± 0.40
GRPO-Std1.02 ± 0.051.03 ± 0.161.05 ± 0.17
Gate1.93 ± 0.661.73 ± 0.501.53 ± 0.39
Sigmoid-Gate1.87 ± 0.691.63 ± 0.451.53 ± 0.36
Dual1.92 ± 0.621.76 ± 0.481.61 ± 0.38

Table 1. Mean API calls per step by budget. Qwen3.5-9B, restricted to episodes completed within budget on AppWorld test-normal with step budgeting. Bold: highest per budget.

sults suggest that the policies learn to use batching as part of allocating their available steps more effectively.

Budget-aware behaviour generalises beyond the training budgets. The dashed vertical lines in Figure 3 mark the six budgets used during training. On AppWorld, the step and API-call evaluations include both interpolated budgets between these lines and extrapolated budgets outside the training grid. The stronger budget-aware policies retain improved budget utility and compliance at these unseen values.

Takeaway. With total and remaining budget feedback, agents can learn to allocate a shared budget across turns. Budget-shaped training improves success within budget and natural compliance over the base models and over task-reward-only training. Resource use and batching vary with task demands and the available budget, and the gains extend to unseen budget values on AppWorld.

Which Rewards Best Teach Budget-Aware Behaviour?

We now address our second research question by comparing how reward objectives balance success within budget and natural compliance.

Utility rankings of budget-shaped rewards. Table 2 aggregates budget utility across the eight AppWorld and BabyAI experiments. Near-best rate measures how often a method is within two percentage points of the best budget utility at each budget, while mean regret is the average gap to the best observed budget utility at each budget, measured in percentage points. Sigmoid-Gate most often attains the highest utility at an individual budget, with a 20.1% win rate. Gate has the highest near-best rate at 39.8%. Dual has the lowest observed mean regret at 2.92 percentage points, followed by Gate at 3.33, Linear-Cost at 3.75, and Sigmoid-Gate at 3.82. Thus, Sigmoid-Gate wins most often at an individual budget and Dual has the smallest observed average loss to the best method across the evaluation. Gate performs surprisingly well for a simple objective that rewards only within-budget success and adds no explicit overspend penalty.

MethodWin (%) ↑Near-best (%) ↑Regret (pp) ↓
Linear-Mag3.16.514.01
Trunc6.620.57.56
Rate3.126.07.46
Gate-Neg16.126.06.00
Exp-Mag7.822.94.32
Sigmoid14.039.24.31
Sigmoid-Gate20.136.93.82
Linear-Cost11.639.33.75
Gate12.439.83.33
Dual10.838.82.92

Table 2. Utility across budgets. Win and near-best (≤2pp) rates and mean regret against the per-budget best method, averaged equally over the eight AppWorld and BabyAI experiments (Appendix § 15.§ 1).

Allowing training rollouts beyond the budget improves pooled utility. Table 2 shows that Gate surpasses Trunc on all three pooled utility metrics, with a higher win rate and near-best rate and a lower mean regret. Gate permits an overspending rollout to finish and assigns it zero return. Tokens generated after the budget boundary remain in the rollout and contribute to training. When the same group contains a positive-return rollout, the overspending rollout receives a negative advantage, providing a learning signal on its actions, including those beyond the budget. Trunc instead ends the rollout at the budget boundary, removing these post-budget tokens from training. The comparison supports retaining overspending trajectories even when they receive no success reward. Note, however, that Trunc has a higher throughput due to not having to generate the additional over budget steps.

Penalty design affects success, compliance, and their trade-off. Gate-Neg assigns every overspent trajectory a reward of −1-1, ranking an in-budget failure above any overspent result. In Figure 3, Gate-Neg generally attains high natural compliance, but its mean regret is 6.00 percentage points, compared with 3.33 for Gate in Table 2. The strong overspend penalty may make the policy more hesitant near the budget boundary, sacrificing some success within budget to avoid a violation.

Rate alone is less competitive than Dual, with mean regrets of 7.46 and 2.92 percentage points, respectively. This is consistent with a learned price on the overspend event being more useful when combined with information about the overspend size. Linear-Cost and Sigmoid, which apply cost pressure before the budget boundary, have mean regrets of 3.75 and 4.31 percentage points, respectively. These results suggest that early pressure to finish does not necessarily improve within-budget utility.

Small overruns without magnitude penalties. Even a policy with high natural compliance can substantially overspend on the episodes where it violates the budget. We therefore also examine conditional excess spend in Figure 4(b), that is, in rollouts that do overspend, how much do they overspend in percent compared to the prompted budget. Gate and Gate-Neg generally have comparatively small conditional overruns, despite neither applying a penalty that grows with overspend magnitude. Explicit magnitude penalties are therefore not necessary to obtain comparatively small overruns in these experiments.

Raw task success generally increases with spend. This paper so far focussed on the evaluation setup where the agent is cut off at the budget in each task. We may, however, also be interested in the tradeoff between how much compute is used overall versus how many tasks are solved. Figure 5 reports pass@1 against mean spend, counting successes regardless of whether the rollout finishes within budget. At both model scales, greater spending is generally associated with higher overall success across steps, tokens, and API calls. This complements the earlier evidence of budget-responsive resource use by showing that spending differences are also accompanied by differences in overall task success.

Figure 5. Raw task success against spend. AppWorld test-normal pass@1 without a budget cutoff against mean spend for Gate, Gate-Neg, Sigmoid-Gate, and Dual. Each point corresponds to a stated budget. Policies retain budget feedback, but successes count regardless of compliance. Bands show ±1 standard deviation of the binomial rate estimates.

Takeaway. Reward objectives produce different trade-offs between success within budget and natural compliance. Dual is closest to the per-budget optimal method on average, Sigmoid-Gate most often achieves the highest within-budget success at an individual budget, and Gate-Neg generally achieves the highest natural compliance. Allowing training rollouts to continue beyond the budget can improve success within budget. The simple Gate objective, which rewards only success within budget, is often surprisingly competitive with more complex methods.

Budget-Aware Behaviour Generalises Beyond the Training Distribution

Budget-aware behaviour persists on shifted AppWorld tasks. We next test whether policies trained to condition on the budget remain responsive to it under distribution shift. Figure 6 (top) evaluates the AppWorld-trained policies on test-challenge, which includes unseen apps and more difficult tasks. As on test-normal, the stronger budget-shaped objectives generally achieve higher budget utility and natural compliance than Base and GRPO-Std at both model scales. Utility rises with the stated step budget and, for the 9B model, continues to increase beyond the largest training budget of 29. These results suggest that both the learned budgeting behaviour and the gains over budget-independent training methods extend to shifted tasks. Gate-Neg once again generally achieves the highest compliance, while utility rankings vary with the budget and model scale.

Distribution shift plots for Qwen3.5-9B and Qwen3.5-4B on AppWorld test-challenge and ASTRA

Figure 6. Distribution shift. AppWorld-trained policies evaluated without retraining on AppWorld test-challenge (top) and ASTRA (bottom) under step budgets. Curves show budget utility U(b)U(b) and natural compliance Comp⁡(b)\operatorname{Comp}(b) against stated budget bb. Bands show ±1\pm1 standard deviation of the binomial rate estimates.

Budget-aware behaviour transfers zero-shot to ASTRA. We also test zero-shot generalization to a new environment. Figure 6 (bottom) evaluates the same policies on ASTRA without retraining. As on test-challenge, the stronger budget-shaped objectives generally retain higher budget utility and natural compliance than Base and GRPO-Std. At both model scales, utility increases over tighter step budgets before flattening at looser budgets, while natural compliance also increases with the allowance. Gate-Neg remains among the most compliant methods, and several objectives achieve similar utility at looser budgets. These results suggest that budget responsiveness and the improvements over the baselines transfer to ASTRA’s distinct personal-assistant tasks and tool domain, using the same Python-REPL action interface (Appendix § 11.§ 2).

Takeaway. Budget-aware policies remain responsive to stated budgets under distribution shift and zero-shot transfer to ASTRA. Gate-Neg remains the best choice when prioritising natural budget adherence without requiring external enforcement.

Conclusion

Simply prompting an agent with an inference budget is not enough to make it adhere to that budget or succeed within it. Without consequences for overspending during training, agents frequently exceed the stated allowance. Budget-aware reward objectives provide a simple remedy, teaching a single policy to adapt its resource use across tasks and budget values. We show that this behaviour extends to unseen budgets, persists under a shifted task distribution, and transfers zero-shot to a separate environment. The choice of objective determines the resulting trade-off. Dual is most consistently close to the best method across budgets, Sigmoid-Gate most often yields the highest within-budget success, and Gate-Neg yields the strongest natural compliance. All three are competitive and require no external budget-allocation controller. We encourage practitioners to experiment with these objectives to select the balance between task success and natural budget adherence that best fits their application.

All tool-use experiments in this work are conducted in research-only simulated environments. The APIs, tasks, datasets, verifier infrastructure, and training procedures described here do not represent or imply any deployed Apple product, production system, or product roadmap.

Apple and the Apple logo are trademarks of Apple Inc., registered in the U.S. and other countries and regions.

Notation

Table 3 acts as a reference for the notation used throughout the paper, grouped by where they are introduced.

Task and environment (§ 3.1 and § 3.2)
SS, S~\widetilde{S}, AA, Ω\Omega, Ω~\widetilde{\Omega}Task and budget-augmented state spaces, action space, and observation spaces
TT, T~\widetilde{T}, OO, O~\widetilde{O}Task and budget-augmented transition and observation kernels
MM, M~\widetilde{M}Task POMDP and budget-augmented POMDP
γ\gamma, μ0\mu_0Discount factor and initial state distribution
xx, pXp_XTask and task distribution over X\mathcal{X}
hth_t, HHObservation history at step tt, and set of all histories
π\pi, Π\PiPolicy, and set of policies
κ\kappaRealised transition cost, abbreviated as κ(at)\kappa(a_t)
a⊥a_\perpcomplete_task action that ends an episode
Tmax⁡T_{\max}, τ\tau, τenv\tau_{\mathrm{env}}Truncation horizon, episode stopping time, and environment termination time
ζ\zetaCompleted trajectory
R(ζ)R(\zeta)Binary terminal reward
Budgets and cost (§ 3.2 and Appendix § 8)
B0B_0, btb_tEpisode budget, and remaining budget at step tt
B\mathcal{B}, MMFinite set of training budgets, and its size M=∣B∣M = \lvert\mathcal{B}\rvert
pBp_BBudget prior over B\mathcal{B}
C(ζ)C(\zeta)Raw trajectory spend, e.g. steps, tool calls, or tokens
C~(ζ,B0)\widetilde{C}(\zeta, B_0)Normalised trajectory cost, C(ζ)/B0C(\zeta)/B_0
δ\deltaPermitted overspend rate
Objectives and rewards (§ 3.3 and Appendix § 10)
PDAPOP_{\mathrm{DAPO}}Soft-overlong penalty, adapted from DAPO
α\alphaCoefficient of PDAPOP_{\mathrm{DAPO}}, fixed at 1/21/2
λb\lambda_bLagrange multiplier at budget bb
Λb\Lambda_bEffective price at budget bb, Λb=λb/pB(b)\Lambda_b = \lambda_b/p_B(b)
Lrate\mathcal{L}_{\mathrm{rate}}, Ldual\mathcal{L}_{\mathrm{dual}}Lagrangians of Rate and Dual, with L\mathcal{L} abbreviating Ldual\mathcal{L}_{\mathrm{dual}} in the derivations
R~(ζ,B0)\widetilde{R}(\zeta, B_0)Shaped return
R~gate\widetilde{R}_{\mathrm{gate}}, R~trunc\widetilde{R}_{\mathrm{trunc}}Gated and truncated within-budget success rewards
R~DAPO\widetilde{R}_{\mathrm{DAPO}}, R~rate\widetilde{R}_{\mathrm{rate}}Rewards with only the overspend magnitude or only the overspend rate penalty
J(π)J(\pi), J~(π)\widetilde{J}(\pi)Success objective, and its shaped counterpart
gb(π)g_b(\pi)Constraint functional at budget bb
Policy optimisation (Appendices § 10.6 and § 10.7)
θ\theta, πθ\pi_\thetaPolicy parameters, and the policy they induce
KK, GGNumber of task-budget groups per iteration, and rollouts per group
A(g,i)A^{(g,i)}Dr. GRPO advantage of rollout ii in group gg
σ(⋅)\sigma(\cdot), σ(g)\sigma^{(g)}Logistic sigmoid in the reward definitions, and group reward standard deviation in GRPO
ϵ\epsilonPPO clip range
rt,l(g,i)(θ)r_{t,l}^{(g,i)}(\theta)Token-level importance ratio
β\betaDual step size
Λmax⁡\Lambda_{\max}Cap on the effective price
p^b\hat{p}_b, IbI_bBatch overspend rate at budget bb, and the rollouts it is estimated from
Evaluation (§ 4)
U(b)U(b), Comp⁡(b)\operatorname{Comp}(b)Budget utility and compliance at budget bb
Xtest\mathcal{X}_{\mathrm{test}}, pXtestp_{\mathcal{X}_{\mathrm{test}}}Held-out evaluation task set and its distribution
C~(ζ,b)\widetilde{C}(\zeta, b)Normalised trajectory cost at budget bb

Table 3. Table 3 Notation. Symbols used throughout the main paper and the appendix.

Limitations and Future Work

Each policy currently manages one resource type at a time. Extending the framework to jointly manage several resources would allow an agent to balance constraints such as tokens, tool calls, and environment steps within the same episode. Although the remaining budget is updated after every turn, the total budget and resource definition are fixed at the start of the episode. Future work could consider budgets that are revised during execution or costs that change with the environment state. The framework could also incorporate stochastic costs such as latency or monetary spend and be combined with inference-time allocation methods that build on the budget awareness already internalised by the policy.

Our evidence covers two scales of one model family and simulated environments. Most method comparisons use one training seed; the additional seeds cover two objectives in one AppWorld setting and do not establish a reliable ordering among all leading methods. Unseen-budget evaluation covers AppWorld interpolation for all three resources and extrapolation for steps and API calls; BabyAI is evaluated only at trained budgets. ASTRA transfer uses step budgets and an action interface aligned with AppWorld.

Natural compliance is imperfect, and the capped multiplier updates do not guarantee the target violation rate. A strict deployment budget therefore still requires a cutoff. Our prompts provide remaining-budget feedback and resource-specific advice, including instructions to batch actions. Without ablations of these prompt components, the experiments establish the behaviour of the combined prompting and training procedure, rather than the separate contribution of each component.

Budget-Conditioned Rewards in Full

This appendix defines every reward of Figure 1 and derives the per-budget price of Rate and Dual. All rewards are written using normalised cost Cˉ=Cˉ(ζ,B0)\bar{C}=\bar{C}(\zeta,B_0) of Equation (6), so that the budget sits at Cˉ=1\bar{C}=1 and allows a generalised application across budget types.

Hard gates and fixed penalties.

  • Trunc enforces the budget in the environment. It halts the episode before executing any action that would overdraw the budget, at τB0:=min⁡(τ,inf⁡{t≥1:bt−κ(at)<0}−1)\tau_{B_0}:=\min\left(\tau,\inf\{t\ge1:b_t-\kappa(a_t)<0\}-1\right), and scores the truncated trajectory by the task reward alone, R~trunc(ζ,B0):=R(ζ≤τB0)\tilde{R}_{\mathrm{trunc}}(\zeta,B_0):=R(\zeta_{\le\tau_{B_0}}). Every training trajectory then complies by construction, but the policy receives no training on continuations beyond the budget boundary. Compliance during training is therefore not evidence that it has learned to stop without a cutoff.

  • Gate lets the rollout continue past the budget but withholds the task reward from any overspending trajectory, R^gate(ζ,B0):=R1[Cˉ≤1]\widehat{R}_{\mathrm{gate}}(\zeta,B_0):=R\mathbf{1}[\bar{C}\le1].

  • Gate-Neg ([24]) extends Gate with a fixed penalty for overspending, R1[Cˉ≤1]−1[Cˉ>1]R\mathbf{1}[\bar{C}\le1]-\mathbf{1}[\bar{C}>1].

  • Linear-Cost ([28]) penalises cost linearly from the first action, R−min⁡(1,Cˉ/2)R-\min(1,\bar{C}/2), so it applies pressure before the budget is reached.

Continuous cost shaping. Sigmoid-Gate and Sigmoid use the logistic sigmoid σ(x):=(1+e−x)−1\sigma(x):=(1+e^{-x})^{-1} to supply continuous cost feedback. They differ in whether that feedback starts only after the budget or also acts within it.

  • Sigmoid-Gate has return R+1−2σ(2(Cˉ−1)+)R+1-2\sigma(2(\bar{C}-1)_+). Its additive penalty is zero for Cˉ≤1\bar{C}\le1 and increases continuously towards 1 beyond the budget. Thus, overspending successes approach return 0 and overspending failures approach −1-1. Despite its name, this is not a multiplicative smoothing of Gate’s success gate; the positive-part operation also introduces a kink at the budget.

  • Sigmoid smooths the overspend indicator 1[Cˉ>1]\mathbf{1}[\bar{C}>1] that Rate and Dual apply as a hard step, R−σ(2(Cˉ−1))R-\sigma(2(\bar{C}-1)). Unlike Sigmoid-Gate, this penalty also acts within budget, with a slope that varies with cost.

Magnitude shaping. We adapt the DAPO shaping Equation (D.1) to the normalised cost so that one form covers every budget in every cost unit,

PDAPO(ζ,B0):=αclip⁡(Cˉ(ζ,B0)−1,0,1),(9)P_{\mathrm{DAPO}}(\zeta,B_0):=\alpha\operatorname{clip}\left(\bar{C}(\zeta,B_0)-1,0,1\right), \tag*{(9)}

where α:=1/2\alpha:= 1/2 is set by DAPO’s reward scale and is not tuned (derived in Appendix § 9). Its reward R~DAPO:=R−PDAPO\widetilde{R}_{\mathrm{DAPO}} := R - P_{\mathrm{DAPO}} extends DAPO from one cap fixed before training to a budget sampled each episode. Its fixed coefficient penalises how far a policy overspends but not how often. Exp-Mag instead decays a success exponentially in the overspend, Re−2(C‾−1)+R e^{-2(\overline{C}-1)_{+}}, and leaves every failure at 0.

A per-budget constrained objective. A cost penalty sets a single trade-off between success and spending, but does not directly control how often the policy overspends. To define the Rate and Dual objectives, we instead maximise success subject to a separate constraint on the probability of overspending at each budget. This gives the constrained objective

max⁡π∈Π Ex∼pX, B0∼pBEζ∼π(⋅∣x,B0)[R(ζ)]s.t.Px∼pXζ∼π(⋅∣x,b)(C‾(ζ,b)>1)≤δ,∀b∈B,(10)\max_{\pi\in\Pi}\ \mathbb{E}_{x\sim p_X,\ B_0\sim p_B}\mathbb{E}_{\zeta\sim\pi(\cdot\mid x,B_0)}[R(\zeta)] \quad\mathrm{s.t.}\quad \mathbb{P}_{x\sim p_X\atop\zeta\sim\pi(\cdot\mid x,b)}\left(\overline{C}(\zeta,b)>1\right)\leq\delta,\quad\forall b\in\mathcal{B}, \tag*{(10)}

where δ∈(0,1)\delta\in(0,1) is the permitted overspend rate. The objective averages over tasks and budgets together, whereas each constraint conditions on the budget and averages over tasks alone, so it is the overspend rate a user would measure at budget bb across the distribution of tasks that they wish to have completed. Slack may therefore move between tasks but never between budgets.

Subtracting PDAPOP_{\mathrm{DAPO}} from the objective of Equation (C.2), with the constraints unchanged, gives our Dual training objective,

max⁡π∈Π Ex∼pX, B0∼pBEζ∼π(⋅∣x,B0)[R(ζ)−PDAPO(ζ,B0)]s.t.Px∼pXζ∼π(⋅∣x,b)(C‾(ζ,b)>1)≤δ,∀b∈B.(11)\max_{\pi\in\Pi}\ \mathbb{E}_{x\sim p_X,\ B_0\sim p_B}\mathbb{E}_{\zeta\sim\pi(\cdot\mid x,B_0)}[R(\zeta)-P_{\mathrm{DAPO}}(\zeta,B_0)] \quad\mathrm{s.t.}\quad \mathbb{P}_{x\sim p_X\atop\zeta\sim\pi(\cdot\mid x,b)}\left(\overline{C}(\zeta,b)>1\right)\leq\delta,\quad\forall b\in\mathcal{B}. \tag*{(11)}

Lagrangian relaxation. Introducing a non-negative multiplier λb\lambda_b for each budget-specific constraint gives the Lagrangian for Rate:

Lrate(π,{λb})=Ex∼pX, B0∼pBEζ∼π(⋅∣x,B0)[R(ζ)−ΛB01[C‾(ζ,B0)>1]]+δ∑b∈Bλb.(12)\mathcal{L}_{\mathrm{rate}}(\pi,\{\lambda_b\}) = \mathbb{E}_{x\sim p_X,\ B_0\sim p_B}\mathbb{E}_{\zeta\sim\pi(\cdot\mid x,B_0)} \left[R(\zeta)-\Lambda_{B_0}\mathbf{1}[\overline{C}(\zeta,B_0)>1]\right] +\delta\sum_{b\in\mathcal{B}}\lambda_b. \tag*{(12)}

Adding the DAPO magnitude penalty gives the Lagrangian for Dual:

Ldual(π,{λb})=Ex∼pX, B0∼pBEζ∼π(⋅∣x,B0)[R(ζ)−PDAPO(ζ,B0)−ΛB01[C‾(ζ,B0)>1]]+δ∑b∈Bλb.(13)\mathcal{L}_{\mathrm{dual}}(\pi,\{\lambda_b\}) = \mathbb{E}_{x\sim p_X,\ B_0\sim p_B}\mathbb{E}_{\zeta\sim\pi(\cdot\mid x,B_0)} \left[R(\zeta)-P_{\mathrm{DAPO}}(\zeta,B_0)-\Lambda_{B_0}\mathbf{1}[\overline{C}(\zeta,B_0)>1]\right] +\delta\sum_{b\in\mathcal{B}}\lambda_b. \tag*{(13)}

Here Λb:=λb/pB(b)\Lambda_b:=\lambda_b/p_B(b) is the effective price of overspending at budget bb; the factor 1/pB(b)1/p_B(b) corrects for how often that budget is sampled. The final term is constant in π\pi, leaving the per-trajectory shaped return used by each method. In particular, R~rate:=R−ΛB01[C‾>1]\widetilde{R}_{\mathrm{rate}}:=R-\Lambda_{B_0}\mathbf{1}[\overline{C}>1], and Dual additionally subtracts PDAPOP_{\mathrm{DAPO}}. Both methods update the multipliers in response to the overspend rate at each budget (Appendix § 10.7). The rate penalty targets how often the policy overspends, while PDAPOP_{\mathrm{DAPO}} in Dual additionally distinguishes overspending trajectories by how far they exceed the budget (Appendix § 10.§ 5).

Adapting DAPO to Multi-Budget Settings

We give DAPO’s original soft-overlong penalty and show how we adapt it from a single fixed token cap to a family of budgets.

DAPO (Yu et al. [29]) introduces a soft-overlong penalty for truncated responses in long-chain-of-thought reinforcement learning, evaluated on mathematical reasoning tasks. The penalty increases with response length within a soft window near the maximum generation length. Given a maximum response length Lmax⁡∈Z>0L_{\max}\in\mathbb{Z}_{>0} and a soft window Ls∈Z>0L_s\in\mathbb{Z}_{>0} with Ls≤Lmax⁡L_s\leq L_{\max}, it shapes the reward according to the response length L(o)∈Z≥0L(o)\in\mathbb{Z}_{\geq0} as

Rlen(o)={0,L(o)≤Lmax⁡−Ls,(Lmax⁡−Ls)−L(o)Ls,Lmax⁡−Ls<L(o)≤Lmax⁡,−1,L(o)>Lmax⁡.(14)R_{\mathrm{len}}(o)= \begin{cases} 0, & L(o)\leq L_{\max}-L_s,\\ \frac{(L_{\max}-L_s)-L(o)}{L_s}, & L_{\max}-L_s<L(o)\leq L_{\max},\\ -1, & L(o)>L_{\max}. \end{cases} \tag*{(14)}

The penalty is zero up to the soft threshold Lmax⁡−LsL_{\max}-L_s, decreases linearly to −1-1 over a window of width LsL_s, and remains at −1-1 beyond Lmax⁡L_{\max}. It therefore supplies a continuous penalty based on overspend magnitude.

This construction was designed for a single token-length cap fixed before training. Our setting instead requires one policy to work across a family of budgets B0B_0, with the budget varying between episodes, and with budgeted quantities other than tokens, such as steps or tool calls. We adapt DAPO’s penalty to this setting by expressing spend relative to the budget of the current episode.

Concretely, set Ls=B0L_{\mathrm{s}} = B_0 and Lmax⁡=2B0L_{\max} = 2B_0 in Equation (D.1). The soft threshold Lmax⁡−LsL_{\max} - L_{\mathrm{s}} is then exactly B0B_0, and the middle branch becomes

(2B0−B0)−L(o)B0=B0−L(o)B0=−(L(o)B0−1).(15)\frac{(2B_0-B_0)-L(o)}{B_0}=\frac{B_0-L(o)}{B_0}=-\left(\frac{L(o)}{B_0}-1\right). \tag*{(15)}

We therefore apply the linear ramp to the normalised trajectory cost Cˉ(ζ,B0)\bar{C}(\zeta,B_0) of Equation (6) instead of to the raw token count L(o)L(o) against one fixed cap. Reversing the sign so that it is written as a positive penalty to be subtracted from the return gives the same ramp in normalised-cost units, clip⁡(Cˉ(ζ,B0)−1,0,1)\operatorname{clip}(\bar{C}(\zeta,B_0)-1,0,1). The cost map κ\kappa determines the quantity being budgeted, while normalisation by B0B_0 makes the soft threshold Cˉ(ζ,B0)=1\bar{C}(\zeta,B_0)=1 for every budget. The same DAPO penalty therefore applies to any budget and to any cost unit.

It remains to match the scale of DAPO’s original reward. DAPO pairs a task reward RDAPO∈{−1,+1}R_{\mathrm{DAPO}}\in\{-1,+1\} with a penalty Rlen∈[−1,0]R_{\mathrm{len}}\in[-1,0], whereas our terminal reward R(ζ)∈{0,1}R(\zeta)\in\{0,1\}. The map x↦(x+1)/2x\mapsto(x+1)/2 takes DAPO’s task-reward scale to ours. Applying the same map to DAPO’s shaped return gives

RDAPO+Rlen+12=RDAPO+12⏟R(ζ)+12Rlen,(16)\frac{R_{\mathrm{DAPO}}+R_{\mathrm{len}}+1}{2} = \underbrace{\frac{R_{\mathrm{DAPO}}+1}{2}}_{R(\zeta)} +\frac{1}{2}R_{\mathrm{len}}, \tag*{(16)}

so preserving DAPO’s relative weighting between task success and the soft-overlong penalty introduces a factor of 12\frac{1}{2}. Combining this rescaling with the normalised expression above gives our penalty

PDAPO(ζ,B0)=12clip⁡(Cˉ(ζ,B0)−1,0,1),(17)P_{\mathrm{DAPO}}(\zeta,B_0)=\frac{1}{2}\operatorname{clip}(\bar{C}(\zeta,B_0)-1,0,1), \tag*{(17)}

which is Equation (C.1) with α=12\alpha=\frac{1}{2}. We therefore set α=0.5\alpha=0.5 throughout (Appendix § 11.7). In raw spend, CC, the penalty has slope 1/(2B0)1/(2B_0) within the linear overspending region, so a fixed absolute overspend carries a larger penalty under a tighter budget than under a looser budget.

The rescaling preserves the relative weighting of task success and the length penalty. The Dr. GRPO advantage centres each trajectory’s return within its group (Appendix § 10.7), so an affine transformation R~↦aR~+c\tilde{R}\mapsto a\tilde{R}+c with a>0a>0 removes the additive constant under centring and multiplies every advantage by aa. For the unfiltered surrogate, this preserves the advantage signs and relative magnitudes and rescales its gradient by a constant.

Optimising Budget-Conditioned Objectives

This appendix describes the optimisation used in § 3. Appendix § 10.§ 2 fixes the policy class and constraint functionals, Appendix § 10.§ 3 verifies the rearrangement of the Lagrangian Equation (C.5), Appendix § 10.§ 4 derives the policy and multiplier updates of Appendix § 10.7 from it, and Appendix § 10.§ 5 explains the distinct signals supplied by Dual’s two penalties. Appendices § 10.6 and § 10.7 give the shared Dr. GRPO policy update and the additional multiplier updates used by Rate and Dual. Appendix § 10.8 gives a general training algorithm for fixed reward objectives, followed by the shared algorithm for Rate and Dual.

Background

Constrained MDPs (cMDPs) typically bound expected cumulative cost for a single fixed threshold ([3, 1]), often using Lagrangian methods for optimisation ([23]). Budgeted MDPs ([5]) extend cMDPs to families of budgets by conditioning value functions on the remaining allowance, but still constrain expected discounted cost return via fitted Q-iteration. This does not directly express budget compliance at the level of individual requests, where an expected-cost constraint can hide frequent individual violations. Risk-aware and chance-constrained formulations instead bound the probability of undesirable events ([9, 12]), and Chow (2017) studies trajectory-level probabilistic constraints under Lagrangian relaxation.

Setup

Throughout we work with the trajectory law induced by a policy π\pi on the budget-augmented POMDP M~\widetilde{\mathcal{M}} of § 3.2. We write Pπ\mathbb{P}_{\pi} for that law, i.e. Pπ(⋅)=Px∼pX,B0∼pB,ζ∼π(⋅∣x,B0)(⋅)\mathbb{P}_{\pi}(\cdot) = \mathbb{P}_{x \sim p_X, B_0 \sim p_B, \zeta\sim\pi(\cdot\mid x,B_0)}(\cdot) and likewise Eπ\mathbb{E}_{\pi} for expectation under it, matching the sampling made explicit in Equations (C.2) and (C.5). We include the task draw in this law rather than writing it separately because every quantity below averages over tasks. Conditioning on a fixed budget, written Pπ(⋅∣B0=b)\mathbb{P}_{\pi}(\cdot\mid B_0 = b) below, still draws x∼pXx \sim p_X and then rolls out ζ\zeta under π(⋅∣x,b)\pi(\cdot\mid x,b). We define the objective and per-budget constraint functionals

J(π):=Eπ[R(ζ)],gb(π):=Pπ(C‾(ζ,B0)>1∣B0=b)−δ,b∈B,(18)J(\pi) := \mathbb{E}_{\pi}[R(\zeta)], \qquad g_b(\pi) := \mathbb{P}_{\pi}\left(\overline{C}(\zeta,B_0) > 1 \mid B_0 = b\right) - \delta,\qquad b \in\mathcal{B}, \tag*{(18)}

so that the constrained objective Equation (C.2) reads max⁡π∈ΠJ(π)\max_{\pi\in\Pi} J(\pi) subject to gb(π)≤0g_b(\pi) \le0 for every b∈Bb \in\mathcal{B}. The conditioning in Equation (E.1) is well-defined because pBp_B has full support on the finite set B\mathcal{B}. Equation (C.3) keeps these constraints and shapes the objective,

J~(π):=Eπ[R(ζ)−PDAPO(ζ,B0)],(19)\widetilde{J}(\pi) := \mathbb{E}_{\pi}\left[R(\zeta) - P_{\mathrm{DAPO}}(\zeta,B_0)\right], \tag*{(19)}

so that it reads max⁡π∈ΠJ~(π)\max_{\pi\in\Pi} \widetilde{J}(\pi) subject to the same gb(π)≤0g_b(\pi) \le0. Its Lagrangian is Ldual\mathcal{L}_{\mathrm{dual}} in Equation (C.5), which we abbreviate as L\mathcal{L} below. Results below are stated for J~\widetilde{J}, and setting α=0\alpha= 0 recovers JJ and Equation (C.2).

Rearrangement of the Lagrangian

Relaxing Equation (C.3) prices each budget with its own multiplier, through the penalty

∑b∈Bλb(Pπ(C‾(ζ,B0)>1∣B0=b)−δ).\sum_{b \in\mathcal{B}} \lambda_b\left(\mathbb{P}_{\pi}\left(\overline{C}(\zeta,B_0) > 1 \mid B_0 = b\right) - \delta\right).

Folding that sum into a single expectation produces the compact Lagrangian Equation (C.5) and its per-trajectory integrand, the shaped return of Dual (Figure 1). Writing each overspend probability as an expectation and splitting the outer expectation over the prior B0∼pBB_0 \sim p_B,

∑b∈BλbPπ(C‾(ζ,B0)>1∣B0=b)=∑b∈BλbEπ[1[C‾(ζ,B0)>1]∣B0=b]=∑b∈BpB(b)λbpB(b)Eπ[1[C‾(ζ,B0)>1]∣B0=b]=Eπ[λB0pB(B0)1[C‾(ζ,B0)>1]],(20)\begin{aligned} \sum_{b \in\mathcal{B}} \lambda_b \mathbb{P}_{\pi}\left(\overline{C}(\zeta,B_0) > 1 \mid B_0 = b\right) &= \sum_{b \in\mathcal{B}} \lambda_b \mathbb{E}_{\pi}\left[\mathbf{1}\left[\overline{C}(\zeta,B_0) > 1\right] \mid B_0 = b\right] \\ &= \sum_{b \in\mathcal{B}} p_B(b)\frac{\lambda_b}{p_B(b)}\mathbb{E}_{\pi}\left[\mathbf{1}\left[\overline{C}(\zeta,B_0) > 1\right] \mid B_0 = b\right] \\ &= \mathbb{E}_{\pi}\left[\frac{\lambda_{B_0}}{p_B(B_0)}\mathbf{1}\left[\overline{C}(\zeta,B_0) > 1\right]\right], \tag*{(20)} \end{aligned}

where the second line divides and multiplies by pB(b)>0p_B(b) > 0 and the third recognises the resulting sum as an expectation over B0∼pBB_0 \sim p_B. The importance weight 1/pB(B0)1/p_B(B_0) therefore corrects for the frequency with which each budget is sampled, so that a budget contributes to the penalty in proportion to λb\lambda_b alone and not to how often it is drawn. The remaining term δ∑b∈Bλb\delta\sum_{b \in\mathcal{B}} \lambda_b is constant in π\pi and plays no part in the policy update. Under the uniform prior used in our experiments, 1/pB(b)=∣B∣1/p_B(b) = |\mathcal{B}| for every budget, so the effective price appearing in the shaped return is Λb=∣B∣λb\Lambda_b = |\mathcal{B}|\lambda_b.

Gradients of the Lagrangian

This section derives the policy and multiplier updates of Appendix § 10.7 from the Lagrangian Equation (C.5), whose per-trajectory integrand is the shaped return R~\widetilde{R} of Dual (Figure 1) and whose trailing term δ∑b∈Bλb\delta\sum_{b \in\mathcal{B}}\lambda_b is constant in π\pi.

Policy gradient. Fix {λb}\{\lambda_b\} and parameterise the policy by πθ\pi_\theta as in Equation (4). In the budget-augmented POMDP M~\widetilde{\mathcal{M}} of § 3.2, neither the kernels T~,O~\widetilde{T},\widetilde{O} nor the budget recursion bt+1=bt−κ(at)b_{t+1}=b_t-\kappa(a_t) depends on θ\theta, so their log-derivatives vanish and the trajectory score reduces to a sum over the policy’s own factors,

sθ(ζ,x,B0):=∇θlog⁡pθ(ζ∣x,B0)=∑t≤τ∇θlog⁡πθ(at∣x,ht,bt,B0).(21)s_\theta(\zeta,x,B_0):=\nabla_\theta\log p_\theta(\zeta\mid x,B_0)=\sum_{t\leq\tau}\nabla_\theta\log\pi_\theta(a_t\mid x,h_t,b_t,B_0). \tag*{(21)}

Since δ∑bλb\delta\sum_b\lambda_b is constant in π\pi, the score-function gradient of the Lagrangian is

∇θL(πθ,{λb})=Ex∼pX, B0∼pB, ζ∼πθ(⋅∣x,B0)[R~(ζ,B0)sθ(ζ,x,B0)].(22)\nabla_\theta\mathcal{L}(\pi_\theta,\{\lambda_b\})=\mathbb{E}_{x\sim p_X,\,B_0\sim p_B,\,\zeta\sim\pi_\theta(\cdot\mid x,B_0)}\left[\widetilde{R}(\zeta,B_0)s_\theta(\zeta,x,B_0)\right]. \tag*{(22)}

Each action ata_t is itself a token sequence, so each factor of Equation (E.4) expands into per-token log-probabilities and sθs_\theta sums over all generated tokens. The return is terminal and undiscounted, so Equation (E.5) weights every token of a trajectory by the same scalar R~\widetilde{R}, with no length normaliser.

We reduce variance by centring returns within each group. Write

R~(g,i):=R~(ζ(g,i),B0(g)),sθ(g,i):=sθ(ζ(g,i),x(g),B0(g)),R~‾(g):=G−1∑j=1GR~(g,j).\widetilde{R}^{(g,i)}:=\widetilde{R}(\zeta^{(g,i)},B_0^{(g)}),\qquad s_\theta^{(g,i)}:=s_\theta(\zeta^{(g,i)},x^{(g)},B_0^{(g)}),\qquad\overline{\widetilde{R}}^{(g)}:=G^{-1}\sum_{j=1}^{G}\widetilde{R}^{(g,j)}.

Within a group, trajectories are i.i.d. given the task and budget. Given that pair, Eζ∼πθ(⋅∣x,B0)[sθ(ζ,x,B0)]=0\mathbb{E}_{\zeta\sim\pi_\theta(\cdot\mid x,B_0)}[s_\theta(\zeta,x,B_0)]=0, so the cross terms vanish. Each trajectory also appears in its own group mean, leaving a factor of 1−1/G1-1/G after averaging over the task and budget draws,

E(x(g),B(g))∼pX⊗pBζ(g,1),…,ζ(g,G)∼πθ(⋅∣x(g),B(g))[(R~(g,i)−R~‾(g))sθ(g,i)]=(1−1G)∇θL(πθ,{λb}).(23)\mathbb{E}_{\substack{(x^{(g)},B^{(g)})\sim p_X\otimes p_B\\ \zeta^{(g,1)},\ldots,\zeta^{(g,G)}\sim\pi_\theta(\cdot\mid x^{(g)},B^{(g)})}}\left[\left(\widetilde{R}^{(g,i)}-\overline{\widetilde{R}}^{(g)}\right)s_\theta^{(g,i)}\right]=\left(1-\frac{1}{G}\right)\nabla_\theta\mathcal{L}(\pi_\theta,\{\lambda_b\}). \tag*{(23)}

with the constant absorbed into the learning rate. We omit GRPO’s standard-deviation and length normalisers of Equation (E.10), which do not preserve this gradient (Appendix § 10.6).

In practice we replace Equation (E.5) by the clipped Dr. GRPO surrogate Equation (E.14), recovering the advantage Equation (E.13). Before the segment filtering of Appendix § 11.6, its expected gradient agrees with the policy gradient up to the factor 1−1/G1-1/G at θ=θold\theta=\theta_{\mathrm{old}}, where every ratio rt,l(g,i)(θ)r_{t,l}^{(g,i)}(\theta) equals one, while clipping controls the off-policy change over repeated optimisation steps on one batch of rollouts (Appendix § 10.6).

Multiplier gradient. Now fix π\pi and let pb:=Pπ(C~(ζ,B0)>1∣B0=b)=gb(π)+δp_b:=\mathbb{P}_{\pi}\left(\widetilde{C}(\zeta,B_0)>1\mid B_0=b\right)=g_b(\pi)+\delta be the overspend rate at budget bb. Differentiating Equation (C.5) in λb\lambda_b, with the penalty written per budget as in Equation (E.3), gives

∂L∂λb=−gb(π)=−(pb−δ).(24)\frac{\partial\mathcal{L}}{\partial\lambda_b}=-g_b(\pi)=-(p_b-\delta). \tag*{(24)}

Since the multipliers minimise L\mathcal{L} subject to λb≥0\lambda_b\geq0, projected gradient descent in λb\lambda_b gives the projected dual update of Algorithm 2,

λb←[λb−β∂L∂λb]+=[λb+β(pb−δ)]+.(25)\lambda_b\leftarrow\left[\lambda_b-\beta\frac{\partial\mathcal{L}}{\partial\lambda_b}\right]_+=\left[\lambda_b+\beta(p_b-\delta)\right]_+. \tag*{(25)}

Replacing pbp_b by the batch estimate p^b\widehat{p}_b gives Equation (E.15). Each multiplier therefore increases when pb>δp_b>\delta and decreases when pb<δp_b<\delta, subject to projection at zero. The batch estimate p^b\widehat{p}_b is unbiased for pbp_b under the current policy. We use it without smoothing across updates to keep the estimate on-policy. By Equation (E.7) the gradient at budget bb does not involve λb′\lambda_{b'} for b′≠bb'\ne b, so all multipliers update in parallel from one batch, as in Algorithm 2.

At a fixed point of the exact-rate update away from the upper cap in Equation (E.15), λb>0\lambda_b>0 implies pb=δp_b=\delta, while λb=0\lambda_b=0 implies pb≤δp_b\leq\delta. Thus, a budget with a positive, uncapped multiplier has overspend rate δ\delta.

Complementary Roles of the Two Penalties

Both penalties in the Dual return Equation (C.5) activate on the same event {C‾(ζ,B0)>1}\{\overline{C}(\zeta, B_0)>1\} but act on different quantities. As a function of the normalised cost c=C‾(ζ,b)c=\overline{C}(\zeta,b) at a fixed task outcome, the rate term Λb1[c>1]\Lambda_b\mathbf{1}[c>1] is constant on {c>1}\{c>1\}, whereas PDAPOP_{\mathrm{DAPO}} of Equation (C.1) has slope α\alpha on (1,2)(1,2). The rate term alone is therefore indifferent between a marginal and a gross overspend. Conversely, α=12\alpha=\frac{1}{2} is fixed and shared across budgets, so the overspend rate it induces at any budget is not controlled, whereas an interior fixed point of the dual update gives pb=δp_b=\delta (Appendix § 10.§ 4).

What reaches the policy is the group-centred advantage Equation (E.13). Fix a group gg at budget bb and drop the index gg, writing R(i)R^{(i)} for the task reward of rollout ii, u(i):=1[C‾(ζ(i),b)>1]u^{(i)}:=\mathbf{1}[\overline{C}(\zeta^{(i)},b)>1] for its overspend indicator, P(i):=PDAPO(ζ(i),b)P^{(i)}:=P_{\mathrm{DAPO}}(\zeta^{(i)},b) for its magnitude penalty and p^:=G−1∑ju(j)\hat{p}:=G^{-1}\sum_j u^{(j)} for the overspend fraction of the group. Centring each term of the return separately gives

A(i)=(R(i)−R‾)⏟task outcome−(P(i)−P‾)⏟magnitude−Λb(u(i)−p^)⏟rate,(26)A^{(i)}=\underbrace{\left(R^{(i)}-\overline{R}\right)}_{\text{task outcome}}-\underbrace{\left(P^{(i)}-\overline{P}\right)}_{\text{magnitude}}-\underbrace{\Lambda_b\left(u^{(i)}-\hat{p}\right)}_{\text{rate}}, \tag*{(26)}

with bars denoting group means. Which terms survive depends on how the group splits on the budget. If no rollout overspends, both penalty terms vanish and the group reduces to ordinary task learning whatever Λb\Lambda_b has reached. If every rollout overspends, the rate term cancels however large Λb\Lambda_b is, and only differences in the magnitude penalty distinguish rollouts with the same task outcome. This signal also vanishes if every magnitude penalty has saturated. Without it, a group that also shares its task outcome has zero advantage. Such groups can occur at tight budgets early in training, when every rollout overspends and none succeeds; rate-only shaping then supplies no policy-gradient signal. If compliance is mixed, the rate term separates compliant from overspending rollouts by exactly Λb\Lambda_b however far the overspenders ran over, while the magnitude term orders the overspending rollouts by at most α\alpha. The dual therefore sets the price of overspending at all, adjusted per budget towards the target rate δ\delta, and PDAPOP_{\mathrm{DAPO}} orders overspending trajectories by how far they ran over. Neither is recoverable from the other by rescaling, so Dual keeps both.

Group-Relative Policy Optimisation

GRPO (Shao et al., [21]) is a critic-free variant of PPO (Schulman et al., [20]). For each prompt, it samples a group of G∈Z>0G\in\mathbb{Z}_{>0} responses with rewards {r(g,i)}i=1G⊂R\{r^{(g,i)}\}_{i=1}^{G}\subset\mathbb{R} and uses the group mean as a baseline. For each group gg, its advantage is

A(g,i)=1σ(g)(r(g,i)−1G∑j=1Gr(g,j)),(27)A^{(g,i)}=\frac{1}{\sigma^{(g)}}\left(r^{(g,i)}-\frac{1}{G}\sum_{j=1}^{G}r^{(g,j)}\right), \tag*{(27)}

where σ(g)\sigma^{(g)} is the standard deviation of the rewards within group gg. This expression applies to groups with nonzero reward variance. GRPO applies this advantage to each response token through a clipped PPO surrogate, averaging the token-level objective within each response. For a batch of KK groups with GG responses per group, this objective is

JGRPO(θ)=1KG∑g=1K∑i=1G1N(g,i)∑t≤τ(g,i)∑l≤Lt(g,i)min⁡(rt,l(g,i)(θ)A(g,i),clip⁡(rt,l(g,i)(θ),1−ϵ,1+ϵ)A(g,i)),(28)\mathcal{J}_{\mathrm{GRPO}}(\theta)=\frac{1}{KG}\sum_{g=1}^{K}\sum_{i=1}^{G}\frac{1}{N^{(g,i)}}\sum_{t\leq\tau^{(g,i)}}\sum_{l\leq L_t^{(g,i)}}\min\left(r_{t,l}^{(g,i)}(\theta)A^{(g,i)},\operatorname{clip}\left(r_{t,l}^{(g,i)}(\theta),1-\epsilon,1+\epsilon\right)A^{(g,i)}\right), \tag*{(28)}

where N(g,i):=∑t≤τ(g,i)Lt(g,i)N^{(g,i)}:=\sum_{t\leq\tau^{(g,i)}}L_t^{(g,i)} is the total number of generated tokens in trajectory (g,i)(g,i), and rt,l(g,i)(θ)r_{t,l}^{(g,i)}(\theta) is the token-level importance ratio between the current and behaviour policies.

Liu et al. [17] identify biases from both normalisers in these equations. Dividing by σ\sigma gives greater weight to groups with lower reward variance. Dividing the surrogate by response length gives shorter positive-advantage responses larger per-token updates, while giving longer negative-advantage responses smaller per-token updates. This can encourage failed responses to grow longer. Dr. GRPO removes both normalisers, using

A(g,i)=r(g,i)−1G∑j=1Gr(g,j)(29)A^{(g,i)}=r^{(g,i)}-\frac{1}{G}\sum_{j=1}^{G}r^{(g,j)} \tag*{(29)}

and summing the clipped surrogate over response tokens without dividing by response length. The batch averaging factor 1/(KG)1/(KG) remains.

We use Dr. GRPO throughout, grouping trajectories by task and budget so that the within-group baseline compares rollouts subject to the same budget. Appendix § 10.7 gives the resulting policy update for our shaped return.

Policy and Multiplier Updates

Policy update. At each iteration, we draw K∈Z>0K \in\mathbb{Z}_{>0} task-budget pairs (x(g),B0(g))∼pX⊗pB(x^{(g)}, B_0^{(g)}) \sim p_X \otimes p_B, g=1,…,Kg = 1,\ldots,K, and sample G∈Z>0G \in\mathbb{Z}_{>0} trajectories ζ(g,i)∼πθ(⋅∣x(g),B0(g))\zeta^{(g,i)} \sim\pi_\theta(\cdot\mid x^{(g)}, B_0^{(g)}), i=1,…,Gi = 1,\ldots,G, for each pair. Writing R~(g,i):=R~(ζ(g,i),B0(g))∈R\widetilde{R}^{(g,i)} := \widetilde{R}(\zeta^{(g,i)}, B_0^{(g)}) \in\mathbb{R} for the chosen training return, we centre it within each group:

A(g,i)=R~(g,i)−1G∑j=1GR~(g,j).(30)A^{(g,i)} = \widetilde{R}^{(g,i)} - \frac{1}{G}\sum_{j=1}^{G}\widetilde{R}^{(g,j)}. \tag*{(30)}

Each group therefore contains rollouts for one task at one budget. For Rate and Dual, the group also shares the same multiplier λB0(g)\lambda_{B_0^{(g)}}. Centring within groups compares trajectories that faced identical budgets. This is Equation (E.12) with r(i)r^{(i)} replaced by R~(g,i)\widetilde{R}^{(g,i)}.

At step tt, collect the policy’s inputs into zt(g,i):=(x(g),ht(g,i),bt(g,i),B0(g))z_t^{(g,i)} := (x^{(g)}, h_t^{(g,i)}, b_t^{(g,i)}, B_0^{(g)}) and write the action as its token sequence at(g,i)=(at,1(g,i),…,at,Lt(g,i)(g,i))a_t^{(g,i)} = (a_{t,1}^{(g,i)},\ldots,a_{t,L_t^{(g,i)}}^{(g,i)}). The token-level importance ratio is

rt,l(g,i)(θ)=πθ(at,l(g,i)∣zt(g,i),at,<l(g,i))πθold(at,l(g,i)∣zt(g,i),at,<l(g,i)).r_{t,l}^{(g,i)}(\theta) = \frac{\pi_\theta(a_{t,l}^{(g,i)} \mid z_t^{(g,i)},a_{t,<l}^{(g,i)})}{\pi_{\theta_{\mathrm{old}}}(a_{t,l}^{(g,i)} \mid z_t^{(g,i)},a_{t,<l}^{(g,i)})}.

For clip range ϵ∈(0,1)\epsilon\in(0,1), we ascend the Dr. GRPO surrogate

J(θ)=1KG∑g=1K∑i=1G∑t≤T(g,i)∑l≤Lt(g,i)min⁡(rt,l(g,i)(θ)A(g,i),clip⁡(rt,l(g,i)(θ),1−ϵ,1+ϵ)A(g,i)).(31)\mathcal{J}(\theta) = \frac{1}{KG}\sum_{g=1}^{K}\sum_{i=1}^{G}\sum_{t \leq T^{(g,i)}}\sum_{l \leq L_t^{(g,i)}} \min\left(r_{t,l}^{(g,i)}(\theta)A^{(g,i)},\operatorname{clip}\left(r_{t,l}^{(g,i)}(\theta),1-\epsilon,1+\epsilon\right)A^{(g,i)}\right). \tag*{(31)}

As in Dr. GRPO, the trajectory-level advantage is applied to every token without a response-length normaliser. This policy update applies to every reward objective. For Dual, Appendix § 10.§ 4 relates it to the policy gradient of Equation (C.5).

Multiplier update. For Rate and Dual, each multiplier λb\lambda_b increases when the policy overspends at budget bb more often than the permitted rate δ\delta, and decreases otherwise. We estimate the overspend rate from the batch rollouts collected at budget bb, pooled over their tasks. Let

C‾(g,i):=C‾(ζ(g,i),B0(g)),Ib:={(g,i):B0(g)=b},\overline{C}^{(g,i)} := \overline{C}(\zeta^{(g,i)},B_0^{(g)}), \qquad\mathcal{I}_b := \{(g,i):B_0^{(g)}=b\},

and let β∈R>0\beta\in\mathbb{R}_{>0} be the multiplier step size. The batch estimate and projected update are

p^b=1∣Ib∣∑(g,i)∈Ib1[C‾(g,i)>1],λb←min⁡{[λb+β(p^b−δ)]+,Λmax⁡pB(b)}.(32)\widehat{p}_b = \frac{1}{|\mathcal{I}_b|}\sum_{(g,i)\in\mathcal{I}_b}\mathbf{1}\left[\overline{C}^{(g,i)}>1\right], \qquad\lambda_b \leftarrow\min\left\{[\lambda_b+\beta(\widehat{p}_b-\delta)]_+,\Lambda_{\max}p_B(b)\right\}. \tag*{(32)}

For budgets with ∣Ib∣>0|\mathcal{I}_b|>0, this is projected gradient descent on the Lagrangian in λb\lambda_b, whose gradient at the true overspend rate pbp_b is δ−pb\delta-p_b (Appendix § 10.§ 4). Budgets absent from the batch retain their previous multiplier. The raw batch estimate is not smoothed across updates, keeping the multiplier update on-policy.

The effective-price cap Λmax⁡\Lambda_{\max} depends on the reward. For Rate, which has no magnitude penalty, we set Λmax⁡=1\Lambda_{\max}=1. For Dual, we set Λmax⁡=12\Lambda_{\max}=\frac{1}{2} because the DAPO penalty is also bounded by 12\frac{1}{2}. In each case, the cap ensures that an overspending success is not valued below a compliant failure. We project the multiplier itself, rather than clipping only the price in the shaped return, so that the price can decrease when the overspend rate falls below δ\delta. The cap makes this a bounded-price relaxation: a budget can retain an overspend rate above δ\delta when its price reaches the cap, and we do not claim constraint satisfaction or convergence for the parameterised policy.

Training Algorithms

Algorithm 1 optimises Equation (5) for a chosen fixed return R~\widetilde{R}. For simplicity, both algorithms sample budgets uniformly from B\mathcal{B}, as in our experiments. Rollouts receive budget feedback and end on agent or environment termination, or at Tmax⁡T_{\max}. GRPO-Std sets R~(ζ,B0)=R(ζ)\widetilde{R}(\zeta, B_0)=R(\zeta), while the fixed budget-shaped objectives use the returns in Appendix § 8. Trunc also applies its budget cutoff. Both algorithms use the segment filtering described in Appendix § 11.6.

Algorithm 1Budget-aware training with a fixed reward objective
Require: Policy πθ\pi_\theta; task distribution pXp_X; budget set B\mathcal{B}; cost map κ\kappa; fixed return R~\widetilde{R}; groups KK; group size GG; clip range ϵ\epsilon; horizon Tmax⁡T_{\max}
1:for each training iteration do
2:θold←θ\theta_{\mathrm{old}}\leftarrow\theta
3:Draw KK pairs (x(g),B0(g))∼pX⊗Unif⁡(B)(x^{(g)},B_0^{(g)})\sim p_X\otimes\operatorname{Unif}(\mathcal{B})
4:for each group gg do
5:for each rollout i=1,…,Gi=1,\ldots,G do
6:Reset the environment for x(g)x^{(g)} and set b1(g,i)←B0(g)b_1^{(g,i)}\leftarrow B_0^{(g)}
7:Collect ζ(g,i)\zeta^{(g,i)} under πθold\pi_{\theta_{\mathrm{old}}} with budget feedback and the update in Equation (1)
8:Compute R(g,i)∈{0,1}R^{(g,i)}\in\{0,1\} and Cˉ(g,i)∈R≥0\bar{C}^{(g,i)}\in\mathbb{R}_{\geq0} from ζ(g,i)\zeta^{(g,i)} (Equation (6))
9:R~(g,i)←R~(ζ(g,i),B0(g))\widetilde{R}^{(g,i)}\leftarrow\widetilde{R}(\zeta^{(g,i)},B_0^{(g)})
10:end for
11:A(g,i)←R~(g,i)−1G∑j=1GR~(g,j)A^{(g,i)}\leftarrow\widetilde{R}^{(g,i)}-\frac{1}{G}\sum_{j=1}^{G}\widetilde{R}^{(g,j)} for each ii
12:end for
13:Apply segment filtering (Appendix § 11.6)
14:Update θ\theta using the clipped Dr. GRPO surrogate in Equation (E.14)
15:end for

Table 1 (PDF p. 23).

Algorithm 2 covers Rate and Dual by adding a learned violation price and updating it from the same rollouts. Under uniform budget sampling, the effective price is Λb=∣B∣λb\Lambda_b=|\mathcal{B}|\lambda_b.

Algorithm 2Budget-aware training with learned violation prices (Rate and Dual)
Require: Policy πθ\pi_\theta; task distribution pXp_X; budget set B\mathcal{B}; cost map κ\kappa; objective Rate or Dual; tolerance δ\delta; dual step β\beta; groups KK; group size GG; clip range ϵ\epsilon; horizon Tmax⁡T_{\max}
1:Set (α,Λmax⁡)←(0,1)(\alpha,\Lambda_{\max})\leftarrow(0,1) for Rate or (12,12)\left(\frac{1}{2},\frac{1}{2}\right) for Dual
2:Initialise λb←0\lambda_b\leftarrow0 for each b∈Bb\in\mathcal{B}
3:for each training iteration do
4:θold←θ\theta_{\mathrm{old}}\leftarrow\theta
5:Draw KK pairs (x(g),B0(g))∼pX⊗Unif⁡(B)(x^{(g)},B_0^{(g)})\sim p_X\otimes\operatorname{Unif}(\mathcal{B})
6:for each group gg do
7:for each rollout i=1,…,Gi=1,\ldots,G do
8:Reset the environment for x(g)x^{(g)} and set b1(g,i)←B0(g)b_1^{(g,i)}\leftarrow B_0^{(g)}
9:Collect ζ(g,i)\zeta^{(g,i)} under πθold\pi_{\theta_{\mathrm{old}}} with budget feedback and the update in Equation (1)
10:Compute R(g,i)∈{0,1}R^{(g,i)}\in\{0,1\} and Cˉ(g,i)∈R≥0\bar{C}^{(g,i)}\in\mathbb{R}_{\geq0} from ζ(g,i)\zeta^{(g,i)} (Equation (6))
11:R~(g,i)←R(g,i)−αclip⁡(Cˉ(g,i)−1,0,1)−∣B∣λB0(g)1[Cˉ(g,i)>1]\widetilde{R}^{(g,i)}\leftarrow R^{(g,i)}-\alpha\operatorname{clip}(\bar{C}^{(g,i)}-1,0,1)-|\mathcal{B}|\lambda_{B_0^{(g)}}\mathbf{1}[\bar{C}^{(g,i)}>1]
12:end for
13:A(g,i)←R~(g,i)−1G∑j=1GR~(g,j)A^{(g,i)}\leftarrow\widetilde{R}^{(g,i)}-\frac{1}{G}\sum_{j=1}^{G}\widetilde{R}^{(g,j)} for each ii
14:end for
15:Apply segment filtering (Appendix § 11.6)
16:Update θ\theta using the clipped Dr. GRPO surrogate in Equation (E.14)
17:for each budget bb sampled in the batch do
18:Ib←{(g,i):B0(g)=b}\mathcal{I}_b\leftarrow\{(g,i):B_0^{(g)}=b\}
19:p^b←1∣Ib∣∑(g,i)∈Ib1[Cˉ(g,i)>1]\hat{p}_b\leftarrow\frac{1}{|\mathcal{I}_b|}\sum_{(g,i)\in\mathcal{I}_b}\mathbf{1}[\bar{C}^{(g,i)}>1]
20:λb←min⁡{[λb+β(p^b−δ)]+,Λmax⁡/∣B∣}\lambda_b\leftarrow\min\{[\lambda_b+\beta(\hat{p}_b-\delta)]_+,\Lambda_{\max}/|\mathcal{B}|\}
21:end for
22:end for

Table 2 (PDF p. 23).

Experimental Setup

We describe the environments, data splits, cost maps, budget grids, and budget-conditioning instructions used in our experiments. Each environment uses the budget-augmented POMDP of § 3.2. The total budget B0B_0 is given at the start of the episode, and the remaining budget btb_t is reported after each turn. All evaluations use four rollouts per evaluation instance and budget, while training uses groups of eight rollouts.

AppWorld

AppWorld ([25]) is an interactive coding-agent benchmark in which the agent completes digital tasks by writing Python code that calls simulated app APIs. Each executed code block is one model turn, including the terminal apis.supervisor.complete_task() call.

We train on the AppWorld training split and evaluate on the 168 tasks in test-normal. With four rollouts per task, this gives 672 rollouts per budget. We also evaluate under distribution shift on the 417 tasks in test-challenge. AppWorld labels each task as easy, medium, or hard, which we use to split spend by difficulty in Figure 4(a). Unless stated otherwise, uncertainty bands for binary success and compliance rates show ±1\pm1 standard deviation of the binomial rate estimate.

Episodes have a horizon of Tmax⁡=40T_{\max}=40 turns for Qwen3.5-9B and Tmax⁡=50T_{\max}=50 turns for Qwen3.5-4B. These horizons exceed the largest training step budgets, allowing overspending to remain observable rather than being hidden by the episode horizon.

ASTRA

ASTRA is a personal-assistant benchmark built on ToolSandbox ([18]), with tasks involving email, calendars, messages, and contacts. Its native interface uses structured tool calls, whereas AppWorld uses Python code. We expose all ASTRA tools through a single all namespace and retain AppWorld’s Python-REPL interface. Calls therefore take the form apis.all.api_name(kwarg=val). This keeps the action interface aligned with AppWorld for the transfer experiments of § 4.4. ASTRA grades success by similarity to a set of reference milestones. We binarise this score at a threshold of 0.8 for our evaluation.

We use ASTRA only to evaluate the AppWorld-trained policies without retraining. The evaluation covers 3116 ASTRA scenarios under step budgets from 2 to 14, with a horizon of 40 turns. It uses the AppWorld step-budget block of Prompt 3. The ASTRA task instruction retains the AppWorld REPL framing and general instructions where possible and differs only where required by the ASTRA tool interface. Prompts 1 and 2 give both task instructions in full.

BabyAI

We use a text interface to BabyAI ([6]), a partially observed gridworld environment built on MiniGrid. The agent receives textual observations and selects moves from a small fixed vocabulary, including turn left, turn right, move forward, pick up, drop, and toggle. This provides a task and environment type distinct from the multi-turn coding settings of AppWorld and ASTRA.

We budget BabyAI by model turns rather than individual moves. Each action block may contain multiple moves and costs one unit regardless of how many moves it contains. This parallels the AppWorld step budget, where an agent can batch multiple API calls within a single turn. The moves execute sequentially without intermediate observations. An invalid move invalidates the entire block while still consuming the turn. The agent can therefore conserve budget by batching moves, at the cost of acting further ahead without observing intermediate states.

We use 15 BabyAI levels covering a range of navigation and object-interaction tasks. Each level defines a family of related tasks rather than a single fixed environment. We generate concrete task instances from each level using fixed random seeds. A seed determines the mission, environment layout, object and door placement, and the agent’s initial state.

We construct non-overlapping training and evaluation sets using disjoint seed pools. No concrete task instance therefore appears in both splits, although both cover the same level families. The evaluation seeds are fixed and shared across methods, so every policy is evaluated on the same missions and environment configurations.

Cost Maps and Budgeted Quantities

We vary the budgeted quantity through the cost map κ\kappa while leaving the rest of the training framework unchanged. Table 4 gives the three cost maps used in our experiments.

Unitκ(at)\kappa(a_t)Interpretation of B0B_0Domains
Steps11Model turns available to the agentAW, AS, BA
Tool calls#\# API calls in ata_tAPI calls available to the agentAW
Tokens∣at∣|a_t| in tokensGenerated tokens, including reasoning and actionsAW

Table 4. Budgeted quantities. Quantities defined by the cost map κ\kappa. The domain abbreviations denote AppWorld, ASTRA, and BabyAI.

Under a step budget, each model turn costs one unit. On BabyAI, one model turn may contain several primitive moves. Under a tool-call budget, each API call is charged independently. Under a token budget, all tokens generated by the policy are charged, including its reasoning and actions. Tokens in the task instruction and environment observations are not charged.

Budget grids. On AppWorld, we construct a separate six point training grid for each model and cost unit. The grid is based on the empirical resource use of GRPO-Std, trained with the shared Dr. GRPO pipeline and a budget-independent task reward. We select budgets at the 1st, 10th, 25th, 50th, 75th, and 90th percentiles of its spend distribution. This produces budgets spanning the observed range of task demands, from highly constrained settings to comparatively generous ones. All reward formulations use the same training and evaluation grids within each model and cost unit.

All AppWorld evaluation grids include training budgets and unseen budgets between the training points. The step and API-call grids also include budgets below and above the training range; the token grids remain within it. Table 5 gives the grids. For BabyAI, all methods and both model scales use the same six turn budgets, {5,7,11,16,23,34}\{5, 7, 11, 16, 23, 34\}, for training and evaluation.

UnitModelTraining grid B\mathcal{B}Evaluation grid Beval\mathcal{B}_{\mathrm{eval}}
StepsQwen3.5-9B{10,15,18,22,25,29}\{10, 15, 18, 22, 25, 29\}{4,8,10,12,15,18,20,22,25,27,29,32,36}\{4, 8, 10, 12, 15, 18, 20, 22, 25, 27, 29, 32, 36\}
Qwen3.5-4B{10,15,17,20,24,26}\{10, 15, 17, 20, 24, 26\}{4,8,9,10,11,12,15,17,18,20,21,22,24,26,29,31,32,34,36}\{4, 8, 9, 10, 11, 12, 15, 17, 18, 20, 21, 22, 24, 26, 29, 31, 32, 34, 36\}
Tool callsQwen3.5-9B{10,15,18,22,26,29}\{10, 15, 18, 22, 26, 29\}{6,10,12,15,18,20,22,24,26,29,32,36}\{6, 10, 12, 15, 18, 20, 22, 24, 26, 29, 32, 36\}
Qwen3.5-4B{13,15,17,19,22,25}\{13, 15, 17, 19, 22, 25\}{6,10,11,12,13,14,15,17,19,20,21,22,24,25,26,27,30,31,35,36}\{6, 10, 11, 12, 13, 14, 15, 17, 19, 20, 21, 22, 24, 25, 26, 27, 30, 31, 35, 36\}
TokensQwen3.5-9B{896,1408,1856,2432,3136,3904}\{896, 1408, 1856, 2432, 3136, 3904\}{896,1152,1408,1600,1856,2112,2432,2752,3136,3520,3904}\{896, 1152, 1408, 1600, 1856, 2112, 2432, 2752, 3136, 3520, 3904\}
Qwen3.5-4B{1452,2073,2489,3066,4264,5186}\{1452, 2073, 2489, 3066, 4264, 5186\}{1452,1728,2073,2240,2489,2752,3066,3584,4264,4672,5186}\{1452, 1728, 2073, 2240, 2489, 2752, 3066, 3584, 4264, 4672, 5186\}
TurnsQwen3.5-4B, 9B{5,7,11,16,23,34}\{5, 7, 11, 16, 23, 34\}{5,7,11,16,23,34}\{5, 7, 11, 16, 23, 34\}

Table 5. Budget grids. Training and evaluation budget grids by cost unit and model. All methods use the same grids.

Budget Conditioning and Prompt Templates

At the start of each episode, the policy receives a domain-specific task instruction followed immediately by a <budget> block. The block states the total budget B0B_0. After every model turn, the environment appends the remaining budget btb_t to the next observation. The policy therefore observes both the original and remaining budgets throughout the episode, as required by Equation (4). Prompt 1 gives the AppWorld task instruction, and Prompt 2 gives its ASTRA adaptation. AppWorld uses separate budget blocks for step, API-call, and token budgets, which are given in Prompts 3 to 5. Prompts 6 and 7 give the BabyAI task instruction and turn-budget block. All models, methods, and splits within a domain and cost unit receive the same text. Only the task-specific fields and total budget vary, together with the user and date fields where applicable.

Prompt 1 AppWorld Task Instruction

I am your supervisor and you are a super intelligent AI Assistant whose job is to achieve my day-to-day tasks completely autonomously.

To do this, you will need to interact with app/s (e.g., spotify, venmo etc) using their associated APIs on my behalf. For this you will undertake a multi-step conversation using a python REPL environment. That is, you will write the python code and the environment will execute it and show you the result, based on which, you will write python code for the next step and so on, until you’ve achieved the goal. This environment will let you interact with app/s using their associated APIs on my behalf.

Here are three key APIs that you need to know to get more information

# To get a list of apps that are available to you.
print(apis.api_docs.show_app_descriptions())
# To get the list of apis under any app listed above, e.g. spotify
print(apis.api_docs.show_api_descriptions(app_name=’spotify’))
# To get the specification of a particular api, e.g. spotify app’s login api
print(apis.api_docs.show_api_doc(app_name=’spotify’, api_name=’login’))

Each code execution will produce an output that you can use in subsequent calls. Using these APIs, you can now generate code, that I will execute, to solve the task.

Key instructions:

(1) Make sure to end code blocks with ` followed by a newline(\n).

(2) Remember you can use the variables in your code in subsequent code blocks.

(3) You can use the “supervisor” app to get information about my accounts and use the “phone” app to get information about friends and family.

(4) Always look at API specifications (using apis.api_docs.show_api_doc) before calling an API.

(5) Write small chunks of code and only one chunk of code in every step. Make sure everything is working correctly before making any irreversible change.

(6) Many APIs return items in “pages”. Make sure to run through all the pages by looping over page_index.

(7) Once you have completed the task, make sure to call apis.supervisor.complete_task(). If the task asked for some information, return it as the answer argument, i.e. call apis.supervisor.complete_task(answer=<answer>). Many tasks do not require an answer, so in those cases, just call apis.supervisor.complete_task() i.e. do not pass any argument.

(8) Do exactly what the task asks for, nothing more. Do not create, modify, or delete any data that the task does not explicitly require. If the task asks you to read information, do not write or modify anything. If the task asks you to perform a specific action, perform only that action using the most direct approach available.

(9) If the task mentions a message, email, or request from someone, always read the actual content of that message/email first — it may contain important details, constraints, or filters not stated in the task description.

(10) When a task depends on the current date, time, or day of the week, always determine it programmatically (e.g., from datetime import datetime; datetime.now()) — never guess or assume.

(11) When filtering entities by category or relationship (e.g., “friends”, “coworkers”), verify membership using the primary/authoritative data source for that relationship — do not infer it from other app-specific lists.

(12) When a task references a time range like “last N days including today”, today counts as day 1 — so the start date is N-1 days ago, not N days ago.

(13) When writing structured output files (CSV, etc.), use minimal formatting — do not add unnecessary quoting or encoding around values.

(14) You should follow three phases: First, explore the APIs and all relevant data. You can explore a bit more alternative data just to go sure that you did not miss anything. Second, summarize your findings and compare them to the task again. Think about whether you might have missed something. Look it up and verify. Third, once you have all information, start conducting the task and complete it. Before you finish, verify that every aspect of the task has been accounted for.

Using these APIs, now generate code to solve the actual task:

My name is: {{main_user.first_name}} {{main_user.last_name}}. My personal email is {{main_user.email}} and phone number is {{main_user.phone_number}}. The current date is {{main_user.session_start_time}}. Task: {{ input_str }}

〈budget-conditioning block, appended here〉

Prompt 2 ASTRA Task Instruction, aligned with Prompt 1

I am your supervisor and you are a super intelligent AI Assistant whose job is to achieve my day-to-day tasks completely autonomously.

To do this, you will need to interact with apps using their associated APIs on my behalf. For this you will undertake a multi-step conversation using a python REPL environment. That is, you will write the python code and the environment will execute it and show you the result, based on which, you will write python code for the next step and so on, until you’ve achieved the goal. This environment will let you interact with these APIs on my behalf.

Here are three key APIs that you need to know to get more information

To get a list of apps that are available to you (this only ever lists the single ’all’ app).

print(apis.api_docs.show_app_descriptions())

To get the list of apis under the ’all’ app.

print(apis.api_docs.show_api_descriptions(app_name=’all’))

To get the specification of a particular api, e.g. the ’all’ app’s send_email api

print(apis.api_docs.show_api_doc(app_name=’all’, api_name=’send_email’))

Each code execution will produce an output that you can use in subsequent calls. Using these APIs, you can now generate code, that I will execute, to solve the task.

Key instructions:

  1. Make sure to end code blocks with ``` followed by a newline(\n).

  2. Remember you can use the variables in your code in subsequent code blocks.

  3. There is exactly one app, named ’all’, which holds every task API. Use the apis.api_docs.* calls only to look up documentation, and call every task API as apis.all.api_name(kwarg1=val1, ...). Do not invent other app names, and do not paste documentation output back as code.

  4. Always look at API specifications (using apis.api_docs.show_api_doc) before calling an API.

  5. Call APIs using only keyword arguments like apis.all.api_name(kwarg1=val1, ...)

  6. Write small chunks of code and only one chunk of code in every step. Make sure everything is working correctly before making any irreversible change.

  7. Many APIs return items in “pages”. Make sure to run through all the pages by looping over page_index.

  8. Once you have completed the task, make sure to call apis.supervisor.complete_task(). If the task asked for some information, return it as the answer argument, i.e. call apis.supervisor.complete_task(answer=<answer>). Many tasks do not require an answer, so in those cases, just call apis.supervisor.complete_task() i.e. do not pass any argument.

  9. Do exactly what the task asks for, nothing more. Do not create, modify, or delete any data that the task does not explicitly require. If the task only asks you to read information, do not write or modify anything. If the task asks you to perform a specific action, perform only that action using the most direct approach available.

  10. If the task mentions a message, email, or request from someone, always read the actual content of that message/email first — it may contain important details, constraints, or filters not stated in the task description.

  11. When a task depends on the current date, time, or day of the week, always determine it programmatically — never guess or assume.

  12. When filtering entities by category or relationship (e.g., “friends,” “coworkers”), verify membership using the primary/authoritative data source for that relationship — do not infer it from other app-specific lists.

  13. When a task references a time range like “last N days including today”, today counts as day 1 — so the start date is N-1 days ago, not N days ago.

  14. When writing structured output files (CSV, etc.), use minimal formatting — do not add unnecessary quoting or encoding around values.

  15. You should follow three phases: First, explore the APIs and all relevant data. You can explore a bit more alternative data just to go sure that you did not miss anything. Second, summarize your findings and compare them to the task again. Think about whether you might have missed something. Look it up and verify. Third, once you have all information, start conducting the task and complete it. Before you finish, verify that every aspect of the task has been accounted for.

Using these APIs, now generate code to solve the actual task:

The current date is {{session_start_time}}.

Task: {{input_str}}

〈budget-conditioning block, appended here〉

Prompt 3 Budget-conditioning block for step budgets on AppWorld and ASTRA

<budget>You have a budget of B0B_0 steps.

Only the code blocks you send count toward your step budget. After each step you are told how many steps remain.

Before sending a code block, think carefully about how many steps you have left and plan how best to use them to complete the task within budget. Because a whole block costs just one step, batch several API calls into a single block whenever they don’t depend on each other’s results — making one call per step wastes budget. Only split work across steps when a later call genuinely needs an earlier call’s output.

Solve the task successfully while staying strictly within your allocated step budget.</budget>

Prompt 4 Budget-conditioning block for API-call budgets on AppWorld

<budget>You have a budget of B0B_0 API calls.

Every apis.<app>.<endpoint>() call you make costs 1 from your budget — this includes apis.api_docs lookups, not just calls to the task apps themselves. Thinking and plain code are free, and it doesn’t matter how many turns your calls are spread across: batching several into one turn costs the same as spreading them out — only making fewer calls total reduces cost. After each step you are told how many API calls remain.

Before making a call, check whether you already have what you need from an earlier call, an earlier doc lookup, or the task description — don’t re-look up something you’ve already seen this episode, and don’t make a call just in case. Plan which calls are actually necessary to solve the task.

Solve the task successfully while staying strictly within your allocated API-call budget.</budget>

Prompt 5 Budget-conditioning block for token budgets on AppWorld

<budget>You have a budget of B0B_0 tokens.

Every token you generate counts toward your token budget: your reasoning between <think> and </think>, plus the code you write after </think>. The task description and the environment’s replies are free — only your own output is charged.

After each step you are told how many tokens you have left and how many your previous step used, so you can calibrate as you go. Before each step, decide the total number of tokens that step will use across your reasoning and your code, state that number in your first line, and keep to it — think enough to act well but no more, since verbose reasoning spends budget just like long code.

Batch independent API calls into one block whenever they don’t depend on each other’s results; only split work across steps when a later call needs an earlier call’s output.

Solve the task successfully while staying strictly within your allocated token budget.</budget>

Prompt 6 BabyAI task instruction

You are an agent in a 2D gridworld. You see only a 7×77 \times7 area in front of you, and parts of the grid remain hidden until you explore them. At each turn, you receive a text description of what you can currently see and the direction you face. You reply with one or more moves. The available moves are listed below.

left turns left by 90 degrees without moving.

right turns right by 90 degrees without moving.

forward moves one tile forward.

pick picks up the object directly in front of you.

drop drops the object you are carrying.

toggle opens, closes, or activates the object directly in front of you.

Give one or more moves in a single action block, with one move per line. The moves execute sequentially from your current state. An unrecognised move invalidates the entire block. None of its moves are executed, but the turn is still consumed.

Task instruction {{mission}}

⟨budget-conditioning block, appended here⟩

Prompt 7 Budget-conditioning block for BabyAI turn budgets

<budget>You have a budget of B0B_0 turns. After each turn, you will be told how many turns remain.

Each action block you send costs one turn. You may batch several moves into one action block when you are confident about the sequence. The moves execute sequentially without intermediate observations, so use a new turn when you need to observe the result before deciding what to do next.

Solve the task successfully while staying strictly within your allocated turn budget.</budget>

At every subsequent turn, the environment appends the remaining budget as <budget>Budget remaining btb_t of B0B_0 {{ unit }}.</budget>, with the unit matching the cost map. Once the policy exceeds its budget, the message reports zero remaining and states how far the policy is over budget. Under a token budget, it also reports the tokens used by the preceding turn and repeats the request to estimate the length of the next turn.

The guidance differs by resource type because each budget can be conserved in a different way. Batching API calls into one code block conserves steps but does not conserve API calls. Token budgets charge both reasoning and code. BabyAI allows several primitive moves to be placed in one turn, but the agent receives no intermediate observation between those moves.

Models and Dr. GRPO Settings

We train Qwen3.5 at 4B and 9B parameters and report both scales throughout. Every method continues training from each model’s released post-trained checkpoint, with no supervised warm start of our own. All parameters are updated, with no LoRA, adapters, or frozen layers.

Optimisation uses the group-centred Dr. GRPO advantage Equation (E.13), with neither length nor standard-deviation normalisation, at γ=1\gamma= 1, for 120 updates on Qwen3.5-9B and 80 on Qwen3.5-4B. The learning rate is flat at 3×10−63 \times10^{-6} with no schedule. Thinking is enabled, with a 768-token allowance on Qwen3.5-9B and 512 on Qwen3.5-4B. Under the step and tool-call cost maps these tokens do not count against the budget, whereas under the token cost map of Appendix § 11.§ 4 they are priced.

Each iteration draws KK groups (Equation (E.13)), with K=8K = 8 on Qwen3.5-9B and K=32K = 32 on Qwen3.5-4B, each comprising G=8G = 8 completions for a shared task and a shared budget, sampled at temperature 1.0 with nucleus and top-kk truncation disabled. The policy update is the clipped surrogate Equation (E.14) with symmetric clip range ϵ=0.2\epsilon= 0.2 and no KL penalty or entropy bonus, so the return is shaped only by each method’s own objective (§ 3.3). Qwen3.5-9B takes 2 epochs per update with gradient accumulation over 8 microbatches of at most 4 segments, and Qwen3.5-4B takes 1 epoch over 2 microbatches of at most 8. Before the update, groups whose advantages are all zero are dropped, and negative-advantage segments are subsampled so that they make up at most a quarter of the batch. This additional sampling step changes the relative weighting of positive and negative advantages; the unfiltered gradient calculation in Appendix § 10.§ 4 does not establish unbiasedness of the implemented update.

Budget and Constraint Settings

Budgets are drawn uniformly from B\mathcal{B}, so 1/pB(b)=∣B∣1/p_{\mathcal{B}}(b) = |\mathcal{B}| and the effective price of Dual and Rate (Figure 1) is Λb=∣B∣λb\Lambda_b = |\mathcal{B}|\lambda_b. The AppWorld horizons of Appendix § 11.§ 1 exceed the largest training step budgets, so step-budget overspending remains observable to both the dual and soft-overlong penalties. The ramp of Equation (C.1) saturates at twice the budget, so under the step cost map it reaches its maximum of α\alpha only when 2b≤Tmax⁡2b \le T_{\max}. On AppWorld, the top three budgets of the Qwen3.5-9B step grid and the top budget of the Qwen3.5-4B step grid fall outside this range. At these budgets, the penalty grades overspending across the entire reachable range without saturating.

We set the permitted overspend rate to δ=0.05\delta= 0.05. The dual step size is β=0.01\beta= 0.01 for Qwen3.5-9B and β=0.04\beta= 0.04 for Qwen3.5-4B. Under the uniform six-rung budget prior, these give effective-price step sizes of ∣B∣β=0.06|\mathcal{B}|\beta= 0.06 and 0.240.24, respectively. We update the dual using the raw within-batch overspend rate in Equation (E.15), without smoothing across batches. The soft-overlong coefficient is α=0.5\alpha= 0.5, following the reward-scale argument in Appendix § 9.

Multipliers are initialised at λb=0\lambda_b = 0 for every budget. For Rate, they are projected onto [0,pB(b)][0,p_B(b)], giving an effective-price cap of Λb≤1\Lambda_b \le1. For Dual, they are projected onto [0,(1−α)pB(b)][0,(1-\alpha)p_B(b)], giving an effective-price cap of Λb≤1−α=0.5\Lambda_b \le1-\alpha= 0.5. These are the largest prices for which an overspending success is not valued below a compliant failure under the corresponding reward formulation.

Compute

Training runs on 8× B200 GPUs with tensor-parallel vLLM generation and an FSDP trainer. Evaluation runs on 8× H100 GPUs for Qwen3.5-9B and 4× H100 for Qwen3.5-4B.

HyperparameterValue
Model and optimisation
Model families and scalesQwen3.5 4B and 9B (released post-trained checkpoints)
Fine-tuningfull-parameter, no LoRA or adapters
OptimiserDr. GRPO, γ=1\gamma= 1
Training updates120 (Qwen3.5-9B), 80 (Qwen3.5-4B)
Learning rateflat, no schedule, 3×10−63 \times10^{-6}
Budget family and constraint
Budget grid B\mathcal{B}six rungs per model and cost unit (Table 5)
Budget prior pBp_{\mathcal{B}}uniform on B\mathcal{B}
Episode horizon Tmax⁡T_{\max}AppWorld 40 (Qwen3.5-9B) and 50 (Qwen3.5-4B); BabyAI 50; ASTRA 40 at evaluation
Overspend rate δ\delta0.05
Dual step β\beta0.01 (Qwen3.5-9B), 0.04 (Qwen3.5-4B)
Initial multipliers λb\lambda_b0 for all bb, with Λb\Lambda_b capped at 1 for Rate and at 1−α=0.51-\alpha=0.5 for Dual
Soft-overlong coefficient α\alpha0.5
Rollout collection and policy update
Groups per iteration KK8 (Qwen3.5-9B), 32 (Qwen3.5-4B)
Group size GG8
Sampling temperature1.0 (top-pp, top-kk disabled)
Thinking tokens768 (Qwen3.5-9B), 512 (Qwen3.5-4B)
PPO clip range ϵ\epsilon0.2 (symmetric)
PPO epochs per update2 (Qwen3.5-9B), 1 (Qwen3.5-4B)
Gradient accumulation8 microbatches of ≤4\leq4 segments (Qwen3.5-9B), 2 of ≤8\leq8 (Qwen3.5-4B)
Gradient-norm clip1.0
Entropy and KL coefficients0, no KL term

Table 6. Training hyperparameters. Budget grids are given by model and cost unit in Table 5. Settings that differ between model scales or reward formulations are stated explicitly. All other settings are shared across methods and domains.

What the dual costs to train. Dual and Linear-Mag provide a direct comparison of the additional algorithmic cost of the dual update. The dual introduces only ∣B∣|\mathcal{B}| scalar multipliers, which are updated once per iteration using Equation (E.15). It requires no additional model parameters, rollouts, forward passes, or backward passes. Both methods use the same rollout configuration, optimiser settings, and hardware. Their realised compute may nevertheless differ because the learned policies generate trajectories of different lengths and advantage filtering may retain different numbers of segments. We therefore treat the methods as matched in training configuration rather than claiming identical wall-clock or optimiser cost.

Additional Results

Across-Budget Utility Metrics

We define the summary metrics reported in Table 2. An evaluation setting is a combination of model scale, environment, and budget unit. We consider eight settings. These comprise AppWorld step, tool-call, and token budgets and BabyAI turn budgets for each of Qwen3.5-9B and Qwen3.5-4B.

We compare the ten budget-shaping mechanisms and exclude Base and GRPO-Std because their rewards do not depend on the budget.

Metrics. Let R\mathcal{R} denote the set of evaluation settings and let Mr\mathcal{M}_r denote the methods evaluated in setting r∈Rr \in\mathcal{R}. Let BrB_r be the evaluation budget grid for setting rr, and let Um,r(b)U_{m,r}(b) denote the observed budget utility of method mm at budget bb. The highest observed utility at each budget is

Ur∗(b)=max⁡m∈MrUm,r(b).(33)U_r^*(b) = \max_{m\in\mathcal{M}_r} U_{m,r}(b). \tag*{(33)}

For each method mm, let Rm⊆R\mathcal{R}_m \subseteq\mathcal{R} contain the settings in which it was evaluated. We define

Win⁡(m)=1∣Rm∣∑r∈Rm1∣Br∣∑b∈Br1[Um,r(b)=Ur∗(b)],(34)\operatorname{Win}(m) = \frac{1}{|\mathcal{R}_m|} \sum_{r\in\mathcal{R}_m} \frac{1}{|\mathcal{B}_r|} \sum_{b\in\mathcal{B}_r} \mathbf{1}[U_{m,r}(b)=U_r^*(b)], \tag*{(34)}
NearBest⁡ϵ(m)=1∣Rm∣∑r∈Rm1∣Br∣∑b∈Br1[Um,r(b)≥Ur∗(b)−ϵ],(35)\operatorname{NearBest}_{\epsilon}(m) = \frac{1}{|\mathcal{R}_m|} \sum_{r\in\mathcal{R}_m} \frac{1}{|\mathcal{B}_r|} \sum_{b\in\mathcal{B}_r} \mathbf{1}[U_{m,r}(b)\ge U_r^*(b)-\epsilon], \tag*{(35)}
Regret⁡(m)=1∣Rm∣∑r∈Rm1∣Br∣∑b∈Br[Ur∗(b)−Um,r(b)].(36)\operatorname{Regret}(m) = \frac{1}{|\mathcal{R}_m|} \sum_{r\in\mathcal{R}_m} \frac{1}{|\mathcal{B}_r|} \sum_{b\in\mathcal{B}_r} [U_r^*(b)-U_{m,r}(b)]. \tag*{(36)}

Win rate measures how often a method attains the highest observed utility at an individual budget. It is a strict measure and can be sensitive to small differences between methods. Near-best rate measures how often a method remains within ϵ\epsilon of the best observed utility and is therefore less sensitive to small estimation differences. Mean regret measures the average utility lost relative to the best observed method and accounts for the magnitude of each difference.

We use ϵ=0.02\epsilon=0.02, corresponding to two percentage points of budget utility. Exact ties count as wins for every tied method, so win rates need not sum to 100%. Each metric is first averaged over budgets within a setting and then averaged equally across settings. Settings with denser evaluation grids therefore receive no additional weight. Win and near-best rates are reported as percentages, while regret is reported in percentage points.

Uncertainty. Budget evaluations within a setting share a trained policy and overlapping tasks, so individual budget points are not independent replicates. Table 2 reports descriptive point estimates, without confidence intervals or a test of differences between methods. The separate seed study below assesses training variability for two objectives in one setting; it does not quantify uncertainty for every pooled ranking.

Seed Robustness and Longer Training

The comparisons in Section 4.2 use one training seed per method and setting. To check how much of the spread between methods is training noise, we retrain Sigmoid-Gate and Linear-Mag on Qwen3.5-9B with AppWorld step budgets using two further seeds, and continue these runs from the 120 updates of the main results to 200 updates. Figure 7 reports their budget utility on test-normal.

Budget utility curves for 120 and 200 updates

Figure 7. Seed robustness and longer training. Budget utility U(b)U(b) on AppWorld test-normal under step budgets for Qwen3.5-9B Sigmoid-Gate and Linear-Mag. Two additional seeds are evaluated after 120 updates (left) and 200 updates (right), with the main 120-update seed shown in both panels. Dotted lines mark training budgets. Bands show ±1\pm1 standard error over tasks.

After 120 updates, the three Linear-Mag seeds differ by around ten percentage points at intermediate budgets, and the Sigmoid-Gate seeds by a few points. The broad ranking of the two methods is preserved across seeds and with longer training, with Sigmoid-Gate generally achieving higher utility at tighter and intermediate budgets. The curves become closer and can cross at the loosest budgets, where the budget is less restrictive. Training for 200 updates improves utility at many budgets.

Resource Use on BabyAI

Budget utility measures whether a task is completed within budget, but it does not show how a policy adjusts its spending or how severely it exceeds the budget when it fails to comply. Figure 8 therefore reports mean trajectory spend and conditional overspend magnitude across BabyAI turn budgets.

Figure 8. Resource use on BabyAI. (a) Mean turns used and (b) mean percentage overspend among rollouts that exceed the budget, for Qwen3.5-9B and 4B. Horizontal axes show the stated turn budget BB, with dotted lines marking training budgets. Overspend axes are capped at 100%.

Mean spend is the average number of turns used by the policy. It shows whether resource use changes with the available budget. Lower spend is not necessarily better because using additional turns may improve task success. We define conditional overspend magnitude as

Excess⁡(b)=E[Cˉ(ζ,b)−1∣Cˉ(ζ,b)>1].(37)\operatorname{Excess}(b)=\mathbb{E}\left[\bar{C}(\zeta,b)-1 \mid\bar{C}(\zeta,b)>1\right]. \tag*{(37)}

This is the expected relative excess among trajectories that exceed the budget. Compliance measures how often the policy stays within budget, while Excess(bb) measures the severity of its violations. We report Excess(bb) as a percentage in the figure.

Violations are generally most severe under the tightest budgets and become less severe as the budget grows.

Qualitative Examples of Budget Use

BabyAI: batching moves under a turn budget

Qwen3.5-9B Sigmoid-Gate, OpenTwoDoors, B=7B = 7. The policy first plans the route against its stated allowance: “This should take 5 turns maximum, well within my 7 turn budget.” It then sends the seven-move trip to the second door in one action block and completes the task in four turns.

AppWorld: batching tool operations under a step budget

Qwen3.5-9B Sigmoid-Gate training rollout, B=15B = 15, two steps remaining. The policy states: “I can batch multiple delete calls in one step,” and combines independent tool operations in a single code block.

References

  1. [1]Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22–31. Pmlr, 2017.arxiv.org/abs/1705.10528
  2. [2]Pranjal Aggarwal and Sean Welleck. L1: Controlling how long a reasoning model thinks with reinforcement learning. In Second Conference on Language Modeling, 2025. URL https://openreview.net/forum?id=4jdlxBXNve.arxiv.org/abs/2503.04697
  3. [3]Eitan Altman. Constrained Markov decision processes. Routledge, 2021.DOI
  4. [4]Daman Arora and Andrea Zanette. Training language models to reason efficiently. Advances in Neural Information Processing Systems, 38:60770–60808, 2026.arxiv.org/abs/2502.04463
  5. [5]Nicolas Carrara, Edouard Leurent, Romain Laroche, Tanguy Urvoy, Odalric-Ambrym Maillard, and Olivier Pietquin. Budgeted reinforcement learning in continuous state space. Advances in neural information processing systems, 32, 2019.arxiv.org/abs/1903.01004
  6. [6]Maxime Chevalier-Boisvert, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio. BabyAI: First steps towards grounded language learning with a human in the loop. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=rJeXCo0Yx.
  7. [8]Mehul Damani, Idan Shenfeld, Andi Peng, Andreea Bobu, and Jacob Andreas. Learning how hard to think: Input-adaptive allocation of lm computation. In International Conference on Learning Representations, volume 2025, pages 102783–102802, 2025.arxiv.org/abs/2410.04707
  8. [9]Peter Geibel and Fritz Wysotzki. Risk-sensitive reinforcement learning applied to control under constraints. Journal of Artificial Intelligence Research, 24:81–108, 2005.
  9. [10]Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025.
  10. [11]Tingxu Han, Zhenrong Wang, Chunrong Fang, Shiyu Zhao, Shiqing Ma, and Zhenyu Chen. Token-budget-aware llm reasoning. In Findings of the Association for Computational Linguistics: ACL 2025, pages 24842–24855, 2025.
  11. [12]William B Haskell and Rahul Jain. A convex analytic approach to risk-aware markov decision processes. SIAM Journal on Control and Optimization, 53(3):1569–1598, 2015.DOI
  12. [13]Yushu Li, Wenlong Deng, Jiajin Li, and Xiaoxiao Li. Spend less, reason better: Budget-aware value tree search for llm agents. arXiv preprint arXiv:2603.12634, 2026.arxiv.org/abs/2603.12634
  13. [14]Chang Liu, Yiran Zhao, Lawrence Liu, Yaoqi Ye, Csaba Szepesvári, and Lin F Yang. Laconic: Length-aware constrained reinforcement learning for llm. arXiv preprint arXiv:2602.14468, 2026.arxiv.org/abs/2602.14468
  14. [15]Shih-Yang Liu, Xin Dong, Ximing Lu, Shizhe Diao, Mingjie Liu, Min-Hung Chen, Hongxu Yin, Yu-Chiang Frank Wang, Kwang-Ting Cheng, Yejin Choi, et al. Dler: Doing length penalty right-incentivizing more intelligence per token via reinforcement learning. arXiv preprint arXiv:2510.15110, 2025a.
  15. [16]Tengxiao Liu, Zifeng Wang, Jin Miao, I Hsu, Jun Yan, Jiefeng Chen, Rujun Han, Fangyuan Xu, Yanfei Chen, Ke Jiang, et al. Budget-aware tool-use enables effective agent scaling. arXiv preprint arXiv:2511.17006, 2025b.arxiv.org/abs/2511.17006
  16. [17]Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. Understanding rl-zero-like training: A critical perspective. In Second Conference on Language Modeling, 2025c. URL https://openreview.net/forum?id=5PAF7P2Y.
  17. [18]Jiarui Lu, Thomas Holleis, Yizhe Zhang, Bernhard Aumayer, Feng Nan, Haoping Bai, Shuang Ma, Shen Ma, Mengyu Li, Guoli Yin, et al. Toolsandbox: A stateful, conversational, interactive evaluation benchmark for llm tool use capabilities. In Findings of the Association for Computational Linguistics: NAACL 2025, pages 1160–1183, 2025.
  18. [20]John Schulman, Filip Wolski, Parafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.arxiv.org/abs/1707.06347
  19. [21]Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models, 2024. URL https://arxiv.org/abs/2402.03300, 2(3):5, 2024.
  20. [22]Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.
  21. [23]Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In International conference on machine learning, pages 9133–9143. PMLR, 2020.arxiv.org/abs/2007.03964
  22. [24]Kimi Team, Tongtong Bai, Yifan Bai, Yiping Bao, Jianfeng Cai, Xinyuan Cai, Peizhou Cao, Yuxuan Cao, Ziwei Chai, Y Charles, et al. Kimi k3: Open frontier intelligence. arXiv preprint arXiv:2607.24653, 2026.
  23. [25]Harsh Trivedi, Tushar Khot, Mareike Hartmann, Ruskin Manku, Vinty Dong, Edward Li, Shashank Gupta, Ashish Sabharwal, and Niranjan Balasubramanian. Appworld: A controllable world of apps and people for benchmarking interactive coding agents. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 16022–16076, 2024.arxiv.org/abs/2407.18901
  24. [26]Hao Wen, Xinrui Wu, Yi Sun, Feifei Zhang, Liye Chen, Jie Wang, Yunxin Liu, Yunhao Liu, Ya-Qin Zhang, and Yuanchun Li. Budgetthinker: Empowering budget-aware llm reasoning with control tokens. arXiv preprint arXiv:2508.17196, 2025.arxiv.org/abs/2508.17196
  25. [27]Zidi Xiu, David Q Sun, Kevin Cheng, Maitrik Patel, Yizhe Zhang, Jiarui Lu, Omar Attia, Raviteja Vemulapalli, Oncel Tuzel, Meng Cao, et al. Astra-bench: Evaluating tool-use agent reasoning and action planning with personal user context. arXiv preprint arXiv:2603.01357, 2026.arxiv.org/abs/2603.01357
  26. [28]Anyi Xu, B Li, Bangcai Lin, Bing Xue, BingCheng Xian, Bingzheng Xu, Bochao Wu, Bowei Zhang, Boyi Deng, CC Yu, et al. Deepseek-v4. 1-flash: Pushing the limits of kv cache compression. arXiv preprint arXiv:2609.19969, 2026.arxiv.org/abs/2609.19969
  27. [29]Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Weinan Dai, Tiantian Fan, Gaohong Liu, Lingjun Liu, et al. Dapo: An open-source llm reinforcement learning system at scale. Advances in Neural Information Processing Systems, 38:113222–113244, 2026.arxiv.org/abs/2503.14476
  28. [30]Caiqi Zhang, Menglin Xia, Xuchao Zhang, Daniel Madrigal, Ankur Mallick, Samuel Kessler, Victor Ruehle, and Saravan Rajmohan. Budget-aware agentic routing via boundary-guided training. arXiv preprint arXiv:2602.21227, 2026.arxiv.org/abs/2602.21227

Paper details

vlnc:W_59mer5gw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents