# Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 19 Aug 2026.

## Builds on (most cited first, 13 of 13)

- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)
- [Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models](https://mlsanity.com/paper/2408.02442/) (2024)
- [TRANX: A Transition-based Neural Abstract Syntax Parser for Semantic Parsing and Code Generation](https://mlsanity.com/paper/1810.02720/) (2018)
- [COLLIE: Systematic Construction of Constrained Text Generation Tasks](https://mlsanity.com/paper/2307.08689/) (2023)
- [ConstraintLLM: A Neuro-Symbolic Framework for Industrial-Level Constraint Programming](https://mlsanity.com/paper/2510.05774/) (2025)
- [Logic.py: Bridging the Gap between LLMs and Constraint Solvers](https://mlsanity.com/paper/2502.15776/) (2025)
- [Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization](https://mlsanity.com/paper/2602.02188/) (2026)
- [R-ConstraintBench: Evaluating LLMs on NP-Complete Scheduling](https://mlsanity.com/paper/2508.15204/) (2025)
- [SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling](https://mlsanity.com/paper/2608.00991/) (2026)

## Abstract (arXiv)

Combinatorial scheduling poses a significant challenge for language models, requiring them to identify feasible solutions within exponentially large search spaces while satisfying complex constraints. This challenge is especially pronounced in resource-constrained settings, where larger language models are impractical and selection is limited to smaller models which often fail to preserve feasibility when scheduling directly from natural language. To address these limitations, we introduce SDDL, a neuro-symbolic framework that translates natural-language scheduling problems into compact, solver-aligned representations of tasks, resources, constraints, and objectives, while delegating low-level modeling and search to a deterministic compiler and external solver. On a 300-instance, multi-family subset of scheduling problems, SDDL improves independently verified feasibility for every resource-constrained model tested. The two strongest SDDL configurations reach 55.3% and 28.3%, up from direct-generation baselines of 23.7% and 1.3% and solver-code baselines of 21.7% and 7.0%, with a 0.0% median optimality gap among feasible schedules. By expressing problem structure rather than generating solutions or solver code, SDDL enables smaller models to approach the strongest evaluated direct- and solver-code configurations, including substantially larger frontier models.