Serialization Solutions for Decision Diagrams

[doganulus]

Moving the discussion here, started in #15.

@nhusung wrote:

It would be great to have a “forum” to discuss requirements and further developments of a universally supported decision diagram file format to have interoperability between tools.

@trolando wrote:

I vaguely recall other people also talking of DD file formats. I'm almost thinking is this worthy to do some Dagstuhl workshop on, get some other key players involved, etc.

Or just take some notes from other file formats like HOA for automata, or AIG. Maybe we should talk with Armin about that, whether there's some lessons learned there.

In principle I favor a text format that can be converted to binary, but we would need to maintain a standard for the most common variants. At the very least support for BDD and ZDD, with algebraic/multiterminal extensions. Maybe complement edges but those can be handled on the fly when importing or exporting. Maybe edge values similar to algebraic/multiterminal extensions. Then there are variants like multi valued DDs (having more than 2 children), and there's LDDs which have a bunch of "weird" special internal nodes, that I think we don't really want in a core standard, there are more recent hybrid DDs like TBDDs.

@doganulus wrote:

From my experience with other tooling and data formats, I may say JSON files with a schema for text files and/or Protobuf-like formats should be considered first, rather than custom formats. The important thing is that these formats already have several implementations in many programming languages. Then, the task is reduced to deciding on the application-specific schema. I don't know how complex it could be but for example, I know the OpenStreetMap project switched to Protobuf format to encode and distribute their complex relational graphs.

@ssoelvsten wrote:

We really should move this discussion elsewhere...

Here we go :)

[ssoelvsten]

[doganulus]

The documentation for Protobuf does not mention any Rust support?

They mention here: https://protobuf.dev/reference/rust/

Yet Google is still a C++ shop. Their Rust support or interest is not so extensive, I think. There are independent protobuf implementations on cargo though.

[doganulus]

Probably it is desired to have both backward and forward compatibility regarding these schemas:

• A new tool using a newer schema shall read files written in older schema versions
• A legacy tool using an older schema shall read files written in newer versions of the schema (of course, without knowing new fields added, but it works as it is)

Another useful feature I have seen is to add an extras or vendor field in nodes to encode vendor-specific information without disrupting other vendors. A new student can provide their own extensions without requiring an initial alignment. If they are universally good, this may be promoted to first-class fields in the schema.

With a careful schema evolution, protobuf and a few other similar formats support forward and backward compatibility. Thinking about whether the extras field would disrupt this or not. I think it is fine too.

[trolando]

I recall having conversations at some point about this with Ondrej Lengal (ondrik on GitHub). He might be interested to discuss this.

[doganulus]

Please feel free to invite anyone who might be interested. I'm also happy to invite them to the organization as well.

Welcome, @ondrik and @daemontus!

[daemontus]

Thanks for adding me!

I'll be very happy to support a unified DD serialization format. I recall trying dddmp a long time ago, getting a bunch of segfaults and concluding it's not worth my time reimplementing it in Rust... glad that someone did it in the meantime :D

My 2 cents:

1. Having "extras" / "annotations" / "vendor extensions" part of the schema is very useful, especially if you can put some raw JSON string into it. Then you have your "optimized" protobuf DD schema (that ultimately cannot evolve with as much flexibility as JSON), and a more generic metadata "object" with fewer actual restrictions on its format/contents. In other words, people writing vendor extensions may not always be comfortable/productive using protobuf; it might be simpler to allow them to embed metadata in some more generic format.

2. Regarding ordering of nodes and complement edges (and ultimately a lot of other decisions): I guess there are two ways the format could go. Either the format is super permissive (every type of DD under the sun can be represented in it directly), in which case it might be a real pain to actually import data from it, because people can give you weird diagrams as input and break various invariants of your library unless you explicitly verify them during import (or add conversion/normalization routines). Of course, it's up to the library authors to decide what is "too weird" for their library and reject other input. But that creates a bit of anxiety, because you can't be sure tool X can actually import any diagram Y. The other direction is to make the format super simple such that essentially everyone should be able to import essentially any DD, but then you of course lose the "universality", and more advanced tools still might need to implement various translation layers to accommodate the less flexible format.

   To be honest, I don't really have a solution right now that I feel is obviously good. What might be a good middle ground though: Make the format super flexible, but as part of the project, provide some simple command line utility that can do basic transformations for you (even if they are not super fast/optimal). For example, if the format supports complement edges, the utility should be able to transform them into normal edges in a safe way. Similarly, if the DD is not ordered in a specific way, the utility should be able to reorder the DD nodes. If the diagram is a ZDD, allow changing it to a BDD (accepting the risk that the result might be much bigger), etc. So, in the end, you can transform any DD file into some "lowest common denominator" that everyone should agree is reasonable to implement in their libraries. Of course, this then becomes a somewhat greater implementation effort.

[doganulus]

The easy answer for (2) is that the serialization format specification assumes no ordering. Even I think it does not need to represent a valid DD. Checking this and other assumptions is better in DD libraries or external utility tools, as you wrote.

For extras/vendor fields, the specification may impose no restriction on them. I have seen this practice in .gltf specification and in CMakePresets. Seems it works as intended.

For example, extras fields may look as follows in JSON, inspired by the aforementioned practices.

// example.bdd.json
{ 
    "id": "1",
    "type": "bdd",
    "attributes": {
        "nodes": [
            {
                "v": 1,
                "0": 2,
                "1": -1
            },
            {
                "v": 2,
                "0": 2,
                "1": -1,
                "extras": { // Extra node properties (free object, not in specification)
                    "cudd": { // Use vendor name as namespace convention
                        "marked": true
                    }
                }
            }
        ],
        "extras" { // Extra graph properties (free object, not in specification)
            "cudd": { // Use vendor name as namespace convention
                "features": "markedness"
            }
        }
    }
}

[daemontus]

In essence, I agree with everything (especially that the order of BDD nodes should not matter). I'm just a bit worried that if you promote extensibility too heavily, you end up in a situation where every library only supports their own flavor of DDs with their exact requirements and metadata, and you still have to write a bunch of translation layers to move data between DD implementations. But this will always be a balancing act I guess :)

[doganulus]

you end up in a situation where every library only supports their own flavor of DDs with their exact requirements and metadata

True. This is always a risk in such standardization projects. But, otherwise, without first-class support for extensibility, tool authors (especially in research) tend to go for their own 100% custom format for their new big idea. I think we cannot (and shouldn't try to) prevent that. Instead, a better approach would be that this standard handles common cases well enough while allowing for wild cases. This way, a shared foundation can still be maintained to some extent.

Hopefully, experimental features introduced in individual tools or papers can, over time, evolve into standard node, edge, graph, or metadata properties if they gain enough traction in the DD community. In that sense, the standard can serve as a mechanism for continuous unification, not by restriction but by adoption.

[ondrik]

Thank you for involving me, I'll be happy to help. Having a common format for storing various DDs has been on my mind for a few years. We discussed at some point with @trolando but it didn't gain traction. Some point addressing the raised issues here:

1. text/binary: definitely text first
2. allow extensions! While decision diagrams with more than one implementation are probably just (c)BDDs, ZDDs, and MTBDDs, it would be good to have a common way for defining extensions, so that one can still have, e.g., a common tool for visualizing the diagrams. From what I've seen, extensions can be seen as BDDs that
   a. have labels on edges,
   b. have labels on nodes, or
   c. have multiple outgoing edges,
   or a combination of the previous (e.g. TBDDs, C(B/Z)DDs, (c)ESRBDDs, EVDDs, QMDDs, LIMDDs, ... maybe also CFLOBDDs, but I haven't tried those).
3. order of nodes: good order helps, but should not be required. One option is to use promises where a file can promise that the order of nodes is correct and the implementation can trust it (similar to what is done in HOA and Spot). One could then have a separate tool that performs the reordering in the preferred way (recursive/level-by-level/...)
4. multiple DDs in one file: as with HOA, one might consider having multiple DDs (perhaps of a different type) in one file
5. metadata: as with HOA, it is good to allow storing arbitrary metadata about a DD

There was an attempt for the format inspired by HOA and MATA formats at https://github.com/VeriFIT/bdd-format with examples of some DDs, which has been implemented by @fifixsandy in a fork of BuDDy that also supports MTBDDs https://github.com/VeriFIT/MoToBuddy.

(let me tag @alaarman, who might also contribute)

[doganulus]

We discussed at some point with @trolando but it didn't gain traction.

Getting traction is one of the key challenges here. If there's one takeaway I'd advocate for in this discussion, it's to resist the urge to define a custom text format.

Instead, I would take a pragmatic approach: start with a textual format like JSON targeting debug and inspection purposes, and pair it with an industry-standard binary format like Protobuf for production use. Then our task is simply reduced to defining schemas in those languages. And we're gonna get all their ecosystem benefits immediately (tooling support, linters, code coloring, etc.). I believe this is critical for getting traction. It is one less thing to convince industry people to try/adopt your tools.

Then your examples give a good sense of possible fields in these schemas, which would be tangible outputs of this discussion.

[ondrik]

We discussed at some point with @trolando but it didn't gain traction.

Getting traction is one of the key challenges here. If there's one takeaway I'd advocate for in this discussion, it's to resist the urge to define a custom text format.

not getting traction was solely due to my lack of capacity to push it. Custom formats worked nicely with HOA, DIMACS, AIG. I like HOA much more than having a JSON/XML/... since I can easily edit them and use standard UNIX CLI tools to work with. I've seen ways to use, e.g., XML to store automata and it was a real PITA to work with.

[doganulus]

That's why I said resisting the urge to define a custom format. :)

I am aware of this tendency in general. But this serialization topic is not the key part of your research. In general, we do not have the capacity to push/maintain/promote such custom formats and tooling around.

So here we really really should use the most generic/common tech. Let's pick an existing serialization format, and let's discuss the schema.

[alaarman]

Thanks for including me, @ondrik. Not reading the entire discussion, I hope I can add something useful.

---

First, some brief comments on minor decisions:

Text seems good (binary can indeed be added). Should text be readable? I don’t know. With a good editor, XML/JSON/etc might be more readable and navigable (we are storing a DAG after all and more generally graphs [WAD]). This would also give much of the parsing and file handling for free.

Storing forests makes sense to me.

---

My longer answer pertains to the extendbility:

I like the metadata idea and share the concerns about a fully extendible format. I wonder if there is a middle way by providing typing. We would have to raise the level of abstraction a bit. Let me illustrate this with examples

Let's fix the scope for now to canonical DD-like data structures with a linear variable order (e.g., excluding SDD, CFLOBDD, HDD). In the most general definition, this includes:

Leaves with typed labels.
Nodes with typed labels.
Edges with typed labels.
Edges with typed modifier labels.

What do I mean with typed labels?

For instance, let’s take a look at diagrams representing Boolean functions f : B^n —> B:

• In the case of a BDD, we have B-typed leaves and B-typed edge labels (low and high). There are no modifiers.

Let’s take a look at diagrams representing pseudo-Boolean functions f : B^n —> D, where D is some field (sometimes just a semi-ring):

• in case of ADD (MTBDD), we have D-typed leafs and Boolean edge labels. There are no edge modifiers.
• In case of a multiplicative-EVDD, we have D-typed leaves and Boolean edge labels. The edge modifier label type consists of an element of the group D (and is indeed interpreted as a scalar for the function that the target node represents). In practice, for canonicity, only the multiplicative unit is taken as a leaf label.
• In case of an additive-EVDD, we have D-typed leaves and Boolean edge labels. The edge modifier label type consists of an element of the group D (and is indeed interpreted as an additive constant for the function that the target node represents). In practice, only the additive unit is taken as a leaf label.
• In the case of LIMDD, the edge modifier of the multiplicative-EVDD is extended with a linear map, which is interpreted as a linear transformation of the pseudo-Boolean function represented by the edge target node (so this is a map over the remaining variables in the DD, perhaps we can type check this).

There are also multiple-valued diagrams defining functions f : N^n —> B. They can be defined similarly. MVBDD would be defined with multiple edge labels, whereas ListDD would have two edge labels (right, down).
(Cool idea: if we include the definition of the semantics using the same tools, we could create a meta-package for decision diagrams. We would also have to parameterize the MakeNode, or more generally, the MakeEdge operation of LIMDD.)

Furthermore, difference decision diagrams [DDD] and decision diagrams modulo theories [DDMT] can probably also be represented this way.

So, in sum, for things to be generic, I assume that there has to be some mathematical structure whose signature can be defined in the header of the file format. Here, it also makes sense to rely on libraries already dealing with these kinds of abstractions. For instance, Dafny (Boogie? other theorem provers) come with many predefined signatures. Again, the parser, etc, can then be reused.

---

PS
I realize now that this can even be extended to support non-linear ordered DDs, such as SDD and HDD: If we make the DD definition itself a type, we can store DDs on the edges. An SDD will have edge labeled by SDDs. An edge is then interpreted as a conjunction of the interpretations of these SDDs, while a node is a disjunction over the edge interpretations.

PPS
Some DD types require variables to have types as well. See, e.g., the positive and negative Davio decomposition of [OKFDD].

[DDD] Møller, Jesper, et al. "Difference decision diagrams." International Workshop on Computer Science Logic. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999.

[DDMT] Michelutti, Massimo, et al. "Canonical decision diagrams modulo theories." ECAI 2024. IOS Press, 2024. 4319-4327.

[OKFDD] Drechsler, Rolf, et al. "Efficient representation and manipulation of switching functions based on ordered Kronecker functional decision diagrams." Proceedings of the 31st annual Design Automation Conference. 1994.

[WAD] Blondin, Michael, et al. "Weakly acyclic diagrams: A data structure for infinite-state symbolic verification." International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Cham: Springer Nature Switzerland, 2025.

There seems to be some previous work:
https://cris.tuni.fi/ws/portalfiles/portal/2312848/stankovic.pdf

[trolando]

A few comments, a bit unstructured:

• I am not a big fan of JSON for this, it's quite verbose especially for editing. The example.bdd.json above, in my opinion it's a lot of text for basically two nodes.

• I would also argue for a way to convert between a binary and ASCII representation at least of the actual nodes. For example we could start with a bunch of headers in text format, then after the headers we would just have all the nodes and edges, and that could be ascii or binary. (With some caveats such as handling of floating point numbers that might change when converting back and forth.)

• I would really want the ability to store a forest, rather than just a single diagram. Storing a forest allows sharing nodes between the stored decision diagrams. That is, the header should have a "roots" field that tells me what node ids are the roots.

• Looking a bit at a format like HOA (hanoi omega automata format), you could have a bunch of metadata in the header describing things like sortedness (or even a specific ordering), or maybe start with a "features" field that has things like if it's ordered, if it's binary or multiway, what kind of leafs there are, what are node/edge label types. The most standard one would be a binary node (two children), the node label is a variable identification, and we could say it's "ordered: 0 1 2 3 4 5" for example, and it would have boolean leafs, or you could define multiple leaf types, like numeric, real, fraction, etc.

• A complement edge technically is an edge labeling without data. I don't personally care if complement edges are in the file format or not. However there are plenty of DD types where you want to store one or more edge labels, e.g. TBDD stores a variable label, etc. So we'd need to potentially put labels on

• Do we want to support anything that has something else than an integer as the node label? Right now of course we just have variables that are /usually/ binary, but not always. Anyway, I think that you could always just say well this node is that type, and that type dictates that the next value is the node label and then followed by x and y and z etc.

• We may want to have additional fields in the headers that are not technically part of the BDD but that give helpful information to whatever internal tool, for example if you need extra things to describe a transition system.

• One useful feature to have is the order in which nodes are stored, could be done bottom-up so you could parse it in one pass. Since we're essentially just storing DAGs, I would actually expect that every DD package would naturally store in that order, unless you just dump the whole forest as-is, without even identifying roots. If nodes are stored in arbitrary order, one would need multiple passes to import the DDs.

So in my mind, you'd want to have a header with metadata, it would tell you what the roots are, what variables there are and maybe what order if there is an order, what types of nodes to expect (including leaf types). Then after the header, you'd just have all the nodes, maybe like this:

Features: bdd ordered leaf-boolean leaf-integer
Order: 1
==
0 bdd 1 1 2
1 leaf-boolean T
2 leaf-integer 5

That would be for a bdd with leaf types boolean and integer (mixed). Each node would have a unique id (the first integer), then a type, and depending on the type, the parameters. We would define a bunch of standard types like bdd, cbdd/czdd, zdd, tbdd, also mdd, etc. It's still a bit verbose to have a type of node in every line, but I don't really see a "nicer" way to do that if storing mixed types. And I haven't really thought yet of how to do edge labels in a meaningful way, especially if there would be multiple potential labels. Or we make this very simple: a node of type "bdd" always has three parameters: id, then-child, else-child. And a node of type "bddc" has a complement on the [true/false] edge. Or a node of type "bddc" has an extra fourth (or fifth) parameter with the complement edge.

[doganulus]

which particular concerns? I don't see it.

You are not bound by the default solution if you want to keep it minimal. For example, Protobuf Lite version keeps it smaller by cutting some advanced features. Other projects like nanopb or protozero keep the bloat even smaller. Since the wire format will not change, you can even write your own binary parser for absolute zero dependency. The wire format guarantees your own parser will work in the future.

Not everyone wants that minimality. A Rust and DD lover may want to depend on a new protobuf parser on Cargo. A good interoperable serialization format should handle many such use cases for many needs and personal choices.

How to solve extensibility, e.g., MTBDD with any domain?

What is your opinion about extras fields in earlier posts?

this might be an issue; any ideas about a workaround? Anyone has experience with Cap'n Proto? I still think a simple text format is the way to go.

One solution, as I said, is to concatenate multiple length-delimited Protobuf messages (each less than 2 GB); the file itself may be larger than that limit. I saw another solution from the ONNX project, which is a Protobuf-based serialization format for neural network models. There, they keep multiple files in a dedicated directory, and tools read all files in the directory for a single model.

I realized the ONNX project is particularly similar to our goals and motivations here in this discussion. I will check it in more detail. Especially its Proto declarations.

[doganulus]

Here is the ONNX format specification:
https://github.com/onnx/onnx/blob/main/docs/IR.md

A similar schema specification could be the tangible output for this discussion.

[ondrik]

Thanks for the reply!

which particular concerns? I don't see it.

You are not bound by the default solution if you want to keep it minimal. For example, Protobuf Lite version keeps it smaller by cutting some advanced features. Other projects like nanopb or protozero keep the bloat even smaller. Since the wire format will not change, you can even write your own binary parser for absolute zero dependency. The wire format guarantees your own parser will work in the future.

ok, I understand now but I'd suggest to really try to look at how the output looks now (I have a bad experience with discrepancies between what is advertised and what is delivered). Regarding the used-once dependency mentioned by @daemontus , this might be actually used-often, e.g., if you're developing an MTBDD-based algorithm and you're changing the domains a bit.

What is your opinion about extras fields in earlier posts?

It is just saying let's have an extra labelling of a node/edge, which is what I'm all in favour of (not necessarily for any DDs though). It depends on the specifics

this might be an issue; any ideas about a workaround? Anyone has experience with Cap'n Proto? I still think a simple text format is the way to go.

One solution, as I said, is to concatenate multiple length-delimited Protobuf messages (each less than 2 GB); the file itself may be larger than that limit. I saw another solution from the ONNX project, which is a Protobuf-based serialization format for neural network models. There, they keep multiple files in a dedicated directory, and tools read all files in the directory for a single model.

I also thought about tarring multiple files together, but will that solve the problem? I understood that the issue is more fundamental, such as the size of the BDDs would be limited, which would be a problem. What is the reason for the limitation? Is there support for references that are 31bit long or something similar?

However, I'm thinking that we are now discussing too specific details and maybe it would be a good time to take a step back and try to define the goals and proposed use cases of the format, otherwise it might be hard to know whether proposed solutions satisfy them or not. Maybe the output of the discussion will be that we should have multiple formats, e.g. binary and concise one for BDDs and text-based one for extensions.

What do you think? I'll probably be off during the weekend, but no one starts earlier, I can probably start some document next week. Maybe starting a repository for a work on the format would make sense.

[trolando]

Personally my main use for storing BDDs in a file is pretty boring, I exclusively use them as benchmark input/outputs. I have a bunch of transition systems that are described "somehow", then I use LTSmin to obtain the BDDs representing the transition system, and I store them to disk so I can do benchmarks without requiring LTSmin...

My own projects that use Sylvan just process the resulting BDD without storing the diagram to a file.

Maybe one could store a BDD as output of something like symbolic state space exploration, to dump the resulting state space to disk. Who knows it might have taken a few hours to compute that state space, and we want to process the result several times without having to repeat the exploration step... that might be a use case for interoperability, if you have different tools that might want to do something with the result. Still, for me this is purely theoretical, I don't have a concrete workflow that asks for a BDD file format in mind.

[doganulus]

I understood that the issue is more fundamental

Yes, the problem is related to some hardcoded 32-bit number in the original Protobuf design. Flatbuffers have the same limitation. Capnproto does not have it as they use 64-bit for everything(?).

However, I'm thinking that we are now discussing too specific details and maybe it would be a good time to take a step back and try to define the goals and proposed use cases of the format,

I agree with that. I think we have understood some requirements better.

Maybe the output of the discussion will be that we should have multiple formats, e.g. binary and concise one for BDDs and text-based one for extensions.

We need to do some exercises how to model known and unknown DD extensions. Like how to model MTBDD using JSON? Or how to model ZDD using Protobufs? How to model edge properties using them? Etc, etc.

[ssoelvsten]

Parts of this discussion relate to visualizing (and editing) BDDs. One of the PhD students at Eindhoven works on this ( I don't remember the name, but @nhusung should know ) ; their inputs/project might be of relevance.

[ondrik]

I made a basic documents with goals here (allowed for suggestions only to avoid ad-robots taking over the discussion; if you want a direct edit permissions, please send me your account name and I'll add you). Please read and comment.

[doganulus]

I actually wonder if random-access zero-copy binary blobs (e.g. written using flatbuffers or capnproto) can be any help for very large DD algorithms. For simulating virtual memory or similar. Again, I am not familiar with those challenges. What could you say, @ssoelvsten?

[ssoelvsten]

For most of my experiments, I've been using applications/benchmarks where the BDDs grow very quickly; hence, there hasn't been much need for serializing BDDs for me. But, for the relprod operation I had to use serialized BDDs from Model Checking to get around a performance issue*. Following the example of Pastva and Henzinger, I used LibBDD on a 64 GiB machine to produce BDDs of each order of magnitude. These were stored together with the transition relation:
https://zenodo.org/records/13928216

I was only able to construct BDDs of size 2²⁵, i.e. ~0.5 GiB . Yet, as Tom points out that might just be a symptom of my state space exploration being too simplistic.

* Adiar's development has not (yet) focused on small instances. Hence, it is several orders of magnitude slower for these; for model checking tasks, Adiar was stuck processing the small instances. I have things planned to address it, assuming I can find time/someone to do it.

[daemontus]

I don't have a very technical opinion on this, but we do sometimes store large BDDs in AEON/lib-bdd as computation results for further analysis. It's usually for problems like synthesis/inference, where the result of the computation is a very large set of candidates that one usually needs to save for further analysis (typically, that analysis is projection to some smaller, more reasonable subset of variables, or search for some maximal/minimal solutions, but you often don't know the exact parameters for this beforehand, so saving the result is quite useful).

Overall, we do sometimes need larger than 2GB BDDs. I don't think it's super often, and we usually don't work with anything on the order of 10s or 100s of GBs (but that's partially also a technical limitation; it's just very slow to get such large BDDs). But not being able to store more than 2GBs of BDD nodes would essentially mean that we still need some internal format for this.

[ssoelvsten]

I could imagine that Marijn Heule (and others) could be interested in model counting via BDDs of 10s or 100s GiB if not even much larger.

[doganulus]

I see the need for serializing and deserializing very large DDs for several reasons. When the graph is too large to fit entirely in main memory, algorithms would operate on it partially, keeping only a subset of nodes in memory at any given time. Once memory is full, portions of the graph can be serialized to disk, and another chunk loaded to continue processing. For small DDs, this adds little to no overhead since the entire operation can be performed in memory.

Now I think the benefits of random access may be negligible in this context because blobs need to load/unload together.

[doganulus]

Dogan: Below is Stefano Quer's message regarding our serialization discussion.

Using this opportunity, I would like to thank him and his colleague Gianpiero Cabodi once again for their time and efforts for the DD research and community. I find that historical motivation very valuable, as problems and solution approaches do not change much over the years. Instead, we have new technologies to solve them.

I've reviewed the discussion and noted that the main concerns are about generality and readability. I'd like to offer some historical context on the design of DDDMP, which might clarify a few points.

1. Prioritizing Compactness: DDDMP was developed at a time when RAM was a scarce resource. Its primary design goal was to store Decision Diagrams (DDs) compactly on disk (another critical resource more than two decades ago). This priority led to the implementation of a binary format that, by design, favors compactness over human readability and generality.
2. Handling Variable Reordering: The tool's complexity also stems from one of its powerful features: the ability to save a DD and load it into a manager using a completely different variable order. While this adds to the difficulty of use, managing the reordering and metadata is essential for many advanced uses.

[ondrik]

@doganulus Thanks for posting the comment.

Do you have any comments to the document I created above? I can put it in markdown and in a github repo if it helps (might be better for tracking the changes).

[doganulus]

I agree with the goals in the document in general @ondrik.

1. It seems we can only two picks among Compactness, Editability, and Commonality.
   • Compactness, Commonality -> Existing binary formats
   • Editability, Commonality -> Existing textual formats
   • Compactness, Editability -> Custom text format
2. Forestness and metadata are easy. And useful in practice.
3. Scalability we need to think more.
4. Tooling must be delegated to other communities as much as possible by picking existing formats and approaches.
5. Extensibility is also very important because a too rigid format will not unify the DD community. It must include mechanisms (e.g. extras) to add extra fields without requiring a consensus otherwise it wouldn't serve research purposes.
6. The lowest-priority goal seems Embedability to me. I think weak references from other formats would be sufficient if they want to refer any DD related task.

My take: I do not think the DD community has enough resources to maintain its own custom serialization format. So my main point here is that this serialization format must use an existing format and implementations. In this case, I would sacrifice editability I guess. Hence, pick a binary format from existing alternatives (See https://arxiv.org/pdf/2201.02089) and create a schema here to achieve these goals.