acceptodds
Under review as a conference paper at ICLR 2027

ASTOR: Benchmarking and Improving Autoformulation for Soft-Constraint Optimization with a Formal Grammar

14 views

Abstract

Real-world decision problems combine two qualitatively different kinds of constraints: requirements that must be satisfied, called hard constraints, and preferences that can be violated, called soft constraints. Because these problems are often posed to decision-makers in natural language, large language models offer a natural tool for assisting with their solution. This has given rise to autoformulation, which focuses on using LLMs to translate natural-language descriptions of decision problems into executable mathematical optimization models. However, this research often neglects soft constraints like those proposed by consumers, managers, and planners, despite the fact that many practical problems require modeling them explicitly. We introduce ASTOR, an inference-time framework that maps a natural-language decision problem to a grammar-guided abstract syntax tree (AST) before deterministically compiling the resulting representation into executable optimization code. The language generated by the grammar is provably adequate for optimization problems with hard and soft constraints. We also introduce SoftOR, a unified benchmark of natural language problems which focuses on soft constraint formulations. On SoftOR, ASTOR achieves the best aggregate accuracy among comparable single-request and multi-agent LLM methods while remaining competitive on standard autoformulation benchmarks, which are dominated by hard constraints.

Primary area:
optimization
Keywords:
large language models, optimization, autoformulation, soft constraints, formal grammar, benchmarking

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_VyxaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ASTOR, a grammar-guided framework for translating natural-language optimization problems into executable formulations. It also introduces SoftOR, a 355-instance benchmark for weighted and lexicographic soft constraints. ASTOR achieves 88.5% accuracy, outperforming the strongest baseline at 84.8%.

Critical strengths
  1. SoftOR addresses an important gap in evaluating soft-constraint optimization.
  2. ASTOR provides a clear, training-free framework with promising improvements, particularly on TravelPlanner.
Critical weaknesses
  1. Ambiguity in weighted evaluation. Qualitative preference rankings do not uniquely determine numerical weights or optimal solutions. Evaluating against hidden original weights may penalize valid formulations.
  2. Limited ablation coverage and generalizability. The ablations cover only 45 soft-constraint instances, including just two weighted-penalty cases. ASTOR does not consistently outperform Codegen across backbones. Moreover, Gemini 3.8 Flash is evaluated only on Nurse Rostering, and newer GPT models are not included.
Questions for authors
  1. If different numerical weights preserve the same qualitative preference ordering but yield different optimal solutions, how can the hidden-weight evaluation justify a unique gold answer?
  2. Given the relatively modest benchmark size and reported API costs, could the authors extend the key ablations to the full 355-instance SoftOR benchmark and conduct full-benchmark comparisons using Gemini 3.8 Flash and newer GPT models?
2 comments

1. Investigating and ablating weights on Nurse Rostering Our reason for withholding the numerical weights was to study what happens when a natural-language problem describes preferences without specifying their exact penalties. In that setting, the model has to infer the weights as part of formulating the problem. We wanted to evaluate this additional challenge as a part of the modeling task. In fact, we had felt that giving the weights could be potentially too advantageous to the more sophisticated methods, so we withheld them. However, we actually ran experiments both with and without explicitly given weights all along, and we are happy to now report both.

Here in this revision, we now also report the complementary with-weights experiment: we explicitly provided the numerical weights in the prompt for all 15 Nurse Rostering instances for each route. With the weights given, ASTOR achieves the highest observed accuracy, solving 14 of 15 instances (93.3%), followed by CoE at 13 of 15 (86.7%). The full results are below.

MethodCorrect / 15Accuracy with weights given
ASTOR14/1593.3%
CoE13/1586.7%
CoT12/1580.0%
ORThought12/1580.0%
Codegen8/1553.3%
OptiMUS8/1553.3%
Direct0/150.0%

These results can also be found in Table 13 within Section A.4 of the appendix.

2-a. Extending the ablations. Thank you for this suggestion. In this revision, we have now conducted all the ablations on all 355 instances of SoftOR, which includes testing other baseline methods and similar variantsto isolate the gains produced by ASTOR, as now reported in Figures 5 and 6 and Tables 6 and 7. To address the JSON format, we include OptiMUS 0.3 as a baseline in our main experiment, which also uses a structured JSON as an intermediate optimization-model representation. ASTOR achieves more than double the performance of this baseline. To address the deterministic compiler component, we include an ablation setting that uses an LLM (Gemini 3.8 Flash, the same as our new main experiment) to compile from JSON to gurobipy, and we see that this reduces performance by 4.8 percentage points. To isolate the contribution of explicitly constructing a formal AST from that of grammar-based guidance alone, we include a grammar-guided code-generation ablation, which reduces performance by 7.6 percentage points. This addition complements our prior ablation of the grammar-guided direct-solve baseline, which reduces performance by 20.0 percentage points. We also include ablations on the temperature setting of the LLM backbone to test ASTOR’s stability under varied outputs, and we see that its accuracy remains stable. The ablations suggest ASTOR’s gain comes from the JSON-format of the formal grammar and deterministic parsing. In Figure 11d we can see that the human readable guidance mostly saves token cost. See Figures 5 and 6 and Tables 6 and 7.

2-b. Backbone coverage and generalizability. In this revision, we also reran all experiments so that they are evaluated in a setting that is both unified and equipped with the latest capabilities All of our main experiments here now use the new LLM backbone Gemini 3.8 Flash. In this run, we see that ASTOR’s accuracy is statistically significantly higher than all other routes. ASTOR leads (88.5%) compared to Codegen (84.2%) ORThought (85.4%), CoE (85.6%), CoT (83.1%) , Direct (63.9%), and OptiMUS (41.7%). To address the need for modern multi-agent routes, we also ran SAC-Opt (ICML 2026), a multi-agent method on all 355 instances of SoftOR using Gemini 3.8 Flash. We observed that about 38 of its responses exceeded Gemini’s max token limit, but on the instances that it did produce an answer, it had an accuracy of 21.5%. We also reran the experiment on ASTOR and its top competitors using GPT 6 as the LLM backbone, and we see that under this setting ASTOR is statistically significantly better than all methods except for Codegen, which it still outperforms. ASTOR leads (87.6%) compared to Codegen (86.5%), ORThought (84.5%), CoE (84.5%), and CoT (83.9%).

In total, for this revision we newly ran all 355 instances of SoftOR through eight routes for the main experiment on Gemini 3.8 Flash, 11 different ASTOR ablation settings, and five routes for the new LLM backbone ablation on GPT-6. Please see Tables 3,6,7 and Figures 5,6.

Thank you for the detailed response and additional experiments. After careful consideration, I have decided to maintain my original rating.

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

The paper explores how autoformulation of optimization problems with language models does for soft constraints and preferences and contains two main contributions: astor and softor. Astor is a method for translating natural language into a grammar-guided AST in JSON for formulating an optimization problem, with a deterministic compiler that compiles the JSON formulation to gurobipy. Softor is a benchmark focused on soft constraint optimization problems. The benchmark contains two types of soft constraints. The first one is lexicographical one, where the preferences are grouped by preference tiers, and improvements to lower tiers cannot make up for violations at the higher tiers. The second is weighted penalty, where each preference that is violated adds a weight cost to the objective. The authors find that astor achieves the highest aggregate accuracy compared to other autoformulation methods on the soft constratined softor benchmark and that it is competitive on hard constraint benchmarks.

Critical strengths

The paper studies a seemingly understudied area of autoformulation, namely soft constraints and the softor benchmark seems to be a useful data point for further optimization autoformulation work. The astor framework with explicit grammar might also be useful, since it is able to achieve comparable performance to multi-agent systems while only requiring one LLM prompt and being 10% cheaper than CoE. The paper contains some useful examples of when astor helps, such as how it almost always gets the priority tiers correct, while baselines often let cost override the priority order. The reproducibility seems strong, with exact prompts and code available.

Critical weaknesses

There could be more ablations on where the benefits of astor come from and there are many confounders. Astor has a different JSON format than other methods, different prompts and has a compiler. Without ablations on each of these, it is hard to tell if the gains in soft constraints come from the new JSON format, or if they simply come from a prompt that is more targeted to soft constrained problems. It would be useful if the authors can more clearly explain how astor differs from previous methods, such as other works that turn JSON into solver code with deterministic code or other LLM approaches to preference modeling. It is not clear how the adequacy theorem actually differentiates the method, since gurobipy is also as expressive and since the grammar doesn't guarantee that the LLM output is correct. The grammar formulation might simply give the astor method more information than previous methods that it needs to be careful about the ranking. Lastly, most results differ by only small margins, meaning it is hard to tell if the results are statistically significantly better.

Questions for authors

The softor benchmark seems novel, but it might need better evidence and more ablations on previous methods or astor, to show where autoformulation methods do well and not on the benchmark. It is less clear that astor is a contribution, so it would be great if the authors can explain in more details how it differs from previous works. It would also be useful if the authors can more clearly break down the gains of astor.

1 comment

In total, for this revision, we evaluated all 355 instances of SoftOR across eight methods for the main experiment on Gemini 3.8 Flash, 11 different ASTOR ablation settings, and five methods for the new LLM backbone ablation on GPT-6 Sol.

Regarding Weaknesses: In response to your points, we have conducted various new ablations on all 355 instances of SoftOR and evaluated additional methods, as reported in Figures 5 and 6 and Tables 6 and 7, to isolate the gains produced by ASTOR. First, to address the JSON format, we now include OptiMUS 0.3 as a baseline in our main experiment, which also uses structured JSON as an intermediate optimization-model representation. ASTOR correctly solves more than twice as many problems as this baseline. To address the deterministic compiler component, we include a new ablation setting that uses an LLM (Gemini 3.8 Flash, the same as in our new main experiment) to compile from JSON to gurobipy, and we find that this reduces accuracy by 4.8 percentage points. To isolate the contribution of explicitly constructing a formal AST from that of grammar-based guidance alone, we include a new grammar-guided code-generation ablation, which reduces accuracy by 7.6 percentage points. This new addition complements our prior grammar-guided direct-solve ablation, which reduces accuracy by 20.0 percentage points. We also include ablations on the temperature setting of the LLM backbone to test ASTOR’s stability under varied outputs, and we find that its accuracy remains stable. The ablations support the contribution of the formal AST representation and deterministic compilation to ASTOR’s gains. This provides evidence supporting the choice of an AST as the intermediate representation and the restriction of LLM use to translation, with deterministic processing elsewhere. We are grateful for your feedback, which prompted these additional evaluations.

We also reran the experiments under a unified setting, all using the newer LLM backbone Gemini 3.8 Flash. In this setting, ASTOR’s accuracy is statistically significantly higher than that of all other evaluated methods. ASTOR leads with 88.5% accuracy, compared to Codegen (84.2%), ORThought (85.4%), CoE (85.6%), CoT (83.1%), Direct (63.9%), and OptiMUS (41.7%). To address the need for modern multi-agent methods, we also evaluated SAC-Opt (ICML 2026), a multi-agent method, on all 355 instances of SoftOR using Gemini 3.8 Flash. We observed that 38 instances reached Gemini’s maximum token limit; excluding those instances, SAC-Opt achieved 21.5% accuracy. We also reran the experiment on ASTOR and its top competitors using GPT-6 Sol as the LLM backbone. In this setting, ASTOR achieves statistically significantly higher accuracy than all other evaluated methods except Codegen, which it still outperforms numerically. ASTOR leads with 87.6% accuracy, compared to Codegen (86.5%), ORThought (84.5%), CoE (84.5%), and CoT (83.9%). See Tables 2, 6, and 7.

Finally, in response to your concern regarding statistical significance and the general benefits of ASTOR, we highlight two changes. First, in the second row of Table 2, we now display the 95% bootstrap confidence interval for the difference in solution accuracy between ASTOR and each baseline method. All of these intervals lie strictly above zero, demonstrating ASTOR’s statistically significant accuracy gains in the main experiment. Second, we identify a new finding in this revision: ASTOR solves five problem instances that no other method solves, and every other correctly solved problem instance is solved by more than one method. Relative to the evaluated baseline approaches from the literature, this shows that ASTOR adds distinct solving capabilities at the problem-instance level while also achieving statistically significant gains in aggregate accuracy in the main experiment.

Regarding Questions: As you noted, one of this paper’s contributions is the new benchmark SoftOR, which remains challenging even for recent LLMs and multi-agent methods. Additionally, we believe that ASTOR contributes both significantly increased accuracy for these soft-constraint optimization problems and a general, flexible framework for formal translation tasks. We provide new evidence of its distinct capabilities on SoftOR in this revision. As discussed in our response to the weaknesses above, ASTOR solves five problems that no other baseline solves, and every other solved problem instance is solved by multiple methods, even after including the two new baselines added in this revision. Thus, ASTOR contributes a capability not exhibited by the evaluated baseline methods. See Table 2.

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

ASTOR addresses soft-constraint modeling, an aspect that has received less attention in the literature than hard-constraint modeling. It uses an abstract syntax tree (AST) as an intermediate representation to translate natural-language descriptions into solver code and solve the resulting optimization problems. To evaluate the proposed approach, the authors introduce a new benchmark featuring soft constraints, weighted-penalty objectives, and lexicographic priorities. Experimental results show that ASTOR outperforms several automatic formulation approaches in terms of solution accuracy and technical error rates.

Critical strengths

Soft-constraint modeling is an interesting research direction in automatic optimization formulation that has received limited explicit attention in the literature. The paper is generally well presented, although some technical details could be clarified. The authors construct a benchmark covering several types of optimization problems involving soft constraints. The experimental results demonstrate that the proposed approach outperforms some simple prompting-based baselines, providing encouraging evidence of its effectiveness. The related work is somehow sufficient covering different approaches in automatic optimization formulation. Representational adequacy is given in appendix as a support of AST soundness in translating the natural language to optimization model.

Critical weaknesses
  1. Insufficient motivation for a specialized benchmark: The paper does not provide sufficient evidence to establish the necessity of developing a dedicated benchmark and approach for soft-constraint modeling. In particular, evaluating existing autoformulation methods on problems involving soft constraints would help demonstrate their limitations and better motivate the proposed approach.

  2. Lack of methodological clarity: The roles of JSON and AST in the proposed framework are not sufficiently clear. Although the appendices provide some partial explanations, a more explicit description of the end-to-end process, from natural-language input to the final solver code and solution, would improve reproducibility and accessibility.

  3. Limited and outdated baselines: The experimental comparisons do not establish ASTOR as a state-of-the-art approach, as the selected baselines are relatively simple and outdated. More recent agentic approaches and stronger LLM backends should be included to provide a more convincing evaluation.

  4. Unclear improvement over existing methods: Although CoE is an early and relatively simple approach, the paper does not demonstrate a clear improvement over it. More comprehensive experiments and analysis are needed to establish the practical advantages of ASTOR.

  5. Limited methodological novelty: The novelty of using an AST as an intermediate representation is not sufficiently established. The paper should better explain the technical advantages of this design over existing intermediate representations and demonstrate its contribution through targeted ablation studies.

Questions for authors

What does “Validate schema, symbols” mean in Figure 1? Is there any chance that the solution value is the same as the optimal value but the constraint preferences are not correct?

2 comments

To address your concerns in order, first, we evaluate existing autoformulation approaches on this benchmark. In addition to the Direct and Codegen baselines, we evaluate CoT (NeurIPS 2022), CoE (ICLR 2024), ORThought (A.I. for Transportation, 2026), and, as two new additions in this revision, OptiMUS 0.3 (ICML 2024) and SAC-Opt (ICML 2026). ORThought, OptiMUS, and SAC-Opt are recent multi-agent methods that produce code, and OptiMUS uses a JSON file, as does ASTOR. We find that ASTOR achieves statistically significantly higher accuracy than all such methods on SoftOR, which we clarify in this revision. Additionally, we report a new finding in this revision: even after including these advanced multi-agent autoformulation methods, ASTOR is the only method that solves SoftOR instances that no other method solves. See Tables 2 and 3.

Second, an end-to-end description of the method is included in Figure 1 and the accompanying text. Please see our response to your Point 5 for further details on ASTOR component ablations, which address various components across the entire pipeline.

Third, we ran new experiments under a unified setting, all using the newer LLM backbone Gemini 3.8 Flash. In this setting, ASTOR’s accuracy is statistically significantly higher than that of all other methods, based on 95% confidence intervals. ASTOR leads with 88.5% accuracy, compared to Codegen (84.2%), ORThought (85.4%), CoE (85.6%), CoT (83.1%), Direct (63.9%), OptiMUS (41.7%), and SAC-Opt (21.5%). We also reran the experiment on ASTOR and its top competitors using GPT-6 as the LLM backbone, and we find that ASTOR is the best-performing method on all benchmark components in this setting. ASTOR leads with 87.6% accuracy, compared to Codegen (86.5%), ORThought (84.5%), CoE (84.5%), and CoT (83.9%). These additions complement our original experiments with Gemini 3.7 Flash as the backbone. See Tables 3, 6, and 7.

Fourth, even with new advanced autoformulation methods included, ASTOR achieves statistically significant accuracy gains over all other methods, including CoE, in the Gemini 3.8 Flash setting, based on 95% confidence intervals. Furthermore, as we mentioned in response to your first point, we identify a distinct contribution in this revision: ASTOR solves five problem instances that no other baseline solves, and every other solved problem instance is solved by multiple methods. See Tables 2 and 3.

Fifth, we conducted new ablations on all instances of SoftOR and evaluated additional methods, as reported in Figures 5 and 6 and Tables 6 and 7, to isolate the gains produced by ASTOR. To address the JSON format, we include OptiMUS 0.3 as a baseline in our main experiment, which also uses a structured JSON representation as an intermediate optimization-model representation. ASTOR correctly solves more than twice as many problems as this baseline. To address the deterministic compiler component, we include an ablation setting that uses an LLM (Gemini 3.8 Flash) to compile from JSON to gurobipy, and we find that this reduces performance by almost 5%, a statistically significant reduction. To isolate the contribution of explicitly constructing a formal AST from that of grammar-based guidance alone, we include a grammar-guided code-generation ablation, which performs worse by almost 8%, a statistically significant reduction. We also include ablations on the temperature setting of the LLM backbone to test ASTOR’s stability under varied outputs, and we find that its accuracy remains stable. In total, for this revision, we evaluated all 355 instances of SoftOR across eight methods for the main experiment on Gemini 3.8 Flash, 11 different ASTOR ablation settings, and five methods for the new LLM backbone ablation on GPT-6.

This paper makes two contributions: the benchmark SoftOR, which remains challenging even for recent LLMs and autoformulation methods, and the method ASTOR, which significantly increases accuracy. Taken together, the new evidence shows that the formal grammar is a flexible tool that can be easily changed or adapted to other formal translation tasks and can be specifically targeted to bespoke optimization tasks involving soft constraints. Additionally, ASTOR’s JSON file and deterministic compilation make errors easier to detect and audit, which is challenging for multi-agent, prompt-based systems.

To address the question, “validate [\] schema, symbols” in Figure 1 denotes a deterministic JSON schema validation step that ensures the JSON conforms to the schema. Since some optima are not unique in SoftOR, it is possible to achieve the same optimal value with a different preference assignment. Just as “Compile” is an action that converts the AST to Gurobi code and “Solve” is an action that produces an optimal solution, “Validate” is an action performed on the schema and generated symbols at the start of the solving pipeline.

Since the deadline is coming up, we wanted to follow up and see if we answered your concerns, and if you have other questions please do let us know.

Comments on the paper

1 comment

Thank you to all of the reviewers for their time and attention to our submission; we feel the paper has been improved significantly in this revision. Among the most notable changes are that we now run the ablations for all 355 SoftOR problem instances, and these studies include 11 different ablations of the ASTOR methodology and another 5 backbone ablations on GPT-6. Furthermore, all the main experiments are now conducted on Gemini 3.8 Flash across all 355 SoftOR instances, including the addition of two new baseline methods from the literature. Through these additions, we also now more clearly demonstrate the benefit of the ASTOR methodology, which we summarize as follow:,

  1. Unique Problem-Solving Coverage: Even with the addition of two strong baselines, ASTOR uniquely solves SoftOR instances that no other method can solve. By contrast, any other correctly solved problem is solved by multiple methods —showing that while existing methods largely overlap in capability, ASTOR solves a distinct class of problems. Thus, we believe that ASTOR makes genuinely novel contributions and adds distinct solving capabilities to the auto-formulation literature.

  2. Statistically Significant Gains: In the second row of Table 2, we now report 95% confidence intervals for the pairwise accuracy differences between ASTOR and every baseline. As evidence of the statistically significant benefit of ASTOR, all of these accuracy differentials are positive (towards ASTOR’s advantage), and none contain 0 within their 95% confidence intervals.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.