An FPGA (a reconfigurable chip) is built from small lookup tables: each one stores the full truth table of a Boolean function of up to six input bits. A classifier made directly of these tables, rather than of arithmetic multipliers, can answer in nanoseconds. BitLogic showed this by training lookup-table networks with gradient descent on smooth stand-ins for Boolean functions. It reports 18.63 ns latency and 72.3% CIFAR-10 accuracy with fewer than 0.3M gates on a Xilinx Zynq-7020. The same paper also reports that this training is unstable in deep stacks, and it has no way to stop logic from piling up. DNA classification is a natural target for such hardware. Its standard input is a one-hot matrix, with one bit per nucleotide per position and exactly one bit set in each position. That input is already Boolean, so no quantization step is needed. This proposal makes one claim. When the input is one-hot, most entries of a lookup table's truth table can never be reached, because two nucleotides cannot both be present at the same position. A search that works directly on truth-table bits and wiring can skip those entries, mark them as "don't care" for the downstream logic-synthesis tool, and penalize logic that is still connected but contributes almost nothing. This should give smaller circuits at equal accuracy than gradient training followed by standard synthesis.
The search method is simulated annealing. It is a single-trajectory random search that sometimes accepts a worse candidate, with probability $\exp(-\Delta E/T)$, where $\Delta E$ is the increase in cost and $T$ is a "temperature" that is lowered over time. Two weaknesses of annealing matter here. Its known failure mode on program search is drift across flat plateaus where $\Delta E=0$. On a one-hot lookup-table network, much of that plateau consists of unreachable truth-table entries, and those can be removed from the move set by construction. The second weakness is "program bloat," the genetic-programming term for growth in size without gain in accuracy. Here it takes the form of lookup tables that are wired in and consume chip area but rarely change the output. We target that bloat with a functional measure rather than a raw size count.
Core Claim
Take a one-hot encoded sequence task, such as N6-methyladenine site detection on 41-nucleotide windows (164 input bits). An annealed search with three properties should reach a better accuracy-versus-lookup-table-count tradeoff after FPGA synthesis than gradient-trained lookup-table networks. First, it proposes moves only on reachable truth-table entries. Second, it wires each table so that the table's inputs respect the one-hot position groups. Third, its cost includes how observable each table is, meaning how often flipping that table's output changes the classifier's decision. The specific new ingredient is treating the one-hot constraint as structured "don't care" space, both during search and at synthesis. Annealing is the optimizer that can use this space. Bloat control is the regularizer that turns the space into area savings.
Research Program
Search state. The state is a layered network of 6-input lookup tables, sized to match the Zynq-7020 primitive. Class scores come from population counts over the output tables, in the style of BitLogic.
Moves. There are three kinds of move. The search can flip one reachable truth-table entry. It can rewire one table input to another bit, either inside the same position group or into a new group. It can delete a table or merge it into a neighbor.
Reachability. A table input pattern is unreachable if it sets two bits from the same position group. In the first layer this is exact. In deeper layers we estimate reachability empirically by counting which patterns occur on training data, and entries that never occur become don't-cares.
Cost. The energy being minimized is
$$E = \mathcal{L}_{\text{train}} + \lambda \sum_{j} \min(1,\ o_j/\tau)$$
The symbols are defined as follows:
- $\mathcal{L}_{\text{train}}$ is training classification error.
- $o_j$ is the fraction of training samples on which flipping table $j$'s output flips the predicted class.
- $\tau$ is an observability threshold.
- $\lambda$ trades accuracy against area.
Under this cost, a table that is wired in but almost never decisive costs nearly as much as a fully used table. That pressure pushes such tables toward deletion. A pure node-count penalty would instead punish all tables equally. This follows the argument in Zhang et al., who evolve symbolic-regression formulas and regularize how rough the function is rather than how large the tree is, after showing that structural size misjudges complexity. We carry their function-over-structure idea into discrete logic, where the functional measure is observability rather than smoothness.
Incremental evaluation. A single entry flip affects only the samples that hit that entry. Its cost is therefore proportional to those samples times the downstream depth, which makes annealing over the roughly 308,000 rice samples feasible.
Warm start. We run annealing two ways: from scratch, and starting from a BitLogic solution. The warm start tests whether annealing works best as a compressor after gradient training rather than as a full replacement for it.
Export. Final truth tables go to Yosys/ABC and Vivado with don't-care entries declared. We report LUT count, latency, and power from the vendor's post-implementation numbers. We do not rely on our internal proxy for these.
The method's lineage comes from two papers. Shi, Minku and Yao evolve analog circuits with genetic programming and repair broken trees rather than discarding them. That choice brought a voltage reference down to 15 components, compared with 32–70 for prior automated methods. This motivates our choice to delete and merge logic as moves inside the search rather than penalize it after the fact, although their work stays analog and uses crossover rather than annealing. The theory of (1+1) GP with functionally complete instruction sets proves that simple mutation-based search finds conjunctions and disjunctions efficiently despite redundant operators. It constrains our expectations: its guarantees do not extend to multi-layer networks, so our claims will be empirical. Kronberger et al. explain bloat as survival through neutral space. That explanation is why we remove neutral moves from the move set rather than relying on temperature alone.
Baselines
Naive reference. The do-nothing reference is a majority-class predictor together with a single layer of randomly wired tables whose truth tables are fit greedily, one table at a time. This shows how much of the accuracy comes from the one-hot input alone.
Accuracy ceiling. The ceiling is Deep6mA, a 5-layer CNN with a bidirectional LSTM trained on 4×41 one-hot DNA. It reports 94.01% accuracy, 95.06% sensitivity and 0.98 AUC on the rice benchmark, plus above 90% cross-species accuracy. It runs on a GPU, so it is not a hardware competitor. It tells us how much accuracy the lookup-table network gives up.
Strongest hardware competitor. This is BitLogic retrained on 6mA-rice-Lv, synthesized with ABC, and implemented on the Zynq-7020. No reported result was found on Lacuna for BitLogic on any DNA benchmark. We will run it ourselves at five network sizes, with the hyperparameter budget matched to annealing's tuning budget in GPU/CPU hours. We will give it the same don't-care declaration at synthesis. That isolates whether the gain comes from searching with don't-cares in view or just from declaring them at the end.
Optimizer ablations. At equal evaluation counts, we compare annealing against greedy hill climbing and against a (1+1) evolutionary algorithm. The (1+1) algorithm is the analyzed algorithm from the GP theory paper.
Cost ablation. We swap the observability penalty for a plain live-table-count penalty.
Encoding ablation. We use 2-bit binary nucleotide codes in place of one-hot.
What counts as beating BitLogic. The test is the Pareto front of held-out AUC against post-implementation LUT count. Annealing beats BitLogic if it dominates that front at matched accuracy, using clearly fewer LUTs across at least three of the five size points, with confidence intervals over five seeds that do not overlap.
Why not just…?
Why not just train with BitLogic and let synthesis delete the dead logic? Synthesis does remove disconnected and constant logic, so purely dead bloat is already handled for free. That is why the cost targets low-observability logic that is still live, which synthesis cannot remove. The BitLogic + ABC baseline, run with don't-cares, settles this question directly. If it matches annealing on the Pareto front, the claim fails. In that case we would report annealing only as a warm-start compressor, provided that variant still helps.
Why not just use greedy local search or a (1+1) evolutionary algorithm? Once unreachable entries are pruned, the plateau that motivates annealing may shrink enough for greedy search to suffice. This is a genuine threat, and the optimizer ablation measures it directly. If hill climbing matches annealing, the contribution reduces to the reachable-move restriction and the cost function, and we will say so.
Why not just encode nucleotides in 2 bits instead of one-hot? Two bits per base halves the input width and leaves no unreachable patterns, so it could be the cheaper design. Our hypothesis is the opposite: one-hot lets a single 6-input table read three positions as direct nucleotide detectors, whereas 2-bit codes force tables to spend capacity on decoding. The encoding ablation decides this on post-implementation LUT count rather than input width.
Why not just use a size penalty? Amil et al. show that static size limits fail as data grows. Zhang et al. show that size misjudges complexity. Both findings come from symbolic regression, though, so the cost ablation tests whether they transfer to logic.
Proposed Experiments
The primary benchmark is 6mA-rice-Lv with Deep6mA's train/test split. Cross-species transfer to Arabidopsis, strawberry and rose tests whether low-observability pruning helps generalization, as the overfitting-bloat account predicts.
A secondary check reruns the method on MNIST with one-hot thresholded pixels against BitLogic's own setting. Only BitLogic's CIFAR-10 figure is reported on Lacuna, so we treat MNIST as a sanity check run on both systems.
The decisive checks are three:
- whether annealing dominates BitLogic + ABC on the AUC-versus-LUT Pareto front;
- whether removing the reachable-only move restriction erases the gain, which would confirm that the one-hot don't-care space is the mechanism;
- whether one-hot beats 2-bit encoding after implementation.
We also report latency in nanoseconds and energy per sample from Vivado. These numbers are directly comparable to BitLogic's reported 18.63 ns and 3.34 nJ on the same device.
References
- BitLogic: Training Framework for Gradient-Based FPGA-Native Neural Networks
- Enhancing Generalization in Evolutionary Feature Construction for Symbolic Regression Through Vicinal Jensen Gap Minimization
- A novel tree-based representation for evolving analog circuits and its application to memristor-based pulse generation circuit
- (1+1) Genetic Programming with Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error
- On the Success Rate of Crossover Operators for Genetic Programming with Offspring Selection
- Deep6mA: A deep learning framework for exploring similar patterns in DNA N6-methyladenine sites across different species
- A Statistical Learning Perspective of Genetic Programming