CS Paper Radar

The Output-Space Hypothesis: Enumerative Equivalence Checking for Tensor Programs

Paul Biberstein, Joseph Devietti, Mayur Naik

cs.PL cs.LGcs.SE ·submitted 2026-09-17 02:54 UTC · v1
hot direction

Abstract

Tensor programs, as used in deep learning models, are a prime target for optimization, as small performance improvements can have a large impact across training or inference workloads. However, such optimizations are complicated and can produce subtle bugs. Traditionally, correctness is assumed when differential testing against a reference on random inputs fails to reveal bugs. However, the inputs to these programs are massive tensors, and finding bugs can require generating extremely low likelihood inputs with precise relationships among their values. We propose a novel way to find bugs more consistently by flipping the quantifiers. Rather than generating a single input and checking all output tensor locations for equivalence, what if you could check a single output tensor location's equivalence for all inputs? We implement this idea in a system, \dirigo, by using a novel symbolic execution strategy. We demonstrate that \dirigo can find bugs effectively in a public dataset of 6,988 AI-written CUDA kernels that are all marked correct by differential testing. Of these, \dirigo finds 600 kernels that are actually buggy, and finds 97.3\% of those bugs within two minutes.

Closest papers

Nearest neighbours by meaning across the whole index.

Racer: Hunting GPU Kernel Bugs with Symbolic Equivalence Checking

cs.SC cs.AI ·2026-10-20 ·Tuan Truong Vu, Cheng Tan
similarity 0.70
Abstract

GPU kernels are critical to the performance of today's AI services, yet the same operators are rewritten repeatedly: for each GPU generation, numeric format, serving regime, and kernel language. Every rewrite must preserve the function computed by the implementation it replaces. Today, this obligation depends almost entirely on differential testing: run the new kernel and a trusted reference on randomly sampled tensors, then compare their outputs within a tolerance. This approach has blind spots that additional test cases cannot eliminate. For example, a logical bug may produce an error smaller than the tolerance required to accommodate a correct optimized kernel. We propose symbolic equivalence checking, which executes a kernel and its reference on symbolic inputs, turning each output cell into an exact algebraic expression, and then checks whether the paired expressions agree for all inputs. Because these expressions are exact, symbolic equivalence checking distinguishes floating-point error from logical bugs, while a single check covers the entire input space. We implement Racer, a PTX-level symbolic equivalence checking engine, with three techniques that make this approach practical for production kernels: (1) Shape Reduction to control checking cost, (2) a lockstep CTA scheduler to handle concurrency, and (3) idiom templates with exact numeric refutation for otherwise inconclusive results. Across 2,408 production kernels from 41 collection targets, Racer found 82 real bugs in 23 libraries, including 76 previously unknown bugs and 41 confirmed so far.

0.15

Stateful Testing for Deep Learning Compilers

cs.SE cs.LG ·2026-10-15 ·Jiatao Ge, Ruixiang Qian, Yibo Hu, Yanzhou Mu, Yinglong Zou +3 more
similarity 0.64
Abstract · 27 pages, 6 figures

Modern deep learning compilers compile models lazily and cache artifacts across invocations. Retained compiler state can make a later invocation incorrect even when it is correct in isolation. An analysis of 26 publicly reported issues in PyTorch, JAX, and TensorFlow shows that detecting such bugs requires sequences that first establish compiler state and then expose a failure. We present Rondo, a stateful testing method that represents each test case as a model paired with an invocation sequence. Rondo mutates invocation sequences and uses a Markov chain Monte Carlo sampler guided by compilation behavior to favor rarely observed behaviors. Its three-way differential oracle compares execution without compilation, compiled execution with compiler state reset, and compiled execution with state retained. It confirms stateful bugs by replaying the same invocation with state retained and reset while preserving inputs and program state, then shortens sequences while preserving the original bug. We evaluate Rondo on four deep learning frameworks using 24 common model architectures. Rondo detects 117 bugs, including 35 stateful bugs. We submit 39 bug reports, including 18 for stateful bugs; developers confirm 35 reports, including 16 for stateful bugs, and fix 18 bugs, including 11 stateful bugs. Rondo achieves the highest behavior coverage and compiler Python source-line coverage among the compared methods, with 99.26% alarm precision. It shortens 44 of 117 invocation sequences, reducing the lengths of these 44 sequences by 83.34% on average.

0.21

Testing Deep Learning Library APIs via Cross-Framework Differential Fuzzing

cs.SE ·2026-08-12 ·Bin Duan, Ruican Dong, Naipeng Dong, Dan Dongseong Kim, Guowei Yang
similarity 0.62
Abstract

Deep learning libraries underpin many safety- and reliability-critical applications, yet existing API-level testing techniques often rely on intra-library properties or CPU--GPU differential oracles and may miss defects that behave consistently across hardware backends. We present Xamt, a cross-framework differential fuzzing approach for deep learning library APIs. Xamt constructs and tests execution-validated groups of APIs intended to implement equivalent operations across seven libraries. It uses explicit API aliases and parameter-role normalization to construct candidate correspondences and validates them through pairwise execution and a group-level behavioral check on canonical ordinary inputs. The resulting groups are explored using variance-guided differential fuzzing with ordinary, boundary, and non-finite inputs. Crash and inconsistency oracles flag executions exhibiting abnormal termination or inconsistent outputs for subsequent reproduction and analysis. Across the seven libraries, Xamt constructs 676 execution-validated groups containing 2,563 matched APIs. Among these, Xamt identifies 72 independently reproduced discrepancy cases, including 4 crash cases and 68 output inconsistencies. Among the 72 developer reports, 25 have been confirmed, including 23 that have been fixed.

0.04

Grounding Deep Learning Framework Testing in Data Flow

cs.SE cs.LG ·2026-10-11 ·Jiatao Ge, Yanzhou Mu, Yinglong Zou, Yibo Hu, Zhenyu Chen +1 more
similarity 0.61
Abstract · 22 pages, 6 figures, 7 tables

Data flow underlies deep learning (DL) framework execution, including automatic differentiation and operator-fusion optimization. Bugs involving data flow can cause incorrect results or unexpected behavior. Existing testing methods represent models primarily by operator topology, omitting runtime tensor values and properties and operator input requirements. They therefore cannot distinguish data flows in models with similar topologies, even when these differences affect framework behavior. We introduce the Tensor Flow Graph (TFG) to capture runtime tensor states and operator input requirements. Its nodes represent operators and their input requirements, while its edges record tensor values and properties. Building on the TFG, we propose FlowMuT, a mutation-based testing method grounded in data flow. Mutations are represented as constrained subgraph replacements, with mutation operators derived from prior work and an analysis of mutable data flow objects. In each round, FlowMuT builds a TFG for the seed model, pairs mutation operators with TFG sites, and filters illegal candidates using data flow constraints. It uses LinUCB to select a candidate based on coverage and impact, executes the mutant, updates selection feedback, and uses each accepted mutant as the next seed. We evaluate FlowMuT on PyTorch and MindSpore using representative models from diverse application scenarios. FlowMuT submitted 55 bug reports for cases missed by all baseline methods; developers confirmed 41 reports and fixed the bugs described in 7 reports. FlowMuT achieves 43.4% higher data flow diversity than the strongest baseline and a legal mutant rate of 96.7%, compared with 86.4% without constraints. These results show that testing from a data flow perspective is practical and effective.

0.44

SparseConflicts: Handling Conflicting Data Layouts in Sparse Tensor Contractions

cs.PL ·2026-09-06 ·Adhitha Dias, Kirshanthan Sundararajah, Artem Pelenitsyn, Milind Kulkarni
similarity 0.60
Abstract · 25 pages, 18 figures, 2 tables

Optimizing sparse tensor computations is challenging due to the use of compressed storage formats, which leads to non-affine loop nests and a vast, complex schedule space. The performance of a given schedule is sensitive to the sparsity pattern of the input tensors, making it difficult to find a single optimal solution. When input tensors in the same tensor contraction have conflicting data layouts in relation to the iteration order, it requires costly-both in time and memory-layout transformation, such as transposition. A promising but under-explored alternative is to generate a schedule that avoids explicit transposition, but this has not been systematically supported in existing compilers. This paper presents a new code generation strategy that generalizes the intermediate representation of the TACO sparse tensor compiler to generate a single loop nest, circumventing explicit transposition of tensors when the tensors have conflicting data layout iteration orders. We extend TACOś iteration graph to express a search-based strategy for locating elements in tensors with conflicting layouts, and we introduce new intermediate representation nodes to lower these schedules to efficient code. This enables the systematic generation of loops that do not require explicit transposition, thus avoiding the overhead of materializing temporary tensors. We evaluate our approach on a set of sparse tensor contractions using both real-world and synthetic datasets. Our results demonstrate that for computations with misaligned data layouts, our fused approach achieves up to 2x speedup for some sparsity patterns over the traditional approach of explicitly creating a transposed temporary. We also provide guidelines for when this new scheduling strategy is likely to be beneficial.

0.35

Sparse Autoencoders Are a Shared Coordinate System for Symbolic Matching

cs.LG cs.AIcs.CLcs.SC ·2026-10-14 ·Xiaocong Yang, Xuanyu Meng, Yuji Zhang, Jiawei Han, ChengXiang Zhai
similarity 0.60
Abstract

Large language models (LLMs) hold broad knowledge in one set of weights, but lack interpretability and trustworthy reasoning, especially in high-stakes use cases. A neuro-symbolic model, with its interpretable architecture and System 2 reasoning capacity, is a promising alternative if built at the scale of LLMs; however, its symbolic backbone is usually constructed with human effort, so existing neuro-symbolic models are bottlenecked by the scope of the symbol component and usually domain-specific. A data-driven method could instead build a larger symbolic system by aligning and merging existing ones. We target its first, foundational step: matching units across these heterogeneous systems. Our method, SAE-IDF, encodes a symbol in its native context into a sparse code with a sparse autoencoder (SAE), re-weights each dimension by its rarity and matches across systems. On 12 tasks across 6 kinds of symbolic system, SAE-IDF outperforms the same LLM's dense baseline on all tasks with Gemma-2-9B and all but one with Llama-3.1-8B, by up to 45 points, consistently across SAE layers and configurations. SAE-IDF is also interpretable: every dimension of the sparse code has a human-readable meaning, so each match decomposes into named concepts (features). Our work paves the way to a universal symbolic backbone.

0.37

Proving LLM-Generated GPU Kernels Correct and Safe: Floating-Point Verification in Lean and VerCors

cs.PL ·2026-10-17 ·Archibald Browne, Eugene Lee, Cristopher Salvi
benchmark similarity 0.60
Abstract

Modern statistical model development begins with a high-level specification in an automatic differentiation framework such as PyTorch, JAX, or TensorFlow, which is then lowered to a target backend by a compiler or implemented manually by a research engineer. In this paper, we study whether frontier language models can correctly perform the latter task by generating GPU kernels from high-level benchmark specifications. We introduce a framework in which a language-model agent uses Velvet, a program verifier for imperative programs embedded in Lean, to prove semantic equivalence between a high-level specification and a generated CUDA kernel under an explicit set of assumptions. It also asks the LLM to prove thread safety and data race freedom of the generated kernel in VerCors, a deductive verifier for parallel code. Our main contribution to the formal verification of LLM- generated GPU kernels is showing that a combination of Lean automation and language-model-guided proof construction can verify a broad set of basic neural- network building blocks over floating-point values, allowing LLMs to implement semantically correct and safe kernels. In our framework, floating-point verifications never rely on compiled code and are always checked via the Lean kernel.

0.29

DIFUZZI: A Differential Fuzzing Tool for Code Functional Similarity Assessment

cs.SE ·2026-10-28 ·Simantika Bhattacharjee Dristi, Matthew B. Dwyer
code/data similarity 0.59
Abstract

A range of software engineering tasks, such as optimization and refactoring, seek to preserve the behavior of software components and require methods to assess functional similarity. Research has explored formal approaches to prove functional equivalence and used machine learning methods to approximate it, but the former does not scale and does not quantify the extent of similarity and the latter struggles when subtle semantic differences are present. Differential fuzzing offers a scalable approach for differencing programs semantically, but applying it often requires substantial manual effort to construct input generators that are well-suited to a target pair of programs. To address this challenge, we introduce DIFUZZI, which incorporates an LLM-based generator synthesis step that is iteratively validated and repaired. By automating this step, DIFUZZI paves the way for broader applicability of differential fuzzing. We release DIFUZZI at https://github.com/Dristi123/difuzzi_tool, with a demonstration video at https://youtu.be/FlHNOHuo9WE

0.39