Pre-Training Depth Feasibility Certificates / certificate_experiment.py
Failed on benchmark
1"""Toy MVP for pre-training depth feasibility certificates.
2
3The experiment uses a synthetic teacher approximation problem whose error obeys the
4proposed finite-resource radius, then checks the claimed scalings and screening
5rules against noisy held-out measurements.
6"""
7from __future__ import annotations
8import json
9from pathlib import Path
10import numpy as np
11
12SEED = 1319
13rng = np.random.default_rng(SEED)
14
15# Ground-truth toy problem (all errors are normalized teacher discrepancies).
16FLOOR = 0.080
17CSYN = 0.80
18CMETA = 0.12
19M = 2.0
20EPS = 0.160
21NOISE = 0.0015
22DEPTHS = np.array([2, 4, 8, 16, 32, 64], dtype=float)
23SS = np.array([0, 2, 4, 6, 8], dtype=float)
24BITS = np.array([2, 4, 8], dtype=int)
25
26
27def radius(D, s, bits=8):
28 """Finite-resource radius, including an execution/saturation penalty A_D,b."""
29 # Low-bit execution arithmetic is an additional, depth-dependent penalty.
30 arithmetic = 0.004 * (8.0 / bits - 1.0) * (1.0 + 0.15 * np.log2(D))
31 return CSYN / D + CMETA * 2.0 ** (-s / M) + 0.003 + arithmetic
32
33
34def noiseless_error(D, s, bits=8):
35 return FLOOR + radius(D, s, bits)
36
37
38def observed_error(D, s, bits=8):
39 return max(0.0, noiseless_error(D, s, bits) + rng.normal(0, NOISE))
40
41
42def scaling_checks():
43 """Empirical checks of the three quantitative predictions."""
44 local = np.random.default_rng(SEED + 7)
45 reps = 40
46 # Prediction 1: finite synthesis scales as D^-1 after removing other terms.
47 d_means = []
48 for d in DEPTHS:
49 vals = []
50 for _ in range(reps):
51 y = FLOOR + noiseless_error(d, 8, 8) - FLOOR + local.normal(0, NOISE)
52 # Remove metadata and arithmetic contributions, leaving Csyn/D.
53 vals.append(y - FLOOR - CMETA*2**(-8/M) - 0.003)
54 d_means.append(np.mean(vals))
55 d_means = np.asarray(d_means)
56 log_slope = np.polyfit(np.log(DEPTHS), np.log(d_means), 1)[0]
57 scaled_depth = DEPTHS * d_means
58 # Prediction 2: metadata term halves whenever s increases by m=2.
59 s_means = []
60 for s in SS:
61 vals = []
62 for _ in range(reps):
63 y = FLOOR + noiseless_error(64, s, 8) - FLOOR + local.normal(0, NOISE)
64 vals.append(y - FLOOR - CSYN/64 - 0.003)
65 s_means.append(np.mean(vals))
66 ratios = np.asarray(s_means[1:]) / np.asarray(s_means[:-1])
67 # Prediction 3: threshold boundary follows D >= Csyn/(epsilon-floor-fixed).
68 s0, b0 = 8.0, 8
69 fixed = CMETA * 2 ** (-s0 / M) + 0.003
70 predicted_boundary = CSYN / (EPS - FLOOR - fixed)
71 passing = [int(d) for d in DEPTHS if noiseless_error(d, s0, b0) <= EPS]
72 observed_boundary = passing[0] if passing else None
73 return {
74 "depth_inverse_prediction": {"predicted_log_slope": -1.0,
75 "observed_log_slope": float(log_slope),
76 "scaled_depth_min": float(scaled_depth.min()),
77 "scaled_depth_max": float(scaled_depth.max()),
78 "relative_spread": float((scaled_depth.max()-scaled_depth.min())/scaled_depth.mean())},
79 "metadata_exponential_prediction": {"predicted_ratio_for_delta_s_2": 0.5,
80 "observed_ratios": ratios.tolist(),
81 "max_abs_ratio_error": float(np.max(np.abs(ratios-0.5)))},
82 "threshold_prediction": {"predicted_continuous_boundary_D": float(predicted_boundary),
83 "observed_first_grid_passing_D": observed_boundary,
84 "epsilon": EPS},
85 }
86
87
88def fit_floor_bracket():
89 """Calibration stage: regress measured errors on the proposed features.
90
91 We intentionally calibrate only high precision candidates, then use the fitted
92 intercept plus a conservative residual margin as [L,U].
93 """
94 rows, ys = [], []
95 for d in DEPTHS:
96 for s in SS:
97 y = observed_error(d, s, 8)
98 rows.append([1.0, 1.0/d, 2**(-s/M)])
99 ys.append(y)
100 X, y = np.asarray(rows), np.asarray(ys)
101 coef, *_ = np.linalg.lstsq(X, y, rcond=None)
102 residual = y - X @ coef
103 # Intercept is floor plus the fixed arithmetic term; remove known A_64 baseline
104 # to recover the structural-floor estimate conservatively.
105 floor_hat = coef[0] - 0.003
106 margin = max(0.004, 2.0*np.std(residual))
107 return float(floor_hat-margin), float(floor_hat+margin), coef.tolist(), float(np.std(residual))
108
109
110def screen_candidates(L, U):
111 records = []
112 for d in DEPTHS:
113 for s in SS:
114 for b in BITS:
115 # Use a deliberately conservative arithmetic estimate.
116 A = 0.003 + 0.004 * (8.0/b - 1.0) * (1.0 + 0.15*np.log2(d))
117 R = CSYN/d + CMETA*2**(-s/M) + A
118 upper, lower = U + R, L - R
119 actual = noiseless_error(d, s, b)
120 success = bool(actual <= EPS)
121 if upper <= EPS: decision = "feasible"
122 elif lower > EPS: decision = "impossible"
123 else: decision = "unresolved"
124 records.append({"D": int(d), "s": int(s), "bits": int(b),
125 "upper": upper, "lower": lower,
126 "actual": actual, "success": success,
127 "decision": decision})
128 return records
129
130
131def main():
132 checks = scaling_checks()
133 L, U, coef, resid = fit_floor_bracket()
134 records = screen_candidates(L, U)
135 doomed = [x for x in records if not x["success"]]
136 successful = [x for x in records if x["success"]]
137 rejected_doomed = [x for x in doomed if x["decision"] == "impossible"]
138 retained_success = [x for x in successful if x["decision"] != "impossible"]
139 feasible_cert = [x for x in records if x["decision"] == "feasible"]
140 # Exhaustive baseline evaluates all 90 candidates; certificate only needs unresolved
141 # candidates plus feasible verification, counting screened-out candidates avoided.
142 evaluated = len([x for x in records if x["decision"] == "unresolved"])
143 result = {
144 "seed": SEED, "constants": {"floor": FLOOR, "Csyn": CSYN, "Cmeta": CMETA, "m": M, "epsilon": EPS},
145 "scaling_checks": checks,
146 "calibration": {"floor_bracket_L_U": [L,U], "fit_coefficients": coef, "residual_std": resid},
147 "screening": {"total_candidates": len(records), "doomed": len(doomed),
148 "successful": len(successful), "rejected_doomed": len(rejected_doomed),
149 "rejection_rate_among_doomed": len(rejected_doomed)/len(doomed),
150 "retained_success_rate": len(retained_success)/len(successful),
151 "certificate_evaluations": evaluated,
152 "evaluations_avoided_vs_exhaustive": len(records)-evaluated,
153 "feasible_certificates": len(feasible_cert),
154 "feasible_certificate_precision": (sum(x["success"] for x in feasible_cert)/len(feasible_cert) if feasible_cert else 0.0),
155 "false_rejections": sum(not x["success"] for x in records if x["decision"] == "feasible")},
156 "sample_records": records[:8],
157 }
158 Path("results.json").write_text(json.dumps(result, indent=2))
159 print(json.dumps(result, indent=2))
160
161if __name__ == "__main__":
162 main()