Investigating the (De)Composition Capabilities of Large Language Models in Natural-to-Formal Language Conversion (2025)

Abstract: Humans have strong capabilities of decomposition and composition in natural-to-formal language conversion (N2F) when faced with an unfamiliar formal language, and can easily cope with compositional gaps and counter-intuitive symbolic names. To investigate whether large language models (LLMs) have this set of basic capabilities in N2F, we propose the STD framework. This framework semi-automatically performs sample and task construction, allowing decoupled evaluation of the set of decomposition and composition capabilities of LLMs in N2F. Based on this framework, we evaluate and analyze the most advanced LLMs, and the main findings include that: (1) the LLMs are deficient in both decomposition and composition; (2) the LLMs show a wide coverage of error types that can be attributed to deficiencies in natural language understanding and the learning and use of symbolic systems; (3) compositional gaps and counter-intuitive symbolic names both affect the decomposition and composition of the LLMs. Our work provides a new perspective for investigating the basic capabilities of decomposition and composition of LLMs in N2F. The detailed analysis of deficiencies and attributions can help subsequent improvements of LLMs.

## introduction a formal language @xcite ) is a symbolic system formed by a set of symbolic primitives that can be combined into expressions to convey specific meanings according to certain rules. common formal languages include formal logic @xcite , structured query language @xcite , formal syntax @xcite , etc. formal languages are often used to more accurately convey the meaning embedded in natural language texts, resulting in many natural-to-formal language conversion (n2f) tasks in the field of natural language processing, such as syntactic-semantic parsing @xcite , structured query language generation @xcite , logical expression generation for symbolic reasoning @xcite , etc. due to the wide coverage of the training corpus, large language models (llms) have developed, to some extent, the capability of n2f on a variety of common formal languages @xcite . however, it is an under-explored question whether llms have developed basic capabilities to cope with arbitrary new formal languages for n2f. when confronted with an unfamiliar formal language, the capabilities of decomposition and composition is necessary to accomplish n2f: after seeing some samples containing expressions in formal language and their corresponding meanings in natural language, llms need to be able to decompose the meanings of symbolic primitives from the samples (decomposition) and combine the symbolic primitives into new expressions with specific meanings @xcite . in addition, to achieve generalized and robust n2f, llms need to have the capability to cope with the following situations during decomposition and composition: (1) there are compositional gaps between the expressions to be combined and the expressions seen, and (2) there are names of symbolic primitives that would not normally correspond to the actual meanings of the symbolic primitives (counter-intuitive). investigating whether llms have this set of capabilities is important from both practical and cognitive perspectives @xcite . from a practical perspective, this set of capabilities is necessary for llms to accomplish n2f under incontext learning @xcite , especially when confronted with uncommon formal languages and complex situations. from a cognitive perspective, the intelligence reflected in this set of capabilities is one of the necessary conditions to con-figure 1 : an illustration of the sample and task construction of the dedc framework. an example of the sample construction is shown on the left. on the right is an illustration of the task construction when the sample on the left is used as the test sample. to solve this problem, we propose the dedc framework. this framework constructs samples and tasks in a semi-automatic manner, allowing decoupled evaluation of llms' decomposition and composition capabilities in n2f. in addition, this framework allows for easy setting adaptations to evaluate the capabilities of llms to cope with compositional gaps and counter-intuitive symbolic names in n2f. based on the dedc framework, we conduct a comprehensive evaluation and analysis of the above-mentioned decomposition and composition capabilities of existing llms. we also conduct a detailed analysis of the specific error behaviors of the llms in n2f to provide more insights into the attributions of errors. ## base evaluation in this section, based on the dedc framework, we perform a base evaluation (i.e., no additional settings) of the llms and analyze the results. ## evaluations with additional settings in the dedc framework, additional settings can be added to evaluate the capability of llms to cope with a variety of situations and estimate the effects of the additional settings on the decomposition and composition of the llms. assuming that the performance of a llm on the task with and without demonstration of primitives under setting s is p s c and p s dc respectively, we estimate the effect of the setting by comparing the performance with that of the base evaluation: in this section, we consider settings related to compositional gaps and counter-intuitive symbolic names. ## conclusion in this work, we propose the dedc framework. this framework performs sample and task construction semi-automatically, allowing decoupled evaluation of the decomposition and composition capabilities of llms in n2f. in addition, this framework allows for the evaluation of the capability of llms to cope with compositional gaps and counterintuitive symbolic names. based on this framework, we evaluate and analyze the most advanced llms. from the results we find that: (1) the llms are deficient in both decomposition and composition, and the deficiencies are more severe in decomposition;