ML-Based Automata Simplification for Symbolic Accelerators

Darssan Eswaramoorthi; Rasha Karakchi; Rye Stahle-Smith; Tiffany Yu

REVIEW 4 major objections 5 minor 14 references

ML-Based Automata Simplification for Symbolic Accelerators

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A machine-learning front end called AutoSlim prunes low-impact transitions from weighted finite automata, reducing FPGA logic usage by up to 40 percent while preserving ranked matching.

desk verdict AutoSlim's FPGA measurements look real, but the semantic-correctness claim is never tested and the 'ML' reduces to a threshold the authors chose themselves. read the letter →

arxiv 2507.08751 v1 pith:ULQG3GYF submitted 2025-07-11 cs.LG

Tiffany Yu , Rye Stahle-Smith , Darssan Eswaramoorthi , Rasha Karakchi This is my paper · ORCID

classification cs.LG

keywords automataprocessingfiniteFPGArandomforesttransitionpruningNAPOLY+weightedNFAsymbolicaccelerator

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

AutoSlim is a preprocessing tool that shrinks weighted finite automata before they are mapped onto the NAPOLY+ FPGA overlay. It trains a Random Forest classifier on transition-level features, chiefly a per-edge score, to decide which transitions are safe to remove. The paper's claim is that this learning-based pruning cuts automaton graph density by more than 30 percent and FPGA lookup-table usage by up to 40 percent while preserving the ranked matching behavior of the scored NFA. If that holds, symbolic workloads such as pattern matching and sequence alignment could run on substantially smaller FPGA configurations without changing their answers.

What carries the argument

The central object is the scored transition graph of a non-deterministic finite automaton as encoded for the NAPOLY+ overlay, where each edge carries a symbolic label and a numerical score and ranked matching selects minimum-cost accepting paths. The mechanism carrying the argument is a Random Forest classifier whose training labels are generated by thresholding that edge score, so the classifier learns a score-aware pruning decision per transition. The AutoSlim pipeline converts NAPOLY+ XML graphs into CSV feature records, trains the classifier, and emits pruned graphs in the original format for HLS-based synthesis. The pruning threshold $\theta$ is the parameter that defines what counts as a low-impact edge and therefore controls the resource-versus-correctness trade-off.

What would settle it

Run AutoSlim on an automaton whose edge scores have been shuffled relative to the true matching costs, then compare the ranked matches of the pruned graph on a held-out sequence set; if any minimum-cost accepting path in the original graph loses a transition that the pruned graph removed, the pruning criterion is not preserving semantic correctness.

Watch

Extended reading notes

Core claim

AutoSlim establishes that score-aware, learning-based pruning of NFA transitions can replace static structural heuristics. A Random Forest classifier trained on edge scores from a synthetic graph generator predicts which transitions are low-impact, and removing those transitions before NAPOLY+ synthesis reduces hardware resource consumption without altering which minimum-cost accepting paths the automaton selects. The paper reports over 30 percent transition pruning, up to 40 percent LUT reduction, and scaling to graphs with 64K nodes, with post-pruning transition counts remaining nearly flat as input size grows. The authors also show that fanout is a dominant driver of FPGA logic usage and that pruning lowers average fanout while preserving critical scoring paths.

Load-bearing premise

The numeric score attached to each transition, which AutoSlim uses as its main pruning signal, actually reflects how much that transition matters for producing the correct ranked matches.

Editorial extensions

If this is right

Larger symbolic workloads, up to 64K nodes, can be mapped to FPGAs with much lower LUT and register counts because pruned transition counts stay nearly flat as graph size grows.
A single trained classifier can be applied across graph sizes and densities, since AutoSlim prunes 1K to 64K node graphs with the same model.
Fanout is a major cost driver in NAPOLY+; pruning reduces average fanout and thereby mitigates routing congestion and resource blowup.
Score-aware pruning preserves ranked matching semantics, so the pruned graph still returns the same minimum-cost path rankings on matching sequences.
The HLS-based NAPOLY+ reimplementation provides cycle-accurate resource and latency estimates, making pruning benefits measurable before place-and-route.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A testable extension the authors leave implicit is running AutoSlim on a real scored workload with known match labels and checking whether the pruned graph's ranked outputs are identical to the original, which would test whether the synthetic score distribution transfers to real semantics.
Sweeping the pruning threshold $\theta$ on a fixed workload would map a resource-versus-correctness trade-off curve, showing how much hardware savings costs how much semantic risk.
Because the classifier is trained on thresholded edge scores, the same toolchain could be re-targeted to other weighted-NFA overlays by re-labeling the same transition features, making AutoSlim a general front-end for scored automata accelerators.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is an engineering paper with real FPGA measurements, but the central claim—that pruning preserves semantic correctness—is never tested, and the 'machine learning' is circular by the authors' own algorithm.

What's actually here: the topic is real. NAPOLY+ is a scored-NFA overlay, and large automata do blow up in LUTs and routing. The authors re-implemented the overlay in HLS and measured LUTs, registers, URAM, latency, and fanout on a ZCU104. The fanout analysis (Figures 6 and 7) is the most useful part: it shows concretely how interconnect complexity drives resource usage, and that pruning reduces it. Scaling to 64K nodes is a reasonable stress test. If the resource numbers reproduce, they'd be valuable to the automata-processing community.

But the paper has a load-bearing gap. It claims 'preserving semantic correctness' and 'maintaining semantic equivalence' (Section IV-D-1) without ever comparing the matching behavior of the original and pruned graphs. No precision, recall, or ranked-output comparison. Section III-C explicitly lists 'accept state preservation and edge coverage metrics' as 'planned for future work,' so the authors themselves know this is missing. You can't assert correctness you didn't measure.

The ML component is also circular. Algorithm 1 sets yi = 1[xi > theta] and trains a Random Forest on that label, using edge score as the primary feature. The forest then predicts the same threshold rule. So the paper has not demonstrated any benefit over simply thresholding the scores. The 'learning-driven' framing adds nothing unless they use other features and validate them.

There's also an internal inconsistency: the abstract claims up to 40% LUT reduction, but Section IV-D-2 shows 47K to under 7K LUTs at 64K—roughly 85%. One of those is wrong, or they're measuring different things. That needs fixing.

Who gets value from this? People building FPGA automata tools, especially on NAPOLY+. The hardware methodology and fanout findings are a credible starting point. But the paper as written doesn't support the headline claim. I'd send it to peer review with a request for major revision: test on a real benchmark like ANMLZoo, compare match/rank outputs, drop or reframe the ML contribution as a threshold baseline, and reconcile the resource numbers. There's something here, but it needs the semantic evaluation before it can be believed.

Referee Report

4 major / 5 minor

Summary. This paper presents AutoSlim, a preprocessing framework that prunes transitions from weighted NFA graphs before FPGA synthesis with the NAPOLY+ overlay. The authors generate synthetic automata datasets with edge scores, label transitions for pruning by thresholding the score, train a Random Forest classifier to predict these labels, and then use the classifier's predictions to remove transitions. They report execution time, transition counts, average transitions per node, and FPGA resource utilization (LUTs, registers, URAM) before and after pruning for graphs from 1K to 64K nodes, claiming up to 40% LUT reduction and over 30% transition pruning while preserving semantic correctness of ranked pattern matching.

Significance. If the central claim were established—that pruned graphs preserve NAPOLY+'s ranked matching behavior—AutoSlim would be a useful front-end optimization for FPGA automata accelerators. The paper's strengths are the measured hardware-resource data (e.g., Section IV-D-2), the demonstration of scaling to 64K-node graphs, and an end-to-end workflow from graph generation to HLS-based deployment. However, the central correctness claim is not measured, and the machine-learning component as described is circular, so the contribution reduces to a score-thresholding heuristic with hardware savings; the claimed significance is therefore not yet supported.

major comments (4)

[Abstract, Section III-C, Section IV-D-1] The paper asserts 'preserving semantic correctness' in the abstract and 'maintaining semantic equivalence' in Section IV-D-1, but no experiment compares the matching behavior of original and pruned graphs. For NAPOLY+, the relevant semantics is ranked matching through minimum-cost paths; the evaluation reports only transition counts, execution time, LUTs, registers, URAM, fanout, and latency. Section III-C explicitly lists 'Accept state preservation and edge coverage metrics' as 'planned for future work,' which confirms that the load-bearing correctness claim is untested.
[Algorithm 1, Section III-B] The label generation is circular. In Algorithm 1, the label-generation step sets y_i = 1[x_i > θ] for each transition, and the primary feature in the current implementation is the edge score x_i (Section III-B). Training a Random Forest on these labels and pruning with its predictions is equivalent to thresholding x_i at θ; the classifier adds no independent evidence about whether a transition is semantically dispensable. The reported 'model prediction accuracy' measures agreement with this self-generated threshold, not match accuracy.
[Section III-A] The edge scores are the sole basis for pruning, but the paper never defines how they are generated or validates them against real workloads. Section III-A says each transition is annotated with 'a numerical score representing its importance, frequency, or computational cost,' but no formula, distribution, or grounding in NAPOLY+ cost semantics is provided. Since the pruning criterion is a threshold on this score, the claimed semantic guarantee rests entirely on an unvalidated proxy.
[Abstract, Section IV-D-2] The resource-reduction claims are internally inconsistent. The abstract states 'up to 40 percent reduction in FPGA LUTs,' but Section IV-D-2 reports that the 64K dataset used over 47,000 LUTs before pruning and less than 7,000 after, an approximately 85% reduction. The authors should reconcile these numbers or restate the abstract.

minor comments (5)

[Abstract, Section II] The phrase 'ML-based learning-based graph simplification' in the abstract and introduction contains a redundant expression; please reword.
[Figures 2 and 3] The series labels 'Estimated' and 'Actual' are not defined in the text; clarify whether 'estimated' refers to a pre-ML heuristic estimate, a prediction from the trained model, or something else.
[Section IV-C] The text says pruning preserves 'classification utility,' a term that is never defined; use a term tied to the reported metrics or define it explicitly.
[Section III-B] The statement that the classifier determines which transitions can be removed 'without significantly affecting the graph's matching accuracy' is unsupported because no matching-accuracy metric is defined or reported anywhere; please define and report such a metric or remove the claim.
[Section IV-A] The explanation that execution time decreases with increasing dataset size 'primarily due to the sparsity induced by pruning' is counterintuitive for a pruning-time measurement; clarify what is being timed and why the trend is as shown.

Circularity Check

2 steps flagged · score 7.0 of 10

AutoSlim's pruning 'prediction' is defined as a threshold on the edge score; the Random Forest learns exactly that rule, so the ML step is a fitted threshold dressed as prediction.

self definitional [Algorithm 1, line 9; Section III-B (Transition Pruning via Supervised Learning)]
"Create labeled dataset D = {(xi, yi)}, where yi = ⊮[xi > θ]"

The training label for each transition is the indicator that its edge score xi exceeds threshold θ. The algorithm then trains the Random Forest on D (line 10) and prunes transitions whose predicted label is 1 (lines 12-13). Since the label is a deterministic function of the single feature xi, fitting a classifier to D can only discover the threshold rule; the pruning decision is, up to approximation error, xi > θ. Section III-B confirms the dependence: 'The primary feature used in the current implementation is the edge score' and 'Labels for training are automatically derived from score thresholds.' Thus the ML classifier is a fitted threshold, not an independent predictor of semantic importance.
fitted input called prediction [Section IV-D-1 (Pruning Effectiveness)]
"The actual number of transitions after pruning closely aligns with machine learning predictions, confirming the effectiveness of AutoSlim’s classifier in identifying low-impact edges."

The 'actual number of transitions after pruning' is produced by applying the trained classifier and keeping the transitions it predicts to keep. The 'machine learning predictions' are the same classifier outputs. Thus the agreement is a tautology: the post-pruning count is the number of predictions equal to 1. It confirms only that the classifier reproduces its own threshold-derived training labels, not that pruning preserves ranked matching semantics. No external comparison of accepted matches or minimum-cost paths is reported.

full rationale

The central pruning method is circular by construction. Algorithm 1 defines the training label as yi = 1[xi > θ] using the edge score xi, then trains a Random Forest on D and uses its predictions to prune. Since the label is a deterministic function of the only feature used, the Random Forest is fitted to approximate the threshold rule; the claimed 'ML-based pruning' reduces to thresholding edge scores. The paper itself states that labels are 'automatically derived from score thresholds' and that the primary feature is the edge score. The evaluation then treats agreement between the pruned count and the classifier predictions as confirmation, but this is a self-consistency check, not independent validation. Moreover, the semantic-correctness claim is never measured: Section III-C lists 'Accept state preservation and edge coverage metrics' as 'planned for future work', and Section IV-D-1 asserts 'maintaining semantic equivalence' without comparing original and pruned automaton outputs on NAPOLY+. The hardware resource reductions are genuine empirical measurements, but they do not validate the correctness-preservation premise. The paper therefore presents a threshold-based filter, relabeled as supervised learning, and does not provide an external test that the filter preserves the ranked matching semantics. Score 7 reflects that the central claim reduces by construction, while the hardware measurements and fanout analysis retain some independent content.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim depends on four unverified assumptions: semantic preservation under score-based pruning, classifier generalization, synthetic graph realism, and HLS equivalence to the original overlay. The free parameter theta is the actual pruning criterion, making the ML component redundant.

free parameters (1)

score threshold theta = not reported per dataset
This threshold defines the pruning labels in Algorithm 1 (yi = 1[xi > theta]). It is tuned per dataset and is the only parameter that controls which transitions are pruned.

assumptions (4)

ad hoc to paper Pruning transitions with scores below threshold theta preserves the automaton's matching semantics.
The paper claims semantic correctness preservation but provides no formal or empirical verification; the assumption is introduced in Section IV-A and is load-bearing for the central claim.
domain assumption The Random Forest classifier trained on score-derived labels generalizes to unseen transitions and graphs.
Algorithm 1 trains on a subset and applies to the rest; the paper reports model prediction accuracy but does not relate it to matching correctness.
domain assumption The synthetic graph generator produces edge scores that reflect real-world automata importance.
All evaluation uses synthetic datasets from Section III-A; no real workloads such as ANMLZoo are tested.
domain assumption The HLS-based NAPOLY+ implementation faithfully replicates the original Verilog overlay.
Section III-D states the HLS version replicates the original datapath and control behavior but no equivalence testing is described.

how reviews work

0 comments

Cite this review

Pith. "Pith review of ML-Based Automata Simplification for Symbolic Accelerators." pith.science (2026). https://pith.science/paper/ULQG3GYF

@misc{pith2026250708751,
  author       = {Pith},
  title        = {Pith review of: ML-Based Automata Simplification for Symbolic Accelerators},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ULQG3GYF}},
  note         = {Machine review of arXiv:2507.08751}
}

read the original abstract

Symbolic accelerators are increasingly used for symbolic data processing in domains such as genomics, NLP, and cybersecurity. However, these accelerators face scalability issues due to excessive memory use and routing complexity, especially when targeting a large set. We present AutoSlim, a machine learning-based graph simplification framework designed to reduce the complexity of symbolic accelerators built on Non-deterministic Finite Automata (NFA) deployed on FPGA-based overlays such as NAPOLY+. AutoSlim uses Random Forest classification to prune low-impact transitions based on edge scores and structural features, significantly reducing automata graph density while preserving semantic correctness. Unlike prior tools, AutoSlim targets automated score-aware simplification with weighted transitions, enabling efficient ranking-based sequence analysis. We evaluated data sets (1K to 64K nodes) in NAPOLY+ and conducted performance measurements including latency, throughput, and resource usage. AutoSlim achieves up to 40 percent reduction in FPGA LUTs and over 30 percent pruning in transitions, while scaling to graphs an order of magnitude larger than existing benchmarks. Our results also demonstrate how hardware interconnection (fanout) heavily influences hardware cost and that AutoSlim's pruning mitigates resource blowup.

Figures

Figures reproduced from arXiv: 2507.08751 by the authors.

**Figure 2.** Execution time across ten files for each dataset size (estimated vs. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Total transitions vs. maximum number of nodes (estimated vs. actual). [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Average Transitions per Node Before and After Pruning [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]

**Figure 7.** Figure 7: shows how maximum and minimum latency values scale with fanout. While larger fanout improves parallelism (lower min latency), it also increases routing complexity and worst-case latency. AutoSlim enables a balance by reducing average fanout while preserving critical sc…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 11 canonical work pages

[1]

Random forests

Leo Breiman. Random forests. Machine learning, 45(1):5–32, 2001

2001
[2]

An efficient and scalable semiconductor architecture for parallel automata processing

Paul Dlugosch, Dave Brown, Paul Glendenning, Michael Leventhal, and Harold Noyes. An efficient and scalable semiconductor architecture for parallel automata processing. IEEE Transactions on Parallel and Distributed Systems, 25(12):3088–3098, 2014

work page 2014
[3]

AI-Driven Optimization of Hardware Overlay Configurations

Rasha Karakchi. Ai-driven optimization of hardware overlay configura- tions. In arXiv preprint arXiv:2503.06351 , 2025

work page Pith review arXiv 2025
[4]

Rasha Karakchi and Jason D. Bakos. Napoly: A non-deterministic automata processor overlay. ACM Transactions on Reconfigurable Technology and Systems, 16:1–25, 2023

work page 2023
[5]

High-level synthesis of a genomic database search engine

Rasha Karakchi, Jordan A Bradshaw, and Jason D Bakos. High-level synthesis of a genomic database search engine. In 2016 International Conference on ReConFigurable Computing and FPGAs (ReConFig) , pages 1–6. IEEE, 2016

work page 2016
[6]

An overlay architec- ture for pattern matching

Rasha Karakchi, Charles Daniels, and Jason Bakos. An overlay architec- ture for pattern matching. In 2019 IEEE 30th International Conference on Application-specific Systems, Architectures and Processors (ASAP) , pages 165–172. IEEE, 2019

work page 2019
[7]

Developing a self-explanatory transformer

Rasha Karakchi and Ryan Karbowniczak. Developing a self-explanatory transformer. In 2024 IEEE/ACM Symposium on Edge Computing (SEC), pages 523–525. IEEE, 2024

work page 2024
[8]

A dynami- cally reconfigurable automata processor overlay

Rasha Karakchi, Lothrop O Richards, and Jason D Bakos. A dynami- cally reconfigurable automata processor overlay. In 2017 International Conference on ReConFigurable Computing and FPGAs (ReConFig) , pages 1–8. IEEE, 2017

work page 2017

Show all 14 references

[9]

A scored non-deterministic finite automata processor for sequence alignment

Ryan Karbowniczak and Rasha Karakchi. A scored non-deterministic finite automata processor for sequence alignment. In arXiv preprint arXiv:2410.19758, 2024

2024 arXiv
[10]

Optimizing sequence align- ment with scored nfas, 2025

Ryan Karbowniczak and Rasha Karakchi. Optimizing sequence align- ment with scored nfas, 2025. arXiv preprint arXiv:2501.02162

2025 arXiv
[11]

Demystifying automata processing: Gpus, fpgas or micron’s ap? In Proceedings of the International Conference on Supercomputing, pages 1–11, 2017

Marziyeh Nourian, Xiang Wang, Xiaodong Yu, Wu-chun Feng, and Michela Becchi. Demystifying automata processing: Gpus, fpgas or micron’s ap? In Proceedings of the International Conference on Supercomputing, pages 1–11, 2017

2017
[12]

Anmlzoo: a benchmark suite for exploring bottlenecks in automata processing engines and architectures

Jack Wadden, Vinh Dang, Nathan Brunelle, Tommy Tracy II, Deyuan Guo, Elaheh Sadredini, Ke Wang, Chunkun Bo, Gabriel Robins, Mircea Stan, et al. Anmlzoo: a benchmark suite for exploring bottlenecks in automata processing engines and architectures. In 2016 IEEE International Sym...

2016
[13]

Automata-to-routing: An open-source toolchain for design-space exploration of spatial au- tomata processing architectures

Jack Wadden, Samira Khan, and Kevin Skadron. Automata-to-routing: An open-source toolchain for design-space exploration of spatial au- tomata processing architectures. In 2017 IEEE 25th Annual Interna- tional Symposium on Field-Programmable Custom Computing Machines (FCCM), pa...

2017
[14]

Automata processor ap- plications in bioinformatics: A survey

Henry Woods and Yannis Papakonstantinou. Automata processor ap- plications in bioinformatics: A survey. IEEE/ACM Transactions on Computational Biology and Bioinformatics , 15(5):1770–1782, 2018

2018

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Random forests

Leo Breiman. Random forests. Machine learning, 45(1):5–32, 2001

2001

[2] [2]

An efficient and scalable semiconductor architecture for parallel automata processing

Paul Dlugosch, Dave Brown, Paul Glendenning, Michael Leventhal, and Harold Noyes. An efficient and scalable semiconductor architecture for parallel automata processing. IEEE Transactions on Parallel and Distributed Systems, 25(12):3088–3098, 2014

work page 2014

[3] [3]

AI-Driven Optimization of Hardware Overlay Configurations

Rasha Karakchi. Ai-driven optimization of hardware overlay configura- tions. In arXiv preprint arXiv:2503.06351 , 2025

work page Pith review arXiv 2025

[4] [4]

Rasha Karakchi and Jason D. Bakos. Napoly: A non-deterministic automata processor overlay. ACM Transactions on Reconfigurable Technology and Systems, 16:1–25, 2023

work page 2023

[5] [5]

High-level synthesis of a genomic database search engine

Rasha Karakchi, Jordan A Bradshaw, and Jason D Bakos. High-level synthesis of a genomic database search engine. In 2016 International Conference on ReConFigurable Computing and FPGAs (ReConFig) , pages 1–6. IEEE, 2016

work page 2016

[6] [6]

An overlay architec- ture for pattern matching

Rasha Karakchi, Charles Daniels, and Jason Bakos. An overlay architec- ture for pattern matching. In 2019 IEEE 30th International Conference on Application-specific Systems, Architectures and Processors (ASAP) , pages 165–172. IEEE, 2019

work page 2019

[7] [7]

Developing a self-explanatory transformer

Rasha Karakchi and Ryan Karbowniczak. Developing a self-explanatory transformer. In 2024 IEEE/ACM Symposium on Edge Computing (SEC), pages 523–525. IEEE, 2024

work page 2024

[8] [8]

A dynami- cally reconfigurable automata processor overlay

Rasha Karakchi, Lothrop O Richards, and Jason D Bakos. A dynami- cally reconfigurable automata processor overlay. In 2017 International Conference on ReConFigurable Computing and FPGAs (ReConFig) , pages 1–8. IEEE, 2017

work page 2017