Ctrl-G × NWA — characterization matrix

One method, one protocol, zero per-task tuning: where does NWA-constrained decoding with an HMM guide work, and why.

NWA = nested-word automaton: a finite automaton augmented with a call/return stack, so it recognizes unbounded balanced nesting (parentheses, JSON, code blocks) that no DFA can. Ctrl-G = constrained decoding where a distilled HMM approximates the LM to score, at each step, the probability mass of constraint-satisfying futures. This project composes the two: hard NWA masks plus HMM future-mass guidance. Benchmarks: countdown (arithmetic target game, equation answer), nested_arith (rewrite a nested expression step by step), planetarium (NL → PDDL problem files), racket (MultiPL-E Racket function completion, unit-test pass), bbeh_dyck (BBEH Dyck bracket-closing), NESTFUL (nested tool-call sequences in JSON).

TL;DR — the complete result

Every number below is final: 2 models × 6 benchmarks × 5 conditions, plus a 24-cell λ ablation. One method, one protocol, no per-task tuning. Nothing is mid-run.

• On Qwen the full method strictly beats pure projection on 3 of 6 benchmarks and matches it on a 4th, at some λ ≤ 0.5. bbeh_dyck 0.315 vs 0.295, countdown 0.836 vs 0.832, planetarium 0.336 vs 0.332; NESTFUL λ=0.1 matches the mask to within 0.001 (0.386 vs 0.387) while closing its last schema failure (200/200 vs 199/200) — a near-free trade, not a strict domination. Caveat on that count: the best λ differs by task (0.5 for countdown and planetarium, 0.1 for NESTFUL), so the claim is "some λ ≤ 0.5 matches or beats the mask on 4 of 6 lanes", not one tuned setting.
• The hard mask (B) is the dependable floor and its value scales with base capability: +7.5pp racket-Qwen, +14.0pp bbeh-Qwen, +2.7pp countdown-Qwen, +5.9pp countdown-Llama, exact no-loss racket-Llama. Structural projection alone recovers real failure mass on every capable lane.
• Long free-form output is where the method still pays. nested_arith collapses at λ=1 on both models (0.000 / 0.005); lowering λ recovers much of it (0.201 Qwen, 0.109 Llama) but never reaches the mask (0.383 / 0.201). racket-Llama is monotone in λ (0.025 → 0.075 → 0.130 vs 0.199 mask). λ scales the long-answer penalty; it does not remove it.
• Learning the guide matters wherever guidance survives: E−D = +29.3pp on NESTFUL-Qwen (0.354 vs 0.061), +26.0pp on bbeh-Qwen, +21.9pp on planetarium-Qwen, +19.1pp on countdown-Qwen, +12.6pp on NESTFUL-Llama. The uniform-guide control (D) isolates this: same machinery, no learned signal.
• Why the guide's nulls happen — now diagnosed, not guessed. Three handoff experiments settle it: on CommonGen the same pipeline shows a trained guide beating a uniform one 200/200 vs 97/200, so the apparatus detects D2 when it exists; T1 shows the trained guide is no better than a blank one at forecasting satisfaction (AUC .940 vs .946); and T2 shows even a correctness-leaking oracle cannot beat the mask (0.360 vs 0.400). The reason is structural: the mask already guarantees satisfaction, so there is no event left for β to predict. These nulls are a property of the benchmarks, not a failure of the method — see the diagnosis.
• Guidance buys guarantees — on the capable base. NESTFUL zeroshot emits 0/200 strictly schema-valid outputs (Llama) and 111/200 (Qwen); the mask reaches 196/200 (Llama) and 199/200 (Qwen). The guided lane reaches 200/200 at every λ ≥ 0.1 on Qwen; on Llama only λ=1 reaches 200/200 (195 / 198 / 200 at λ = 0.1 / 0.5 / 1) — at λ=0.1 it is actually worse than the mask. The guarantee is free on Qwen and costs accuracy on Llama.
• The C condition (audited 2026-07-23): a zero-cell audit found walker.max_depth was silently ignored by the planetarium and bbeh walkers — their original C cells were byte-identical duplicates of E and have been superseded (planetarium C was re-run with a functional cap — jobs 1910589/1910590, final at 0.000 on both models; bbeh C is n/a — its answer language has no nesting). countdown and arith honor the cap but their decoded outputs never nest ≥ 2, so C ≡ E there is an honest (if uninformative) result. planetarium-Qwen is the real NWA>DFA separation: depth-2 C = 0.000 (0/256) vs E = 0.324 (83/256), +32.4pp. racket C is 0.000 on both models too, but racket-Qwen E is also 0.000, so that lane separates nothing — its outputs are budget-truncated, not depth-limited. (C shares E's guide DP; only the hard mask is depth-capped.)

Method & math

Decoding rule (all constrained conditions)

• B (mask) is the λ-term-free special case: log-softmax, keep walker-valid tokens at their LM scores, renormalize — Outlines-style; no HMM at all. LM likelihood ratios are preserved within the kept top-32 valid set (see implementation note above); exact for greedy decoding.
• β via offline DP: the HMM guide and the NWA are composed once per task into cached tensors (T_ι, C_γ, R_γ, W, β) by build_offline_cache — fp64, since fp32 future mass underflows on long completions. Runtime lookup is O(1) per candidate.
• Prefix-conditioned guides (v2): guides are HMMs distilled from the base model's own constrained samples. Training rows are (thinking-OFF rendered prompt) + answer; at eval the guide's belief state is initialized by forwarding the same prompt (hmm_prefix_ids) — byte-identical conditioning between distillation and decoding. LVD (latent-variable distillation from LM hidden states) initializes EM; EM trains on the prefixed rows (h=256 suite, h=512 NESTFUL).
• Reasoning is never constrained: thinking models decode <think>…</think> freely; a free warm-up runs to the task's answer marker (token-id-preserving cut); the constraint applies only from there. Greedy, beam 1, identical budgets across conditions within a task. Exception: racket and nested_arith define no answer marker, so on Llama (no thinking mode) their constrained conditions decode under the mask from the first token — no free prose phase, unlike condition A. Those are also the two lanes characterized below as "long free-form", so part of that penalty may be warm-up asymmetry rather than guidance.

Conditions — what each isolates

Results — Llama-3.1-8B-Instruct (complete)

Accuracy (exact task metric), n = full benchmark. Suite cells recomputed from per-example predictions at page build; NESTFUL from the scorer's final log block. Bold = row best. Llama decodes answers directly (no thinking mode).

bold = row best among completed cells · — = not started · … k/n = running, mean suppressed below 25% coverage · n/a = condition undefined for the task · Δ columns computed on raw counts before rounding (may differ from displayed cells by ±0.001) · † = transductively distilled guide (see caveats)

Results — Qwen3.5-9B (complete)

Same protocol, thinking ON (free, never constrained; max_think 4096–8192 per task). Every guide is distilled from this model's own constrained samples. Bold = row best.

bold = row best among completed cells · — = not started · … k/n = running, mean suppressed below 25% coverage · n/a = condition undefined for the task · Δ columns computed on raw counts before rounding (may differ from displayed cells by ±0.001) · † = transductively distilled guide (see caveats)

Why the uniform guide (D) scores ~0 on long-answer tasks

This is measured formulation behavior, not a bug — condition D exists to expose exactly this. With uniform emissions, every completion of length ℓ has probability V^−ℓ (V ≈ 128k–152k vocab), so:

The data shows all three signatures (figures below are Llama unless noted; Qwen is given where it differs). countdown-Llama (answers ≈ 14 chars): D = 0.188 ≈ B = 0.191 — harmless below the horizon, the clearest evidence the D implementation is correct. But countdown-Qwen D = 0.641 vs B = 0.832: even short answers lose 19pp once the base model is capable enough that the tilt competes with real preferences. nested_arith: outputs collapse to minimal valid shapes ('1. \n7 \n2 \n7…') → 0. racket / planetarium (Llama): long outputs that are almost entirely comments (penalty-free) with no scored structure → 0; planetarium-Qwen reaches 0.105, not 0. NESTFUL-Llama: minimal valid call-JSON (median 76 chars, vs 277 for the mask) — 200/200 schema-valid, 0.017 correct. E−D therefore reads: what does learning the guide buy, given identical machinery.

NESTFUL in depth (validity is a first-class result)

accuracy_combined = the benchmark's combined intent+slot+sequencing metric. "schema-valid" = outputs strictly accepted by the call-schema parser as emitted.

The accuracy–guarantee trade at λ=1: B leads accuracy (0.260) with 4/200 schema failures; E gives up ~12pp accuracy for zero schema failures; zeroshot A emits nothing strictly schema-valid (its calls are recovered only by lenient extraction). The earlier exploratory λ-sweep (archived) showed the gap closing as λ → 0.1–0.2 with validity retained — measuring that on the v2 prefix-conditioned guides is the λ-ablation section below, which found λ=0.1 recovers 0.252 (Llama) and 0.386 (Qwen).

λ ablation — the guidance-strength frontier

The matrix above fixes λ=1 (the pure formulation). Here condition E is re-run at λ ∈ {0.1, 0.5} with everything else identical — same guides, same budgets, greedy, thinking unconstrained. The λ=0 column is condition B shown as the λ→0 limit of the guide term — it is a separate mask-only run, not a sweep point (the β=0 hard ban applies at every λ, so a literal λ=0 guided run is still not the mask). 24 guided cells, all complete at full n.

Qwen3.5-9B

bold = best guided-or-mask cell in the row (suppressed when that best is 0.000) · λ=0 column = condition B, a separate mask-only run shown as the λ→0 limit; λ=1 = condition E from the main matrix · NESTFUL cells show accuracy with schema-validity beneath (jobs 1924871-1924874) · † = transductively distilled guide (see caveats)

Llama-3.1-8B-Instruct

bold = best guided-or-mask cell in the row (suppressed when that best is 0.000) · λ=0 column = condition B, a separate mask-only run shown as the λ→0 limit; λ=1 = condition E from the main matrix · NESTFUL cells show accuracy with schema-validity beneath (jobs 1924871-1924874) · † = transductively distilled guide (see caveats)

What the frontier shows

• On a capable base, guidance is free. Qwen matches or beats the mask on 4 of 6 tasks at low/mid λ: countdown flat at 0.832 (λ=0.5 is row-best 0.836), planetarium flat ≈0.33, and NESTFUL λ=0.1 gives 0.386 accuracy with 200/200 schema validity against the mask's 0.387 at 199/200 — i.e. it matches the mask to within 0.001 accuracy while closing the last schema failure, not a strict domination (0.386 < 0.387). λ=0.5 (0.384, 200/200) sits beside it, so the region is a plateau rather than a lucky setting.
• bbeh_dyck is the clean win over projection: 0.315 at every λ tested vs the mask's 0.295 and zeroshot's 0.155 — untuned and strength- independent. Paired at the example level it is +4 / −0 flips out of 200 (exact McNemar two-sided p = 0.125): directionally clean with zero regressions, but not statistically significant at this n. It is also a transductive-guide lane (†).
• Long free-form output still pays. nested_arith collapses at λ=1 on both models (0.000 / 0.005); moderate λ recovers much of it (0.201 Qwen, 0.109 Llama) but never reaches the mask (0.383 / 0.201). racket-Llama is monotone: 0.025 → 0.075 → 0.130 against a 0.199 mask. λ scales the long-answer penalty; it does not remove it.
• A weak base turns the same machinery into a genuine trade. NESTFUL-Llama: accuracy 0.260 → 0.252 → 0.222 → 0.143 as λ rises, validity 196 → 195 → 198 → 200/200. Note this is not a clean Pareto frontier: λ=0.1 (0.252, 195/200) is dominated by the mask on both axes; only λ=0.5 → λ=1 is a real accuracy-for-validity trade. Guarantee-at-no-cost needs a capable base and a prefix-conditioned guide and λ ≤ 0.5.
• Open anomaly: nested_arith-Qwen is non-monotone — λ=0.5 (0.201) beats λ=0.1 (0.130) by 27/384 examples, too large for sampling noise. Some factor other than guide strength interacts on that lane (candidates: max_new=1536 truncation, the walker's line cap, EOS pressure). Flagged rather than explained; it should be resolved before any arith-specific claim.
• racket-Qwen is budget-bound, not λ-bound: flat 0.000 at every λ against a 0.360 mask, matching the audit finding that 100% of its constrained generations hit the 384-token cap without ever reaching an accepting configuration. The indicated follow-up is a budget experiment, not a λ one.

D1 — does look-ahead buy anything? (measured; answer: no)

The matrix and the λ section both measure D2 — what grading the viable set buys. The other half of the decomposition is D1: what reachability look-ahead buys over plain one-step legality. Two arms, both on the same objects as the matrix.

Arm 1 (walker, repair disabled) turned out to be a null instrument: 0 differing answers in 2,063 matched examples. The per-task walkers are viability-complete by construction — their step function refuses any character that would strand the generation — so the decoder never dead-ends and the fallback is unreachable. It measures nothing about look-ahead and is reported here only so the zero is not mistaken for evidence.

Arm 2 (the real one): one-step nwa.step legality vs 1[β>0] from the offline DP, both on the same token NWA.

1,965 matched examples · 8 differing answers (0.41%) · D1 = +0.0000 on every lane · countdown/qwen and nested_arith/qwen are partial (202, 289) because their 12 h wall hit — matched-pair comparison still settles them, and they were not resubmitted to reconfirm a structural property on a shared cluster

Why — and it was predicted before it was measured

Every structural NWA in this project is a bracket/balance hull, and on such a hull every legal prefix extends to an accepting string by appending closers. So 1[β>0] and 1[legal now] are the same function, and the offline DP decides nothing the one-step relation had not already decided. The project's own handoff argued exactly this a priori — "nesting depth and look-ahead depth are orthogonal; bracket viability is shallow look-ahead yet needs NWA state" — and this measures it on four languages and two models. The NWA earns its keep through state (unbounded nesting a DFA cannot track), not through look-ahead; β's remaining justification is grading, i.e. D2.

Why does guidance help on CommonGen but not here? (the diagnosis)

The matrix, the λ ablation and the D1 study all return nulls for the guide. Three further experiments — the ladder from the project's own handoff — were run to establish why, and whether the nulls are about the method or about the benchmarks. They answer it.

Experiment A — the CommonGen positive control

What it does. Runs Ctrl-G on the benchmark it was built for, using its own released assets (gpt2-large_common-gen + the h=4096 CommonGen HMM) and its own DFA machinery: the constraint is keyword inclusion (every concept must appear in some inflected form). Two arms, identical except for the guide — uniform (h=2, uninformative) vs trained (h=4096). n=200. Metric: constraint satisfaction, plus mean log p_LM per generated token (what rank_generated_ids already ranks by, i.e. the pipeline's own notion of quality).

Why it matters. The handoff is blunt about it: "without this anchor, a null result anywhere else is uninterpretable." If our apparatus cannot detect a guide's benefit where one is known to exist, every null we report is worthless.

a third "viability" arm was attempted and abandoned after two failed implementations — documented in EXPERIMENT_LOG, excluded here rather than reported

Finding. The trained guide dominates on both axes at once: +51.5pp constraint satisfaction and better fluency. D2 is large and easily detected when it exists. The apparatus works.

Experiment B — T1, event calibration

What it does. Asks whether β̂ is actually a good forecaster of the thing it claims to predict. Take an in-language partial generation, read β̂ at its automaton config, then roll the base LM forward unconstrained 8× and record whether those rollouts satisfy the constraint. Score β̂ as a probabilistic forecaster of that realized event — Brier and AUC — for the trained guide and a uniform one. 59 live prefixes, stratified across difficulty.

Why it matters. Perplexity measures the guide's content model. Whether the guide predicts the satisfaction event is a different functional, and it is the one Ctrl-G's decoding rule actually consumes.

base rate 0.746 — predicting the base rate alone would score Brier ≈ 0.19

Findings. (1) β is not a probability. Both guides forecast ≈1e−10 where realized satisfaction is 0.75; Brier ≈ 0.74 against ≈0.19 for base-rate prediction. (2) Learning adds nothing to event prediction — uniform is marginally ahead on AUC. Both rank well (≈0.94) using the same structural signal, shortest-completion length, which the uniform guide has by construction. This is the handoff's H4 hypothesis, confirmed.

Experiment C — T2, the MC-oracle ceiling

What it does. Removes guide quality from the equation entirely. At each binding decision point (where more than one token is viable, so grading could change the outcome), it replaces β̂ with a Monte-Carlo estimate from the base LM itself: roll forward 6× per candidate and score the outcomes, then decode with that. It is the ceiling any future-aware scorer could reach.

oracle − mask = −0.040, one differing example in 25; oracle active at 11.0 decision points per generation on average

Finding. The oracle does not beat the mask. And this is the strong form: our oracle scores rollouts by verified task correctness, not merely by constraint satisfaction — it is more powerful than Ctrl-G's β is entitled to be — and it still buys nothing. By the handoff's own decision rule, nested_arith has no D2 headroom. Not a guide-fidelity problem.

caveats: n=25 with one differing example means "no detectable difference", not "the oracle is worse"; and the oracle is capped at 12 binding points before falling back to mask decoding, making it a lower bound on the true ceiling

The takeaway these three give together

Caveats & scope

• λ grid is {0, 0.1, 0.5, 1}. The MAIN matrix is λ=1 (the pure formulation); the λ-ablation section reports λ ∈ {0.1, 0.5}. No finer sweep was run, and no λ is tuned per task in the headline protocol.
• Resolved (2026-07-30) — nested_arith's λ curve is a walker-cap artifact, not a guidance effect. Any λ > 0 drives arith into a line-padding regime that hits ArithChainWalker._MAX_LINES = 128: 279/384 answers sit at the cap at λ=0.1 and 236/384 at λ=0.5, versus 12/384 for the mask (median 128 lines vs 8). At λ=0.1, 49 of the 50 correct answers are cap-truncated runs. So the 0.130-vs-0.201 gap measures how much padding happens before the cap binds — the arith guided cells at every λ are artifact-dominated and are not evidence about guidance on this benchmark.
• racket-Qwen 0.000 — budget explanation REFUTED (2026-07-31). Re-run at max_new=1024 (2.7×) gives exactly 0.0000 again, with 136/161 answers byte-identical to the 384 run. The real cause is completion shape: Racket prompts end mid-define, so a valid completion needs one extra ), but 84/161 guided answers are self-balanced standalone fragments that leave the header open — the assembled program fails with read-syntax: expected a ')' even though the answer alone parses. The 2026-07-23 audit's "100% budget-truncated" reading was wrong and is superseded. Root cause (splicing vs walker vs guide) still open.
• Guide capacity is bounded, not tuned: h=256 is the largest that fits every suite NWA's offline-cache envelope (arith s=98 rules out h≥512), and the NESTFUL h=1024 guide OOM'd in build_offline_cache (33 GiB C_stack intermediate) and was deferred pending a loop-form build. Where guidance underperforms, capacity is a live un-tested lever.
• NESTFUL-Qwen's guide corpus is thinking-OFF while its eval is thinking-ON (the five suite Qwen guides are sampled with thinking on). The conditioning prefix is byte-identical either way; the answer distribution the guide saw is not.
• The mask is not universally safe: it loses on 2 of 12 lanes — bbeh-Llama (B 0.000 vs A 0.045; projection removes the model's only correct answers) and arith-Qwen (0.383 vs 0.396).
• The learned guide loses to the uniform one on 2 lanes: countdown-Llama (E 0.172 vs D 0.188) and arith-Qwen (0.000 vs 0.005).
• Zero-cell audit (2026-07-23, 4 independent verifiers): every 0.000 cell was adversarially checked — known-passing answers round-trip True through the same scoring paths, all failures reproduce offline, and failure taxonomies match the formulation's predictions. Two findings: racket-Qwen D is truly ≈1.9% (3/161 outputs carry a correct program in a later markdown fence than the first-fence extraction rule scores — the rule is uniform across all conditions, so it stands, disclosed); and the bbeh answer walker banned the literal 'No' that 10/200 gold targets use (the dataset's own instruction) while the harness prompt said 'NA' — fixed (walker/NWA/prompt now accept 'No'); all bbeh cells shown here were re-run against freshly distilled v2 guides (bbeh_hmm_v2 / bbeh_hmm_llama_v2, jobs 1910583-1910588 / 1910625 / 1911121), and the pre-fix runs are preserved under results/_superseded/.
• racket & bbeh_dyck guides are transductive (†): no train split exists (161 and 200 examples total, respectively), so their corpora are self-distilled from TEST prompts (temp-1.0 samples under the walker mask; gold answers and the verifier never touch the corpus). Their C/E cells carry the † marker in the tables above.
• bbeh_dyck has a tiny answer language: zeroshot 4.5% (Llama) / 15.5% (Qwen), so single-example noise is material — see the paired-flip count in the λ section rather than reading its deltas as significant.
• Superseded runs are preserved, not deleted: results/_superseded/2026-07-23_bbeh_no_fix/ holds the full pre-'No'-fix bbeh grid (Qwen A .200/B .295/C .330/D .115/E .330; Llama A .025/B .005/C .000/D .005/E .000) and 2026-07-23_pddl_dfa_noop/ holds the two no-op planetarium C files. The bbeh fix changed the prompt as well as the walker, so pre/post bbeh numbers are not directly comparable.
• NESTFUL C is n/a: the call-schema language has bounded nesting — already DFA-expressible, no depth axis to cap.
• Racket verification runs with a pinned local rackunit (PLTADDONDIR); per-file labels re-checked offline before reporting (a per-node package issue once produced all-False labels).
• Every cell on this page is final at full n; nothing is mid-run.

Implementation map

Per-task budgets (identical across conditions within a task)