Vernier/SOLVER.md

Sketch Constraint Solver Spec

Status: v2. The draft's adversarial review confirmed two findings (singular damping on untouched parameters; auto-constraints missing from scope) before session limits truncated verification of the remaining claims — those were triaged empirically during implementation instead, and every behavioural claim below is enforced by a named fixture. The amendments log at the bottom records what changed and why.

The locked decision (brief §3): own solver, sparse Jacobian + Levenberg–Marquardt. Phase 2 gate: a fully-constrained sketch does not move when dragged; solve < 5 ms at 200 constraints (release build). vernier-solver has zero kernel dependencies and no dependency on vernier-doc; the document stores its own sketch model and converts at the boundary (Phase 3).

1. Model

A sketch is a pool of parameters (all f64, millimetres and radians) owned by entities, plus constraints referencing entities:

• Point { x, y } — 2 params.
• Line { start: PointId, end: PointId } — 0 own params (geometry lives in the points).
• Circle { center: PointId, radius } — 1 own param.
• Arc { center: PointId, start: PointId, end: PointId } — 0 own params, plus one internal constraint |start−center| = |end−center| generated automatically (an arc is well-formed only with it).

Entities and parameters are identified by index-free ids allocated by the sketch (PointId, EntityId — solver-local, monotonic; the doc maps them to its own ids in Phase 3). Parameter vector order is allocation order — deterministic because sketch construction order is part of the input.

2. The twelve constraints, plus five added since

Residuals are dimensionally consistent: lengths in mm; angular relations via cross/dot products of unit-normalized directions, scaled by a characteristic length L (the sketch bounding-box diagonal, min 1 mm) where needed to keep all residuals commensurable in mm. L is frozen at solve entry — a live scale would make the Jacobian inconsistent with its own residuals (S1 catches this).

#	Constraint	Residual(s)	DOF removed
1	Coincident(a, b)	a.x−b.x, a.y−b.y	2
2	Horizontal(line)	end.y−start.y	1
3	Vertical(line)	end.x−start.x	1
4	Distance(a, b, d)	`	a−b
5	PointOnLine(p, line)	`cross(end−start, p−start) /	end−start
6	Parallel(l1, l2)	cross(d̂1, d̂2) · L	1
7	Perpendicular(l1, l2)	dot(d̂1, d̂2) · L	1
8	EqualLength(l1, l2)	`	l1
9	Angle(l1, l2, θ)	atan2(cross(d̂1,d̂2), dot(d̂1,d̂2)) − θ, wrapped to (−π, π], scaled by L	1
10	Radius(circle, r)	radius − r	1
11	TangentLineCircle(line, c)	`	cross(d̂, center−start)
12	Lock(p, x₀, y₀)	p.x−x₀, p.y−y₀	2

A thirteenth kind, ArcRadiiEqual(centre, start, end) — residual |start−centre| − |end−centre| — is internal and not user-facing: Sketch::add_arc adds exactly one per arc to keep the arc circular, and nothing else may construct it. It is why an arc costs 5 DOF (six point parameters less one internal row) rather than 6. Constraints 10 and 11 (Radius, TangentLineCircle) accept an arc wherever they accept a circle; an arc's radius is the derived length |start−centre|, so its gradient flows to two points instead of one parameter column.

Constraints 13–17, added to close FUSION_LOG's constraint-vocabulary entry. Same residual idiom as the twelve above — lengths in mm, no new scaling convention — so S1's finite-difference check covers all five at one non-degenerate probe alongside the original twelve.

#	Constraint	Residual(s)	DOF removed
13	Midpoint(p, line)	p − (start+end)/2, x and y	2
14	Collinear(a, b)	PointOnLine's residual applied twice — b.start and b.end each against a's carrier	2
15	Concentric(a, b)	Coincident applied to the two curves' centres	2
16	Symmetric(a, b, axis)	midpoint((a+b)/2) on axis's carrier; (a−b)·d̂	2
17	TangentCircles(a, b, external)	`	centre_a−centre_b

Two things worth recording about these five, beyond the table:

• Collinear and Midpoint don't invent new math — both reuse the exact PointOnLine residual (point_on_line_row in the implementation), applied to a derived point (Midpoint's target is a stored point but the gradient pattern is identical) or applied twice (Collinear). Neither needed a new closed form.
• TangentCircles is arc-aware for free, the same way Radius and TangentLineCircle are: it goes through the same curve_center/ curve_radius helpers, so a circle and an arc are interchangeable wherever this constraint takes either.

TangentCircles is solver-complete but not document-reachable — the same status TangentLineCircle has had since M1. Its external: bool needs the same treatment Side does: chosen once from live geometry at command time, not re-derived by the throwaway solve solve_sketch builds per call (§3's determinism requirement — invariant #1). Unlike Side it has no solver-internal type to mirror into vernier-doc (bool already serializes), so only the "decided at command time" half is the blocker, but it is real, and it is the same later-milestone design question TangentLineCircle already carries, not a new one to improvise here.

Degenerate guards: unit directions d̂ require |end−start| ≥ ε_len (1e-9 mm); a degenerate line in any constraint is a solve error (DegenerateEntity), not a silent skip.

3. Solve: sparse Jacobian + Levenberg–Marquardt

• Residual vector r(x), analytic Jacobian J stored as sorted triplets (constraint-major, parameter order within a row) — sparse in storage, deterministic in iteration.
• Normal equations (JᵀJ + λ·max(diag(JᵀJ), 1e-12)) δ = −Jᵀr, solved by profile (skyline) LDLᵀ over touched parameters only. max(diag(JᵀJ), 1e-12) is a scalar — the maximum over the whole diagonal, floored — and λ multiplies that one number uniformly across every column. It is not the element-wise textbook Marquardt form λ·diag_i. The formula was ambiguous as first written and was implemented per-column; see §9 and MISTAKES.md for what that cost. Uniform damping is the right reading for this solver specifically, because §2 constructs every residual to be commensurable in mm, so a single scale speaks for the whole system. Parameters no constraint references are excluded from the factorization (they would otherwise be exactly singular under element-wise damping — confirmed review finding; under the scalar damping above they would merely be damped noise, but excluding them is still correct, since they are free DOF and not unknowns of the solve) and count directly as free DOF. Allocation order clusters connected geometry near the diagonal, keeping the profile narrow; a dense factorization missed the §6 gate by 8×, the profile one beats it by 7×.
• λ schedule: start 1e-3; accept step if ‖r‖² decreases → λ /= 3; reject → λ ×= 10, retry (max 8 rejects per iteration). Convergence: ‖r‖_∞ < 1e-9 (converged) or ‖δ‖_∞ < 1e-12 (stalled → check residual: small = converged, large = NoConvergence). Iteration cap 100 → NoConvergence.
• Determinism: fixed evaluation order everywhere, no randomness, no parallelism inside the solve. Same sketch + same start → bit-identical result and iteration trace.
• All diagnostics carry constraint ids, never row indices.

4. Degrees of freedom and diagnostics

After (attempted) solve, rank analysis of J at the solution via Householder QR with column pivoting (threshold τ = 1e-8 · ‖J‖):

• dof = free_params − rank(J).
• Well-constrained: dof = 0 and converged.
• Under-constrained: dof > 0 and converged (report dof).
• Over-constrained: rows exceed rank — report the dependent constraint set (constraints whose rows fall outside the pivoted row basis). The set names candidates, not a verdict on which single constraint is "guilty" — attribution beyond the dependent set is a recorded non-goal for Phase 2. Two sub-cases: redundant (converged anyway — dependent but consistent) and conflicting (residual of a dependent row stays above tolerance → the sketch is unsatisfiable). Conflicts are reported with the conflicting constraint ids; the solver never returns converged-to-garbage — if ‖r‖_∞ ≥ 1e-9, the status says failed.
• Lock constraints participate in rank like any other rows.

5. Drag

Dragging point p toward target t = bounded-step continuation: p advances toward t in steps no larger than 0.05·L, re-solving after each (constraints hard, no drag residual), stopping when the target is reached or the constraints refuse further progress. A single hard p := t jump was the v1 design and is wrong twice over, empirically: a far drag can converge into a different discrete solution (the mirrored rectangle satisfies every constraint — the gate property would fail), and an under-constrained solve from a far start splits the difference instead of following the cursor. Bounded steps keep the solve in the original basin and track the target.

• Fully-constrained sketch: every step snaps back, so the sketch does not move — the gate property, structurally rather than by luck.
• Under-constrained: the dragged point tracks t along the manifold.
• Drag of a locked point: the Lock rows win; the point never leaves.
• Per-frame drags continue from the current (solved) state — the API is stateless beyond the sketch itself.

5b. Auto-constraints (brief Phase 2 row)

Inference is a pure, deterministic solver function, not a UI behaviour: infer_line_constraints(sketch, line, tolerances) proposes, in fixed rule order — axis snap (Horizontal/Vertical), endpoint coincidence (nearest, ties to lower id), parallel/perpendicular against earlier lines (skipped when both are axis-snapped) — under fixed default tolerances (2°, 0.5 mm). Inferred constraints reach saved documents, so inference falls under invariant #1; the UI's only role (Phase 5) is choosing whether to apply the proposals.

Extended (M3-1) to arcs and circles, as two more pure functions with the same contract: infer_arc_constraints and infer_circle_constraints, in fixed rule order — concentric (nearest earlier centre), endpoint coincidence (arcs only), tangent-to-line (side decided once, never re-derived), tangent-to-circle (external/internal decided once) — and looking only at STRICTLY EARLIER entities, which is what makes a rule stable when several curves are committed at once: an "all but self" reading has a hexagon's edge 0 propose Parallel{0,3} and edge 3 propose Parallel{3,0}, two different values naming one relation that no dedup by value can see. Endpoint coincidence is the exception and is not restricted that way, because a point id has no ordering relation to a curve id. Equal-radius is deliberately NOT proposed: SketchConstraint has no such kind, and the solver's ArcRadiiEqual is internal to add_arc. Ordering is by rule then ascending entity id, and is asserted under entity permutation, because inferred constraints reach saved documents (invariant #1).

The rules are a LIBRARY, not a policy: the app's commit path additionally refuses to propose what the sketch states verbatim, refuses to relate a primitive's curve to another curve of the same primitive, and drops any proposal whose trial solve makes the sketch Redundant.

And the CLICK SNAP subsumes two of the rules. DRAW_SNAP_MM is 2 mm and the inference distance tolerance is 0.5 mm, so a click near enough to infer Coincident or Concentric has already reused the existing point and the relation holds by IDENTITY — there is nothing left to constrain. Both rules stay reachable through a drag or a solve, and the hover glyph is unaffected; what changes is what a drawing gesture can be said to demonstrate. Two of M3 lane A's own tests were asserting those rules through a gesture that cannot exercise them, and were green on a constraint that made the sketch Redundant. Whether the two tolerances should be related at all is an open question, recorded in FUSION_LOG rather than answered here.

6. Performance budget

Gate: < 5 ms for a solve at ≥200 constraints, release build, on the dev machine — measured 2026-08-09: 692 µs at 287 constraints / 288 params from the perturbed grid start (the fixture code is the normative definition of the start state). Measured by a #[ignore]d release-mode benchmark test with a documented fish one-liner; CI runs the same sketch for correctness only (debug-build timing is not asserted). The 200- constraint fixture is a generated rectangular grid of connected, dimensioned rectangles — representative connectivity, not a pathological chain.

solve() is what this budget measures and what the #[ignore]d gate asserts. analyze() — which vernier_doc::solve_sketch runs on every compile, adding a dense rank pass over the same system — is measured by vernier-cli --bench (solver-analyze-287, the same §6 grid). Its number and the date it was taken are in crates/vernier-cli/src/bench.rs's module doc; as of 2026-09-06 it is ≈15 ms release, roughly twenty times the solve it wraps, which is a cost §6's budget never covered.

7. Fixtures (all headless, in-crate)

• S1 unit: each constraint's residual zeroes on a satisfying configuration and its analytic Jacobian matches finite differences (1e-6 relative) at random-free deterministic probe points.
• S2 property: a fully-constrained rectangle (4 lines, coincident corners, H/V, two distances, one lock) has dof = 0 and does not move under drag of any point (max displacement < 1e-6 mm — the residual tolerance bounds constraint violation, not parameter displacement, so the displacement bound is conditioning-aware) — the gate.
• S3 property: removing one dimension → dof = 1, drag moves the sketch consistently (constraints still satisfied after drag).
• S4: duplicated distance with a different value → Over-constrained / conflicting, naming the guilty pair; same value → redundant, still solvable.
• S5: near-degenerate line (1e-12 mm) → DegenerateEntity, no NaNs anywhere (asserted).
• S6 determinism: identical solve twice → bit-identical parameter vector and iteration count (selftest check drives this cross-process). Bit-identity is guaranteed per build; across machines/libc versions, libm (atan2, sqrt) may differ in final bits, so cross-machine comparisons are threshold-based like render goldens.
• S7 scale: the §6 grid at 200 constraints converges, dof correct.
• S8 visual: vernier-cli --sketch-debug <fixture> <out.svg> renders entities, constraint glyphs, and residual vectors as deterministic SVG bytes — the solver debug visualiser the brief prescribes for the morale trough, headless-first.

8. Open questions (to settle in review)

• Angle-residual scaling: L-scaled radians keep rows commensurable but couple the angle tolerance to sketch size; alternative is unscaled radians with a per-row weight. Proposed: L-scaled, revisit on S7 evidence.
• Whether under-constrained drag should add a tiny regularization pull toward the pre-drag state of other points (Fusion-like "minimum motion feel") or rely purely on warm-start LM behaviour. Proposed: warm start only, evaluate by hand with S8 SVGs.
• Conflict attribution quality: QR-pivot dependent-set reporting can name a redundant constraint rather than the intuitively guilty one; acceptable for Phase 2, revisit with real sketches.

9. Amendments (implementation + review, 2026-08-09)

• Scalar damping (§3, M1a): λ·max(diag(JᵀJ), 1e-12) was implemented element-wise. A parameter that a constraint touches with a near-zero partial then gets damping proportional to that near-zero, and the solve reports NoConvergence on satisfiable geometry — an arc endpoint directly above its centre, or two EqualLength points on an axis. Disambiguated to the scalar reading; fixture axis_aligned_equal_length_still_converges is written in pre-arc constraints because the defect was never arc-specific. The §6 perf gate improved from 692 µs to 383 µs at 287 constraints (fewer rejected steps). infer::tests::nearly_horizontal_line_snaps_and_solves_flat asserted a coordinate at 1e-9 that stacks two residual tolerances; it now asserts the inferred constraint's own residual and bounds the coordinate at 2×, which is what convergence actually promises.

• Arcs (§1, §2, M1a): Entity::Arc { center, start, end } with all three as ordinary solver points, plus the internal ArcRadiiEqual row above. A collapsed arc (|start−centre| == 0) is EvalError::Degenerate, matching Distance and line_geom, rather than a zeroed gradient — the radial direction is undefined there, and the shared radial() helper returns None before any division, so no NaN is reachable.

• Frozen L (§2): live scale broke the Jacobian/residual consistency; caught by S1 on first run.

• Reduced skyline factorization (§3): fixes the confirmed singular-damping finding structurally (untouched params never reach the factorization; regression fixture: rectangle + stray point) and the 8×-over-budget dense solve (39 ms → 692 µs).

• Continuation drag (§5): replaces single-shot warm start after S2 empirically flipped a rectangle into its mirror under a far drag.

• Auto-constraints specified and implemented (§5b): the review's second confirmed finding — the brief's Phase 2 row item was silently missing from the draft.

• S2 displacement tolerance 1e-6 and "guilty pair" softened to dependent-set reporting (§4, S4) — honest to what rank analysis provides.

• Review-verification caveat: 26 verifier agents were lost to session limits; their finder claims were triaged empirically (each fix above carries a fixture) rather than adversarially verified. Re-review at the Phase 3 boundary if sketch-solver interaction shows anomalies.