Scaffolding or Decoding Tax? Disentangling Structure, Length, and Noise in Transformer-based Boolean Reasoning

Large Language Models (LLMs) have demonstrated strong capabilities in solving realworld logical problems. It is commonly assumed that, compared to formal logical languages,natural language increases the computational burden on Transformers due to its inherentambiguities and structural redundancy. However, our controlled experiments suggest a morenuanced picture. We find that simple natural language structures can act as useful ”thinkingtokens,” supporting the reasoning capacity of Transformers. The model’s predictive accuracydeclines primarily when the natural language becomes highly complex and unstructured.To systematically investigate this phenomenon, we construct a dataset of Boolean logicAbstract Syntax Trees (ASTs) with varying levels of natural language complexity and trainmulti-layer Transformers to solve them. Our preliminary mechanistic analysis suggests thatsimple linguistic structures may help the Attention mechanism capture the relationshipsbetween Boolean operators. In contrast, complex and noisy redundant words do not appear to provide the same scaffolding benefit, and are associated with a greater reliance ondeeper Feed-Forward Network (FFN) layers to process the logic. Overall, our study providescontrolled evidence for the role of natural language structure in Transformer-based logicalreasoning.