acceptodds
Under review as a conference paper at ICLR 2027

Exactly Verifiable Reinforcement Learning for LLM-Written Rules

Abstract

An NP-hard problem is intrinsically difficult to solve optimally. In practice, one has to resort to heuristic algorithms, that is, hand-coded rules that provide quick decision-making and solutions of adequate quality. Workload scheduling is an example. In a large computing system, more jobs arrive than can be served. Thus, there is a need to create rules for selecting the next job to serve and to modify them as necessary due to changes in workload and/or goals. A rule can be expressed as a short program, hence a language model can write one, and an exact simulator can judge it by re-running a recorded log of real requests under that rule. The latter creates a verifiable reward. We present , a framework which approaches NP-hard problems by learning their heuristics. It trains a language model that writes rules and a selector that chooses among them. The rule writer proposes new rules to deal with shortcomings of the current set, the simulator verifies the candidates, and only valuable rules are selected. At runtime, the selector picks new rules to test and makes the scheduling decision. Using the BurstGPT public trace of inference requests, with the Qwen3.5/3.6, Nemotron 3 Nano, and Nemotron 3.5 Lightning model family, RuleForge manages to match the accuracy of a similarly sized search on the same set of rules with one-sixth the number of replays, meet goals not met by the search, and get within 3.3 points of the optimum of the complete trace in under one-twentieth of the number of replays. On the benchmark job-shop problems, the learned selector performs much better in meeting scheduling goals, by 7.2 to 10.0 points, and matches the schedule quality of an exact solver with one-third the computation time.

Primary area:
foundation or frontier models, including LLMs
Keywords:
reinforcement learning with verifiable rewards, large language models, automated heuristic design, scheduling, NP-hard, program synthesis

Reviews

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

The paper proposes a system called RuleForge to learn a rule library to solve a set of problems/goals. It designs the reward function during the training so that the the newly written rules that maximises the gain of the missing goals of the current library are added into the library, and the rules sharing the same goals also share the credits. Experiments on different learning to optimise problems show that the proposed system is better than the compared rule learning approaches.

Critical strengths

The problem of learning to solve difficult optimisation problems is important, especially for unseen problems with different characteristics.

The experimental results look promising when comparing with other approaches.

Critical weaknesses

The problem is unclearly described/defined. The goals/tasks seem to be pre-defined before training. In this case, there are many multi-task learning approaches, including multi-task GPHH for rule learning approaches. However, such line of research is never mentioned nor compared.

It is unclear whether the learned library of rules can be generalised to unseen different problems during the training. If it only works for the problems seen in the training, the impact is limited.

The algorithm design is rather ad hoc than systematic. For example, why are there only 3 generations? Why to select six rules from W? Why train on groups of 8 rules? Why "one to three metrics" in the goal definition?

It is not clear how the rules look like and how the simulation looks like to evaluate the rules. Table 2 is hard to understand, as the rules look generic and not specific to the scheduling, packing, or routing problems.

The sentence "If that value is a tenant-share error of 0.20 and the goal asks for 0.10, a rule that reaches 0.15 scores 0.25 (Appendix C). In every other case g). s(r, g) = v(r, g)" is hard to understand.

There is no reference for the methods compared in Table 1. It is not clear which exact publication was used (e.g., there are many genetic programming approaches for scheduling).

As optimisation problems, it is more common to check the gap in objective values rather than goals met. The performance metrics should be set consistently with the problem itself.

The motivation of using rules to solve static optimisation problems is not justified. For static problems, usually meta-heuristics are better than constructive heuristics or rules.

Questions for authors

See my comments in weaknesses.

7 comments
AuthorsOpenReview ↗

Response to Reviewer JXpH (1/3)

We thank the reviewer for the detailed and constructive feedback. We address your points below, including additional experiments and paper edits found in our revised draft. Figure, table, and appendix numbers below refer to the revised PDF.

W1a. The problem is unclearly described or defined.

Thanks for pointing out that the problem definition was confusing in the submitted draft. We want to clarify the problem with one example. On inference scheduling, an instance is a window of LLM requests from several tenants. A goal sets thresholds on one to three metrics of that window, for example a bound on how far the tenants' shares of served work stray from equal. A rule is a short expression that scores the waiting requests, and the simulator runs the highest-scoring request next. For instance, 0 - tokens runs the shortest request first.

Goals are fixed before a run, as an operator states service objectives. We draw each held-out threshold uniformly from the range the hand-written rules reach on its window, widened by a tenth on each side, and we pick half the held-out goals so that no hand-written rule meets them (Appendix C). A run is given the ten hand-written rules, 720 training goals on 15 trace windows and a budget of 30,833 simulator runs. It returns a library of rules and a selector that picks one library rule per goal. We report the share of 2,816 held-out goals that the chosen rule meets. These goals lie on 176 trace windows that no run trains on. On the four other problems, a goal bounds the mean gap or tardiness on a class of instances, and Table 1 reports that mean for the rule the selector picks on each test set, so the metric there is the objective gap you ask about in W7. Section 2 now states the task in this form and gives the example rule.

W1b. The goals are defined before training, so multitask learning approaches, including multitask GPHH, should be discussed and compared.

Our submission cited multitask GPHH and multi-task MAP-Elites in Appendix A but did not compare with them. Motivated by your feedback, Table 1 now includes two multitask baselines that share what they find across tasks and train no model. Multitask genetic programming (Zhang et al., 2021) treats each of the 15 training windows as a task, as Zhang et al. treat a few scheduling scenarios. It evolves one subpopulation of rules per task, with crossover between them. Multi-task MAP-Elites (Mouret and Maguire, 2020) keeps the best rule for each training goal as an elite. Both run under our budget, grammar, prescreen, admission and selector and are tuned like every baseline. Table 30 gives their settings, and Section 5 now discusses both. Results on the five problems (Table 1):

MethodInference, chosen rule ↑Inference, library oracle ↑Job shop ↓Flow shop ↓Bin packing ↓TSP ↓
Genetic programming63.167.81.003.051.0513.4
Multitask genetic programming64.969.60.952.980.9712.8
Multi-task MAP-Elites64.270.40.963.000.9412.6
CALM, best other LLM-driven65.070.10.962.930.6411.3
RuleForge71.075.40.892.560.389.9

Sharing across tasks lifts genetic programming by 1.8 [0.9, 2.7] points on inference. RuleForge leads multitask genetic programming by 6.1 [4.6, 7.6] points and multi-task MAP-Elites by 6.8 [5.3, 8.3]. With our Shapley credit as its selection score, multitask genetic programming rises to 66.3 percent, above CALM's 65.0, with no model trained (Table 30). In other words, the credit adds to what sharing across tasks gives, and training a writer on it gains the most.

W2. Can the learned library generalize to unseen problems with different characteristics?

A library holds rules for one problem, since a rule scores that problem's options, such as its requests, bins or cities. The method carries across problems. One recipe runs on all five problems and, on inference, with seven base models from 4.7 to 116.8 billion parameters. Only the writer's and the selector's learning rates are set per model. It leads the eleven LLM-driven baselines on all five problems, and on inference it leads the best other method by 4.7 to 6.7 points with each of the seven models.

Within a problem, the library and selector transfer to unseen workloads without retraining. Motivated by your feedback, we added held-out windows with more or fewer tenants than any training window (Table 31, Figure 36b and c):

Setting, no retrainingRuleForgeBest other LLM-driven
Inference, Azure 2024 trace, goals met (%) ↑67.361.2
Inference, Mooncake trace, goals met (%) ↑64.958.9
Inference, 2 or 24 tenants, goals met (%) ↑63.458.6
Job shop, due-date allowance three, tardiness ↓0.900.97
Job shop, due-date allowance six, tardiness ↓0.910.98
Flow shop, 240 large VRF instances, gap (%) ↓2.492.81
AuthorsOpenReview ↗

Response to Reviewer JXpH (2/3)

(W2, continued)

RuleForge leads the best other LLM-driven method in all six settings, by 4.8 to 6.1 points on the three inference shifts. Observation 7 in Section 4 now states this transfer result.

W3. The design looks ad hoc rather than systematic. Why three generations, six rules from the writer, groups of eight and one to three metrics per goal?

Thanks for the suggestion. Each choice now has a sensitivity test that varies it alone with the rest of the recipe fixed (Figure 5c in Section 4, and Tables 25 and 32 in Appendix N). Held-out inference goals met, means over five seeds:

ChoiceSettings, recipe in boldHeld-out goals met (%)
Generations, each at its own budget2, 3, 4, 568.8, 71.0, 72.1, 72.6
Rules per prompt3, 6, 12, 2469.3, 71.0, 71.4, 70.2
Group size4, 8, 16, 3270.3, 71.0, 70.9, 70.6
Admissions per generation4, 8, 1669.1, 71.0, 70.7
Prescreen margin (%)0, 2, 570.1, 71.0, 70.3
Metrics per goal, as lead over CALM (points)1, up to 2, up to 34.2, 5.4, 6.0

Three generations. Three generations fit the fixed budget. Five held to it reach 70.4 percent, within noise of three. With their own larger budgets, four and five reach 72.1 and 72.6, so more generations help only with more evaluations.

Six rules from the writer. Goals met rise from three rules per prompt to six and stay flat to twelve. Each candidate is verified from the budget, so twenty-four rules per prompt leave too few survivors and fall back.

Groups of eight. Groups of eight lie in CALM's tuning grid, so the comparison of the two rewards holds group size fixed. Groups of 16 and 32 stay within 0.4 points.

One to three metrics. An operator states a few service objectives at once, such as tenant shares, wait and requests served. RuleForge's lead over CALM grows with the metrics per goal, from 4.2 to 6.0 points.

Every setting stays within 2.2 points of the recipe and above CALM's 65.0.

W4. It is unclear what the rules look like and how the simulation evaluates them. Table 2's rules look generic rather than specific to scheduling, packing or routing.

Thanks for pointing out that Table 2 was confusing in the submitted draft. Its rules came from the earlier version of RuleForge. Table 2 now shows three admitted inference rules of the final recipe, all proposed by the writer, with the held-out goals each meets alone, and its caption defines every feature they read. Motivated by your feedback, we also added Table 34, which gives one admitted rule of the final recipe per problem, the one of largest admission gain in the run of seed 0. The writer proposed all five, and each reads only its own problem's features:

ProblemRuleWhat it does
Inference schedulingwhere(deficit > 0, 2*deficit - 0.8*tokens - 0.05*wait, -1.5*tokens - 0.1*agemax)below-share tenants first by how far below, then shortest first, newer requests first
Dynamic job shop0 - p * (1 + max(0, 0 - slack) / (wr + 1)) - 0.2*nrshortest operation first, a late job's time scaled by its lateness over its remaining work, fewer remaining operations first
Online bin packingwhere(rem - item < 0.1*cap, 3 - (rem - item)/cap, 0 - rem/cap)fills a bin the item nearly completes, otherwise best fit
Traveling salesman0 - d_cur - 0.6*left*d_mean - 0.3*d_start*(1 - left)nearest city, early toward cities near the other unvisited ones, late toward the start
Flow shopsum_p + 0.4*max_p to order, 0 - idle - 0.2*pos to break tieslargest total work first, ties to the position with least idle time, then the earliest

One evaluation is one simulator run of one rule on one instance. On inference, the simulator replays a trace window's requests from several tenants on four to eight slots without preemption. At each decision the rule scores every waiting request and the highest score runs next, in a median of 40 microseconds. At the window's end, the simulator computes four metrics and checks each goal's thresholds. On the other problems, the rule orders a machine's queue, sets NEH's job order and tie-break, scores the open bins for an arriving item or scores the next city (Appendix H).

W5. The graded-score sentence is hard to understand.

Thanks for catching this. The sentence did not say what the score is for, and its example pointed back to an ambiguous "that value". The graded score gives partial credit on a goal no hand-written rule meets, so a rule that closes part of the gap is rewarded. Section 2 now reads as follows.

AuthorsOpenReview ↗

Response to Reviewer JXpH (3/3)

(W5, continued)

Half the held-out inference goals are picked so no hand-written rule meets them, and a binary verdict rewards no progress on these. A goal is graded if no hand-written rule meets it but some hand-written rule meets all its thresholds except one. On a graded goal we pick the threshold that hand-written rules miss by the least. A rule that misses only this threshold gets a graded score s(r,g)s(r,g), the fraction by which it improves on the best hand-written value there, capped below 1. Suppose the best hand-written tenant-share error is 0.20 and the goal asks for 0.10. A rule that reaches 0.15 improves on 0.20 by a quarter, so it scores 0.25 (Appendix C). Otherwise s(r,g)=v(r,g)s(r,g) = v(r,g), so a rule that meets the goal scores 1.

W6. Table 1 gives no references for the compared methods, and many genetic-programming approaches exist for scheduling.

Thanks for catching this. Appendix E now names the publication behind every LLM-driven and multitask baseline of Table 1, and the Baselines paragraph cites each method inline. Our genetic programming is the standard tree-based genetic-programming hyper-heuristic for dispatching rules (Branke et al., 2016; Nguyen et al., 2017), the single-population method that the multitask genetic programming of Zhang et al. (2021) extends to several tasks. It evolves rules in our grammar under the same budget, admission and selector, with its population and tournament size tuned like every baseline (Appendix E). RuleForge leads it by 7.9 [6.1, 9.7] points on inference.

W7. For optimization problems, the gap in objective value is more common than goals met.

We agree, and the four other problems already report it in Table 1, as relative tardiness on the job shop and the percent gap to the best-known makespan, the bin lower bound and the optimal tour. Inference scheduling has no single objective. An operator states service objectives as thresholds on several metrics at once, such as tenant shares, wait fairness and requests served, and a schedule meets them or misses them. Motivated by your feedback, we added the relative shortfall to the thresholds, which is zero on a met goal and otherwise the goal's largest relative miss, a metric's distance past its threshold over the threshold. Mean over the 2,816 held-out goals (Table 31, Figure 36a):

MethodGoals met (%) ↑Relative shortfall ↓
Hand-written rules45.20.148
Classical pool57.50.097
Genetic programming63.10.074
CALM65.00.061
RuleForge71.00.038

RuleForge's shortfall is 0.023 [0.016, 0.030] below CALM's, 38 percent less, and Observation 7 in Section 4 now states this result. Part of this order follows from goals met. On the goals both RuleForge and CALM miss, RuleForge's shortfall is still the smaller, 0.112 against 0.139, so RuleForge also comes closer on the goals it misses.

W8. Using rules for static problems is not motivated, since metaheuristics usually beat constructive heuristics there.

We agree, and Section 4 now says so. Our target is the online problem, where requests, jobs or items arrive over time and a rule decides each one as it comes. Three of the five problems are online. The static flow shop and TSP are standard benchmarks of automatic heuristic design, and there a metaheuristic given more time does better. A learned rule can still start a metaheuristic. Appendix H reported that a start from RuleForge's flow-shop rules improves the iterated greedy algorithm of Ruiz and Stützle (2007). Appendix N now gives the gaps at 30 seconds per instance on the 240 large VRF instances:

Start of iterated greedyGap (%) ↓
NEH0.61
Best published tie-breaking0.54
RuleForge's flow-shop rules0.52

The RuleForge start beats NEH by 0.09 [0.02, 0.16] points of gap and matches the best published start. The credit also helps when the program is a whole metaheuristic. Inside ShinkaEvolve, where a frozen model writes complete metaheuristics run for 10 seconds per instance, replacing its fitness with the Shapley credit lowers the gap from 0.94 to 0.81 percent on the flow shop and from 1.92 to 1.64 on the TSP, each paired interval above zero (Table 33).

The revision also runs the loop without seed rules, and from an empty library RuleForge's lead over CALM grows from 6.0 to 7.7 points (Table 27). Motivated by your comments on presentation, we also rewrote parts of Sections 2 to 4 for clarity.

Thanks again for your feedback. Motivated by your points, we have run additional experiments and made numerous paper edits, while making our wording about our method more clear which we feel has improved the quality of our draft. We would greatly appreciate it if you would consider raising your score accordingly. Do you have any other questions we can address?

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

This paper proposes RuleForge, a framework for discovering executable priority-rule heuristics using reinforcement learning. Its main contribution is a library-aware reward that uses Shapley credit to measure each generated rule's contribution to the existing rule library across multiple goals. A selector then chooses suitable rules for different goals. Experiments on five optimization problems demonstrate improvements over existing LLM-based approaches, supported by ablation studies and statistical tests.

Critical strengths

The paper presents a well-motivated library-aware credit assignment mechanism with strong empirical support. In particular, Shapley credit improves held-out goal satisfaction from 66.6% to 71.0% compared with simpler per-sample marginal-gain credit, with statistically significant improvements. The extensive ablations strengthen the evidence for the proposed reward design.

Critical weaknesses

The methodological novelty is somewhat limited, as the approach builds on established Shapley-based credit assignment and is tailored to a predefined priority-rule representation and a goal-conditioned library objective. Its broader applicability to general algorithm discovery remains unclear. Moreover, although the proposed reward clearly outperforms simple per-sample credit, the additional benefits of cross-goal credit are not consistently significant across all tasks. This raises questions about the conditions under which the proposed mechanism provides substantial advantages.

Questions for authors

What properties of the goal distribution make Shapley-based library credit particularly beneficial compared with simpler per-sample marginal-gain credit? In particular, how does the advantage depend on goal heterogeneity and cross-instance rule complementarity, especially in single-objective settings? A clearer characterization of these conditions would help establish the generality and significance of the proposed method.

4 comments
AuthorsOpenReview ↗

Response to Reviewer E1LZ (1/2)

We thank the reviewer for the detailed and constructive feedback. We address your points below, including additional experiments and paper edits found in our revised draft. Figure, table, and appendix numbers below refer to the revised PDF.

W1 and Q1. What properties of the goal distribution make Shapley library credit beat simpler per-sample marginal-gain credit? How do goal heterogeneity and cross-instance complementarity matter, especially under a single objective, and why is cross-goal credit not significant on every task?

Thanks for this question, which the revision now answers directly (Appendix N). Our credit has two parts. Each is measured against the closest prior credit, and each is tied to one property of the goals.

The split. Per-sample credit as in TestDecision also credits every goal, so it differs from ours only in the split. We call a group coupled when two or more of its rules add value on one goal. On a coupled group, per-sample credit gives each such rule the whole shared gain, so it rewards a rule that duplicates another. The Shapley credit shares that gain, while a rule that covers instances the others miss keeps its whole gain. This is how the split rewards cross-instance complementarity, and it can only matter on coupled groups.

The scope. TailRL's credit counts only the goal named in the prompt, so it differs from ours only in the scope. Our credit counts a rule's gain on every training goal. This matters in proportion to goal heterogeneity, which we measure as the share of a group's gain that lands off the prompting goal.

Measured conditions. Motivated by your question, we sorted the training goals into terciles by each property and trained on each tercile. Section 4 now reports this as Observation 7 with Figure 5, and Appendix N gives the details (Table 29). Paired gains in held-out inference goals met, with 95 percent intervals:

Training goalsCoupled groupsGain off the prompting goalSplit gainScope gain
Low coupling12%36%1.4 [0.5, 2.3]
Medium coupling24%38%3.6 [2.5, 4.7]
High coupling37%39%5.0 [3.7, 6.3]
Low heterogeneity23%14%0.5 [−0.3, 1.3]
Medium heterogeneity24%26%2.5 [1.5, 3.5]
High heterogeneity26%41%4.1 [2.9, 5.3]
The recipe's goals, one to three metrics24%38%4.4 [3.1, 5.7]3.2 [2.0, 4.4]
Goals on one metric each22%11%2.1 [1.2, 3.0]0.4 [−0.4, 1.2]

The split's gain rises from 1.4 to 5.0 points across the coupling terciles, and the scope's from within noise to 4.1 points across the heterogeneity terciles. Each sort leaves the other property nearly unchanged, so the two effects are not confounded. A tercile run trains on a third of the goals, so the terciles give each effect's direction and the full goal sets give its size.

Single objective. The split needs only that several sampled rules can fix one goal, which does not depend on how many metrics a goal constrains. On goals that each constrain one metric, the split still gains 2.1 [1.2, 3.0] points and RuleForge leads CALM by 4.2 [2.9, 5.5]. On single-metric inference goals only 11 percent of a group's gain lands off the prompting goal, so crediting every goal is within noise there. Heterogeneity under a single objective has to come from the instances. Bin packing and the traveling salesman problem each have one objective, yet their instances differ enough for crediting every goal to help on both (table below).

Other problems. We agree that cross-goal credit is not significant on every problem. It is significant on the three problems with the largest share of a group's gain off the prompting goal and within noise on the two shops, which have the smallest (Appendix H):

ProblemMetrics per goalGain off the prompting goalCrediting every goal
Inference schedulingone to three38%+3.2 [2.0, 4.4] points
Bin packingone33%gap 0.09 [0.05, 0.13] lower, p=0.001p = 0.001 after Holm
Traveling salesmanone27%gap 0.47 [0.24, 0.70] lower, p=0.001p = 0.001 after Holm
Dynamic job shopone24%within noise
Flow shopone18%within noise

The split helps on all five problems, as per-sample credit trails the Shapley credit with an interval that excludes zero. The limitations section now states when each part of the credit helps.

AuthorsOpenReview ↗

Response to Reviewer E1LZ (2/2)

W2. The method builds on established Shapley credit and is tailored to priority rules and a goal-conditioned library objective. How far does it reach toward general algorithm discovery?

What is new. We agree that the Shapley split is established. On one goal, TailRL already gives our credit and the objective it ascends. What is new is the game the credit splits, a library's gain summed over every training goal, and Proposition 1, which extends TailRL's result to every semivalue credit. Let JmJ_m be the expected gain in library value of mm rules the writer samples for one goal. For on-policy samples with credits centered on the group mean, per-sample credit ascends only J1J_1, leave-one-out credit only Jn−1J_{n-1} and the Shapley credit ∑m=1n−1Jm/m\sum_{m=1}^{n-1} J_m/m, while the best-of-kk credit of PKPO, with its own baseline, ascends only JkJ_k. As predicted, the Shapley credit's weight on rarely fixed goals rises with the group size, from 1.27 at groups of 4 to 3.21 at 64 (Table 26).

Portfolio Shapley values (Fréchette et al., 2016) score solvers already kept, while RuleForge uses the share as the advantage of fresh samples in training, so it shapes what the model writes next. Each prior credit, run in our loop with everything else fixed, trails RuleForge (Table 19):

Writer's creditAs inGoals met (%)Below RuleForge
Shapley share of the library's gain over every goalRuleForge71.0
Best-of-6 with a leave-two-out baseline, same gameMaxPO70.01.0 [0.6, 1.4] over 15 seeds
Best-of-6, same gamePKPO67.04.0 [2.7, 5.3]
Leave-one-out, same game66.44.6 [3.1, 6.1]
Shapley share on the prompting goal aloneTailRL67.83.2 [2.0, 4.4]
Shapley share of the group's own value, no libraryGCPO67.13.9 [2.6, 5.2]
Per-sample gain over the libraryTestDecision66.64.4 [3.1, 5.7]

Neither part suffices alone. On our game, per-sample, best-of-6 and leave-one-out credit trail by 4.0 to 4.6 points, about as much as splitting the group's own value without the library, as GCPO does. Only MaxPO's split on our game comes close, one point below. In other words, the lead needs both the library game and the Shapley split.

Reach. The credit is tied neither to our grammar nor to goals an operator states. Inside CALM, for example, its population is the library and each training instance is a goal whose target gap is zero. Motivated by your feedback, we also added EoH-S, where a frozen model uses the credit as its selection score. Percent gap with each pipeline's own score replaced by the Shapley credit, lower is better (Appendices G and N):

PipelineThe credit replacesBin packingTraveling salesman
CALMits training reward0.74 to 0.6211.8 to 11.1
EvoTuneeach program's own score in its DPO pairs0.82 to 0.7012.1 to 11.5
EoH-S with a frozen model, added in revisionits selection score0.79 to 0.6811.2 to 10.6

Inside EoH-S, over five seeds, the paired gains are 0.11 [0.05, 0.17] on bin packing and 0.6 [0.3, 0.9] on the TSP. On inference scheduling, RuleForge's loop over native Python priority functions meets 71.4 percent of held-out goals, against 65.8 for CALM in its native form (Appendix G). Motivated by your feedback, we also tested the credit on whole programs. Inside ShinkaEvolve, a frozen model writes complete schedulers for multi-tenant LLM serving, run in vLLM, or complete metaheuristics for the flow shop and the TSP, and the Shapley credit over its archive replaces its fitness in parent selection and admission. Means over five seeds of 2,000 programs (Table 33):

Whole programMetricShinkaEvolve's fitnessShapley creditPaired gain
Scheduler for LLM serving in vLLMgoals met (%) ↑55.859.94.1 [2.5, 5.7]
Flow-shop metaheuristic, 10 s per instancegap (%) ↓0.940.810.13 [0.06, 0.20]
Traveling-salesman metaheuristic, 10 s per instancegap (%) ↓1.921.640.28 [0.15, 0.41]

The credit helps whole programs as it helps rules, and the whole schedulers stay below RuleForge's trained rules, which meet 61.0 percent of the vLLM goals. The limitations now state that its reach beyond optimization is open.

The revision also adds multitask genetic programming and multi-task MAP-Elites to Table 1, and RuleForge leads both on all five problems. With the Shapley credit as its selection score, multitask genetic programming rises above CALM with no model trained (Table 30). We also rewrote parts of Sections 2 to 4 for clarity.

Thanks again for your feedback. Motivated by your points, we have run additional experiments and made numerous paper edits, while making our wording about our method more clear which we feel has improved the quality of our draft. We would greatly appreciate it if you would consider raising your score accordingly. Do you have any other questions we can address?

Thank you for the comprehensive rebuttal and additional experiments, which successfully clarified my questions regarding Shapley-based credit assignment, cross-goal credit, and whole-program search. Nevertheless, my core concern regarding methodological novelty persists. Although the library-level reward and theoretical analysis are useful, the underlying approach appears to be an incremental advancement over existing Shapley-based credit assignment and portfolio optimization methods. I am not fully convinced of the substantiality of the methodological contribution. Therefore, while I commend the authors' efforts and the strengthened empirical evidence, I will keep my current rating.

AuthorsOpenReview ↗

Response to Reviewer E1LZ (novelty)

Thank you for the follow-up, and we are glad the new experiments clarified your questions on Shapley credit, cross-goal credit and whole-program search. We agree that the Shapley value is established, and below we state what is new relative to the two lines of work you name.

Portfolio methods. Hydra searches a solver's configuration space for the configuration of largest marginal gain, and Fréchette et al. (2016) value existing solvers by their Shapley share. Used as those methods use it, to guide a search with no trained model, our credit lifts multitask genetic programming from 64.9 to 66.3 percent (Table 30). Used to train the writer, it carries 4.9 of RuleForge's 6.0-point lead over CALM, and 4.4 of a 5.6-point lead averaged over seven base models (Observation 4). The contribution is the use of the share as the training signal for the model that writes new members, and it accounts for most of the result.

Shapley credit in reinforcement learning. Prior credits split one prompt's own reward among its samples. Ours splits a rule's gain over a persistent library across every training goal. With the same Shapley formula, the games of TailRL and GCPO trail ours by 3.2 and 3.9 points in our loop (Table 19). Proposition 1 also holds beyond our setting, for any group credit that weighs marginal gains by subset size and for any game, so it tells a practitioner which objective a group credit optimizes under GRPO before any training. It recovers TailRL and MaxRL as special cases, and Proposition 3 extends it to goals that conflict.

To our knowledge, RuleForge is the first method to train a model on the Shapley split of a library's gain over every goal. We would be grateful if you would reconsider your rating in light of this, and we are happy to answer any further questions.

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

This paper proposes a method to automatically create primal heuristics for NP complete problems by automatically creating rules using an LLM. The LLM is trained using GRPO on a Shapley score. In addition, the model proposes creating a selection function using an LLM which picks the correct rule.

Critical strengths

The work is very thorough and the idea of using LLMs to automatically design heuristics from a pool of examples is sound. I especially liked the ablation across multiple LLMs (appendix) and the analysis in section 4 (particularly observation 6 rules out a common “hero heuristic” explanation that can happen in heuristic generation).

Critical weaknesses

One concern for the training objective is that the problem is, as far as I can tell, partially observable since the model never sees the entire pool of goals. In general, rewarding a model for meeting some other missed goal than the one originally asked for seems somewhat dangerous: Isn’t this just random noise from the point of view of the LLM since the model does not know and therefore actively craft actions to catch those missed goals?

Using grammar mutation in addition to the LLM based generation also muddles the point of the advantage of training a generator model (e.g. are table 2 rules LLM designed and not just grammar mutations of one existing reference).

Why are only 2 episodes worth of the GRPO updates done? What would happen if you increased the number of training sessions?

The verification and admission step could also be improved: The currently used greedy heuristic may be appropriate for large candidate sets, but as far as I can tell, we have only 12 admissable rules at most (6 from W and 6 from mutation), and admit 8 of them. Exact solution is still feasible, even for a brute force search over all 12 choose 8 options. Picking the maximizing rules could make a significant difference since it affects both the total number of rules necessary to cover the problem set, and it affects the covering of each individual rule, which affects the selector quality necessary for good performance.

Even if I misunderstood the number of candidates, often using greedy selection as a primal heuristic and then running local mutation into branch-and-bound for the candidate set can significantly improve the overall results (though the exact level of improvement does depend on the distribution and correlation of the proposed rules).

The size of pool should also be ablated since it changes the effective speed of generation: I expect that scoring a rule is practically free compared to generating them using an LLM (branches+arithmetic operations should not be expensive to evaluate), so depending on how diverse the LLM generated rules really are this could materially speed up the generation of heuristics (this also reveals how good the shapley based loss and the submodular optimization is at reducing redundancy in the rulesets).

A similar claim can be made for training: Recent work (“Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statistic”) demonstrates that larger group sizes (32-64) may be statistically attractive, though this depends on how expensive rollouts are (though generating small rules and verifying them is presumably not too expensive…). The interesting thing for this work is that the samples are not iid but coupled within the group, so the behavior will generally be different, but perhaps more aligned to the “diversity” objective aimed for in this work.

In general, I would also expect some comparison in whether a selector is even necessary: How much slower is it to just run all found rules in parallel on the instances? For table 1: How many inference goals are there? E.g. is it 45.2 out of 100 or out of 1000?

One potential bias in the results are the hand-written rules used to seed the process: Depending on the choice (and whether prior methods use them), hand-written rules can easily affect the overall conclusion. The easiest way to remove this would be to run a loop without any seed rules.

Some of the notation is quite hard to follow: e.g. equation 2, I would expect more typical notation for the policy value function under policy σ\sigma, i.e. Vσ(L)V^\sigma(L) rather than “Met”. Line 250-251 does not really make sense since the J_m are presented without any particular order.

Questions for authors

See "weaknesses" section

5 comments
AuthorsOpenReview ↗

Response to Reviewer LFSZ (1/3)

We thank the reviewer for the detailed and constructive feedback. We address your points below, including additional experiments and paper edits found in our revised draft. Figure, table, and appendix numbers below refer to the revised PDF.

W1. The writer never sees the other goals, so credit for meeting them may be noise from the model's point of view.

The credit on other goals carries signal, and the writer does not need to see a goal to learn from it. The reward changes which rules the writer is likely to write. On inference, the goals of one window set thresholds on the same four correlated metrics, so a rule that meets one missed goal often meets others. If this credit were noise, removing or scrambling it would cost nothing. Motivated by your feedback, we tested both and also named the nearest goals in the prompt. Held-out inference goals met, means over five seeds (Appendix N, Table 28):

Writer's creditGoals met (%)Against the recipe
Shapley credit on every goal, the recipe71.0
The same, plus the eight nearest training goals named in the prompt72.2+1.2 [0.4, 2.0]
Shapley credit on the prompting goal alone67.8−3.2 [−4.4, −2.0]
Shapley credits shuffled within each group65.3−5.7 [−7.0, −4.4]
Expert iteration, no credit65.1

Crediting the prompting goal alone removes only the credit on other goals and costs 3.2 points. In other words, the writer learns from credit on goals it never sees. Shuffling the credits within each group keeps the reward's scale and distribution and removes only which rule holds which share, and goals met fall to the level of expert iteration, which never trains on the credit. Naming the nearest goals in the prompt adds a further 1.2 points, so the writer also uses this information when it has it.

W2. Grammar mutation muddles the advantage of training the writer. Are Table 2's rules written by the model or mutations of an existing rule?

You are right that the submitted Table 2 did not settle this. Its three admitted rules came from the earlier version of RuleForge (Appendix M), whose admissions mixed the writer's proposals with other sources. Motivated by your feedback, Table 2 now shows three admitted inference rules from a run of the final recipe, all proposed by the writer, and the new Table 34 gives the admitted rule of largest gain on each of the five problems, again all from the writer. The writer's share of admissions also grows as it trains. Rules admitted per generation, out of 8, means over five runs (Appendix F):

ProposerGen 0Gen 1Gen 2
Writer2.15.66.6
Grammar mutation5.92.41.4

Mutation with greedy admission alone reaches 63.3 percent (Table 1). The recipe without mutation reaches 69.9 percent and still leads CALM by 4.9 [3.5, 6.3] points (Table 11). With mutation unchanged, giving the writer CALM's reward costs 4.9 of the 6.0-point lead, and a frozen writer reaches 64.9 percent, level with CALM's 65.0 (Observation 4). The lead therefore comes from training the writer.

W3. Why are only two rounds of GRPO updates done, and what happens with more?

The writer trains with GRPO after generations 0 and 1, and no proposals follow the last generation, so three generations give two rounds of GRPO. Three generations divide the fixed budget into three rounds of admission. Thanks for the suggestion, we ran four and five generations, each with its own budget, and five generations held to the fixed budget (Table 25, Figure 33b):

Generations (GRPO rounds)EvaluationsGoals met (%)
3 (2), the recipe30,83371.0
4 (3)39,10072.1
5 (4)47,40072.6
5 (4), held to the budget30,83370.4

A fourth generation adds 1.1 [0.3, 1.9] points and a fifth 0.5 [−0.3, 1.3] more. Held to the fixed budget, five generations stay within noise of three, at −0.6 [−1.4, 0.2]. In other words, more rounds help when they come with more evaluations, so at the fixed budget we keep three.

AuthorsOpenReview ↗

Response to Reviewer LFSZ (2/3)

W4. Admission picks 8 of at most 12 candidates, so exact admission, or greedy admission followed by local search, is feasible and could matter.

Thanks for pointing out that the size of the admission pool was confusing in the submitted draft. We want to clarify that twelve is the number of candidates per prompt, six from the writer and six mutations. Each generation prompts every graded training goal the library misses, so admission chooses its eight rules from about 790, 440 and 260 survivors in generations 0, 1 and 2. Step 2 in Section 3 now says that admission chooses from several hundred survivors, and Table 25 gives the counts. As you suggest, we also ran swap local search after greedy admission, and exact admission with CP-SAT, each on the recipe's survivor pools. CP-SAT solves each generation in 1.0 to 47 seconds against 0.2 for greedy, with no extra evaluations (Table 25, Figure 33c):

AdmissionChosen rule (%)Library oracle (%)Against greedy
Greedy, the recipe71.075.4
Greedy, then swap local search71.275.6+0.2 [−0.6, 1.0]
Exact, CP-SAT71.375.8+0.3 [−0.5, 1.1]

Greedy admission reaches over 98 percent of the exact gain in library value in every generation, far above its 1−1/e1 - 1/e guarantee, so exact admission adds only 0.3 points, within noise. Both admissions keep libraries of 34 rules, and the library oracle moves only from 75.4 to 75.8, so the library's coverage, and with it the selector's task, barely changes. Exact admission also moves CALM only from 65.0 to 65.2, so admission does not separate the methods.

W5. The pool size should be ablated, since scoring a rule is nearly free next to generating it.

Thanks for the suggestion, we varied the rules sampled per prompt from 3 to 24 (Table 25, Figure 33a). In our protocol, scoring is not free, since every verification comes out of the evaluation budget all methods share. Each candidate takes one prescreen and each survivor 14 more evaluations, so a run spends 150 plus its candidates plus 14 times its survivors (Appendix E). Held-out inference goals met with the budget capped at 30,833 evaluations, means over five seeds. With three rules per prompt, a run prompts every missed goal and stops at 23,650 evaluations:

Rules per promptChosen rule (%)Library oracle (%)CandidatesSurvivorsRepeats (%)
369.373.66,9801,1809
6, the recipe71.075.49,8201,49012
1271.475.712,3001,31016
2470.274.515,5201,08023
12, at 1.8 times the budget71.976.216,9802,69015
6, plus 18 mutations71.275.614,6001,14012
6, plus 42 mutations70.575.021,90062012

Twelve rules per prompt add 0.4 [−0.4, 1.2] points, within noise, and twenty-four fall by 0.8 [−1.6, 0.0], at the edge of noise. A larger pool spends more of the budget on prescreens and finds fewer survivors, since more of its proposals repeat a library rule. Sampling dominates a run's wall-clock time, and twelve rules per prompt lengthen it by 38 percent for a gain within noise, so a larger pool does not speed up the search. Mutations need no model, so we also enlarged the pool with them, as your point suggests. Extra mutations add under 2 percent to a run's wall-clock time, yet 18 or 42 per prompt stay within noise of the recipe, since each still takes a prescreen and most repeat a library rule's outcome. The repeats column measures the redundancy you ask about. A repeat adds no gain, so the Shapley credit gives it nothing, and training on it cuts the writer's repeats from 37 to 12 percent (Observation 4).

W6. Larger groups of 32 to 64 may be statistically attractive, and the samples of a group are coupled.

Thanks for the pointer to "Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statistic". Its U-statistic view can favor groups of 32 to 64 when each sample is scored alone. Under our credit, as you note, a rule's reward depends on the other rules of its group, so the objective the update ascends changes with the group size nn. By Proposition 1, the centered Shapley credit ascends ∑m=1n−1Jm/m\sum_{m=1}^{n-1} J_m/m, so a larger group weighs goals the writer rarely fixes more heavily. Motivated by your feedback, we added groups of 32 and 64 to the groups of 4, 8 and 16 of Appendix I, under plain on-policy GRPO at a fixed number of samples (Table 26, Figure 34):

nnGoals met (%)Weight on rarely fixed goalsPredicted by Proposition 1Coupled groups (%)
466.21.271.1414
866.91.581.4224
1667.12.191.9733
3267.32.742.8641
6467.23.213.9748
AuthorsOpenReview ↗

Response to Reviewer LFSZ (3/3)

(W6, continued)

Goals met stay within 0.4 points from 8 to 64, while the weight on rarely fixed goals rises as predicted, within 0.22 of the prediction up to groups of 32. The last column measures the coupling you describe, the share of groups in which two or more rules add value on one goal. The Shapley split differs from per-sample credit only on these groups. Inside the full recipe, groups of 32 reach 70.6 percent against 71.0 at a fixed number of samples, and 71.6 at a fixed number of groups with 2.4 times the evaluations. Each sample's verification counts against the shared budget, so we keep groups of eight.

W7a. Is a selector necessary? How much slower is it to run every rule in parallel?

The selector is necessary on an online problem, since a scheduler commits to one order before the window runs and learns which rule's replay was best only in hindsight. Thanks for the suggestion, we timed each policy over RuleForge's 34-rule library, with replays on one CPU core and the selector's model call on one H100 (Table 27, Figure 35a):

Policy over the libraryReplays per goalTime per goalGoals met (%)
Best single rule10.19 s61.5
Selector's chosen rule10.19 s and one 0.21 s model call71.0
Selector's shortlist of three, best kept30.57 s and one 0.21 s model call73.6
Every rule, best kept (library oracle)346.5 s75.4

On inference scheduling, keeping the best of every rule is possible only in simulation, where every replay finishes before a rule is chosen. The selector recovers 9.5 of the 13.9 points that separate the best single rule from this hindsight oracle, with one replay instead of 34. It calls the model once per goal, before the window, and no model runs at any scheduling decision. On the static flow shop and traveling salesman problem, keeping the best of every rule is a valid method. It lowers the gaps from 2.56 to 2.43 and from 9.9 to 9.3 at up to 25 times the computation (Appendix H). As Step 5 states, only the first rule of the shortlist runs.

W7b. How many inference goals does Table 1 count?

Thanks for catching this. Table 1 reports the percent of 2,816 held-out goals met, so the hand-written rules meet 45.2 percent of them. Table 1's caption now gives the denominator.

W8. The hand-written seed rules may bias the result, so run the loop without seed rules.

On inference scheduling, every method starts from the same ten hand-written rules. Thanks for the suggestion, we also started RuleForge, CALM, EoH-S and mutation with greedy admission from first come, first served alone, and the first three from an empty library. Without seeds in its library, RuleForge's writer still fine-tunes on the hand-written rules, while CALM's writer starts from the base model. We therefore also ran RuleForge from an empty library with its writer started from the base model. Held-out inference goals met, means over five seeds (Table 27, Figure 35b and c):

MethodTen hand-written rulesFirst come, first servedEmpty library
RuleForge71.070.169.8
RuleForge, no supervised start68.6
CALM65.062.862.1
EoH-S64.362.061.4
Mutation, greedy admission63.355.4needs a parent rule
RuleForge minus CALM6.0 [4.5, 7.5]7.3 [5.8, 8.8]7.7 [6.1, 9.3]
Change in the lead from the seeds+1.3 [0.1, 2.5]+1.7 [0.4, 3.0]
No supervised start, minus CALM6.5 [4.9, 8.1]

The seeds lift the search baselines more than RuleForge, so its lead over CALM grows without them, by 1.7 [0.4, 3.0] points from an empty library. With no supervised start either, RuleForge still leads CALM by 6.5 points, within noise of its lead with the seeds. For every method, the goals and the graded score are still defined from the hand-written rules' outcomes.

W9. Equation 2 should use standard value-function notation instead of "Met", and lines 250 to 251 list the objectives without an order.

Thanks for catching both. Equation 2 now writes the met rate as a value function V(L,σ)V(L, \sigma), with the library oracle V∗(L)V^*(L). Section 3 now states the order of the objectives, J1≤⋯≤JnJ_1 \le \dots \le J_n, since a larger set of rules gains at least as much.

The revision also adds multitask genetic programming and multi-task MAP-Elites to Table 1, and RuleForge leads both on all five problems. Observation 7 and Figure 5 now show when each part of the credit helps, and every choice of the recipe varied alone stays above CALM (Table 32). We also rewrote parts of Sections 2 to 4 for clarity.

Thanks again for your feedback. Motivated by your points, we have run additional experiments and made numerous paper edits, while making our wording about our method more clear which we feel has improved the quality of our draft. We would greatly appreciate it if you would consider raising your score accordingly. Do you have any other questions we can address?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.