Curriculum Design for Trajectory-Constrained Agent: Compressing Chain-of-Thought Tokens in LLMs
Authors: Georgios Tzannetos
Parameswaran Kamalaruban
Adish Singla
Venue: NeurIPS 2025 poster ()
Keywords: Curriculum Design
Large Language Models
Reinforcement Learning
Chain-of-Thought Reasoning
Primary area: reinforcement_learning
TL;DR: We propose a curriculum strategy for guiding the training of agents that operate under strict trajectory constraints during deployment by adaptively tightening constraints based on agent's performance.

Abstract: Training agents to operate under strict constraints during deployment, such as limited resource budgets or stringent safety requirements, presents significant challenges, especially when these constraints render the task complex. In this work, we propose a curriculum learning strategy that gradually tightens constraints during training, enabling the agent to incrementally master the deployment requirements. Inspired by self-paced learning techniques in unconstrained reinforcement learning (RL), our approach facilitates a smoother transition to challenging environments by initially training on simplified versions of the constraints and progressively introducing the full deployment conditions. We provide a theoretical analysis using an RL agent in a binary-tree Markov Decision Process (MDP) to demonstrate that our curriculum strategy can accelerate training relative to a baseline approach that imposes the trajectory constraints from the outset. Moreover, we empirically validate the effectiveness and generality of our method across both RL and large language model (LLM) agents in diverse settings, including a binary-tree MDP, a multi-task navigation domain, and a math reasoning task with two benchmarks. These results highlight the potential of curriculum design in enhancing the efficiency and performance of agents operating under complex trajectory constraints during deployment. Moreover, when applied to LLMs, our strategy enables compression of output chain-of-thought tokens, achieving a substantial inference speedup on consumer hardware, demonstrating its effectiveness for resource-constrained deployment.

Curriculum Design for Trajectryy-Consrraiee Agent: Compressing Chain-of-Thought Tokens in LLMs
Georgios Tzannetos
Parameswaran Kamalaruban Featurespace Innovation Lab, Visa kaparame@visa.com
Adish Singla MPI-SWS adi adis@iisssssss org
MPI-SWS
gtzannet@mpi-see org
Abstract
Training agents to operate under strict constraints during deployment, such limited resource budgets or stringent safety requirements, presents significant chal- lenges, especially when these constraints render the task complex. In this work, we propose a curriculum learning strategy that gradually tightens constraints during training, enabling the agent to incrementally master the deployment requirements. Inspired by self-pacee learning techniques in unconstrained reinforcement learning (RL), our approach facilitates smoother transition challenging environments by initially training on simplified versions of the constraints and progressively intro- ducing the full deployment conditions. We provide a theoretical analysis using an RL agent in binary-tree Markov Decision Process (MDP) to demonstrate that our curriculum strategy can accelerate training relative to a baseline approach that im- poses the trajectory constraints from the outset. Moreover, we empirically validate the effectiveness and generality of our method across both RI and large language model (LLM) agents in diverse settings, including binary-tree MDP, multi-task navigation domain, and math reasoning task with two benchmarks. These results highlight the potential of curriculum design in enhancing the efficiency and perfor- mance of agents operating under complex trajectory constraints during deployment. Moreover, when applied to LLMs, our strategy enables compression of output chain-of-thought tokens, achieving a substantial inference speedup on consumer hardware, demonstrating its effectiveness for essoucce-constraincd deployment.
Introduction
Recent advances in reinforcement learning (RL) have enabled agents to excel in diverse applications, including robotics, gaming, and large language models (LLMs) [1, 2, 3, 4, 5]. A common assumption in these domains is that the resources available during training, such computational power and time, remain equally accessible during deployment. However, in many real-world scenarios, deployment- time constraints such as limited resource budgets or strict safety requirements significantly diverge from the training environment, posing unique challenges that standard RL methods often overlook.
Consider robot navigating from point to B that is expected to reach its destination, while ensuring that travel time and energy consumption do not exceed predefined limits. Similarly, consider an LLM being used for answering mathematical question, where user requires that the response arrive at the correct answer while using no more than a specified number of thain-of-thought (CoT) tokens. Recent works have studied how to control the length of LLM responses test-time via training objectives or prompting, leading to improved reasoning capabilities [6, 7, 8, 9]. We consider from the prospective of designing curriculum strategy that can enable LLMs to output responses more desirable than the initial response in terms of reduced inference time and computational cost, while preserving the answer's accuracy (Figure 1). Motivated by these examples, consider the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Test-set Math Question: Below is an instruction that describes a task. Write a response that appropriately completes the request. ### Instruction: John adopts dog. He takes the dog to the groomer, which costs $ 1000. The groomer offers him 30% discount for being customer. How much does the grooming cost? ### Response: Let's 's think step by step.
Base Model Response: The grooming cost is $100. The groomer offers a 30% discount, which means John will pay 100 (30% of 100) S70 for the grooming. So, the grooming cost is $70. #8## 70
The answer is:
Fine-tuned Model Response (50K Episodes): The grooming cost $100. The groomer offers 30% discount, so the discount amount is 30% of $100, which is 0.3 $100 = $30. Therefore, the final cost of the grooming is $100 $30 = $70. #### 70
The answer is: 70
Fine-tuned Model Response (100K Episodes): The original cost of grooming is $100. The discount is 30% of $100, which is $100 0.30 $30. The final cost $100 13:000-330-00 $70. #### 70
The answer is:
Fine-tuned Model Response (200K Episodes): Discouni-0.3 -0000000--00000000000 10oo=s0=000000 100t--0000000000000 ### 70
The answer is: 70
Fine-tuned Model Response (400K Episodes): 100*.7=70 #### 70
The answer is: 70
Figure 1: Inference an unseen GSM8K test-set question using different model checkpoints obtained during fine-tuning. These responses showcase that the fine-tuned models progressively learn to generate shorter yet correct solutions by implicitly performing intermediate reasoning steps.
following research question: How can we effectively guide the training process when deployment- constraints are known in advance, in order to achieve the best performance under those constraints?
natural approach to impose deployment-time constraints during training. However, doing so exacerbates the sparse reward problem common in RL, since the agent only receives a reward upon both task completion and strict constraint adherence. This setup contrasts with standard constrained RL formulations [10, 11], where the goal is to maximize the expected reward subject to bounded expected cost, relaxation that does not fully capture the strict nature of deployment requirements. Alternatively, curriculum learning methods developed for contextual RL [12, 13, 14] can treat the permissible cost budget as an input context and gradually shift towards the deployment budget. Yet, these methods incur significant computational overhead because they require extensive performance evaluations across the entire digeeniienii context space, an issue that becomes particularly problematic in domains such as LLMs, where each rollout can be costly.
In this work, we propose novel curriculum strategy that adaptively adjusts the permissible cost budget during training based on the agent's ' current performance. This strategy starts with relaxed trajectory constraints and adaptively tightens them, facilitating a smoother transition stringent deployment conditions. Our main results and contributions are as follows:
1. We introduce computationally--fiini efficieen curriculum strategy tailored to deployment- constraints in RL.
2. We provide theoretical analysis on binary-tree MDP demonstrate that our adaptive curriculum strategy accelerates training relative to approaches that enforce strict deployment constraints from the beginning.
3. We validate our method's 's effectiveness and versatility through comprehensive experiments with both RL and LLM agents across multiple domains. The results highlight its potential to enhance agent performance under real-world deployment constraints, demonstrated by compressing L.LM's output chain-of-thougee tokens in math reasoning."
1.1 Related Work
Constrained Reinforcement Learning. Constrained reinforcement learning (CRL) is typically
formulated a constrained Markov decision process (CMDP) [15], where the goal maximize the
!Github: https:/ http:///tttttoooocccccaaaaaaaaaa http://cccieee.eeeeeoooooooooora curriculurrruuu um- 11m- tokens
group/neurrps2226

---

expected cumulative reward while satisfying expectation based cost constraints. Standard approaches include Lagrangian methods [11, 16], which optimize a weighted combination of rewards and costs using a scalar multiplier, and trust-region methods [10, 17, 18] that enforce constraint satisfaction during policy updates. these formulations, the objective is generally given by
subject to E (T'-C((()) (a Sa
max ENT
where R is the reward function, C' is the cost function, and a is the cost threshold. In contrast, our formulation enforces strict, trajectory-level constraint satisfaction by considering the problem
max E
Σ T
R(sl)) ( 1 Σr C(s ( ( sa
where the indicator function ensures that rewards are only granted if the entire episode adheres to the cost constraint. This stricter requirement inherently induces sparse reward setting, posing unique challenges that are not addressed by conventional CRL methods.
Curriculum for Contextual Reinforcement Learning. Curriculum learning has been widely used
in contextual RL gradually expose agents to increasingly challenging tasks [19, 20J. Self-paced learning approaches [21, 22], such as SPDL [12, 23J, SPACE [24], and CURROT [13], dynamically adjust the task distribution based on agent performance. Similarly, unsupervised environment design (UED) methods [25, 26, 27, 28] evolve the environment alongside the agent. ZPD-basel strategies [29, 30, 31, 32]. such as GOALGAN [33], and PROCURL- -ARGGT [14], select tasks of intermediate difficulty to maximize learning. While our setting could be framed as contextual RI,, treating the cost budget as context and the deployment-ting constraint as the target, this would require learning and evaluating a contextual policy across the full context space, which is impractical for domains like LLMs, where each (prompt. budget) pair demands separate rollouts. Instead, we train a non-contextual policy that adapts the cost budget per prompt, avoiding this computational overhead.
Curriculum for Constrained Reinforcement Learning. Another line of work has addressed curriculum strategies in constrained RL. A recent work [34] extends CURROT [13] to generate safe curricula that begin with low-cost tasks to reduce safety violations, then transition high- reward contexts, and eventually converge to the target. Similarly, [35] introduces human human-inspired inspired teaching strategy, where an artificial teacher guides the agent through progressively challenging, safety-preser stages. However, both approaches assume expectation-basee constraints, making them less applicable to our setting, which requires strict trajectory-level constraint satisfaction. Our work extends curriculum learning to this more stringent setting, offering both theoretical insights and empirical validation.
Efficient LLM Reasoning with Compressed Output. Recent works have begun exploring ways improve the efficiency of LLM reasoning by controlling the model's output token length through prompting or training strategies [6. 7, 8, 9]. Fine-tuning LLMs to reduce verbosity or to adhere to length constraints specified in prompts has been studied, though primarily in the context of general- purpose text generation [36, 37]. For reasoning tasks, [7] proposed simple RI method to train models to follow length constraints provided in the prompt, while [6] modified the RI. objective to penalize longer correct responses. Similarly, [38] and [39] employed RL-based techniques to reduce L.M output length. However, these approaches do not consider strict user-specified test-time constraints; instead, they explore tradeoff's between accuracy and output length. In contrast, our work introduces a curriculum strategy that enables RL fine-tuning with the original sparse reward while ensuring that the resulting LLM strictly adheres to user-defined test-time constraints, without requiring constraint-speae -specfff prompts.
Formal Setup
Multi-task RL, We consider a multi task reinforcement learning (RL) setting with a task or context space X. Each task x E corresponds a learning environment modeled contextual Markov Decision Process (MDP) M2 := (S, A. y: Tz. Rz, Cz, a; P.)), where the state space S, action space A, and discount factor 7 are shared across tasks, while the transition dynamics T. : S x A + [0. 1J. reward function Rg S x A - [0, 1}. cost function C, : S x A + [0, 1J. permissible cost budget a and initial state distribution po S > [0, 1] are task-speeific components [40, 41]. The collection of all environments is represented M {M² E X}.
3

---

Algorithm Training RL Agents with Deployment-time Constraints
1: Input: RL agent's s initial policy m
2: for | 1, do
3: Environment: randomly picks a task 2, E X.
4: Teacher component: picks training-timm time permissible cost budget ay.
5: Student component: attempts the task 2, via K rollouts {5: k generated using the policy me
in the modified MDP MM..
6: Student component: updates the policy to Te+1 using the rollouts ( and the training- time reward function Jz.-
7: Output: RL agent's final policy Tend f- TT+1-
RL agent and performance evaluation. We consider RL agent operating in environment M2 E M using a contextual policy π S x X x A + [0. 1]. which maps a state and task context to probability distribution over actions. Given task rollout obtained by executing its policy æ in the MDP Mra- The trajectory rollout is denoted as
X, the agent attempts the task via a trajectory
& = ( a ) where 500) ~ Po. Let E denote the space of all possible trajectories. To
evaluate the agent's performance, we define a trajectory-level reward function Jæ + [0, 1] based on Rag Cz, and the cost budget a;;
JL(E) == v R. ( E Cr(s s sa
The agent's s performance on task x is then measured by the value function V (= J.) = Bg [=]( Finally, the uniform performance the agent across all tasks in is given
by V" (nittoom)))) [VT(x;]z)]
Training process of the RL agent. During training, the agent employs a student component, re- sponsible for policy updates, and teacher component, which guides the student's 's learning process to find policy that performs uniformly well across all tasks in X, i.e., max, , V Training occurs in discrete steps indexed by t t= 1, ..2..... as formally described in Algorithm 1. At each step f, the environment randomly selects task x, along with its deployment-ting teacher component modifies this budget, replacing it with training-time cost budget or,, This effec- tively transforms the original MDP Mz, into new MDP Mz, AS, Ta Re Cz 0t, P
cost budget oz However, the
thereby shaping the original trajectory-level reward function J=. - to obtain a new reward function Jz. Jsh where:
(E) Rot-R (o( (a. C2 sal
The student component then attempts task Ie by executing the policy ni for K rollouts, denoted as { within the modified MDP Mr,, After collecting these rollouts, the student component updates the policy to T++11 based on the current policy m. the selected task Iz, the teacher-shaped reward function Je., and the set of rollouts {5.), Formally, the policy update is given by:
Tt-1 <- L(T,, Tt, Ja., {&r } where L is a learning algorithm. Let wend denote the agent's final policy at the end of training. The training objective is to ensure that the performance of the policy Tend e-near-optimal, i.e., (max, V V"-V""a > < The primary objective of this work is to design teacher component that achieves this training objective efficiently, both computationally and in terms of sample complexity.
3 Our Curriculum Strategy
In Section 3.1, we propose a curriculum strategy for selecting a permissible cost budget or (Algo- rithm at Line 4). In Section 3.2, we provide theoretical analysis binary-tree environment, demonstrating that the proposed strategy accelerates the agent's training process.

---

3.1 Curriculum Strategy
First, we discuss the challenges of using deployment-ting cost budgets during training, i.e. selecting
Or = 2x in Line 4 of Algorithm 1. When the reward function R. is goal- goal-oriented (i.e., (s a) = for all a E A and & E Gz. and R₂ (s. a) = otherwise for some goal space 9x), training with the deployment-time cost budget a can be highly ineffective, especially when o is small. In such cases, obtaining successful rollouts, i.e., trajectories & where (E) > using the randomly initialized policy क is extremely difficult. As a result, directly using the original deployment-tne
budget a (or the corresponding reward function Jz) during training may fail to provide a meaningful learning signal for policy updates, making the update rule T++1 + Ie, J... {&: {
K ineffective.
Te,
To address these challenges, introduce curriculum strategy that dynamically selects permissible cost budget ot based on the agent's current performance. At a high level, the intuition behind our approach is follows: each step 4, given a task 2tt, we shape the trajectory-level reward function Jz, obtain a new reward function Ja,, which remains close to Jz, while ensuring that the performance of the current policy Ti on task 24 is above certain threshold. This naturally leads to a curriculum strategy for selecting Ct.
Formalization of the curriculum strategy. At each step i, given a task It, the teacher component picks Or by solving the following optimization problem for given performance threshold > 0:
at arg min (a a²,)² subject to V* J2.) 2 min V Jo. - }}
(2)
at [=
where V (zii (. Eg [Je] (E) represents the value of policy Te on task o, under the
reward function J Since V (I7s J is the maximum achievable value due to the monotonically non-decreasing property of V (T JT) with respect to a, the optimization problem in Eq. (2) always has at least one feasible solution: a = -- Our curriculum strategy adaptively selects a such that: (1) a remains as close as possible to the target permissible cost budget a%,,, and (2) the resulting reward function Ja: provides sufficient learning signal for policy updates, as enforced by
the constraint V* (Iz; Jos) 2 m V=* J). Notably, we identify two particular cases of our strategy. First, when O, the constraint is trivially satisfied for a = oz leading to a a This corresponds to the target curriculum, where the teacher directly picks the target az, Second,
when the maximum achievable value for the unconstrained problem V (Ire: J zero, the curriculum selects the largest possible target parameter, aligning with the unconstrained curriculum.
Practical implementation. For any task and trajectory &, the reward function J (C) is mono- tonically non-decreasing in a. Consequently, for any policy म, the value function V (2;;; J is also monotonically non-decreasing with respect a. This property enables efficient solving of the optimization problem in Eq. (2) using binary search. The full procedure is presented in Algorithm 2.
Algorithm 2 Teacher Component: Curriculum Strategy for Picking ar (Line 4 of Algorithm I)
1: Input: current policy mi, current task 2r, and performance threshold B.
2: Generate a of rollouts E ( using the policy me in Mas-
3: Set / min
B, N 1 Juh (Ex)
4: Binary search the smallest a E [ +-y
such that 1 M (E:(E.) 2 B.
5: Output: permissible cost budget at
3.2 Theoretical Analysis
We theoretically demonstrate the usefulness of our curriculum strategy in accelerating agent's learning in a binary-tree environment. We select this basic RL setup, because it encapsulates the core challenge of our study, i.e., the sparse reward nature in strictly constrained RL problems.
Binary-tree environment. We consider a binary-tree MDP Mx == AS, 7, Trx Rz, Cr, oz PD) of depth H (focusing on the single-task setting X {T)). The state space S consists of the nodes of
5

---

the i-th node (from the left) at level h. At each node, the agent .22 -1), where w/ represents of two actions, choose
(H) (H) a binary tree, denoted as S (v6' -V Mi ,... .No :
(0) (2) (1)
(H)
A = {LEFT, RIGHT), which deterministically transitions the agent to the respective child node in the tree. The initial-state distribution is concentrated at the root node Y/o (0) with P (U))) (0) 1. Each
trajectory through the tree terminates at a leaf node, representing a unique deterministic path from the root. All leaf nodes are designated as goal states, with rewards defined as Rw (s, a) = 1 for all
s E {36 (4) ... 3/22 (H) } and a E A, and Rx (s, a) = 0 otherwise. The cost function C3 is structured such that total trajectory cost increases monotonically from the leftmost to the rightmost
leaf node. Denoting the total cost of a trajectory (0) V. (1) as C2 (0) ./, (4))
this condition
formally expressed as: C26 ..... (H)) < C2(10 .... yi (H) < <... Cz(1b (%)
// -1 -)-
Any given tree structure can be rearranged to meet this property. A permissible cost budget, a E [0, 1]. is specified as a constraint. Only the leftmost leaf node satisfies Ca (0)
M/0 (H) S 0
while all other leaf nodes exceed the budget, i.e., C2 Cv (0) ... yi ( > a for E (1, [1,.... .........
, 2H 1}.
The agent begins with a uniformly random policy where ग (LEFT [. ( गं (RIGHT (h))) 0.5, Vi E {O...., 2a }} h E {O...., H 1}. The optimal policy deterministic, always choos- ing LEFT at all relevant states, i.e., x² "LEFT ) 1.0, h E (O...., H 1).
Now, we compare the effects of two strategies in the binary-tree MDP described above:
1. Target curriculum strategy:
The teacher always selects the target cost budget parameter oz (i.e., 3 = 0). meaning the learner receives non-zero reward only upon completing full successful trajectory (i.e., reaching the lefumost leaf). As we will demonstrate, this baseline strategy requires exponential number of rollouts with respect to the tree depth H.
2. Curriculum strategy with adaptive 3r > 0: Here, the teacher gradually tightens the cost constraint by setting the performance threshold parameters to Br 0.5 (1 e)- for ( 1,...., H. This design ensures that non-negligible fraction of rollouts yield a positive reward well before the optimal trajectory reached, thereby promoting progressive learning.
The following theorem establishes that our curriculum strategy dramatically reduces the sample complexity compared the baseline.
Theorem 1. Consider the binary-tree MDP with depth H. Suppose the teacher employs the curricu- lum strategy as defined Eq. (2) with threshold parameters 3r 0.5 e)r-1, for 1,..., H, and selects the cost budget parameter on, at euch time step by solving
Ott f arg min (a - a?)) subject to V (x; Jo) 2 Bc,
where y is chosen so that y 2 0.5 (which guarantees that Be S 7 for all t). Then, with probability
al least 1 - 5, the learner obtains an e-suboptimal policy (i.e., TH ( Wo (h) 2 1 e, vh E {0. ... H 13) after a total of EE K, Ei= -1= rollouts, where K, the number of rollouts required at step t. In particular, setting c= H+1 yields an overall sample complexity of O (H In contrast, the baseline target curriculum strategy (with at = axt)) has an expected overall sample complexity of O )
ln(3)
Proof sketch. Under the target curriculum strategy, the learner receives non-zero reward only when a successful rollout (reaching the leftmost leaf) occurs. For a uniformly random policy, the probability of following the leftmost branch in a tree of depth H is p (1)* H Thus, the expected number of rollouts needed achieve successful trajectory is 1 2 leading to O(2") sample complexity.
In our curriculum strategy, at each step t, the teacher sets the cost threshold a, that fraction 0.5 (1 - <)--1 of the rollouts yield a reward of 1. For example, at t = 1 the teacher selects aj such that half of the rollouts are successful, ensuring / (T; ) > 0.5. As the learner collects K, rollouts at step f, Hoeffding's s inequality guarantees that the updated policy T442 satisfies the
s 22-exp e-expp(22 2- K₁ 22. Setting this probability to be at most d and accounting for the compounded e-suboptimality from previous steps,
following: Me+1 (LEFT) 3o (("))) (LEFT y0 -(-"))] >

---

Weng 812 hour babysitting Yesterday, she just did 50 min- utesof bahysitting How much did carn?
Problem:
Weng carns 12/60 0.2 per minute. Working
Solution:
minntes, she earned 0.2 50 = 10, # #### # 10
Cost:O
Cost:l
Cost:2
Cost:3
The answer is: 10
(b)
(d)
Figure 2: Illustrative visualization of each environment (from left right): (a) BINARYTREE, (b) PUDDLEGRID-SINGLE, (c) PUDDLEGRID-MULTI, and (d) SVAMP / GSM8K.
In(3)
one obtains K2 2 2----(1-) Summing over all gives the total sample complexity. With a proper can show that the overall complexity is bounded by ((H)). O
choice of (e.g., #41
2
Theorem rigorously shows that our curriculum strategy dramatically reduces the rollout complexity for learning an e-suboptimal policy. In contrast, the baseline suffers from exponential dependence on tree depth H, our approach leverages intermediate learning signals to guide the agent more efficiently.
4 Experimental Evaluation
We evaluate our curriculum across three RL. environments of increasing complexity with challenging trajectory constraints, culminating in real-world math reasoning task involving LLM agent. For RL experiments, we employ REINFORCE in both tabular and neural single-/multi-taass settings [42]. For LLMs, adapt Hugging Face's ' TRL library [43] using the RLOO trainer [44], RL fine-tuning method equivalent to REINFORCE. This unified setup ensures consistency across all experiments. To assess the robustness of our findings the choice of the training algorithm, we provide additional results in Appendix E. where RL agents are trained with Proximal Policy Optimization (PPO) [45].
4.1 Environments
BINARYTREE. This environment is inspired by our theoretical analysis (Figure 2a). We binary tree of depth H = 12, resulting in 2 = 4096 leaf nodes, each representing a terminal state associated with cost. The leftmost leaf has cost of O, with costs increasing monotonically from left to right. The target cost budget is a = 0, i.e., only the leftmost leaf yields a reward of at test time.
(Figure 2b), is cus- tomized variant of the MINIGRID environment. The state representation includes the red agent's location and orientation, while the action space comprises three discrete actions: move, turn-left. and turn-right. The agent's objective to reach the green square. Stepping on a lava (orange) square increases the trajectory cost by 1 per time step. The agent receives reward of 1 only if it reaches the green square with a trajectory cost below the target budget; otherwise, the reward 0. The target cost budget is set a" 0, i.e., the agent must avoid stepping on lava squares entirely.
PUDDLEGRID-SINCE
The second environment, PUDDLEGRID-SINONE
Building on the previous environment, we design PUDDLEGRID-ME MULLTI (Figure 2c), which extends FUDDLEGRID-SINGLL to multi-task setting. The core structure remains the same, but after each episode, both the agent's initial location and the goal location are randomly selected. The state representation is augmented to include the goal location within the grid. In this multi-task setup, each task can have its own constraint during training and testing. As in WUNDLLGRID-SINGGLE the target cost budget is set a² 0.
PUDDLEGRID-MUSI
SVAMP GSM8K. Last, we consider more challenging setting which involves using LLMs to solve math problems. Given a math problem (Figure 2d), an LLM agent generates a solution trajectory. reward of is assigned only if the final answer is correct and the number of generated tokens does not exceed the target budget. To ensure the generality of our evaluation, we assess the performance of our algorithm on two mathematical reasoning benchmarks: SVAMP [46], and GSM8K [47]. Given the varying levels of difficulty across datasets, we set the target cost per test sample as a percentage of the base model's ' original response length. We fine-tune two base models with LoRA [48] using (METAMATH) [50].
RLOO: QWEN2.5- SWEN2.5-MMTH- 1.5B (QWEN) [49], and METAMATH-
7

---

CURLTRAC PROCURL
EXPSCHEDULEy-PY -I-IID
UNCONSTRAINT
1.39
1.3
10
0.3-
0.34
marforaance
mace
Performance
0.5
6.5
0.49
0-4
0.20
0.24
0.2
Episodes
XID
Episodes
Episodes
(a) BINARYTRED
(b) WOODLEGGRD-SINGGLE
(c) PUDDLEGRID-MULE
Figure 3: Performance of RI. agents trained with different strategies, measured by the agent's ' mean return (with 95% confidence intervals over 10 random runs), evaluated under test-time constraints.
CURLTRAC
SOFT- 11
EXPSCREDUL IID
UNCONSTRAITT --.-------- TARGET
ANSONIYYPRMME
0.5
8.5
0.5
Performance
Performance
0.44
0.0
0.0
20
20
Episodes
XII
Episades
(a) SVAMP-QWEN
(b) SVAMP-METAMATH
0.8
0.5-
Perfommance
Performance
0.4
0.44
0.24
0.0
0.0
20
40
20
60
60
300
Episodes
x1I
Episodes
x.1
(c) GSMSK-QWERR QWEN
(d) METAK-METAMATH
Performance of LLM agents trained with different strategies, measured by the agent's 's mean accuracy (with 95% confidence intervals over random runs), evaluated under test-time constraints.
Figure 4:
4.2 Methods Evaluated
We follow Algorithm 2 with a fixed performance threshold of B = 0.5 across all experiments, following the idea of intermediate difficulty. In Appendix E.2, we conduct sensitivity analysis of 3 across all RL environments to assess the robustness of the proposed method. Starting from an upper bound on a, we perform binary search find the smallest value satisfying the constraint in Line 4 of Algorithm 2. A history of per-task rollouts is maintained in rolling buffer. When task x selected, rollout outcome and length are added to corresponding per-task buffer, and the associated training budget or is updated. In practice, updating a does not require collecting additional rollouts at different constraint levels. Instead, the update relies solely on previously collected training rollouts, introducing additional computational overhead.
Our strategy CURLTRAC.
Contextual RL curriculum. We employ recent curriculum strategy, MEOCCURL-TARGIA [14], which trains RL agents toward challenging target distributions. To apply a contextual RL curriculum our setting, the trajectory constraint must be treated as an input context, and the deployment- constraint as the target distribution. While this adaptation is conceptually straightforward. applying to domains with large context spaces, as in LLMs, is impractical. Effective training with such technique would require generating all possible (prompt, budget) pairs. Even with discretization, the resulting augmented context space becomes intractable, Therefore, we apply MOOUCRR--AAGOE only in the RL environments.

---

CURLTRAC
SOFT- SOFT-RIm..de Rim
EXPSCHEIDLLE IID UNCONSTRAINT
TARGET
330-
Moan training coat coata
300-
Mean training roward
resp respoone length
175+
150
300-
225
500m
130-
50-
12
Episodes
Episodes
(a) Training cost
(b) Training Reward
(c) Training Response Length
Figure 5: Training plots of SVAMP--QW OWEN for different strategies. (a) shows the progression of the
cost budget during training. (b) shows the average observed reward during training. (c) shows the progression of the generated response lengths during training.
Regularized RL baselines. An alternative option is relax the strict trajectory-level constrained RL objective in Eq. (1) by considering regularized, softer version, denoted as SOFT-RL, following [6]. This method aims to balance the trade-off between accuracy and response length rather than explicitly enforcing hard constraints. It can also be applied to our LLM setup. Although it does not guarantee satisfaction of the target constraints at the end of training, the added regularization ferm encourages both correctness and brevity in the model's responses. While [6] used a coefficient of Oreg 0.4, we found stronger regularization to be more competitive. Hence, we report results with Oreg 0.9, corresponding to SOFT-RLa.g--h to further encourage shorter responses.
Typical and heuristic baselines. We compare against three standard baselines: TARGET, trains directly under the deployment constraint; UNCONSTRAINT, trains without restrictions; and IID, trains by sampling the cost budget randomly per episode. Motivated by the observation that CuRL- TRAC exhibits an empirical decay pattern resembling exponential scheduling, we also include EXPSCHEDULE [51], static curriculum with exponential decay. While the decay horizon T is typically unknown in advance, we estimate it based on the convergence behavior of CURLTRAC in each environment. In Appendix E.3, we evaluate EXPŠCHEDULF with variable and fixed decay lengths T = {T", T /2, 50000, 5000), where T denotes the total number of training episodes per environment. We report results for the most competitive variant, EXPSSHEDUULET.TT
Prompting-best based baseline. We also consider a prompting-bee baased based baseline, ANSONLY to evaluate model's accuracy under test-time constraints without any fine-tuning, ANSONLYPROMPT prompts the model to provide a direct answer without any chain-of-thoughe reasoning." Further implementation details are provided in Appendix D.2.
4.3 Results
Convergence behavior. RL and LLM agents trained with CURLTRAC consistently outperform all baselines under test-time constraints (Figures and 4). PROCURL-TARGEY performs relatively well in RL enviromennts but relies on providing the target budget as context, limiting its applicability in complex LLM domains. EXPSCHEDDLLE
effectively trains RL agents settings where the target budget is identical across tasks; however, its performance becomes inconsistent in per-task target settings, underscoring the need for per-task exponential scheduling. SOFT- NOFT-RLo.. a state-of-the-ar method for balancing response length, achieves competitive performance, yet its formulation lacks an explicit notion of target constraints and therefore requires per-domain tuning of its regulam aegularizaionn coefficient. MosONLYPROMPE method shows that, without fine-tuning, the LLM fails to satisfy target constraints.
Training cost. Figure 5a shows the progression of the average training cost budget o, which reflects task difficulty and defines the training curriculum. SOFT-R Rtn--RL.....0000 incorporates response length directly into the reward function; hence, it does not control a. TARGET maintains a fixed cost budget, while UNCONSTRAINT allows maximum token generation. IID samples a randomly per episode. EXPSCHEDULET /2 decays at fixed rate, whereas CURLTRAC adaptively tightens constraints by decreasing a based on model performance, gradually converging to the test target.
Note that all other methods default chain-of-thouge prompt that encourages step-by-sted reasoning.

---

Table 1: Comparison of models in terms of inference metrics when deployed on various consumer hardware configurations. Results are reported for inference on SVAMP test-set with QWEN as base model used for fine-tuning. We consider the following inference metries: (a) "Response Time", (b) "Response Length", (c) "Accuracy", and (d) "Constr. Accuracy". Here, "Accuracy" denotes the overall test-set accuracy, while "Constr. Accuracy" corresponds to the performance metric used in Figure 4 (i.e., mean accuracy under test-time constraints). We report results for three configurations, namely, MI (Apple MI Pro). GTX (Nvidia GTX 1070), and RTX (Nvidia RTX 3060).
Inference Metrics
Method
Respouse
Response Length (tokens)
Accuracy (%)
Constr. Accuracy (%)
M1
GTX
RTX
M1
GTX
RTX
MI
GTX
RTX
MI
GTX
RTX
Base model
(.5().2)
3.9 (0.1)
2.5 (0.1)
138 (3.9)
142 (4.0)
145 (4.2)
77
77
75
0
PNOONLYPROMPT
5.6(0.3)
2.8 (0.1)
(.710
101 (3.4)
102 (5.3)
101(5.5)
60)
63
61
9
8
9
UNCONSTRAINT
(..))
(0.1)
(..1)
121 (2.1)
119 (2.2)
(2.1)
TARGET
0.6
0.5 (0.0)
0.3 (0.0)
(.088)
4(0.1)
4(0.6)
61
62
61
62
CURLTRAC
(0.(0.0)
0,5 (0.0)
0.3 (0.0)
(
3(0.1)
3(0.1)
74
74
T2
74
74
72
Training reward. Figure 5b shows that although UNCONSTRAINT and TDD achieve increasing training rewards, these gains do not transfer to test-time performance (see Figure 4). TARGET yields delayed or no rewards due to its strict constraints, providing weak learning signals. In contrast, CURLTRAC exhibits initial reward drop decreases and tasks become more challenging, yet the reward remains above the threshold 3 0.5. Once stabilized around 3, performance improves, indicating that the models learn to adapt progressively tighter constraints. EXPSCIIEDULE:=-> shows a sharp reward decline, indicating rapid constraint tightening. Finally, SOFT- SOFT-RLa.. regularizes UNCONSTRAINT balancing accuracy and brevity through regularized reward signal.
Training Response length. Figure 5c shows varying rates of response-length reduction as models adapt to meet test-time constraints. CURLTRAC achieves the fastest adaptation to shorter responses, followed by SOFT-RI COFT-RI. =0.9- IID shows moderate reduction but remains above the target lengths. UNCONSTRAINT and TARGET exhibit no and late change during training.
LLM Deployment on Consumer Hardware. Next, assess the practical impact of our strategy by comparing inference metrics of QWEN models across hardware configurations (Table 1). Performance of the base model serves as a default baseline of the model used for fine-tuning. ANSONLYPROMPP fails to adequately reduce the response time, and displays drop in accuracy. Fine-tuning with UNCONSTRAII improves accuracy, but results in high response time; tnnettunig with TARGET decreases response time, but leads to a notable drop in accuracy. Our strategy CURLTRAC achieves a balaneed trade-off between response time and accuracy, while also ensuring high constrained accuracy. Relative to the base model, CURLTRAC provides a substantial reduction in response time (e.g., 7.5 vs. 0.6 on M1 configuration), while maintaining accuracy (e.g., 77 vs. 74 on M1 configuration).
Concluding Discussions
We proposed curriculum strategy for RL under strict trajectory-lever constraints, enabling agents to adapt to stringent resource or safety requirements. Our theoretical analysis on binary-tree MDP showed faster convergence compared to imposing constraints from the outset, and our empirical results across multiple domains highlighted its effectiveness. Applied to math reasoning, our strategy allowed us to fine-tune an L.M to compress its output of-hhuhttthought tokens to strict deployment constraints, achieving a substantial speedup during inference time.
Next, we discuss a few limitations and outline a plan for addressing them in future work. First, we assume that deployment-ting constraints are predefined. Future work could explore Matryoshka-style learning [52] train models capable of dynamically adapting to varying target constraints, thereby accommodating different test-time resources. Second, in our setting we compressed the output chain- of-thought tokens of the model to satisfy certain deployment constraints. In future work, would be interesting to apply this idea of token compression to mitigate other inference- time bottlenecks, such as reducing the number of rollouts best-of-N sampling or reducing the size of input context. Finally, while our strategy improves performance under constraints, its impact on the model's 's internal behavior remains unclear. Investigating changes in attention patterns or internal representations after fine-tuning could provide deeper insight into the model's 's adaptation.
10

---

Acknowledgments and Disclosure of Funding
Funded/Co- by the European Union (ERC, TOPS, 101039090). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can held responsible for them.
References
[1] Volodymyr Mnih, Koray Kavukeuoglu. David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, and Georg Ostrovski. Human- Level Control Through Deep Reinforcement Learning. Nature, 518(7540):529-333 2015.
[2] Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous Control with Deep Reinforcement Learning. CoRR, abs/1509.02977 2015.
[3] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end Training of Deep Visuomotor Policies. JMLR, 17(1):1334-1373, 2016.
[4] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, and Adrian Bolton. Mastering the Game of Go Without Human Knowledge. Nature, 550(7676):354-355 2017.
[5] Moschoula Pternea, Prema Singh, Abir Chakraborty, Yagna Oruganti, Mirco Milletari, Sayli Bapat, and Kebei Jiang. The RI/LLM Taxonomy Tree: Reviewing Synergies Between Rein- forcement Learning and Large Language Models. JAIR, 80:1525-1573, 2024.
[6] Daman Arora and Andrea Zanette. Training Language Models to Reason Efficiently. CoRR, abs/2502.04463, 2025.
[7] Pranjal Aggarwal and Sean Welleck. LI: Controlling How Long a Reasoning Model Thinks With Reinforcement Leaming. CoRR, abs/2503.0469 2025.
[8] Simon A Aytes, Jinheon Baek, and Sung Ju Hwang. Sketch-of-Thought Efficient LLM Reasoning with Adaptive Cognitive-Inspired Sketching. CoRR, abs/2503.05179, 2025.
[9] Tingxu Han, Zhenting Wang, Chunrong Fang, Shiyu Zhao, Shiqing Ma, and Zhenyu Chen. Token Bikeet-uddet-Awarr Aware LLM Reasoning. CoRR, abs/2412.18547, 2024.
[10] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained Policy Optimization.
In ICML, 2017.
[11] Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward Constrained Policy Optimization. In ICLR, 2019.
[12] Pascal Klink, Carlo D' Eramo, Jan R Peters, and Joni Pajarinen. Self-Paced Deep Reinforcement Learning. In NeurIPS, 2020.
[13] Pascal Klink, Haoyi Yang, Carlo D'Eramo, Jan Peters, and Joni Pajarinen. Curriculum Rein- forcement Learning via Constrained Optimal Transport. In ICML, 2022.
[14] Georgios Tzannetos, Parameswaran Kamalaruban, and Adish Singla. Proximal Curriculum with Task Correlations for Deep Reinforcement Learning. In IJCAI, 2024.
[15] Eitan Altman. Constrained Markov Decision Processes. Routledge, 2021.
[16] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-Constrained Reinforcement Learning with Percentile Risk Criteria. JMLR, 1-11, 2018.
[17] Tsung- Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter Ramadge. Projection-Bane Constrained Policy Optimization. In ICLR, 2020.

---

[18] Yiming Zhang, Quan Vuong, and Keith Ross. First Order Constrained Optimization in Policy Space. NeurlPS, 2020.
[19] Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey, JMLR, 21:1-50, 2020.
[20] Rémy Portelas, Cédric Colas, Lilian Weng, Katja Hofmann, and Pierre Yves Oudeyer. Auto- matic Curriculum Learning for Deep RL: A Short Survey. In IJCAI, 2021.
[21] M Pawan Kumar, Benjamin Packer, and Daphne Koller. Self- Learning for Latent Variable Models. In NeurIPS, 2010.
[22] Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander G Hauptmann. Self-Paced Curriculum Learning. In AAAI, 2015.
[23] Pascal Klink, Hany Abdulsamad, Boris Belousov, Carlo D' D'Eramo, Jan Peters, and Joni Pajarinen. Probabilistic Interpretation of Self-Paced Learning with Applications to Reinforcement Learning. JMLR, 22:182-1, 2021.
[24] Theresa Eimer, André Biedenkapp. Frank Hutter, and Marius Lindauer. Self-Paced Context Evaluation for Contextual Reinforcement Learning. In ICML, 2021.
[25] Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design. In NeurIPS, 2020.
[26] Minqi Jiang, Edward Grefenstette, and Tim Rocktäschel. Prioritized Level Replay. In ICML, 2021.
[27] Minqi Jiang, Michael Dennis, Jack Parker-Holder, Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Replay-Guided Adversarial Environment Design. In NeurIPS, 2021.
[28] Jack Parker-Holder, Minqi Jiang, Michael Dennis, Mikayel Samvelyan, Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Evolving Currieula with Regret-Based Based Environment Design. In ICML, 2022.
[29] Lev Semenovich Vygotsky and Michael Cole. Psychological Processes. Harvard University Press, 1978.
Mind in Society: Development of Higher
[30] Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse Curriculum Generation for Reinforcement Learning. CORL, 2017.
[31] Jan Wöhlke, Felix Schmitt, and Herke van Hoof. A Performance-Basse Start State Curriculum Framework for Reinforcement Learning. In AAMAS, 2020.
[32] Georgios Tzannetos, Bárbara Gomes Ribeiro, Parameswaran Kamalaruban, and Adish Singla. Proximal Curriculum for Reinforcement Learning Agents. In TMLR, 2023.
[33] Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic Goal Generation for Reinforcement Learning Agents. In ICML, 2018.
[34] Cevahir Koprulu, Thiago D Simão, Nils Jansen, et al. Safety-Prioritizing Curricula for Con- strained Reinforcement Learning. In ICLR, 2025.
[35] Matteo Turchetta, Andrey Kolobov, Shital Shah, Andreas Krause, and Alekh Agarwal. Safe Reinforcement Learning via Curriculum Induction. In NeurlPS, 2020.
[36] Renlong Jie, Xiaojun Meng. Lifeng Shang. Xin Jiang, and Qun Liu. Prompt-based Length Controlled Generation with Reinforcement Learning. CoRR, abs/2308. 12s/2008.12000, 2023.
[37] Weizhe Yuan, Ilia Kulikov, Ping Yu, Kyunghyun Cho, Sainbayar Sukhbaatar, Jason Weston, and Jing Xu. Following Length Constraints in Instructions. CoRR, abs/2406. 17744, 2024.
12

---

[38] Jingyang Yi and Jiazheng Wang. Shorterbetter: Guiding Reasoning Models to Find Optimal Inference Length for Efficient Reasoning. CoRR, abs/2504.21370. 2025.
[39] Mehdi Fatemi, Banafsheh Rafice, Mingjie Tang, and Kartik Talamadupula. Concise Reasoning via Reinforcement Learning. CoRR, abs/2504.05185, 2025.
[40] Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual Markov Decision Processes. CoRR, abs/1502.02259, 2015.
[41] Aditya Modi, Nan Jiang, Satinder Singh, and Ambuj Tewari. Markov Decision Processes with Continuous Side Information. In ALT, 2018.
[42] Ronald J Williams. Simple Statistical Gradient- Following Algorithms for Connectionist Rein- forcement Learning. Machine learning, 8(3-4):229-25 1992.
[43] Leandro von Werra, Younes Belkada, Lewis Tunstall, Edward Beeching, Tristan Thrush, Nathan Lambert, Shengyi Huang, Kashif Rasul, and Quentin Gallouédec. TRL: Transformer Reinforce- ment Learning. https: / gi thub www.cc/ggggggancee/oooooo/ooccee
2020.
[44] Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadaee, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker. Back to Basics: Revisiting REINFORCE-Style Optimization for Learning from Human Feedback in LLMs. In ACL, 2024.
[45] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Optimization Algorithms. CoRR, abs/1707 707.000777777 2017.
[46] Arkil Patel, Satwik Bhattamishra, and Navin Goyal. Are NLP Models really able to Solve Simple Math Word Problems? In NAACI, 2021.
[47] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jenry Tworek, Jacob Hilton, Reicchiro Nakano, Christopher Hesse, and John Schulman. Training Verifiers to Solve Math Word Problems. CoRR, abs/2110. 141668 2021.
[48] Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, al. LoRA: Low-Rank Adaptation of Large Language Models. In ICLR, 2022.
[49] An Yang, Beichen Zhang, Binyuan Hui, Bofei Gao, Bowen Yu, Chengpeng Li. Dayiheng Liu, Jianhong Tu, Jingren Zhou, Junyang Lin, Keming Lu, Mingfeng Xue, Runji Lin, Tianyu Liu, Xingzhang Ren, and Zhenru Zhang. Qwen2.5 -athh Technical Report: Toward Mathematical Expert Model via Self- rel--Improvement arXiv preprint arXiv:2409. 12102 2024.
[50] Longhui Yu, Weisen Jiang, Han Shi, Jincheng YU, Zhengying Liu, Yu Zhang, James Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap Your Own Mathematical Questions for Large Language Models. In ICLR, 2024.
[51] Shahaf S Shperberg, Bo Liu, and Peter Stone. Relaxed Exploration Constrained Reinforcement Learning. In AAMAS, 2024.
[52] Aditya Kusupati, Gantavya Bhatt, Aniket Rege, Matthew Wallingford, Aditya Sinha, Vivek Ramanujan, William Howard- Howard-Snyder, Kaifeng Chen, Sham Kakade, Prateek Jain, and Ali Farhadi. Matryoshka Representation Learning. In NeurIPS, 2022.
[53] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. 7eRO: Memory Opti- mizations Toward Training Trillion Parameter Models. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-16. IEEE, 2020.
[54] Ollama. https://ollama.com/.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper organized according to the contributions listed the end of the introduction section. The theoretical and experimental claims and outcomes mentioned in the abstract and the introduction are detailed Sections 3 and 4.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the paper are specifically discussed in Section 5, along with future plan address those limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the assumptions of the theoretical results have been stated in Subsection 3.2. Complete proofs of the theoretical results are included in main paper and in Appendix C.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the information and the details needed to reproduce the experiments are provided in the paper (Section and Appendix D).
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We release the code in a publicly available GitHub repository, which enables the reproduction of the main experimental results.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All the training and test details required to understand the results are provided in Section and Appendix D. Moreover, full details are documented in the code.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: To obtain the results, ran the experiments independent runs and report error-bars for the results with 95% confidence interval. To obtain the confidence interval we use bootstrapping from Searborn package.
8. Experiments compute resources
14

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The compute resources are reported Appendix D.I.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http://eeerppp.eeeeee
Answer: [Yes]
Justification: We confirm that our paper conforms the ethies review guidelines.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: This work presents new curriculum strategy for learning agents. Given the algorithmic and empirical nature of our work applied learning agents, we do not foresee any direct negative societal impacts of our work in the present form.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: This paper poses such risks.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: are using some assets, such as code and models that are used literature for our experiments. We have cited all the sources.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code is provided in a publicly available GitHub repository. All parts of the code are sufficiently documented.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No crowdsourcing nor research with human subjects was involved.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
15

---

Justification: No crowdsourcing nor research with human subjects was involved.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLM was involved in the core method development of this work.
16

---

A Table of Contents
In this section, we briefly outline the content included in the paper's appendices:
Appendix B presents additional examples of model responses observed during training.
Appendix contains the proof of Theorem (Section 3).
Appendix details further implementation aspects of the experiments (Section 4).
Appendix E provides additional experimental results, including experiments with Prox- imal Policy Optimization as the learning algorithm, parameter sensitivity analysis of CURLTRAC, and comparisons with additional baselines.
B Additional Examples with Model Responses
We present additional qualitative outputs generated by the language model at various stages training. These examples demonstrate how the fine-tuned model learns to produce compressed responses that explicitly skip steps in chain-of-thouge reasoning without compromising final correctness. To maintain clarity and conciseness, we omit intermediate evaluation steps where the model's responses show negligible variation for a given test question. Figure illustrates the progression of METAMATH model responses for representative example from the S VVAMP dataset. In Figure 7, we highlight a notable case where the METAMATH model, by the end training, produces the correct answer directly, without relying intermediate chain-of-thoughh reasoning. Figure 8 shows the progression of QWEN'S responses for an example from the GSM8K dataset. The model implicitly halves the total number of glasses and computes the discounted glass price, significantly compressing the chain-of-thought process by reducing the number of generated tokens. Similarly, Figure 9 presents the progression of QWEN's 's responses for another example from the GSM8K dataset. In this case, the model implicitly computes the number of downloads for the second and third months, and directly proceeds to calculate the total.
Test-set Math Question: Below is an instruction that describes a task. Write a response that appropriately completes the request. ### Instruction: Jesse's 's rooms are 19 feet long and 18 feet wide. If she has 20 rooms, how much carpet does she need to cover the floors of all rooms? ### Response: Let''s think step by step.
Base Model Response: Jesse's 's rooms are feet long and feet wide. To find area of one room, we multiply the length by the width: 19 feet 18 feet = 342 square feet. Jesse has 20 rooms in total. To find the total area of all the rooms, we multiply the area of one room by the number of rooms: 342 square feet 20 6840 square feet. Therefore, Jesse needs 6840 square feet of carpet to cover the floors of all the rooms. ### 6840
The answer is: 6840
Fine-tuned Model Response (25K Episodes): The area of each room 19 feet 18 feet 342 square feet.Since Jesse has 20 rooms, the total area of all the rooms is 342 square feet x 20 = 6840 square Thereffr,,, Jesse needs 6840 square feet of carpet to cover the floors of all the rooms. #### 6840
The answer is: 6840
Fine-tuned Model Response (50K Episodes): The area of each room is 19 feet 18 feet 342 square feet.Since Jesse has 20 rooms, she needs total of 20 342 square feet of carpet. #### 6840
The answer is: 6840
Fine-tuned Model Response (75K Episodes): She needs (19 * 18) 6840 square feet of carpet. ####
6840
The answer is: 6840
Fine-tuned Model Response (100K Episodes) 19*18*20 #### 6840
The answer is: 6840
Fine-tuned Model Response (250K Episodes): 19*18*20 The answer is: 6840
Figure 6: METAMATH responses to a SVAMP test question at different stages of training. The model trained with curriculum technique learns minimize the chain-of-thought process. In this example, only the final calculation is generated.
17

---

Test-set Math Question: Below is an instruction that describes a task. Write a response that appropriately completes the request. #H# Instruction: Melissa scored total of 21 points playing some games. Is she scored 7 points each game. How many games did she play? ### Response: Let's think step by step.
Base Model Response: If Melissa scored points in each game, then the total number of games she played is 21 /7 Therefore, Melissa played 3 games. #H 3 The answer is: 3
Fine-tuned Model Response (50K Episodes): Melissa scored 7 points each game, then the number of games she played is 2 3. ##ii 3
The answer is: 3
Fine-tuned Model Response (75K Episodes): She played 21/7 = games. ##fi 3
The answer is: 3
Fine-tuned Model Response (100K Episodes): 21/7 ##### 3
The answer is: 3
Fine-tuned Model Response (225K Episodes): 3
The answer is: 3
Figure 7: METAMATI responses to a SVAMP test question at different training stages. By the end of training. the fine-tuned model directly answers without any chain-of-then of-thhougt tokens.
Test-set Math Question: Below is an instruction that describes a task. Write a response that appropriately completes the request. ### Instruction: Kylar went to the store buy glasses for his new apartment. One glass costs $5, but every second glass costs only 60% of price. Kylar wants to buy 16 glasses. How much does he need to pay for them? ### Response: Let's think step by step.
Base Model Response: To determine how much Kylar needs to pay for 16 glasses, need to consider the pricing structure: one glass costs S5, but every second glass costs only 60% of S5, which S3. We break down the cost as follows:
1. Calculate the cost of the first glass.
2. Calculate the cost of the second glass.
Repeat this pattern for all 16 glasses.
Sum up the costs to get the total amount Kylar needs to pay.
Let's write the Python code to calculate this.
"'yython
# Define the cost of glass and the discounted cost
cost_ per glass 5 discounted cost per glass cost per glass 0.6
Total number of glasses
total glasses = 16
# Calculate the total cost total_ for in range(total glasses): if (i 1) % 2 = O: total cost += discounted_cost glass clse: total_cost += cost_per_ggte print(totall_omm ...
.. output 64.0 "* The total amount Kylar needs to pay for glasses
64
Fine-tuned Model Response (100K Episodes): The cost the first glass $5. The cost of the second glass is $5 0.60 = $3. - The cost of the third glass is $5. - The cost of the fourth glass is $5 0.60 $3. And so on... We can see that the cost alternates between $5 and $3. Since Kylar wants to buy 16 glasses, there will be 8 glasses at $5 and 8 glasses $3. The total cost is:
5
40 24 64
So, Kylar needs to pay
64
Fine-tuned Model Response (200K Episodes): Cost
=4 64
64
Fine-tuned Model Response (300K Episodes): Total = 8 8+3
8+ -04244-4044
64
Fine-tuned Model Response (500K Episodes): 8*5+ 8+548843300444664
64
Figure 8: QWEN'S responses a GSM8K test question at different training stages. The model trained with our curriculum technique learns to reduce the chain-of-though process, either by simplifying steps or skipping them. this example, the model implicitly halves the total number of glasses and computes the discounted glass price, without explicitly generating those intermediate steps.
18

---

Test-set Math Question: Below is an instruction that describes a task. Write a response that appropriately completes the request. ### Instruction: A new program had 60 downloads in the first month. The number of downloads in the second month three times as many as the downloads in the first month, but then reduced by 30% the third month. How many downloads did program have total over the three months? ?### Response: Let's think step by step.
To determine the total number of downloads over the three months, we need to calculate the number of downloads for each month and then sum them up. Let's break down:
Base Model Response:
1. **First Month: The program had 60 downloads.
2. **Second Month:*# The number of downloads in the second month was three times as many as the downloads in the first month. So, we calculate:
3 60 180
Therefore, the program had 180 downloads in the second month. **Third Month:** The number of downloads in the third month was reduced by 30
0.30 x 180 = 54
Then, we subtract this from the second month's 's downloads:
180 54 126
Therefore, the program had 126 downloads in the third month. **oota Downloads:** To find the total number downloads over the three months, we sum the downloads from each month:
60 + 180 + 126 = 366
So, the total number of downloads the three months is 366
Fine-tuned Model Response (100K Episodes): 1. The number of downloads in the first month is 60. The number downloads in second month is three times the first month, so is x 60 180.
3. The number of downloads in the third month is reduced by 30% from the second month, so is 180
0.3 x 180 = 180 54- 126.
4. The total number of downloads over the three months is 60 180 + 126 366.
The total number of downloads over the three months is 366
Fine-tuned Model Response (200K Episodes): First month: 60
Second month: 60 = 180
Third month: 180 (1 0.30) 126
Total: 60 180 + 126 366 366
Fine-tuned Model Response (300K Episodes): 3*60=180
100 60+180+126=366
366
Fine-tuned Model Response (500K Episodes): 60+180+ 126=366 366
Figure 9: QWEN's responses to a GSM8K test question at different training stages. The model trained with our curriculum technique learns reduce the chain-of-the of-thought process, either by simplifying steps or skipping them. In this example, the model implicitly computes the number of downloads for the second and third months, then directly proceeds to calculate the total.
19

---

C Proof of Theorem 1
Proof. We analyze Algorithm I in single-task setting where the environment consistently selects the same task T (Line 3).
Analysis of the target curriculum strategy (3 = 0). Under the target curriculum strategy, the teacher always selects O₁ og each time step f, ensuring that the learner consistently trains under the target setting. Initially, until a successful rollout (trajectory reaching the leftmost leaf node) is realized using the learner's current policy, learning signal is provided the learner due the zero reward. Consequently, the learner's ' policy remains unchanged during this phase.
Once successful rollout is realized, the learner receives a non-zero reward, which serves learning signal. In the best-case scenario, the learner immediately identifies the optimal policy x², given that the reward signal aligns perfectly with the target optimal trajectory. Thus, the sample or rollout complexity of this baseline is determined by the time required to achieve a successful trajectory using the initial random policy.
When sampling from a distribution, the expected number of trials needed to achieve the first success is given by the geometric distribution. If the probability of success in single trial is p, the expected number of trials to get the first success is: E NNumber of trials] =
For random policy, the probability of reaching the leftmost Icaf node a trajectory of depth H is p = -4) Consequently, the expected number of rollouts required to achieve a successful trajectory is = -2 Thus, the total number of steps taken by the learner is t K x O (24). This highlights the exponential dependence of the baseline's complexity on the depth H, reflecting the difficulty of achieving success with this baseline.
Analysis of the curriculum strategy with 3, 0.5 (1 c)- We consider the curriculum strategy defined in Eq. ( ((2)) and set the threshold parameter as B, = 0.5- (1-e))-1 which guarantees that each time step the teacher selects cost budget parameter ar that facilitates progressive learning by the agent. For the binary-tree MDP under consideration, the optimal value is given by m V* J 7 Thus, provided that y is sufficiently large-specificllyy, if 33 S H for
all f, which is ensured when y 2 0.5 we can simplify the curriculum strategy in Eq. (2) to:
ag arg min (a-aa (a) subject to (=; 2 Sc.
At time step = 1, the teacher selects aj such that:
Cr
yo
(0)
(H)
S on,
ViE (0..,0..,,
221 -1].
Cx yu
(0)
(H) an Vi (2 !!...,2" -1.
This choice guarantees that, in expectation, half of the rollouts & produced by policy yield
reward jon (<) = 1 and the other half yield J (ς) 0. Consequently, the expected value satisfies (I 2 31 = 0.5. By the end of step 1, with a sufficiently large number K₃ of rollouts, the learner correctly identifies the optimal action level with high probability. In particular, by using Hoeffding's 's inequality, the updated policy no satisfies the following:
P
LEFT
(00) -T" (LEFT)
30
(0)
c]
< 2 exp (-2- -K.K)) -2) 6.
In(2)
Thus, with probability at least - 8, if K₁
2 then:
n2
LEFT
yo (0)
2 "²"
(LEFT) 16 - = c
At step t 2, the teacher selects ag such that:
CF y0 (0)
... .1 (1))
S a2
Vi (o....., 2
20

---

compensates for the CF y0 (0)
Vi mh
a2. Vi {2 ...., 22 1 11..
This choice ensures that, in expectation, a fraction 0.5 (1 -) of the rollouts & generated by policy T2 receive a reward _ (E) = 1, with the remainder receiving _ (E) 0. Therefore, the expected value satisfies V (x; _ 2 82 = 0.5 (1 (e-e). By the end of step f 2, with a sufficiently large number K2 of rollouts, the learner identifies the optimal action at level 1 with high probability. In particular, by using Hoeffding's inequality, the updated policy 4y satisfies the following:
PP TT [EFFT Do ( - x²" (LEFT) yo (
$] S exp (-2 K2 2 S
ln(3) ())
Thus, with probability least 1 5, if K2 2
(1-e(1-c) (where the factor
e-suboptimality accumulated up to level 0), then:
T3
LEFT
yo (0)
2 π (LEFT
90
(1)
- = 1-6
eie {0,1}.
More generally, step = h, the teacher selects on such that:
Cx
yo
(0)
Vi
(H)
S Oh:
Vi {0. .0......2.. 2 1}
C+
y/
10)
Mi
(H)
> ah: ei f2 1..., - -13.
This choice guarantees that, in expectation, a fraction 0.5 (1 --0- of the rollouts produced by policy тe yield reward J (E)
with the remaining rollouts yielding J2 (g) O; hence, 4 (I; J 3n 0.5 (1 - By the end of step t h, with sufficiently large number K2, of rollouts, the learner identifies the optimal action at level 1 with high probability. Consequently, the updated policy Th+ satisfies the following:
Th++ (LFFT
y0 (
Vi E 40....,n-11 13 2 21
ln ?
with probability least 1 5. provided that K₁ (1-2((--ja=- (where the factor (1-e)-- compen- sates for the c-suboptimality accumulated up to level h 2).
This process continues iteratively until /. = H, at which point the learner recovers a near-optimal policy # satisfying:
(8) nH+1 LEFFT 30
Vi {0, .., 1}.
In(3) (1-)((--)----
with probability at least - 8. provided that K 2
The total sample complexity for learning e-suboptimal policy with probability at least 1 is therefore:
H In (2)
In (2)
Σ
K.
Σ t=1
2 2 (1 ---- S H
2. 2 (1 H-
1=1
In particular, if we choose
H+I then Σ/1 Ke = O (H1²)
2
21

---

D Implementation Details
We provide additional implementation details for the experiments described in Section 4.
D.1 Compute Resources
We conducted the LLM experiments on a SLURM cluster comprising nodes with eight Nvidia H100 GPUs. Using those resources, the longest LLM experiment ran for approximately three days. We conducted the RL experiments on a cluster comprising nodes equipped with Intel Xcon Gold CPUs.
D.2 Training Details and Hyperparameters
RL experiments. We the REINFORCE algorithm train an MLP policy [42]. For BINARYTREE. the policy is tabular, while for PUDDLEGRID-SINGLL and BEDDLEGRID-MULTT we use a neural policy with two hidden layers. Policies are updated using batch size of five episodes and the Adam optimizer with a learning rate of 3e-4 across all environments. PUDDLEGRID-SINGIAA and PUDDLEGRID- MULTI have maximum of 200 steps per episode. Since PUDDLEGRID-MUU a multi-task environment, we generated 100 tasks by randomly positioning the agent and goal. To ensure the tasks are challenging, the agent and goal are placed on opposite sides of the lava squares.
LLM experiments. As METAMATH-LLEMME. 7B serves as one of the base models in our LLM experiments, we adopt the prompt template (Figure 10), introduced by [50]. It corresponds default chain-of- of-thought prompt that encourages step-by-step reasoning. This prompting template used all methods during fine-tuning. Additionally, for both SVAMP [46] and GSM8K [47], we filter out prompts exceeding 512 tokens. To conduct the experiments, we use Huggingface's ' Accelerate and Transformers libraries. For RL fine-tuning, we employ the RLOO trainer [44] from the TRL library. training with DeepSpeed ZeRO Stage 2 [53]. The RLOO trainer is an adapted version of the PPO trainer; since REINFORCE is special case of PPO, where the number of PPO epochs and the number of mini-batches are set to 1. This formulation is adopted in the TRL implementation. All training parameters and details are reported in Figure 11. Remaining hyperparameters are set to default values and kept consistent across all baselines. Target cost budgets for all tasks are defined as percentage of the base model's original response length. Given the differing characteristics of models and datasets, we set the target cost budgets to 10% of the original response tokens for the QWEN model, and to 20% and 35% for the METAMATH model on SVAMP and GSM8K. respectively. Regarding the LLM deployment comparison, we evaluate inference metrics using Ollama [54] for both base and fine-tuned models across multiple hardware configurations. All models are converted to GGUF format.
Chain-of Thought Prompt
Below is instruction that describes task. Write response that appropriately completes the request.
### Instruction:
<question>
### Response: Let's think step by step.
Instruction template that encourages step-by-step reasoning used to format the input question. The dataset's math question replaces the <question> placeholder. This is the default prompt used across all methods during finettuning
Figure 10:
Variants of prompting templates. We experiment with different prompting templates to examine whether it possible improve the performance of large language models under test-time constraints without any fine-tuning. We explore the following variants of prompting templates. In Figure 12, we present a prompt that asks the model to provide an answer directly. In Figure 13, we present a prompt that specifically requests short answer. In Figure 14, we show prompt that instructs the model to generate an answer within specified token budget. The method ANSONlYPRROE corresponds to the prompting template that achieved the highest test performance.
22

---

Parameter
SVAMP
GSM8K
Fine- Tine-tuning Method
PEFT with LoRA
LoRa a LoRa r
96
LoRa Dropout
0.1 all linear
Target Modules
Per-device Train Batch Size
Per-device Eval Batch Size
Gradient Accumulation Steps
Local Rollout Forward Batch Size
Learning Rate
3 x 10-6
KL Coefficient
0,0001
Max Response Length
350
512
Figure 11: Training details and hyperparameters used across all baselines for S SVAMP and GSM8K.
ANSONLYPROMPT
Below is an instruction that describes task. Write a response that appropriately completes the request. Provide response that contains only the answer.
### Instruction:
<question>
### Response:
Instruction template used to format the input questions to induce direct answers without any chain-of-thought reasoning. The dataset's math question replaces the <question> placeholder.
Figure 12:
SHORTANSPROMPE
Below is an instruction that describes task. Write a response that appropriately completes the request. Provide reaponse that is as short as possible.
### Instruction:
<question> ### Response:
Figure 13:
Instruction template used to format the input questions to encourage short responses. The dataset's 's math question replaces the <question> placeholder.
ANSUNDERCONSTRAING
Below is instruction that describes task. Write response that appropriately completes the request. Provide a response where the maximum number tokens is (target_tokens, ### Instruction:
<question>
### Response:
Figure 14: Instruction template used to format the input questions to encourage answers below maximum number of tokens that correspond to the target constraint. The dataset's math question replaces the <question> placeholder.
Implementation details about our curriculum strategy CURLTRAC (Section 3). We apply our curriculum training following Algorithm 1, and update the training cost budget a using Algorithm 2.
23

---

CURLIRAC PROCURL-TARGET
EXPSCHEDULL
-IID
UNCONSTRAINT TARGET
0.8
0.8
0.5
Performance
Performance
Performance
9.6-
0.4
0.4
0.4
0.2
0.24
0.24
0.0
0.0
0.0
Episodes
Episodes
Episodes
(a) BINARYTREE
(b) PUIDDLEGRID-SINGIA
(c) PUDDI.FGRIN-MULTT
Figure 15: Performance comparison of RL agents trained with PPO learning algorithm, measured by mean return (with 95% confidence intervals for 10 random runs) under test-time constraints.
As shown, the only byperparameter is the performance threshold B. According to Line 3 of Algo- rithm 2, at each step and for each task It, the value of /3 is determined by min (3, V (10;; Jr. }} where 4 (zz; J2, denotes the maximum achievable performance for task 2t- We set B = 0.5 across all environments without any tuning. To avoid performing rollouts per task in Algorithm 1, we use buffer to collect rollouts during online training. Several design choices are possible for the buffer. Our strategy, CURLTRAC, employs fixed-size buffer that stores rollouts per task. Once the buffer for a given task is full, we update the corresponding a value using binary search procedure. The buffer then continues to store new rollouts in a FIFO manner, and the a value recomputed accordingly. The binary search is conducted over predefined range: the upper bound is set to the maximum trajectory or response length observed in the environment, and the lower bound is defined as the per-task target cost. In experiments, use K 10 for all RL and LLM settings, except for S SVAMP-QWEN, where K = 15 is used.
E
Additional Experimental Evaluation
E.1
PPO Experiments
We selected REINFORCE [42] the primary learning algorithm for main experiments because it closely aligns with the theoretical analysis. Moreover, REIRsORReett algorithms have recently gained traction in fine-tuning LLMs, such as in RLOO [44], REINFORCE++, and GRPO, due to their simplicity, efficiency, and stability. Nevertheless, we conducted additional experiments using PPO [45] across all RL environments, and report the results in Figure 15. We observe similar results with REINFORCE, indicating robustness of our technique to the choice of learning algorithm.
E.2 Parameter Sensitivity Analysis
The performance threshold / the primary hyperparameter of our strategy, CURLTRAC. As mentioned earlier, we use standard value of 3 = 0.5, which aligns with the idea of intermediate difficulty, and keep it fixed across all settings. In general, smaller values of allow for faster reduction in the training budget a, leading to quicker convergence to the target constraint. Conversely, larger values of 3 slow down this progression.
To evaluate the robustness of CURLTRAC, we conduct sensitivity analysis across all RL environ- ments. In Figure 16, we report performance under test constraints for CURLTRAC with the parameter 3 ranging from 0.1 to 0.9, where 3 = 0.5 corresponds to the default setting used in all experiments. Note that 8 and 3 correspond the TARGET and UNCONSTRAINT baselines, respectively. and are therefore excluded. Figure 16 shows that CURLTRAC is highly robust, performing well across a wide range of 3 values. As expected, increasing 3 slows down the change in training cost budget (Figure 16b), which in turn affects performance. In Figure 16c, we observe how CURL- TRAC controls the observed reward during training, maintaining it below the respective threshold B. Additionally, conduct sensitivity analysis across all RL environments. In Figure 17, we present the
24

---

CURLTRAC CURLTRACA 5-06
CURLIRAC C 2005
CURLTRAC
CCRL-TRAJG3a0
CURLTRACa-a: CURLTRACA
CURLTRACa-as
1.0
4000
Mean Training Reward
Mean Training Cost
0.8
Performance
3000
0.6-
6.66
2000
1000+
0.24
0.2
0.0
2 Episodes
2 Episodes
x100
Episodes
x100
x10
(a) Performance
(b) Training cost
(c) Training Reward
Figure 16: Sensitivity analysis of performance threshold parameter & for CURLTRAC strategy in BINARYTREE environment. (a) shows the performance measured by mean return under test-time constraints. (b) shows the progression of the cost during training. (c) shows the average observed reward during training.
CURLTRAC3
CURLTRAC; as
CURLTRAC 0.3
CURLTRAC JURL-TRAJC3-.. as
C
CORLTRAC
CURLTRACa500
CURLTRAC
1.0
2004
1.0
Mean Training Reward
175
Mean Training Cost
Performance
1266
150
0.6
125+
0066
100
754
50
0.2-
25
0.0
0.0
3
3
5
Episodes
110
Episodes
Episodes
(a) Performance
(b) Training cost a
(c) Training Reward
Figure 17: Sensitivity analysis of performance threshold parameter 3 for CURLTRAC strategy in PUDDLEGRID-SINGLL environment. (a) shows the performance measured by mean return under test-time constraints. (b) shows the progression of the cost during training, (c) shows the average observed reward during training.
CURETRAA
CURLTRACaEs
CURETRRAG
CURETTAC CURL-TTRRRR TRA3C-s
CURETRACCas
CURLTRAC
CURETRACA-0
CURETTAC
1.0
2004
1.0
Mean Training Reward
175+
Mean Training Cost
0.8-
Performance
150+
0.6
00.6+
100+
0.4
50-
0.24
25.
0.0
0.0
3
12
15
13
12
is
Episodes
Episodes
Episodes
(a) Performance
(b) Training cost a
(c) Training Reward
Figure 18: Sensitivity analysis of performance threshold parameter & for CURLTRAC strategy in PUDDLEGRID-MULTT environment. (a) shows the performance measured by mean return under test-time constraints. (b) shows the progression of the cost during training. (c) shows the average observed reward during training.
25

---

CURLTRAC EXPSCHEDULE,.1
EXPSCHEDULE; 1-22
EXPSCHEDULE, EXPSCHEDULE
1.0
6.8
6.6
0.54
Perforance
Performanes
Performance
6-6-
0.44
0.4
0.0
0.0
0.0g
Episodes
Episodes
(a) BINARY
(b) PUDDLEGRID-SINGILE
(c) PUDDLEGRID-MULLI
Figure 19: Performance comparison of agents trained with variants of EXPSCHEDULE, measured by mean return (with 95% confidence intervals for 10 random runs) under test-time constraints.
results for the PUDDLEGRID-SING environment, where the robustness of CURLTRAC is evident (Figure 17)). As expected, increasing 3 slows convergence to the test-time target constraints. The training cost trends are similar to those observed in BINARYTREE, though the differences are less pronounced due to the increased complexity of PUDDLEGRID-SINGLI (Figure 17b). The choice of 3 directly influences the level training reward observed (Figure 17c). Similarly, for multi-task environments, CURLTRAC behaves expected across different & values (Figure 18).
E.3 Additional Baselines
To provide more thorough evaluation of our curriculum, we incorporate several additional baselines.
Variants of EXPSCHEDULE. As illustrated in Figure 5, our curriculum strategy naturally produces per-task schedules that, on average, follow form of exponential decay. This observation motivates the inclusion of a related baseline, EXPSCHEDULE, which applies a fixed exponential decay schedule [51]. The intuition is that a well-tuned exponential decay should perform comparably
strategy.
We evaluate variants of this strategy with different decay lengths T (T" T /2, 50000, 5000}, where I denotes the total number of training episodes per environment. These correspond Ex- #SCHEDULET_TT. EXPSCHEDULEy /2. EXPSCHEDULE7 and EXPSCHEDULET respectively. Figure 19 compares our strategy, CURLTRAC, with the variants of EXPSCHEDULE across RL environments. Our approach consistently achieves the strongest and most stable empirical performance. In contrast, the fixed exponential schedules exhibit instability, yielding competitive results in some environments but failing to generalize across all. Among the exponential variants, EXPSCHEDULEE==" /2 demonstrates comparatively greater stability, albeit with lower overall per- formance than CURLTRAC. This suggests that incorporating domain knowledge, such as the total number training episodes T** plays a critical role tuning the decay schedule effectively.
This is a variant of CURLTRAC that maintains a single global value of shared across all tasks, rather than assigming an individual training budget as per task x. We refer to this method as CURLTRAC-GLOO that rollouts from all selected tasks are stored in common global buffer. As a result, single global training budget a is updated after each task. In single-task settings (as in BINARY and PUDDLEGRID- -GINGGLGE-E,, the two strategies are equivalent. The adaptive CURLTRAC requires collecting a sufficient number of rollouts per task to enable task-specific updates of a. In contrast, one advantage of CRR.TTAA-GGLOR
CURLTRAC-GLOBE
The procedure is identical to CURLTRAC, except
a shorter warm-up phase, as the global buffer is populated with rollouts from multiple tasks, allowing the threshold a to begin adapting earlier. We provide direct comparison between CURLTRAC and its global variant, WARLTRAC-GLOBAR
Performance comparison with additional baselines. In Figure 20, we compare the convergence behavior of LLM agents across additional baselines, including the global strategy CURLTRAC- GLOBAL, a softer regularization variant SOFT-RLa.. and fixed decay rate strategy EXp- SCHEDULE, =00000 Table 2 summarizes test-time performance two training checkpoints. The strategy CURLTRAC-GG.OBAL shows a rapid initial performance increase, as it does not require a warm-up phase for collecting rollouts per task. However, due to per-task targets in the LLM setting, its performance ultimately plateaus below that of the adaptive CURLTRAC. The weaker regular- ization SI 0.4 leads to slower convergence toward test-time constraints compared to CoFT-RLogest 0.9.. expected. The EXPSCHEDULEY strategy is unstable across all settings.
26

---

CURLTRAC
SorT-Rlo ExpSemnctttag
UNCONSTRAINT
TARGET ANsOsLY
CURLTRRC--GOBAL
SOFT-RI Rl
EXPSCHEDULEy.PPp
0.5
0.5
0.6
0.5-
Performance
Performance
0.24
0.24
0.34
0,3
00
20
20
30
30
Episodes
Episodes
10
(a) SVAMP-QWER
(b) HHAMP-METAMATH
0.5
Performance
Performance
0.:4
0.2-
0.2-
0.00
0.3
20
20
40
20
00
50
300
Episades
Episades
(c) GSM8K QWEN
(d) GSM8K METAMATH
Figure 20: Performance of LLM agents trained with different strategies, measured by the agent's 's mean accuracy (with 95% confidence intervals over random runs), evaluated under test-time constraints.
Table 2: Summary L.LM performance across two mathematical benchmarks, SVAMP and GSM8K, and two large language models, QW MAAN2.55-MAH-111 and METAMATH-LLEEMAAE as detailed Figure 20. For each column, the underlined.
strategy is shown in bold, and the second-best
Dataset: SVAMP
Dataset: GSMBK
Model: QWEN
Model: METAMATH
Model: QWEN
Model: METAMATH
Method
# Episodes
Episodes
Episodes
Episodes
100K
250K
250K
500K
250K
500K
500K
IM
Test-time Performance
CURLTRAC
0.69
0.74
0.63
0.63
0.43
0.60
0.49
0.53
CURLTRAC-GL.OT
0.60
0.63
0.62
0.62
0.49
0.48
0.49
0.46
SOFT-RA SOFT-RLo..e RL
0.19
0.44
0.24
0.41
0.43
0.49
SOFT-RLong--0
0.26
0.69
0.54
0.54
0.52
0.50
0.49
0.47
EXPSCHEDULEY-.coM
0.48
0.45
0.00
0.00
0.00
0.00
0.00
0.00
EXPSCHEDULEY--r09
0.10
0.55
0.52
0.48
0.20
0.20
0.10
0.10
IID
0.00
0.03
0.00
0.00
0.01
0.06
0.00
0.00
UNCONSTRAINT
0.00
0.00)
0.00
0.00
(1.00
0.00
0.00
0.00
TARGET
0.00
0.00
0.00
0.00
0.00
ANSONLYPROMPT
0.28
0.28
0.00
0.00
0.00
0.00
0.00
0.00
27


Reviews:
[{"review_id": "NB7mDruuvh", "reviewer": "Reviewer_sU2F", "summary": "- In the paper the authors try to address the problem of deployment constraints in terms of budget or safety requirements while training RL agents.\n- The authors propose a curriculum learning strategy to dynamically/adaptively adjust the constraints (from relaxed to strict) during the training of RL agents based on their performance. \n- The authors try to find answers to the question: “How to guide the training and get the best performance when deployment-time constraints advance”\n- The paper introduces a curriculum learning framework to have a sample and compute efficient training strategy under strict trajectory-level constraints so that the final policy can adapt to strict resource and safety requirements.\n- The authors test this framework on a toy binary-tree MDP example and as well as multi-task navigation and LLM based math reasoning tasks.\n- When applying this curriculum learning based strategy for LLM tasks, they claim to have compressed output tokens (a deployment constraint) with a 4.5x inference speedup on consumer hardware. \n- The paper formulates this strategy as a constrained MDP problem where the RL agent (student) tries to roll out the policy to accomplish a task (from the task space) given a required constrained/budget, get the training-time (constrained) rewards and updates the policy. A teacher component is responsible for adjusting/replacing the deployment-time budget with the relaxed training-time cost. \n  - This is done to ensure that the  final performance of the policy is eps-near-optimal. \n  - The framework now tries to optimize the teacher component to select permissible training time budget so that the required policy performance is achieved efficiently in terms of cost and sample complexity.", "questions": "- How can we impose other real-time constraints like memory constraints in terms of model size, quantization, GPU memory, etc?\n- Do we have any numbers/plots in terms of latency or inference-speed?\n\nSuggestions:\n- Models that can be deployed under different/dynamic test-time constraints or budgets can be trained (similar to [Matryoshka style learning](https://arxiv.org/abs/2205.13147)) and can be adaptively used as per budget requirements as they change with time.", "limitations": "- The authors mentioned extending this work to the programming/code generation domains as well rather than just for math.\n- How the model optimizes for the given constraints during the training is still unclear.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "** Strengths:**\n- The authors try to solve the sparse reward problem of training with the strict deployment constraints from the beginning and instead try to introduce a curriculum strategy.\n- The paper did a good job in providing a thorough theoretical analysis of how the proposed strategy would work for the toy example of binary-tree MDP.\n  - The paper is able to prove that imposing a target/deployment-time budget at the start of the training would require an exponential number of rollouts as compared to polynomial $O(H^3)$ sample complexity in case of curriculum strategy. \n  - The paper shows theoretically that the proposed strategy reduces the number of rollouts required to learn an eps-suboptimal policy. \n- Results from experiments on other environments (navigation and LLM reasoning) supported the theoretical results. \nThe results and the plots are nicely presented. \n\n**Weakness:**\n- It would be nice to have some tabular results as well to have some numerical analysis.\n\n- While there have been good efforts in terms of having theoretical and empirical analysis, this work seems to be deriving few things from the ProCurl-Target work (it does not mean that this fact downweighs this paper’s efforts), this can still be experimented and extended to some other high-dimensional tasks and other LLM or VLM domains to have more real-world constraints.\n\n- This work can present more LLM based use-cases as well given the title of the paper. \n- It would be can be worth trying to incorporate some constraints related to: \n  - different (reduced) input token numbers \n  - token generation: tokens/sec\n  - other test-time scaling constraints.\n  - some subjective constraints like safety, preference, etc.", "was_revised": true, "final_justification": "The authors tried to resolve some of the concerns during the rebuttal.\n- Authors mentioned the work is not directly related to ProCurL-Target framework.\n- Additional LLM-based experiments were conducted that could be more suitable given the proposals and title of the paper.\n- Authors mentioned that system-level constraints like memory usage, quantization, or model size fall outside the current scope of o the proposed framework.\n\nThere are still some future directions that were agreed upon by the authors in the rebuttal and those would be great if worked upon or at least included in the future directions in the final version of the paper.\n\nThis work is a good combination of research and practical engineering. I hope to have a better and more comprehensive final version of the paper. I would still like to maintain my score.", "rebuttal": "Thank you for carefully reviewing our paper! We greatly appreciate your feedback. Please see below our responses to your comments.\n\n-----\n\n**1. It would be nice to have some tabular results as well to have some numerical analysis.**\n\nWe focus on test performance curves and training plots to highlight the learning dynamics and how agent behavior evolves throughout training. We thank the reviewer for the suggestion and are happy to include tabular results in the Appendix, reporting performance metrics along with a brief analysis.\n\n-----\n\n**2. While there have been good efforts in terms of having theoretical and empirical analysis, this work seems to be deriving few things from the ProCurl-Target work (it does not mean that this fact downweighs this paper’s efforts), this can still be experimented and extended to some other high-dimensional tasks and other LLM or VLM domains to have more real-world constraints.**\n\nWe would like to clarify that our work does not derive techniques from the ProCuRL-Target framework. There are several key conceptual and methodological differences: (1) ProCuRL-Target focuses on curriculum design for contextual RL, whereas our work targets RL with trajectory-level constraints — Section 4.2 discusses why ProCuRL-Target is not practical for large-scale constrained RL settings; (2) their curriculum strategy is based on the ZPD principle, while ours is inspired by self-paced learning; (3) our theoretical formulation, analysis, and proof techniques are entirely different and novel; and (4) unlike ProCuRL-Target, we include LLM-based experiments in the main paper and have added further LLM results in this rebuttal. \n\n-----\n\n**3. This work can present more LLM-based use-cases as well, given the title of the paper.**\n\nWe have conducted additional LLM-based experiments, which will be included in the revised version of the paper.\n\nThe new experiments include:\n\n- A model of different family and size — Qwen2.5-Math-1.5B — evaluated on both datasets.\n\n- A variable target setting, where each task $t$ has its own target budget $\\alpha^*$, determined based on the original model response length. This setting is applied across both models and datasets, resulting in four additional experiments. \n\nWe present the results in tabular form below.\n\n**Experiments with Qwen2.5-Math-1.5B: SVAMP**\n\n| Method | 50K | 100K | 150K | 200K | 250K | \n| ----- | --- | --- | --- | --- | --- | \n| CuRL-TrajC (ours) | $0.59$ | $0.78$ | $0.81$ | $0.80$ | $0.81$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.00$ |  $0.00$ | $0.64$ | \n| IID | $0.00$  | $0.00$ | $0.02$ | $0.20$ | $0.29$ | \n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.57$ | $0.61$ | $0.60$ |\n|\n \n**Experiments with Qwen2.5-Math-1.5B: GSM8K**\n\n| Method | 200K | 300K | 400K | 500K | \n| ----- | --- | --- | --- | --- |\n| CuRL-TrajC (ours) | $0.37$ | $0.56$ | $0.58$ | $0.62$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.04$ |  $0.50$ | \n| IID | $0.02$  | $0.03$ | $0.13$ | $0.17$ |\n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.23$ | $0.25$ | $0.25$ | $0.25$ |\n|\n\n**Experiments with variable targets Qwen2.5-Math-1.5B: SVAMP**\n\n| Method | 50K | 100K | 150K | 200K | 250K | \n| ----- | --- | --- | --- | --- | --- | \n| CuRL-TrajC (ours) | $0.27$ | $0.76$ | $0.77$ | $0.77$ | $0.77$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.00$ |  $0.00$ | $0.60$ | \n| IID | $0.00$  | $0.00$ | $0.01$ | $0.02$ | $0.07$ | \n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n|\n\n**Experiments with variable targets Qwen2.5-Math-1.5B: GSM8K**\n\n| Method | 200K | 300K | 400K | 500K | \n| ----- | --- | --- | --- | --- | \n| CuRL-TrajC (ours) | $0.26$ | $0.49$ | $0.56$ | $0.61$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.01$ |  $0.23$ | \n| IID | $0.01$  | $0.02$ | $0.08$ | $0.05$ |\n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n|\n\n**Experiments with variable targets MetaMath: SVAMP**\n\n| Method | 50K | 100K | 150K | 200K | 250K | \n| ----- | --- | --- | --- | --- | --- | \n| CuRL-TrajC (ours) | $0.06$ | $0.46$ | $0.61$ | $0.63$ | $0.63$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.00$ |  $0.04$ | $0.58$ | \n| IID | $0.00$  | $0.00$ | $0.00$ | $0.01$ | $0.00$ | \n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n|\n\n**Experiments with variable targets MetaMath: GSM8K**\n\n| Method | 200K | 300K | 400K | 500K | \n| ----- | --- | --- | --- | --- |\n| CuRL-TrajC (ours) | $0.18$ | $0.38$ | $0.41$ | $0.42$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.00$ |  $0.27$ | \n| IID | $0.00$  | $0.00$ | $0.00$ | $0.00$ |\n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n|\n\n-----\n\n**4. It would be worth trying to incorporate some constraints related to: i) different (reduced) input token numbers, ii) token generation: tokens/sec, iii) other test-time scaling constraints, iv) some subjective constraints like safety, preference, etc., v) memory constraints in terms of model size, quantization, GPU memory.**\n\nWe would like to note that our problem setup — and the proposed curriculum strategy — applies broadly to scenarios where trajectory-level constraints can be expressed via a cost function over the output or response trajectories. More concretely:\n\n- Reaching a goal under navigation cost constraints, as demonstrated in the paper through the agent's path cost in MiniGrid. \n\n- LLM output generation with reduced reasoning tokens, also covered in the paper as trajectory length constraints. \n\n- In the rebuttal, we present additional LLM experiments involving variable token length constraints based on original model response length.\n\nBeyond these, our method naturally extends to: \n\n- Harmfulness constraints in LLMs, where a harmfulness or toxicity score can serve as the cost function. \n\n- Code generation tasks, where generated programs must satisfy test cases or meet resource/memory constraints — both of which can be captured via cost functions over the generated output.\n\nWhile system-level constraints like memory usage, quantization, or model size are important, they fall outside the current scope of our framework, which is designed to handle constraints that can be expressed as cost functions over output trajectories.\n\nIn general, any constraint on response trajectories that can be formalized as a cost function is compatible with our framework. While it’s not practical to include all possible scenarios in the paper, we aimed to showcase a representative set of impactful applications. \n\n-----\n\n**5. Do we have any numbers/plots in terms of latency or inference speed?**\n\nAt the end of Section 4.3, we provide a qualitative comparison of the inference time comparison between the model fine-tuned using our approach and the original model to highlight its practical impact. In the revised version, we are happy to include a more detailed comparison to further support this analysis. \n\n-----\n\n**6. The authors mentioned extending this work to the programming/code generation domains as well rather than just for math.** \n\nWe focused on mathematical tasks because they are widely regarded as standard benchmarks for evaluating the reasoning capabilities of LLMs. Nevertheless, as noted in our earlier response, while math problems often use reasoning length as a constraint, code generation introduces different types of constraints. In addition to achieving the task objective, generated code may need to meet specific security requirements, satisfy test cases, or stay within memory or compute resource limits during execution. These can be naturally incorporated into our framework by defining appropriate cost functions — e.g., test-case pass rates or programmatic evaluations — over the code/program space.\n\n-----\n\n**7. How the model optimizes for the given constraints during the training is still unclear.**\n\nThe student model is optimized using a standard RL update rule, where the reward function depends on the training constraint or budget selected by the teacher at each step t. As a result, the reward function is non-stationary throughout training, i.e., starting with an unconstrained reward setting and gradually shifting toward the target constraint. The student thus learns under a progressively constrained reward landscape. We will clarify this point in the revised draft.\n\n-----\n\n**8. Models that can be deployed under different/dynamic test-time constraints or budgets can be trained (similar to Matryoshka style learning) and can be adaptively used as per budget requirements as they change with time.**\n\nThis is a very interesting suggestion, and we thank the reviewer for highlighting it. We view this as a promising direction for future work. \n\n-----\n\n**9. ​​It would be nice to define what is meant by “Performance” in the plots or how it is calculated.**\n\nPerformance refers to the agent’s average return when evaluated on the test tasks under the target test-time constraints. We will clarify this in the revised version.\n\n-----\n\nWe hope that our responses can address your concerns and are helpful in improving your rating. If you have any other comments or feedback, please let us know! We are looking forward to hearing back from you! Thank you again for the review."}, {"review_id": "sObPGGhOsv", "reviewer": "Reviewer_CkZL", "summary": "The paper presents a new curriculum learning paradigm for addressing exploration tasks with hard constraints. The gist of the approach is the use of a teacher that can shape the reward of the learner, specifically constructed to reflect a sparse reward structure, so that they can learn with increasingly lower budgets. A theoretical analysis is provided for the case of a binary-tree MDP. Empirical evaluation covers 3 domains (4 if counting both PuddlePoint), with the last one being a real-world LLM solving a math problem using a chain-of-thought step count as a budget. The results show improved performance under strict test-time constraints, including higher success rates and shorter outputs for LLMs, without violating the budget.", "questions": "1. What are your thoughts about the theoretical analysis of this approach beyond the binary-tree MDP? Obviously it might be much more challenging to provide sound claims, but I wonder about your intuitions. When will it work well and when will it fail?\n2. Have you explored generalization to unseen tasks beyond the ones used during training?\n3. How sensitive is the approach to curriculum parameters like the performance threshold beta?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n+ The problem formulation of exploration under hard constraints or a budget is an important step towards practical agents.\n+ Using curriculum learning with RL exploration for LLMs is a novel and promising approach with practical potential.\n+ The paper is mostly well-written and easy to follow.\n\nWeaknesses:\n- While the idea of the curriculum is novel and has merit, the outcome of the proposed approach is limited: Theorem 1 covers only the binary-tree MDP case. Most exploration problems are more complex than that, so it is unclear how much merit this theorem provides. Moreover, the curriculum relies on accurate performance estimation at various constraint levels using only the learner's rollouts. In complex domains like MathLLM, where each rollout is expensive and noisy, this may limit the teacher's ability to adaptively select effective budgets.\n- The paper cites a recent survey of curriculum learning for RL agents [19], but ignores the content of the survey beyond the reference. It can provide useful vocabulary for this work (e.g., threshold performance).\n- The paper similarly mentions a recent work that is similar [14], but refers to it beyond the reference number only in the empirical methods. This work seems to be the closest to this one, so it should be better explained (in the introduction, not as an afterthought in the methods) what the gaps are that [14] still has and are addressed here.", "was_revised": true, "final_justification": "The authors have engaged in the discussion and answered my questions to my satisfaction. Given their responses and the other reviews, I keep my score as is.", "rebuttal": "Thank you for carefully reviewing our paper! We greatly appreciate your feedback. Please see below our responses to your comments.\n\n-----\n\n**1. While the idea of the curriculum is novel and has merit, the outcome of the proposed approach is limited: Theorem 1 covers only the binary-tree MDP case. Most exploration problems are more complex than that, so it is unclear how much merit this theorem provides … What are your thoughts about the theoretical analysis of this approach beyond the binary-tree MDP? Obviously it might be much more challenging to provide sound claims, but I wonder about your intuitions. When will it work well and when will it fail?**\n\nWe note that binary-tree (or chain-style) environments are canonical settings frequently used in exploration-focused RL theory due to their interpretability and the analytical insights they offer. Our analysis can indeed be extended to more general structures such as multi-branch tree MDPs or star-shaped directed graph MDPs, though the derivations become more involved. For clarity and ease of exposition, we chose to focus on the binary-tree case.  \n\nInterestingly, as shown in [1], many reasoning tasks with concrete goals in LLMs can be modeled as star-shaped directed graphs. In this light, our analysis is relevant to more practical problems as well. Overall, the theoretical guarantees provided in this simplified setting help build foundational understanding, while our empirical results validate the method across both RL and LLM domains.  \n\n [1] Bachmann and Nagarajan, 2024. “The Pitfalls of Next-Token Prediction”. ICML 2024\n\n-----\n\n**2. Moreover, the curriculum relies on accurate performance estimation at various constraint levels using only the learner's rollouts. In complex domains like MathLLM, where each rollout is expensive and noisy, this may limit the teacher's ability to adaptively select effective budgets.**\n\nWe would like to clarify that our method does not require collecting additional rollouts at different constraint levels to adapt the training budget $\\alpha$. Instead, the teacher selects $\\alpha$ based solely on the history of rollouts already collected during the student’s training. As a result, there is no added computational overhead. While this may introduce some noise in budget estimation, our experimental results demonstrate that the adaptively selected budgets are still effective in practice. We will clarify this in the implementation section of the revised draft. \n\n-----\n\n**3. The paper similarly mentions a recent work that is similar [14], but refers to it beyond the reference number only in the empirical methods. This work seems to be the closest to this one, so it should be better explained (in the introduction, not as an afterthought in the methods) what the gaps are that [14] still has and are addressed here.**\n\nThere are several key conceptual and methodological differences between the ProCuRL-Target framework and our work: (1) ProCuRL-Target focuses on curriculum design for contextual RL, whereas our work targets RL with trajectory-level constraints — Section 4.2 discusses why ProCuRL-Target is not practical for large-scale constrained RL settings; (2) their curriculum strategy is based on the ZPD principle, while ours is inspired by self-paced learning; (3) our theoretical formulation, analysis, and proof techniques are entirely different and novel; and (4) unlike ProCuRL-Target, we include LLM-based experiments in the main paper. We will make these distinctions explicit in the introduction of the final draft.\n\n-----\n\n**4. Have you explored generalization to unseen tasks beyond the ones used during training?**\n\nYes, in the LLM experiments, performance under test-time constraints is evaluated on unseen test sets for both the SVAMP and GSM8K datasets, demonstrating the model's ability to generalize beyond the training tasks. \n\n-----\n\n**5. How sensitive is the approach to curriculum parameters like the performance threshold beta?**\n\nWe would like to emphasize that in our experiments, we did not fine-tune the performance threshold $\\beta$. We used a standard value of $\\beta = 0.5$, which aligns with the principle of intermediate difficulty, and kept it fixed across all settings. In general, smaller values of $\\beta$ allow a faster decrease in the training budget $\\alpha$, resulting in quicker convergence to the target constraint. Conversely, larger $\\beta$ values slow down this progression.\n\nTo evaluate robustness, we conducted an ablation study on $\\beta$ across all RL environments. We will include these results in the Appendix and present them below.\n\n**Performance of CuRL-TrajC w.r.t. performance threshold $\\beta$: BinaryTree**\n\n| $\\beta$ | 20K | 30K | 40K | \n| ----- | --- | --- | --- | \n| 0.1 | $0.24$ | $0.73$ | $0.90$ | \n| 0.2 | $0.29$ | $0.73$ | $0.90$ | \n| 0.3 | $0.30$ | $0.74$ | $0.90$ | \n| 0.4 | $0.30$ | $0.73$ | $0.90$ |\n| 0.5 (paper) | $0.23$ | $0.70$ | $0.90$ |\n| 0.6 | $0.17$ | $0.60$ | $0.86$ | \n| 0.7 | $0.10$ | $0.41$ | $0.82$ | \n| 0.8 | $0.04$ | $0.23$ | $0.56$ | \n| 0.9 | $0.01$ | $0.05$ | $0.16$ |\n|\n\n**Performance of CuRL-TrajC w.r.t. performance threshold $\\beta$: PuddleGrid-Single**\n\n| $\\beta$ | 2K | 3K | 4K | 5K |\n| ----- | --- | --- | --- | --- |\n| 0.1 | $0.01$ | $0.13$ | $0.55$ |  $0.93$ | \n| 0.2 | $0.00$ | $0.35$ | $0.71$ |  $0.95$ | \n| 0.3 | $0.06$ | $0.38$ | $0.85$ |  $0.97$ | \n| 0.4 | $0.07$ | $0.37$ | $0.80$ | $0.97$ | \n| 0.5 (paper) | $0.10$ | $0.33$ | $0.77$ | $0.97$ | \n| 0.6 | $0.07$ | $0.28$ | $0.77$ |  $0.97$ | \n| 0.7 | $0.05$ | $0.19$ | $0.65$ |  $0.96$ | \n| 0.8 | $0.07$ | $0.16$ | $0.54$ |  $0.96$ | \n| 0.9 | $0.04$ | $0.08$ | $0.22$ | $0.60$ | \n|\n\n**Performance of CuRL-TrajC w.r.t. performance threshold $\\beta$: PuddleGrid-Multi**\n\n| $\\beta$ | 5K | 10K | 15K |\n| ----- | --- | --- | --- | \n| 0.1 | $0.44$ | $0.91$ | $0.98$ | \n| 0.2 | $0.37$ | $0.98$ | $0.99$ | \n| 0.3 | $0.40$ | $0.91$ | $0.98$ |  \n| 0.4 | $0.30$ | $0.94$ | $0.97$ | \n| 0.5 (paper) | $0.30$ | $0.94$ | $0.98$ | \n| 0.6 | $0.26$ | $0.73$ | $0.94$ |  \n| 0.7 | $0.30$ | $0.81$ | $0.98$ |  \n| 0.8 | $0.27$ | $0.56$ | $0.81$ |  \n| 0.9 | $0.20$ | $0.40$ | $0.42$ |\n|\n\nNote that $\\beta=0$ and $\\beta=1$ correspond to the Target and Unconstrained baselines respectively, and are therefore excluded from the tables.\n\n-----\n\n**6. The paper cites a recent survey of curriculum learning for RL agents [19], but ignores the content of the survey beyond the reference. It can provide useful vocabulary for this work (e.g., threshold performance).** \n\nWe thank the reviewer for this helpful suggestion and will take it into consideration. Throughout the paper, we have used standard terminology from the curriculum learning and reinforcement learning literature. \n\n-----\n\nWe hope that our responses can address your concerns and are helpful in improving your rating. If you have any other comments or feedback, please let us know! We are looking forward to hearing back from you! Thank you again for the review."}, {"review_id": "woDpfIptkI", "reviewer": "Reviewer_jEUn", "summary": "This paper introduces a curriculum learning strategy for training agents to operate deployment time constraints like limited resources or safety requirements. The method adaptively adjusts cost budget during training, starting off with more relaxed constraints and then slowly makes the constraints more restrictive. This helps smoothen the transition into the more strict deployment conditions. The paper provides theoretical analysis that demonstrates the curriculum strategy accelerates training compared to baseline approaches that enforce the strict constraints right from the start. Empirically, the method is tested on reinforcement learning and LLM agents and achieves significant inference time speedup for LLM output token compression hardware.", "questions": "Questions\n- does the teacher component incur an additional computational overhead?\n- is token length =40 a real world constraint? I suppose constraints like memory footprint or harmfulness scores would be considered a more meaningful constraints in the semantic experiments of the LLM space\n- how would you choose for a new task what the best maximal/relaxed cost budget to start off with is? Is it always 1/(1-gamma)?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- the problem is well-motivated and the writing is generally clear\n- while having an adaptive budget for curriculum isn’t exactly a novel concept [1], I think examining the empirical performance of adapting costs in application to RL for LLM is quite interesting\n- the approach is promising in that it demonstrates significant performance improvements compared to baseline in highly complex tasks like solving gsm8k reasoning questions\n- overall the approach is theoretically grounded in computational/sample complexity\n\nWeakness\n- for th rl experiments it would have been nice to see experiments with a bit more complex algorithms than reinforce, like sota ones including ppo\n- also safe rl environments that are more complex than puddle-grid would be valuable\n- (minor) it would be nice to have a table of contents of all the variables defined (perhaps in appendix) for improved readability\n- (minor) in the figures, you should indicate which algorithm is the papers with something like (ours) to distinguish from baselines\n\n[1]Narvekar et al. \"Curriculum learning for reinforcement learning domains: A framework and survey.\" JMLR 2020", "was_revised": true, "final_justification": "My main concern was with the baselines -- specifically I recommended the authors consider sota RL algorithms to compare such as PPO. The authors have provided these results during the rebuttal.", "rebuttal": "Thank you for carefully reviewing our paper! We greatly appreciate your feedback. Please see below our responses to your comments.\n\n-----\n\n**1. For the RL experiments it would have been nice to see experiments with a bit more complex algorithms than reinforce, like sota ones including ppo.**\n\nWe have conducted additional experiments using PPO across all RL environments and report the results below.\n\n**Experiments with PPO algorithm: BinaryTree**\n\n| Method | 10K | 20K | 30K | 40K | \n| ----- | --- | --- | --- | --- | \n| CuRL-TrajC (ours) | $0.30$ | 0.93 | $0.97$ | $0.99$ | \n| ProCuRL-Target | $0.02$ | $0.50$ | $0.63$ | $0.74$ | \n| ExpSchedule | $0.00$  | $0.04$ | $0.10$ |  $0.54$ | \n| IID | $0.01$  | $0.16$ | $0.26$ | $0.44$ \n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.05$ | $0.15$ |\n|\n\n**Experiments with PPO algorithm: PuddleGrid-Single**\n\n| Method | 2K | 3K | 4K | 5K | \n| ----- | --- | --- | --- | --- |\n| CuRL-TrajC (ours) | $0.25$ | $0.60$| $0.78$ | $0.83$ | \n| ProCuRL-Target | $0.18$ | $0.30$ | $0.33$ | $0.47$ | \n| ExpSchedule | $0.10$  | $0.06$ | $0.05$ |  $0.06$ | \n| IID | $0.09$  | $0.07$ | $0.10$ | $0.08$ \n| Unconstrained | $0.04$ | $0.02$ | $0.01$ | $0.00$ |\n| Target | $0.01$ | $0.00$ | $0.01$ | $0.00$ |\n|\n\n**Experiments with PPO algorithm: PuddleGrid-Multi**\n\n| Method | 2K | 5K | 8K | 10K | \n| ----- | --- | --- | --- | --- |\n| CuRL-TrajC (ours) | $0.36$ | $0.65$ | $0.84$ | $0.90$ | \n| ProCuRL-Target | $0.41$ | $0.68$ | $0.72$ | $0.71$ | \n| ExpSchedule | $0.31$  | $0.30$ | $0.33$ |  $0.46$ | \n| IID | $0.24$  | $0.27$ | $0.25$ | $0.25$ \n| Unconstrained | $0.20$ | $0.20$ | $0.26$ | $0.24$ |\n| Target | $0.00$ | $0.20$ | $0.30$ | $0.36$ |\n|\n\nWe selected REINFORCE as the primary learning algorithm for our experiments because it closely aligns with the theoretical analysis presented in the paper. Moreover, REINFORCE-style methods have recently gained traction in fine-tuning LLMs — such as in RLOO [1], REINFORCE++ [2], and GRPO — due to their simplicity, efficiency, and stability. Notably, in our LLM experiments, we use the RLOO training algorithm.\n\n[1] Ahmadian et al., “Back to Basics: Revisiting REINFORCE Style Optimization for Learning from Human Feedback in LLMs”, arXiv preprint arXiv:2402.14740 (2024).\n\n[2] Hu et al., \"REINFORCE++: An Efficient RLHF Algorithm with Robustness to Both Prompt and Reward Models.\", arXiv preprint arXiv:2501.03262 (2025).\n\n[3] Shao et al., \"DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models.\" arXiv preprint arXiv:2402.03300 (2024).\n\n-----\n\n**2. Safe RL environments that are more complex than puddle-grid would be valuable.**\n\nMinigrid-style environments such as PuddleGrid-Single and PuddleGrid-Multi have been used in recent safe reinforcement learning literature ([1], [2]) as standard benchmarks for studying goal-reaching tasks under navigation cost constraints. We consider these environments sufficiently rich to evaluate our proposed method and to provide meaningful insights into its effectiveness. Moreover, our work includes a diverse range of experiments involving both RL and LLM agents. That said, we agree that exploring additional complex environments would be an interesting direction for future work. \n\n[1] Kim et al., “Sample-Efficient and Safe Deep Reinforcement Learning via Reset Deep Ensemble Agents”, NeurIPS 2023.\n\n[2] Gros et al., “Safe Reinforcement Learning Through Regret and State Restorations in Evaluation Stages”, AAAI 2024.\n\n-----\n\n**3. Does the teacher component incur an additional computational overhead?**\n\nThe teacher selects the current training budget $\\alpha$ using a simple binary search procedure, which incurs minimal computational overhead. Importantly, it relies solely on rollout histories already collected by the student during training, so no additional rollouts are required — making the budget estimation effectively cost-free.\n\n-----\n\n**4. Is token length =40 a real world constraint? I suppose constraints like memory footprint or harmfulness scores would be considered a more meaningful constraints in the semantic experiments of the LLM space.**\n\nA constraint on response length naturally arises in scenarios where users require faster responses or reduced inference cost and time. Fine-tuning LLMs to produce more concise, less verbose reasoning can lead to more efficient and practical deployments. Thus, we view length constraints as a meaningful and realistic use case.\n\nWe would like to note that our problem setup — and the proposed curriculum strategy — applies broadly to scenarios where trajectory-level constraints can be expressed via a cost function over the output or response trajectories.\n\nFor instance, our method can extend to: \n- Harmfulness constraints in LLMs, where a harmfulness or toxicity score can represent the cost function. \n- Programming tasks, where generated programs must satisfy certain test-cases or meet resource/memory constraints — both of which can be captured via cost functions over the generated output.\n\nIn general, any constraint on response trajectories that can be formalized as a cost function is compatible with our framework. While it’s not practical to include all possible scenarios in the paper, we aimed to showcase a representative set of impactful applications. \n\n-----\n\n**5. How would you choose for a new task what the best maximal/relaxed cost budget to start off with is? Is it always 1/(1-gamma)?**\n\nWhile setting the maximum cost budget to $1/(1-\\gamma)$ follows from the theoretical analysis, in practice, there are more intuitive and task-specific ways to define it. One simple option is to choose a sufficiently large value when no prior knowledge is available, ensuring that early learning is unconstrained. Alternatively, the budget can be set based on the maximum expected cost observed in task trajectories. For example, in LLM settings with length constraints, if generation is limited to $N$ tokens with a per-token cost of 1, a natural choice for the maximum budget is $N$. Similarly, in RL domains, the maximum budget can correspond to the episode length or the maximum number of environment steps. \n\n-----\n\n(Minor suggestions)\n**6. It would be nice to have a table of contents of all the variables defined (perhaps in appendix) for improved readability … In the figures, you should indicate which algorithm is the papers with something like (ours) to distinguish from baselines.**\n\nWe thank the reviewer for the suggestions. We will incorporate them in the revised version.\n\n-----\n\nWe hope that our responses can address your concerns and are helpful in improving your rating. If you have any other comments or feedback, please let us know! We are looking forward to hearing back from you! Thank you again for the review."}, {"review_id": "6jlMewZhrC", "reviewer": "Reviewer_UKTS", "summary": "The paper suggests a curriculum learning strategy to learn the textual reasoning chain-of-thoughts limited to a certain target length (in tokens). The proposed CURL-TRAJC strategy is based on the properties of a binary tree and is given theoretical justification. The supporting experiments are performed on 3 synthetic/toy benchmarks and 2 math benchmarks. The paper aims to improve LLM’s end-user experience with LLM inference in exchange for extra complexity in the training stage.", "questions": "[1] What is “deployment”? This term from the industry/business is not used in academia often.\n\n[2] Is there any way to preserve the reward even with squeezing the size of reasoning into the constraint?\n\n[3] How could tool invocations be incorporated into reasoning?", "limitations": "The method is shown to work only for math problems. The method is limited to text-only reasoning, without support for within-reasoning tool invocation.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n[1] The study is well-rounded, with a theoretically clear problem statement, rigorous theoretical analysis of the solution and the support by experiments.\n\nWeaknesses:\n\n[1] The background for the problem is too brief. While the example on Figure 1 is very insightful, it is not clear, what could other practical uses be apart from solving math puzzles.\n\n[2] The experiments are performed on 3 synthetic/toy benchmarks and the only two practically significant benchmarks (SVAMP and GSM8K) are both math, which is not diverse enough to prove the generalization of the method. A non-math benchmark should be considered (as the authors admit in the discussions), for example HumanEval or even MLEBench.\n\n[3] Phrasing “Compressing LLM Output Tokens” is highly misleading. The individual tokens are not compressed, but rather the reasoning as a sequence of tokens is learned to be shorter.\n\n[4] “Response after 400K Episodes” suggests that training is very slow. 400K episodes looks like a lot to teach the model to reason briefly. Curriculum learning makes a promise to make training fast, which does not seem to be the case here.\n\n[5] Figure 4, CuRL-TrajC clearly is able to get to the target cost the fastest, however its final rewardlags behind the Unconstrained by a large margin, and is not better than other baselines. It is expected for the tradeoff to be like that, but I do not see much of the advantage of CuRL-TrajC compared to ExpSchedule. Yes, it arrives to the same brief reasoning and poor reward, but faster.", "was_revised": true, "final_justification": "The authors have addressed my concerns.", "rebuttal": "Thank you for carefully reviewing our paper! We greatly appreciate your feedback. Please see below our responses to your comments.\n\n-----\n\n**1. The background for the problem is too brief. While the example on Figure 1 is very insightful, it is not clear, what could other practical uses be apart from solving math puzzles.**\n\nWe would like to note that our problem setup — and the proposed curriculum strategy — applies broadly to scenarios where trajectory-level constraints can be expressed via a cost function over the output or response trajectories. More concretely:\n- Reaching a goal under navigation cost constraints, as demonstrated in the paper through the agent's path cost in MiniGrid. \n- LLM output generation with reduced reasoning tokens, also covered in the paper as trajectory length constraints. \n- In the rebuttal, we present additional LLM experiments involving variable token length constraints based on the original model response length.\n\nBeyond these, our method naturally extends to: \n- Safety constraints in RL domains, modeled via safety cost functions over the agent’s trajectory. \n- Harmfulness constraints in LLMs, where a harmfulness or toxicity score can serve as the cost function. \n- Code generation tasks, where generated programs must satisfy test cases or meet resource/memory constraints — both of which can be captured via cost functions over the generated output.\n\nIn general, any constraint on response trajectories that can be formalized as a cost function is compatible with our framework. While it’s not practical to include all possible scenarios in the paper, we aimed to showcase a representative set of impactful applications. \n\n-----\n\n**2. The experiments are performed on 3 synthetic/toy benchmarks and the only two practically significant benchmarks (SVAMP and GSM8K) are both math … A non-math benchmark should be considered (as the authors admit in the discussions), for example HumanEval or even MLEBench.**\n\nAs noted above, we conducted experiments with different types of trajectory-level constraints. We focused on mathematical tasks because they are widely regarded as standard benchmarks for evaluating the reasoning capabilities of LLMs. To ensure diversity within this domain, we included two distinct math datasets: SVAMP and GSM8K.\n\nFurthermore, we have conducted additional LLM-based experiments, which will be included in the revised version of the paper.\n\nThe new experiments include:\n- A model of different family and size — Qwen2.5-Math-1.5B — evaluated on both datasets.\n- A variable target setting, where each task $t$ has its own target budget $\\alpha^*$, determined based on the original model response length. This setting is applied across both models and datasets, resulting in four additional experiments. \n\nWe present the results in tabular form below.\n\n**Experiments with Qwen2.5-Math-1.5B: SVAMP**\n\n| Method | 50K | 100K | 150K | 200K | 250K | \n| ----- | --- | --- | --- | --- | --- | \n| CuRL-TrajC (ours) | $0.59$ | $0.78$ | $0.81$ | $0.80$ | $0.81$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.00$ |  $0.00$ | $0.64$ | \n| IID | $0.00$  | $0.00$ | $0.02$ | $0.20$ | $0.29$ | \n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.57$ | $0.61$ | $0.60$ |\n| \n\n**Experiments with Qwen2.5-Math-1.5B: GSM8K**\n\n| Method | 200K | 300K | 400K | 500K | \n| ----- | --- | --- | --- | --- |\n| CuRL-TrajC (ours) | $0.37$ | $0.56$ | $0.58$ | $0.62$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.04$ |  $0.50$ | \n| IID | $0.02$  | $0.03$ | $0.13$ | $0.17$ |\n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.23$ | $0.25$ | $0.25$ | $0.25$ |\n|\n\n**Experiments with variable targets Qwen2.5-Math-1.5B: SVAMP**\n\n| Method | 50K | 100K | 150K | 200K | 250K | \n| ----- | --- | --- | --- | --- | --- | \n| CuRL-TrajC (ours) | $0.27$ | $0.76$ | $0.77$ | $0.77$ | $0.77$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.00$ |  $0.00$ | $0.60$ | \n| IID | $0.00$  | $0.00$ | $0.01$ | $0.02$ | $0.07$ | \n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n|\n\n**Experiments with variable targets Qwen2.5-Math-1.5B: GSM8K**\n\n| Method | 200K | 300K | 400K | 500K | \n| ----- | --- | --- | --- | --- |\n| CuRL-TrajC (ours) | $0.26$ | $0.49$ | $0.56$ | $0.61$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.01$ |  $0.23$ | \n| IID | $0.01$  | $0.02$ | $0.08$ | $0.05$ |\n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n|\n\n**Experiments with variable targets MetaMath: SVAMP**\n\n| Method | 50K | 100K | 150K | 200K | 250K | \n| ----- | --- | --- | --- | --- | --- | \n| CuRL-TrajC (ours) | $0.06$ | $0.46$ | $0.61$ | $0.63$ | $0.63$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.00$ |  $0.00$ | $0.58$ | \n| IID | $0.00$  | $0.00$ | $0.00$ | $0.01$ | $0.00$ | \n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n|\n\n**Experiments with variable targets MetaMath: GSM8K**\n\n| Method | 200K | 300K | 400K | 500K | \n| ----- | --- | --- | --- | --- |\n| CuRL-TrajC (ours) | $0.18$ | $0.38$ | $0.41$ | $0.42$ | \n| ExpSchedule | $0.00$  | $0.00$ | $0.00$ |  $0.27$ | \n| IID | $0.00$  | $0.00$ | $0.00$ | $0.00$ |\n| Unconstrained | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n| Target | $0.00$ | $0.00$ | $0.00$ | $0.00$ |\n|\n\n-----\n\n**3. Phrasing “Compressing LLM Output Tokens” is highly misleading … the reasoning as a sequence of tokens is learned to be shorter.**\n\nIn the revised version, we plan to rephrase the title to “Curriculum Design for Trajectory-Constrained Agents with Applications to Efficient Reasoning Compression in LLMs” to make it more explicit that we refer to the reasoning trajectory of the model and not to the individual tokens. We thank the reviewer for the suggestion.\n\n-----\n\n**4. “Response after 400K Episodes” suggests that training is very slow … Curriculum learning makes a promise to make training fast, which does not seem to be the case here.**\n\nIn general, curriculum learning aims to improve convergence and enable learning of complex tasks that might otherwise be unlearnable. In our case, the final constrained task is highly challenging, and baseline curriculum strategies fail to learn it successfully. Notably, compared to other methods that do converge — such as ExpSchedule — our approach, CuRL-TrajC, converges significantly faster, demonstrating clear advantages in training efficiency.\n\n-----\n\n**5. Figure 4, CuRL-TrajC clearly is able to get to the target cost the fastest … Yes, it arrives to the same brief reasoning and poor reward, but faster.**\n\nThe horizontal line represents an upper bound — showing the model’s performance when trained under an unconstrained objective purely to maximize reward. As such, it is not directly comparable to the constrained setting, where the objective includes both performance and cost.\n\nImportantly, compared to ExpSchedule, CuRL-TrajC converges significantly faster. For context, the performance gap corresponds to approximately 250K episodes — or about 43 hours of training using 4 GPUs. Furthermore, as shown in our additional results presented during rebuttal, CuRL-TrajC consistently outperforms ExpSchedule across all benchmarks.\n\n-----\n\n**6. What is “deployment”? This term from the industry/business is not used in academia often.**\n\nWe use test-time and deployment interchangeably throughout the paper.\n\n-----\n\n**7. Is there any way to preserve the reward even with squeezing the size of reasoning into the constraint?**\n\nIt is expected that overall accuracy may drop when the response length is heavily constrained. However, our results show that it's possible to achieve substantial output compression — leading to faster inference — while still maintaining competitive performance relative to baselines. \n\nSeveral strategies can help improve the trade-off: \n- The compression level can be adapted per task, based on task difficulty and the model’s initial performance. \n- Since the fine-tuned model generates shorter responses, techniques like Best-of-N (BoN) sampling can be used at inference time to boost performance without increasing overall cost. For example, if the original model outputs 120 tokens on average and the compressed model outputs 20, using best-of-5 sampling remains more efficient. \n- Further improvements could come from tuning training hyperparameters, such as the KL coefficient or LoRA configuration.\n\n-----\n\n**8. The method is limited to text-only reasoning, without support for within-reasoning tool invocation. How could tool invocations be incorporated into reasoning?**\n\nWe would like to clarify that our method is not limited to text-only reasoning — see, for example, the safe navigation experiments in RL. The framework is generally applicable to scenarios where trajectory-level constraints can be expressed as cost functions over output trajectories.\nTool invocations can be incorporated similarly. If invoking a tool (e.g., a calculator) incurs an additional cost, this can be captured in the total trajectory cost. For simpler tasks, the model may choose to reason without invoking the tool to minimize cost, while for harder tasks, it may opt to bear the additional cost for better performance. This fits naturally within our trajectory-level cost formulation.\n\n-----\n\nWe hope that our responses can address your concerns and are helpful in improving your rating. If you have any other comments or feedback, please let us know! We are looking forward to hearing back from you! Thank you again for the review."}]

Author rebuttal:

Meta-review: The authors present a framework for introducing a curriculum to gradually incorporate constraints into constrained reinforcement learning settings with demonstrations of its use in a variety of settings including binary-tree MDPs and math reasoning tasks using LLMs. Additionally, they provide some theoretical analysis to motivate why this curriculum learning approach can accelerate training.

Strengths: The work is theoretically grounded and the demonstrations of the method in both very simple and very complex settings is impressive.  Using curriculum learning with RL exploration for LLMs is a novel and promising approach with practical potential. Reviewers also found the paper easy to follow.

Weaknesses: There are similarities to prior work ProCurl-Target. The theoretical analysis is only on the binary-tree MDP case. While there are case studies on toy MDPs and math reasoning tasks, there is nothing inbetween on more standard RL benchmarks. Evaluation was only performed on a few types of constraints and with only very basic methods as baselines.

Reasons for decision: Overall the contribution of this work is impressive both empirically and theoretically. There are some weaknesses, i.e. the theory is only relevant for the binary-tree MDP case and the work would benefit from filling in the gap of having experiments on other RL domains with more varied forms of constraints.

Rebuttal summary: The reviewers had questions about the sensitivity of this method to hyperparameters, as well as questions about other types of constraints and use cases and methods that were compared against. The authors provided additional results with hyperparameter sweeps, more baseline comparisons, and demonstrations of more LLM use cases.
Decision: Accept (poster)