How Transformers Solve Propositional Logic Problems: A Mechanistic Analysis

• URL: http://arxiv.org/abs/2411.04105v3
• Date: Mon, 09 Dec 2024 16:36:34 GMT
• Title: How Transformers Solve Propositional Logic Problems: A Mechanistic Analysis
• Authors: Guan Zhe Hong, Nishanth Dikkala, Enming Luo, Cyrus Rashtchian, Xin Wang, Rina Panigrahy,
• Abstract summary: Large language models (LLMs) have shown amazing performance on tasks that require planning and reasoning.<n>Motivated by this, we investigate the internal mechanisms that underpin a network's ability to perform complex logical reasoning.
• Score: 16.65073455206535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large language models (LLMs) have shown amazing performance on tasks that require planning and reasoning. Motivated by this, we investigate the internal mechanisms that underpin a network's ability to perform complex logical reasoning. We first construct a synthetic propositional logic problem that serves as a concrete test-bed for network training and evaluation. Crucially, this problem demands nontrivial planning to solve. We perform our study on two fronts. First, we pursue an understanding of precisely how a three-layer transformer, trained from scratch and attains perfect test accuracy, solves this problem. We are able to identify certain "planning" and "reasoning" mechanisms in the network that necessitate cooperation between the attention blocks to implement the desired logic. Second, we study how pretrained LLMs, namely Mistral-7B and Gemma-2-9B, solve this problem. We characterize their reasoning circuits through causal intervention experiments, providing necessity and sufficiency evidence for the circuits. We find evidence suggesting that the two models' latent reasoning strategies are surprisingly similar, and human-like. Overall, our work systemically uncovers novel aspects of small and large transformers, and continues the study of how they plan and reason.

Related papers

• Frontier LLMs Still Struggle with Simple Reasoning Tasks [53.497499123166804]
  This work studies the performance of frontier language models on a broad set of "easy" reasoning problems.<n>We create a suite of procedurally generated simple reasoning tasks, including counting, first-order logic, proof trees, and travel planning.<n>We show that even state-of-the-art thinking models consistently fail on such problems and for similar reasons.
  arXiv  Detail & Related papers  (2025-07-09T22:22:49Z)
• Reasoning Large Language Model Errors Arise from Hallucinating Critical Problem Features [0.0]
  We test o1-mini, o3-mini, DeepSeek-R1, Claude 3.7 Sonnet, Gemini 2.5 Pro Preview, and Grok 3 Mini Beta on graph coloring as a variable-complexity constraint-satisfaction logic problem.<n>We find evidence from both error rate comparisons and CoT/explanation text analysis that RLLMs are prone to hallucinate edges not specified in the prompt's description of the graph.
  arXiv  Detail & Related papers  (2025-05-17T21:55:12Z)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  Chain-of-Thought (CoT) prompting enhances the reasoning of large language models (LLMs) by decomposing problems into sequential steps.<n>We propose Syzygy of Thoughts (SoT)-a novel framework that extends CoT by introducing auxiliary, interrelated reasoning paths.<n>SoT captures deeper logical dependencies, enabling more robust and structured problem-solving.
  arXiv  Detail & Related papers  (2025-04-13T13:35:41Z)
• Empowering LLMs with Logical Reasoning: A Comprehensive Survey [49.91445266392609]
  Large language models (LLMs) have achieved remarkable successes on various tasks.<n>Recent studies have found that there are still significant challenges to the logical reasoning abilities of LLMs.
  arXiv  Detail & Related papers  (2025-02-21T18:20:35Z)
• How Do LLMs Perform Two-Hop Reasoning in Context? [76.79936191530784]
  We train a three-layer transformer on synthetic two-hop reasoning tasks. We explain the inner mechanisms for how models learn to randomly guess between distractions. Our findings provide new insights into how reasoning emerges during training.
  arXiv  Detail & Related papers  (2025-02-19T17:46:30Z)
• Mechanistic Unveiling of Transformer Circuits: Self-Influence as a Key to Model Reasoning [9.795934690403374]
  It is still unclear which multi-step reasoning mechanisms are used by language models to solve such tasks. We employ circuit analysis and self-influence functions to evaluate the changing importance of each token throughout the reasoning process. We demonstrate that the underlying circuits reveal a human-interpretable reasoning process used by the model.
  arXiv  Detail & Related papers  (2025-02-13T07:19:05Z)
• Make LLMs better zero-shot reasoners: Structure-orientated autonomous reasoning [52.83539473110143]
  We introduce a novel structure-oriented analysis method to help Large Language Models (LLMs) better understand a question. To further improve the reliability in complex question-answering tasks, we propose a multi-agent reasoning system, Structure-oriented Autonomous Reasoning Agents (SARA) Extensive experiments verify the effectiveness of the proposed reasoning system. Surprisingly, in some cases, the system even surpasses few-shot methods.
  arXiv  Detail & Related papers  (2024-10-18T05:30:33Z)
• Counting in Small Transformers: The Delicate Interplay between Attention and Feed-Forward Layers [16.26331213222281]
  We investigate how architectural design choices influence the space of solutions that a transformer can implement and learn. We characterize two different counting strategies that small transformers can implement theoretically. Our findings highlight that even in simple settings, slight variations in model design can cause significant changes to the solutions a transformer learns.
  arXiv  Detail & Related papers  (2024-07-16T09:48:10Z)
• Distributional reasoning in LLMs: Parallel reasoning processes in multi-hop reasoning [8.609587510471943]
  We introduce a novel and interpretable analysis of internal multi-hop reasoning processes in large language models. We show that during inference, the middle layers of the network generate highly interpretable embeddings. Our findings can help uncover the strategies that LLMs use to solve reasoning tasks, offering insights into the types of thought processes that can emerge from artificial intelligence.
  arXiv  Detail & Related papers  (2024-06-19T21:36:40Z)
• Understanding Transformer Reasoning Capabilities via Graph Algorithms [25.08208816144745]
  We study which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems. Our results show that transformers excel at many graph reasoning tasks, even outperforming specialized graph neural networks.
  arXiv  Detail & Related papers  (2024-05-28T18:31:14Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a complex reasoning schema over KG upon large language models (LLMs) We augment the arbitrary first-order logical queries via binary tree decomposition to stimulate the reasoning capability of LLMs. Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)
• LogicBench: Towards Systematic Evaluation of Logical Reasoning Ability of Large Language Models [52.03659714625452]
  Recently developed large language models (LLMs) have been shown to perform remarkably well on a wide range of language understanding tasks. But, can they really "reason" over the natural language? This question has been receiving significant research attention and many reasoning skills such as commonsense, numerical, and qualitative have been studied.
  arXiv  Detail & Related papers  (2024-04-23T21:08:49Z)
• $\ exttt{LM}^\ exttt{2}$: A Simple Society of Language Models Solves Complex Reasoning [22.810441504080703]
  Large Language Models (LLMS) often lose track of complex, multi-step reasoning. This paper proposes LM2 to address these challenges. LM2 modularizes the decomposition, solution, and verification into three different language models.
  arXiv  Detail & Related papers  (2024-04-02T19:23:10Z)
• Assessing Logical Reasoning Capabilities of Encoder-Only Transformer Models [0.13194391758295113]
  We investigate the extent to which encoder-only transformer language models (LMs) can reason according to logical rules. We show for several encoder-only LMs that they can be trained, to a reasonable degree, to determine logical validity on various datasets. By cross-probing fine-tuned models on these datasets, we show that LMs have difficulty in transferring their putative logical reasoning ability.
  arXiv  Detail & Related papers  (2023-12-18T21:42:34Z)
• Towards a Mechanistic Interpretation of Multi-Step Reasoning Capabilities of Language Models [107.07851578154242]
  Language models (LMs) have strong multi-step (i.e., procedural) reasoning capabilities. It is unclear whether LMs perform tasks by cheating with answers memorized from pretraining corpus, or, via a multi-step reasoning mechanism. We show that MechanisticProbe is able to detect the information of the reasoning tree from the model's attentions for most examples.
  arXiv  Detail & Related papers  (2023-10-23T01:47:29Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  We investigate the limits of transformer large language models across three representative compositional tasks. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching.
  arXiv  Detail & Related papers  (2023-05-29T23:24:14Z)
• Exploring Self-supervised Logic-enhanced Training for Large Language Models [59.227222647741094]
  In this paper, we make the first attempt to investigate the feasibility of incorporating logical knowledge through self-supervised post-training. We devise an auto-regressive objective variant of MERIt and integrate it with two LLM series, i.e., FLAN-T5 and LLaMA, with parameter size ranging from 3 billion to 13 billion. The results on two challenging logical reasoning benchmarks demonstrate the effectiveness of LogicLLM.
  arXiv  Detail & Related papers  (2023-05-23T06:13:10Z)
• How Do Transformers Learn Topic Structure: Towards a Mechanistic Understanding [56.222097640468306]
  We provide mechanistic understanding of how transformers learn "semantic structure" We show, through a combination of mathematical analysis and experiments on Wikipedia data, that the embedding layer and the self-attention layer encode the topical structure.
  arXiv  Detail & Related papers  (2023-03-07T21:42:17Z)
• Faithful Reasoning Using Large Language Models [12.132449274592668]
  We show how LMs can be made to perform faithful multi-step reasoning via a process whose causal structure mirrors the underlying logical structure of the problem. Our approach works by chaining together reasoning steps, where each step results from calls to two fine-tuned LMs. We demonstrate the effectiveness of our model on multi-step logical deduction and scientific question-answering, showing that it outperforms baselines on final answer accuracy.
  arXiv  Detail & Related papers  (2022-08-30T13:44:41Z)
• Unveiling Transformers with LEGO: a synthetic reasoning task [23.535488809197787]
  We study how the transformer architecture learns to follow a chain of reasoning. In some data regime the trained transformer finds "shortcut" solutions to follow the chain of reasoning. We find that one can prevent such shortcut with appropriate architecture modification or careful data preparation.
  arXiv  Detail & Related papers  (2022-06-09T06:30:17Z)
• End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking [52.05847268235338]
  We show how machine learning systems can perform logical extrapolation without overthinking problems. We propose a recall architecture that keeps an explicit copy of the problem instance in memory so that it cannot be forgotten. We also employ a progressive training routine that prevents the model from learning behaviors that are specific to number and instead pushes it to learn behaviors that can be repeated indefinitely.
  arXiv  Detail & Related papers  (2022-02-11T18:43:28Z)
• Thinking Like Transformers [64.96770952820691]
  We propose a computational model for the transformer-encoder in the form of a programming language. We show how RASP can be used to program solutions to tasks that could conceivably be learned by a Transformer. We provide RASP programs for histograms, sorting, and Dyck-languages.
  arXiv  Detail & Related papers  (2021-06-13T13:04:46Z)
• AR-LSAT: Investigating Analytical Reasoning of Text [57.1542673852013]
  We study the challenge of analytical reasoning of text and introduce a new dataset consisting of questions from the Law School Admission Test from 1991 to 2016. We analyze what knowledge understanding and reasoning abilities are required to do well on this task.
  arXiv  Detail & Related papers  (2021-04-14T02:53:32Z)
• CausalWorld: A Robotic Manipulation Benchmark for Causal Structure and Transfer Learning [138.40338621974954]
  CausalWorld is a benchmark for causal structure and transfer learning in a robotic manipulation environment. Tasks consist of constructing 3D shapes from a given set of blocks - inspired by how children learn to build complex structures.
  arXiv  Detail & Related papers  (2020-10-08T23:01:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.