Behavior and Representation in Open-Weight Large Language Models for Combinatorial Optimization: From Feature Extraction to Algorithm Selection

arXiv:2512.13374v2 Announce Type: replace Abstract: Recent advances in Large Language Models (LLMs) open new perspectives for automation in optimization, yet little is known about whether their internal representations capture problem structure or algorithmic behavior. We investigate whether representations learned by frozen, open-weight LLMs for combinatorial optimization instances can support downstream decision tasks. The goal is not to replace exact feature extractors or to propose a new algorithm, but to assess whether such representations are reusable for feature recovery and algorithm selection. Our methodology combines direct querying, which tests explicit feature extraction, with probing analyses of whether this information is implicitly encoded in the hidden layers. The probing framework is further extended to a per-instance algorithm selection task. Experiments span four benchmark problems, three instance representations, and five open-weight models from 3B to 120B parameters across the Llama instruct and GPT reasoning families, including a chain-of-thought study on Llama models. Results show a limited ability to recover features explicitly, particularly those requiring structured computation, while part of this information remains implicitly encoded in the hidden states. A consistent gap separates implicit encoding from explicit retrieval. Model scale attenuates this gap, whereas the effect of chain-of-thought prompting depends strongly on model size, and in all cases the gap remains open. Reasoning-oriented models also tend to abstain more when reliable computation is not possible. Notably, the predictive power of LLM hidden-layer representations is comparable to traditional feature extraction across all five models, indicating they can act as effective surrogate descriptors for downstream optimization tasks.

Source: arXiv cs.AI | 2026-08-13