Abstract
Natural-to-Formal (N2F) conversion is a critical task for Large Language Models (LLMs), yet it remains unclear whether their success stems from genuine logical reasoning or pattern matching of familiar languages. This paper introduces the DEDC (Decoupled Evaluation of LLMs’ Decomposition and Composition) framework to isolate two core cognitive processes: decomposition (inferring the meaning of symbolic primitives from examples) and composition (assembling those primitives into complex structures). By testing models on a novel synthetic language, we reveal a significant "intelligence gap": LLMs excel at assembly when definitions are provided but struggle to deduce meanings from context, particularly when symbolic names contradict their functional roles.
Introduction
The ability to translate natural language instructions into formal code—such as SQL, Python, or domain-specific languages—is a cornerstone of modern AI utility. While current LLMs demonstrate impressive proficiency in common programming languages, their performance is often buoyed by the vast amounts of similar code seen during pre-training. This raises a fundamental question: do LLMs possess the underlying "reasoning muscles" to handle entirely unfamiliar symbolic systems?
To address this, researchers from Peking University developed the DEDC framework. This framework treats N2F conversion as a two-step process. First, the model must perform Decomposition, analyzing few-shot examples to map natural language concepts to symbolic "primitives." Second, it must perform Composition, logically combining these primitives to solve novel, complex problems. By decoupling these steps, the researchers can pinpoint exactly where the reasoning chain breaks down.
The DEDC Framework
The core of the DEDC methodology is a comparative evaluation strategy using two distinct prompt settings:
- $P_{dc}$ (Decomposition + Composition): The model is provided only with a few examples of (Natural Language, Formal Expression) pairs. It must autonomously deduce the function of each primitive before generating a solution for a new query.
- $P_c$ (Composition Only): The model is provided with an explicit "cheat sheet" or documentation defining every primitive. This removes the need for deduction, allowing the researchers to measure the model's pure assembly logic.
By comparing the performance in these two settings, the framework derives two key metrics: $D_c$ (the composition defect, representing errors in assembly) and $D_d$ (the decomposition defect, representing errors in deducing meanings).
Experimental Setup
The study utilizes a synthetic language designed for tabular reasoning, consisting of 10 distinct primitives (e.g., f0 for filtering, f3 for finding a maximum value). Expressions are represented as Directed Acyclic Graphs (DAGs) to ensure structural complexity and to prevent models from relying on simple linear patterns.
To test these capabilities, the researchers curated a benchmark of 323 samples. These samples were generated semi-automatically by identifying six base graph types and populating them with valid function combinations. Each sample includes a natural language question, a multi-step formal expression, and the underlying graph structure. The dataset and associated code have been open-sourced to facilitate further research into LLM systematicity.
Key Results and Analysis
The study evaluated several state-of-the-art models, including GPT-4o, Claude-3.5-Sonnet, DeepSeek-2.5, Mistral-Large, and Llama-3.1-405B. Several critical insights emerged:
1. Decomposition is the Primary Bottleneck
Across the board, the error rate attributed to decomposition ($D_d$) was significantly higher than the error rate for composition ($D_c$). While models are relatively competent "assemblers" when given clear instructions, they are much less effective as "detectives" tasked with uncovering the rules of a new system from observation alone.
2. The "Semantic Trap"
LLMs exhibit a heavy reliance on the linguistic priors of function names. In a "Cross-mapping" experiment, researchers renamed functions to be counter-intuitive (e.g., naming a "find maximum" function bottom_k). In these scenarios, model performance plummeted. Rather than following the logic demonstrated in the few-shot examples, the models often defaulted to the misleading literal meanings of the names. For some models, the decomposition defect ($D_d$) spiked by over 30% under these conditions.
3. Model Rankings
Claude-3.5-Sonnet emerged as the top performer, achieving the highest overall accuracy ($P_{dc}$ of 91.02%) and the lowest decomposition defect ($D_d$ of 7.74%). While most top-tier models showed strong composition skills (errors < 10% when definitions were provided), Claude demonstrated a superior ability to learn from context without being misled by symbolic labels.
4. Error Taxonomy
The researchers identified six recurring error types that plague LLMs in N2F tasks. These include "Primitive Fiction" (hallucinating non-existent functions) and "Variable Misuse" (failing to correctly pass intermediate steps through the DAG structure).
Conclusion and Future Work
The DEDC framework highlights a fundamental gap in LLM reasoning: a reliance on surface-level semantics over functional evidence. While LLMs are proficient at recombining known elements, their ability to systematically deduce and apply new symbolic rules is fragile.
Future improvements in N2F conversion will likely require training methodologies that encourage "name-invariance." By forcing models to focus on the functional mappings shown in context rather than the names of the symbols themselves, researchers may be able to build AI systems that are more robust, adaptable, and capable of true logical deduction in unfamiliar domains.
Summary updated