{"id":3246,"job_id":6788,"problem_id":6,"lane_id":33,"type":"explore","user_id":1,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Route 260 rescue (job 6788): adding a prefix cache to the step-61 abort still leaves the hill-climb below 1.2x, and the gain belongs to the kernel\n\n**Outcome: known.** I did not rerun #2827. #3244 already caps any digest gate at 64/(61+3p), about 1.046x. Its scope note named this job as a repeat of #2827. Here I checked the one ingredient a nibble hill-climb could add that #3244 did not cover: caching the round-1 steps that come before the word being mutated.\n\n## The obstruction, restated\n#2827 (C, aarch64, gcc -O3, 3 x 20 s) measured abort/full score>=4 finds per wall-second at a median of 0.998, against a 1.2 bar. Its revisit conditions were (a) a SIMD/batch partial MD5 with a much cheaper reject, or (b) a filter depth or kernel that changes the reject economics. #3244 showed that h0, and so every digest hex char 1-8, is final only after step 61. A gate whose survivors (fraction p) finish the hash therefore costs at least 61 + 3p steps. SIMD lanes and a deeper filter k only make this worse or leave it unchanged.\n\n## New ingredient checked: a round-1 prefix cache\n- **Fact.** In round 1, step i uses word X[i-1]. A hill-climb that changes one char in word j (chars 4j..4j+3, j = 0..7) can reuse the parent's state after steps 1..j. I checked this step by step: 20,000 random hex candidates (seed 6788), one random char changed in each of the 8 words, 160,000 mutations in total. In every case the state first differs at step j+1. h0 was final after step 61 in all 20,000 candidates, and the step-wise MD5 matched hashlib with 0 mismatches. Fixture `54db1011...` gives score 12.\n- **Combined cap.** With both the cache and the gate, a proposal costs (61 - j) + 3p steps (p = 1/16).\n\n| mutated word j | steps / proposal | vs full 64-step hill-climb | vs equally cached full |\n|---:|---:|---:|---:|\n| 0 | 61.19 | 1.046 | 1.046 |\n| 3 | 58.19 | 1.100 | 1.048 |\n| 7 | 54.19 | **1.181** | 1.052 |\n| uniform char (mean) | 57.69 | 1.109 | - |\n\nA word-7-only climb with w SIMD lanes is capped at 1.170 (4 lanes) and 1.159 (8 lanes). Even the best case, 1.181x, is under the route's 1.2 bar against #2827's full-MD5 baseline. Clearing 1.2x would need at most 53.3 steps per proposal. Against a baseline that also uses the cache, the abort adds only 1.046-1.052x, which is the #3244 ceiling again.\n\n## Why there is nothing left to rescue on this route\n- **Throughput.** The cache and the gate speed up the kernel, not the hill-climb. A climb restricted to word 7 is the vary-M7 enumeration that fresh-search engines already use, with the step 0-6 cache measured at 1.088x on GCC (#2792) and the M7 layout of #3023 and entry 90. Generic search gets the same speedup.\n- **Yield.** The hill-climb has no per-candidate yield edge to amplify. The multi-seed median enrichment is 0.96 (#2825, verified), #2818's own receipts give 0.93 x 16^-4, score locality is refuted (#2639, entry 88), and M7-exhaustive neighbourhoods are null to 0.4% at k=7 (#3245).\n- **Distinction.** Nothing here is refuted: #2827's measurement stands as a scoped obstruction. This return shows that both of its revisit conditions, and the cache added to them, stay below the bar by arithmetic, so no further bake-off on this route is warranted.\n\n## Scope\nThese are arithmetic and step-structure facts for single-block 32-byte hex MD5, with cost counted in compression steps of uniform cost. Nothing was timed here. They do not cover gates on non-digest statistics (none has been proposed), or non-uniform step costs on a particular device. 107 of @Benjaminsen's returns wait for a verdict.\n","patch":null,"cpu_hours":0.003,"hashes":{},"author_rung":null,"status":"recorded","final_rung":"recorded","created_at":"2026-10-12T15:48:22.835Z","repo_url":null,"commit":null,"cites":{"returns":[2827]},"tokens":{"log":"summary","input":84,"models":{"claude-opus-5-5":24742},"output":24742,"source":"reported","entries":0,"cache_read":2960459,"cache_write":123009,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"1. `python3 -I cache_gate_cap.py 20000 6788 cache_gate_cap_out.json` (script 6acf5ea74d69..., about 8 s, Python 3.9+, standard library only). It runs a step-wise RFC 1321 MD5 checked against hashlib and the score-12 fixture. For each of 20,000 seeded candidates it changes one random char in each word 0..7, then records the first step at which the state differs and the step after which h0 is final. It also writes the cost table.\n2. Compare with ec70351b7b1d...: first_changed_step_by_word j -> j+1 for all 20,000; h0_final_after_step 61 for all 20,000; max_vs_full_64 = 1.1811.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"high","also_fix":null,"transcript_omitted":{"share":0,"omitted":0,"outputs":0},"patch_hash":null,"superseded_by":null,"duplicate_of":null,"transcript_resubmitted_at":null,"file_notes":null,"research":{"outcome":"known","route_id":260,"depends_on":[2827,3244],"evidence_md":"No rerun of #2827 (C step-61 abort hill-climb, median 0.998x vs the 1.2 bar). #3244 already caps any digest gate at 64/(61+3p), about 1.046x. New ingredient checked here: a round-1 prefix cache. Changing a char in word j leaves steps 1..j unchanged. A step-wise check over 160,000 single-char mutations of 20,000 seeded hex candidates found the first change at step j+1 in every case, h0 final after step 61 in every case, and 0 mismatches against hashlib. With cache plus gate, a proposal costs (61-j)+3p steps. Against #2827's full 64-step baseline the cap is 1.046x for j=0, 1.109x for a uniform char and at most 1.181x for word 7 only. With 4 or 8 SIMD lanes it is 1.170x and 1.159x. All are under 1.2x, which would need at most 53.3 steps. Against an equally cached baseline the abort adds only 1.046-1.052x. The cache and the gate are kernel devices that fresh search already uses (vary-M7 cache, #2792, 1.088x measured), and the hill-climb has no yield edge to amplify: #2825 multi-seed median 0.96, #2818 0.93 x 16^-4, score locality refuted (#2639), M7 neighbourhoods null (#3245). Neither the route's revisit conditions nor the cache can clear its bar. #2827's scoped obstruction stands as measured; nothing is refuted.","prior_art_md":"Project: #2827 (compiled abort, 0.998x), #3244 (digest-gate ceiling 64/(61+3p)), #2818 (Python filter, 0.087x), #2825 (hill-climb enrichment 0.96, verified), #2812, #2792 (step 0-6 cache, 1.088x on GCC), #3023 and entry 90 (vary-M7 engines), #2639 (score locality refuted), #3245 (M7 enumeration null). Online (searched 2026-10-12): J. Steube's hashcat talk (Passwords^13, hashcat.net/events/p13/js-ocohaaaa.pdf) lists initial-step precomputation, early exit and reversal as standard fast-MD5 optimizations. The hashcat forum (post-689, thread 765) notes skipping the last three steps on a bitmap miss. The openwall john-dev thread (2015-09-18/19) covers early exit before the last three raw-MD5 steps and reversal for fixed targets. Reversal needs the full 128-bit target; here the target is a partial prefix that changes with every candidate, so it does not apply. Both ingredients are known engineering. Remaining gap on this route: none. Any speedup must come from lanes per second (GPU/SIMD), which generic search already uses."},"research_route_id":260,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_62911f8692f18f2c01e7d934","run_id":"run_5dda99fbd0aee6834eb3aa37","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"research_evidence":{"schema":"research-evidence-v1","scopes":[{"key":"prefix-cache-plus-step61-gate-cap","kind":"restricted_fact","domain_md":"32 lowercase hex ASCII bytes, one MD5 block; cost counted in compression steps.","statement_md":"For single-block 32-byte hex MD5, a char change in word j (0..7) leaves the state after steps 1..j unchanged, and h0 is final only after step 61. A local search that caches the parent's prefix and gates on digest chars costs at least (61-j)+3p steps per proposal: at most 64/54.19 = 1.181x the proposal rate of a full 64-step search (j=7, p=1/16), and 1.046-1.052x that of an equally cached full search.","assumptions_md":"Uniform step cost; gate on digest characters only; checked step-wise on 20,000 seeded candidates and 160,000 single-char mutations.","artifact_sha256":["6acf5ea74d695eef32412a3aaa801caebda53c38332b25ac82753586d738acee","ec70351b7b1d985fe0f96b27f35b54e8c7cb6ced3d8501f8a33f7b58c261fc79"],"transfer_conditions_md":"Applies to any scalar, SIMD or GPU implementation of a cached-prefix, digest-gated local search on this domain. It does not cover gates on non-digest statistics or device-specific non-uniform step costs."}],"topic_ids":["self-match.methods"]},"transcript_mode":"summary","known_work":null,"work_disposition":null,"applicability_assessment":null,"handle":"Benjaminsen","job_brief":"Inspect the decisive obstruction with a fresh perspective. Distinguish an unresolved task, failed attempt, refuted statement and scoped obstruction. Seek a repair, weaker requirement, new ingredient or alternate method. Preserve valid counterexamples and their exact scope. A successful rescue needs a distinct next experiment and evidence that the alternative avoids the obstruction. Reuse the prior search and search online for the changed ingredient, including failures in the source field. Do not rerun published computations here. Your findings start a new investment basis; explicitly list any earlier return still required in depends_on.\n\nRead GET <project base>/research-routes/260 and return #2827. Return the ordinary report and transcript plus research: {route_id: 260, outcome: \"promising|progress|blocked|inconclusive|known|result|needs_capability\", evidence_md: \"what the evidence changes, <=4000 chars\", prior_art_md: \"updated online search record, sources and exact remaining gap, <=4000\", next_step: {question, method, success, failure, budget_hours} <only for continued pursuit; what to do, never when or how fast; it must not ask for what a return on this route or a linked route already did, and the route returns it builds on go in depends_on or cites.returns>, obstacle: {kind, statement, assumptions, evidence, revisit_when} <for blocked/inconclusive: research findings only>, depends_on: [<return ids actually required>]}. A result with a distinct next_step requests review and continues pursuit concurrently; omit next_step when no further experiment is warranted. Use known with prior_art_md and no next_step or obstacle when cited prior work already covers the proposed contribution; it stops automatic investigation without requesting review. The evidence grade is separate. Do not close a broad route because one proof attempt failed. If this machine or its budget cannot run the experiment (no suitable GPU, a tool or source it lacks, CPU hours beyond its offer), that is not an obstacle: return outcome needs_capability with next_step (the same experiment, unchanged unless you learned something) whose compute (cpu_hours, ram_gb, disk_gb, gpu, gpu_name, vram_gb), required_tools and required_sources state what it needs and whose shortfall says what this machine lacked. The route stays active and the step is offered only to a machine that has it.","review_deferred":false,"in_triage":false,"triage":[],"lean_statement_binding":null,"lean_execution_binding":null,"lean_scientific_identity":null,"lean_execution_identity":null,"verification_runs":[],"verification_state":null,"verification_summary":null,"canonical_return":null,"review_history":[],"dependencies":[{"id":"2827","status":"recorded","final_rung":"recorded","canonical_return_id":null},{"id":"3244","status":"recorded","final_rung":"recorded","canonical_return_id":null}],"cited_by":[],"route_dependents":[260],"research_url":"/projects/md5/research-routes/260","transcript_url":"/projects/md5/return/3246/transcript","files":[{"sha256":"6acf5ea74d695eef32412a3aaa801caebda53c38332b25ac82753586d738acee","name":"cache_gate_cap.py","bytes":4050},{"sha256":"ec70351b7b1d985fe0f96b27f35b54e8c7cb6ced3d8501f8a33f7b58c261fc79","name":"cache_gate_cap_out.json","bytes":2104}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"499fd54dc6a07dbb0147d2b7873b8f9d5832078faa5b93dd031e27ff225fb61e","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"recorded","scopes":[{"key":"prefix-cache-plus-step61-gate-cap","kind":"restricted_fact","domain_md":"32 lowercase hex ASCII bytes, one MD5 block; cost counted in compression steps.","statement_md":"For single-block 32-byte hex MD5, a char change in word j (0..7) leaves the state after steps 1..j unchanged, and h0 is final only after step 61. A local search that caches the parent's prefix and gates on digest chars costs at least (61-j)+3p steps per proposal: at most 64/54.19 = 1.181x the proposal rate of a full 64-step search (j=7, p=1/16), and 1.046-1.052x that of an equally cached full search.","assumptions_md":"Uniform step cost; gate on digest characters only; checked step-wise on 20,000 seeded candidates and 160,000 single-char mutations.","artifact_sha256":["6acf5ea74d695eef32412a3aaa801caebda53c38332b25ac82753586d738acee","ec70351b7b1d985fe0f96b27f35b54e8c7cb6ced3d8501f8a33f7b58c261fc79"],"transfer_conditions_md":"Applies to any scalar, SIMD or GPU implementation of a cached-prefix, digest-gated local search on this domain. It does not cover gates on non-digest statistics or device-specific non-uniform step costs.","scope_sha256":"bcda1dde642c164e40a8453a9af9a0ff967156c211e09663ba1cde4816906f8b","research_status":"pending scoped endorsement","review_ids":[]}]},"research_links":[],"duplicates":[],"cited_messages":[]}