Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates

• URL: http://arxiv.org/abs/2505.10039v1
• Date: Thu, 15 May 2025 07:35:14 GMT
• Title: Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates
• Authors: Hang Chen, Jiaying Zhu, Xinyu Yang, Wenya Wang,
• Abstract summary: We introduce three types of logic gates: AND, OR, and ADDER gates, and decompose the circuit into combinations of these logical gates.<n>We propose a framework that combines noising-based and denoising-based interventions, which can be easily integrated into existing circuit discovery methods.
• Score: 31.608080868988825
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Circuit discovery has gradually become one of the prominent methods for mechanistic interpretability, and research on circuit completeness has also garnered increasing attention. Methods of circuit discovery that do not guarantee completeness not only result in circuits that are not fixed across different runs but also cause key mechanisms to be omitted. The nature of incompleteness arises from the presence of OR gates within the circuit, which are often only partially detected in standard circuit discovery methods. To this end, we systematically introduce three types of logic gates: AND, OR, and ADDER gates, and decompose the circuit into combinations of these logical gates. Through the concept of these gates, we derive the minimum requirements necessary to achieve faithfulness and completeness. Furthermore, we propose a framework that combines noising-based and denoising-based interventions, which can be easily integrated into existing circuit discovery methods without significantly increasing computational complexity. This framework is capable of fully identifying the logic gates and distinguishing them within the circuit. In addition to the extensive experimental validation of the framework's ability to restore the faithfulness, completeness, and sparsity of circuits, using this framework, we uncover fundamental properties of the three logic gates, such as their proportions and contributions to the output, and explore how they behave among the functionalities of language models.

Related papers

• Position-aware Automatic Circuit Discovery [59.64762573617173]
  We identify a gap in existing circuit discovery methods, treating model components as equally relevant across input positions.<n>We propose two improvements to incorporate positionality into circuits, even on tasks containing variable-length examples.<n>Our approach enables fully automated discovery of position-sensitive circuits, yielding better trade-offs between circuit size and faithfulness compared to prior work.
  arXiv  Detail & Related papers  (2025-02-07T00:18:20Z)
• Unveiling Language Skills via Path-Level Circuit Discovery [31.608080868988825]
  We propose a novel path-level circuit discovery framework capturing how behaviors emerge through interconnected linear chain.<n>Our framework is constructed upon a fully-disentangled linear combinations of memory circuits'' decomposed from the original model.<n>In contrast to circuit graph from existing works, we focus on the complete paths of a generic skill rather than on the fine-grained responses to individual components of the input.
  arXiv  Detail & Related papers  (2024-10-02T08:52:58Z)
• Functional Faithfulness in the Wild: Circuit Discovery with Differentiable Computation Graph Pruning [14.639036250438517]
  We introduce a comprehensive reformulation of the task known as Circuit Discovery, along with DiscoGP. DiscoGP is a novel and effective algorithm based on differentiable masking for discovering circuits.
  arXiv  Detail & Related papers  (2024-07-04T09:42:25Z)
• Adaptive Planning Search Algorithm for Analog Circuit Verification [53.97809573610992]
  We propose a machine learning (ML) approach, which uses less simulations. We show that the proposed approach is able to provide OCCs closer to the specifications for all circuits.
  arXiv  Detail & Related papers  (2023-06-23T12:57:46Z)
• Kerr-effect-based quantum logical gates in decoherence-free subspace [1.194799054956877]
  decoherence-free subspace (DFS) introduced can effectively decrease the influence of decoherence effect. We propose some schemes for setting up a family of quantum control gates, including controlled-NOT (CNOT), Toffoli, and Fredkin gates for two or three logical qubits.
  arXiv  Detail & Related papers  (2023-06-09T02:18:01Z)
• Direct pulse-level compilation of arbitrary quantum logic gates on superconducting qutrits [36.30869856057226]
  We demonstrate any arbitrary qubit and qutrit gate can be realized with high-fidelity, which can significantly reduce the length of a gate sequence. We show that optimal control gates are robust to drift for at least three hours and that the same calibration parameters can be used for all implemented gates.
  arXiv  Detail & Related papers  (2023-03-07T22:15:43Z)
• On the role of entanglement in qudit-based circuit compression [0.0]
  Gate-based universal quantum computation is formulated in terms of two types of operations: local single-qubit gates, and two-qubit entangling gates. We show how the complexity of multi-qubit circuits can be lowered significantly by employing qudit encodings.
  arXiv  Detail & Related papers  (2022-09-29T06:48:48Z)
• Efficient Quantum Circuit Design with a Standard Cell Approach, with an Application to Neutral Atom Quantum Computers [45.66259474547513]
  We design quantum circuits by using the standard cell approach borrowed from classical circuit design. We present evidence that, when compared with automatic routing methods, our layout-aware routers are significantly faster and achieve shallower 3D circuits.
  arXiv  Detail & Related papers  (2022-06-10T10:54:46Z)
• Quantum circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
  We present a technique that pinpoints the sections of a quantum circuit that affect the circuit output the most. We demonstrate the practicality and efficacy of the proposed technique by applying it to example algorithmic circuits implemented on IBM quantum machines.
  arXiv  Detail & Related papers  (2022-04-12T19:39:31Z)
• Logical blocks for fault-tolerant topological quantum computation [55.41644538483948]
  We present a framework for universal fault-tolerant logic motivated by the need for platform-independent logical gate definitions. We explore novel schemes for universal logic that improve resource overheads. Motivated by the favorable logical error rates for boundaryless computation, we introduce a novel computational scheme.
  arXiv  Detail & Related papers  (2021-12-22T19:00:03Z)
• Low-overhead pieceable fault-tolerant construction of logical controlled-phase circuit for degenerate quantum code [11.106110829349221]
  We search for a non-transversal but fault-tolerant construction of a logical controlled-phase gate for quantum code. We find a 3-piece fault-tolerant logical CZ circuit on this code.
  arXiv  Detail & Related papers  (2021-05-15T04:06:12Z)
• Refined Gate: A Simple and Effective Gating Mechanism for Recurrent Units [68.30422112784355]
  We propose a new gating mechanism within general gated recurrent neural networks to handle this issue. The proposed gates directly short connect the extracted input features to the outputs of vanilla gates. We verify the proposed gating mechanism on three popular types of gated RNNs including LSTM, GRU and MGU.
  arXiv  Detail & Related papers  (2020-02-26T07:51:38Z)
• Hardware-Encoding Grid States in a Non-Reciprocal Superconducting Circuit [62.997667081978825]
  We present a circuit design composed of a non-reciprocal device and Josephson junctions whose ground space is doubly degenerate and the ground states are approximate codewords of the Gottesman-Kitaev-Preskill (GKP) code. We find that the circuit is naturally protected against the common noise channels in superconducting circuits, such as charge and flux noise, implying that it can be used for passive quantum error correction.
  arXiv  Detail & Related papers  (2020-02-18T16:45:09Z)

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.