Reducer scales as O(k²) for non-fixed-point iteration: lazy argument reduction in tail recursion

[kumavis]

Summary

A function that recurses by passing an unreduced expression as its accumulator parameter forces the reducer to redo the full term-tree walk on every iteration. For an iteration of depth k whose intermediate values differ at every step, this scales as O(k²) instead of the expected O(k) — even though the algorithm is structurally O(k). With float-like types (Posit32) where every step introduces tiny rounding so the accumulator never collapses to a shared value, the blowup is severe enough that small workloads (n=4, k=4) take ~15 s of pure reduce time and deeper iteration becomes intractable.

This is pitfall #11 in docs/tracking/2026-04-23_eigentrust_pitfalls.md and is the dominant reason the surface-language EigenTrust variants are ~500 000× slower than plain Racket on the same algorithm (see docs/tracking/2026-04-23_eigentrust_comparison.md).

Reproducer

;; Tail-recursive iterator that passes the unreduced step result as
;; the new accumulator — exactly the shape of EigenTrust, gradient
;; descent, fixed-point iteration, etc.
spec eigentrust-iterate
  [Vector Posit32] [List Posit32] Posit32 Posit32 Int [List Posit32]
  -> [List Posit32]
defn eigentrust-iterate [c p alpha eps budget tnew]
  match [int-le budget 0]
    | true  -> tnew
    | false ->
      ;; *** the load-bearing line — argument is NOT pre-reduced ***
      [eigentrust-iterate c p alpha eps [int- budget 1]
                          [eigentrust-step c p alpha tnew]]

Per-iteration the reducer sees a deeper unreduced spine each round, has to re-walk the entire chain to refine the leaf, then match re-walks it again to inspect the head. With Posit32 arithmetic where each step introduces ~1 ulp of rounding, the spine never collapses across iterations.

Concrete measurements (W3 reference workload — ring-4, α=0.3, k=4)

Variant	reduce_ms	vs math	Notes
Plain Racket flonum	~0.03 ms	1×	Direct flvector arithmetic
Racket on propagators (float)	~0.10 ms	~3×	Cell + BSP overhead, same kernel
Prologos (List + Posit32)	15 047 ms	~500 000×	Pure reduce_ms for one W3 expression — elaboration/type-check/qtt/zonk excluded

Higher k blows up further:

• List+Rat at fixed-point (uniform M, p=uniform) k=10: ~36 s — the term tree collapses to a single repeated value, so this is "only" O(k)
• List+Posit32 at fixed-point (uniform M, p=uniform) k=10: does not terminate within 2 min — Posit32 rounding prevents term-tree collapse
• List+Posit32 on asymmetric 3×3, k=5: does not terminate within 3 min

What this is and isn't

Is: an architectural property of the current reducer. Tail-recursive accumulators are reduced lazily; deep iteration with non-collapsing intermediate values redoes the full chain at every level.

Isn't:

• A bug in the algorithm — eigentrust-iterate is correct and the same shape any FP language uses
• Specific to Posit32 — Rat hits the same blowup whenever intermediate values differ; Posits just never collapse, so they always trigger it
• An issue with surface syntax / parser / elaborator — pure reducer behavior. The other phases (elaborate, type-check, qtt, zonk) sum to ~1.5 s on the W3 workload, ~100× smaller than reduce.

Workaround (current)

Rewrite the iterator to converge in 1–2 rounds and exit via the eps-comparison branch (current eigentrust-iterate's shape). For workloads that genuinely need deep iteration with rounded arithmetic, there's no workaround at the surface — reduction time blows up regardless of matrix size.

Suggested fix paths

Several options, ordered by surface impact:

1. Force argument reduction at the recursive call site

Add a seq / force / whnf primitive (or a defn-attribute marker) that the user can apply to the accumulator argument to request strict reduction before the tail call:

[eigentrust-iterate c p alpha eps [int- budget 1]
                    [force [eigentrust-step c p alpha tnew]]]

The reducer evaluates the argument to WHNF (or NF) before binding into the recursive call's parameter. This pushes the cost forward — each iteration pays O(spine of one step) instead of O(spine of all prior steps).

Pros: small surface; user-controllable; no implicit policy change.
Cons: user has to know to add it; ergonomics of "you must annotate the recursive call" is poor.

2. Reducer auto-detects strict positions in tail calls

When a parameter is consumed strictly by the body (matched, projected, or arithmetic-applied without intermediate sharing), the reducer evaluates the argument to WHNF before substitution. This is essentially the demand analysis Haskell's STG does.

Pros: zero user-visible change; handles the common case.
Cons: requires a strictness analysis pass; risks changing termination behavior of currently-correct programs. Needs careful design.

3. Aggressive normalization for primitive-typed values

Whenever a step result has type Posit32, Rat, List Posit32, [Vector Posit32], etc. — types that are bit-pattern values — eagerly normalize results to their canonical form ([posit32 N], '[lit lit ...]) before they become accumulator arguments. The reducer already knows these types; this is a targeted policy change.

Pros: no user-facing surface; surgical fix targeted at the load-bearing case.
Cons: doesn't help for user-defined value types; "primitive" gets hard to define cleanly across the codebase.

4. Memoize / share the argument expression

When the same expression is referenced from the recursive spine, the reducer could share its reduction. This is the standard call-by-need / thunk-update approach.

Pros: principled; makes the surface program O(k) without any user-visible change.
Cons: largest surface — affects every reduce path, not just iteration accumulators. Significant ROC impact.

Scope

• In scope (this issue): track the architectural problem, document its impact, decide which fix path to pursue
• Out of scope: the actual implementation — design doc + targeted track when scheduled

Why this matters

Iteration with rounded arithmetic is the most basic workload of any numerical algorithm — eigenvalue solvers, PageRank-like algorithms, neural-net forward passes, ODE integrators. The O(k²) reducer blowup makes Prologos unable to run any of these at meaningful sizes today. Closing this gap is the single highest-leverage change for the surface variant's wall-clock-on-numerical-code story.

References

• Pitfall memo: docs/tracking/2026-04-23_eigentrust_pitfalls.md § 11 ("Lazy argument reduction makes deep iteration scale as O(k²)…")
• Comparison doc: docs/tracking/2026-04-23_eigentrust_comparison.md (~500 000× math-vs-Prologos-math gap; reducer named as the bottleneck)
• Reproducible measurement: racket/prologos/benchmarks/comparative/eigentrust-list-posit-w3only.prologos (single W3 expression, isolates reduce_ms from W1/W2/other workloads)
• Branch with the measurement infrastructure: claude/eigentrust-prologos-implementation-JGszt
• Related upstream goal: "Prologos network" axis (compile surface code to a propagator network instead of evaluating through the reducer) — see comparison doc § "What this tells us about the layered design"

Priority

High. The reducer blowup is the dominant cost on every numerical workload we care about and is the gating issue between Prologos's surface-language story and "you can write real numerical code in Prologos."