SMTB: Fast Structure-Mapping with Tight Bounds

1.1 Water Flow →Heat Flow Example

• Structure mapping aligns relational structure rather than surface features, and the water-flow / heat-flow example shows how such an alignment can support an inference about the target.The intended mapping links beaker to coffee, water to heat, and flow to flow, helping infer that heat flows because the coffee’s temperature is greater.Source: §1 · p. 1, §1.1 · p. 2, Table 1 · p. 2

1.2 Our Motivations

• SMTB was developed as a fast, Python-accessible structure-mapping implementation after SME’s constraints and search biases excluded solutions needed in the authors’ use cases.The authors position it within CRE, which supports flexible specification and inspection of knowledge structures through wrapper languages such as Python.Source: §1 · p. 2, §1.2 · pp. 3–4
• SMTB is reported as 5–15x faster than SME and able to work in cyclic domains as well as tree-like nested predicate logic.The paper presents SMTB as an extension of CRE for structure mapping.Source: §1.2 · p. 3
• CRE provides a C++ framework callable from wrapper languages such as Python, where users can flexibly specify, inspect, and edit knowledge structures.The framework aims to support rapid iteration in cognitive systems research.Source: §1.2 · pp. 3–4

2.1 structure-mapping Theory

• Structure-Mapping Theory constrains mappings to be one-to-one, preserve argument correspondences, prefer identical expressions, and favor larger relational systems, especially nested higher-order ones.The last constraint comprises systematicity’s preference for larger systems and, particularly, those with higher-order relations and nested children.Source: §2.1 · p. 4

2.2 SME’s Implementation

• SME first generates plausible expression-pair hypotheses, then forms scored kernels from root hypotheses and their descendants, and finally greedily merges consistent kernels into complete matches.Restarting from lower-scoring seeds produces alternative interpretations, three by default.Source: §2.2 · p. 4
• SMTB aligns with the four constraints but relaxes SME’s explicit preference for deeper hierarchies, which it may still find through larger systems of overlap.This relaxes systematicity’s higher-order preference rather than making higher-order structure a special condition for mapping.Source: §2.2 · p. 5

3. When Privileging "Higher-Order" Correspondences can be a Failure Mode

• When flat first-order representations lack nested structure, SME kernels reduce to individual match hypotheses, leaving SME equivalent to greedy merging that may fail to find good mappings in larger problems.The passage notes that flat representations are common and that relational structure can exist without hierarchy.Source: §3 · p. 5
• Predicate-logic notation can impose arbitrary higher-order distinctions and obscure relational connectedness, while SMTB can map across frame-based, first-order, and nested-predicate representations.The authors also note that cycles make it unclear which elements are higher or lower, a representational distinction they argue should not constrain structure mapping.Source: §3 · pp. 5–6
• In the equation example, SME misses the shared Equal→Equal structure because unmatched numerals prevent a valid kernel, while SMTB can retain the higher-order match Pow→Num(9).Both systems map Add→Add on the shared left-hand side, but only SMTB avoids discarding the other correspondences.Source: §3 · p. 6

4. SMTB: structure-mapping with Tight Bounds

• SMTB incrementally assigns base entities to target entities, seeking a mapping that maximizes entity-pair and mutually consistent ExpressionPair weights.A one-to-one assignment cannot share a row or column.Source: §4 · pp. 6–7

4.1 Conceptual Framing with a Naive Upper Bound

• SMTB addresses the naive bound’s overcount of mutually exclusive ExpressionPairs by tightening the heuristic and updating it incrementally, supporting good greedy matches without backtracking.The naive approach also recomputes the heuristic after each assignment.Source: §4.1 · pp. 8–9

4.2 Tightening the Bounds by Peeking Ahead

• A one-step lookahead estimates the maximum ExpressionPair weight an assignment can lock in, accounting for dependent assignments that must remain one-to-one consistent.The dependency matrix distributes ExpressionPair weight among dependency slots and takes the minimum of summed row and column maxima.Source: §4.2 · pp. 9–10
• 2/3 for 0 →5 and 3/3 for 0 →10 are the tight heuristic values in the example, correctly favoring 0 →10.The heuristic uses a dependency matrix to estimate realizable ExpressionPair weight while preserving one-to-one consistency.Source: Table 6 · p. 10, §4.2 · p. 10

4.3 Preferring Global Structural Connectivity with Paired Walks

• Paired walks measure shared connectivity around each assignment without relying on higher-order predicates, unlike SME’s SES.Walk depth controls the recursive steps; a covered set bounds walk length to the domain size.Source: §4.3 · pp. 10–11
• The connectivity bias decays exponentially with search depth because it is most useful for seeding connected groups early, before assignments make candidate connections unrealizable.The bias is calculated at startup and becomes less useful as the search proceeds.Source: §4.3 · p. 11

Evaluation setup

• SMTB and SME v4 are compared head-to-head on 5,845 SME corpus domain pairs, with mappings scored under both systems’ objectives relative to SME.The corpus has five sub-corpora; both systems run single-threaded on the same device.Source: §5 · p. 11

Kernel-violation analysis

• The evaluation records the percentage of SMTB correspondences that SME would treat as kernel violations and scores mappings again after removing those assignments.This tests whether score comparisons depend on correspondences forbidden by SME’s kernel constraints.Source: §5 · pp. 11–12

Timing and scoring

• Figure 1 plots mapping-quality ratios under both objectives and model solve time, including match-hypothesis construction and search, against problem size.Problem size is the maximum number of entities between base and target.Source: §5 · p. 11, Figure 1 · p. 12

Search configurations

• SMTB’s bounded backtracking search is parameterized by branch width w and depth d; w=1, d=1 is purely greedy, and LAP over hnaive is a baseline.Branch width sets how many candidate columns a row may try; branch depth sets how far search may backtrack.Source: §5 · p. 12

Overall comparison

• For problems over 128 entities, SMTB reaches 1.80× SME on SMTB’s objective and 1.52× on SME’s objective; w=3, d=1 is 5–15x faster across problem sizes.Figure 1 reports score ratios and total solve time; the 5–15x speedup is for w=3, d=1.Source: §6 · pp. 12–13

Paired walks

• Paired walks marginally improve score quality at small runtime cost; in thermo, L=5 cuts kernel violations from 9.16% to 5.84%.In moraldm, L=5 cuts violations from 0.14% to 0.0%; ap-physics SME-objective scores rise from 34.0% above SME at L=0 to 41.9% at L=3, with a slight increase in violations.Source: §6 · p. 13

Domain-level gains

• Most of SMTB’s SME-objective advantage comes from domains where SME has not saturated available entities; gains are largest in ap-physics and smaller in moraldm.Table 8 reports about 50% more mutually consistent correspondences in more deeply nested domains such as ap-physics and moraldm.Source: §6 · p. 13, Table 8 · p. 14

Interpretation of gains

• SMTB’s larger consistent systems explain its gains in nested domains, and its SME-objective advantage persists after kernel-violation correspondences are removed.SMTB’s objective is proportional to correspondence count, whereas SME’s SES-based objective favors systems with more higher-order structure.Source: §6 · pp. 13–14

Practical and theoretical implications

• SMTB’s practical strengths are a fast, Python-accessible toolkit, flexibility across representational choices, and good mappings in large problems with higher-order structure.The authors suggest connectedness alone may suffice for good higher-order mappings, while noting that human experiments could clarify whether people privilege higher-orderness or larger connected systems.Source: §7 · p. 14

• The authors are especially excited by the practical trajectory of CRE and SMTB.Source: §8 · p. 14
• Symbolic cognitive systems often learn considerably faster than neural approaches like reinforcement learning and typically induce interpretable, robust knowledge structures.Source: §8 · p. 15
• The authors argue that, with the right tools, cognitive systems could follow a trajectory like AI capabilities accelerated by tools such as PyTorch and TensorFlow.Source: §8 · p. 15
• Structure-mapping would play a key role in a cognitive-systems trajectory because it supports rapid human-like learning and flexible pattern matching over symbolic knowledge representations.Source: §8 · p. 15