- 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
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:
| Choice | Settings, recipe in bold | Held-out goals met (%) |
|---|---|---|
| Generations, each at its own budget | 2, 3, 4, 5 | 68.8, 71.0, 72.1, 72.6 |
| Rules per prompt | 3, 6, 12, 24 | 69.3, 71.0, 71.4, 70.2 |
| Group size | 4, 8, 16, 32 | 70.3, 71.0, 70.9, 70.6 |
| Admissions per generation | 4, 8, 16 | 69.1, 71.0, 70.7 |
| Prescreen margin (%) | 0, 2, 5 | 70.1, 71.0, 70.3 |
| Metrics per goal, as lead over CALM (points) | 1, up to 2, up to 3 | 4.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:
| Problem | Rule | What it does |
|---|---|---|
| Inference scheduling | where(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 shop | 0 - p * (1 + max(0, 0 - slack) / (wr + 1)) - 0.2*nr | shortest operation first, a late job's time scaled by its lateness over its remaining work, fewer remaining operations first |
| Online bin packing | where(rem - item < 0.1*cap, 3 - (rem - item)/cap, 0 - rem/cap) | fills a bin the item nearly completes, otherwise best fit |
| Traveling salesman | 0 - 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 shop | sum_p + 0.4*max_p to order, 0 - idle - 0.2*pos to break ties | largest 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.
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 , 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 , 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):
| Method | Goals met (%) ↑ | Relative shortfall ↓ |
|---|---|---|
| Hand-written rules | 45.2 | 0.148 |
| Classical pool | 57.5 | 0.097 |
| Genetic programming | 63.1 | 0.074 |
| CALM | 65.0 | 0.061 |
| RuleForge | 71.0 | 0.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 greedy | Gap (%) ↓ |
|---|---|
| NEH | 0.61 |
| Best published tie-breaking | 0.54 |
| RuleForge's flow-shop rules | 0.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?
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 - tokensruns 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):
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):