Concept · A1131

COVERAGE EVALUATION +
GREEDY CELF SELECTION

Set-Cover Optimization Lazy Greedy (CELF) Submodular Marginal Gain

How rule_ranker's celf_recompute_gpu.py turns a huge pool of candidate rules into a small ruleset that actually maximizes distinct password recovery — instead of just summing individual rule scores — and why this consistently beats plain frequency ranking at every budget size.

2 phases
coverage evaluation · CELF selection
1 objective
| union of recovered target words |
O(log n) amortized cost per pick
vs O(rules) for naive greedy
1M candidates in the real run below
no matrix to outgrow — GPU time is the only limit
0 coverage rows stored
recomputed live on the GPU instead
The Core Idea

Sorting candidate rules by raw GPU frequency and taking the top-N is the obvious first approach, but it optimizes the wrong quantity. Two high-frequency rules can crack almost the same subset of the target list — keeping both wastes budget that a lower-frequency, but orthogonal, rule would have spent far better. What actually matters for a ruleset of size k is not the sum of individual scores, but the size of the union of everything those k rules recover.

That's a classic set-cover problem: each rule r defines a set C(r) of the distinct target words it actually cracks, and the goal is to choose a budget-sized collection of rules whose combined C(r) sets cover as much of the target universe as possible. Set cover is NP-hard to solve exactly, but the coverage function is submodular — each additional rule can only add as much or less than it would have earlier, never more — which is exactly the property that makes a simple greedy strategy provably close to optimal (within a factor of 1 − 1/e, roughly 63%, of the true best selection).

Phase 1 — Coverage Evaluation
01

Cracked list → sorted unique 64-bit fingerprints

load_cracked_universe() reads the target/cracked-password file and hashes every line with FNV-1a-64 (fast_fnv1a_hash_64), then dedups to a sorted array of unique fingerprints — with an on-disk fingerprint cache so a re-run against the same cracked file skips re-hashing entirely. There is no bloom filter anywhere in this tool; that two-stage prefilter/verify split is specific to the rulest pipeline, not rule_ranker.

02

GPU open-addressing hash table, not integer target IDs

Those fingerprints are built into a GPU-resident open-addressing table (_build_open_addressing_table, ≤50% load factor, SplitMix64 slot distribution) once per run. A word is "covered" when its FNV-1a-64 fingerprint lands in an occupied table slot — coverage is tracked by hash-table slot, not by a deduplicated integer target-word ID as in rulest. The project's own docs are explicit that this is a hash table in the ordinary birthday-bound sense, not a cryptographic or string-exact guarantee.

03

Pass 1: exact upper bound per rule, no coverage rows kept

Every candidate rule is run once against the full (not-yet-covered) wordlist on the GPU and its hit count against the hash table is accumulated with a single atomic counter per rule — not a per-rule array of which words it hit. That count is this rule's monotone upper bound for every later round, since coverage can only shrink from here.

04

No coverage store at all — not dict, not disk

Per the module's own docstring: "nothing shaped (n_rules × cracked_universe) is ever allocated, in RAM or on disk." There is no size threshold that switches between an in-memory dict and a disk-backed store — that distinction belongs to rulest's CoverageStore. Here the only persistent state between rounds is the active bitmap (which hash-table slots are still uncovered) and each rule's current upper bound; every gain is recomputed from the wordlist on demand rather than looked up.

Phase 2 — Greedy CELF Selection
05

Naive greedy: correct, but too slow at scale

The textbook greedy algorithm repeatedly scans every remaining candidate, recomputes its marginal gain against the current covered set, and picks the best one — then repeats from scratch. That's O(rules × budget) evaluations, which is fine at a few thousand candidates but becomes the bottleneck well before 100k, let alone the million-candidate pools shown in the real run further down this page.

06

CELF: lazy re-validation via a max-heap

The Cost-Effective Lazy Forward selection algorithm exploits submodularity directly: since a rule's marginal gain can only shrink (never grow) as more of the target universe gets covered, a rule whose gain was already computed doesn't need to be rescanned — it only needs to be re-checked if it reaches the top of a priority queue. Each step pops the current best candidate off a heap, recomputes its gain against the up-to-date covered set, and either accepts it immediately (if it's still the best) or re-inserts it at its corrected priority and pops again.

07

GPU-resident bitmap, not a host-side numpy mask

The covered set lives entirely on the GPU as active_g — a uint32 bitmap over hash-table slots, cleared in place by apply_and_clear_kernel / clear_recorded_slots_kernel once a winner is chosen. (This differs from rulest, which tracks its covered set as a numpy boolean array in host memory with fancy indexing.) The host only reads active back — via remaining_active_count() — to report totals; every marginal-gain check happens on-device against the live bitmap.

08

Stop at budget, or at saturation

Selection continues until either the requested --budget is reached, or the best remaining candidate's gain drops to zero (saturation — no rule left adds any new coverage). Unlike rulest's selector, this implementation takes no cost-alpha parameter: there's no depth-based bias toward shorter chains here, and no optional 1-swap local-search pass after selection — what CELF picks is the final output.

How rule_ranker Runs This

celf_recompute_gpu.py is a standalone post-processing tool: it takes a ranker CSV or a plain .rule file already produced by ranker.py and re-selects it against a target cracked-password list. It never stores a coverage row for any rule at all, not even one. A single streaming pass computes each rule's exact full-target score once as a monotone upper bound; after that, every round re-scores candidates live on the GPU against a shrinking active bitmap, using a GPU open-addressing hash table for membership tests instead of a per-hit binary search.

rule_ranker
$ python3 -m rule_ranker.celf_recompute_gpu \ --rules-file top_optimized.rule \ --wordlist hashmob.mini.found \ --cracked hashmob.large.found \ --budget 150000 --output celf_selected.rule

Peak state is just O(n_rules) + O(cracked_universe bits): the active bitmap, the per-rule upper-bound array, and the heap — no dict, no SQLite file, no coverage matrix in any form. The RANKER_GREEDY_RESCORE_BATCH env var (default 32) controls how many speculative contenders get rescored together per round; RANKER_GREEDY_PROFILE=1 logs total rescore counts at the end.

Why This Beats Frequency Ranking

Frequency ranking asks "how many hits does this rule get on its own?" Greedy CELF asks "how many new passwords does this rule recover that nothing already selected recovers?" Those are different questions, and at every budget size the second one is the one that actually determines how many unique passwords a ruleset of size k will crack. The practical result is a ruleset that reaches a given coverage percentage with dramatically fewer rules — or reaches a much higher coverage percentage at the same rule count — than a frequency-sorted list ever can, because frequency ranking has no mechanism to notice or penalize redundancy between rules.

The submodularity guarantee: because marginal gains only ever shrink as more gets covered, CELF's lazy re-validation is not an approximation shortcut — it produces the exact same selection as naive greedy, just without the wasted rescans. The speed comes for free; nothing is traded away for it.
The Heap

Python's built-in heapq only knows how to be a min-heap — it always hands you back the smallest item first. CELF wants the opposite: the rule with the biggest possible remaining gain. The trick is to store every candidate's bound as a negative number, (-gain, rule_index). The biggest gain becomes the most negative number, which is exactly what a min-heap pops first — so a min-heap storing negated scores behaves like a max-heap of gains, without needing a separate max-heap implementation. The second item in the tuple, rule_index, is just there to break ties the same way every time (lower index wins).

Every candidate's first number isn't a guess — it's its exact score against the whole target list, computed once in an upfront GPU pass. Because coverage is submodular (a rule can only recover fewer new words later, never more, once other rules have already covered part of the list), that first score is guaranteed to be the most that rule could ever still be worth. It's a safe-to-trust ceiling, not a real-time estimate.

Picking each rule then works like this: pop the top of the heap, and actually recompute its gain against what's been covered so far. If no other rule left in the heap could possibly beat that number — because even their best-case ceiling is lower — that rule is the correct pick, full stop, no need to check anyone else. If some other rule's ceiling could still win, recompute a small batch of those too, keep whichever came out on top, and drop the rest back into the heap with their freshly tightened (and now lower) ceilings. Rules that turn out to add nothing are thrown away for good. Most of the heap is never touched in a given round — that's what makes CELF fast: it skips rescoring every candidate it can already prove loses, while still picking exactly the same rule plain greedy would have picked.

Same trick, smaller job: the ranker's own top-N extraction (picking the best k scored rules out of a stream, unrelated to CELF) uses a plain min-heap capped at size k — add freely until it's full, then swap in a new entry only when it beats the current worst one. Simpler than CELF's version because nothing ever needs to be recomputed, but the same min-heap-as-a-ceiling idea.

Real run, rule_ranker — recompute-GPU + heap path: 1M candidate rules — taken from the top-scored output of a previous rank run and fed into postprocess/CELF — selected down to a 150,000-rule budget against a 57.2M-entry cracked universe (hashmob.large.found), with the initial heap built from hashmob.mini.found upper bounds on an RTX 3060Ti. No coverage matrix was ever allocated in RAM or on disk; memory stayed at roughly O(n_rules) + O(universe bits) throughout.

StageDetail
Hash table build72.5s (vectorized, one-time)
Upper-bound pass977 batches in 1:55 (8.49 batch/s)
Greedy selection150,000 rules in 11:49 — avg. 167.3 rules/s
Coverage achieved35,760,483 / 57,238,127 cracked — 62.47%
Practical Notes
No coverage store at all

celf_recompute_gpu.py keeps no coverage rows anywhere — not a dict, not SQLite. Only the active bitmap, each rule's upper bound, and the heap are kept between rounds; every gain is recomputed live on the GPU instead of looked up.

Budget vs saturation

A fixed budget stops selection at exactly k rules. Leaving it unset runs to saturation — every rule that can still add coverage gets added, useful for finding the practical ceiling of a candidate pool before picking a production budget.

Speculative rescore batch

RANKER_GREEDY_RESCORE_BATCH (default 32, capped at the rule batch size) controls how many heap contenders get rescored together once the seed candidate's bound is beaten — fewer means less speculative GPU work, more means fewer kernel launches per round.

Tie-breaking

Heap entries are (-gain, rule_index), where rule_index is a rule's position in the input list — so equal-gain ties go to whichever rule came first in --rules-file / --ranking-csv order, deterministically, with no separate tie-break rule needed. (This differs from rulest, whose heap entries carry the rule string itself and so tie-break lexicographically.)

Takeaway: greedy CELF selection isn't a heuristic trick layered on top of frequency ranking — it optimizes a fundamentally different, and more correct, objective (union coverage instead of summed score), and CELF's lazy heap is what makes running that correct objective affordable at candidate pools from a few thousand up to millions of rules.