NecroMOnk/bfs-optimal-symbolic-algebra-simplification-trajectories

ISRE v7 BFS Trajectories

This dataset contains BFS-optimal symbolic algebra simplification trajectories for the ISRE research project.

Each row is one trajectory. Nested fields are stored as JSON strings to preserve the original AST and step structure without lossy flattening.

What This Dataset Is

This is not a natural-language instruction dataset. It is a symbolic algebra policy-learning dataset.

Each trajectory starts from a deliberately scrambled algebraic expression and ends at a canonical simplified expression. At each intermediate state, the dataset records:

• —the current expression,
• —all valid candidate rewrite actions,
• —the BFS-optimal gold action,
• —the AST node where that action should be applied.

The intended learning problem is:

Given an algebraic expression state and a set of valid candidate rewrites, choose the next rewrite that stays on a shortest path to the canonical form.

What the Algebra Actions Mean

The action names are symbolic rewrite rules. They are not labels like sentiment classes; they are concrete algebra transformations.

SORT_COMMUTATIVE is a real trajectory action in this benchmark. It is not just pretty-printing: the policy must sometimes choose it to reach the canonical state.

Example Trajectory

One row can contain a multi-step optimal simplification path. Example:

trajectory_id: traj_0000002
original:      (4 + ((3 + 5) * (1 * (x + 0))))
canonical:     ((8 * x) + 4)

BFS-optimal forward steps:

The final expression is ((8 * x) + 4).

In steps_json, each step stores the full AST state plus fields such as:

{
  "state_expr": "((8 * (1 * (x + 0))) + 4)",
  "candidate_actions": [[1, "FLATTEN_MUL"], [3, "EXPAND"], [3, "REMOVE_ONE"], [5, "REMOVE_ZERO"]],
  "gold_action": "REMOVE_ONE",
  "gold_node_id": 3,
  "complexity": 11
}

Generation

• —Source project: ISRE (Interpretable Symbolic Reasoning Engine)
• —Generator: scripts/regen_parallel.py
• —Output mode: BFS-optimal gold trajectories
• —Seed: 43
• —Requested trajectories: 100000
• —Generated trajectories: 98472
• —Drop rate: 1.53%
• —Max degree: 5
• —Max AST depth: 7
• —Max backward trajectory length: 6
• —BFS budget: 50000

Command:

python scripts/regen_parallel.py \
  --out isre/trajectories_v7_bfs \
  --n 100000 \
  --workers 8 \
  --seed 43 \
  --gold-mode bfs \
  --max-degree 5 \
  --max-depth 7 \
  --max-traj 6 \
  --bfs-budget 50000

Summary

• —Trajectories: 98472
• —Training pairs: 293631
• —State cycles: 0

Gold action distribution:

Columns

• —trajectory_id: Stable trajectory id.
• —canonical_expr: Canonical target expression.
• —canonical_ast_json: Canonical AST as JSON string.
• —original_expr: Scrambled starting expression.
• —original_ast_json: Scrambled starting AST as JSON string.
• —steps_json: Forward simplification steps as JSON string.
• —difficulty: Number of BFS-optimal forward steps.
• —inverse_sequence_json: Backward scramble operations as JSON string.
• —n_steps: Number of forward steps.

Loading

from datasets import load_dataset
import json

ds = load_dataset("NecroMOnk/bfs-optimal-symbolic-algebra-simplification-trajectories")
row = ds["train"][0]
steps = json.loads(row["steps_json"])

print(row["original_expr"], "=>", row["canonical_expr"])
for step in steps:
    print(step["state_expr"], "=>", step["gold_action"], "at node", step["gold_node_id"])

Notes

This is a research artifact for studying compact neural policies over symbolic AST transformations. It should be treated as an experimental benchmark, not a general-purpose algebra dataset.