Technical Summary: Behavior and Representation in Open-Weight LLMs for Combinatorial Optimization

Problem Statement

Combinatorial Optimization (CO) relies heavily on manual, expertise-driven processes for algorithm development and selection. While Machine Learning (ML) has begun to integrate into this domain, the internal representational capabilities of Large Language Models (LLMs) regarding CO problem structures remain largely unexplored. Existing studies primarily assess the functional performance of LLMs (e.g., generating heuristics or code) without investigating whether their internal representations capture meaningful information about problem instances or algorithmic behavior.

This study addresses the gap between observable competence and latent understanding in LLMs. It investigates whether frozen, open-weight LLMs encode structural and numerical information about Combinatorial Optimization Problems (COPs) that can be leveraged for downstream tasks. Specifically, the research distinguishes between information that can be explicitly recovered through direct prompting and information that is implicitly encoded within hidden layers, even if not accessible via generation.

Methodology

The authors propose a unified experimental framework combining Direct Querying and Probing analyses across four benchmark problems: Bin Packing (BPP), Graph Coloring (GCP), Jobshop Scheduling (JSP), and Knapsack Problem (KP).

1. Experimental Setup

• Models: Five open-weight LLMs ranging from 3B to 120B parameters, including the Llama instruct family (3B, 8B, 70B) and the gpt-oss reasoning family (20B, 120B).
• Data: A stratified 5% subset of benchmark instances from prior Instance Space Analysis (ISA) studies, preserving coverage across problems, feature complexities, and algorithm portfolios.
• Representations: Instances were presented in three formats: Standard (structured text), Code-like (MiniZinc), and Natural Language.
• Constraints: No task-specific fine-tuning was performed; models were used "off-the-shelf" to assess intrinsic representations.

2. Direct Querying (Explicit Recovery)

Models were prompted to extract specific instance features (e.g., node counts, graph density, average weights) directly from the input text.

• Prompt Variants:
  • Standard: Direct request for a numeric value in JSON.
  • Chain-of-Thought (CoT): Request for a reasoning trace followed by the value.
  • Native Reasoning (gpt-oss): Utilization of the model's internal reasoning channel via the Harmony interface.
• Evaluation: Predicted values were compared against ground-truth values computed by handcrafted extractors using metrics like Mean Absolute Error (MAE) and the proportion of predictions within 1% of the truth.

3. Probing (Implicit Decodability)

To assess latent representations, the authors extracted hidden-layer activations from the final layer of the models.

• Pooling: Activations were pooled using mean, max, and last-token strategies.
• Probes: Supervised models (Ridge regressors, MLPs, LightGBM) were trained on these pooled vectors to predict instance features (regression) or the best-performing algorithm for an instance (classification).
• Goal: To determine if feature information is linearly or non-linearly decodable from the latent space, independent of the model's generative output.

4. Algorithm Selection

The probing framework was extended to a per-instance algorithm selection task. LLM-derived embeddings were used as inputs to classifiers to predict the optimal algorithm from a portfolio, with performance compared against baselines using handcrafted and ISA-based features.

Key Contributions

1. Unified Framework: Introduced a methodology to jointly evaluate explicit feature extraction (querying) and latent representation analysis (probing) for CO.
2. Scale and Reasoning Analysis: Validated the framework across five models (3B–120B) and analyzed the impact of Chain-of-Thought prompting, revealing its strong dependence on model scale.
3. Dissociation of Signals: Provided the first large-scale evidence that explicit retrieval and latent encoding are distinct properties; models may fail to generate a correct value while still encoding that information in hidden states.
4. Surrogate Descriptors: Demonstrated that LLM hidden-layer representations can serve as effective surrogate descriptors for algorithm selection, achieving predictive power comparable to traditional handcrafted features.
5. Reproducibility: Released the dataset, code, and prompts to foster further research at the intersection of LLMs and optimization.

Key Results

Direct Querying Performance

• Feature Complexity: Models reliably recover simple, directly extractable features (e.g., counts) but struggle significantly with features requiring structured computation or aggregation (e.g., averages, ratios).
• Model Scale: Scaling improves performance for low-complexity features but yields diminishing returns for high-complexity features.
• Chain-of-Thought (CoT): The effect of CoT is non-monotonic and scale-dependent. It degrades performance on small models (3B), offers selective benefits on intermediate models (8B), and consistently improves performance on large models (70B). However, it always increases computational cost.
• Failure Modes: Reasoning-oriented models (gpt-oss) exhibit "calibrated abstention," frequently returning null when computation is unreliable, whereas Llama models tend to produce "over-confident hallucinations" (incorrect but valid-looking numbers).

Probing and Latent Encoding

• Latent vs. Explicit: A consistent gap exists between explicit recovery and latent decodability. Probing often achieves higher accuracy than direct querying, particularly for complex features, indicating that relevant information is present in the hidden states but not accessible via generation.
• Representation Robustness: The predictive signal in latent representations is robust to variations in input representation (Standard vs. Natural Language vs. Code-like) and pooling strategies.

Algorithm Selection

• Predictive Parity: LLM-derived embeddings achieved predictive accuracy in algorithm selection comparable to traditional handcrafted and ISA-based features across all five models.
• Classifier Dependence: The choice of downstream classifier (e.g., LightGBM vs. Logistic Regression) had a more significant impact on performance than the specific source of the representation (LLM vs. Handcrafted).
• No Systematic Advantage: No robust evidence was found that ISA-based features systematically outperform LLM-derived representations, nor vice versa.

Significance and Claims

The paper claims that LLMs possess a functional asymmetry between their explicit reasoning capabilities and their internal representations. While LLMs are not yet reliable replacements for exact, handcrafted feature extractors due to high computational costs and unreliability in structured computation, their latent representations contain sufficient statistical regularities to act as effective surrogate descriptors.

The authors argue that LLM-derived representations are most valuable in scenarios where:

1. Handcrafted feature engineering is unavailable or too expensive to design.
2. Instances arrive in heterogeneous or non-standard formats.
3. A problem-agnostic instance descriptor is needed before specific feature engineering is possible.

The study concludes that while LLMs do not currently "compute" features in the deterministic sense required for exact optimization pipelines, their internal states encode a signal that is highly predictive of algorithmic performance, bridging the gap between raw instance data and algorithm selection without the need for manual feature design.