Stencil-Lifting: Hierarchical Recursive Lifting System for Extracting Summary of Stencil Kernel in Legacy Codes

• URL: http://arxiv.org/abs/2509.10236v2
• Date: Mon, 15 Sep 2025 08:39:52 GMT
• Title: Stencil-Lifting: Hierarchical Recursive Lifting System for Extracting Summary of Stencil Kernel in Legacy Codes
• Abstract summary: We introduce Stencil-Lifting, a novel system for automatically converting stencil kernels written in low-level languages into Domain-Specific Language implementations.<n>Stencil-Lifting achieves scalable stencil kernel abstraction through two key innovations.<n>We evaluate Stencil-Lifting on diverse stencil benchmarks from two different suites and on four real-world applications.
• Score: 12.182789082355058
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce Stencil-Lifting, a novel system for automatically converting stencil kernels written in low-level languages in legacy code into semantically equivalent Domain-Specific Language (DSL) implementations. Targeting the efficiency bottlenecks of existing verified lifting systems, Stencil-Lifting achieves scalable stencil kernel abstraction through two key innovations. First, we propose a hierarchical recursive lifting theory that represents stencil kernels, structured as nested loops, using invariant subgraphs, which are customized data dependency graphs that capture loop-carried computation and structural invariants. Each vertex in the invariant subgraph is associated with a predicate-based summary, encoding its computational semantics. By enforcing self-consistency across these summaries, Stencil-Lifting ensures the derivation of correct loop invariants and postconditions for nested loops, eliminating the need for external verification. Second, we develop a hierarchical recursive lifting algorithm that guarantees termination through a convergent recursive process, avoiding the inefficiencies of search-based synthesis. The algorithm efficiently derives the valid summaries of stencil kernels, and its completeness is formally proven. We evaluate Stencil-Lifting on diverse stencil benchmarks from two different suites and on four real-world applications. Experimental results demonstrate that Stencil-Lifting achieves 31.62$\times$ and 5.8$\times$ speedups compared to the state-of-the-art verified lifting systems STNG and Dexter, respectively, while maintaining full semantic equivalence. Our work significantly enhances the translation efficiency of low-level stencil kernels to DSL implementations, effectively bridging the gap between legacy optimization techniques and modern DSL-based paradigms.

Related papers

• Recursive Multi-Agent Systems [106.82473907888497]
  We introduce RecursiveMAS, a multi-agent framework that casts the entire system as a unified latent-space computation.<n>RecursiveMAS connects heterogeneous agents as a collaboration loop through the lightweight RecursiveLink module.<n> Theoretical analyses of runtime complexity and learning dynamics establish that RecursiveMAS is more efficient than standard text-based MAS.
  arXiv  Detail & Related papers  (2026-04-28T17:59:34Z)
• $\mathcal{S}^2$IT: Stepwise Syntax Integration Tuning for Large Language Models in Aspect Sentiment Quad Prediction [51.165432266846096]
  syntactic structure information is underutilized in the generative paradigm of large language models (LLMs)<n>S2IT progressively integrates syntactic structure knowledge into LLMs through a multi-step tuning process.<n> Experiments demonstrate that S2IT significantly improves state-of-the-art performance across multiple datasets.
  arXiv  Detail & Related papers  (2026-04-25T13:24:29Z)
• Prism: Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models [96.0074341403456]
  Inference-time compute has re-emerged as a practical way to improve LLM reasoning.<n>Most test-time scaling (TTS) algorithms rely on autoregressive decoding.<n>We propose Prism, an efficient TTS framework for dLLMs.
  arXiv  Detail & Related papers  (2026-02-02T09:14:51Z)
• Training-Free Tokenizer Transplantation via Orthogonal Matching Pursuit [45.18582668677648]
  We present a training-free method to transplant tokenizers in large language models.<n>We approximate each out-of-vocabulary token as a sparse linear combination of shared tokens.<n>We show that OMP achieves best zero-shot preservation of the base model's performance.
  arXiv  Detail & Related papers  (2025-06-07T00:51:27Z)
• COrAL: Order-Agnostic Language Modeling for Efficient Iterative Refinement [80.18490952057125]
  Iterative refinement has emerged as an effective paradigm for enhancing the capabilities of large language models (LLMs) on complex tasks. We propose Context-Wise Order-Agnostic Language Modeling (COrAL) to overcome these challenges. Our approach models multiple token dependencies within manageable context windows, enabling the model to perform iterative refinement internally.
  arXiv  Detail & Related papers  (2024-10-12T23:56:19Z)
• Dynamic Perceiver for Efficient Visual Recognition [87.08210214417309]
  We propose Dynamic Perceiver (Dyn-Perceiver) to decouple the feature extraction procedure and the early classification task. A feature branch serves to extract image features, while a classification branch processes a latent code assigned for classification tasks. Early exits are placed exclusively within the classification branch, thus eliminating the need for linear separability in low-level features.
  arXiv  Detail & Related papers  (2023-06-20T03:00:22Z)
• Scalable Learning of Latent Language Structure With Logical Offline Cycle Consistency [71.42261918225773]
  Conceptually, LOCCO can be viewed as a form of self-learning where the semantic being trained is used to generate annotations for unlabeled text. As an added bonus, the annotations produced by LOCCO can be trivially repurposed to train a neural text generation model.
  arXiv  Detail & Related papers  (2023-05-31T16:47:20Z)
• Top-Down Synthesis for Library Learning [46.285220926554345]
  corpus-guided top-down synthesis is a mechanism for synthesizing library functions that capture common functionality from a corpus of programs. We present an implementation of the approach in a tool called Stitch and evaluate it against the state-of-the-art deductive library learning algorithm from DreamCoder.
  arXiv  Detail & Related papers  (2022-11-29T21:57:42Z)
• Shift-Reduce Task-Oriented Semantic Parsing with Stack-Transformers [6.744385328015561]
  Task-oriented dialogue systems, such as Apple Siri and Amazon Alexa, require a semantic parsing module in order to process user utterances and understand the action to be performed. This semantic parsing component was initially implemented by rule-based or statistical slot-filling approaches for processing simple queries. In this article, we advance the research on neural-reduce semantic parsing for task-oriented dialogue.
  arXiv  Detail & Related papers  (2022-10-21T14:19:47Z)
• Autoregressive Search Engines: Generating Substrings as Document Identifiers [53.0729058170278]
  Autoregressive language models are emerging as the de-facto standard for generating answers. Previous work has explored ways to partition the search space into hierarchical structures. In this work we propose an alternative that doesn't force any structure in the search space: using all ngrams in a passage as its possible identifiers.
  arXiv  Detail & Related papers  (2022-04-22T10:45:01Z)
• A Parallelizable Lattice Rescoring Strategy with Neural Language Models [62.20538383769179]
  A posterior-based lattice expansion algorithm is proposed for efficient lattice rescoring with neural language models (LMs) for automatic speech recognition. Experiments on the Switchboard dataset show that the proposed rescoring strategy obtains comparable recognition performance. The parallel rescoring method offers more flexibility by simplifying the integration of PyTorch-trained neural LMs for lattice rescoring with Kaldi.
  arXiv  Detail & Related papers  (2021-03-08T21:23:12Z)
• Improved Code Summarization via a Graph Neural Network [96.03715569092523]
  In general, source code summarization techniques use the source code as input and outputs a natural language description. We present an approach that uses a graph-based neural architecture that better matches the default structure of the AST to generate these summaries.
  arXiv  Detail & Related papers  (2020-04-06T17:36:42Z)

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.