Autoregressive Synthesis of Sparse and Semi-Structured Mixed-Type Data

The paper introduces Origami, an autoregressive transformer-based architecture that natively generates high-fidelity, privacy-preserving synthetic data from sparse, semi-structured mixed-type formats like JSON without requiring flattening or imputation, outperforming existing methods designed for dense tabular data.

The Gist

Imagine you are a librarian trying to recreate a massive, chaotic library for a new building.

The Problem: The "Flattening" Disaster
Most modern libraries (databases) don't store books in neat, uniform rows like a spreadsheet. Instead, they store them like JSON files: a messy, nested pile of folders, sub-folders, and lists.

• One book might have a "Author" folder, inside which is an "Address" folder, inside which is a "Street" and "City."
• Another book might have a "Reviews" list with 50 items, while a third has none.
• Some books have a "Price" tag, others don't.

Existing AI tools for making fake data (synthetic data) were built for flat spreadsheets. To use them on this messy library, you have to force everything into a giant, flat table.

• The Analogy: Imagine trying to fit a 3D tree into a 2D piece of paper. You have to stretch every branch out.
• The Result: You end up with a table that has thousands of columns (one for every possible sub-folder). Most of these columns are empty (sparse) because not every book has every sub-folder. It's like trying to fill a stadium with seats, but 90% of the seats are empty. The AI gets confused, the computer runs out of memory, and the fake data looks nothing like the real thing.

The Solution: Origami
The authors built a new AI called Origami. Instead of forcing the messy data into a flat sheet, Origami learns to fold it like paper. It treats the data exactly as it is: a hierarchy of keys, values, and structures.

Here is how Origami works, using simple metaphors:

1. The Tokenizer: Turning Data into Lego Bricks

Instead of reading the whole book at once, Origami breaks every record down into tiny, specific Lego bricks called tokens.

• It sees a "Key" (like "Author").
• It sees a "Value" (like "Jane Doe").
• It sees "Structural Bricks" (like "Start of a Folder," "End of a List").
• Why it matters: It doesn't care if the list is long or short. It just builds the structure brick by brick.

2. The Map: KVPE (The GPS for Data)

Standard AI models usually count steps: "This is the 1st word, this is the 2nd word." But in a JSON file, the order of keys doesn't matter. "Author" then "Title" is the same as "Title" then "Author."

• The Analogy: If you tell a robot to walk "10 steps forward," it might walk into a wall if the room is different.
• Origami's Trick: It uses Key-Value Position Encoding (KVPE). Instead of counting steps, it gives every brick a GPS coordinate based on its location in the folder tree. It knows exactly where a piece belongs, regardless of the order. This prevents the AI from memorizing a specific order and forces it to learn the actual relationships between the data.

3. The Shuffling: The "Randomized Puzzle"

To make sure the AI doesn't just memorize the data (cheating), the authors do something clever: they shuffle the order of the keys every time they show the AI a record.

• The Analogy: Imagine teaching someone to bake a cake by showing them the ingredients in a different order every time (Eggs, Flour, Sugar... then Sugar, Flour, Eggs...).
• The Result: The student can't just memorize the sequence; they have to understand the logic of baking. This makes the AI much smarter and less likely to copy-paste real data (which is a privacy risk).

4. The Dual-Head Chef: Handling Numbers and Words

Real data has both words (categorical) and numbers (continuous).

• The Problem: Standard AI often tries to turn numbers into words (discretizing them), which loses precision. Or it tries to turn words into numbers, which gets messy.
• Origami's Chef: It has two heads working together.
  • Head 1 (The Word Chef): Predicts keys, categories, and structure (like "Action Movie" or "Start of Array").
  • Head 2 (The Math Chef): Predicts numbers using a special "Mixture of Gaussians" (a fancy way of saying it understands that numbers can be clustered in different ways, like a bell curve).
• The Result: It handles both types perfectly without forcing them into the wrong shape.

5. The Grammar Police: Pushdown Automaton

When Origami generates new data, it needs to make sure it doesn't create nonsense (like a list that never ends or a folder that opens but never closes).

• The Analogy: Imagine a strict editor who checks every sentence you write to ensure you have a matching closing parenthesis.
• The Result: Every piece of fake data Origami creates is perfectly valid JSON. It never breaks the rules.

The Big Win

The paper tested Origami against the best existing tools (like GANs, Diffusion models, and other Transformers) on datasets ranging from simple tables to massive, messy medical records with over a million entries.

• On simple data: Origami was just as good as the best tools.
• On messy, sparse data: The other tools crashed, ran out of memory, or produced garbage. Origami thrived. It created data that was so realistic, even a super-smart computer couldn't tell the difference between the real and fake data.

In Summary:
If existing data tools are like a flat iron trying to press a crumpled, 3D origami bird into a flat sheet (ruining it), Origami is a new tool that understands how to fold the paper in 3D, preserving the bird's shape, wings, and tail perfectly, even if the bird is huge and complex.

Technical Summary

1. Problem Statement

Synthetic data generation is critical for privacy, testing, and benchmarking. However, existing methods (GANs, VAEs, Diffusion models, and standard Autoregressive models) are designed for dense, fixed-schema tabular data. They fail to handle modern data systems (document databases, REST APIs, data lakes) which store data in sparse, semi-structured formats (e.g., JSON).

Applying current methods to semi-structured data requires a "flatten-and-impute" pipeline:

1. Flattening: Nested objects and variable-length arrays are expanded into wide tables with hundreds of columns.
2. Imputation: Missing values (structural sparsity) are filled with mean values or sentinel markers.
3. Consequences: This process destroys hierarchical structure, introduces massive sparsity (up to 38% in real-world datasets), inflates categorical cardinality (via one-hot encoding), and leads to poor scalability, memory exhaustion, and low-fidelity synthetic data that is easily distinguishable from real data.

2. Methodology: Origami

The authors propose origami (Object Representa-tIon via Generative Autoregressive ModelIng), an autoregressive transformer architecture designed to synthesize semi-structured data end-to-end without flattening or imputation.

A. Tokenization & Representation

Instead of treating data as a flat table, origami tokenizes JSON records directly:

• Structure: It serializes records via depth-first traversal into sequences of Key, Value, and Structural Tokens (e.g., obj_start, arr_end).
• Hierarchy: Nested objects and variable-length arrays are preserved as part of the token sequence.
• Mixed Types: Handles type polymorphism (where a key holds different types in different records) natively.
• Numeric Handling: High-cardinality numeric values are standardized and passed through a parallel continuous channel, while low-cardinality values are treated as categorical tokens.

B. Key-Value Position Encoding (KVPE)

Standard transformers use sequential position indices, which impose an artificial order on JSON keys (which are inherently unordered).

• KVPE: Replaces sequential indices with structural path encodings. Each token's position is encoded based on its path through the JSON tree (e.g., user.address.city).
• Benefit: This makes the model invariant to the order of sibling keys, allowing the model to learn semantic relationships rather than memorizing key ordering.

C. Key-Order Shuffling

To prevent the model from memorizing specific key orders (a form of overfitting), the training data undergoes random key-order shuffling at every nesting level for every epoch. Combined with KVPE, this acts as a powerful regularizer, forcing the model to learn robust causal dependencies rather than spurious correlations.

D. Dual-Head Architecture

The model employs a hybrid output head to handle mixed data types:

1. Discrete Head: Predicts structural tokens, keys, and categorical values using standard next-token prediction (Cross-Entropy loss).
2. Continuous Head: Predicts high-cardinality numeric values using a Mixture of Gaussians (MoG). This models the probability distribution of continuous values without discretization or binning, preserving precision and ordinal structure.

E. Constraints (Grammar & Schema)

To ensure syntactic validity and semantic correctness:

• Grammar Constraints: A Pushdown Automaton (PDA) tracks the nesting context (objects vs. arrays) during generation, masking invalid tokens (e.g., preventing a value before a key).
• Schema Constraints: A compiled mask derived from the training data enforces type restrictions, allowed keys, and array bounds.
• Post-Processing: A deterministic pass clips values to observed bounds, snaps to enums, and rounds integers to ensure generated data adheres to the original domain constraints.

3. Key Contributions

1. First End-to-End Semi-Structured Synthesizer: Origami is the first architecture capable of modeling and generating semi-structured data natively, handling hierarchy, sparsity, and type polymorphism without flattening.
2. KVPE Mechanism: Introduces a principled, order-invariant position encoding specifically for key-value data, demonstrated to be superior to sequential encoding for nested structures.
3. Evaluation Framework: Proposes a flattening methodology and enhanced metrics that account for structural missingness and type fidelity, enabling fair comparison between native semi-structured generators and flattened baselines.
4. Comprehensive Benchmarking: Evaluates on datasets ranging from standard tabular benchmarks to large-scale semi-structured collections (up to 1M+ records).

4. Experimental Results

The authors evaluated origami against six baselines (CTGAN, TVAE, TabDiff, REaLTabFormer, Tabby, TabularARGN) across five datasets (Adult, Diabetes, Electric Vehicles, Yelp, DDXPlus).

• Fidelity & Detection: Origami achieved the highest fidelity scores across all datasets. On sparse datasets (Yelp: 38% sparsity, DDXPlus: 35% sparsity), baselines either failed to train (OOM) or produced data easily distinguished from real data (Detection ROC AUC > 0.99). Origami maintained high fidelity (0.96–0.99) and was the hardest to detect (Detection scores ~0.96–1.0).
• Utility: Origami achieved state-of-the-art utility scores (Train-Synthetic-Test-Real) on 4/5 datasets, preserving predictive power for downstream ML tasks.
• Privacy: Origami maintained high privacy scores (>0.97) with low memorization (Distance to Closest Record near 50%).
• Scalability & Efficiency:
  • Memory: Baselines like CTGAN and TVAE failed on sparse datasets due to one-hot encoding explosion. Origami scaled efficiently.
  • Model Size: Origami is significantly smaller (1.7M parameters) than REaLTabFormer (59.4M) and TabDiff (25.8M), yet trains faster and achieves better results.
• Ablation Studies:
  • KVPE vs. Sequential PE: Sequential PE failed to distinguish identical keys at different paths, collapsing to uniform distributions. KVPE accurately recovered path-specific marginals.
  • Key Shuffling: Enabled better utility and privacy by preventing memorization, with only a marginal trade-off in raw fidelity.

5. Significance

This work bridges the gap between modern data engineering (JSON/NoSQL) and synthetic data generation. By moving away from the "flatten-then-synthesize" paradigm, origami:

• Preserves Structural Integrity: It respects the hierarchical and sparse nature of real-world data, avoiding the artifacts introduced by imputation.
• Enables New Applications: As a tractable density estimator, it opens doors for conditional sampling, data imputation, cardinality estimation, and outlier detection on semi-structured data.
• Sets a New Standard: It demonstrates that autoregressive transformers, when combined with structural awareness (KVPE) and constraint enforcement, outperform diffusion and GAN-based approaches for complex, sparse data distributions.

The code and artifacts are publicly available, and the model is released as a standalone Python package (origami-ml).