Transformers for Program Termination

• URL: http://arxiv.org/abs/2604.00039v1
• Date: Wed, 25 Mar 2026 17:40:26 GMT
• Title: Transformers for Program Termination
• Abstract summary: We investigate whether transformer architectures can recognise termination patterns directly from source code.<n>We design an ensemble framework of compact transformer encoders, systematically trained with a suite of imbalance-aware loss functions.<n>We introduce an attribution pipeline that produces syntax-aware explanations for the termination estimation.
• Score: 1.2891210250935148
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Determining whether a program terminates is a core challenge in program analysis with direct implications for correctness, verification, and security. We investigate whether transformer architectures can recognise termination patterns directly from source code and how their strengths can be amplified through ensembles. To overcome the extreme scarcity of non-terminating examples, we design an ensemble framework of compact transformer encoders, systematically trained with a suite of imbalance-aware loss functions and class-aware sampling techniques. By combining models trained with distinct loss functions, our ensembles achieve substantially stronger performance than any single transformer, outperforming both powerful off-the-shelf LLMs and graph-based methods. Finally, we introduce an attribution pipeline that produces syntax-aware explanations for the termination estimation.

Related papers

• DIFF-ERO: A Conformance-Aware Loss for Deep Learning in Process Mining [8.304025820176394]
  We introduce DIFF-ERO, a conformance-aware loss function for deep learning models on process data.<n>DIFF-ERO is a differentiable formulation of entropy-based conformance that incorporates control-flow information during training.<n>We show improved predictive performance where structure matters most while maintaining parity elsewhere.
  arXiv  Detail & Related papers  (2026-06-12T09:06:05Z)
• Training LLMs for Multi-Step Tool Orchestration with Constrained Data Synthesis and Graduated Rewards [76.49428173793386]
  LLMs must invoke multiple dependent APIs in the correct order while propagating intermediate outputs.<n>Training models to handle such faces two obstacles: existing environments focus on simple per-turn function calls with simulated data, and binary rewards.<n>We present a framework addressing both challenges. First, we construct a reinforcement learning environment backed by a large-scale cache of real API responses, enabling a data synthesis pipeline that samples valid multi-step orchestration traces.<n>Second, we propose a graduated reward design that decomposes correctness into atomic validity and orchestration.
  arXiv  Detail & Related papers  (2026-03-25T18:31:39Z)
• Weights to Code: Extracting Interpretable Algorithms from the Discrete Transformer [65.38883376379812]
  We propose the Discrete Transformer, an architecture engineered to bridge the gap between continuous representations and discrete symbolic logic.<n> Empirically, the Discrete Transformer not only achieves performance comparable to RNN-based baselines but crucially extends interpretability to continuous variable domains.
  arXiv  Detail & Related papers  (2026-01-09T12:49:41Z)
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  We propose an end-to-end deep learning (DL) framework with low inference complexity for symbol-level precoding.<n>We show that the proposed framework captures substantial performance gains of optimal SLP, while achieving an approximately 80-times speedup over conventional methods.
  arXiv  Detail & Related papers  (2025-10-02T15:15:50Z)
• Measuring Uncertainty in Transformer Circuits with Effective Information Consistency [0.0]
  We develop a sheaf/cohomology and causal emergence perspective to Transformer Circuits.<n>EICS combines (i) a normalized sheaf inconsistency computed from local Jacobians and activations, with (ii) a Gaussian EI proxy for circuit-level causal emergence.<n>We provide practical guidance on score interpretation, computational overhead (with fast and exact modes), and a toy sanity-check analysis.
  arXiv  Detail & Related papers  (2025-09-08T18:54:56Z)
• On the Existence of Universal Simulators of Attention [17.01811978811789]
  We present solutions to identically replicate attention outputs and the underlying elementary matrix and activation operations via RASP.<n>Our proofs, for the first time, show the existence of an algorithmically achievable data-agnostic solution, previously known to be approximated only by learning.
  arXiv  Detail & Related papers  (2025-06-23T15:15:25Z)
• Robust Noise Attenuation via Adaptive Pooling of Transformer Outputs [0.0]
  This work considers problems where a subset of the input vectors contains requisite information for a downstream task (signal) while the rest are distractors (noise)<n>Standard methods used to aggregate transformer outputs, AvgPool, MaxPool, and ClsToken, are vulnerable to performance collapse as the signal-to-noise ratio (SNR) of inputs fluctuates.<n>We show that an attention-based adaptive pooling method can approximate the signal-optimal vector quantizer within derived error bounds for any SNR.
  arXiv  Detail & Related papers  (2025-06-10T20:18:32Z)
• Towards Interpretable Sequence Continuation: Analyzing Shared Circuits in Large Language Models [9.56229382432426]
  This research aims to reverse engineer transformer models into human-readable representations that implement algorithmic functions. By applying circuit interpretability analysis, we identify a key sub-circuit in both GPT-2 Small and Llama-2-7B. We show that this sub-circuit has effects on various math-related prompts, such as on intervaled circuits, Spanish number word and months continuation, and natural language word problems.
  arXiv  Detail & Related papers  (2023-11-07T16:58:51Z)
• Uncovering mesa-optimization algorithms in Transformers [61.06055590704677]
  Some autoregressive models can learn as an input sequence is processed, without undergoing any parameter changes, and without being explicitly trained to do so. We show that standard next-token prediction error minimization gives rise to a subsidiary learning algorithm that adjusts the model as new inputs are revealed. Our findings explain in-context learning as a product of autoregressive loss minimization and inform the design of new optimization-based Transformer layers.
  arXiv  Detail & Related papers  (2023-09-11T22:42:50Z)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  This paper proposes the first end-to-end differentiable meta-BO framework that generalises neural processes to learn acquisition functions via transformer architectures. We enable this end-to-end framework with reinforcement learning (RL) to tackle the lack of labelled acquisition data.
  arXiv  Detail & Related papers  (2023-05-25T10:58:46Z)
• Transformer-based Planning for Symbolic Regression [18.90700817248397]
  We propose TPSR, a Transformer-based Planning strategy for Symbolic Regression. Unlike conventional decoding strategies, TPSR enables the integration of non-differentiable feedback, such as fitting accuracy and complexity. Our approach outperforms state-of-the-art methods, enhancing the model's fitting-complexity trade-off, Symbolic abilities, and robustness to noise.
  arXiv  Detail & Related papers  (2023-03-13T03:29:58Z)
• HEAT: Hardware-Efficient Automatic Tensor Decomposition for Transformer Compression [69.36555801766762]
  We propose a hardware-aware tensor decomposition framework, dubbed HEAT, that enables efficient exploration of the exponential space of possible decompositions. We experimentally show that our hardware-aware factorized BERT variants reduce the energy-delay product by 5.7x with less than 1.1% accuracy loss.
  arXiv  Detail & Related papers  (2022-11-30T05:31:45Z)

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.