Pith. sign in

REVIEW 3 major objections 5 minor 29 references

An online-trained language model can replace GRASP’s hand-crafted constructor and match the gain from GPU acceleration on hard flow-shop instances.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 16:45 UTC pith:IOSUJ67Q

load-bearing objection Clean online-IL constructor idea with a real numerical win over GPU-GRASP on ta51–ta60, but the “practical alternative to hand-engineered constructors” claim outruns a weak baseline set. the 3 major comments →

arxiv 2607.28135 v1 pith:IOSUJ67Q submitted 2026-07-30 cs.LG

LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning

Mohand Mezmaz , Gr\'egoire Danoy This is my paper
classification cs.LG
keywords combinatorial optimizationGRASPimitation learningbehavioral cloningdecoder-only Transformerpermutation flow-shoponline learningmetaheuristics
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Classical GRASP builds solutions with a fixed, myopic greedy rule that never learns from the good solutions it already found. This paper reframes that construction step as online imitation learning: local search acts as the expert, a decoder-only Transformer acts as the policy, and the only training data are the elite solutions discovered on the instance itself. No offline pretraining and no problem-specific features are required—the system talks to the domain only through the objective evaluator. On the hardest intermediate Taillard flow-shop block (50 jobs × 20 machines), where half the optima are still open, the resulting LM-GRASP beats a GPU implementation of classical GRASP by roughly the same margin that GPU acceleration itself beats a sequential CPU run. The claim is that instance-specific, online-trained sequence models are a practical alternative to hand-engineered constructors precisely when the landscape resists classical greedy construction.

Core claim

On Taillard ta51–ta60 under a fixed five-hour wall-clock budget on identical V100 hardware, LM-GRASP reaches mean makespan 3771.8 versus GPU-GRASP’s 3800.4 (algorithmic gap 28.4 units), comparable to the 27.2-unit hardware gap between CPU-GRASP and GPU-GRASP, and is best on every instance and every run. The result is offered as evidence that a construction policy learned online from local-search optima can replace a hand-crafted greedy heuristic on landscapes that resist classical construction.

What carries the argument

LM-GRASP’s learn–infer–improve cycle: a decoder-only Transformer is behaviorally cloned on a dynamic elite archive of local-search trajectories, then used for autoregressive construction; the archive is refreshed and the policy retrained each generation, with the domain interface limited to the objective evaluator.

Load-bearing premise

That beating the standard incremental-makespan GRASP baseline (CPU and GPU) is enough to establish the method as a practical alternative to hand-engineered constructors in general.

What would settle it

On the same ta51–ta60 instances and five-hour budget, a stronger published PFSP metaheuristic or a coordinated hyper-heuristic GRASP pool closes or reverses the 28-unit gap versus LM-GRASP.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • For permutation problems whose fitness landscapes are rugged enough that classical greedy construction plateaus early, an online-trained Transformer constructor can buy roughly as much quality as moving the same heuristic onto a GPU.
  • The only required domain interface is an objective evaluator plus a local-search oracle, so the same loop can be dropped onto other pure-permutation problems without redesigning a Restricted Candidate List.
  • Because the anytime curve has not flattened at budget exhaustion, longer runs or continuous (rather than batch) policy updates should continue to improve solution quality.
  • Hand-tuning large pools of construction configurations becomes less necessary once the constructor itself is learned from the elite solutions found on the instance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same online-imitation loop may be most attractive exactly where offline neural constructors are weakest: single hard instances or new problem variants for which no large pretraining corpus exists.
  • If behavioral cloning on local optima already generalizes inside the archive, adding a light DAgger-style correction for distribution shift could shrink the early bootstrap overhead that currently costs roughly the first 11 minutes.
  • The complexity-frontier argument used for 50×20 PFSP suggests a practical test: measure where the crossover occurs between classical GRASP and LM-GRASP as machine count or landscape ruggedness is varied.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes LM-GRASP, a hybrid metaheuristic that replaces GRASP’s hand-crafted randomized construction with an instance-specific decoder-only Transformer trained online via behavioral cloning. Local search acts as an expert oracle; elite trajectories form a dynamic archive; no external data or offline pretraining is used. The pipeline interfaces with the domain only through the objective evaluator. On Taillard PFSP ta51–ta60 (5 h wall-clock, identical V100), LM-GRASP reports mean makespan 3771.8±5.4 versus GPU-GRASP 3800.4±5.8 (algorithmic gap 28.4±8.4), comparable to the CPU→GPU hardware gap of 27.2±11.0, and is best on all 10 instances and all 100 runs. A taxonomy positions the method in a new ILM-to-Solution cell.

Significance. If the result holds under stronger baselines, the work is a genuine contribution: it cleanly isolates an algorithmic learning delta from hardware acceleration, requires no problem-specific feature engineering, and occupies an underexplored niche (online, from-scratch, instance-specific generative construction). Code availability via COLM and the three-tier experimental design are concrete strengths. The practical-alternative claim is currently overstated relative to the baseline set, but the paradigm and the narrow numerical win over classical GPU-GRASP are worth publishing after revision.

major comments (3)
  1. [§5.2, Abstract, §6] §5.2 Evaluated Methods; Abstract; §6: The central claim that LM-GRASP is a “practical alternative to hand-engineered constructors” rests on CPU/GPU-GRASP with a single incremental-makespan RCL. The paper itself notes that competitive GRASP on this block previously required coordinating 315 hand-tuned configurations [1], and Fig. 3 shows GPU-GRASP plateauing by ~30 s. Without comparison to that hyper-heuristic pool, multi-α/path-relinking GRASP, or standard strong PFSP methods (e.g. iterated greedy), the interpretive payload does not follow from the narrow win. At minimum, add one stronger classical baseline under the same budget, or narrow the claim to “alternative to classical single-heuristic GRASP construction.”
  2. [Table 3, §5.3] Table 3 and §5.3: The algorithmic gap (28.4±8.4) and hardware gap (27.2±11.0) have overlapping standard deviations, which the abstract acknowledges. The all-instance/all-run win count is stronger evidence than the mean gap alone. Report a paired statistical test (e.g. Wilcoxon signed-rank across the 100 runs) and avoid equating the two deltas in magnitude without that test; otherwise the “comparable to GPU acceleration” framing overreaches.
  3. [§5.2] §5.2 Hyperparameter Selection; free parameters (L=14, d=768, K=5000, τ=1.3, top-k=0.2n, etc.): All architectural and inference hyperparameters were set by limited preliminary trials with no sensitivity analysis. For a method whose overhead is dominated by online Transformer training (~660 s bootstrap, Fig. 3), robustness to archive size, temperature, and depth is load-bearing. A minimal ablation (e.g. K ∈ {1k,5k}, τ ∈ {1.0,1.3}, or a smaller L) under a shortened budget would substantially strengthen the practicality claim.
minor comments (5)
  1. [Table 1] Table 1 caption and body cite “updated: June 2026” and arXiv date is 30 Jul 2026; ensure consistency with actual known-optima counts at submission time, or mark as provisional.
  2. [§2.1] §2.1 Eqs. (1)–(4): standard PFSP recurrence; fine, but C_i(π,k) notation mixes machine/job indices without a brief reminder that π is the job order—add one clarifying sentence for non-scheduling readers.
  3. [Figure 3] Figure 3: log-scale time axis is appropriate; state explicitly whether curves are mean over 100 runs or a single representative run, and whether bands are std or min–max.
  4. [§3.2] §3.2 / Figure 1: “ILM-to-Solution” novelty claim is plausible; a one-sentence check against instance-specific fine-tuning of pretrained CO policies would make the “first instantiation” wording safer.
  5. [Algorithm 2, §2] Typos/style: “V alidate” in Algorithm 2 (spurious space); “themakespan” / “apure” spacing glitches in §2; “half its optima being unknown” is slightly informal for the abstract.

Circularity Check

0 steps flagged

No significant circularity: empirical online-learning metaheuristic evaluated against external Taillard benchmarks and independent classical baselines.

full rationale

LM-GRASP is an empirical optimization paper. Its central claim is a measured makespan gap (LM-GRASP 3771.8±5.4 vs GPU-GRASP 3800.4±5.8 under fixed 5h V100 wall-clock on ta51–ta60), not a first-principles derivation or a fitted constant presented as prediction. Training the Transformer via behavioral cloning on elite trajectories discovered by local search is the intentional method (online imitation), not a tautology: the policy is then used to generate new candidates that are validated, improved by local search, and scored by the external objective; Fig. 5 even reports that from iteration 5 the policy produces lower mean makespan than its own training corpus, which would be impossible if performance were definitional. Evaluation anchors are external (Taillard best-known makespans; CPU-GRASP and GPU-GRASP with the same hand-crafted incremental-makespan RCL). Self-citations ([1], [18], [19]) supply background on PFSP difficulty, prior hyper-heuristic GRASP, and code availability; none is a uniqueness theorem or load-bearing premise that forces the reported gap. No equation reduces a claimed prediction to a fitted input by construction. Baseline weakness is a correctness/scope concern, not circularity.

Axiom & Free-Parameter Ledger

9 free parameters · 6 axioms · 2 invented entities

Load-bearing content is mostly methodological choices and empirical hyperparameters, not physical axioms. The central performance claim rests on: standard CO/math background; the modeling choice that BC on local-search trajectories is a valid expert signal for construction; a large set of hand-chosen network/training/inference knobs; and the invented LM-GRASP loop / ILM-to-Solution framing. No new physical entities. Transfer beyond PFSP is assumed possible via ‘objective evaluator only’ interface but not demonstrated.

free parameters (9)
  • Transformer depth L = 14
    Set to 14 layers by limited preliminary trials; controls capacity and training cost under the fixed wall-clock budget.
  • Attention heads / embedding dim = 12 heads, 768 dim
    12 heads, d_model=768 chosen empirically; standard GPT-2-scale knobs not swept systematically.
  • Archive capacity K = 5000
    Elite corpus size fixed at 5000; directly defines the BC dataset and eviction pressure.
  • Softmax temperature τ = 1.3
    Inference exploration knob set to 1.3; strongly affects diversity vs mode concentration of constructed permutations.
  • top-k fraction α_inf = 0.2 × n
    k=⌊0.2×n⌋ truncation chosen empirically; analogous to classical GRASP α but not cross-validated.
  • Learning rate and training schedule = lr=6e-4; warmup=500; etc.
    6e-4, 500-step warmup, weight decay 0.1, grad clip 1.0, max 2001 steps, early-stop patience 15 on 1e-4; all hand-set.
  • Candidates per generation M / batch B_inf = M=10000, B_inf=512
    M=10000, B_inf=512 determine how wall-clock is split between inference and training.
  • Wall-clock budget T = 5 hours
    5-hour fixed budget defines the comparison regime; LM-GRASP’s ~660s bootstrap makes results budget-sensitive.
  • Dropout rate = 0.2
    0.2 on residuals, embeddings, attention; regularization choice without ablation in the paper.
axioms (6)
  • standard math PFSP makespan recurrence and strong NP-hardness for m≥3 (standard scheduling theory).
    Section 2.1 equations (1)–(4) and Garey et al. citation; defines the objective the archive optimizes.
  • domain assumption Local search on a neighborhood N produces expert trajectories suitable for behavioral cloning of a constructive policy.
    Core of §2.3 and §4: LS is the inductive expert oracle; classic BC distribution-shift risk is acknowledged via citations but not mitigated (no DAgger).
  • domain assumption A decoder-only causal LM over job tokens can represent feasible permutations and non-myopic construction structure without problem-specific features.
    §2.4 and §4.4 mapping tokens→jobs, sequences→solutions; feasibility enforced by post-hoc filter rather than architectural constraint.
  • domain assumption Interfacing only through the objective evaluator suffices for cross-domain applicability of the pipeline.
    Stated in Abstract and §4.1; used to claim generality, but only PFSP is evaluated.
  • ad hoc to paper Classical incremental-makespan RCL GRASP is the appropriate foil for ‘hand-engineered constructors’ on this block.
    §5.2 baseline choice; underpins the practical-alternative claim without SOTA PFSP or multi-config hyper-heuristic controls.
  • ad hoc to paper Fisher-Yates random permutations are an adequate prior-free bootstrap for the elite archive.
    §4.2 Phase 1; no problem knowledge at seed time by design.
invented entities (2)
  • LM-GRASP learn–infer–improve loop independent evidence
    purpose: Replace GRASP’s static RCL construction with an online-trained autoregressive policy and elite archive.
    Algorithm 2 / Figure 2; the paper’s main methodological object. Operationally defined and implemented; not a physical postulate.
  • ILM-to-Solution taxonomy cell no independent evidence
    purpose: Position the method as the first instance-specific LM that directly emits solutions trained online from scratch.
    §3.2 Figure 1; taxonomic label rather than empirical entity. ‘First’ claim is authors’ knowledge claim, not independently surveyed here.

pith-pipeline@v1.2.0-daily-grok45 · 19646 in / 4540 out tokens · 109252 ms · 2026-07-31T16:45:55.218408+00:00 · methodology

0 comments
read the original abstract

Machine learning for combinatorial optimization typically relies on neural constructors trained via reinforcement learning on large offline datasets for a fixed problem class-incurring high pretraining costs and generalizing poorly outside the training distribution. We propose an alternative: a metaheuristic framework that reformulates the randomized constructive phase of GRASP as an online imitation learning task, trained from scratch on each problem instance. A local search procedure acts as an expert oracle, while a decoder-only Transformer serves as the constructive policy. Unlike classical GRASP, which relies on static, myopic heuristic rules based on localized scalar costs, our approach is fully data-driven: the construction policy emerges from high-quality solutions discovered during the search itself, with no problem-specific feature engineering required. We instantiate this as LM-GRASP, a hybrid metaheuristic following an iterative learn-infer-improve cycle, training the policy online via behavioral cloning on a dynamic archive of elite trajectories-no external data or offline pretraining needed. The pipeline interfaces with the domain solely through the objective evaluator used by local search. Evaluated on the Taillard PFSP benchmark (ta51-ta60), the most discriminating block due to half its optima being unknown, LM-GRASP outperforms GPU-GRASP by 28.4 makespan units on average-comparable to the gain from GPU acceleration over sequential execution (27.2 units), though with overlapping standard deviations. This suggests instance-specific, online-trained language models are a promising, practical alternative to hand-engineered constructors, especially for landscapes resistant to classical greedy construction.

Figures

Figures reproduced from arXiv: 2607.28135 by Gr\'egoire Danoy, Mohand Mezmaz.

Figure 1
Figure 1. Figure 1: Taxonomy of language model-based optimization approaches along two axes: training corpus [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Structural comparison between classic GPU-GRASP and the proposed LM-GRASP framework. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Average optimization trajectories over time (log scale) across [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Breakdown of the 10,000-candidate batch by category across iterations. The proportion of novel, [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Intra-iteration makespan at four checkpoints per generation averaged across [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 2 linked inside Pith

  1. [1]

    Alekseeva, M

    E. Alekseeva, M. Mezmaz, D. Tuyttens, and N. Melab. Parallel multi-core hyper-heuristic GRASP to solve permutation flow-shop problem.Concurrency and Computation: Practice and Experience, 29(9): e3835, 2017

    2017

  2. [2]

    Chen and Y

    X. Chen and Y. Tian. Learning to perform local rewriting for combinatorial optimization. InAdvances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019

    2019

  3. [3]

    S. J. Chin, M. Winkenbach, and A. Srivastava. Learning to deliver: A foundation model for the Montreal capacitated vehicle routing problem, 2024. arXiv preprint arXiv:2403.00026

    Pith/arXiv arXiv 2024

  4. [4]

    Da Ros, M

    F. Da Ros, M. Soprano, L. Di Gaspero, and K. Roitero. Large language models for combinatorial optimization: A systematic review, 2025. arXiv preprint arXiv:2507.03637

    arXiv 2025

  5. [5]

    Elhenawy et al

    M. Elhenawy et al. Visual reasoning and multi-agent approach in multimodal large language models: Solving TSP and MTSP combinatorial challenges.Machine Learning and Knowledge Extraction, 6(3): 1894–1920, 2024

    1920

  6. [6]

    T. A. Feo and M. G. C. Resende. Greedy randomized adaptive search procedures.Journal of Global Optimization, 6(2):109–133, 1995

    1995

  7. [7]

    M. R. Garey, D. S. Johnson, and R. Sethi. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2):117–129, 1976

    1976

  8. [8]

    Gasse, D

    M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi. Exact combinatorial optimization with graph convolutional neural networks. InAdvances in Neural Information Processing Systems, volume 32, 2019

    2019

  9. [9]

    J. Gmys. Exactly solving hard permutation flowshop scheduling problems on peta-scale GPU-accelerated supercomputers.INFORMS Journal on Computing, 34(5):2448–2466, 2022

    2022

  10. [10]

    Held and R

    M. Held and R. M. Karp. A dynamic programming approach to sequencing problems.Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210, 1962

    1962

  11. [11]

    J. J. Hopfield and D. W. Tank. “Neural” computation of decisions in optimization problems.Biological Cybernetics, 52(3):141–152, 1985

    1985

  12. [12]

    Huang, Q

    X. Huang, Q. Shen, Y. Hu, A. Gao, and B. Wang. LLMs for mathematical modeling: Towards bridging the gap between natural and mathematical languages. InFindings of ACL: NAACL 2025, pages 2678–2710, 2025

    2025

  13. [13]

    Hussein, M

    A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne. Imitation learning: A survey of learning methods. ACM Computing Surveys, 50(2):1–35, 2017

    2017

  14. [14]

    W. Kool, H. van Hoof, and M. Welling. Attention, learn to solve routing problems! InInternational Conference on Learning Representations (ICLR), 2019. 16

    2019

  15. [15]

    Y.-D. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, and S. Min. POMO: Policy optimization with multiple optima for reinforcement learning. InAdvances in Neural Information Processing Systems (NeurIPS), pages 21188–21198, 2020

    2020

  16. [16]

    F. Liu, X. Tong, M. Yuan, X. Lin, F. Luo, Z. Wang, Z. Lu, and Q. Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model, 2024. arXiv preprint arXiv:2401.02051

    Pith/arXiv arXiv 2024

  17. [17]

    Martinek, S

    A. Martinek, S. Lukasik, and A. H. Gandomi. Large language models as tuning agents of metaheuristics. InESANN 2024, 2024

    2024

  18. [18]

    M. Mezmaz. COLM: A platform for integrating language models in combinatorial optimization.https: //gitlab.com/uniluxembourg/snt/pcog/colm, 2026

    2026

  19. [19]

    Mezmaz, N

    M. Mezmaz, N. Melab, and E.-G. Talbi. A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems. InProceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 1–9, 2007

    2007

  20. [20]

    D. A. Pomerleau. Efficient training of artificial neural networks for autonomous navigation.Neural Computation, 3(1):88–97, 1991

    1991

  21. [21]

    M. G. Ravetti, C. Riveros, A. Mendes, M. G. Resende, and P. M. Pardalos. Parallel hybrid heuristics for the permutation flow shop problem.Annals of Operations Research, 199(1):269–284, 2012

    2012

  22. [22]

    S. Ross, G. Gordon, and D. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. InProceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 627–635. JMLR Workshop and Conference Proceedings, 2011

    2011

  23. [23]

    Taillard

    E. Taillard. Benchmarks for basic scheduling problems.European Journal of Operational Research, 64 (2):278–285, 1993

    1993

  24. [24]

    Varrette, H

    S. Varrette, H. Cartiaux, S. Peter, E. Kieffer, T. Valette, and A. Olloh. Management of an academic HPC & research computing facility: The ULHPC experience 2.0. InProceedings of the 6th ACM High Performance Computing and Cluster Technologies Conference (HPCCT 2022), Fuzhou, China, 2022. Association for Computing Machinery (ACM). ISBN 978-1-4503-9664-6

    2022

  25. [25]

    Vaswani, N

    A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin. Attention is all you need. InAdvances in Neural Information Processing Systems, volume 30, 2017

    2017

  26. [26]

    Vinyals, M

    O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. InAdvances in Neural Information Processing Systems (NeurIPS), volume 28, 2015

    2015

  27. [27]

    J. P. Watson, J. C. Beck, A. E. Howe, and L. D. Whitley. Problem difficulty for permutation flow-shop scheduling.Artificial Intelligence, 149(2):199–231, 2003

    2003

  28. [28]

    D. H. Wolpert and W. G. Macready. No free lunch theorems for optimization.IEEE Transactions on Evolutionary Computation, 1(1):67–82, 2002

    2002

  29. [29]

    Zhang, J

    T. Zhang, J. Yuan, and S. Avestimehr. Revisiting OPRO: The limitations of small-scale LLMs as optimizers. InFindings of ACL 2024, pages 1727–1735, 2024. 17

    2024