Pith. sign in

REVIEW 1 major objections 33 references

Algebraic Model Counting for Global Analysis of Optimal Decision Trees

T0 review · 1 major / 0 minor · reviewed 2026-07-03 · grok-4.3

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

Pith's one-line read Algebraic model counting unifies tasks like optimization and sampling of decision trees into semiring sum-of-products solved by dynamic programming.

desk verdict The paper recasts decision-tree analysis as algebraic model counting with a DP that runs in n^{O(Δ)} time and adds tensors for multi-metric trade-offs. read the letter →

arxiv 2607.02069 v1 pith:3EUAFHYT submitted 2026-07-02 cs.AI

Hiroki Arimura This is my paper · ORCID
classification cs.AI
keywords algebraicmodelcountingdecisiontreesdynamicprogrammingsemiringsexplainableAIoptimalglobalanalysis
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

The paper presents Algebraic Decision Tree Counting as a way to turn many different analyses of decision trees into one kind of algebraic computation. Tasks such as finding the best tree, counting how many trees meet certain rules, or sampling from near-optimal ones all reduce to the same sum-of-products problem over a semiring. A dynamic programming procedure then solves this in time O star of n to the O of depth, where n is the number of features. Multi-criterion constraints are managed by building tensors that combine the semiring values through convolution. This produces a profile of the entire space of trees and the trade-offs among accuracy, size, and fairness measures.

What carries the argument

Algebraic Decision Tree Counting (ADTC), the reformulation of analysis tasks as sum-of-products computations over semirings solved by dynamic programming on the tree structure.

What would settle it

A task such as computing a non-additive statistical property of trees where no semiring captures the required quantity exactly, or where the resulting DP runs slower than a direct specialized algorithm on the same inputs.

Watch

Extended reading notes

Core claim

ADTC reformulates diverse analytical tasks, such as optimization, counting, and sampling, into a unified sum-of-products computation over a semiring R. While the hypothesis space of decision trees is doubly exponential with respect to the maximum depth Δ, the dynamic programming algorithm achieves O star n to the O of Δ time complexity in the number of features n. Model behavior tensors aggregate semiring values via convolution products over a tensor semiring to handle complex constraints consisting of multiple tree metrics, thereby constructing a model profile that captures the global landscape and trade-offs between criteria such as accuracy, size, and fairness.

Load-bearing premise

Every analytical task on decision trees can be expressed as a single sum-of-products computation over some semiring without loss of information or prohibitive overhead in the operations.

Editorial extensions

If this is right

  • Optimization, counting, sampling, and multi-metric constraint satisfaction all become instances of the same algebraic computation.
  • Convolution over tensor semirings lets multiple criteria be combined without separate algorithms for each pair of metrics.
  • The resulting model profile directly shows the global distribution of trees and the achievable trade-offs among accuracy, size, and fairness.
  • Implementation on real datasets demonstrates that the approach supports evidence-based selection among optimal and near-optimal trees.

Reading between the lines

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

  • The same semiring reduction may apply to other recursively structured hypothesis spaces such as rule lists or shallow neural nets if they admit analogous dynamic programming.
  • Efficient semiring operations would allow repeated global queries during interactive model auditing without rebuilding the profile from scratch.
  • Techniques developed for algebraic model counting in other domains could be imported to accelerate particular choices of semiring for tree problems.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 0 minor

Summary. The paper introduces Algebraic Decision Tree Counting (ADTC), which reformulates global analysis tasks for optimal and near-optimal decision trees (optimization, counting, sampling, multi-metric constraints) as unified sum-of-products computations over a semiring R. It claims a dynamic programming algorithm running in O^*(n^{O(Δ)}) time (O* suppressing polynomials) despite the doubly exponential hypothesis space in depth Δ, and extends the framework with model behavior tensors using convolution over a tensor semiring to aggregate multiple tree metrics such as accuracy, size, and fairness. The approach is implemented in the emtrees software and illustrated on real-world datasets for evidence-based model selection in XAI.

Significance. If the reduction is faithful and the complexity bound holds, the work would provide a notable unification of analytical tasks over decision-tree hypothesis spaces via algebraic model counting, enabling efficient global profiling that is otherwise intractable. The explicit software artifact (emtrees) and empirical demonstration on datasets constitute a practical strength that supports reproducibility and applicability in sensitive domains.

major comments (1)
  1. [Abstract] Abstract: the O^*(n^{O(Δ)}) time bound for the dynamic programming algorithm and the tensor-semiring construction for multi-metric constraints are asserted without any derivation, proof sketch, or concrete definitions of the semiring operations (or the tensor semiring). This is load-bearing for the central complexity claim, as it is necessary to confirm that the reduction to an existing AMC primitive introduces no hidden exponential factors in the state space or semiring operations.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for highlighting the need for greater transparency on the central complexity claims. We address the point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the O^*(n^{O(Δ)}) time bound for the dynamic programming algorithm and the tensor-semiring construction for multi-metric constraints are asserted without any derivation, proof sketch, or concrete definitions of the semiring operations (or the tensor semiring). This is load-bearing for the central complexity claim, as it is necessary to confirm that the reduction to an existing AMC primitive introduces no hidden exponential factors in the state space or semiring operations.

    Authors: The abstract is necessarily concise and therefore omits derivations. The full manuscript defines the semiring operations (Section 2), presents the DP recurrence over feature subsets at each depth (Section 3) that yields the O^*(n^{O(Δ)}) bound by keeping the per-level state polynomial in n, and defines the tensor semiring together with its convolution product (Section 5). The reduction to AMC is direct; the chosen semirings admit polynomial-time operations and the state space does not re-introduce the double-exponential enumeration. To address the concern we will insert a compact proof sketch and the key semiring definitions into the introduction. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper frames ADTC as a direct reduction of decision-tree analysis tasks (optimization, counting, sampling, multi-metric constraints) to an existing Algebraic Model Counting primitive over a semiring, with the O^*(n^{O(Δ)}) bound following from standard dynamic programming on a state space whose size is polynomial in n for fixed depth Δ. No derivation step is shown to be self-definitional, a fitted input renamed as a prediction, or dependent on a load-bearing self-citation whose content is itself unverified. The tensor-semiring extension is presented as an orthogonal aggregation mechanism and does not collapse any central claim back to an input parameter. The derivation is therefore self-contained against external AMC benchmarks.

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

The framework rests on the algebraic properties of semirings (standard) and introduces model behavior tensors as a new aggregation device; no free parameters or fitted constants are mentioned.

assumptions (1)
  • standard math Semiring operations are closed, associative, and distribute in the required way for sum-of-products evaluation
    Invoked when the paper states that diverse tasks reduce to a unified sum-of-products computation over a semiring R
invented entities (1)
  • model behavior tensors
    purpose: aggregate semiring values via convolution products to handle multiple tree metrics simultaneously
    Introduced explicitly to manage complex constraints consisting of accuracy, size and fairness

how reviews work

0 comments
Cite this review

Pith. "Pith review of Algebraic Model Counting for Global Analysis of Optimal Decision Trees." pith.science (2026). https://pith.science/paper/3EUAFHYT

@misc{pith2026260702069,
  author       = {Pith},
  title        = {Pith review of: Algebraic Model Counting for Global Analysis of Optimal Decision Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3EUAFHYT}},
  note         = {Machine review of arXiv:2607.02069}
}
abstract

Ensuring model reliability in Explainable AI requires a global assessment of the hypothesis space. We propose a formal framework for the exhaustive analysis of optimal and near-optimal decision trees, called Algebraic Decision Tree Counting (ADTC). Inspired by Algebraic Model Counting (AMC) in knowledge representation, ADTC reformulates diverse analytical tasks, such as optimization, counting, and sampling, into a unified sum-of-products computation over a semiring $R$. While the hypothesis space of decision trees is doubly exponential with respect to the maximum depth $\Delta$, our dynamic programming algorithm achieves $O^*(n^{O(\Delta)})$ time complexity in the number of features $n$, where $O^*$ suppresses polynomial factors. To handle complex constraints consisting of multiple tree metrics, we introduce model behavior tensors that aggregate semiring values via convolution products over a tensor semiring. This algebraic approach efficiently constructs a model profile that captures the global landscape and trade-offs between criteria such as accuracy, size, and fairness. We demonstrate the utility of our software, emtrees, on real-world datasets, illustrating how ADTC facilitates evidence-based model selection in sensitive domains.

Figures

Figures reproduced from arXiv: 2607.02069 by the authors.

Figure 1
Figure 1. Model profiles of 34,706 decision trees with [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Model profiles of 34,706 decision trees with [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. (a) Model profiles generated by ADTC on the adult dataset showing the struc￾tural distribution of near-optimal models (Sec. 5.3). (b) Dashboard interface for select￾ing a model from the cross-table to display its decision tree (Sec. 4.2). 3-way contingency tables [20]. Let indices i, j, k ∈ {0, 1} represent the true label y, predicted label yˆ = ft(x), and sensitive attribute z in a dataset S, respectively. For a tr… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Scalability of ADTC relative to data size (Sec. 5.2). k-th cell of T holds a pair T(k) = (Nk, tk) consisting of a count Nk ∈ N and a tree tk ∈ M∆. The first semiring N = (N, +, ×) maintains the count Nk of trees falling into the k-th cell of T, Nk = T(k) ∈ N, for all i…
Figure 5
Figure 5. Figure 5: Impact of maximum depth on efficiency (Sec. 5.2). [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: Effect of tree size on resolution (Sec. 5.2). [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: Model profiles generated by ADTC on the adult dataset. Horizontal axes de￾note accuracy; vertical axes represent (c) EOdd and (d) EOpp gaps. Higher values are better for accuracy, whereas lower values indicate better fairness (Sec. 5.4). 5.3 Impact of model complexity …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    In: Proc

    Aglin, G., Nijssen, S., Schaus, P.: Learning optimal decision trees using caching branch-and- bound search. In: Proc. AAAI. vol. 34, pp. 3146–3153 (2020)

    work page 2020

  2. [2]

    IEEE transactions on Information Theory46(2), 325–343 (2002)

    Aji, S.M., McEliece, R.J.: The generalized distributive law. IEEE transactions on Information Theory46(2), 325–343 (2002)

    work page 2002

  3. [3]

    Arimura, H.:emtrees: algebraic model counting-based tool for optimal decision tree anal- ysis (2026).https://doi.org/10.5281/zenodo.20842908

    work page doi:10.5281/zenodo.20842908 2026

  4. [4]

    of the Int’l Fed

    Arimura, H., Osabe, K., Uno, T.: Optimization and enumeration of decision trees from mas- sive data sets (talk),10.5281/zenodo.20837712, the 23rd Conf. of the Int’l Fed. of Oper. Res. Soc. (IFORS), Québec (17 July 2017)

    work page doi:10.5281/zenodo.20837712 2017

  5. [5]

    Fagin's Theorem for Semiring Turing Machines

    Badia, G., Droste, M., Eiter, T., Kiesel, R., Noguera, C., Paul, E.: Fagin’s theorem for semir- ing turing machines. arXiv preprint arXiv:2507.18375 (2025) 18 Hiroki Arimura

    work page Pith review arXiv 2025

  6. [6]

    Bakibayev, N., Olteanu, D., Závodn `y, J.: FDB: A query engine for factorised relational databases. Proc. the VLDB Endowment5(11) (2012)

    work page 2012

  7. [7]

    In: Proc

    Black, E., Raghavan, M., Barocas, S.: Model multiplicity: Opportunities, concerns, and so- lutions. In: Proc. FAccT 2022. pp. 850–863 (2022)

    work page 2022

  8. [8]

    Breiman, L.: Statistical Modeling: The Two Cultures (with comments and a rejoinder by the author). Stat. Sci.16(3), 199 – 231 (2001)

    work page 2001

Show all 33 references
  1. [9]

    CRC press (1984)

    Breiman, L., Friedman, J., Stone, C.J., Olshen, R.A.: Classification and regression trees. CRC press (1984)

    1984

  2. [10]

    Bürgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic complexity theory, vol. 315. Springer Science & Business Media (2013)

    2013

  3. [11]

    MIT press, 3rd edn

    Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms. MIT press, 3rd edn. (2009)

    2009

  4. [12]

    JAIR17, 229–264 (2002)

    Darwiche, A., Marquis, P.: A knowledge compilation map. JAIR17, 229–264 (2002)

    2002

  5. [13]

    In: Proc: AAAI

    Demirovi ´c, E., Stuckey, P.J.: Optimal decision trees for nonlinear metrics. In: Proc: AAAI. vol. 35-5, pp. 3733–3741 (2021)

    2021

  6. [14]

    Dong, J., Rudin, C.: Exploring the cloud of variable importance for the set of all good models. Nat. Mach. Intell.2, 810–824 (2019)

    2019

  7. [15]

    Springer, 2 edn

    Ebbinghaus, H.D., Flum, J., Thomas, W.: Mathematical Logic. Springer, 2 edn. (1994)

    1994

  8. [16]

    JAIR77, 207–293 (2023)

    Eiter, T., Kiesel, R.: Semiring reasoning frameworks in AI and their computational complex- ity. JAIR77, 207–293 (2023)

    2023

  9. [17]

    In: Proc

    Goral, A., Giesen, J., Blacher, M., Staudt, C., Klaus, J.: Model counting and sampling via semiring extensions. In: Proc. AAAI. vol. 38, pp. 20395–20403 (2024)

    2024

  10. [18]

    In: Proc: AAAI

    Hara, S., Maehara, T.: Enumerate lasso solutions for feature selection. In: Proc: AAAI. vol. 31 (2017)

    2017

  11. [19]

    NeurIPS29, 3323–3331 (2016)

    Hardt, M., Price, E., Srebro, N.: Equality of opportunity in supervised learning. NeurIPS29, 3323–3331 (2016)

    2016

  12. [20]

    Springer Series in Statistics, Springer (2001)

    Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning. Springer Series in Statistics, Springer (2001)

    2001

  13. [21]

    ICML HILL Workshop, arXiv:1906.01876 (2019)

    Kanamori, K., Hara, S., Ishihata, M., Arimura, H.: Enumeration of distinct support vectors for interactive decision making. ICML HILL Workshop, arXiv:1906.01876 (2019)

    1906 arXiv

  14. [22]

    Journal of Ap- plied Logic22, 46–62 (2017)

    Kimmig, A., Van den Broeck, G., De Raedt, L.: Algebraic model counting. Journal of Ap- plied Logic22, 46–62 (2017)

    2017

  15. [23]

    In: Proc

    Lin, J., Zhong, C., Hu, D., Rudin, C., Seltzer, M.: Generalized and scalable optimal sparse decision trees. In: Proc. ICML. pp. 6150–6160 (2020)

    2020

  16. [24]

    In: Proc

    Marx, C., Calmon, F., Ustun, B.: Predictive multiplicity in classification. In: Proc. ICML

  17. [25]

    6765–6774 (2020)

    pp. 6765–6774 (2020)

    2020

  18. [26]

    In: Proc

    Mata, K., Kanamori, K., Arimura, H.: Computing the collection of good models for rule lists. In: Proc. the 18th MLDM, arXiv:2204.11285 (2022)

    2022

  19. [27]

    Theoretical Computer Science270(1-2), 609–623 (2002)

    Mehta, D., Raghavan, V .: Decision tree approximations of boolean functions. Theoretical Computer Science270(1-2), 609–623 (2002)

    2002

  20. [28]

    Data Mining and Knowledge Discovery21(1), 9–51 (2010)

    Nijssen, S., Fromont, E.: Optimal constraint-based decision tree induction from itemset lat- tices. Data Mining and Knowledge Discovery21(1), 9–51 (2010)

    2010

  21. [29]

    Statistic Surveys16, 1–85 (2022)

    Rudin, C., Chen, C., Chen, Z., Huang, H., Semenova, L., Zhong, C.: Interpretable machine learning: Fundamental principles and 10 grand challenges. Statistic Surveys16, 1–85 (2022)

    2022

  22. [30]

    In: Proc

    Ruggieri, S.: Enumerating distinct decision trees. In: Proc. ICML. pp. 2960–2968 (2017)

    2017

  23. [31]

    Cambridge University Press (2014)

    Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning - From Theory to Al- gorithms. Cambridge University Press (2014)

    2014

  24. [32]

    SIAM Journal on Computing8(3), 410–421 (1979)

    Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM Journal on Computing8(3), 410–421 (1979)

    1979

  25. [33]

    NeurIPS35, 14071–14084 (2022)

    Xin, R., Zhong, C., Chen, Z., Takagi, T., Seltzer, M., Rudin, C.: Exploring the whole rashomon set of sparse decision trees. NeurIPS35, 14071–14084 (2022)

    2022

Pith tools

Reviewed July 3, 2026 · model on record in the stance chip above.