From Verification to Herding: Exploiting Software’s Sparsity of Influence

Tim Menzies, Kishan Kumar Ganguly · 2026

Read From Verification to Herding: Exploiting Software’s Sparsity of Influence by Tim Menzies, Kishan Kumar Ganguly (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10478.txt.

Introduction

Tim Menzies and Kishan Kumar Ganguly argue that software testing should shift from costly verification to herding, steering systems toward goals by search instead of models. Their lever is the sparsity of influence: in many systems a few variables rule a huge state space. Their learner EZR finds those controlling variables directly by light sampling, with no prior knowledge assumed. Across dozens of tasks it reached near peak results with only a few dozen samples, replacing heavy solvers at a fraction of the effort.

Catalog record

CREATORTim Menzies, Kishan Kumar Ganguly
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27529
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.10478

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

From Verification to Herding: Exploiting Software’s Sparsity of Influence Tim Menzies, Kishan Kumar Ganguly Abstract Software verification is now costly, taking over half the project effort while failing on modern complex systems. We hence propose a shift from verification and modeling to herding : treating testing as a model-free search task that steers systems toward target goals. This exploits the ”Sparsity of Influence” —the fact that, often, large software state spaces are ruled by just a few variables, We introduce EZR (Efficient Zero-knowledge Ranker), a stochastic learner that finds these controllers directly. Across dozens of tasks, EZR achieved 90% of peak results with only 32 samples, replacing heavy solvers with light sampling. 1 Introduction Testing remains the dominant economic bottleneck in software production. Despite advances in automation, verification and validation (V&V) consume up to 60% of total development effort [ 20 ] . This cost is escalating as systems transition from deterministic logic to stochastic behaviors driven by AI components, concurrency, and distributed data. In these environments, the traditional goal of ”verification”—proving the absence of errors across all states—is computationally intractable. A common response has largely been to address this complex problem with yet more complexity. Techniques like symbolic execution, model checking, and fuzzing attempt to explore the full combinatorial explosion of the state space ( 2^{|A|} ). When these fail, researchers turn to higher-order logic systems, such as Answer Set Programming (ASP) or Probabilistic Programming (PP), to reason about uncertainty. We argue that these approaches miss a fundamental physical property of software: Sparsity of Influence . While the theoretical state space of a program is vast, the effective control space is surprisingly small. Empirical evidence across decades of software engineering research suggests that program behavior is rarely determined by complex interactions of hundreds of variables. Inste ad, it is governed by a ”master key” subset of variables (often |A^{\prime}|\leq 10 ). This paper proposes Herding , a change to the nature of the testing process. Instead of verifying correctness or building complex models, Herding uses lightweight sampling to identify these ”master keys” and steer the system toward a ”Heaven” state (e.g., zero defects, low latency). Our contributions are: • The Anti-Modeling Argument: We critique the ”Model-First” approach (ASP/PP), since direct data sampling can be more cost- effective than building new kinds of models (Section 2). • The Generalization of “Testing” Section 3 makes a theoretical argument that the prpcess we call “testing” cab be ge generatized to cover a large space of tasks. • The Sparsity Synthesis: We compile extensive evidence showing that software sparsity is a general result, present in many domains (Section 4). • The EZR Recipe: We present a recipe for EZR (Efficient Zero-knowledge Ranker), an algorithm that exploits sparsity to optimize software with minimal compute (Section 5). • Empirical Evidence: We show that on 63 tasks, 32 samples are sufficient to reach 90% of optimality (Section 6). 2 The Modeling Trap Before detailing our approach, we must address the prevailing ”high-road” solutions to software uncertainty: Answer Set Programming (ASP) and Probabilistic Programming (PP). Both communities offer sophisticated tools to handle non-determinism. However, both fall into the ”Modeling Trap.” 2.1 The Cost of T (The Theory) Both ASP and PP rely on the existence of a robust model, T . 1. Answer Set Programming (ASP): ASP solves search problems by reducing them to stable models of logic programs [ 6 ] . While powerful for well-defined combinatorial problems (e.g., graph coloring, scheduling), applying ASP to testing requires encoding the system’s behavior into logical rules. 2. Probabilistic Programming (PP): PP frameworks like Stan [ 8 ] or Pyro [ 5 ] allow developers to specify probabilistic models and perform inference (usually MCMC). However, PP requires a model T that defines priors and relationships. The drawback in both approaches is the assumption that T is cheaper to build than the software itself. In modern software engineering (SE), the system is the model. Recreating a logical or probabilistic shadow of a million-line distributed system is a ”boil the ocean” strategy. It shifts the burden from ”testing the code” to ”verifying the model of the code.” 2.2 The ”Data-First” Alternative Our approach posits that we do not need to fully understand a model chain to control it. This is a ”black-box” optimization philosophy. If the control space is sparse, we can ignore the complex internal mechanics ( T ) and focus solely on the Input/Output pairs (X,Y) . Instead of asking ”Why does this fail?” (which requires a Model), Herding asks ”Which inputs maximize success?” (which requires only data). By bypassing the construction of T , we eliminate a fragile and expensive step in the V&V pipeline. As we show in Section 6, simple rank-based sampling can outperform more complex reasoning because it goes straight to the empirical reality of the system. 3 An Abductive Model of Testing (and Other Things) To formalize this “data-first” stance without falling back into the “modeling trap,” we adopt Poole’s abductive framework [ 31 ] . Unlike the heavy model-building of ASP, Poole’s logic allows us to accept the system-as-is as the theory ( T ) and reframe the engineering challenge as the optimization of assumptions ( A ). In turns out that Poole’s framework provides a unifying theory for activity across the software engineering life cycle, from requirements engineering (at inception) to verification (at the end). It handles an interesting and challenging case (testing non-deterministic systems) while also offering engineering insight into when many SE tasks, including testing, can become very simple indeed (specifically, when the number of key assumptions is very small). (In this paper, assumptions are an umbrella term that covers design choices, runtime choices coded by a programmer, or environmental factors outside the program e.g., traffic on the internet, weather.) In summary, in this framework, all inference becomes an optimization task exploring assumptions in order to reach goals. In the general case, only a subset of a theory T can be used to achieve goals G using assumptions A without leading to errors (denoted \bot ): \begin{array}[]{l@{\hspace{1cm}}l}T\subseteq\mathit{theory}\hfil\hskip 28.45274pt&T\wedge A\vdash G\\ A\subseteq\mathit{assumptions}\hfil\hskip 28.45274pt&T\wedge A\not\vdash\bot\\ G\subseteq\mathit{goals}\hfil\hskip 28.45274pt&\end{array} (1) In plain English: • T\wedge A\vdash G means testing that “we can do something” (functionality); • T\wedge A\not\vdash\bot means testing that “we don’t mess up” (validity). Equation 1 is a useful model for a variety of tasks. Nondeterminism , is the stochastic selection among these different worlds In design , some humans choose the assumption, while in diagnosis , the world chooses A , and our task is to find the minimal A that covers the symptoms G . Equation 1 also models common SE tasks. Testing is the search for an assignment A^{\prime} that triggers a specific behavior (e.g., a crash or a successful transaction). More specifically, metamorphic testing asks the question: what extra knowledge can be imported to assess a system; i.e., it focuses on the clause T\wedge A\not\vdash\bot G\subseteq\mathit{goals} . But not just testing: Equation 1 maps cleanly onto formal models of requirements engineering. The traditional view of RE [ 35 ] assumed that Specification ( S ) and Domain Knowledge ( K ) must logically entail Requirements ( R ). However, Jureta et al. [ 17 ] argue in their

Read the complete text