A Reality Check of Language Models as Formalizers on Constraint Satisfaction Problems
Rikhil Amonkar Ceyhun Efe Kayan Qimei Lai, {rikhil.amonkar|harry.zhang @drexel.edu} · 2025
Read A Reality Check of Language Models as Formalizers on Constraint Satisfaction Problems by Rikhil Amonkar Ceyhun Efe Kayan Qimei Lai, {rikhil.amonkar|harry.zhang @drexel.edu} (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13252.txt.
Introduction
Rikhil Amonkar and co-authors give language models a reality check as translators of word problems into solver-ready code. Their paper appeared in 2025. The fashionable pipeline has the model write a formal program, then lets an exact solver finish the job. Across four real-life constraint benchmarks, six models, and two formal languages, that pipeline lost to simply letting the model solve directly in fifteen of twenty-four combinations, despite its checkable outputs.
Worse, formalizing degraded with problem complexity just as fast as direct solving. The team caught models burning tokens on solver-like reasoning and sometimes hard-coding answers. The authors say formalization is no free lunch: the translation step itself is where capability leaks, and future work must shore it up.
Catalog record
| CREATOR | Rikhil Amonkar Ceyhun Efe Kayan Qimei Lai, {rikhil.amonkar|harry.zhang @drexel.edu} |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13252
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Reality Check of Language Models as Formalizers on Constraint Satisfaction Problems Rikhil Amonkar Ceyhun Efe Kayan Qimei Lai, {rikhil.amonkar|harry.zhang @drexel.edu} Abstract Recent work shows superior performance when using large language models (LLMs) as formalizers instead of as end-to-end solvers for symbolic reasoning problems. Given the problem description, the LLM generates a formal program that derives a solution via an external solver. We systematically investigate the formalization capability of LLMs on real-life constraint satisfaction problems on 4 benchmarks, 6 LLMs, and 2 types of formal languages. We show that LLM-as-formalizer by no means trivializes the problem but underperforms LLM-as-solver in 15 out of 24 model-dataset combinations, despite the former’s verifiability and interpretability. Although the formalization space is magnitudes smaller than the search space, our scaling analysis shows that LLM-as-formalizer still drastically degrades as problem complexity increases similar to LLM-as-solver. To better understand this limitation, we observe excessive, solver-like reasoning tokens that sometimes lead to hard-coded solutions, highlighting a key challenge for improving LLM-based formalization. 1 1 1 Code: github.com/rikhil-amonkar/llm-csp 1 Introduction Considerable efforts have been dedicated to improving the ability of large language models (LLMs) to solve logical reasoning tasks ( Saxton et al., 2019 ; Clark et al., 2021 ) , primarily in an end-to-end manner involving intermediate chain-of-thought tokens ( Wei et al., 2022 ; Kojima et al., 2022 ) . Despite their strong performance, these LLM-as-solver methods have been shown to lack faithfulness, verifiability, and formal guarantee ( Lyu et al., 2023 ) . To bridge this gap, an emerging line of neuro-symbolic methods use LLMs to translate the natural language problem description into a formal program, from which a solution can be derived using an external solver ( Gao et al., 2023 ; Pan et al., 2023 ; Han et al., 2024 ) . Despite the desirable features above, the reported triumphant performance of formalization predates the advance of large reasoning models (LRMs) that scales reasoning tokens during inference time ( Muennighoff et al., 2025 ; Guo et al., 2025 ) . Most recent work shows the performance comparison between two methodologies remains unclear and debated ( Huang & Zhang, 2025 ; Kagitha et al., 2025 ) , hindering real-life application. We systematically compare these two methodologies on constraint satisfaction problems (CSPs) following existing work that form the backbone of many real-world planning and scheduling systems, including calendar scheduling, trip planning, and meeting planning, in addition to a logic grid puzzle. On these 4 domains, we evaluate 6 state-of-the-art LLMs, including 4 LRMs (DeepSeek-R1, Qwen3-32B, o3-mini-high, GPT-5) and 2 non-reasoning counterparts (DeepSeek-V3, Qwen2.5-32B), both as solvers and as formalizers. To ensure maximal generalizability and fairness of comparison, we consider only one-shot settings with a minimal instruction to generate a solution or a code, but additionally provide formalizers with revision attempts. We consider two formalization targets: free-form Python and specific code to interface a Satisfiability Modulo Theories (SMT) solver. Figure 1: An example of the output for LLM-as-solver (top) and LLM-as-formalizer with two types of formalism (middle and bottom) in a real-life constraint satisfaction task, calendar scheduling. While existing work established the superiority of LLM-as-formalizer , we instead show that it underperforms LLM-as-solver in 12 out of 16 LRM-dataset combinations and 4 out of 8 non-reasoning-LLM-dataset combinations. While many expect LLM-as-formalizer to scale with problem complexity since the formalization space is magnitudes smaller than the search space, our analysis shows that its performance still drastically degrades as problem complexity increases just as LLM-as-solver . We perform a fine-grained error analysis and attribute the anti-climatic performance of LLM-as-formalizer largely to missing constraints and erroneous logic. Despite the comparative token efficiency of LLM-as-formalizer for LRMs, we observe surprising, excessive, solver-like reasoning tokens that sometime lead to hard-coded solutions, likely an artifact of pre-training. Our work suggests multiple future directions spanning performance, robustness, and efficiency of neurosymbolic auto-formalization, which promises verifiability and interpretability. 2 Related Work 2.1 LLM-as-solver LLM-as-solver , also known as informal reasoning or end-to-end reasoning, is a paradigm when one or more LLMs generate optional intermediate tokens and eventually the solution to a logical reasoning problem. As early problem solving ability comes from training, many major LLMs have been trained or evaluated as a solver ( Rajani et al., 2019 ; Brown et al., 2020 ) , while limited to low-complexity, common-sense problems. The introduction of chain-of-thought reasoning made LLM-as-solver feasible in complex tasks such as mathematics and logic puzzles ( Wei et al., 2022 ; Kojima et al., 2022 ; Sel et al., 2024 ; Feng et al., 2023 ) . Follow-up techniques to further improve LLM-as-solver based on chain-of-thought included self-verification ( Weng et al., 2023 ) , self-refine ( Madaan et al., 2023 ) , tree-of-thought ( Yao et al., 2023 ) , self-consistency ( Wang et al., 2023 ) , etc. Despite strong performance, LLM-as-solver has been shown to lack faithfulness, verifiability, and formal guarantees ( Lyu et al., 2023 ; Turpin et al., 2023 ; Stechly et al., 2025 ) . To bridge these gaps, neuro-symbolic methods were introduced to combine LLM-as-solver with formal tools ( Jha et al., 2023 ; Saparov & He, 2023 ) . 2.2 LLM-as-formalizer LLM-as-formalizer is a subset of the above neuro-symbolic methods where LLMs generate neither the solution nor the chain-of-thought towards the solution, but rather translate the natural language problem description to an executable program based on LLM’s ability to generate code. This methodology has been reported to greatly outperform LLM-as-solver in classical planning ( Liu et al., 2023 ; Xie et al., 2023 ; Hao et al., 2025 ) , constraint satisfaction ( Berman et al., 2024 ; Kesseli et al., 2025 ) , mathematics ( Wu et al., 2022 ; Yang et al., 2023 ; Jiang et al., 2023 ) , and general logical reasoning tasks ( Ye et al., 2023 ; Gao et al., 2023 ; Pan et al., 2023 ; Han et al., 2024 ) . Despite the overwhelming report of its success, it has also been shown to be unstable, dependent on the choice of formal language and solver ( Matthew Lam et al., 2024 ; Beiser et al., 2025 ) . 2.3 LLM-as-formalizer vs. LLM-as-solver For effective application, research like ours that systematically compares LLM-as-formalizer and LLM-as-solver is crucial but lacking, especially with the introduction of LRMs, which reported dramatically improved performance on algorithmic tasks where LLM-as-solver used to fail ( Muennighoff et al., 2025 ; Guo et al., 2025 ) . The closest work to ours is Chen et al. (2025) , which did not consider any open-source model or inference-time scaling LRMs, whereas open-source LRMs are our focus. Moreover, their work is an initial investigation where conclusions are surface-level (formalizing is hard) and inconclusive (neither is optimal), while ours is a deep dive resulting in an array of fine-grained, relatively definitive, and somewhat counterintuitive conclusions. The other work that considered both LLM-as-formalizer and LLM-as-solver for LRMs is Kagitha et al. (2025) , which only focuses on classical planning tasks, similarly lacking decisive findings. Calendar Scheduling Trip Planning Meeting Planning Zebra Logic X_{i} start hour s , end hour e day d , city c person p , start s , duration d person p , attribute a