acceptodds
Under review as a conference paper at ICLR 2027

SCALABLE: Scaling CApabilities Beyond the Best-of- Limit with Adaptive Boundary LEarning

Abstract

Reinforcement learning with verifiable rewards (RLVR) often improves the single-sample reasoning performance of large language models (LLMs), yet whether the long-run capability growth can surpass the frontier reachable by the initial policy through best-of- sampling remains debated. In this paper, we investigate the conditions under which RLVR can sustain capability growth beyond this apparent ceiling. We study problems with a controllable difficulty scale and fine-grained, verifiable solution-quality evaluation, with a focus on combinatorial optimization (CO). We observe a sharp performance decline as task difficulty increases, which we characterize as an empirical capability boundary. Under RL with uniform sampling, this boundary shifts toward harder instances, and its movement can be tracked using intrinsic or extrinsic signals. Based on these observations, we propose Adaptive Boundary Reinforcement Learning (ABRL), a novel learning strategy that dynamically concentrates training near the model's moving capability boundary. Across three CO tasks, ABRL sustains capability improvement, while experiments in other reasoning domains provide supporting evidence of its effectiveness beyond CO. At the largest problem sizes in our best-of- evaluation across the CO tasks, ABRL achieves average normalized best-of-1 performance of 0.5548, approximately the initial policy's best-of-4096 performance. In addition, we find that the number of training steps required to reach target performance exhibits an empirical power-law relationship with problem size across a broad range of problem settings.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning with Verifiable Rewards, Large Language Model Reasoning, Capability Boundaries, Combinatorial Optimization, Curriculum Learning, Test-Time Scaling, Power-Law Scaling

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_kCHCOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper investigates the conditions under which Reinforcement Learning with Verifiable Rewards (RLVR) can sustain capability growth beyond the initial policy. The authors hypothesize that sustained improvement requires training instances that remain informative as the policy evolves. Using combinatorial optimization (CO) tasks with controllable difficulty, they observe that RL progressively shifts toward harder instances and identify mean thinking length as an intrinsic indicator of the model’s capability boundary. Based on these findings, they propose Adaptive Boundary RL (ABRL), which dynamically concentrates training near this boundary. Empirical results show that ABRL substantially outperforms uniform RL in average normalized performance.

Critical strengths
  • Empirical results show that ABRL provides strong performance gains over best-of-kk initial policy.
Critical weaknesses
  • The paper's observation that the capability boundary shifts toward harder instances is somewhat similar to Boundary-aware Curriculum Learning [1] and the edge-of-competence phenomenon [2]. While the authors claim that ABRL differs by tracking the boundary using intrinsic response lengths, this metric requires further justification beyond combinatorial optimization (CO) tasks.
  • Although the paper aims to understand the conditions under which RL can sustain capability growth beyond the initial policy, I find it difficult to connect its insights to previous observations. For example, ProRL expands the reasoning boundary without dynamically allocating training data across difficulty levels. Furthermore, the proposed approach relies on a known problem difficulty axis, limiting its applicability to domains where estimating problem difficulty is challenging.
  • The controlled tasks with varying difficulty levels demonstrate cross-difficulty transfer. However, the underlying assumption of gradient alignment may not hold in practice, where gradient interference can be more severe and has been identified as a potential explanation for capability boundary shrinkage [3,4,5].
Questions for authors
  • How can the paper's insights help explain the conditions under which ProRL achieves capability boundary expansion?
  • Does the observed pattern, where thinking length initially increases with problem size and then decreases, also hold for mathematical reasoning or general tasks? Prior work suggests that harder problems generally actually exhibit longer reasoning chains [6]
  • Could the authors further clarify the key differences between ABRL, Boundary-aware Curriculum Learning, and the edge-of-competence phenomenon?
  • Could the authors clarify the meaning of reward shaping in Lines 882–888? The current manuscript provides little explanation of this term.

[1] Curriculum Reinforcement Learning Can Incentivize Reasoning Capacity in LLMs Beyond the Base Model. arxiv 2606.22317.
[2] On the Interplay of Pre-Training, Mid-Training, and RL on Reasoning Language Models. ICML 2026 Spotlight.
[3] POPE: Learning to Reason on Hard Problems via Privileged On-Policy Exploration. arxiv 2601.18779.
[4] Prompt Interference in LLM Post-Training: Why Pass@k Optimization Can Degrade Pass@1. arxiv 2602.21189v3.
[5] The Reasoning Boundary Paradox: How Reinforcement Learning Constrains Language Models. arxiv 2510.02230.
[6] Wait, Wait, Wait... Why Do Reasoning Models Loop? ICML 2026 Spotlight.
1 comment

Thank you for your response. The rebuttal has partially addressed my concerns. However, Fig. 16 does not clearly establish how thinking length can serve as a reliable metric for identifying the capability boundary, especially on OpenMath dataset. Furthermore, the connection between the conditions under which ProRL is effective and its ability to expand model capabilities remains unclear.

Overall, I find the contribution somewhat incremental and conceptually similar to [1]. In contrast, [1] provides strong empirical evidence on standard benchmarks, whereas the current work is evaluated only in controlled settings, raising concerns about the generalizability of its findings. Therefore, I will maintain my original score.

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

The question is whether RLVR can push a policy past what its starting point already reaches by best-of-k sampling. The authors move that question into combinatorial optimization, where difficulty is a single number and solution quality is graded instead of pass/fail: TSP scored by gap to an LKH-3 reference, sorting by inversions, stable matching by blocking pairs. Performance collapses over a narrow band of problem sizes, and the paper defines that band through the local rate of decline, then asks which training-time signals can find it without scoring the task at all. Mean thinking length turns out to locate it about as well as reward variance does. ABRL tracks the band with a running average of the thinking-length profile and samples difficulties from an exponential kernel centred there, wider on the easier side, with ten percent uniform exploration. The headline number is an average normalized score of 0.5548 at the largest sizes against 0.0621 for the initial policy at best-of-4096, reported as 8.93x, and Sec. 4.4 adds a power-law fit of steps-to-threshold against problem size.

Critical strengths
  1. Turning difficulty into a scalar with graded verifiers lets the paper measure a capability boundary instead of arguing about one, and the finding that mean thinking length locates it as well as reward variance does is the most useful thing I took away.

  2. The curriculum choice is isolated at matched steps, including a three-way branch from a single shared checkpoint that comes close to a causal test.

Critical weaknesses
  1. The comparison that gives the paper its title does not test the title: Fig. 4 puts the trained policy at k = 1 against the untrained one at k = 4096, a mean against a maximum. No best-of-k curve is reported for any trained policy at any k, so I cannot tell whether RL moved the frontier or concentrated mass inside it - the question Sec. 1 positions the paper against. The ratio is fragile too: Sort's initial best-of-4096 is 0 at the two largest sizes, so 8.93x has a zero in the denominator and dropping Sort leaves 4.22x. ABRL clearly trains much better policies than uniform sampling; it is the framing the evidence does not reach.

  2. The method is underspecified where a reimplementation would need it - delta, tau_t and the rule for choosing the sampling centre are all missing - while Table 10 hand-sets six quantities per task, including a slope ratio that changes sign between tasks with no sweep. There is also no oracle-boundary control, which would be the direct test of whether the length-based estimate is good enough to matter.

Questions for authors
  1. Can you report the trained policy's own best-of-k up to k = 4096 on the Fig. 4 instances, with decoding settings? Does ABRL best-of-4096 beat the initial policy's best-of-4096?
  2. Please define best-of-k performance formally, and put the initial policy's mean at k = 1 next to 0.5548.
  3. What are delta and tau_t, and what exactly maps Eq. 18 candidates to the sampling centre?
  4. How was the slope ratio chosen per task, and what happens on TSP with Sort's value?
  5. For Fig. 5, how many points enter each fit, over what size ranges, and what are the exponents with intervals? Table 12 reports R^2 only, and the K = 1 TSP fits fall to 0.85-0.90 at the higher thresholds.
Reviewer_P9KuOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates whether reinforcement learning can improve LLM reasoning capabilities beyond the performance achievable through extensive sampling from the initial policy. The authors identify a moving capability boundary characterized by a sharp performance decline as task difficulty increases and observe that mean thinking length can serve as an intrinsic signal for tracking this boundary. Based on this observation, they propose Adaptive Boundary Reinforcement Learning (ABRL), which dynamically adjusts the training difficulty distribution to concentrate learning near the model's current capability boundary.

Critical strengths
  1. Interesting and Well-Motivated Research Question. The paper investigates an important question in LLM reinforcement learning: whether RL can improve reasoning performance beyond what is achievable through extensive inference-time sampling from the initial model.

  2. Insightful Empirical Observations. The authors identify a moving capability boundary and demonstrate that mean thinking length can effectively track its evolution. This provides an interesting perspective on the relationship between reasoning behavior, task difficulty, and model capability.

Critical weaknesses
  1. Limited Novelty and Insufficient Justification of the Thinking-Length-Based Capability Boundary. Adaptive curriculum learning based on task difficulty has been extensively studied in reinforcement learning, such as [1], including methods that prioritize samples near the model's current learning frontier. Therefore, the main novelty of this work largely relies on using the turning point of mean thinking length as an indicator of the model's capability boundary. However, the relationship between thinking length and capability remains insufficiently explained. Although the authors provide empirical evidence that thinking-length turning points correlate with performance declines in TSP, this observation does not establish a general or causal relationship.

  2. Insufficient Justification for Thinking Length as a Capability Boundary Indicator. The paper lacks a convincing explanation for why thinking length should decrease when task difficulty exceeds the model's capabilities. Intuitively, models may instead engage in prolonged reasoning or overthinking on difficult problems. Although the authors observe this pattern empirically on TSP, its underlying mechanism and generalizability remain unclear, raising concerns about the reliability of the proposed boundary estimation.

[1] Depth-Breadth Synergy in RLVR: Unlocking LLM Reasoning Gains with Adaptive Exploration

Questions for authors

See weakness

1 comment

I sincerely appreciate the authors' response.

However, the methodology presented in this paper is primarily based on the Traveling Salesperson Problem (TSP), and the proofs and supplementary explanations provided by the authors are also rooted in the TSP. There is no evidence to suggest that this approach can be extended to other problems; therefore, I remain skeptical regarding its generalizability.

Consequently, I have decided to maintain my current score.

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

The paper studies adaptive difficulty allocation in reinforcement learning with verifiable rewards. On TSP, it finds that the turning point of mean reasoning length tracks the transition from strong to weak performance across problem sizes, and uses this statistic to center an asymmetric sampling distribution in Adaptive Boundary Reinforcement Learning (ABRL). Experiments on three combinatorial tasks compare ABRL with uniform and curriculum-based RL, report performance beyond the initial policy's finite-budget best-of-4096 reference, and fit empirical relationships between problem size and training steps to performance thresholds. Three adapted non-combinatorial tasks and several TSP mechanism studies provide additional validation.

Critical strengths
  1. ABRL produces a substantial empirical improvement over straightforward allocation strategies. The paper also reports the case where ADR initially wins on Sort, followed by ABRL's later improvement, and includes a rollout-compute comparison for TSP.

  2. The mechanism studies separate several plausible explanations for the gains. More directly, the shared-checkpoint experiment in Tables 21 and 22 holds the starting model fixed: training at the estimated boundary improves performance on the other 88 sizes from 0.3178 to 0.4870, compared with 0.3310 after easy-size training and 0.2613 after hard-size training. This is consequential evidence for where training is allocated, rather than merely showing that additional training helps.

Critical weaknesses
  1. ABRL's length-profile turning point over an external difficulty axis is a concrete distinction from Cai et al., SEC, CDAS, and FG-ExPO, but its added value needs clearer characterization. Table 1 supports comparable localization to reward variance, and Table 5 reports a positive gain (0.5560 versus 0.5307). This comparison covers TSP at step 200, without uncertainty estimates or cross-task isolation of the length signal. Independence from task scores does not imply lower cost when RL already computes rewards. Evidence on robustness, applicability, or probing requirements would clarify the contribution's significance.

  2. The empirical evidence does not sufficiently strengthen that residual contribution. Tables 10 and 11 provide curriculum settings and token limits, but the manuscript omits the main CO generation distributions, per-size evaluation counts, full RL/sampling settings, and precise best-of-k pool construction.

Questions for authors
  1. How variable is the 0.0253 difference between the two boundary-based signals in Table 5 across independent runs? Do existing analyses clarify when length-based localization is preferable or complementary to reward-based localization, for example in estimation stability, probing requirements, or applicability? This would help establish the scope of the contribution even where final task performance is similar.

  2. Could you clarify the CO train/evaluation separation and per-size counts, optimization/sampling settings, and best-of-k construction? Are the ABRL scores and per-instance maxima evaluated on the same independent instances, and are there long-run seed repeats beyond Table 16's early window?

  3. What points are removed by the scaling window and trimming rule, and what happens to exponents and fit quality without trimming? Are independent validation measurements available for Stable Matching? These questions concern the strength of the reported evidence, rather than unrelated future directions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.