Research map / Learning theory and algorithms / Combinatorial and search optimization
CTSketch: Compositional Tensor Sketching for Scalable Neurosymbolic Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CTSketch, which decomposes a neurosymbolic symbolic program into sub-programs summarized by TT-SVD-sketched tensors so inference reduces to tensor contractions, scaling neurosymbolic learning to sums of 1024 digits.
Problem
Neurosymbolic learning must compute the output distribution of a discrete symbolic program over neural predictions, but the exact program summary tensor grows exponentially with the number of inputs, so existing methods fail on tasks with many inputs.
Approach
Manually decompose the symbolic program into a tree of sub-programs, sketch each sub-program's input-output summary tensor with tensor-train SVD into low-rank cores, and propagate distributions layer by layer via cheap contractions with the cores plus an RBF kernel and L1 normalization, with a bound on approximation error.
Key results
- CTSketch reaches 2.73% accuracy on sum_1024 where all baselines fail or time out, and 83.84% on sum_16 versus 83.01% for the next best (IndeCateR).
- CTSketch is the top performer on visudo_9 (92.50%), sudoku (81.46%), and scene (69.78%), and is within 2.55% of A-NeSI on visudo_4.
- Average epoch time for add_15 is 1.70 seconds for CTSketch versus 23.07 seconds for IndeCateR and over 20 minutes for DeepSoftLog.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use CTSketch instead of A-NeSI | visudo9 · visudo9 | accuracy: 92.11 ± 1.71 -> 92.50 ± 1.81 | Helped |
| use CTSketch instead of ISED | Sudoku solving · Sudoku solving | accuracy: 80.32 ± 1.79 -> 81.46 ± 0.53 | Helped |
| use CTSketch instead of ISED | Scene classification · Scene classification | accuracy: 68.59 ± 1.95 -> 69.78 ± 1.52 | Helped |
| use CTSketch instead of the strongest listed baseline | sum16 · sum16 | accuracy: 83.01 ± 1.18 -> 83.84 ± 0.92 | Helped |
| use CTSketch instead of the strongest listed baseline | sum64 · sum64 | accuracy: 44.43 ± 10.19 -> 47.14 ± 3.29 | Helped |
| use CTSketch instead of the strongest listed baseline | sum1024 · sum1024 | accuracy: 1.21 ± 1.28 -> 2.73 ± 0.81 | Helped |
| use CTSketch instead of DSL | add2 · add2 | accuracy: 96.6 ± 0.3 -> 96.7 ± 0.4 | Helped |
| increase sketch decomposition from dims 16 to dims 8, 2 (ablation) | CTSketch on sum16 · sum16 | accuracy: 83.52 -> 83.88 | Helped |
| increase sketch decomposition from dims 16 to dims 4, 4 (ablation) | CTSketch on sum16 · sum16 | accuracy: 83.52 -> 83.25 | Hurt |
| increase sketch decomposition from dims 16 to dims 2, 2, 2, 2 (ablation) | CTSketch on sum16 · sum16 | accuracy: 83.52 -> 82.51 | Hurt |
| replace rank-2 sketches with full one-hot tensors at dims 4, 4 (ablation) | CTSketch on sum16 · sum16 | accuracy: 83.25 -> 85.59 | Helped |
| replace rank-2 sketches with full one-hot tensors at dims 2, 2, 2, 2 (ablation) | CTSketch on sum16 · sum16 | accuracy: 82.51 -> 85.80 | Helped |
Surprising findings
- On sum_1024, CTSketch's 2.73% final-sum accuracy corresponds to about 93.69% per-digit accuracy, while A-NeSI reaches similar final accuracy with only about 17.92% per-digit accuracy.
- Full-rank sketching was not always better: the rank-8 tensor converged to 95% on HWF in 70 minutes while the full-rank tensor was still around 80% after 90 minutes.
Limitations
- Requires manual decomposition of the symbolic program into sub-programs, which may be difficult or impossible for complex tasks.
- Black-box LLM components (GPT-4) cannot be decomposed and are summarized as a single tensor.
- Error bound is derived for full reconstruction rather than the actual core-based inference used in practice.
Experimental setup
Datasets: MNIST ViSudo-PC SatNet sudoku HWF (NGS handwritten formula dataset) leaf database Multi-illumination dataset
Benchmarks: MNIST sum_n (n up to 1024) multi-digit MNIST addition add_n visual sudoku (ViSudo-PC) sudoku solving (SatNet) HWF leaf identification scene classification
Metrics: test accuracy training time per epoch reconstruction error
Baselines: Scallop DeepSoftLog IndeCateR ISED A-NeSI
Builds on: Scallop A-NeSI ISED IndeCateR DeepSoftLog
Closest papers by meaning
- DOLPHIN: A Programmable Framework for Scalable Neurosymbolic Learning (ICML 2025 · similarity 0.88)
- Data-Efficient Learning with Neural Programs (NeurIPS 2024 · similarity 0.86)
- Imbalances in Neurosymbolic Learning: Characterization and Mitigating Strategies (NeurIPS 2025 · similarity 0.85)
- Over-parameterized Student Model via Tensor Decomposition Boosted Knowledge Distillation (NeurIPS 2024 · similarity 0.85)
- Concise and Logically Consistent Conformal Sets for Neuro-Symbolic Concept-Based Models (NeurIPS 2026 · similarity 0.85)
- Efficient Sketches for Training Data Attribution and Studying the Loss Landscape (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.