Complexity Theory of Randomised Testing

• URL: http://arxiv.org/abs/2607.11811v1
• Date: Mon, 13 Jul 2026 17:08:03 GMT
• Title: Complexity Theory of Randomised Testing
• Abstract summary: We present the first complexity-theoretic foundations for random generators in software testing.<n>We show that the theoretically generable languages coincide exactly with the enumerable languages.<n>This has direct implications for testing at the boundaries of decidability.
• Score: 0.6999740786886536
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Randomised testing is a widely-used approach to software validation, yet its theoretical foundations remain thin. In particular, the fundamental question of what it means for a set of inputs to be \emph{generable} has gone unanswered in both the literature and folklore. We present the first complexity-theoretic foundations for random generators in software testing. We model generators as Turing transducers that consume random bits and produce string-encoded outputs, and show that the theoretically generable languages coincide exactly with the recursively enumerable languages. This has direct implications for testing at the boundaries of decidability, such as compiler testing. For \emph{efficient} generation, we show that the polynomial-time generable languages lie within \textit{NP}, that certain \textit{NP}-complete languages admit efficient generators, and that -- under standard cryptographic assumptions -- there are languages in \textit{P} for which no efficient generator exists: the complexity of efficienct generation and of efficient decision are not the same. We show space-bounded complexity is the natural framework for generators producing \emph{correlated} samples, capturing methodologies such as coverage-guided fuzzing and symbolic execution. Beyond classification, we characterise efficient generability: a language has a polynomial-time generator iff it admits a \emph{certificate scheme} over a verifier -- so witness planting, the folklore technique behind generators to test SAT solvers, is in a sense the only route to efficient generation. On the design of property-based testing libraries, we prove no library can compositionally derive efficient generators from logical predicates involving conjunction or negation, under standard assumptions. However, restricted classes like \textit{NL} (equivalently, linear Datalog predicates) would admit such a compilation.

Related papers

• Language Identification with Succinct Machine-Independent Traces [10.036312061637764]
  We show how to define computational traces that enable identification in the limit.<n>We show how to define traces using an alphabet of tokens that is linear in the size of the alphabet that the languages are defined over.
  arXiv  Detail & Related papers  (2026-07-14T07:18:07Z)
• Is Code Better Than Language for Algorithmic Reasoning [58.86873062890482]
  We show that for tool-augmented language models, comparing natural-language reasoning with code-execution pipelines is difficult because the comparison changes both the intermediate representation and the execution mechanism.<n>We separate these factors with an intermediate intervention: the model expresses its reasoning as executable code, and the language model simulates that code in context to produce an answer.<n>We observe that the intermediate intervention is not meaningfully different from natural-language reasoning (+0.15pp)
  arXiv  Detail & Related papers  (2026-06-14T04:17:21Z)
• Mitigating Bias in Locally Constrained Decoding via Tractable Proposals [73.78736135699953]
  Existing locally constrained decoding approaches enforce constraints by myopically masking out next tokens.<n>Recent work uses sequential Monte Carlo methods to mitigate such biases, but designing effective proposal distributions or potential functions remains a key challenge.<n>We propose a generic approach to construct proposals and potentials for SMC sampling from $p_mathrmlm( cdot mid mathrmconstraint)$.
  arXiv  Detail & Related papers  (2026-06-01T08:58:18Z)
• TENSURE: Fuzzing Sparse Tensor Compilers (Registered Report) [9.083996936429465]
  We present TENSURE, the first black-box fuzzing framework specifically designed for the testing of sparse Compilers.<n>We propose a novel constraint-based generation algorithm that guarantees 100% semantic validity of synthesized kernels.<n>Our evaluation on two state-of-the-art systems, TACO and Finch, reveals widespread fragility, particularly in TACO, where TENSURE exposed crashes or silent miscompilations.
  arXiv  Detail & Related papers  (2026-03-19T00:13:14Z)
• High-Performance Generation of Constrained Inputs [4.837737516460689]
  Language-based testing combines context-free grammar definitions with semantic constraints to generate test inputs.<n>We present a novel approach for evolutionary language-based testing that improves performance by 3-4 orders of magnitude over the current state of the art.<n>We demonstrate this by a case study for a C subset, in which FANDANGO-RS is able to generate 401 diverse, complex, and valid test inputs for a C compiler per minute.
  arXiv  Detail & Related papers  (2025-11-08T12:26:55Z)
• On the Query Complexity of Verifier-Assisted Language Generation [35.43462431990329]
  We develop a framework for reasoning about constrained generation using a pre-trained language model generator oracle.<n>Access to a verifier can render an intractable problem (information-theoretically or computationally) to a tractable one.<n>We show even simple algorithms, like tokenwise rejection sampling, can enjoy significant benefits from access to a verifier.
  arXiv  Detail & Related papers  (2025-02-17T18:46:32Z)
• Exploring Facets of Language Generation in the Limit [10.18252143035175]
  We show that every countable language collection has a generator which has the stronger property of non-uniform generation in the limit.<n>We formalize the tension between validity and breadth in the generation algorithm of [KM24] by introducing a definition of exhaustive generation.<n>We also provide a precise characterization of the language collections for which exhaustive generation is possible.
  arXiv  Detail & Related papers  (2024-11-22T22:13:40Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  We train and evaluate neural networks directly as binary classifiers of strings.<n>We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures.<n>Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Slaves to the Law of Large Numbers: An Asymptotic Equipartition Property for Perplexity in Generative Language Models [0.0]
  We show that the logarithmic perplexity of any large text generated by a language model must converge to the average entropy of its token distributions.<n>This defines a typical set'' that all long synthetic texts generated by a language model must belong to.
  arXiv  Detail & Related papers  (2024-05-22T16:23:40Z)
• Lexinvariant Language Models [84.2829117441298]
  Token embeddings, a mapping from discrete lexical symbols to continuous vectors, are at the heart of any language model (LM) We study textitlexinvariantlanguage models that are invariant to lexical symbols and therefore do not need fixed token embeddings in practice. We show that a lexinvariant LM can attain perplexity comparable to that of a standard language model, given a sufficiently long context.
  arXiv  Detail & Related papers  (2023-05-24T19:10:46Z)
• Locally Typical Sampling [84.62530743899025]
  We show that today's probabilistic language generators fall short when it comes to producing coherent and fluent text.<n>We propose a simple and efficient procedure for enforcing this criterion when generating from probabilistic models.
  arXiv  Detail & Related papers  (2022-02-01T18:58:45Z)
• Zero-Shot Cross-lingual Semantic Parsing [56.95036511882921]
  We study cross-lingual semantic parsing as a zero-shot problem without parallel data for 7 test languages. We propose a multi-task encoder-decoder model to transfer parsing knowledge to additional languages using only English-Logical form paired data. Our system frames zero-shot parsing as a latent-space alignment problem and finds that pre-trained models can be improved to generate logical forms with minimal cross-lingual transfer penalty.
  arXiv  Detail & Related papers  (2021-04-15T16:08:43Z)

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.