acceptodds
Under review as a conference paper at ICLR 2027

Think in Strategies, Act with Tools: Traceable Agentic Optimization for Combinatorial Problems

Abstract

Optimization by PROmpting (OPRO) directly leverages Large Language Models (LLMs) to generate candidate solutions through natural-language prompting. However, OPRO’s optimization process is difficult to track, which prevents LLMs from capturing useful information accumulated over previous iterations, thereby limiting solution quality. To address this limitation, we propose a Tool-Augmented Strategic Agent (TASA) which summarizes and exploits trajectory to improve solution quality. Specifically, TASA plans the strategy for each step based on the optimization trajectory, which decomposes the optimization process into traceable strategy selections. Moreover, we leverage LLM to construct problem-specific tools and introduce a strategy-guided adaptive tool planner, which efficiently utilizes the information of trajectory to update solutions. We establish local convergence under persistent exploration and evaluate the complete framework under a shared candidate-evaluation budget. The results support its solution quality and the traceability of strategy-guided search.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Tool-Augmented Strategic Agent, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_WW1wOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper focuses on combinatorial probelm optimaziation by LLMs. Specifically, the paper propose a Tool Augmented Strategic Agent (TASA) to leverage LLM to generate tools and as a strategy-guided adaptive tool planner. Moreover, the LLM can utilize previous optimization trajectory (e.g. tool calls or strategies) instead of just candidate solutions for next planning. Experimental results across diverse combinatorial optimization problems demonstrate that TASA not only makes the optimization process traceable but also improves solution quality.

Critical strengths
  1. The "solutions without intent" traceability pain of OPRO-style optimization is important but rarely formalized; the strategy–tool two-layer decoupling is clean and interpretable (Figure 1), making the optimization process inspectable in principle.
  2. The problem setup (Sec. 3.1) and algorithm description are clean; Eqs. (4), (5), (9) are specified concretely enough to reimplement.
Critical weaknesses
  1. Ablation for the LLM strategy planner. The Table 1 gains may come entirely from the tool library plus the adaptive scheduling of Eqs. (4)–(5); CB's strong results on KP/TSP — with no LLM and no tool library — already hint at this competing explanation. I suggest the author complement additional experiments: (a) a fixed-rotation or rule-based strategy controller consuming the same trajectory summary s_k; (b) a no-strategy variant running the planner over all tools; (c) LLM-built library vs. a human-curated standard operator library. Without these, the title-level claim "think in strategies" can be neither confirmed nor falsified.
  2. Cost Analysis. TASA's tool construction, strategy-planning LLM calls, and any internal multi-update search inside a tool are all free, while every baseline sample is billed. A polish tool running a full 2-OPT sweep consumes far more than one objective evaluation without being counted. In effect, "shared budget" means "TASA's internal computation is free." Please switch to counting total objective-function evaluations (including intra-tool ones), or report wall-clock / LLM-call / total-evaluation ledgers side by side, with per-task totals and intra-tool operator statistics.
Questions for authors

See my questions in weakness.

Reviewer_GqU5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes TASA, a tool-augmented agentic framework for combinatorial optimization. Instead of directly generating candidate solutions, an LLM selects optimization strategies based on historical search trajectories, while an adaptive tool planner executes problem-specific operators. The authors evaluate the method on eight combinatorial optimization problems and report competitive performance against several LLM-based and traditional optimization baselines.

The problem is relevant, and the empirical results are encouraging. However, I have several significant concerns.

  1. Limited methodological novelty. The framework primarily combines well-established ideas, including adaptive local search, exploration–exploitation, trajectory-based feedback, and LLM-guided tool selection. The four proposed strategies—rebuild, repair, polish, and escape—closely resemble standard operations in metaheuristic optimization. The tool-selection mechanism is also a relatively straightforward variant of epsilon-greedy exploration with historical reward statistics. The paper does not sufficiently establish what is fundamentally new beyond integrating these existing ideas.

  2. Inadequate comparisons with established combinatorial optimization algorithms. Although the paper evaluates several traditional baselines, these are largely generic methods such as random search, Bayesian optimization, genetic algorithms, and combinatorial bandits. For the eight classical optimization problems considered, many sophisticated algorithms already exist, including specialized local search, large-neighborhood search, tabu search, simulated annealing, and problem-specific heuristics. The paper does not convincingly demonstrate that TASA is competitive with these established methods. The inclusion of RefSolver is helpful, but its exact configuration and computational budget are unclear from the main paper.

  3. Questionable fairness of computational budgets. All methods are limited to 60 candidate evaluations, but a single TASA tool invocation can perform multiple optimization operations. Consequently, the number of candidate evaluations does not necessarily reflect the actual computational effort. The paper explicitly acknowledges that tool computations and LLM calls differ across methods. Without comparisons under matched wall-clock time or computational budgets, the reported performance advantages are difficult to interpret.

  4. Insufficient isolation of the LLM's contribution. The framework relies heavily on predefined optimization strategies and executable operators. It is unclear whether the LLM's strategy planning provides substantial benefits over conventional rule-based or adaptive heuristic selection. The existing ablations examine tool-selection policies and feedback granularity, but do not adequately compare LLM strategy planning against a carefully designed non-LLM strategy controller using the same tools.

  5. Limited theoretical contribution. The local convergence result in Section 3.5 follows from finite feasible search spaces, strict improvement, and an assumed persistent positive probability of generating an improving solution. This is a standard argument in stochastic local search. More importantly, the paper does not establish that the proposed LLM strategy planner and tool-selection mechanism actually satisfy the persistent exploration assumption. Consequently, the theoretical result provides limited insight into the practical convergence behavior of TASA.

  6. Limited experimental robustness. The experiments use only three random seeds and a budget of 60 candidate evaluations. This is insufficient to establish reliable performance across large and challenging combinatorial optimization instances. More extensive evaluations over problem sizes, computational budgets, and independent runs would strengthen the conclusions.

Overall, the paper addresses an interesting problem and presents promising empirical results. However, the limited methodological novelty, insufficient comparisons with state-of-the-art combinatorial optimization algorithms, and potentially unfair computational budget comparisons substantially weaken the contributions. I am not convinced that the experiments establish a meaningful advantage over existing optimization methodologies.

Critical strengths
  1. Broad applicability. The framework is evaluated across eight combinatorial optimization problems with different structures and constraints.

  2. Promising empirical performance. TASA achieves competitive solution quality across the benchmarks, suggesting that trajectory-guided tool selection can be useful in practice.

Critical weaknesses
  1. Insufficient comparisons with established optimization algorithms. The paper does not demonstrate competitiveness against strong, problem-specific combinatorial optimization heuristics.

  2. Limited novelty and questionable computational fairness. The method mainly integrates established optimization strategies, while the fixed candidate-evaluation budget does not account for potentially substantial differences in tool-execution costs.

Questions for authors
  1. Can the authors compare TASA against established problem-specific optimization algorithms, such as large-neighborhood search, tabu search, and other competitive heuristics, under matched computational budgets?

  2. How much computation is performed within each tool invocation? Can the authors report wall-clock time and total computational costs for all methods?

  3. Does LLM-based strategy planning outperform a non-LLM adaptive strategy controller using exactly the same tool library and evaluation budget?

  4. How does performance change with larger problem instances, more optimization iterations, and additional independent runs?

Reviewer_Ui4WOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces TASA, an LLM-driven framework for combinatorial optimization. Rather than having the LLM generate candidate solutions directly, as OPRO does, TASA uses it to choose a high-level search strategy (rebuild, repair, polish, or escape) by looking at the optimization trajectory so far. Each chosen strategy is then carried out by two components. The first is a problem-specific tool library, which the LLM builds by combining a set of registered primitive operators. The second is a bandit-style planner that picks tools according to their past improvements and how long they have stagnated. The authors also give a local convergence analysis. They evaluate TASA on eight combinatorial problems against twelve baselines, with every method limited to the same budget of 60 candidate evaluations.

Critical strengths
  1. The paper applies core components of general LLM agents, such as planning, tool use, and memory of past actions, to combinatorial optimization problem.

  2. The framework is applied to eight different combinatorial problems and finds feasible solutions on all of them.

Critical weaknesses
  1. The introduction motivates TASA solely by contrast with OPRO’s untraceable generation. However, EoH, already a baseline in Table 1, shares essentially the same motivation. What is the key difference between TASA and such methods, and why is this not addressed in the introduction?

  2. (continued from weakness 1) The motivation in the introduction (OPRO’s untraceable generation) supports the trajectory recording and strategy planning, but not the tool library and tool planner, which are introduced without clear justification. The performance gains may largely come from the tools, so the link between the stated motivation and the results is unclear.

  3. The need for the convergence analysis in Sec. 3.5 is unclear. It relies only on elitism and Assumption 4, which are not derived from TASA’s design. Simple baselines such as RandSearch or an elitist GA also have similar, or even global, convergence guarantees under similar conditions. What does this result show about TASA specifically?

  4. All experiments use a single LLM (Qwen-Plus). It is unclear whether the results hold with other LLMs.

  5. Each task uses a single fixed instance size. There is no analysis of how TASA behaves as problem size or constraint difficulty increases.

Questions for authors

What registered primitive operators are provided for each problem, and how much does the LLM-generated archetype actually change the final tool library (e.g., the ratio of bound, corrected, pending, and rejected archetypes)?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.