Predicate Search Space: Where new predicates come from

The Tao that can be told is not the eternal Tao. The name that can be named is not the eternal name. The nameless is the beginning of heaven and earth; the named is the mother of all things.

This chapter formalizes predicate invention as constrained search, defining A20 (Predicate Search Space) -- a five-component structure indexed by scope and authority that makes the space of expressible predicates enumerable, prunable, orderable, auditable, and evolvable. The five components are: a grammar/DSL that bounds expressiveness, invariant constraints (A18) that prune invalid candidates, a scoring function that ranks admissible candidates by fit and utility, a witness format that requires derivations, and an update rule that lets accepted predicates become primitives for future composition. The chapter resolves touchstone T3 (compositionality) by showing that grammar-driven synthesis produces derivations guaranteeing systematic generalization, and develops the vocabulary feedback loop (A11) as a controlled strange loop stabilized by conservative extension (A17b). The reader seeking the motivating argument for why predicate invention must be structured search rather than unconstrained creativity should consult Vol I, Chapter 7 (The Witness Protocol).

The Question After Certification

Embeddings can propose candidates for equivalence but cannot certify them. That was the lesson of the previous chapter: proposals are cheap, witnesses are expensive, and without witnesses you have correlation dressed as identity.

But a parallel question waits: what proposes candidate predicates?

A common answer is "creativity" or "ML feature learning." But creativity is not an operation; it is a description of an outcome. ML feature learning produces representations, not predicates with derivations and scopes. The Third Mode needs something more structured.

The answer is: search through a constrained hypothesis space.

Consider what happens when a user wants to name a cluster of dresses with a shared aesthetic. The user provides examples. The system must propose candidate predicates that capture the pattern. Where do those candidates come from?

The candidates come from composing existing primitives according to grammatical rules. The space is large but not infinite. It is structured by what the grammar allows, pruned by what the invariants forbid, and ordered by what the scoring function prefers. Neural network representations may inform the proposal step, but the search itself operates on typed candidates with derivations.

The Search Space Structure

Why this structure? Because it makes predicate invention:

• Enumerable: The bounded grammar defines what is expressible
• Prunable: Invariants eliminate invalid candidates
• Orderable: Scoring ranks what remains
• Auditable: Witness format explains each candidate
• Evolvable: Update rule lets vocabulary grow

This is not AI creativity. This is constrained search with receipts.

Grammars Make Search Tractable

Without grammar, the space of predicates is infinite. With grammar, the space is structured. This is not a limitation; it is what makes search possible.

Attribute grammars define predicates by attribute combinations:

P → attr(domain, value)
P → P ∧ P
P → P ∨ P

Example: color(dress, red) ∧ length(dress, midi)

Rule-based grammars define predicates by logical rules over existing vocabulary:

P → base_predicate(args)
P → P₁(x) ∧ P₂(x)
P → ∃y. R(x, y) ∧ P(y)

Example: puffy(d) := voluminous(d) ∧ ¬structured(d)

Measurement grammars define predicates by computation over measurable attributes:

P → measure(attr) θ threshold
P → ratio(measure₁, measure₂) θ threshold

Example: affordable(d) := price(d) / median_price(category(d)) < 0.8

Learned-function grammars define predicates by trained models with provenance:

P → classifier(model_id, input, confidence_threshold)
P → regressor(model_id, input) θ threshold

Example: puffy_v2(d) := classifier(puffy_model_v2, features(d), 0.7)

Learned predicates are not a loophole in the formalism. They require a witness format that maintains discipline: model_id, training distribution summary, evaluation set with metrics, calibration curve, known failure modes, and declared scope.

The grammar determines what distinctions can be expressed. Different domains may use different grammars. A fashion catalog might favor attribute and measurement grammars. A knowledge base might favor rule-based grammars. A hybrid system might use all four.

The choice of grammar is a design decision, not a metaphysical commitment. But it is not arbitrary. The grammar shapes what predicates are easy to express and what predicates require deep derivations. A grammar that lacks disjunction cannot express "sustainable := organic_material ∨ certified(GOTS) ∨ certified(OEKO_TEX)" directly. A grammar that lacks quantification cannot express "all_reviews_positive(product) := ∀r. review(r, product) → positive(r)".

Boundedness makes search tractable. Derivation depth is limited to d. Continuous parameters (thresholds, ratios) are drawn from discrete typed parameter sets or searched in a separate inner loop. Without boundedness, the space is infinite; with it, the space is finite and enumerable.

Grammar is the first constraint. It determines the boundary of the expressible. Everything inside that boundary is a candidate; everything outside is not even a hypothesis.

The Search Procedure

Search is not a metaphor but an algorithm with steps.

PredicateSearch(exemplars, context, grammar_fragments):
  
  // 1. PROPOSE: Use A19 to generate typed terminals and partial programs
  //    (e.g., floral, soft_palette, price/median_price < t) with scores
  primitives = P(exemplars, context)
  
  // 2. EXPAND: Grammar-driven composition (beam search)
  candidates = []
  for depth in 1..d:
    candidates += expand_by_grammar(primitives, grammar_fragments, depth)
  
  // 3. PRUNE: Apply A18 hard invariants
  valid_candidates = []
  for c in candidates:
    if satisfies_hard_invariants(c, I_hard):
      valid_candidates.append(c)
  
  // 4. SCORE: Compute S(p) for each valid candidate
  scored = [(c, S(c)) for c in valid_candidates]
  scored.sort_by(score, descending)
  
  // 5. WITNESS: Produce witness for top candidates
  for c in scored.top(k):
    w = produce_witness(c)  // derivation + exemplars + provenance
    
    // 6. ACCEPT: Check A17 obligations + A17b conservativity
    result = check_obligations(c, w, context)
    if result.success:
      // 7. UPDATE: V ↦ V′
      vocabulary.add(c, w)
      return PredicateDossier(c, w)
  
  return ObstructionWitness(best_failure_reason)

This is a canonical skeleton. Implementations may use beam search, MCTS, synthesis-by-examples, or other methods for the expand step. The structure matters more than the algorithm.

Return behavior: In practice the system returns the top-N PredicateDossiers plus the top obstruction witnesses for failures, so humans or agents can choose among certified candidates or understand why search failed.

Search generates candidates; A17 certifies acceptance. A high-scoring candidate may still fail the three obligations (local grounding, overlap agreement, invariant preservation). The search procedure incorporates these checks, but the conceptual separation matters: search explores the space; certification validates the result.

Constraints Prune and Score

Constraints from A18 interact with grammar to shape the search space.

Hard constraints eliminate candidates:

• Type violations: puffy : Dress → String is not well-typed
• Invariant violations: candidate forces existing invariant violation
• Authority violations: candidate claims scope beyond authority

Soft constraints score candidates:

• Complexity penalty: simpler predicates preferred
• Narrowness penalty: predicates that apply to < 1% of items penalized
• Coherence cost: predicates with high reconciliation burden penalized

The scoring function is policy, not semantics:

S(p) = α · fit(p; E⁺, E⁻) + β · value(p) 
       - λ_c · complexity(p) 
       - λ_h · coherence_cost(p)
       - λ_n · narrowness(p)

Where:

• fit(p; E⁺, E⁻): Measures how well p separates positive from negative exemplars (measurable loss)
• value(p): Expected downstream utility (query frequency × saved cost, or business value)

Different deployments may weight these factors differently. A research environment might tolerate high complexity for high utility. A production catalog might penalize complexity heavily. A compliance system might weight invariant satisfaction above all else.

The scoring function is tunable precisely because there is no universal "best" ordering. What counts as a good predicate depends on what you are trying to do with it. The structure of A20 makes this explicit: S is a parameter, not a constant.

Coherence cost integration (A13): A predicate whose evaluation depends on view-local primitives accrues overlap reconciliation cost proportional to its use of non-glued components. If pastoral is defined differently by Merchant A and Merchant B, then cottagecore := floral ∧ pastoral ∧ soft_palette inherits that reconciliation burden. Chapter 19 develops this cost model fully.

T3: Compositionality Resolved

T3 (Compositionality) is the SCAN-style systematic generalization problem. "Add jump" means combining "add" and "jump" compositionally, even if that combination never appeared in training.

The failure mode: Neural networks interpolate without systematic rule. They produce outputs that look right but have no derivation. When novel combinations appear, they fail because they memorized patterns rather than learning composition.

The SCAN dataset(Baroni 2018)Brenden M. Lake and Marco Baroni, "Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks," in Proceedings of the 35th International Conference on Machine Learning (ICML 2018), 2873–2882.View in bibliography famously surfaces this failure mode under certain generalization splits: models trained on "jump" and "walk left" fail on "jump left" because they learned correlations, not composition rules. They have no representation of "left" as an operator that can apply to any action.

The resolution: Predicate synthesis under grammar produces derivations. The derivation shows how primitives combine. Novel combinations succeed if they follow the grammar, regardless of training data.

cottagecore := floral ∧ pastoral ∧ soft_palette

Derivation:
  cottagecore : Dress → Bool
  └── ∧
      ├── floral : Dress → Bool        [primitive]
      ├── pastoral : Dress → Bool      [primitive]
      └── soft_palette : Dress → Bool  [primitive]

Important clarification: The DSL does not eliminate learning. It relocates learning to primitives and acceptance. Grammar guarantees systematic composition once primitives exist; the vocabulary feedback loop (A11) and the proposal operator (A19) handle acquiring primitives in the first place.

The Vocabulary Feedback Loop

When a predicate is accepted, the vocabulary changes. This is A11 in action.

Before accepting cottagecore:

• cottagecore is not a primitive
• Predicates like dark_cottagecore cannot be expressed
• The search space has a certain shape

After accepting cottagecore:

• cottagecore is now a primitive
• dark_cottagecore := cottagecore ∧ dark_palette is expressible
• The search space has grown; new compositions are possible

This is the vocabulary feedback loop:

observations → candidate predicate → search → acceptance →
  → updated vocabulary → new candidates possible → ...

The loop is a controlled strange loop (Interlude II-A). The system's vocabulary affects what distinctions it can make, which affects what predicates it can propose, which affects its vocabulary.

What "acceptance" means:

(i) Definitional extension: The new predicate is defined in terms of prior vocabulary. cottagecore := floral ∧ pastoral ∧ soft_palette is conservative by construction; it introduces no new Σ-consequences beyond what the definition entails.

(ii) New measurement/learned operator: The new predicate introduces a new evaluation method (sensor, classifier, oracle) with provenance. This is not definitional, but still conservative over the old language if it introduces no new Σ-consequences. If the system aliases an existing symbol to the new operator, that triggers operational breaking change per Chapter 16.

Acceptance artifact: Acceptance produces a PredicateDossier = {spec, witness, invariant_report, conservativity_report, scope, authority}.

The distinction matters for migration: definitional extensions can always be expanded inline; new operators cannot.

Stabilization: The loop must be stabilized by conservative extension (A17b). New predicates cannot contradict old truths without migration witnesses. The loop is strange but not chaotic.

This is the key insight from Interlude II-A applied to predicates. The system can observe, name, and then observe differently because it has new names. But the naming does not corrupt existing truths. It extends the vocabulary; it does not revise the history. When revision is required (a new operator replaces an old one), the migration witness makes the change explicit.

Search Has Costs

Search is not free. Enumerating candidates, checking constraints, computing scores, producing witnesses: all have computational and organizational costs.

The search space structure lets you estimate costs before committing:

• How deep is the derivation? Deeper = more expansion steps
• How many primitives are involved? More = more constraint checks
• What is the coherence cost? Higher = more reconciliation burden

A predicate with high coherence cost may not be worth inventing even if it passes all constraints. The utility must outweigh the ongoing maintenance burden.

Chapter 19 develops this: coherence costs money. The scoring function previews that cost; Chapter 19 makes it operational.

The search space structure provides the machinery to estimate costs before committing. Derivation gives a prior estimate (structure-based): count the non-glued primitives, estimate the reconciliation burden, multiply by expected query frequency. Empirical conflict rates update this estimate as the predicate is used. If the cost exceeds the utility, the candidate is admissible but not advisable.

This is the discipline that separates the Third Mode from "just add features." In the embedding empire, features are cheap to add and expensive to maintain. In the schema empire, features are expensive to add and cheap to maintain. In the Third Mode, you can estimate both costs before committing.

What Predicate Search Is Not

Search is not free association. The grammar constrains what can be expressed. You cannot "just think of" a predicate outside the grammar's expressiveness.

Search is not pattern matching. Embeddings find similar items; they do not produce typed predicates with derivations. Embeddings inform proposals; search operates on structured candidates.

Search is not enumeration. The proposal operator narrows the space; beam search explores promising directions; pruning eliminates dead ends.

Search is not one-shot. The vocabulary feedback loop means today's search depends on yesterday's acceptances. The search space is shaped by its own history.

Search is not validation. Search produces candidates; A17 certifies them. Many high-scoring candidates should not be accepted.

Consequence

Predicate invention is search, not magic. The search space is structured by grammar, constrained by invariants, scored by utility, and updated by acceptance.

T3 is resolved: compositional predicates have derivations that show how primitives combine. The system can handle novel combinations because the grammar, not the training data, determines what is expressible.

The vocabulary feedback loop (A11) means search is dynamic: today's accepted predicates become tomorrow's primitives. The search space grows as vocabulary grows, enabling increasingly sophisticated compositions.

The derivation is the artifact that makes this work. It is not enough to have the right predicate; you must have the right predicate with a derivation showing how it was constructed. The derivation enables:

• Explanation: Why does this dress match the predicate? Trace the derivation.
• Generalization: What other dresses might match? Anything satisfying the leaf primitives.
• Maintenance: What happens if a primitive changes? Recompute affected derivations.
• Composition: What new predicates can be built? Anything using this predicate as a primitive.
• Debugging: Why did this predicate fail on this item? Check which leaf primitive returned unexpected value.

Without derivations, predicates are black boxes. With derivations, predicates are transparent compositions that can be inspected, explained, and evolved.

The search has costs. Enumerating, pruning, scoring, witnessing: each step has a price. Chapter 19 asks the next question: given that search has costs and coherence has costs, how do you decide what is worth the cost? When does vocabulary extension pay for itself?