# Tagma Structural Indexing

Multi-axis coordinate index for the FIH storage engine

Author

Affiliation

SSCCS Foundation [](mailto:contact@ssccs.org)

[SSCCS Foundation](https://ssccs.org)

Published

August 3, 2026

Abstract

The Tagma coordinate space replaces the multi-HashMap index layer (FihCoord) with a direct-address N-tuple identity, eliminating join explosion on multi-axis queries. The storage IO layer, record format, and external FihHash interface remain unchanged. The integration is a targeted 30-line addition to the index layer with zero changes to the surrounding architecture.

Other Formats

[LLMs](https://docs.ssccs.org/projects/nexus/notes/tagma_integration.llms.md)

## Motivation

The FIH storage engine’s index layer (`FihCoord`) stores six independent axis indexes as individual HashMaps:

- `by_origin`, `by_creator`, `by_status`, `by_semantic`, `by_time`, `by_fact`

Each axis is queryable independently, but multi-axis queries (e.g., “all facts by creator X in time range Y with origin Z”) require manual Vec intersection at the call site:

``` rust
let by_origin = coord.by_origin("document:nexus");
let by_creator = coord.by_creator("ingestion-agent");
let by_time = coord.by_time(t0..t1);
let result: Vec = by_origin.iter()
    .filter(|id| by_creator.contains(id))
    .filter(|id| by_time.contains(id))
    .collect();
```

As the number of axes grows, intersection cost explodes. RoaringBitmap, QueryPlanner, and selectivity-based ordering are mitigations for a fundamental problem: identity and index are separate data structures.

Tagma solves this by making the identity itself a coordinate in N-dimensional space. A multi-axis query becomes a single CoordPath construction followed by an O(N) array traversal (where N is path depth, unrelated to dataset size).

## Design Principle

The integration follows a strict principle: **external interfaces remain unchanged**. The storage IO layer, record types, serialization format, and FihHash identity type are never modified. Tagma is introduced as a drop-in replacement for the multi-axis index only.

| Layer | Changed | Rationale |
|----|----|----|
| Storage IO | No | IO is the architectural boundary; untouched |
| Record types (Fact, Intent, Hint) | No | Same fields, same serialization |
| FihHash (\[u8; 32\]) | No | External identity contract preserved |
| FihCoord multi-axis HashMap | **Yes** | Replaced with CoordSpaceN index |
| by_fact reverse index | No | Tagma cannot express reference graphs |
| Time index (BTreeMap) | No | Continuous time vs discrete coordinates |

## Architecture

``` text
BoardState (unchanged)
  │
  ├── Record Layer (unchanged)
  │   ├── facts:  Vec<Fact>
  │   ├── intents: Vec<Intent>
  │   └── hints:  Vec<Hint>
  │
  ├── Index Layer (Tagma replaces FihCoord)
  │   ├── axis_index: CoordSpaceN<3, FihHash>
  │   │     origin × creator × type → FihHash (single CoordPath lookup)
  │   ├── by_fact: HashMap<FihHash, Vec<FihHash>> (unchanged)
  │   └── time_index: BTreeMap<u64, FihHash> (unchanged)
  │
  └── FihCoord (deprecated, legacy compat shim)
```

The `CoordSpaceN<3, FihHash>` maps a 3-axis coordinate (origin, creator, type) directly to a FihHash. No HashMap lookup, no intersection, no allocation.

## Recursive Coordinate Composition

A Tagma `Coord` is a 16-bit value defined by a 3-axis composition formula with ranges Axis 0 (19), Axis 1 (21), and Axis 2 (28), yielding 11,172 valid combinations total.[^1] Multiple `Coord` values compose into a `CoordPath` of arbitrary length for N-dimensional addressing.

The critical design property is that each dimension (origin, creator, type) occupies one Coord position in the path, NOT one axis within a Coord:

``` text
FIH identity = CoordPath (variable length)

Example 3D (origin × creator × type):
  CoordPath<3> = [origin_coord, creator_coord, type_coord]

Each coord.index() = 0..11172 (NOT 0..18)
Each dimension = 11,172 values, NOT 19
```

This avoids the flat mapping fallacy of assigning `initial=origin(19)`, `medial=creator(21)`, `final=type(28)`. The 3-axis decomposition of an individual Coord is an internal encoding detail used only for Hamming distance and human readability. The storage and query hot path uses only `coord.index()` which is a flat 0..11172 value.

For tens of millions of entries, a 2-Coord `CoordSpaceN<2, FihHash>` with batch allocation (first coord = allocation batch, second coord = slot within batch) provides 124,813,584 addressable slots while keeping memory under control:

| Entries    | Batches | Leaf arrays | Index memory |
|------------|---------|-------------|--------------|
| 100,000    | 9       | 9           | ~3.2 MB      |
| 1,000,000  | 90      | 90          | ~32 MB       |
| 10,000,000 | 895     | 895         | ~320 MB      |

The leaf array allocation is the dominant cost: each populated batch allocates a fixed 11,172-slot `[Option<FihHash>; 11172]` array (approximately 357 KB). For practical FIH workloads with 1-10 million entries, this is acceptable.

## Performance

### Index-level comparison

The following table compares the current FihCoord (multi-HashMap) approach against Tagma CoordSpaceN for the same query patterns. Results are from the syntagma Criterion benchmark suite on ARMv8.4-A Firestorm.

| Query pattern | Example | Current (FihCoord) | Tagma (CoordSpaceN) | Ratio |
|----|----|----|----|----|
| Single-axis | “creator=Y” | O(1) HashMap lookup | O(domain) 11K scan | HashMap faster, kept |
| 2-axis selective | “origin=X & creator=Y” | Vec intersection O(KxN) | O(2) path lookup | ~1000x |
| 3-axis selective | “origin=X & creator=Y & type=Z” | 3 Vec ops + 2 intersections | O(3) path lookup | ~1000-3000x |
| Existence check | “does this 3-axis point exist?” | HashMap + Vec fetch | O(3) path lookup, None possible | ~1Mx (nonexist) |
| Nonexistent check | “does NOT exist” | Vec scan until found | O(3) None return | **14.0Mx** |
| Single CoordSpace get | baseline | N/A | 0.82 ns | baseline |
| CoordSpaceN\<2\> get | 2-Coord | N/A | ~1.5 ns (est) | baseline |

The nonexist column requires explanation and is detailed below.

### Identity generation

Tagma CoordPath generation replaces SHA256-based FihHash creation in new code paths. The identity size matches the address space requirements rather than being fixed at 32 bytes.

| Method | N-Coord | Address space | Latency (ns/op) | Size (bytes) | Speedup vs SHA256 |
|----|----|----|----|----|----|
| SHA256 | N/A | 2^256 | 227 | 32 | 1x |
| Tagma 1-Coord | 1 | 1.12e4 | 0.38 | 2 | 597x |
| Tagma 2-Coord | 2 | 1.25e8 | 1.1 | 4 | 206x |
| Tagma 6-Coord | 6 | 1.94e24 | 3.7 | 12 | 61x |
| Tagma 19-Coord | 19 | ~2^256 | 54.9 | 38 | 4.1x |

For FIH identity generation, a 6-Coord Tagma CoordPath (12 bytes, 1.94e24 address space, ~3.7 ns) provides UUID-scale collision-free identity at 61x the speed of SHA256.

### The nonexist asymmetry

The decisive advantage of Tagma indexing is not in existing-entity queries but in nonexistent-entity queries. This is the benchmark result that requires careful explanation because it is counterintuitive.

**Current FihCoord approach:**

A `by_origin.get("X")` returns a HashMap lookup of `Vec<u32>` in O(1). That is fast. But a query of “origin=X AND creator=Y AND type=Z” requires:

``` rust
let by_o = coord.by_origin("X");    // O(1), returns Vec
let by_c = coord.by_creator("Y");   // O(1), returns Vec
let by_t = coord.by_type("Z");      // O(1), returns Vec

// Intersection: at minimum, iterate smallest Vec and check HashSet
let smallest = [&by_o, &by_c, &by_t].iter().min_by_key(|v| v.len());
let others: HashSet<u32> = ...;

let result: Vec = smallest.iter()
    .filter(|id| others.contains(id))
    .collect();                     // O(K) where K = smallest Vec size
```

If the smallest Vec has 1000 elements and the intersection is empty, the query still iterates 1000 elements and performs 1000 HashSet lookups before returning None.

**Tagma CoordSpaceN approach:**

``` rust
let path = CoordPath::new([origin_idx, creator_idx, type_idx]);
let result = axis_index.at_path(&path);  // O(3), returns Option<&FihHash>
```

If the 3-axis point does not exist, the third array access returns None and the query terminates immediately. No Vec iteration, no allocation, no HashSet.

This asymmetry is structural. The HashMap-based index can answer “what exists at this single axis” in O(1), but answering “what exists at this combination of N axes” requires materializing each axis Vec and computing their intersection. The cost grows with axis cardinality and is paid regardless of whether the result is empty.

Tagma’s direct-address structure answers the N-axis question at the same cost as a single-axis question: N array accesses. The result is None at the same cost as Some. This is the source of the 14.0Mx benchmark result for nonexistent prefix queries.

### ev (ExaVerif) synergy

An incidental but structurally significant finding: the ev verification tool already imports `tagma_core::{Coord, CoordPath}` and uses `coords_to_path` to bridge instruction field combinations into Tagma coordinate space. The RISC-V instruction verification state space is structurally identical to the FIH coordinate space. Both are N-dimensional state spaces indexed by coordinate composition, and both benefit from O(1) direct addressing versus enumeration-based approaches.

## Implementation

### Phase 1a: Multi-axis index (30 lines)

Add `CoordSpaceN<3, FihHash>` as a field in `FihCoord`. Route multi-axis queries through the Tagma path. Single-axis queries continue through the existing HashMap indexes for backward compatibility.

``` rust
// In FihCoord:
pub struct FihCoord {
    // Legacy single-axis indexes (kept for backward compat)
    by_origin: HashMap<String, Vec<u32>>,
    by_creator: HashMap<String, Vec<u32>>,
    by_status: HashMap<String, Vec<u32>>,
    by_semantic: BTreeMap<String, Vec<u32>>,

    // Tagma multi-axis index (added)
    axis_index: CoordSpaceN<3, FihHash>,

    // Unchanged
    by_fact: HashMap<u32, Vec<u32>>,
    time_index: BTreeMap<u64, u32>,
    // ...
}
```

### Phase 1b: TagmaId identity (20 lines)

Add an optional `TagmaId` field alongside `FihHash` in new record creation. New scopes can opt into Tagma-based identity without affecting existing scopes.

``` rust
pub struct Fact {
    pub id: FihHash,                    // unchanged, external
    pub tagma_id: Option<CoordPath<6>>, // added, internal
    // ...
}
```

### Phase 2: New scope migration

New nex-tagma scopes use Tagma CoordPath as the primary identity. Existing scopes continue with FihHash. The storage layer is trait-parameterized.

### Phase 3: FihHash deprecation for query-dominated workloads

Scopes with heavy multi-axis queries migrate fully to Tagma-based addressing. FihHash remains for workloads requiring cryptographic preimage resistance.

## Non-goals

- Replacing cryptographic hashing. SHA256 remains for signatures, Merkle proofs, and verifiable provenance chains.
- Removing FihHash entirely. Both identity systems coexist.
- Modifying the storage IO layer. Tagma is an index-only addition.
- Hardware verification of Tagma Coord. Requires a separate silicon track.
- Time index replacement. BTreeMap serves continuous time values well.

## Impact summary

| Metric | Before (FihCoord) | After (Tagma index) | Change |
|----|----|----|----|
| Multi-axis query | Vec intersection O(KxN) | CoordPath O(N) | 1000x+ |
| Nonexist detection | Vec scan until empty | O(N) None return | 14.0Mx |
| Identity generation | SHA256 227 ns | CoordPath ~3.7 ns (6-Coord) | 61x |
| Index memory (10M entries) | ~128 MB (6 HashMap) | ~320 MB (CS3 arrays) | 2.5x more |
| Code change | baseline | +30 lines | negligible |
| Storage IO | baseline | unchanged | 0 |

The memory tradeoff (2.5x more for the index) is acceptable because the index is a fixed overhead per populated batch slot, not per entry. At 10M entries using batch allocation, approximately 895 leaf arrays consume ~320 MB. This is dwarfed by the record storage itself (~1.28 GB for 10M Fact records).

## References

- syntagma (github.com/ssccsorg/syntagma): Core Coord, CoordSpaceN, DynCoordSpace implementation. Criterion benchmark suite (51+ functions, 12 groups). White paper at `tagma/docs/wp.qmd`.
- syntagma PR \#23: CoordMap to CoordSpace rename, merged to main 2026-07-18.
- nexus issue \#151: Structural addressing epic.
- nexus issue \#150: nex-tagma PoC.
- ev (github.com/ssccsorg/ev): ExaVerif verification tool, imports tagma_core for coordinate-based state space.

## Footnotes

[^1]: The ranges 19, 21, and 28 derive from the Unicode block U+AC00–U+D7AF, which encodes the compositional writing system.