AI
Language Models Struggle as Formal Problem Solvers, Study Finds
A new analysis reveals that using LLMs to generate formal code for constraint problems often underperforms direct problem solving, despite promises of greater interpretability.
Recent research has challenged the assumption that large language models excel when tasked with converting problem descriptions into formal mathematical code—a strategy thought to offer clearer reasoning and verifiable solutions. A systematic evaluation across multiple benchmarks and model families paints a more complicated picture.
The Strategy Gap#
The idea behind using LLMs as "formalizers" is appealing: rather than asking a model to reason directly toward an answer, provide a natural-language problem statement and have the model generate executable formal code that an external solver then runs. This approach promises better interpretability and the ability to verify correctness through formal methods. However, the new study finds this method underperforms direct LLM problem-solving in 15 out of 24 tested model-dataset combinations, suggesting the theoretical advantages don't always translate to practice.
What the Research Examined#
Researchers tested the formalization approach across constraint satisfaction problems using 6 different language models and 4 real-world benchmark datasets, with the models generating code in 2 distinct formal languages. The findings consistently showed that as problem complexity increased, LLM formalization ability degraded sharply—mirroring the scaling failures already known to plague end-to-end LLM reasoning.
Why This Matters#
One striking discovery was that LLMs often generate excessive "reasoning tokens"—verbose intermediate steps—that sometimes devolve into hard-coded solutions rather than genuine formal abstractions. Even though the space of possible formal programs is vastly smaller than raw search spaces, the models still struggle to produce correct specifications. This suggests that simply giving a model a smaller search space doesn't automatically unlock better performance if the underlying reasoning capability isn't there.
The work underscores a fundamental challenge: converting natural language into formal specifications remains difficult for LLMs, and the promise of formalization as a shortcut to symbolic reasoning may need realistic recalibration.
