Predicate Search Space

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 ten thousand things.

A named predicate can shorten a later search. Once cottagecore has an accepted definition, another search can use the name where it previously had to assemble the expression. What has been saved depends on the grammar and the search limits: a new primitive may make an old possibility accessible without adding anything to the language’s expressive power.

The Question After Certification

The examples supplied by a user do not determine a unique predicate. Several expressions may separate them equally well and behave differently on the next item. A proposal therefore needs both a place among alternatives and an account of its construction. Neither its ranking nor its derivation alone establishes that it is fit for admission.

A20 describes one way to organize this work: a search through typed expressions, using a declared grammar, constraints, scoring rule, witness format and vocabulary-update rule. Learned representations can suggest candidates or supply evaluators within them. The receiving operation still needs to know which expression was proposed, which checks were completed and what the search left unexplored. These are the costs and opportunities behind the narrative in Vol I, Chapter 7, The Witness Protocol.

The Search Space Structure

The same examples can produce different searches under different grammars or authorities. Keeping these choices in A20 makes a rejected candidate distinguishable from one the procedure never considered. It also lets an accepted expression become useful work for a later search rather than remain an isolated answer.

Bounding the Search

A grammar specifies constructions the procedure can explore. Its recursive rules may still generate infinitely many expressions; an executable search needs a boundary of its own.

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)".

A finite search boundary. Suppose derivation depth is limited to d. A finite set of productions, terminals and parameter values together with a finite derivation-depth bound gives a finite enumerable space. A merely discrete parameter set can still be infinite; an inner search over continuous parameters needs its own termination or approximation contract.

A finite space can still be too large to exhaust. Beam width, depth and witness budget determine which part is actually examined, and the result must retain that coverage. An expression outside this grammar remains available to another inquiry; this search has made no judgment about it.

The Search Procedure

The following schematic procedure returns the first successfully checked dossier. It retains proved candidate violations even when other checks remain unfinished.

PredicateSearch(exemplars, context, grammar_fragments, limits):
  primitives = P(exemplars, context)
  candidates, coverage = expand_by_grammar(primitives, grammar_fragments, limits)
  eligible, violations, pending, completed_admission = [], [], [], []
  for c in candidates:
    result = check_hard_invariants(c, I_hard)
    if result is Passed: eligible.append(c)
    if result is Violated: violations.append((c, result.evidence))
    if result is Inconclusive: pending.append((c, result.reason))

  for c in rank(eligible, S).top(limits.witness_candidates):
    w = produce_witness(c)
    result = check_obligations(c, w, context)
    if result is Success:
      completed_admission.append(c)
      search_record = SearchReport(coverage, violations, pending,
                          eligible - completed_admission)
      return PredicateDossier(c, w, result, search_record)
      // Promotion to a primitive requires the separately declared update authority.
    if result is Violated:
      violations.append((c, result.evidence))
      completed_admission.append(c)
    if result is Inconclusive: pending.append((c, result.reason))

  return SearchReport(coverage, violations, pending,
                      eligible - completed_admission)

The successful dossier retains this search record too. Finding one acceptable candidate leaves earlier violations, unfinished checks and unexamined alternatives visible; it does not certify the best candidate or complete the search. A report can establish that particular candidates violated an obligation while leaving the search for an admissible predicate open. A claim that none exists requires complete coverage of the declared finite space and completed checks, or a proof excluding the remaining possibilities. Neither a beam’s exhaustion nor failure among its highest-ranked candidates supplies that conclusion.

An implementation returning several dossiers would continue after the first success and report which candidates it checked. A high score remains a reason to examine a candidate; admission depends on A17’s applicable grounding, compatibility and invariant obligations. Exact gluing enters where its hypotheses and requested guarantee apply.

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.

If pastoral differs between two merchants, using it in a joint cottagecore query may require comparing those meanings or preserving separate evaluations. A13 supplies no price for that work. A declared checking regime can estimate the mappings, evaluations and reviews the query requires; Chapter 19 examines what such an estimate can support.

A Derivation for the Combination

The SCAN experiments of Lake and Baroni¹ tested whether trained sequence models could interpret combinations withheld under particular splits. Poor performance under the relevant splits raised a question about systematic generalization; it did not establish that every neural model lacks rules or that writing a grammar settles how learned primitives behave.

Predicate synthesis can supply a narrower achievement. An expression carries a derivation showing how declared primitives were combined. Once those primitives have evaluations, the composition specifies how to calculate its result. Whether those evaluations capture the intended property remains a question for their evidence.

cottagecore := floral ∧ pastoral ∧ soft_palette

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

The DSL leaves the learned evaluations to be established on their own grounds. 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
• dark_cottagecore requires an expanded expression, unless another abbreviation is available
• The search space has a certain shape

After accepting cottagecore:

• cottagecore is now a primitive
• dark_cottagecore := cottagecore ∧ dark_palette is expressible
• The new primitive changes expression lengths and the candidates reachable within a bounded search

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: An extension claiming logical conservativity must preserve the old-language consequence relation. A changed evaluator or alias has an additional operational contract to meet. A migration witness records an authorized revision’s affected uses; naming the revision does not preserve those uses automatically.

Search Has Costs

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

The grammar identifies operations for a cost estimate: expansion, evaluation, witness checking and any comparison with other views. Depth and primitive count describe the expression; they do not by themselves order runtime or expense. Reused checks, caching and different evaluation methods can change the work required.

A proposed predicate may pass its admission checks while imposing a maintenance burden its expected usefulness does not justify. The decision needs a stated estimate, including the frequency and scope of later uses. Observed checking work can then revise it. Chapter 19 examines what that cost framework can support.

The proposal brings search and maintenance costs into the same decision. Other engineering practices can do this too; the estimates remain conditional on the specified work and may be wrong. Their value is that the expected burden can be examined before a convenient new name becomes a dependency.

What Predicate Search Is Not

This search operates on structured candidates. Learned methods and pattern matching may contribute to their construction. The returned derivation must state how the expression was formed; its existence does not depend on which technology proposed it.

Search need not be exhaustive. A proposal operator or beam can omit a valid candidate. Such a search can establish that it found nothing within its explored subset, not that no admissible predicate exists in the grammar. A derivation certifies how an expression was formed; evaluation is still needed to establish how it performs.

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

A derivation exposes the components of a predicate. A recipient can evaluate the same expression on another item, inspect an unexpected leaf result, or find the uses that may need reassessment when a primitive changes. A learned leaf still needs its own evidence; the tree does not make its interior transparent.

Giving a useful expression a name also changes what the next search can afford to consider. Its definition may add no expressive power and nevertheless save repeated construction and checking. That saving has to be compared with the work of maintaining the new dependency. Chapter 19 follows the expenditure after the convenient name has entered the vocabulary.