aiqbench analysis
GenOS introduces a formal probabilistic framework to ensure that semantically equivalent prompts yield identical code-generation outcomes in AI agentic workflows, addressing critical robustness gaps where minor text variations alter program behavior distributions. By modeling each workflow layer as a Markov kernel with observer-relative equivalence, the research provides mathematically proven bounds on approximation errors and validates safety under sound validation without relying on assumptions about specific language model parameters. This work advances the theoretical foundations of reliable AI code generation by establishing compositional criteria for safely replacing components within complex agentic pipelines.
GenOS: Compositional Certificates for Semantic Robustness in AI Code Generation
arXiv:2608.03588v1 Announce Type: cross Abstract: AI coding agents are stochastic workflows: prompts are interpreted, artifacts are sampled, validators produce observations, and orchestrators commit or repair. Small prompt or specification changes can therefore alter program-behavior distributions even when the texts appear synonymous. Existing systems evaluate correctness, but lack a compositional criterion for safely replacing a prompt, contract, generator, or program inside a complete agentic workflow. We introduce GenOS, a probabilistic operational semantics for this replacement problem. Each layer is modeled as a Markov kernel, and each interface carries an observer-relative equivalence. We prove that equivalence-compatible kernels descend to quotient classes and that quotienting commutes with distributional extension and sequential composition. Hence, equivalent prompts induce equal probabilities for all downstream equivalence-closed events, including verified commit. We also establish workflow bisimulation, guarded-commit safety under sound validation, total-variation non-expansiveness, and an additive robustness bound that attributes approximation error to individual pipeline layers. An executable insertion-sort audit instantiates the theory with natural-language paraphrases, a formal contract, six programs, two observers, and exhaustive execution on 121 inputs. Equivalent prompts yield identical code-class and commit distributions; a prompt assigning 5% probability to an in-place contract is distinguished by a mutation observer, while downstream distances remain within the predicted bound. Across 20,000 randomized finite-kernel trials, no exact or approximate law is violated. GenOS is model-parametric: compatibility is a measurable property to test, not an assumption about language-model behavior.
Abstract:AI coding agents are stochastic workflows: prompts are interpreted, artifacts are sampled, validators produce observations, and orchestrators commit or repair. Small prompt or specification changes can therefore alter program-behavior distributions even when the texts appear synonymous. Existing systems evaluate correctness, but lack a compositional criterion for safely replacing a prompt, contract, generator, or program inside a complete agentic workflow. We introduce GenOS, a probabilistic operational semantics for this replacement problem. Each layer is modeled as a Markov kernel, and each interface carries an observer-relative equivalence. We prove that equivalence-compatible kernels descend to quotient classes and that quotienting commutes with distributional extension and sequential composition. Hence, equivalent prompts induce equal probabilities for all downstream equivalence-closed events, including verified commit. We also establish workflow bisimulation, guarded-commit safety under sound validation, total-variation non-expansiveness, and an additive robustness bound that attributes approximation error to individual pipeline layers. An executable insertion-sort audit instantiates the theory with natural-language paraphrases, a formal contract, six programs, two observers, and exhaustive execution on 121 inputs. Equivalent prompts yield identical code-class and commit distributions; a prompt assigning 5% probability to an in-place contract is distinguished by a mutation observer, while downstream distances remain within the predicted bound. Across 20,000 randomized finite-kernel trials, no exact or approximate law is violated. GenOS is model-parametric: compatibility is a measurable property to test, not an assumption about language-model behavior.
Programming Languages (cs.PL); Artificial Intelligence (cs.AI); Software Engineering (cs.SE)
F.3.2; F.3.1; D.2.4; I.2.2
arXiv:2608.03588 [cs.PL]
(or arXiv:2608.03588v1 [cs.PL] for this version)
https://doi.org/10.48550/arXiv.2608.03588 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 329 words
Related coverage
[AINews] not much happened today
Latent Space · Sep 10, 2026
Open-Qwen-Music: An Auditable Framework for LLM-Based Music Composition and Diffusion Rendering
arXiv · Sep 29, 2026
Functional Cache Grafting: Robust and Rapid Code-Policy Synthesis for Embodied Agents
arXiv · Jul 31, 2026
Functional Cache Grafting: Robust and Rapid Code-Policy Synthesis for Embodied Agents
arXiv · Jun 12, 2026