Making the Cyclic Quorum Solvers Fast

---

# ⚡ Making the Cyclic Quorum Solvers Fast

## Symmetry pruning, a resurrected RL agent, and a lock-free brain 🧠

### 🔍 → 🤖 → 🧵

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**Part 1 — The Setup** 🧭
- Difference covers, quickly
- The two solvers
- How we measure 📏

**Part 2 — Symmetry Pruning** 🔄
- Necklace → bracelet
- The `q[]` / `CheckRev` port
- Equivalence + speedup ✅

**Part 3 — The RL Agent That Never Learned** 🤖
- The silent no-op gradient 🕳️
- Real REINFORCE + entropy
- Learning curves 📈

]
.pull-right[

**Part 4 — RL Efficiency** ⚡
- Cache the forward pass
- Kill the allocations
- Lock-free (Hogwild) 🧵

**Part 5 — Robustness** 🛡️
- Overflow-safe validation
- Fuzzing & bounds checks

**Part 6 — Results & Lessons** 🎓

]

---

## 🧭 Part 1 — The Setup

---

### 🧩 Difference Covers, Quickly

A **base quorum** ${\color{salmon}B_0} = \{a_1, \dots, a_d\}$ generates a cyclic quorum
system by shifts ${\color{salmon}B_i} = {\color{salmon}B_0} + i \pmod N$.

It works **iff** every non-zero residue is hit by a pair difference:

$$ \forall m \in \{1,\dots,N-1\},\; \exists a_u,a_v \in {\color{salmon}B_0}:\;
   a_u - a_v \equiv {\color{royalblue}m} \pmod N $$

The set ${\color{salmon}B_0}$ is a **relaxed difference cover**. Finding the smallest
${\color{royalblue}d}$ is the hard part. 🧠

> Valid inputs: $N \ge 3$, $d \ge 3$, ${\color{royalblue}N \le d(d-1)+1}$.

---

### 🛠️ Two Solvers, One Problem

<pre>
graph LR
    P["Difference cover\nN, d"]
    S["Combinatorial search\nDcGenerator + ThreadPool"]
    R["Reinforcement learning\nPolicyNetwork"]
    P --> S
    P --> R
    S -->|"exhaustive,\nguaranteed ✅"| SOL["Base quorum"]
    R -->|"learned,\nno guarantee 🎲"| SOL
    style P fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style S fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style R fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style SOL fill:#d1c4e9,stroke:#6a1b9a,stroke-width:3px
</pre>

]

This deck is about **making both fast — and making the RL one actually work**. 🔬

---

### 📏 How We Measure

| Metric | Search 🔍 | RL 🤖 |
|:-------|:----------|:------|
| Speed | wall clock / enumeration | episodes to first solution |
| Correctness | every residue covered ✅ | every residue covered ✅ |
| Progress | nodes explored | mean residue coverage |
| Stability | deterministic | repeated trials (variance!) |

> Profiling first, then optimize — the bottleneck is rarely where you guess. 🔎

---

## 🔄 Part 2 — Symmetry Pruning

---

### 🪞 Two Symmetries, Not One

The original search only broke **rotation** symmetry (necklaces). It ignored
**reflection** — the reversal $a_i \mapsto N - a_i$. 🔁

<pre>
graph TD
    T["Search tree"]
    ROT["Rotation classes\nnecklaces"]
    BR["Rotation + reflection\nbracelets"]
    T --> ROT
    ROT -->|"add CheckRev"| BR
    ROT -->|"~2× redundant"| X["equivalent branches\nre-explored ❌"]
    style T fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style ROT fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style BR fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style X fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
</pre>

]

---

### 🧩 The Port: `b[]` → `q[]` + `CheckRev`

`diff_cover3.cpp` already had the bracelet machinery. We ported it into the main solver. 🔧

```cpp
int CheckRev(int t_1) {
    for (int idx = a[1]; idx <= t_1 / 2; ++idx) {
        if (q[idx] < q[t_1 - idx]) return  1;   // prefix smaller
        if (q[idx] > q[t_1 - idx]) return -1;   // reverse smaller
    }
    return 0;                                   // palindromic prefix
}
```

- `q[value]` — membership marker of the current configuration
- Skip the branch when the **reverse is lexicographically smaller** (`rev == -1`)
- `GenD` → `BraceFD`, `Gen11` → `BraceFD11`

---

### ✂️ Where the Pruning Fires

<pre>
graph LR
    A["extend prefix\na[t+1] = max"] --> B{"a[1] == max - a[t]?"}
    B -->|"no"| C["recurse normally"]
    B -->|"yes"| D["CheckRev(max)"]
    D -->|"rev == -1\nreverse smaller"| E["PRUNE ✂️"]
    D -->|"rev != -1"| F["recurse"]
    style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style B fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style D fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style E fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style F fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style C fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
</pre>

]

> Reflection only helps near the symmetric frontier — hence a **modest** gain. 📏

---

### ✅ Equivalence: 12 Cases, Zero Invalid

Every reported cover re-checked with the residue-coverage rule:

| N | d | new | reference | identical | invalid |
|:--|:--|:----|:----------|:----------|:--------|
| 15 | 5 | 76 | 76 | ✅ | 0 |
| 21 | 5 | 2 | 2 | ✅ | 0 |
| 31 | 6 | 10 | 10 | ✅ | 0 |
| 57 | 8 | 12 | 12 | ✅ | 0 |
| 73 | 9 | 8 | 8 | ✅ | 0 |
| 91 | 10 | 12 | 12 | ✅ | 0 |

]

…plus N=25/37/43/49/65/81 — all byte-for-byte identical to `diff_cover3`. 🎯

---

### ⚡ Speedup: Real but Modest

<text x="170" y="178" text-anchor="end">N=91, d=10 (10T)</text>
    <rect x="180" y="164" width="144" height="18" fill="#a3be8c" rx="3"/>
    <text x="332" y="178" fill="#2e7d32" font-weight="bold">1.07×</text>
  </g>
  <text x="16" y="238" font-family="sans-serif" font-size="12" fill="#4c566a">Pruning only triggers at the symmetric frontier → ~10–17% overall.</text>
</svg>

</p>

---

## 🤖 Part 3 — The RL Agent That Never Learned

---

### 🕳️ The Silent Bug

`RL_mt.cpp` allocated gradients, computed a local `gradLogits`… and **threw it away**.
`update()` then subtracted **zero** from every weight. 😱

```cpp
for (size_t t = 0; t < states.size(); ++t) {
    std::vector<float> gradLogits(N, 0.0f);      // local!
    for (int idx = 0; idx < N; ++idx)
        gradLogits[idx] = returns[t] * (indicator - probs[idx]);
}                                                  // gradLogits dies here

policyNet.update(gradW1, gradB1, ...);             // gradW1.. all zero 😴
```

> The "AI" was a **fixed random policy** wearing a neural network costume. 🎭

---

### 📉 Proof: It Was Flat as a Pancake

Single-thread probe, mean residue coverage over 40 000 episodes (N=15, d=5):

</p>

---

### 📐 Real REINFORCE

We maximise the expected return with the policy-gradient theorem:

$$ \nabla_\theta J \;=\; \mathbb{E}\Big[\, {\color{#a3be8c}G_t}\,
   \nabla_\theta \log \pi_\theta(a_t \mid s_t) \,\Big] $$

For a softmax head the logit gradient is clean:

$$ \frac{\partial \log \pi(a)}{\partial z_i} \;=\; {\color{#5e81ac}\delta_{ia}} - {\color{#5e81ac}p_i}
   \quad\Longrightarrow\quad
   \frac{\partial L}{\partial z_i} \;=\; {\color{#a3be8c}G_t}\,\big(p_i - \delta_{ia}\big) $$

and weights descend ${\color{#bf616a}w \leftarrow w - \eta\,\partial L/\partial w}$. ✅

---

### 🌡️ The Entropy Bonus (and Its Sign)

To keep exploring, add an entropy bonus ${\color{#ebcb8b}\beta H}$ with
$H = -\sum_a p_a \log p_a$:

$$ \frac{\partial H}{\partial z_i} \;=\; -\,{\color{#5e81ac}p_i}\,\big(\log p_i + H\big) $$

To **maximise** $H$ under $w \leftarrow w - \eta\,\partial L/\partial w$, the loss gradient
must carry $+{\color{#ebcb8b}\beta}\,p_i(\log p_i + H)$:

$$ \frac{\partial L}{\partial z_i} \;=\;
   {\color{#a3be8c}G_t}(p_i-\delta_{ia})
   \;{\color{#a3be8c}+}\;{\color{#ebcb8b}\beta\,p_i(\log p_i + H)} $$

> `RL_mt2.cpp` and `RL2.cpp` had a **`−`** there — it *minimised* entropy and collapsed. 🕳️

---

### 🎯 Does the Sign Fix Matter? Yes.

N=31, d=6, 16 trials, 15 s budget each — **solutions found**:

<text x="150" y="156" text-anchor="end">old  (−β)</text>
    <rect x="160" y="136" width="200" height="28" fill="#bf616a" rx="3"/>
    <text x="370" y="156" fill="#bf616a" font-weight="bold">5 / 16</text>
  </g>
  <text x="16" y="205" font-family="sans-serif" font-size="12" fill="#4c566a">The old sign sharpens the policy (H → 0.05) and gets stuck; +β keeps searching. 🎲</text>
</svg>

</p>

---

## ⚡ Part 4 — RL Efficiency

---

### 🔁 #2a — Cache the Forward Pass

The old loop **re-forwarded** every state during backprop. We cache activations during rollout. 🗃️

<pre>
graph TD
    subgraph OLD["Before · 2T forwards"]
        O1["rollout\nforward × T"] --> O2["backward\nforward × T again"]
    end
    subgraph NEW["After · T forwards"]
        N1["rollout\nforward × T"] --> N2["backward\nreuse cached ✅"]
    end
    style O1 fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style O2 fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style N1 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style N2 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
</pre>

]

> Bonus: cached activations are **consistent** with the sampled probabilities. 🎯

---

### 🧹 #2b — Reuse Per-Thread Buffers

Every episode used to allocate fresh vectors. Now they live **outside** the episode loop. 📦

```cpp
const int T = D - 1; const int IN = 2 * N;
std::vector<std::vector<float>> states(T, std::vector<float>(IN));
std::vector<ForwardResult> fwdList(T);   // activations, reused
std::vector<std::vector<float>> gradW1(HIDDEN_SIZE1, std::vector<float>(IN, 0.0f));
// ... once per thread, not once per episode
```

- `resize()` on an already-sized buffer is a **no-op** after the first episode ✅
- `softmax(logits, probs)` writes into a caller buffer instead of returning one

---

### 🧵 #2d — Lock-Free (Hogwild)

The update mutex serialised 10 threads. We removed it — async SGD tolerates lost updates. 🏎️

```cpp
void update(...) {          // no mutex — Hogwild async SGD
    for (row...) W1[row][col] -= LEARNING_RATE * gradW1[row][col];
}
```

<pre>
graph LR
    W1["worker 1"] --> NET["shared network"]
    W2["worker 2"] --> NET
    W3["worker N"] --> NET
    NET --> OUT["mutex only on output ✅"]
    style W1 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style W2 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style W3 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style NET fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style OUT fill:#fff9c4,stroke:#f57f17,stroke-width:3px
</pre>

]

> Formally a C++ data race (UB) — **documented**, relies on tear-free aligned floats. ⚠️

---

### 📊 Throughput & Scaling

<text x="170" y="136" text-anchor="end">post-opt · 1 thread</text>
    <rect x="180" y="118" width="270" height="24" fill="#a3be8c" rx="3"/>
    <text x="458" y="135" fill="#2e7d32" font-weight="bold">50.8 s · 1.48×</text>

<text x="170" y="196" text-anchor="end">post-opt · 10 threads</text>
    <rect x="180" y="178" width="28" height="24" fill="#5e81ac" rx="3"/>
    <text x="216" y="195" fill="#5e81ac" font-weight="bold">5.34 s · 9.5×</text>
  </g>
  <text x="180" y="248" font-family="sans-serif" font-size="13" fill="#4c566a">Cache + buffers: <tspan font-weight="bold" fill="#2e7d32">1.48×</tspan> single-thread.</text>
  <text x="180" y="272" font-family="sans-serif" font-size="13" fill="#4c566a">Hogwild: <tspan font-weight="bold" fill="#5e81ac">9.5×</tspan> scaling on 10 threads.</text>
</svg>

</p>

---

## 🛡️ Part 5 — Robustness

---

### 🧱 Overflow-Safe Validation

The guard `N > d*(d-1)+1` was computed in **32-bit `int`** — it overflows for huge `d`. 💥

$$ {\color{#bf616a}d = 2\,147\,418\,113}:\quad d(d-1)+1 \text{ wraps} \;\Rightarrow\; \text{guard passes} $$

Fix (all four solvers):

```cpp
if (N < 3 || D < 3 || D > N || N > MAX_N ||
    (long long)N > (long long)D * (D - 1) + 1) { usage(); return 1; }
```

- `long long` product → no wrap
- `D > N` → a cover cannot exceed the ring size
- `MAX_N` bound → keeps `int` size arithmetic safe

---

### 🧪 Fuzzing the CLI

Crafted inputs across `diff_cover`, `RL_mt`, `RL_mt2`, `RL2`:

| Input | Verdict |
|:------|:--------|
| no args · `5` · `2 5` · `5 2` | ✅ usage, exit 1 |
| `0 0` · `-1 5` · `5 -1` | ✅ usage, exit 1 |
| `2147483647 3` · `3 2147483647` | ✅ rejected |
| `33554433 2147418113` (overflow pair) | ✅ rejected |
| `241 16` (search max) · `273 17` (RL max) | ✅ accepted |
| `91 10` (valid) | ✅ runs to completion |

]

> No crashes, no out-of-bounds — just clean rejects. 🧯

---

### 🧷 Memory-Safety Checks

- `_GLIBCXX_ASSERTIONS` build → **no `std::vector` out-of-bounds** in any binary ✅
- `diff_cover` equivalence re-run under the same build → identical output ✅
- RL outputs re-validated as genuine difference covers: **12/12** each ✅
- ASan/UBSan unavailable in the MinGW toolchain (noted, not a blocker) 📝

<pre>
graph LR
    B["bounds guard"] --> V["validated input"]
    V --> A["_GLIBCXX_ASSERTIONS"]
    A --> O["valid cover ✅"]
    style B fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style V fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style A fill:#d1c4e9,stroke:#6a1b9a,stroke-width:3px
    style O fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
</pre>

]

---

## 🎓 Part 6 — Results & Lessons

---

### 📋 Results at a Glance

| Change | File | Effect |
|:-------|:-----|:-------|
| Bracelet symmetry | `diff_cover.cpp` | **1.07–1.17×**, output identical ✅ |
| Real backprop | `RL_mt.cpp` | coverage **12.5 → 13.9** (was flat) ✅ |
| Entropy sign fix | `RL_mt2.cpp`, `RL2.cpp` | **11/16** vs 5/16 solved ✅ |
| Cache + buffers | `RL_mt.cpp` | **1.48×** single-thread ✅ |
| Lock-free Hogwild | `RL_mt.cpp` | **9.5×** on 10 threads ✅ |
| Overflow-safe guard | all solvers | no OOB / no crash ✅ |

]

> Two of these were **bugs**, not tuning: a no-op gradient and an inverted sign. 🐛

---

### 🧠 Key Takeaways

**Correctness first** 🐛
- A "learning" agent with a discarded gradient is just **random search in disguise**
- An inverted entropy sign silently **collapses** the policy — derive the sign, don't guess

**Measure the right thing** 📏
- Mean coverage looked like a regression in one seed; **solution-finding rate** told the truth
- High variance needs **many trials**, not one curve

**Optimize with evidence** ⚡
- Cache recomputation (#2a), reuse buffers (#2b), drop the lock (#2d)
- Pruning helps only where it actually fires (symmetry frontier)

---

### 📜 Artifacts From This Session

| Artifact | Where |
|:---------|:------|
| Issue (suggestions + progress) | `luk036/cyclic_quorum#4` |
| Symmetry port | `src/diff_cover.cpp` (`CheckRev`, `BraceFD`) |
| Backprop + entropy | `src/RL_mt.cpp` (`ForwardResult`, `backward`) |
| Entropy sign fix | `src/RL_mt2.cpp`, `src/RL2.cpp` |
| Hardened validation | all four solvers |
| Docs | `AGENTS.md`, `src/RL_mt.md` |

> Not committed at time of writing — working tree changes. 🌱

---

# 🙋 Q&A

**Making the Cyclic Quorum Solvers Fast**

### Questions? Discussion? 💬

---

# 👏 Thank You

## Make it correct, then make it fast. 🎯

Slides built with Remark.js 🎉 | KaTeX 📐 | Mermaid 🧩 | Nord Theme 🌙