BLISP Research Program

AI systems that generate computational pipelines from natural language may propose operations that are structurally valid but semantically unwarranted. This paper presents a grounding gate: a mandatory admissibility boundary between AI-proposed operations and deterministic execution. The system discovers which capabilities match the user's terms by querying a live registry (236 capabilities) and rejects proposals whose names lack discovery evidence. Evaluated on 30 prompts: unwarranted execution reduced from 23.3% to 10.0% (Fisher exact p = 0.027). Replay produces bit-identical hashes across 50 runs. Grounding overhead under 14 ms.

When the generator of computation is stochastic, independently generated programs that represent the same intended computation arrive in different surface forms. This paper presents the canonical execution boundary: an architectural invariant beyond which stochasticity does not propagate. Four mechanisms enforce the boundary: typed specifications, a canonicalization pipeline (278 surface forms to 235 canonical operations), 8-layer execution hashing, and description/identity separation. Evaluated on 1,200 stochastic LLM generations with 50-run replay determinism and provenance stability under registry evolution.

The operational equivalence generated by the system's rewrite rules (alias resolution, argument-order normalization, canonical form selection) forms a congruence: equivalent subexpressions remain equivalent under arbitrary well-typed pipeline composition. This is the central formal result of the program. The resulting quotient category gives precise meaning to deterministic execution identity. Content-addressed hashing serves as a computable operational witness of quotient membership. A projection connects stochastic proposals to their execution classes, with fibers measuring collapse from surface diversity to canonical identity.

Provenance for deterministic execution systems is not metadata but a semantic factorization of execution identity. A provenance map decomposes each execution equivalence class into an 8-layer hash record with declared dependencies. A dependency-indexed composition law establishes that pipeline provenance is determined by stage provenance and the declared dependency map. This enables replay equivalence by hash comparison, divergence localization to specific semantic layers, partial replay of only changed layers, and provenance-preserving registry evolution where discovery aliases are invisible at all eight layers.

Two distinct kinds of variation emerge when stochastic generators propose executable specifications: surface-form variation (absorbed by canonicalization, intra-fiber) and execution ambiguity (changing execution identity, inter-fiber). Across 2,200 proposals with controlled perturbations: synonym rewording stays within fibers (rho = 0.985), metric and family substitutions produce zero same-fiber mass (rho = 0.000) with perfect per-variant stability (sigma = 1.000). The execution adjacency graph is sparse (density = 0.095, 10 connected components). The key finding is that provenance-level changes create clean, stable transitions between execution classes, not noisy instability.

A single 7-valued coordinate (DependencyClass) classifies operations by data-dependency shape and predicts four independent optimizer behaviors—fusion eligibility, window semantics, pipeline position, and state management—with 99.6% accuracy (243/244 behavior predictions, z = 13.0, p < 10⁻³⁸ vs random baseline). The coordinate is not a descriptive label; it is a predictive object that determines execution behavior from semantic structure alone.

A frozen taxonomy trained on 61 operations generalizes to 25 unseen operations at 100% accuracy (100/100 holdout predictions) with zero recalibration. Coordinate ablation confirms that the full coordinate is minimal—removing any single dimension degrades prediction. Random baselines with equivalent cardinality achieve chance accuracy. The result establishes semantic coordinates as predictive objects: they predict optimizer behavior, not merely describe it.

A frozen 8-valued dependency-shape taxonomy, built without inspecting either target system, predicts three execution behaviors (streaming, buffering, warmup) in Polars (Rust, morsel-driven) and DuckDB (C++, push-based). Buffering predictions reach 96.7% accuracy in both systems. Combined accuracy across 180 predictions is 91.1%, with zero errors from incorrect dependency-shape assignments. All errors trace to architectural choices and API conventions, not to the taxonomy itself.

Independent frontier model families (Anthropic, OpenAI, Google), working on independent domains (finance, SQL, build/CI), reconstruct structurally equivalent execution-identity primitives under task pressure. Nine question tiers of increasing difficulty elicit eight primitives: normalization, canonical identity, equivalence classes, grouping, composite rewriting, replay mappings, computation DAGs, and policy checking. 7/8 primitives converge above 0.90 across 55 runs. Reconstruction is convergent, staged, and expensive (~178,000 tokens per reconstruction). A reference implementation materializes the same eight primitives as persistent, composable, domain-portable infrastructure at zero marginal query cost.

Sub-expression caching keyed on data hashes produces silent false hits when the same intermediate data flows through differently parameterized pipeline branches. In a 515-comparison experiment across 9 strategy families, data-hash keying produces 97 false hits (18.8%). Identity-hash keying (MOR_HSH/SRH_HSH) produces zero. The paper proves that safe compositional caching requires the cache key to induce a congruence—an equivalence preserved under composition—on the computation algebra. Data-hash equivalence is not a congruence; canonical equivalence is. This is the theoretical anchor of the program: it characterizes why computation identity works and what breaks without it.

Every production tool-calling protocol treats tool selection as an assertion sufficient for execution. This paper identifies a verification gap and maps the emerging landscape into three layers: post-hoc audit (deployed), policy gates (emerging), and semantic verification (this work). We present the first implemented and empirically evaluated system for runtime semantic verification of AI tool selection, using content-addressed behavioral identity and a runtime grounding wall. In 180 trials, semantic verification reduced uncaught wrong-tool selection from 23.3% to 10.0% (Fisher exact p = 0.027). A 10-system comparison table distinguishes integrity verification (hashing what a tool is) from behavioral verification (hashing what a tool does).