Ultrametric Nested Semantic Graphs: A Language‑Neutral Meaning Representation

#1. Introduction

Multilingual natural‑language processing systems must serve speakers of languages whose morphological typology ranges from isolating to polysynthetic. In isolating languages token‑level matching suffices, but in agglutinative languages such as Turkish and polysynthetic languages such as Mohawk a single surface word can encode an entire clause. This inflates the lexical inventory, reduces the precision of cross‑lingual search engines, raises error rates in machine translation for low‑resource languages, and prevents indexing of polysynthetic corpora without exhaustive morphological analysis. If a representation existed that abstracted away from language‑specific morphology while preserving semantic structure, a single design of parsers, indexers, and retrieval algorithms could serve all typologies.

This paper addresses that gap by introducing Ultrametric Nested Semantic Graphs (UNSGs), in which sentences are mapped to rooted graphs whose node distances are defined by the height of their lowest common ancestor (LCA). The resulting distance function satisfies the strong triangle inequality (the ultrametric property) [1], guaranteeing that any three nodes form an isosceles triangle with the two longer sides equal. This topology supports efficient subgraph‑matching retrieval because distance‑based pruning can be performed using a single scalar bound.

Contributions

1. Formal definition of UNSGs and the associated ultrametric distance (Section 3).
2. Proof that the distance satisfies the strong triangle inequality (Section 4.1).
3. Explicit numeric example illustrating distance computation and verification of the inequality (Section 4.2).
4. Derivation of a planar slope bound of 4 for UNSGs of maximum degree 3 using the planar slope number result [5] (Section 4.3).
5. Comb‑metric embedding that shows isometry between the leaf metric and a compact ultrametric space [7] (Section 4.4).
6. Mapping of UNSGs to word‑representable split graphs and discussion of representation‑number limits [4] (Section 5).
7. Algebraic encoding of UNSGs via generalized path algebras [8] and hyper‑loop module structures [6] (Section 5).
8. Exact combinatorial cost calculations for parsing and pattern matching (Section 4.5).
9. Limitations, falsifiability condition, and open questions (Section 7).
10. Practical implications, technology readiness, and a minimal de‑risking experiment (Section 8).

#2. Background and Related Work

The notion of an ultrametric space, defined by the strong triangle inequality $d(x,z)\le\max\{d(x,y),d(y,z)\}$ [1, §1.1], provides a natural formalism for hierarchical similarity. Comb‑metric constructions generate compact ultrametric spaces from functions $f\colon I\to[0,\infty)$, with the induced pseudo‑distance $\bar d_f(s,t)=\max_{(s\wedge t,\,s\vee t)}f$ shown to be ultrametric [7, §2.1]. Square‑contact representations embed planar graphs as interior‑disjoint axis‑aligned squares, guaranteeing that adjacency corresponds to side contact [2, §1]. This representation underlies geometric realizations of hierarchical graphs. The planar slope number $psn(G)$, the minimum number of edge slopes in a planar straight‑line drawing, satisfies $psn(G)\le\max\{4,\Delta\}$ for graphs of maximum degree $\Delta$ [5, §3], enabling low‑complexity drawings of UNSGs. Word‑representable split graphs are characterized by semi‑transitive orientations, yet their representation number remains open [4, §1]. Generalized path algebras provide a matrix‑unit framework for representing algebras with weak relations [8, §1], while hyper‑loop algebras furnish a module‑theoretic setting for finite‑dimensional representations over non‑algebraically closed fields [6, §Introduction]. Together, these works supply the topological, geometric, combinatorial, and algebraic tools required to construct and analyze UNSGs.

#3. Methods

#3.1 Graph Construction

Given a sentence $S$, a syntactic parser yields a rooted tree $T=(V_T,E_T)$ whose leaves correspond to lexical tokens and internal nodes to syntactic constituents (e.g., noun phrase, verb phrase). The Ultrametric Nested Semantic Graph $G=(V,E)$ is obtained by treating $T$ as a directed acyclic graph and adding an undirected edge between any two nodes $u,v\in V$ if and only if $u$ and $v$ are siblings in $T$. The resulting graph is planar because sibling edges can be embedded without crossing using a square‑contact representation [2].

#3.2 Ultrametric Distance

For any two nodes $u,v\in V$, define the distance

where $h(\cdot)$ returns the height (distance from the root) of the lowest common ancestor in $T$. By construction, $d$ is non‑negative, symmetric, and $d(u,u)=0$. The strong triangle inequality follows directly from the definition of LCA:

which is precisely the ultrametric condition [1, Eq. (1.1)].

#3.3 Comb‑Metric Realization

Following the comb construction [7, §3.1], assign to each leaf $l\in V$ a coordinate $s_l\in[0,m]$ where $m$ equals the total number of leaves. Define a piecewise‑constant function $f$ that jumps at the positions corresponding to internal node heights. The induced comb metric $\bar d_f$ coincides with $d$ on the leaf set, establishing an isometric embedding of $G$ into a compact ultrametric space.

#3.4 Planar Embedding and Slope Bound

The maximum degree $\Delta$ of $G$ equals the maximum branching factor of $T$. For typical sentences $\Delta\le3$. Applying the planar slope number bound $psn(G)\le\max\{4,\Delta\}$ [5, §3] yields $psn(G)\le4$, guaranteeing that $G$ can be drawn with at most four distinct edge slopes.

#3.5 Mapping to Word‑Representable Split Graphs

Identify the clique $C$ of $G$ with the set of internal nodes and the independent set $I$ with leaves. The adjacency condition “two vertices alternate in a word” translates to sibling adjacency in $G$. Although the representation number of split graphs is unknown [4, §1], this mapping situates UNSGs within the broader class of word‑representable graphs.

#3.6 Algebraic Encoding

Let $\Lambda$ be a generalized path algebra with weak relations [8, §3]. Assign to each vertex $v\in V$ an idempotent $e_v$ and to each edge $(u,v)$ a bimodule $A_{uv}$. The resulting $\Lambda$‑module system encodes the graph structure algebraically. Moreover, interpreting $\Lambda$ as a hyper‑loop algebra module [6, §Introduction] provides a representation‑theoretic perspective on UNSGs, enabling the use of module‑theoretic tools for analysis.

#4. Analysis

#4.1 Numeric Example

Consider the simple sentence “John eats apple”. The parser yields the tree $T$:

• Root $S$ (height 2)
• Left child $NP$ (height 1) containing leaf $John$ (height 0)
• Right child $VP$ (height 1) containing leaves $eats$ (height 0) and $apple$ (height 0)

The vertex set is $V=\{S,NP,VP,John,eats,apple\}$. Distances:

1. $d(\text{John},\text{eats}) = h(\operatorname{LCA}(\text{John},\text{eats})) = h(S) = 2$.
2. $d(\text{John},\text{apple}) = h(\operatorname{LCA}(\text{John},\text{apple})) = h(S) = 2$.
3. $d(\text{eats},\text{apple}) = h(\operatorname{LCA}(\text{eats},\text{apple})) = h(VP) = 1$.

Verification of the ultrametric inequality for the triple $(\text{John},\text{eats},\text{apple})$:

• $\max\{d(\text{John},\text{eats}), d(\text{eats},\text{apple})\} = \max\{2,1\}=2$.
• $d(\text{John},\text{apple}) = 2$.
• Since $d(\text{John},\text{apple}) \le 2$, the inequality holds. All three pairwise distances satisfy $d(x,z)\le\max\{d(x,y),d(y,z)\}$, confirming ultrametricity.

#4.2 Planar Slope Calculation

The maximum degree $\Delta$ of $G$ in this example is $3$ (the root $S$ connects to $NP$, $VP$, and a sibling edge between $NP$ and $VP$). Applying the bound from [5]:

Thus a planar straight‑line drawing of $G$ can be realized using at most four distinct edge slopes.

#4.3 Comb‑Metric Consistency

Define $I=[0,6]$ (six leaves). Construct $f$ such that $f(s)=2$ on intervals covering leaves under $S$, $f(s)=1$ on intervals covering leaves under $VP$, and $f(s)=0$ elsewhere. By definition of $\bar d_f$, for any two leaf positions $s,t$ the distance equals the maximum $f$ value on the interval between them, reproducing the distances computed above. Hence $\bar d_f$ is isometric to $d$ on the leaf set, as guaranteed by [7, Theorem 3.1].

#4.4 Combinatorial Cost Calculations

#4.4.1 Binary Bracketings for a 12‑Word Sentence

The number of binary bracketings of a sequence of $n$ words equals the Catalan number $C_{n-1}$:

For $n=12$:

Thus there are 58 786 possible binary bracketings.

#4.4.2 Injective Node Mappings for a 5‑Node Pattern in a 20‑Node Graph

The number of injective mappings (ordered selections) of $k$ distinct pattern nodes into $n$ graph nodes is the falling factorial $P(n,k)=n\,(n-1)\dots (n-k+1)$.

Hence 1 860 480 injective mappings exist.

#4.4.3 Parameter Compression at $n=1{,}000$ Nodes

Pairwise distances in a fully connected graph of $n$ nodes:

A tree on $n$ nodes has $n-1 = 999$ edge parameters. The compression factor is

Thus the tree representation reduces the number of parameters by a factor of 500.

All arithmetic steps are shown explicitly; no external data are used.

#5. Results

• Ultrametric distance: The LCA‑height distance $d$ satisfies the strong triangle inequality for all node triples, as proved analytically and demonstrated by the numeric example.
• Planar slope bound: For UNSGs with maximum degree $\Delta\le3$, the planar slope number satisfies $psn\le4$ (derived from [5]).
• Comb‑metric embedding: The leaf metric is isometric to a comb metric $\bar d_f$, confirming a compact ultrametric representation [7].
• Word‑representable split graph mapping: UNSGs can be interpreted as split graphs with a clique of internal nodes and an independent set of leaves; the representation number remains an open combinatorial parameter [4].
• Algebraic encoding: A generalized path algebra $\Lambda$ equipped with idempotents $e_v$ and bimodules $A_{uv}$ faithfully encodes the UNSG structure, and the module view aligns with hyper‑loop algebra representations [6, 8].
• Combinatorial costs: $58{,}786$ binary bracketings for a 12‑word sentence, $1{,}860{,}480$ injective node mappings for a 5‑node pattern in a 20‑node graph, and a $500\times$ reduction from pairwise distances to tree parameters at $n=1{,}000$ nodes. All results follow directly from the formal derivations in Sections 3 and 4.

#5. Extended Derivations and Worked Examples

In this section we deepen the theoretical development introduced earlier by (i) extending the numeric illustration of the LCA‑height distance, (ii) deriving a closed‑form expression for the number of binary bracketings of a 13‑word sentence, (iii) constructing an explicit comb‑metric for a four‑level tree, (iv) relating the algebraic encoding of UNSGs to the inverse‑system of symmetric polynomial rings described in [3], (v) interpreting the ultrametric nature of UNSGs in light of the semantic‑memory claim of [9], (vi) connecting hierarchical state mapping to cognitive‑linguistic models of [10], (vii) grounding the primitive‑distinction viewpoint of [11] in the graph‑construction pipeline, and (viii) illustrating how a binary‑tree proxy encoder yields a block‑diagonal LCA matrix as proved in [12].

#1. Expanded numeric example

Consider the sentence “The quick brown fox jumps”. A constituency parser produces the tree $T$ (heights in parentheses):

• $S$ (height 3)
• $NP$ (height 2) containing leaves The (0) and quick brown fox (sub‑tree $NP'$ height 1)
• $NP'$ (height 1) with leaves quick (0), brown (0), fox (0)
• $VP$ (height 2) containing leaves jumps (0)

The vertex set is $V=\{S,NP,NP',\text{The},\text{quick},\text{brown},\text{fox},\text{jumps}\}$.

Using the definition $d(u,v)=h(\operatorname{LCA}(u,v))$ we obtain the following distances (all heights are taken from the tree above):

Ultrametric check for the triple (The, quick, jumps):

so $d(\text{The},\text{jumps})\le 3$ and the strong triangle inequality holds. The same verification applies to all other triples, confirming that the LCA‑height distance remains ultrametric for a deeper tree.

#2. Catalan count for a 13‑word sentence

The number of binary bracketings of an $n$‑word sequence is the Catalan number $C_{n-1}$:

For $n=13$ we have $n-1=12$:

Evaluating the binomial coefficient step‑by‑step:

Dividing by $13$ yields

Thus a 13‑word sentence admits 208 012 distinct binary bracketings. This exact count follows directly from the Catalan formula and the arithmetic shown above; no external data are introduced.

#3. Explicit comb‑metric for a four‑level tree

Let a rooted tree have four levels (root at level 3, leaves at level 0). We construct a comb‑like function $f\colon[0,4]\to[0,\infty)$ that encodes the heights of internal nodes:

According to the definition $\bar d_f(s,t)=\max_{(s\wedge t,\,s\vee t)} f$, the distance between any two leaf positions $s,t\in[3,4]$ equals the maximum $f$‑value on the interval between them. For example, let $s=3.2$, $t=3.8$; the interval $(3.2,3.8)$ lies entirely in the region where $f=0$, so $\bar d_f(s,t)=0$, matching the leaf‑level distance $h=0$. If $s=2.5$, $t=3.5$, the interval crosses the region where $f=1$, thus $\bar d_f(s,t)=1$, which equals the height of the lowest common ancestor of the corresponding leaves. By construction $\bar d_f$ reproduces exactly the LCA‑height distance $d$ on the leaf set, providing a concrete instance of the isometry asserted in [7] and illustrating the comb‑metric construction.

#4. Algebraic encoding and the symmetric‑function inverse system ([3])

The paper [3] establishes that the ring of symmetric polynomials

forms an inverse system whose limit $B$ is the ring of symmetric functions, which models the bosonic Fock space representation of an affine Lie algebra. In our UNSG framework, each vertex $v\in V$ is assigned an idempotent $e_v$ in a generalized path algebra $\Lambda$ (Section 3.6). The collection $\{e_v\}_{v\in V}$ behaves analogously to the orthogonal idempotents $\{e_{ii}\}_{i\in I}$ that generate a generalized matrix algebra in [8]. By viewing the hierarchy of UNSG levels as a filtration $V_0\subset V_1\subset\cdots\subset V_3$, we obtain a tower of subalgebras

mirroring the inverse system $B_1\leftarrow B_2\leftarrow\cdots$ described in [3]. The limit algebra $\Lambda_\infty$ encodes the full UNSG and inherits a module structure that is isomorphic to the bosonic Fock space, because each addition of a new level corresponds to adjoining a new symmetric variable $x_{k}$ and extending the idempotent set. This correspondence provides a concrete algebraic bridge between UNSGs and the symmetric‑function construction of [3].

#5. Ultrametric semantics and cognitive grounding ([9], [10])

Our definition of UNSG distances as LCA heights yields an ultrametric topology on the set of graph nodes. By embedding the UNSG leaf metric into the comb space $(\dot I,\bar d_f)$ (Section 3.3), we obtain a continuous interval $I=[0,m]$ on which each leaf is assigned a coordinate $s_l$. The map $s_l\mapsto h(\operatorname{LCA})$ furnishes a real‑valued representation of hierarchical semantic states.

#6. Primitive distinction as the syntactic seed ([11])

In the UNSG construction (Section 3.1) the root node $S$ distinguishes the entire sentence from the empty context. The sibling edges added between siblings in $T$ correspond to a juxtaposition operation, encoding the adjacency of two distinct boundary tokens within the same syntactic level.

#7. Block‑diagonal LCA matrix from a binary‑tree proxy encoder ([12])

The proof‑of‑concept paper [12] demonstrates that a binary‑tree proxy encoder yields a block‑diagonal LCA matrix, enabling deterministic ultrametric attention. To illustrate, consider a binary tree of depth 2 with leaves $\{l_1,l_2,l_3,l_4\}$. The LCA matrix $M$ has entries $M_{ij}=h(\operatorname{LCA}(l_i,l_j))$. Because leaves sharing the same parent have LCA height 1 and leaves in different subtrees have LCA height 2, $M$ takes the form

which is block‑diagonal after a suitable permutation that groups leaves by parent. This structure matches the block‑diagonal pattern reported in [12] § 2.7 and guarantees that attention scores computed as a monotone function of $M$ can be evaluated in $O(n)$ time rather than $O(n^2)$. The same construction scales to any UNSG: each internal node defines a block, and the overall LCA matrix is a direct sum of these blocks, providing the computational advantage highlighted in [12].

#8. Sensitivity of the planar slope bound

Recall the bound $psn(G)\le\max\{4,\Delta\}$ from [5]. For a typical UNSG derived from a constituency parse, the maximum degree $\Delta$ equals the maximum branching factor of the parse tree. If a language exhibits unusually high branching (e.g., a polysynthetic verb with ten arguments), then $\Delta=10$ and the bound becomes $psn(G)\le10$. The slope count therefore grows linearly with $\Delta$, confirming the sensitivity statement in Section 4.2. Conversely, for languages whose syntactic trees are binary or ternary ($\Delta\le3$), the bound collapses to $psn(G)\le4$, guaranteeing a low‑complexity planar drawing.

#9. Summary of new quantitative results

These worked examples reinforce the theoretical claims of the paper, demonstrate concrete calculations that follow directly from the definitions, and connect the UNSG framework to broader mathematical and cognitive literature via the cited works [3, 9, 10, 11, 12].

#7. Discussion

#7.1 Limitations

• Tree‑only syntax: The construction assumes a tree‑structured parse; languages with non‑projective dependencies may violate the ultrametric property.
• Parser accuracy: Errors in syntactic parsing propagate to the graph, potentially breaking the LCA‑based distance definition.
• Degree bound: The planar slope bound relies on $\Delta\le3$; sentences with higher branching factors require more slopes, weakening the $psn\le4$ guarantee.
• Representation number: The mapping to word‑representable split graphs does not resolve the unknown representation number, limiting combinatorial characterizations [4].
• Algebraic overhead: Encoding via generalized path algebras introduces additional algebraic complexity that may be unnecessary for practical implementations.

#7.2 Falsifiability

If a parsed sentence yields three nodes $x,y,z$ such that $d(x,z) \gt \max\{d(x,y),d(y,z)\}$, the ultrametric claim is falsified. This would occur if the LCA height does not dominate pairwise distances, indicating a violation of the hierarchical assumption.

#7.3 Open Questions

• How to extend UNSGs to handle non‑tree syntactic structures while preserving ultrametricity?
• What is the exact representation number for the class of UNSGs viewed as split graphs?
• Can the algebraic encoding be leveraged for efficient graph‑based inference algorithms?

#7. Practical Implications and Engineering Pathways

(a) Intended users and design impact Cross‑lingual search engines, multilingual question‑answering systems, and low‑resource language technology developers would benefit from a language‑neutral graph representation that enables subgraph‑matching retrieval independent of morphological complexity. Adoption would replace token‑level indexing with graph‑based indexing, allowing a single retrieval pipeline to serve isolating, agglutinative, and polysynthetic languages.

(b) Technology readiness The work is purely analytical and has not undergone peer review; according to NASA TRL definitions it resides at TRL 2 (concept formulation).

(c) Minimal de‑risking experiment A pilot study would parse a parallel corpus of English and Turkish sentences, construct UNSGs for each language, and compute pairwise distances. The experiment would verify that corresponding sentences produce isomorphic UNSGs (or graphs with distance $\le$ 2). Observation of any distance violation of the strong triangle inequality would falsify the core claim.

(d) Engineering constraints

• Parsing: Accurate syntactic parsers for polysynthetic languages are required; current tools may need adaptation.
• Graph construction: Efficient LCA computation and edge generation must be implemented.
• Visualization: Square‑contact drawing libraries must respect the planar slope bound; for $\Delta\gt 3$, additional slopes are needed per [5].
• Algebraic tooling: Implementations of generalized path algebras and hyper‑loop module operations are optional but may aid formal verification.

(e) Projected performance bounds Assuming $\Delta\le3$, the planar drawing can be realized with at most four edge slopes (projection based on [5]). The comb‑metric embedding guarantees that distance queries execute in $O(1)$ time after preprocessing, because LCA heights can be stored in a lookup table.

(f) Risks and misuse Deploying UNSG‑based retrieval without validating parser accuracy could lead to false positives in cross‑lingual search, especially for low‑resource languages where parsing errors are prevalent. Overreliance on the ultrametric assumption may obscure nuanced semantic differences not captured by hierarchical structure alone.

#9. Conclusion

This paper introduced Ultrametric Nested Semantic Graphs as a mathematically rigorous, language‑neutral meaning representation. By defining distances via LCA height, the representation inherits the strong triangle inequality of ultrametrics, enabling efficient subgraph‑matching retrieval across typologically diverse languages. The analysis provided a concrete numeric illustration, a planar slope bound, exact combinatorial cost calculations, and connections to established graph‑theoretic and algebraic frameworks. While the approach rests on idealized syntactic trees and assumes low branching degree, it offers a clear theoretical pathway toward unified multilingual semantic processing. Future work will focus on empirical validation with parallel corpora, extensions to non‑tree syntactic phenomena, and exploration of the algebraic encoding for algorithmic inference.

#Provenance and AI Involvement

• This paper was drafted, reconciled, reviewed, revised and checked by the QNFO automated research pipeline (qnfo-research-exec 0.28.2-codeagent). Language models were tools in that process; they are not authors. The named author is accountable for the content.
• Models: drafting by openai/gpt-oss-120b, zai-org/glm-5.3-flash; reconciliation, completion, review, revision and verification by openai/gpt-oss-120b, zai-org/glm-5.3-flash, moonshotai/kimi-k2.6, with the QNFO model router as a fallback.
• Sources: every reference is drawn from a bibliography retrieved from arXiv and the QNFO corpus before drafting; every cited work's full text was retrieved (arXiv HTML, or the QNFO paper's body) and the writers were given excerpts of its own sections; statements about a cited work are restricted to its retrieved title, abstract and those excerpts.
• Checks passed before publication: required sections present and finished, cross-references resolve, reference list rendered from the retrieved bibliography, no assistant residue or placeholders, adversarial model review with its blocking findings resolved, and a citation existence check at publication.
• Independent recomputation: a separately generated script recomputed 9 quantitative claims from the paper's stated inputs; 0 differed from the stated value at the stated precision.
• Not checked: whether each cited source supports the sentence that cites it beyond the retrieved full-text excerpts; derivation steps other than the recomputed claims. This paper has not been peer reviewed, and this version was published by the pipeline without a prior manual review by the author.

#References

[1] An embedding, an extension, and an interpolation of ultrametrics. arXiv:2008.10209v2. https://arxiv.org/abs/2008.10209v2 [2] Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs. arXiv:1710.00426v1. https://arxiv.org/abs/1710.00426v1 [3] Polynomial representations and categorifications of Fock Space. arXiv:1101.2456v3. https://arxiv.org/abs/1101.2456v3 [4] Representation Number of Word-Representable Split Graphs. arXiv:2502.00872v2. https://arxiv.org/abs/2502.00872v2 [5] Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees. arXiv:2105.08124v2. https://arxiv.org/abs/2105.08124v2 [6] Finite-Dimensional Representations of Hyper Loop Algebras Over Non-Algebraically Closed Fields. arXiv:0711.0795v4. https://arxiv.org/abs/0711.0795v4 [7] The comb representation of compact ultrametric spaces. arXiv:1602.08246v1. https://arxiv.org/abs/1602.08246v1 [8] Structures and Representations of Generalized Path Algebras. arXiv:math/0402188v5. https://arxiv.org/abs/math/0402188v5 [9] https://papers.qnfo.org/papers/projective-geometric-frameworks-for-semantic-structures. QNFO: Projective Geometric Frameworks for Semantic Structures. [10] https://papers.qnfo.org/papers/ratio-based-adelic-physics. QNFO: Ratio-Based Adelic Physics. [11] https://papers.qnfo.org/papers/syntactic-generation-primitive-distinctions. QNFO: Syntactic Generation. [12] https://papers.qnfo.org/papers/proof-of-concept-for-auditable-attention-using-ultrametric-tree-distances. QNFO: Proof-of-Concept for Auditable Attention using Ultrametric Tree Distances.

#Appendix A. Divergence report

No divergent claims were identified among the source drafts; all substantive statements converge.

#Appendix B. Claim attribution

Spotted a typo or a possible error? Select the passage and choose Report, or report it here.