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

arXiv: https://arxiv.org/abs/2512.13374 · HTML: https://mlsanity.com/paper/2512.13374/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 69 references that are in the map.
- First posted on arXiv 15 Dec 2025.

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Sparse Autoencoders Find Highly Interpretable Features in Language Models](https://mlsanity.com/paper/2309.08600/) (2023)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [Probing Classifiers: Promises, Shortcomings, and Advances](https://mlsanity.com/paper/2102.12452/) (2021)
- [The Geometry of Truth: Emergent Linear Structure in Large Language Model Representations of True/False Datasets](https://mlsanity.com/paper/2310.06824/) (2023)
- [Do NLP Models Know Numbers? Probing Numeracy in Embeddings](https://mlsanity.com/paper/1909.07940/) (2019)
- [Probing Pretrained Language Models for Lexical Semantics](https://mlsanity.com/paper/2010.05731/) (2020)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)
- [OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models](https://mlsanity.com/paper/2402.10172/) (2024)
- [LLaMEA: A Large Language Model Evolutionary Algorithm for Automatically Generating Metaheuristics](https://mlsanity.com/paper/2405.20132/) (2024)
- [Summary of a Haystack: A Challenge to Long-Context LLMs and RAG Systems](https://mlsanity.com/paper/2407.01370/) (2024)
- [A Systematic Survey on Large Language Models for Algorithm Design](https://mlsanity.com/paper/2410.14716/) (2024)
- [How Large Language Models Encode Context Knowledge? A Layer-Wise Probing Study](https://mlsanity.com/paper/2402.16061/) (2024)
- [Probing What Different NLP Tasks Teach Machines about Function Word Comprehension](https://mlsanity.com/paper/1904.11544/) (2019)
- [A Survey on Large Language Models with some Insights on their Capabilities and Limitations](https://mlsanity.com/paper/2501.04040/) (2025)
- [Discourse Probing of Pretrained Language Models](https://mlsanity.com/paper/2104.05882/) (2021)
- [Holy Grail 2.0: From Natural Language to Constraint Models](https://mlsanity.com/paper/2308.01589/) (2023)
- [Large Language Models for Combinatorial Optimization: A Systematic Review](https://mlsanity.com/paper/2507.03637/) (2025)
- [Pooling And Attention: What Are Effective Designs For LLM-Based Embedding Models?](https://mlsanity.com/paper/2409.02727/) (2024)
- [Syntactic Perturbations Reveal Representational Correlates of Hierarchical Phrase Structure in Pretrained Language Models](https://mlsanity.com/paper/2104.07578/) (2021)
- [Automated Algorithm Selection: from Feature-Based to Feature-Free Approaches](https://mlsanity.com/paper/2203.13392/) (2022)
- [Identifying Linear Relational Concepts in Large Language Models](https://mlsanity.com/paper/2311.08968/) (2023)
- [Exploring Multilingual Probing in Large Language Models: A Cross-Language Analysis](https://mlsanity.com/paper/2409.14459/) (2024)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [Code Evolution Graphs: Understanding Large Language Model Driven Design of Algorithms](https://mlsanity.com/paper/2503.16668/) (2025)
- [Beyond the Hype: Benchmarking LLM-Evolved Heuristics for Bin Packing](https://mlsanity.com/paper/2501.11411/) (2025)
- [Combinatorial Optimization for All: Using LLMs to Aid Non-Experts in Improving Optimization Algorithms](https://mlsanity.com/paper/2503.10968/) (2025)
- [Large Language Models for the Automated Analysis of Optimization Algorithms](https://mlsanity.com/paper/2402.08472/) (2024)
- [The Impact of Persona-based Political Perspectives on Hateful Content Detection](https://mlsanity.com/paper/2502.00385/) (2025)

## Built on by (most cited first, 1 of 1)

- [From Hand-Crafted to LLM-Based Variation Operators in Metaheuristics: A Tutorial](https://mlsanity.com/paper/2609.31649/) (2026)

## Abstract (arXiv)

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.