ADR 0001: Reverse Cross generation and solution semantics¶
- Status: Accepted
- Date: 2026-08-27
- Scope: Reverse Cross Phase 3
- Audience: Backend engineers and reviewers of generation correctness or resource bounds
- Implementation snapshot:
jm/string-repetitionata12ff3b; production feature state must be verified operationally
Context¶
Reverse Cross needs an on-demand generator that can use a large shared lexical catalog while remaining responsive and predictable in an Azure Container App. The initial private-beta replica has only 0.5-1 GiB of memory for cost reasons. Recent catalog work demonstrated that whole-document parsing, duplicate projections, and per-entry temporary allocations can exhaust that budget even when the final retained data would fit.
Generation also needs an explicit correctness rule. A generated private solution proves that the public mask and entry bank are solvable, but players may find a different arrangement that obeys all puzzle rules. Proving uniqueness during generation would add search cost without improving the core reconstruction rule.
Decision¶
Fill and mask sequence¶
The first fill candidate will be a native, bounded constraint search over shared catalog entries. Phase 3B will benchmark it against validated fixture masks before Phase 3C adds mask construction. This isolates fill behavior from mask quality and gives the candidate a clear rejection test. We will adopt another search implementation only if measured success rate, latency, memory, or maintainability justifies the added dependency or complexity.
Every emitted puzzle must include a complete private construction witness and pass an independent validator. The public puzzle is derived from the validated result. No partially filled candidate is served.
Completion and alternate solutions¶
The private construction solution is a witness, not an exclusive answer key. A submission is complete when it:
- uses every public bank entry exactly once by stable entry ID;
- fills every maximal Across and Down slot exactly once;
- places each entry contiguously and at exactly the slot's grapheme length; and
- agrees at every crossing and obeys the public mask.
The authoritative backend validator applies those rules without requiring the submitted placement map to equal the stored witness. Generation will not enumerate all solutions or reject a puzzle solely because it has another rule-valid reconstruction. Alternate-solution discovery and analysis are deferred to spoiler-protected God View/editorial tooling. Ambiguity may later be measured as a quality signal, but it is not a Phase 3 correctness invariant.
Bounds, replay, and failure¶
One attempt is identified by the complete versioned options, deterministic seed, generator version, and resolved content version. Options independently bound wall-clock time, mask attempts, search nodes, slot lengths, dimensions, language/profile, and optional quality constraints.
Generation is asynchronous and observes caller cancellation. Time, attempt, and search limits end with distinct structured outcomes. Catalog unavailability, no-fill, validation failure, and cancellation are also distinct. There is no unbounded recursion or retry loop. Phase 3D selects the existing fixture provider as the serving fallback for a disabled or failed feature flag, bounded generation failure, catalog/index failure, or concurrency rejection. Caller cancellation remains terminal and is never converted into a fixture response.
The contract's absolute ceilings are misuse guardrails, not latency targets. Supported presets will receive lower measured budgets where appropriate.
The current production-provider defaults and contract ceilings are:
| Limit | Provider default | Contract ceiling |
|---|---|---|
| Wall-clock budget | 5 seconds | 30 seconds |
| Mask attempts | 25 | 10,000 |
| Search nodes | 100,000 | 10,000,000 |
| Slot length | 3-9 graphemes | Board-dimension bound |
| Concurrent generation attempts | 2 per process | Configuration must remain positive |
flowchart TD
Request["Provider request"] --> Gate{"Concurrency slot available?"}
Gate -->|No| Policy{"Fallback allowed?"}
Gate -->|Yes| Mask["Construct candidate mask"]
Mask --> Fill["Bounded fill search"]
Fill --> Valid{"Complete and valid?"}
Valid -->|Yes| Generated["Return generated candidate"]
Valid -->|No, budget remains| Mask
Valid -->|No, exhausted| Policy
Policy -->|Yes| Fixture["Return fixture fallback"]
Policy -->|No, strict request| Failure["Return structured failure"]
Generated --> Caller["Application layer persists<br/>when the mode requires it"]
Fixture --> Return
Failure --> Return
Caller --> Return["Return provider result"]
Structural-quality strategy addendum (2026-09-03)¶
Mask strategy is a versioned replay input. IndependentV1 preserves the original deterministic
cell-at-a-time behavior. SymmetryPreferredV2 attempts deterministic 180-degree rotational orbits
before deterministic individual-cell fallback. Exact rotational symmetry is not a correctness
invariant and is not required when a paired mutation would prevent reaching a useful legal mask.
The first optional production structural policy requires every playable cell to participate in
both an Across and Down slot and requires exactly one connected open component. It is selected by
the fail-safe ReverseCrossStructuralQuality feature flag only after ReverseCrossGeneration has
admitted the request. A missing, disabled, or failed quality-flag evaluation preserves
IndependentV1 with no quality filter. Disabling the parent generation flag retains the existing
fixture-serving kill switch.
This generation-policy change does not revise reverse-cross-evaluator-v1. Complete evaluator
reports remain separate persistence items, while bounded activity tags expose selected structural
measurements for rollout comparison. Report creation follows the winning puzzle save and is
best-effort rather than transactional; a failed report write is observable but does not make the
playable puzzle unavailable.
Memory and resource sizing¶
The catalog snapshot remains the single owner of lexical entry data. Reverse Cross views and future indexes should reference snapshot entries and compact scalar metadata; they must not clone strings, grapheme arrays, provenance, or the full catalog. Construction should use bounded or pooled scratch state where profiling shows a benefit, and release heavyweight build state before creating final projections.
Evaluation records scalar samples only: outcome, elapsed time, allocations, retained managed-memory delta, process working set, attempts, search nodes, backtracks, and slot count. It reports cold and warm catalog/view/index behavior plus p50, p95, maximum latency, success rate, and failure reasons. Forced-GC retained deltas and process working set are noisy process-level observations, so resource decisions require repeated representative runs and container telemetry, not one local sample.
The initial 0.5-1 GiB allocation is a cost target, not a correctness ceiling. Before increasing it, we will remove avoidable duplicate ownership and transient amplification, then measure baseline runtime, shared catalog/views, peak bounded generation work, representative concurrency, startup, and operational headroom. If the remaining footprint is irreducible and the measured container tail approaches its limit, increasing replica memory is the correct action. We will not trade away boundedness, reliability, catalog quality, or reasonable latency merely to preserve an arbitrary initial allocation.
Phase 3A baseline¶
On 2026-08-27, an isolated Release run on the Windows development workstation loaded pinned catalog
version word-catalog-v1:59247d5c85ec26416bd6362b1eac9daa58318af4e729c12b5a2c22892b958ccb.
It measured 767,019 catalog entries, 378,785 Letter Golf index entries, and 567,657 Reverse Cross
view entries. Post-full-GC managed retention was approximately 572.5 MiB for the catalog, another
198.1 MiB for the Letter Golf index, and another 47.3 MiB for the Reverse Cross view: approximately
817.9 MiB in total. The post-view process working set was 979.0 MiB, and the post-catalog checkpoint
reached 1,157.5 MiB. The run allocated 3,056.1 MiB cumulatively while building these retained views.
This sample rules out 0.5 GiB and leaves no credible operational or generation headroom at 1 GiB. The next production-class validation should therefore use at least the 2 GiB container class, then measure startup, bounded fill, representative concurrency, and tail behavior before adopting that as the final allocation. The values are diagnostic workstation observations, not a claim that 2 GiB is sufficient or a substitute for container telemetry.
Phase 3B known-mask result¶
On 2026-08-28, Phase 3B implemented deterministic MRV backtracking for fixed validated masks. Each attempt independently enforces cancellation, wall-clock time, and search-node limits and returns a structured outcome. Successful candidates pass the existing puzzle/solution validator before they are returned. Fixture tests cover 5x5, 7x7, and 9x9 replay plus no-fill, cancellation, time-budget, node-budget, content-version, mask-validity, and distinct-entry behavior.
The first production-catalog experiment bucketed references only by grapheme length. It retained little additional memory, but repeated bucket scans produced a 5x5 p95 of approximately 2,676 ms and all three 7x7 attempts reached the 10-second limit. That implementation was rejected.
The accepted Phase 3B candidate adds a reusable positional index for lengths 3 through 9. It is
bulk-built with mutable dictionaries and lists, then frozen once into catalog-entry reference arrays
and flat integer posting arrays. It does not create a per-entry map or clone lexical strings,
graphemes, provenance, or entries. This construction deliberately avoids the persistent
ImmutableSortedDictionary insertion cost that previously caused the Letter Golf catalog index to
exhaust memory.
An isolated Release run on the same pinned 767,019-entry catalog indexed 243,643 eligible entries and 1,758,867 positional references in 294.1 ms. Index construction allocated 33.3 MiB and retained approximately 8.7 MiB after full GC; the post-index process working set was 1,006.0 MiB. With seed 1729, a 10-second wall-clock limit, and a 100,000-node limit, three of three attempts succeeded for each fixture. Measured p50/p95 latency was 66.4/69.5 ms for 5x5, 572.2/604.0 ms for 7x7, and 116.4/121.5 ms for 9x9. The largest observed search used 708 nodes and 694 backtracks.
These workstation results accept the native indexed fill candidate for known masks and justify continuing to Phase 3C. They do not validate mask construction, representative concurrency, Azure container startup/tail behavior, or final replica sizing. The 2 GiB class remains the next production-container benchmark candidate rather than a final allocation.
Phase 3C mask-construction result¶
On 2026-08-28, Phase 3C added deterministic mask construction followed by Phase 3B fillability feedback. A seed, zero-based mask attempt, dimensions, slot limits, and optional exact blocked-cell target produce the same candidate. Without an explicit quality target, attempts explore blocked-cell ratios from 8% through 32% in 4-point steps. Candidates reject short or overlong maximal runs and open cells outside a legal Across or Down slot before search. Optional target density, checked-cell ratio, and orthogonal open-cell connectivity are evaluated only when supplied; this phase does not promote historical experiments into product presets.
The first production-catalog run exposed a boundedness defect in the outer policy: the first sparse 9x9 candidate received the complete remaining 10-second budget, so all three seeds timed out on attempt one and later masks were never evaluated. That policy was rejected. The accepted orchestrator allocates each candidate an equal share of the remaining wall-clock and search-node budgets. A local slice timeout or node limit rejects that candidate and feeds back into the next mask, while caller cancellation, invalid options, and validation failure remain terminal. Global limits are checked before another mask is counted, and metrics aggregate all attempted fills.
An isolated Release rerun against the same pinned 767,019-entry catalog and shared Phase 3B index used seeds 1729, 2718, and 3141 for each size, with 25 mask attempts, a 10-second global limit, and 100,000 total search nodes. All nine generations succeeded. The 5x5 p50/p95 was 30.0/40.2 ms with at most one attempt, 14 nodes, four backtracks, and 0.2 MiB allocated. The 7x7 p50/p95 was 432.5/497.2 ms with at most two attempts, 539 nodes, 523 backtracks, and 0.7 MiB allocated. The 9x9 p50/p95 was 991.6/993.1 ms with at most three attempts, 1,040 nodes, 1,017 backtracks, and 3.3 MiB allocated. The post-index process working set remained approximately 1,005.9 MiB; generation's maximum observed process working set was 967.5 MiB, a noisy process-wide sample rather than retained generation memory.
These workstation results accept deterministic mask-first construction with bounded fillability feedback for Phase 3C. They do not select production quality presets, prove concurrency headroom, validate Azure container behavior, or integrate generation into serving and persistence; those remain later work.
Phase 3D serving decision¶
Phase 3D composes generation behind a separate ReverseCrossGeneration server-side feature flag.
The flag is deliberately absent from checked-in settings, so missing configuration and evaluation
failures keep the authored fixture behavior. Enabling generation does not alter the legacy or typed
public response contracts and does not expose the private solution.
When dimensions are omitted, the serving provider deterministically selects a supported 5x5, 7x7, or 9x9 preset from the generation seed. Explicit dimensions remain unchanged. Other startup-validated defaults are five seconds, 25 masks, 100,000 search nodes, slot lengths 3-9, no quality constraints, and two concurrent generations per process. The gate does not queue excess work; it returns a fixture immediately. A successful generated puzzle receives an opaque SHA-256 provider ID derived from the complete serialized replay identity, so changes to any option, content version, or generator version cannot alias the same ID.
The Phase 3B positional index remains reference-only and process-wide. Its provider coalesces builds for the same language, catalog/profile version, and length bounds, atomically replaces a completed older version, and clears failed builds for retry. Index construction does not receive a caller token: individual cancellation ends only that request's wait and cannot poison shared work.
Generation traces contain only scalar replay and outcome data. They include dimensions, seed, language/profile, effective bounds and budgets, quality preset state, content/generator versions, elapsed time, attempts, search nodes, backtracks, and slot count; lexical entries and private witness data are excluded. Production-container load, startup, tail-latency, and memory measurements remain a staged-release requirement rather than an unmeasured claim of Phase 3D.
Consequences¶
- Phase 3A can define contracts and measurement without allocating a production search index.
- Phase 3B establishes a measured native known-mask fill using a bulk-built, reference-only positional index under explicit budgets and replay identities.
- Phase 3C establishes deterministic mask exploration with optional quality constraints and fair, globally bounded fillability feedback across candidates.
- Phase 3D adds a default-off serving switch, fixture rollback path, bounded concurrency, replay-safe telemetry, and one reusable version-keyed positional index without changing public puzzle DTOs.
- Players are not rejected for a valid reconstruction merely because it differs from generation.
- Production completion requires a rule validator rather than equality with private placements.
- Resource increases require reproducible evidence; cost remains visible but does not override safe operation.
- God View must protect private witness and alternate-solution data from normal player APIs.
Revisit triggers¶
Revisit the fill implementation if the Phase 3B matrix misses its agreed success, latency, or memory objective. Revisit uniqueness only if playtesting demonstrates material player harm that cannot be addressed by ranking, editorial review, or God View analysis.