WorksComputer Science
AutoDiDact: Input Reduction over Inferred Structure
Abstract
Delta debugging reduces a failing input by deleting chunks of it, keeping a deletion only if an oracle confirms the failure persists. It chunks the input based only on its length, so its deletions cut through units such as identifiers and delimited groups, wasting calls and leaving outputs large. Current state-of-the-art structural reducers avoid this by supplying grammars or built-in format knowledge. We show that structured reduction needs neither: a neutral word and delimiter pairs suffice, and both can be inferred from the failing input by asking only what delta debugging already asks its oracle: does the failure persist? A neutral word, such as a space, preserves the failure when inserted between such units but not inside them, so it splits the input into tokens. A delimiter pair is two tokens that preserve the failure only when added or removed together, so the span they bound can be reduced as a unit. We formalize both, state when the oracle can reveal them, and learn each with a bounded number of calls. AutoDiDact reduces the resulting tree of spans by hierarchical delta debugging (HDD) and shrinks each token across its occurrences. AutoDiDact finds a neutral word in 75 of 125 inputs from 18 format families. On these, it returns outputs 83% smaller than byte-level delta debugging with 37% fewer calls on geometric mean, inference included. The savings grow with input size, to 98% and 87% on inputs of at least 10 KiB. Without a grammar, AutoDiDact matches grammar-based HDD in output size at 3.85 times its calls, and uses 54% fewer calls than C-Reduce's language-agnostic mode. Because it needs only the oracle, AutoDiDact can minimize whatever a fuzzer finds, malformed inputs included.
Introduction
Delta debugging [41] reduces a failing input by deleting chunks of it, keeping a deletion only when an oracle confirms the failure persists. Byte-level delta debugging chunks the input based only on its length, blind to its structure. A chunk that cuts through a unit such as an identifier or splits a pair of parentheses is rejected, wasting a call. A whole unit is deleted only when a chunk happens to align with it, and edits that must touch separate places at once, such as removing both parentheses of a pair, are never tried. On a 95.4 KiB C program from our benchmark that crashes GCC 4.3.0 (Table 2), byte-level delta debugging spends 232,803 calls and stops at 45,061 bytes, not counting whitespace: no single byte can be removed, yet the output is far from small.
Structural reducers edit whole units, using format knowledge supplied in advance. Hierarchical delta debugging (HDD) [26] and Perses [33] obtain units from a grammar. Such a grammar may be unavailable, even for a widely used language [30] or a specified format [10], and one that exists may not cover the dialects and extensions an input uses [27, 29]. Other reducers build format knowledge into the tool. C-Reduce [31] transforms C and C++ with the Clang front end, and for other formats, its --not-c mode keeps generic passes, such as deleting lines, C tokens, or bracket pairs from a fixed list, with or without their contents. This fixed list cannot pair an XML start tag <name> with its end tag </name>, since the names vary with the input.
We show that structured reduction needs neither a grammar nor built-in format knowledge: a neutral word and delimiter pairs suffice. Both can be inferred from the failing input by asking only what delta debugging already asks its oracle, without a lexer, example corpus, or syntax oracle. A neutral word, such as a space, preserves the failure when inserted between units but not inside them, so the offsets where it is accepted split the input into tokens. Each delimiter pair, such as matching parentheses or an XML start and end tag, encloses a span. Its delimiters are coupled: they preserve the failure when added or removed together but not either one alone. We implement this approach in AutoDiDACT, which applies HDD to the inferred tokens and spans, deleting whole spans or only their delimiters, and then shortens each distinct token at all its occurrences. The reducer keeps an edit only if the oracle confirms that the failure persists. Incorrect structure may leave a larger output or require more calls. On the GCC input, AutoDiDACT reaches 151 bytes in 3,023 calls, inference included.
When no neutral word is found, reduction works on bytes, and when no pairs are found, on flat tokens. Because the inferred structure comes from the oracle, it reflects what the failure depends on. In a JavaScript test that crashes an instrumented library, the imported module path "../instrumented/lodash/hasPath.js" stays one token, while the printed test title 'SynTest Test Suite', where a space is accepted at every offset, splits into single characters.
We evaluate AutoDiDACT on 125 inputs from 18 format families. Inference finds a space as the neutral word on every text input and abstains on all but one binary input. Given a neutral word, AutoDiDACT returns outputs 83% smaller than byte-level delta debugging with 37% fewer calls on geometric mean, inference included. The savings grow with input size: on inputs of at least 10 KiB they reach 98% and 87%, respectively, while below 1 KiB outputs are still 30% smaller for 1.79× the calls. Even without a grammar, AutoDiDACT matches grammar-based HDD in output size, at 0.96× on 50 inputs, for 3.85× the calls, or 1.53× excluding inference. Against C-Reduce’s language-agnostic mode, it uses 54% fewer calls. Its outputs are 30% smaller overall, driven by XML, and 1.23× C-Reduce’s on the other families. Inference finds 97.7% of the token boundaries that a standard lexer finds. It makes 11.6% of AutoDiDACT’s calls overall and 8.9% on inputs of at least 10 KiB.
AutoDiDACT parses nothing, so it runs on malformed and binary inputs alike. Fuzzers such as AFL [40] and libFuzzer [23] minimize the crashing inputs they find at the byte level, since they cannot assume an input format. With AutoDiDACT, a fuzzer can carry a general minimizer that works on any input.
Contributions:
The observation that a neutral word and delimiter pairs, both learnable from the failure oracle, suffice for structured reduction without a grammar or built-in format knowledge.
Formal definitions of neutral words and delimiter pairs as oracle behavior, the conditions under which the oracle reveals them, and bounded, sampling-based learners that infer them or abstain, together with a tokenizer that predicts boundary verdicts from earlier probes and tests likely boundaries together.
Laminar reduction, HDD over inferred tokens and spans, with a tree construction in which stray delimiters change the number of spans by at most .
An empirical evaluation on 125 inputs from 18 format families against byte-level delta debugging, HDD, and C-Reduce, with a released benchmark of oracles, pinned target builds, our implementation AutoDiDACT, and experiment scripts.
Input Reduction
Given a failing input , an input reducer deletes atoms, here bytes, while preserving the failure. An oracle returns if candidate triggers the failure and otherwise, and a reducer keeps a deletion only if the result is accepted. We measure cost in oracle calls and in wall time, since calls differ in cost: one may run several target processes.
Ideally, a reducer would return a global minimum: an accepted subsequence of smallest size. Without assumptions about , finding one can require exponentially many oracle calls [41].
Reducers therefore settle for local minimality. An input is 1-minimal over a given sequence of units, such as atoms or tokens, if no single unit can be deleted while preserving the failure.
Running example. Consider a C compiler that crashes on any call to a function named trace, but only after the call parses and type-checks. Suppose a reported function body contains the statements int count = 0; if (count > 100) { trace(count); }. To keep the example small, we reduce only these 49 bytes and keep the rest of the function fixed, with void trace(int); declared. The oracle compiles the function with the candidate in place and accepts it if the compiler crashes. It rejects a candidate that does not parse or type-check, just as it rejects one that compiles without crashing, so the reducer cannot tell the two apart. For the measurements below, we simulate the crash: the oracle accepts a candidate that type-checks and contains a call to trace.
Delta debugging. Delta debugging [41] deletes chunks of the input, keeping each deletion the oracle accepts. We use drdd [20] (Algorithm B.2), a variant of the original ddmin algorithm that defers its restarts. It sweeps the input with chunks of halving size , from half the input down to two units. Each sweep cuts the input into chunks of units, the last possibly shorter, and tries deleting each in turn, from left to right, keeping every accepted deletion. A closing scan then tries deleting each unit alone, repeating until a scan deletes nothing. The result is 1-minimal over the chosen units, so the choice of units determines both where the cuts fall and what the result guarantees.
In the byte-level run, the sweeps with 24- and 12-byte chunks delete nothing, since no candidate compiles. With 6-byte chunks (Figure 1), the sweep successfully deletes > 100, leaving (count).

Figure 1. The third drdd sweep over the running example, in 6-byte chunks of its bytes and 3-token chunks of its tokens. Boxes are units, underlines are chunks, red squiggles split an identifier, and ␣ is a space.
Avoiding bad divisions. Byte-counted cuts fall inside identifiers. Five of the nine chunks at split count or trace. Deleting one leaves a broken or undeclared name, such as unt from deleting int co, which the compiler rejects before reaching the crash, each at the cost of a compilation. Byte-level drdd issues 111 queries, of which only 8 are accepted and 103 do not compile, and ends at the 36-byte int count=0;if(count){trace(count);}. However, if given the token boundaries of a C lexer, drdd can instead count tokens when forming chunks. Every candidate then keeps or deletes whole tokens, never splitting an identifier, and the result is 1-minimal over tokens. On the example, this takes 58 queries and ends at the 34-byte int count=0;if(100){trace(count);}.
Tokens alone still waste queries. With 3-token chunks, the chunk if ( separates ( from its ), and deleting it leaves an unbalanced condition that does not compile. If the reducer also knew that parentheses and braces enclose spans, it could delete a whole span, or unwrap it by deleting both its delimiters in one query. Given these spans as well as the tokens, a span or unwrap drdd (§ 3) deletes the if and its condition and unwraps the braces, reaching the 25-byte int count=0;trace(count); in 47 queries. One relation remains: count must be spelled alike at its declaration and remaining use, so no deletion inside one occurrence alone is accepted. Shortening both at once, as shrinking does (§ 3), reaches the 17-byte int t=0;trace(t); in 15 more queries.
These counts assume the structure is given. This section describes reduction over tokens and spans, and § 4 infers both from the failing input and its oracle.
Reduction over Laminar Structure
Reduction takes the failing input , its oracle, and two kinds of structure. The tokens partition into nonempty, contiguous pieces, and each delimiter pair is an opening and a closing token. a symmetric delimiter, such as a quote, both are the same token. Reduction runs in two stages: laminar reduction deletes tokens and the spans that pairs enclose, and shrinking shortens tokens.
Building the tree. The tree (Figure 2) matches opening delimiters with closing ones. Some delimiters may have no match: failing inputs are often malformed, comments and strings contain delimiters, and pair learning may admit a wrong pair. We want each such stray delimiter to change the number of spans by at most one. A stack that matches each close with the latest unmatched open lacks this property: in { /* (1 */ trace(count); }, the parenthesis in the comment is still open when the closing brace arrives, so the brace span is lost, and with it every span enclosing it. We therefore choose as spans a largest laminar set of matched pairs [16], leaving unmatched delimiters, like that parenthesis, as ordinary tokens. Finding it is Dyck edit distance restricted to deletions [1, 5]. Inserting or deleting delimiters changes the number of spans by at most , and admitting a further pair never reduces it. A stack first matches the unambiguous pairs, and a cubic interval dynamic program then matches the rest exactly (Section B.1, Algorithm B.1). With the parentheses and braces of the running example as pairs (Figure 2), the root holds the declaration’s tokens, if, spaces, and two spans, (count > 100) and { trace(count); }, which holds the span (count).

Figure 2. The running example’s tokens as boxes, and the spans of its parentheses and braces as frames colored by depth. The root holds the unframed tokens and the two outer spans.
Reducing a node. At each node, a delta debugging reducer deletes tokens and child spans, keeping the node’s own delimiters and everything outside it fixed. Laminar drdd uses drdd. For example, deleting if (count > 100) at the root leaves int count = 0; { trace(count); }, which still crashes. Once a non-root node is reduced, two edits try to remove its delimiters while keeping some of its contents. The node is first hoisted: its nearest descendant spans of the same pair are tried in its place, one query each, and the first one accepted replaces it, following Picireny’s hoisting [34]. A node that is not hoisted is then unwrapped by deleting both its delimiters in one query. Unwrapping the braces of { trace(count); } results in trace(count);.
Traversal and guarantees. Laminar reduction (Algorithm B.3) is HDD* [26] over the constructed tree: it reduces nodes level by level from the root, descends only into surviving spans, and repeats until a traversal changes nothing. It reduces each node separately, where HDD reduces a whole level at once.
For any tokens and pairs, laminar reduction guarantees that it (1) preserves the failure, (2) terminates after at most traversals that change the input, since each deletes a nonempty token, and (3) ends with every node 1-minimal over its items and every remaining span’s hoists and unwrapping rejected.
Each traversal runs drdd’s closing scan once per node, so it makes at most three queries per item for the sweeps and the scan and two per span to hoist or unwrap it, and by (2) laminar reduction makes queries, as drdd does in its own worst case.
Shrinking tokens. After laminar reduction, shrinking (Algorithm B.4) runs one pass of drdd that shortens each distinct multi-atom token by deleting from all of its occurrences at once, which turns int count=0; trace(count); into int t=0; trace(t);.
1-minimality. Like HDD* [26], laminar reduction ends 1-minimal over nodes by (3). It is not 1-minimal over atoms, since it never deletes a lone delimiter or part of a token. Shrinking may also re-enable a deletion that laminar reduction rejected. Repeating drdd’s closing scan over atoms until it deletes nothing makes any output 1-minimal over atoms, at one query or more per remaining atom. AutoDiDact does not run this scan, and § 7.1 reports what it adds.
Inferring the Structure
The oracle answers only yes or no for a whole input, so we read structure from how its verdict changes under edits of the failing input: insertions reveal tokens, and paired edits reveal delimiters.
Oracle-Relative Structure
Tokens and delimiter pairs follow one pattern of oracle verdicts: an edit that respects the structure preserves the failure, while controls, minimal variants that break the structure, lose it. Only this contrast shows that a word separates or a pair matches: accepting both edits, as inside a comment, or rejecting both reveals nothing. Neither definition mentions a format or needs to be well formed.
Tokens. We seek a word that the failure treats as a separator: inserted between units, it preserves the failure, and inserted inside one, it does not. With such a word, one query per offset locates every boundary. Lexers often discard such a separator, like whitespace, between tokens. In the running example, inserting a space between trace and ( gives trace (count);, which still crashes. Inserting a byte absent from the input, such as @, gives trace@(count);, which is rejected, as is tr ace(count);, with a space inside the identifier. Spaces at any number of token boundaries, in any amount, compile and crash. We take this contrast as the definition of neutral words.
Let for the failing input , and number each internal offset by the count of atoms before it, so that . For a word , we write for with inserted at . Fix a control atom that is as rare in as possible, so it is unlikely to be neutral. An offset is selective for a word if the oracle accepts but rejects both controls and , the latter with copies of . Selectivity rules out regions the oracle ignores and regions where any text of the right length suffices. A nonempty word is neutral for if, for some nonempty set of selective offsets, the oracle accepts with copies of inserted at each , for every choice of the counts . Neutrality asks more than one accepted insertion: copies must be accepted in any amount and at all offsets of at once, as a separator’s are. Given a neutral word , the token boundaries of are the offsets accepting a single insertion of it,
and these boundaries cut into its tokens. Every selective offset is a token boundary, and offsets that the failure ignores, such as those inside a comment, are token boundaries without being selective. In the running example, the space is neutral, and the tokens are the C tokens and the spaces.
An input may have several neutral words, such as a space and a newline in C, and their boundaries can differ: inside a string literal, a space may be accepted where a newline is not. If the oracle sees its input only through a lexer that discards between tokens and rejects there, every lexical boundary is a token boundary, and a lexical token is split exactly where the failure does not need it whole (Section A.1), as with the JavaScript test title of § 1. Any separator such a lexer discards thus recovers the lexical boundaries, and finding one is a matter of inference (§ 4.2).
Spans. Parsers need brackets to match: adding or removing an open and close together can keep them matched, and adding or removing only one does not. In the running example, wrapping count gives the accepted trace((count));, and adding only one parenthesis, as in trace((count); or trace(count));, is rejected. Again we take this contrast as the definition. Because delimiters are tokens, a pair can be any two tokens that the failure needs matched, not only bracket characters: begin and end, a quotation mark with itself, or the <name and </name that open an XML start and end tag, whose names vary with the input and so escape any fixed list of brackets. The candidates thus narrow from every substring of to its distinct tokens. Write for its tokens. For tokens and , a matching of a token sequence pairs positions with and , using each position at most once, so that any two pairs are nested or disjoint. Let be the size of a largest matching and the number of positions holding or . Then is matched if a largest matching leaves no delimiter out, that is,
where counts the occurrences of a token in , and ranges over the prefixes of . The difference counts stray delimiters, which the tree of § 3 minimizes over all pairs at once. The spans of are the intervals with , , , and a matched interior , which for a symmetric delimiter holds none of it, since quotes do not nest. We write a span as , with opening delimiter , interior , and closing delimiter . Each row below replaces a span, leaving the rest of fixed, by a paired edit, which adds or removes and together, and by two controls, each off by one delimiter, an in one and a in the other:
The span couples if, in some row, the oracle accepts the paired edit and rejects both controls, telling balanced delimiters from unbalanced ones. The pair is a delimiter pair of if at least two of its spans couple, since one coupled span could be a coincidence. Parentheses that the oracle ignores, as in a comment, are not a delimiter pair. Suppose the oracle, like a parser, rejects every unmatched input, and that is matched. Every paired edit then keeps matched, and every control does not, since one delimiter more or fewer makes odd, so every control is rejected. A parser’s pair is thus a delimiter pair once two of its spans survive a paired edit (Section A.2). For the same reason, deleting or unwrapping a span keeps the delimiters matched, and spans spare reduction the doomed deletion of one delimiter alone (§ 2). Nor must be matched: coupling is judged span by span, and the tree of § 3 leaves stray delimiters as ordinary tokens.
What the learners admit. The learners of § 4.2 and § 4.4 admit a word or pair on finite evidence for these definitions. Neutral-word discovery admits a word that is selective at observed offsets and passes a few reuse tests, each inserting copies of it at some of those offsets. A neutral word passes these tests within its set . Pair learning admits a pair once it observes coupling at two candidate intervals, pooling the spans of a family of pairs that differ only in a name, such as XML tags. Two further checks guard admission: an entropy guard vetoes a word confirmed on weak evidence in a repetitive input, and a pair is tested only if duplicating either delimiter of a representative pair is rejected.
What queries cannot show. Both learners generalize from finitely many queries, which cannot rule out a different verdict on an untested edit or name. The definitions also leave four cases open. A neutral word need not separate anything: a digit is neutral when lengthening a number keeps the failure. Genuine delimiters yield no witness when every paired edit destroys the failure. Tokens that must appear together without enclosing anything, such as ? and : in C, can also couple. If the control is accepted at every sampled offset, none is selective, and discovery abstains.
Neutral-Word Discovery
Neutral-word discovery (Algorithm 1) proposes repeated substrings, observes where each is selective, and tests the most promising for reuse. It judges neutrality from a sample of offsets, and the evidence a sample provides depends only on the sample size. If a word rejects of the offsets where it is selective, such offsets drawn uniformly at random all accept it with probability at most , however long is. The implementation therefore uses a fixed budget of 300 calls, with 16 reserved for confirmation. The bound assumes uniform sampling, and SCHEDULE skews it toward varied contexts, so the bound only motivates the budget.
Algorithm 1 Discover a neutral word
Input: Failing input , oracle Output: An admitted word, or to abstain
Before any query would exceed 300 calls in total, return .
sourcesfirst 40 words of CANDIDATES(), and the first 24if then return
the lowest byte from 1 to 255 absent from , or else the rarest byte of , lowest on ties
OBSERVE(, , , , SCHEDULE(,
sources), 284)if then return
rankedwords with and ((C.1)), stably by decreasingrefutedwhile
rankeddoRemove from
rankedits first word whose rootrefuted, or else its first wordSITES(, ), and REFINESITES(, )
Test REUSETESTS(, ) in order, stopping at the first rejection
if all reuse tests accepted then return if and , else
if a reuse test rejected then
refutedrefutedreturn
Candidates. A separator tends to recur beside varied tokens. In the running example, the space occurs 10 times, after 7 distinct atoms and before 10. CANDIDATES therefore proposes maximal repeats: substrings that occur at least twice, with at least two distinct atoms before them and two distinct atoms after them. Non-separators such as (count also qualify, but ount does not, since it always follows c. A candidate with occurrences, distinct atoms before, and after ranks by , with shorter words first on ties. The space thus ranks first at , well ahead of 0 at . The top 40 candidates steer where SCHEDULE samples offsets, and the top 24 of them form the tested words . An offset where is rejected costs one query per tested word, so with 24 words the observation budget covers about ten such offsets. The other 16 only steer sampling, at no cost. Both limits are hand-picked. The root is the shortest word whose repetitions form , and words with the same root form a family, such as one and two spaces.
Assumptions. Discovery finds a neutral word only if it occurs in as a maximal repeat among the top 24 candidates. It cannot learn a word that does not repeat, such as a space in minified code, and then abstains, so reduction proceeds over bytes. Formats without a recurring separator, such as most binary formats, account for all 50 abstentions in our benchmark (§ 7.3).
Observation and scoring. At each offset that SCHEDULE picks, OBSERVE first inserts the control . If is accepted, the offset reveals nothing. Otherwise, it inserts each word of and credits the words that are selective there. A word’s score averages its credit, weighting offsets that credit few families more, since an offset that credits many says little about any one. Its adjusted score subtracts a rank penalty, so later candidates need more evidence. Scores filter and order candidates for confirmation.
Confirmation. Selectivity shows only that one copy is accepted at one offset, and a neutral word must also preserve the failure with any number of copies at the offsets of together. In the running example, adding three more spaces after int gives int___count = 0;, which still crashes. Such a query is a reuse test, inserting copies of the word at one site or at several together. In score order, discovery confirms the first word that passes its reuse tests. Each word gets at most five tests, at up to four accepted offsets, favoring distinct contexts (Section C.1). A rejection refutes reuse at those sites, and discovery tries other families first. Passing cannot rule out non-neutral words or interactions at untested sites. On the running example, the space ranks first and is confirmed in 5 calls after 284 observation calls.
Abstention. Neutral-word discovery abstains when no word passes confirmation within its 300 calls. It also abstains on weak evidence in repetitive inputs, where a word may pass only by lengthening padding: if fewer than three selective sites support the confirmed word and . Here is the entropy of the atoms of , normalized by its maximum for their number of distinct values, and zero when fewer than two distinct atoms occur.
Tokenization
Given the neutral word , tokenization finds the token boundaries (1). Probing each internal offset alone, by querying , finds them exactly, at one query per offset. The default tokenizer (Algorithm 2) saves queries in two ways: it predicts verdicts from those it has already settled on the same input, and it tests several likely boundaries with one query.
Algorithm 2 Tokenize with boundary prediction and pooling
Input: Failing input , neutral word , oracle
Output: The tokens of
Every verdict that the oracle answers or implies trains Estimate.
empty verdict map, and empty pool
for do
if or then
✓ if , else X predict
else if then
, then probe alone
else
Add to , and ✓ tentative boundary
if then
return the substrings of between consecutive offsets of
Prediction. Inputs repeat local patterns, and so do verdicts. In the running example, the offsets inside count have the same atoms around them at all three occurrences, as does the offset between ( and count at two. Estimate predicts an offset’s verdict from the settled verdicts of offsets that resemble it in the atoms around them, the verdicts next to them, or the share of boundaries nearby. Each kind of resemblance is a context. Estimate combines the boundary rates of an offset’s 14 contexts into , the estimated chance that the offset is a boundary. It trusts a context more when more settled offsets share it, and learns on each input which contexts predict well (Section C.2). The tokenizer predicts the verdict at fixed cutoffs or . The contexts and cutoffs are hand-picked and shared across formats.
Pooling. A neutral word can appear at many offsets at once, so the tokenizer tests likely boundaries together: one query inserts at every offset of a pool. In the running example, trace_(_count_)_; still crashes, settling the four offsets between the tokens of trace(count); in one query. A rejected pool holds at least one non-boundary, which binary splitting finds (Section C.2), as in adaptive group testing [8]. Pooling assumes, beyond what neutrality guarantees, that a pool is exactly when each of its insertions alone would be. Where this fails, a rejected pool of boundaries yields a false non-boundary, merging two tokens.
What to query. A query tells the most when its outcome is a coin flip and the least when it is nearly certain (Section C.2). The tokenizer therefore predicts nearly certain verdicts, and probes a likely non-boundary, with , alone, since a pool containing it would probably be rejected. It adds each likely boundary to the pool instead, and tests the pool once the estimated chance that all its offsets are boundaries, , falls to one half.
What prediction affects. The thresholds give no error guarantee. A wrong prediction can only merge tokens, hiding a delimiter, or split a token that exhaustive probing keeps whole, changing the inferred pairs, output size, and oracle cost. The resulting tokens are then frozen for pair learning and reduction. § 7.3 measures them against exhaustive probing and against real lexers.
Pair Learning
§ 4.1 showed that (count) couples. In the running example, so does (count > 100), the other span of the parentheses. Pair learning (Algorithm 3) finds such pairs on its own. It proposes hypotheses, each a single pair or a family of related pairs, such as XML tags, together with candidate intervals where they might delimit spans. It ranks hypotheses without queries, skips unpromising ones, and admits a hypothesis once two of its candidate intervals couple, as the parentheses do.
Algorithm 3 Learn delimiter pairs
Input: Input with frozen tokens, word , oracle Output: Inferred delimiter pairs
, and — admitted intervals
for do
, and
for each do
if then break
, and
if reuses a token of , , no interval in encloses a non-blank token, or not then continue — screens
if then , , and else
return
Hypotheses. Delimiters are non-blank tokens, those not made only of copies of . A hypothesis is stacked if its opening and closing delimiters differ, so that a stack can match them like brackets, and symmetric if a token pairs with itself, like a quotation mark. Every two distinct tokens that each occur at least twice form a stacked single pair, in whichever orientation balances better, and every token occurring at least four times forms a symmetric one. An affix family is a set of pairs whose delimiters share a name and differ only in a fixed prefix or suffix, such as and for XML tags. It pools evidence from names too rare to propose alone. Formally, it groups the pairs or over at least two names , in either orientation, for any distinct nonempty affixes . Hypotheses ranks each kind and keeps its best, a hand-picked cap that binds on most inputs. The stacked list is tested first, and the symmetric list is built from the intervals admitted so far.
Assumptions. Pair learning can admit a pair only if tokenization kept its delimiters as tokens, the pair is proposed as above, and its hypothesis ranks among the top of its kind. A pair occurring only once can be learned only through an affix family. In the running example, the braces occur once each, so pair learning never proposes them.
Candidate intervals. Each hypothesis proposes intervals for coupling tests. For a stacked hypothesis, a stack matches each closing delimiter with the opening delimiter on top of the stack if it has the same name, and each match is a candidate interval, such as (count > 100) and (count) in the running example. Admitted intervals divide the input into regions, each directly inside one interval. Within each region, a symmetric hypothesis pairs its occurrences in order: the first with the second, the third with the fourth, and so on (Section C.3). In f('a'); g("it's"); h('b');, the apostrophe in it's is alone inside ’s admitted parentheses, so it pairs with nothing, while over the input it would pair with the quote opening 'b'. Candidate intervals need not be spans: family matching can leave stray delimiters inside one, and in-order pairing ignores nested regions.
Ranking. In the running example, the two ( and two ) occur in balanced order, which only two of their six orders achieve. Delimiters that the failure needs matched are balanced like this far more often than chance. Each hypothesis therefore gets a prior , the surprise of its balance, meaning the negative log probability that a random shuffle of its occurrences leaves no more closing delimiters unmatched than the input does. For the parentheses, . A family adds the surprise of its names, and a symmetric hypothesis counts the regions holding an odd number of its occurrences (Section C.3). Every prior is capped at , and only hypotheses with at least two candidate intervals are eligible. Stacked hypotheses rank by , and symmetric ones by , which favors tokens with more sites to test. The prior only orders hypotheses and sets each one’s testing allowance , so that more surprising hypotheses get more tries.
Screens. Before spending coupling queries, Algorithm 3 screens out any hypothesis that (1) reuses an admitted delimiter, (2) has more than intervals that cross admitted ones, or (3) has no interval enclosing a non-blank token. These screens cost no queries. Screen (3) can discard a useful pair, since even an empty span may be worth unwrapping. A survivor must also be sensitive: duplicating either delimiter of a representative pair must be rejected (Section C.3).
Confirmation. Test seeks two witnesses, intervals that couple, among the intervals that cross no admitted one. It tries intervals of varied contexts and lengths, giving up after intervals without a witness, or in all (Algorithm C.3). On each interval, Coupled tries the rows of (3) in order and succeeds at the first that couples, since a genuine span can fail some rows. Four consecutive failed hypotheses stop the current kind, and screened hypotheses do not count toward that streak.
Once a hypothesis is admitted, it pairs join , and its intervals that cross no admitted one are admitted too, tested or not. A family’s two witnesses may come from one name, so its other names are admitted by extrapolation, and the newly admitted intervals can suppress later hypotheses.
Query Bounds
Every stage’s query count is bounded in the input size . Neutral-word discovery makes at most 300 queries. Exhaustive tokenization makes , and prediction and pooling usually make fewer, with queries even in the worst case at the fixed thresholds (Section C.2). Pair learning tests at most hypotheses of each kind, each with at most queries, and , so it makes queries (Section C.3). Laminar reduction makes (§ 3), and shrinking, one drdd pass per distinct token, makes at most quadratically many in the tokens’ total length. The whole pipeline thus makes queries in the worst case, the order of drdd itself. Candidate generation, ranking, prediction, and tree construction make none.
Evaluation
We evaluate AutoDiDACT on 125 failing inputs from 18 format families against byte-level drdd, HDD, and C-Reduce. The most important question for a new reducer is whether it improves upon the baseline. Hence, we ask:
RQ1: How does AutoDiDACT compare with byte-level drdd in output size and calls?
counts a family’s inputs, and the benchmark has 125 in all. ICE denotes an internal compiler error, and control denotes behavior preservation. In the word column, ␣ is a space, 10 B is the sequence returned on one ASN.1 input, and – denotes abstention.
With inferred structure, AutoDiDact can tackle structured inputs. But how good is that structure? Is it competitive with reducers that have format knowledge? Hence, we ask:
RQ2: How does AutoDiDact compare with the format-aware HDD and C-Reduce?
Finally, AutoDiDact rests on structure learned from the oracle alone, so we ask what that inference recovers and what it costs.
RQ3: What structure does inference recover from the failing input and its oracle alone, and at what cost? An answer tells us whether a failure oracle can stand in for the lexer and grammar that structural reducers need.
Inputs and Oracles
To cover a range of formats, we evaluate on 125 failing inputs from 18 format families (Table 1): 74 text-based and 51 binary, of 16 to 224,151 bytes. Of these, 113 reproduce failures, and 12 are controls that must preserve a program’s behavior.
| Family | # | Size | Oracle | Word | Family | # | Size | Oracle | Word |
| Text-based inputs | Binary inputs | ||||||||
| c | 10 | 3.0 – 121.7 KiB | ICE, control | ␣ | asn1 | 6 | 500 B – 1.2 KiB | Magma fault | 10 B |
| crashjs | 10 | 644 B – 1.3 KiB | API exception | ␣ | binutils | 10 | 683 B – 21.0 KiB | signal, allocator | – |
| graphviz | 2 | 2.1 – 161.7 KiB | sanitizer | ␣ | ffmpeg | 10 | 468 B – 150.7 KiB | sanitizer | – |
| lua | 2 | 889 B – 1.2 KiB | assertion | ␣ | fonts | 8 | 200 B – 65.0 KiB | sanitizer | – |
| 5 | 4.4 – 15.2 KiB | Magma fault | ␣ | parquet | 4 | 66.8 – 110.3 KiB | sanitizer | – | |
| python | 5 | 212 B – 1.1 KiB | interpreter failure | ␣ | pcap | 3 | 73 – 205 B | sanitizer | – |
| smt | 10 | 2.4 – 218.9 KiB | assertion | ␣ | png | 2 | 218 – 708 B | Magma fault | – |
| sql | 10 | 51 – 538 B | error, wrong result | ␣ | tiff | 8 | 409 B – 9.4 KiB | Magma fault | – |
| xml | 10 | 3.7 – 107.0 KiB | differential | ␣ | All | 51 | |||
| yaml | 10 | 16 – 177 B | parse control | ␣ | |||||
| All | 74 |
Table 1. Benchmark families and neutral-word discovery outcomes
The inputs come from existing collections and bug reports. C, JavaScript, Python, and SMT-LIB inputs come from RedBench [18], CrashJS [28], GTR [12], and ddSMT [17]. Binutils, FFmpeg, font, Parquet, and libpcap inputs come from upstream reports and the OSS-Fuzz [32] and FuzzBench [25] archives, Graphviz and LuaJIT from upstream reports, SQL from upstream reports and SQLFlex [2], XML from [43], and ASN.1, PDF, PNG, and TIFF from Magma’s proofs of concept [11]. We keep at most ten inputs per family, spread across failure groups and sizes, stratifying JavaScript by project and C compiler failures by crashing source file, after dropping four near-duplicates: inputs of one failure group whose normalized compression distance [7] is at most 0.12.
Each oracle fixes its target versions and accepts a candidate that reproduces the recorded outcome. For most families, this is a signal, sanitizer report, assertion, diagnostic, or stack signature. For ASN.1, PDF, PNG, and TIFF, it is a recorded Magma [11] fault, and for SQL, an internal error or wrong result. For XML, BaseX must disagree with Saxon on a fixed query at affected revisions and agree at fixed ones. The controls must compile two Csmith [39] programs with sanitizers, run them, and keep their checksums, or keep the libyaml event streams of ten YAML test-suite inputs [37]. All reducers share each input’s oracle, which rejects timeouts. Inference sees only the oracle’s verdicts on raw bytes. Every original input passes its oracle before a run, and every output after.
Comparators
We compare AutoDiDact, with one set of parameters for every family, against three reducers: byte-level drdd, HDD, and C-Reduce. Where discovery abstains, it reduces exactly as drdd does, so RQ1 and RQ2 use the 75 inputs with a returned word, from 50 failure groups.
HDD. We run a pinned Picireny [13, 14] to a fixpoint. It implements HDD* with ddmin at each level, caching, pruning, and hoisting [34], over parse trees from grammars-v4 grammars [3] under ANTLR 4.13.2. A grammar exists for 50 inputs from eight families: C, JavaScript, Graphviz, Lua, Python, XML, and the SQLite and SMT-LIB 2 inputs of SQL and SMT. The C grammar alone is 18,234 bytes. We keep C’s and Python’s hidden tokens, which preserve directives and indentation, and patch Python’s synthetic token text so that unparsing preserves the source.
C-Reduce. We run a pinned C-Reduce [31] as creduce --not-c --n 1 --tidy on all 75 returned-word inputs, the C inputs included, so that every format gets the same passes, and let it run to its own fixpoint. This mode drops the Clang-based passes and keeps generic ones over lines, C tokens, and a fixed list of bracket pairs, plus integer reduction and peephole edits.
Measurement
Output size. We count non-whitespace bytes, since HDD spaces the tokens it unparses and C-Reduce reformats. For AutoDiDact against drdd, both of which only delete, this changes the mean size ratio by under one percent.
Calls. We count oracle executions. Every reducer’s oracle caches recent verdicts, and the counts exclude rechecks of inputs whose verdict is known: the checks of original and final inputs, C-Reduce’s initial sanity check, and Picire’s assertion at the start of each ddmin round.
Wall time. Measured on one core of an AMD Ryzen AI 9 HX PRO 370 under Fedora 44, it covers inference or reduction, oracle execution, and each stage’s startup and shutdown. HDD’s includes generating its parser. Since setup costs differ across tools, comparisons emphasize calls.
Results
We answer the three questions in order, charging inference in full throughout. Table 3 summarizes the comparisons of RQ1 and RQ2.
| Reducer | All 50 inputs: Size | All 50 inputs: Smaller/larger | All 50 inputs: Calls | All 50 inputs: Reduction calls | Without XML: Size | Without XML: Calls |
| AutoDiDact | 0.10 | 49/0 | 0.37 | 0.15 | 0.18 | 0.51 |
| C-Reduce (--not-c) | 0.19 | 43/7 | 1.06 | – | 0.15 | 0.94 |
| HDD (Picireny) | 0.11 | 47/3 | 0.10 | – | 0.21 | 0.20 |
Table 3. Reducers relative to drdd. On HDD’s 50 inputs, AutoDiDact’s outputs are 90% smaller than drdd’s with 63% fewer calls, 0.96× HDD’s at 3.85× the calls, and smaller than C-Reduce’s with 65% fewer calls
RQ1: Comparison with Byte-Level Delta Debugging
We compare AutoDiDact with byte-level drdd on the 75 inputs with a returned word, charging all inference to AutoDiDact. Against drdd, AutoDiDact returns outputs 83% smaller with 37% fewer calls on geometric mean, inference included. Its outputs are smaller on 60 of 75 inputs, equal on 14, and larger on one, and it uses fewer calls on 36. These results include AutoDiDact’s final shrinking pass, which reduces 55 of the 75 laminar outputs further, by 16% on geometric mean, for 11% more calls. Table 2 gives each input’s outputs, calls, and time, and Table D.1 itemizes AutoDiDact’s by stage.
Input size. The savings grow with input size (Figure 3). On the 26 inputs of at least 10 KiB, outputs are 98% smaller and calls 87% fewer, with 23 outputs smaller and 22 runs cheaper. Between 1 and 10 KiB, outputs are 69% smaller for 7% fewer calls. Below 1 KiB, outputs are 30% smaller, and calls rise 1.79×, with fewer calls on 5 of 34 inputs. In wall time, AutoDiDact takes 0.25× drdd’s time at 10 KiB and above and 0.89× overall, and longer on smaller inputs.

Figure 3. AutoDiDact’s advantage over drdd grows with input size: points fall further below the diagonal as drdd’s outputs and calls grow. On the 75 returned-word inputs, AutoDiDact’s output is smaller on 60 and larger on one. It makes fewer calls on 22 of the 26 inputs of at least 10 KiB, but on only 5 of the 34 below 1 KiB. Left: output size in non-whitespace bytes. Right: calls, including all inference. Axes are logarithmic. Points below the dashed diagonal, where the two are equal, favor AutoDiDact, and colors and marks distinguish families.
1-minimality over atoms. Laminar reduction’s output is 1-minimal over nodes, and drdd’s over atoms. Running drdd’s closing atom scan on AutoDiDact’s output makes it 1-minimal over atoms too: the scan shrinks 28 of 75 outputs, leaves outputs 0.17× drdd’s on geometric mean, and adds 11% to the calls, which stay 30% fewer than drdd’s.
| Case | Input | AutoDiDact Output | AutoDiDact Calls | AutoDiDact Time | drdd Output | drdd Calls | drdd Time | HDD Output | HDD Calls | HDD Time | C-Reduce Output | C-Reduce Calls | C-Reduce Time |
| asn1 | |||||||||||||
| asn1-aah055-nested | 580 | 112 | 623 | 33 s | 164 | 455 | 17 s | – | – | – | 579 | 3,280 | 4 m |
| c | |||||||||||||
| 02 | 3,623 | 457 | 3,032 | 7 m | 824 | 2,679 | 4 m | 481 | 5,219 | 24 m | 399 | 13,856 | 23 m |
| 10 | 3,071 | 281 | 2,126 | 4 m | 528 | 1,859 | 3 m | 277 | 1,515 | 3 m | 224 | 4,319 | 7 m |
| tree-ssa-structalias_c_4773_96K | 97,658 | 151 | 3,023 | 3 m | 45,061 | 232,803 | 2.0 h | 182 | 1,902 | 3 m | 132 | 8,174 | 3 m |
| tree-vect-transform_c_6496_55K | 55,923 | 114 | 5,658 | 4 m | 13,940 | 146,979 | 1.6 h | 111 | 7,046 | 11 m | 98 | 5,993 | 3 m |
| fold-const_c_8943_23K | 23,171 | 101 | 2,447 | 74 s | 9,620 | 42,493 | 12 m | 152 | 1,178 | 2 m | 126 | 5,791 | 2 m |
| recog_c_1990_63K | 63,509 | 138 | 2,533 | 2 m | 31,646 | 156,700 | 61 m | 107 | 513 | 78 s | 65 | 2,795 | 70 s |
| simplify-rtx_c_4922_43K | 43,720 | 135 | 3,029 | 91 s | 17,308 | 66,093 | 25 m | 146 | 1,116 | 2 m | 76 | 4,586 | 2 m |
| gimple_c_2343_122K | 124,593 | 142 | 10,302 | 13 m | 31,151 | 284,208 | 3.2 h | 194 | 14,342 | 42 m | 91 | 12,537 | 8 m |
| emit-rtl_c_1950_75K | 76,263 | 155 | 2,690 | 3 m | 35,434 | 188,661 | 1.7 h | 185 | 2,134 | 6 m | 135 | 6,507 | 3 m |
| ira-emit_c_371_17K | 16,424 | 199 | 3,110 | 77 s | 8,914 | 38,223 | 11 m | 315 | 3,467 | 8 m | 229 | 15,364 | 6 m |
| crashjs | |||||||||||||
| 7 | 1,012 | 159 | 1,782 | 5 m | 333 | 1,966 | 6 m | 126 | 252 | 2 m | 127 | 2,016 | 6 m |
| 10 | 830 | 113 | 1,441 | 5 m | 332 | 2,246 | 7 m | 151 | 363 | 2 m | 134 | 1,524 | 5 m |
| commander-4 | 778 | 166 | 1,434 | 4 m | 313 | 1,062 | 3 m | 249 | 757 | 4 m | 208 | 5,163 | 15 m |
| commander-31 | 1,055 | 156 | 1,371 | 4 m | 297 | 1,185 | 3 m | 209 | 394 | 2 m | 184 | 3,473 | 10 m |
| javascript-algorithms-5 | 745 | 220 | 1,535 | 5 m | 497 | 1,637 | 5 m | 354 | 602 | 3 m | 240 | 2,690 | 8 m |
| javascript-algorithms-14 | 814 | 252 | 1,233 | 4 m | 331 | 1,045 | 4 m | 204 | 313 | 2 m | 194 | 1,897 | 6 m |
| moment-1 | 800 | 181 | 1,521 | 9 m | 434 | 1,694 | 11 m | 130 | 405 | 5 m | 144 | 1,943 | 7 m |
| moment-17 | 1,340 | 188 | 1,768 | 10 m | 483 | 2,000 | 12 m | 222 | 707 | 7 m | 207 | 2,267 | 8 m |
| express-1 | 644 | 98 | 1,182 | 4 m | 210 | 1,185 | 4 m | 122 | 186 | 87 s | 107 | 1,888 | 6 m |
| express-48 | 903 | 117 | 1,336 | 4 m | 181 | 904 | 3 m | 220 | 281 | 2 m | 212 | 2,872 | 9 m |
| graphviz | |||||||||||||
| issue-1436 | 165,583 | 2,270 | 57,940 | 3.2 h | 12,949 | 137,314 | 4.2 h | 1,614 | 5,512 | 16 m | 51 | 6,781 | 10 m |
| issue-2723 | 2,141 | 90 | 1,011 | 47 s | 257 | 1,461 | 55 s | 89 | 722 | 2 m | 85 | 2,048 | 71 s |
| lua | |||||||||||||
| luajit-913 | 1,248 | 72 | 1,325 | 52 s | 320 | 1,934 | 28 s | 114 | 308 | 59 s | 58 | 1,789 | 49 s |
| luajit-1116 | 889 | 377 | 2,385 | 58 s | 377 | 1,991 | 42 s | 357 | 3,529 | 8 m | 389 | 10,087 | 3 m |
| pdf-fuzzer-aah052 | 15,421 | 118 | 1,419 | 2 m | 118 | 688 | 33 s | – | – | – | 113 | 3,053 | 2 m |
| pdf-fuzzer-jch207 | 15,505 | 7 | 672 | 29 s | 7 | 111 | 3.5 s | – | – | – | 115 | 246 | 15 s |
| pdfimages-jch207-kw6 | 4,543 | 3 | 1,107 | 24 s | 3 | 63 | 1.1 s | – | – | – | 3 | 541 | 20 s |
| pdftoppm-aah052 | 15,495 | 139 | 1,576 | 86 s | 120 | 701 | 25 s | – | – | – | 111 | 2,702 | 2 m |
| pdftoppm-jch207 | 15,532 | 794 | 4,733 | 2 m | 799 | 3,929 | 2 m | – | – | – | 3 | 2,794 | 2 m |
| python | |||||||||||||
| ackermann | 483 | 123 | 1,113 | 2 m | 216 | 1,073 | 86 s | 142 | 1,117 | 5 m | 78 | 2,784 | 4 m |
| alloc | 1,125 | 304 | 2,373 | 3 m | 466 | 1,856 | 2 m | 426 | 2,124 | 7 m | 220 | 7,729 | 10 m |
| dict | 265 | 135 | 1,232 | 90 s | 148 | 765 | 54 s | 150 | 1,087 | 4 m | 92 | 3,476 | 5 m |
| rmorеf | 383 | 170 | 1,052 | 83 s | 211 | 935 | 66 s | 225 | 1,014 | 4 m | 182 | 5,328 | 7 m |
| recursion | 212 | 59 | 815 | 64 s | 113 | 484 | 34 s | 74 | 461 | 2 m | 62 | 1,314 | 2 m |
| smt | |||||||||||||
| btor2-bug-16966-2630 | 2,435 | 862 | 8,632 | 44 s | 1,991 | 7,914 | 29 s | – | – | – | 719 | 37,289 | 11 m |
| btor2-bug-21435-401 | 3,546 | 1,058 | 9,564 | 51 s | 2,887 | 11,445 | 44 s | – | – | – | 1,185 | 62,063 | 18 m |
| btor2-bug-16965-103 | 9,773 | 1,495 | 31,307 | 3 m | 7,591 | 38,428 | 3 m | – | – | – | 957 | 94,137 | 29 m |
| btor2-bug-19025-698 | 63,795 | 2,772 | 185,324 | 56 m | 2,001 | 28,101 | 54 m | – | – | – | 1,925 | 491,145 | 53.3 h |
| btor4-bug-29933-6674 | 95,337 | 1,364 | 30,525 | 7 m | 11,027 | 78,179 | 7 m | – | – | – | 655 | 92,026 | 26 m |
| btor4-bug-1428-13899 | 162,928 | 712 | 144,595 | 67 m | 61,394 | 444,404 | 1.6 h | – | – | – | 407 | 55,025 | 1.7 h |
| btor4-bug-29800-10218 | 224,151 | 708 | 97,583 | 43 m | 32,617 | 158,747 | 23 m | – | – | – | 449 | 170,158 | 58 m |
| smlib384a04 | 43,696 | 172 | 2,097 | 3 m | 4,723 | 17,826 | 16 m | 223 | 945 | 3 m | 157 | 8,742 | 8 m |
| smlib46f14a | 43,323 | 172 | 2,126 | 3 m | 3,943 | 14,513 | 13 m | 223 | 945 | 3 m | 157 | 8,742 | 8 m |
| smlibf957ea | 43,937 | 151 | 1,841 | 3 m | 3,556 | 11,455 | 9 m | 234 | 834 | 3 m | 157 | 8,763 | 8 m |
| sql | |||||||||||||
| postgresql-18398 | 277 | 126 | 797 | 21 s | 218 | 751 | 18 s | – | – | – | 101 | 1,866 | 68 s |
| mysql-112460 | 538 | 208 | 1,486 | 2 m | 368 | 1,333 | 64 s | – | – | – | 197 | 5,291 | 5 m |
| sqlite-b17914e575 | 503 | 233 | 2,300 | 32 s | 375 | 1,164 | 16 s | 210 | 846 | 18 s | 177 | 5,689 | 3 m |
| sqlflex-sqlite-79 | 128 | 64 | 579 | 7.9 s | 101 | 310 | 4.1 s | 59 | 110 | 5.3 s | 35 | 786 | 24 s |
| sqlflex-sqlite-165 | 163 | 38 | 504 | 9.9 s | 135 | 387 | 5.2 s | 41 | 61 | 4.5 s | 35 | 824 | 25 s |
| sqlflex-sqlite-256 | 104 | 69 | 554 | 7.7 s | 90 | 218 | 3.0 s | 45 | 126 | 5.8 s | 41 | 791 | 25 s |
| sqlflex-sqlite-622 | 53 | 36 | 432 | 9.5 s | 42 | 119 | 1.6 s | 39 | 58 | 4.4 s | 35 | 422 | 15 s |
| sqlflex-sqlite-686 | 179 | 58 | 640 | 8.7 s | 108 | 417 | 5.6 s | 63 | 112 | 5.4 s | 38 | 483 | 17 s |
| sqlflex-sqlite-808 | 51 | 36 | 430 | 9.5 s | 42 | 117 | 1.6 s | 39 | 60 | 4.5 s | 30 | 420 | 15 s |
| sqlflex-sqlite-909 | 144 | 83 | 691 | 9.5 s | 106 | 419 | 5.6 s | 71 | 143 | 5.9 s | 78 | 1,534 | 43 s |
Table 2. Reduction results for the 75 inputs with a returned word. Sizes are in bytes, without whitespace. AutoDiDact’s calls and time include its inference, but the stage in Table D.1, and HDD’s and C-Reduce’s exclude validation queries. Dashes mark inputs a reducer did not run on. Each output and call count is shaded by its ratio to the smallest in its row: 1× 10× 100× 1000×.
| Case | Input | AutoDiDact Output | AutoDiDact Calls | AutoDiDact Time | drdd Output | drdd Calls | drdd Time | HDD Output | HDD Calls | HDD Time | C-Reduce Output | C-Reduce Calls | C-Reduce Time |
| xml | |||||||||||||
| 1.2 | 3,974 | 66 | 1,322 | 86 s | 1,079 | 4,110 | 78 s | 29 | 96 | 15 s | 78 | 7,633 | 3 m |
| 3.2 | 3,835 | 149 | 1,580 | 2 m | 1,035 | 3,896 | 75 s | 118 | 360 | 27 s | 1,416 | 8,976 | 3 m |
| 4.1 | 3,933 | 140 | 2,308 | 2 m | 811 | 3,491 | 81 s | 117 | 595 | 53 s | 214 | 12,071 | 4 m |
| 5.2 | 4,052 | 130 | 1,571 | 95 s | 1,004 | 3,919 | 78 s | 104 | 184 | 21 s | 141 | 10,737 | 3 m |
| 071d221-1 | 101,759 | 15 | 3,887 | 8 m | 19,966 | 108,336 | 54 m | 15 | 28 | 14 s | 28,960 | 142,284 | 77 m |
| 2d4ec80-1 | 108,560 | 63 | 4,221 | 3 m | 19,980 | 108,244 | 35 m | 47 | 80 | 16 s | 19,437 | 125,681 | 63 m |
| 327c8af-1 | 103,527 | 60 | 4,168 | 4 m | 19,576 | 106,657 | 41 m | 48 | 237 | 33 s | 4,426 | 137,325 | 54 m |
| 4c99b96-1 | 104,930 | 62 | 3,993 | 14 m | 20,000 | 108,471 | 57 m | 106 | 260 | 48 s | 27,401 | 131,567 | 82 m |
| 8ede045-1 | 106,398 | 60 | 4,065 | 3 m | 19,841 | 108,616 | 36 m | 45 | 232 | 32 s | 26,684 | 209,083 | 1.8 h |
| f053486-1 | 109,614 | 33 | 5,230 | 13 m | 19,381 | 107,771 | 76 m | 15 | 20 | 14 s | 28,116 | 135,287 | 1.7 h |
| yaml | |||||||||||||
| 9J7A | 16 | 11 | 138 | 0.3 s | 11 | 41 | 0.1 s | – | – | – | 11 | 42 | 2.1 s |
| 9FMG | 36 | 15 | 396 | 0.8 s | 15 | 87 | 0.2 s | – | – | – | 15 | 216 | 4.8 s |
| G4RS | 177 | 153 | 682 | 1.3 s | 153 | 407 | 0.8 s | – | – | – | 153 | 423 | 7.5 s |
| FBC9 | 148 | 130 | 702 | 1.4 s | 130 | 421 | 0.8 s | – | – | – | 130 | 1,029 | 16 s |
| 6JQW | 44 | 21 | 384 | 0.7 s | 21 | 49 | 0.1 s | – | – | – | 21 | 185 | 4.9 s |
| 96L6 | 63 | 46 | 415 | 0.8 s | 46 | 92 | 0.2 s | – | – | – | 46 | 232 | 5.2 s |
| 3GZX | 108 | 94 | 535 | 1.0 s | 94 | 272 | 0.5 s | – | – | – | 94 | 382 | 6.8 s |
| ZH7C | 16 | 10 | 136 | 0.3 s | 10 | 44 | 0.1 s | – | – | – | 10 | 114 | 3.4 s |
| 6FWR | 20 | 9 | 202 | 0.4 s | 9 | 41 | 0.1 s | – | – | – | 9 | 68 | 3.8 s |
| NAT4 | 86 | 35 | 582 | 1.1 s | 35 | 189 | 0.4 s | – | – | – | 35 | 506 | 11 s |
Table 2 (PDF p. 14). Reduction results for the 75 inputs with a returned word (continued)
Every row covers the same 50 inputs, the returned-word inputs with a grammar that HDD reduces, so the reducers also compare with each other through drdd. Ratios are geometric means of reducer / drdd. Ratios below 1 beat drdd. Size counts non-whitespace bytes. Smaller/larger counts inputs on which the reducer’s output is strictly smaller or larger than drdd’s. AutoDiDact’s calls include its inference, and its reduction calls leave it out. The tools’ calls exclude their validation queries.
Against drdd, AutoDiDact’s outputs are 83% smaller with 37% fewer calls, inference included, and 98% smaller with 87% fewer calls on inputs of at least 10 KiB. Below 1 KiB, it makes drdd’s calls.
RQ2: Inferred Structure against Format Knowledge
We compare AutoDiDact with HDD, which is given a grammar, and with C-Reduce’s language-agnostic mode, which has a fixed list of bracket pairs and a C lexer built in (Table 3 and Figure 4).

Figure 4. Without a grammar, AutoDiDact matches HDD’s output sizes at more calls, and it needs fewer calls than C-Reduce. Top: against HDD on its 50 inputs, size points straddle the diagonal, smaller on 28, and call points lie mostly above it, fewer on only 6. Bottom: against C-Reduce’s --not-c mode on its 75 inputs, call points lie mostly below the diagonal, fewer on 59, XML’s size points lie far below it, and the other families’ lie slightly above. Left: output size in non-whitespace bytes. Right: calls, AutoDiDact’s including all inference and HDD’s and C-Reduce’s excluding their validation queries. Axes are logarithmic. Points below the dashed diagonal, where the two are equal, favor AutoDiDact, and colors and marks distinguish families.
HDD. On the 50 inputs with a grammar, AutoDiDact’s outputs are HDD’s on geometric mean, smaller on 28 inputs, with a median ratio of 0.92. drdd’s outputs are HDD’s on the same inputs. AutoDiDact makes HDD’s calls, fewer on 6 inputs, and for reduction alone. On XML, AutoDiDact makes HDD’s calls for outputs as large. Without XML, its outputs are HDD’s at the calls, and without the 2 Python inputs that ANTLR parses only by recovering from syntax errors, at .
C-Reduce. Against C-Reduce’s --not-c mode, AutoDiDact uses 54% fewer calls, fewer on 59 of 75, or C-Reduce’s for reduction alone, and its outputs are 30% smaller on geometric mean. On XML, C-Reduce leaves most large inputs at tens of kilobytes, and AutoDiDact’s are C-Reduce’s. On other families, AutoDiDact’s outputs are C-Reduce’s at the calls. Overall, AutoDiDact’s are smaller on 26, equal on 11, and larger on 38, with a median ratio of 1.03.
Exact is the share of a family’s inferred tokens equal to a lexical token. Space, Quoted, and Other are the shares strictly inside a lexical token that is a whitespace run, a quoted literal, or any other token. Merged counts inferred tokens that join whole lexical tokens, and Straddling those that cross a lexical boundary with an end inside a lexical token. Recall is the share of the lexer’s token boundaries that the inferred tokens recover. The lexers are the grammars-v4 ANTLR 4 lexers, except Python’s tokenize module and PyYAML’s scanner. Lexical tokens keep every byte: hidden tokens such as comments stay, and skipped text becomes whitespace runs, line breaks, and single characters.
Whitespace. Counting whitespace, AutoDiDact’s outputs are C-Reduce’s and HDD’s.
AutoDiDact’s outputs are HDD’s at HDD’s calls, or excluding inference. Against C-Reduce’s language-agnostic mode, it makes 54% fewer calls, and its outputs are 30% smaller overall and C-Reduce’s outside XML.
RQ3: What Inference Recovers, at What Cost
We check the inferred tokens against real lexers and the pairs against each format’s delimiters, and give each learner’s cost.
The neutral word. Neutral-word discovery returns a single space on all 74 text-based inputs, across ten families. It abstains on 50 of the 51 binary inputs and returns a 10-byte sequence on one ASN.1 input. In a budget ablation on 37 inputs, every text input finds the space from 200 calls on, and 300 calls is the smallest budget that reproduces every main-run outcome.
Discovery spends nearly its whole budget whether it finds a word or abstains: 278 calls on text inputs and 284 on binary ones, taking 11.0 s, all on geometric mean. An abstention costs 284–289 calls before drdd, adding 2.9% to the pooled calls of the abstaining inputs and 18.2% per input on geometric mean, and outweighing the reduction itself on 12 small inputs, by up to 6.9×.
Tokens. On the 69 returned-word inputs from the nine families with a lexer (Table 4), 99.2% of inferred tokens lie within one lexical token, 45.9% matching one exactly, and they recover 97.7% of the lexer’s token boundaries. Of the inferred tokens strictly inside a lexical token, 42.9% lie in quoted literals, such as XML attribute values and Graphviz strings, and 16.3% in whitespace runs. Most of the rest lie in SMT symbols and XML text. 12,492 inferred tokens cross a lexical boundary, 99.6% of them joining whole lexical tokens and 99.7% in XML, Python, and YAML.
| Family | Inputs | Tokens Lexical | Tokens Inferred | Inferred tokens (%) Exact | Inferred tokens (%) Space | Inferred tokens (%) Quoted | Inferred tokens (%) Other | Crossing Merged | Crossing Straddling | Recall (%) |
| c | 10 | 287,893 | 320,842 | 88.3 | 9.3 | 0.6 | 1.8 | 13 | 0 | >99.9 |
| crashjs | 10 | 2,526 | 4,342 | 51.5 | 9.3 | 23.6 | 15.4 | 11 | 0 | 99.6 |
| graphviz | 2 | 25,489 | 131,760 | 13.2 | 39.1 | 46.3 | 1.4 | 3 | 10 | 99.9 |
| lua | 2 | 1,026 | 1,341 | 70.6 | 18.7 | 1.2 | 9.5 | 0 | 0 | 100.0 |
| python | 5 | 997 | 1,132 | 68.4 | 17.1 | 7.0 | 0.0 | 63 | 22 | 87.9 |
| smt | 10 | 332,269 | 480,203 | 61.5 | <0.1 | <0.1 | 38.5 | 0 | 1 | >99.9 |
| sql | 10 | 1,007 | 1,089 | 89.8 | 5.2 | 0.9 | 4.0 | 0 | 0 | 100.0 |
| xml | 10 | 147,295 | 546,158 | 14.9 | 8.5 | 50.6 | 23.7 | 12,334 | 9 | 87.4 |
| yaml | 10 | 191 | 214 | 54.7 | 4.7 | 23.4 | 5.1 | 24 | 2 | 80.7 |
| All | 69 | 798,693 | 1,487,081 | 45.9 | 8.7 | 22.9 | 21.7 | 12,448 | 44 | 97.7 |
Table 4. AutoDiDact’s inferred tokens against each family’s standard lexer, on the 69 returned-word inputs with a lexer. 99.2% of inferred tokens lie within one lexical token
Tokenization cost. Probing every internal gap alone makes up to one call per gap. With prediction and pooling, tokenization makes 52,943 calls for 2,102,563 gaps, 2.5% as many. This share falls with input size (Figure 6), from 38.9% below 1 KiB to 2.1% at 10 KiB and above. On the largest input, of 224,151 bytes, tokenization makes 454 calls, 0.2% of its gaps.

Figure 6. Tokenization’s calls per gap fall sharply with size, becoming negligible for large inputs. Calls fall from 38.9% of gaps below 1 KiB to 2.1% at 10 KiB and above. The plot gives these calls as a percentage of internal gaps on each of the 75 returned-word inputs, against input size, with a logistic fit in log size.
Prediction accuracy. On 20 inputs from 11 families, we also probed every gap alone with the same word (Table 5). In each family, we chose the inputs with the smallest and the largest share of
| Family | Case | Gaps | Predicted (%) | Calls | Exhaustive | Missed | Extra | Agreement (%) |
| asn1 | asn1...055-nested | 579 | 72.9 | 125 | 529 | 20 | 0 | 96.55 |
| c | 10 | 3,070 | 69.3 | 514 | 2,582 | 8 | 44 | 98.31 |
| c | simp...c_4922_43K | 43,719 | 98.8 | 453 | 36,099 | 0 | 40 | 99.91 |
| crashjs | java...orithms-14 | 813 | 65.7 | 247 | 750 | 3 | 0 | 99.63 |
| crashjs | express-1 | 643 | 34.1 | 341 | 579 | 0 | 0 | 100.00 |
| graphviz | issue-2723 | 2,140 | 91.2 | 120 | 1,753 | 1 | 47 | 97.76 |
| lua | luajit-913 | 1,247 | 58.5 | 444 | 1,124 | 1 | 2 | 99.76 |
| lua | luajit-1116 | 888 | 83.9 | 96 | 602 | 0 | 0 | 100.00 |
| pdf-fuzzer-jch207 | 15,504 | 99.1 | 12 | 14,885 | 0 | 80 | 99.48 | |
| pdfi...jch207-kw6 | 4,542 | 74.2 | 480 | 4,079 | 0 | 24 | 99.47 | |
| python | alloc | 1,124 | 55.2 | 350 | 791 | 1 | 8 | 99.20 |
| python | recursion | 211 | 28.9 | 109 | 144 | 0 | 12 | 94.31 |
| smt | btor...16966-2630 | 2,434 | 92.5 | 161 | 2,113 | 0 | 0 | 100.00 |
| smt | btor...-19025-698 | 63,794 | 99.5 | 265 | 56,083 | 0 | 0 | 100.00 |
| sql | mysql-112460 | 537 | 65.9 | 155 | 420 | 0 | 0 | 100.00 |
| sql | sqlf...sqlite-808 | 50 | 4.0 | 39 | 45 | 0 | 0 | 100.00 |
| xml | 4.1 | 3,932 | 72.4 | 533 | 3,731 | 0 | 0 | 100.00 |
| xml | 8ede045-1 | 106,397 | 93.3 | 3,095 | 97,250 | 12 | 1 | 99.99 |
| yaml | 6FWR | 19 | 5.3 | 17 | 14 | 0 | 0 | 100.00 |
| yaml | NAT4 | 85 | 58.8 | 23 | 57 | 0 | 0 | 100.00 |
| All | 251,728 | 94.4 | 7,579 | 223,630 | 46 | 258 | 99.88 |
Table 5. The default tokenizer against exhaustive probing on 20 selected inputs. It makes 3.4% of exhaustive probing’s calls and agrees with it at 99.88% of gaps.
Gaps counts internal offsets, and Predicted is the share of them whose verdict the default tokenizer predicted without a query. Calls and Exhaustive count the oracle calls of the default tokenizer and of probing every gap alone. Missed and Extra count the boundaries the default tokenizer omits or adds relative to exhaustive probing, over all gaps, and Agreement is the share of gaps on which both agree. The total pools gaps.
among those estimated to take under an hour to probe exhaustively. Where only one qualified, we used it. On these inputs, the default tokenizer makes 7,579 calls where exhaustive probing makes 223,630, 3.4% as many, and the two agree at 99.88% of the 251,728 gaps, from 94.3% to 100% per input, and on every gap of the SMT, SQL, and YAML inputs. Of the 304 disagreements, 298 are mispredictions, and the other six lie at gaps settled by pooling. Most are extra boundaries, which exhaustive probing rejects: in a C preprocessor directive, between the adjacent minus signs of C decrements, in Graphviz’s numeric identifiers, in Python indentation, and in PDF keywords.
Pairs. Pair learning admits 4,478 pairs on 59 of the 75 inputs, nearly all the format’s own delimiters. Apart from tags, 96 of the 109 pairs are brackets and quotes: parentheses on every C, Python, SMT, and SQL input, braces, brackets, and quotes in C, JavaScript, and Graphviz, and quotes in Lua and Python. On XML, affix families recover 4,369 start- and end-tag pairs. The conditional operator ? . . . : is admitted on six C inputs, and the seven others are not delimiters of the format. Where no pair is admitted, as on ASN.1, PDF, and most YAML inputs, reduction proceeds over flat tokens.
Pair learning is the cheapest stage. It makes 5,841 calls over all 75 inputs, a median of 71 per input and at most 255, and takes a median of 7.7 s per input.
Where the calls go. Inference makes 11.6% of AutoDiDact’s calls: tokenization 7.7%, discovery 3.1%, and pair learning 0.8%. Its share falls with input size (Figure 5), from 50.1% below 1 KiB to 8.9% at 10 KiB and above. Discovery’s and pair learning’s calls stay nearly constant, and tokenization’s grow roughly with the square root of input size.

Figure 5. Inference’s share of calls falls with input size, from 50.1% below 1 KiB to 8.9% at 10 KiB and above. Discovery and pair learning make nearly constant calls, and tokenization’s grow roughly with the square root of size. Reduction includes shrinking. The dashed line marks one call per gap.
Discovery finds a space on every text input. Inferred tokens recover 97.7% of the lexer’s token boundaries, and pair learning admits the formats’ brackets, quotes, and XML tags. Inference makes 11.6% of AutoDiDact’s calls, and 8.9% at 10 KiB and above.
Discussion
Competitive without a grammar. AutoDiDact receives only what drdd receives, a failing input and its oracle. From these alone, it returns outputs 83% smaller than drdd’s with 37% fewer calls, and this gain makes it competitive with grammar-aware reducers. On the inputs with a grammar, drdd’s outputs are HDD’s, and AutoDiDact’s are . Against C-Reduce, which builds in a C lexer and a list of bracket pairs, AutoDiDact makes 54% fewer calls for outputs 30% smaller. The inferred structure is small: for the GCC input of § 1, the word and pair tables take 99 bytes, against 18,234 bytes for the C grammar HDD needs. The price is calls against HDD, HDD’s in all and for reduction alone, so learning the structure accounts for most of the difference. The grammar helps HDD most on XML, whose tokens AutoDiDact must find by probing.
Tolerating errors. A grammar-aware reducer needs a grammar for the format and a parse of the input. HDD ran on only 50 of the 75 inputs, since no grammar was at hand for ASN.1, PDF, YAML, or the other SQL and SMT dialects, and ANTLR parsed 2 Python inputs only by recovering from syntax errors. Failing inputs are often malformed, and AutoDiDact parses nothing. A stray delimiter changes the span count by at most one (§ 3). AutoDiDact thus ran on all 75 returned-word inputs, including a binary ASN.1 input. In this respect, inferred structure goes beyond a grammar.
A minimizer for any fuzzer. Fuzzers minimize the crashing inputs they find at the byte level, as afl-tmin [40] and libFuzzer’s -minimize_crash [23] do, because they cannot assume the target’s input format. With inferred structure, a fuzzer can carry a general minimizer that works on any input. It needs nothing beyond the oracle the fuzzer already has, and where discovery abstains, it falls back to bytes after at most 300 calls.
Inferred against built-in knowledge. Because the structure comes from the oracle, it can also exceed a fixed description of the format: C-Reduce’s bracket list cannot pair XML tags, but affix families learn them. On the other families, C-Reduce also makes changes that no deletion can, through integer reduction and peephole edits, and inferred tokens could guide such edits as they guide shrinking. Ignoring whitespace in these comparisons is conservative, since counting it favors AutoDiDact (§ 7.2).
Why the savings over drdd grow with size. On large inputs, drdd stops at large 1-minimal outputs, such as the GCC input’s 45,061 bytes. Deleting or unwrapping whole spans gets past them. Below 1 KiB, drdd needs only 414 calls on geometric mean, not much more than discovery’s fixed budget, so inference rarely pays for itself. Inference queries also run on the whole input, so inference weighs more in wall time than in calls. With the closing atom scan, AutoDiDact’s calls stay below drdd’s, so the comparison also holds when both outputs are 1-minimal over atoms.
What the oracle reveals. Inference sees only the structure that the failure makes visible. Inferred tokens split a lexical token where the failure does not need it whole, as Section A.1 predicts: a whitespace run accepts the neutral word anywhere, and a comment may split into single bytes because insertions there do not matter. They cross lexical tokens where a lexer places boundaries that the neutral word cannot reach, such as after < in an XML tag or before indentation in Python and YAML. Coupling likewise follows the failure: the conditional operator ? . . . : is admitted because the compiler accepts its halves only together. A genuine pair may yield no witness when every paired edit destroys the failure. An abstention likewise leaves open whether useful structure exists. Such partial structure is safe to use, since the oracle checks every edit during reduction: it guides reduction without having to be a correct lexer or parser. Where the evidence is insufficient, discovery abstains at bounded cost, and reduction falls back to bytes.
Where inference is cheap. Tokenization’s share of calls falls with input size, consistent with larger inputs repeating more contexts. Pair learning would stay a small fraction of all calls even at ten times its cost, which leaves room for a learner that tests more hypotheses or other relations. The remaining overheads are discovery’s fixed budget, which small inputs cannot repay, and tokenizing inputs with little repetition, such as the large XML inputs. Both belong to the current learners, which are one way to infer the targets of § 4.1. Other learners could do better: a word learned on one input of a format could serve the next, and better prediction would cut tokenization further. How cheaply an oracle can reveal structure remains open.
Related Work
Delta debugging. ddmin [41] tests subsets and complements of supplied units, drdd [20] changes its restart schedule while keeping 1-minimality, and ProbDD [35] chooses deletions with a probabilistic model. Our inference supplies units and nesting to any such reducer.
Reduction with format knowledge. HDD [26] reduces a parse tree level by level, as Picire [13, 14] does for ANTLR grammars, with hoisting [34]. Perses [33] uses grammar rules for syntax-preserving deletions and replacements, GTR [12] learns tree transformations from a corpus, and T-Rec [36] reduces within tokens using a language’s lexical syntax. C-Reduce [31] deletes or unwraps brackets from a fixed list among other passes, and Shrink Ray [24] pairs generic passes with format-specific ones. Each obtains units and hierarchy from a grammar, a lexer, a corpus, or built-in knowledge. We obtain them from the failing input and its oracle.
LLM-assisted reduction. LPR [42] alternates a generic reducer with transformations that a large language model proposes, and Yang et al. [38] prompt a model to write a reducer for each failing input. Model queries add cost to every reduction, and the cost grows when a fuzzing campaign yields thousands of inputs. With AutoDiDact reducing them, a model’s effort can go to selecting which inputs to reduce and which failures to investigate.
Grammar inference. GLADE [6] generalizes seed inputs with membership queries, Arvada [19] and TreeVada [4] merge nodes of trees over example inputs, Kedavra [22] infers grammars incrementally, and Crucio [21] scales inference to C, confirming token boundaries by inserting a space after checking that the parser ignores spaces. V-Star [15] is closest to pair learning: it infers call and return tokens from nesting patterns and learns a visibly pushdown grammar. Our coupling tests share its coordinated edits and rejected controls without requiring a visibly pushdown language. These learners assume a parser oracle and positive examples and seek a grammar of the whole language. We have one failing input and a failure oracle, which tests failure preservation and may accept malformed inputs. We discover the separator, learn only the relations reduction uses, abstain when evidence is weak, and check every edit.
Threats to Validity
Internal validity. All reducers use the same oracle for each input, and original and final inputs are checked, though a shared symptom need not identify the same fault. One run per input and reducer cannot separate nondeterminism from the methods’ effects. Parameters are fixed across families but were chosen on these inputs, and the budget ablation covers selected inputs and one parameter.
External validity. The 125 inputs cover 18 families, at most ten per family, largely from existing reproducer collections, some already reduced. They are not independent samples of defects, and other inputs may behave differently. Every text input yielded a space and one binary input another word, so evidence for other words and for binary formats is limited. The comparisons cover one configuration each of HDD and C-Reduce, on cohorts set by discovery and the available grammars, and do not isolate the effects of nesting, hoisting, unwrapping, shrinking, and traversal order.
Construct validity. Agreement with a lexer depends on its conventions for hidden tokens and skipped text, and agreement with exhaustive probing measures fidelity to probing on inputs chosen for affordable probing. Coupling witnesses establish only the contrasts tested. Oracle calls have unequal costs, and wall times come from one machine without repeated trials, so we report both. Byte counts may differ from debugging effort, and ignoring whitespace discounts it in Python and YAML. Per-input results, medians, and win counts expose variation that geometric means hide.
Conclusion
The most widely used fuzzers, such as AFL [9, 40] and libFuzzer [23], know nothing of their targets’ input formats. Yet they must reduce what they find, from corpus seeds to crashing inputs, and their minimizers have so far worked on bytes. This paper removes that limit. A neutral word and delimiter pairs, inferred from an input and its oracle alone, give structured reduction without a grammar. Reduction over them returns outputs 83% smaller than byte-level drdd’s with 37% fewer calls, matches grammar-based HDD in output size, and uses 54% fewer calls than C-Reduce’s --not-c mode. Because AutoDiDACT parses nothing and checks every edit, it accepts whatever a fuzzer finds, malformed inputs included, with any property the fuzzer can check, from a crash to a seed’s coverage. Grammar-agnostic fuzzers can now carry a structure-aware minimizer, for smaller seeds that are cheaper to run and smaller crash inputs that are quicker to diagnose.
AI Use
We used Codex (OpenAI) and Claude Code (Anthropic) primarily to acquire and build benchmark targets, implement and validate oracle wrappers, and write experiment and analysis scripts, including table and figure generators. We also used them for localized implementation cleanup, documentation, debugging, and validation tests, to search for related literature, and to check the paper’s algorithms, arguments, and numerical claims against the implementation and saved results.
Data-Availability Statement
A replication package and prebuilt image are available at doi:10.5281/zenodo.24164465. The package contains the implementation source, benchmark inputs and oracles, experiment and analysis scripts, and saved results.
References
Structural Arguments
The following arguments support § 4.1; Sections B to D give reduction algorithms, inference details, and supplementary results.
Tokens under a Lexer
Let and let be the internal lexical boundaries. Assume that erases arbitrary copies of inserted at any subset of , while inserting either control, or , there is rejected. Erasure preserves , so every lexical boundary is selective and, when , is neutral with . By (1),
Exhaustive probing therefore refines the lexical partition; prediction and pooling need not. Erasure ensures composition at lexical boundaries, but not at extra boundaries within tokens, where insertions can interact.
Delimiter Pairs under a Parser
Assume that is matched for and the oracle rejects every unmatched input. The paired edits of (3), span deletion, and unwrapping preserve matchedness: for distinct delimiters, each replacement and the original span have equal opening and closing counts and no prefix with more closes than opens, preserving matchedness in the walk of (2). For symmetric delimiters, each edit changes the count by an even number. Each control instead changes the total delimiter parity and is rejected. Coupling therefore reduces to acceptance of a paired edit; matchedness alone does not ensure that acceptance.
Reduction Algorithms and Guarantees
Assume a deterministic Boolean oracle. Queries count requests before caching and hence also bound oracle executions.
Matching and Tree Construction
Stability. For fixed admitted pairs, let be the largest matching size. Deleting delimiter removes at most one pair from a largest matching; every matching of the shorter sequence is also valid before deletion. Hence . Insertion reverses this argument, so inserted or deleted delimiters change the size by at most . Admitting another pair enlarges the feasible set and cannot decrease . These bounds concern span counts, not identities.
Construction. Some largest matching contains all pairs made by the stack pass of Algorithm B.1. When it pairs adjacent unmatched delimiters, an optimal matching can add their pair if neither is used, or swap it for the existing pair if one is used. Pairing both elsewhere would cross unless a token serves both roles, so two-sided tokens are skipped; for a symmetric pair, the two partners can instead pair with each other. The pass is linear and complete on well-nested input without two-sided tokens. An interval program matches the remaining delimiters . Let be the largest matching size on , with for ; otherwise,
since is unpaired or paired with some , separating the inside and following intervals. Traceback skips on ties; otherwise it takes the least maximizing and recurses inside and after that pair.
Algorithm B.1 TREE: match delimiters into spans
Input: Tokens , admitted pairs
Output: The root of the span tree
A two-sided token both opens and closes pairs of and occurs in a nonsymmetric pair.
1: , and empty list matched pairs, unmatched delimiters
2: for each position whose token is a delimiter of , in order do
3: Append to
4: if ends in with , and neither nor is two-sided, then add to , and remove and from
5: Complete on using (B.1) and its traceback
6: Start a stack with a delimiterless root
7: for each token position , in order do
8: if opens a pair of then create and push a child of the top node
9: else if closes a pair of then close and pop the top node
10: else append to the top node’s items
11: return the root
Base Reducer
Algorithm B.2 gives drdd [20] with a closing-scan budget : laminar reduction uses per node, shrinking .
Algorithm B.2 drdd: chunk sweeps and closing scans
Input: Accepted unit sequence , oracle , closing-scan budget
Output: An accepted subsequence, 1-minimal over units if
1:
2: while do
3: Sweep(), and
4: repeat
5: Sweep(1)
6: until the sweep deletes nothing, or sweeps of size 1 have run
7: return
8: procedure Sweep()
9: Partition into chunks of units, the last possibly shorter
10: for to do
11: if then
Laminar Reduction
Promoted spans join the current level in Algorithm B.3 and are processed in their new positions.
Fixpoint. Each accepted edit removes a nonempty token, so at most traversals change an input of tokens. An unchanged traversal rejects every single-item deletion, permitted hoist, and unwrapping against the final input, proving local minimality despite . An early stop combines the unchanged prefix through stop with the suffix checked after the preceding traversal’s last change. Neither oracle monotonicity nor correct inferred structure is needed.
Query cost. With , drdd costs queries for items. A traversal processes each node once, including promoted nodes; their item lists total entries. Charge each hoist query to its offered descendant: only its nearest remaining ancestor of the same pair can offer it, and ancestors are processed first. Each descendant is thus offered at most once per traversal; each span also costs at most one unwrapping query. Each traversal costs , and at most changing traversals plus a final check cost .
Shrinking
Algorithm B.4 Shrinking: shorten each distinct token at all occurrences
Input: Tokens left by laminar reduction, oracle
Output: The shrunk tokens
for each distinct token with , in order of first occurrence do
fixed while reducing
Reduce ’s atoms by drdd with , testing each at all positions in the current input and keeping accepted edits
return without empty tokens
For initial distinct-token lengths , shrinking costs , since . Later token edits may invalidate an earlier token’s local fixpoint.
Inference Procedures
These subroutines complete Algorithms 1 to 3. Discovery’s budget counts executions, so cached verdicts cost no calls.
Neutral-Word Discovery
Candidate enumeration. CANDIDATES enumerates maximal repeats as internal intervals of a suffix array’s longest-common-prefix tree whose occurrences have at least two distinct preceding atoms. Children give distinct following atoms; input ends count as distinct markers. Prefix doubling takes comparisons, Kasai’s longest-common-prefix construction time, and merging preceding-atom sets smaller into larger insertions, without queries.
Runs and classes. Maximal consecutive copies of on either side of an offset form a run; its two adjacent atoms, or end markers, are its surroundings. Inserting at any copy boundary within a run gives the same input. A word’s class is .
Schedule. SCHEDULE visits distinct offsets in this order:
the starts of the leading candidate’s first and last occurrences;
both ends of the runs around each source word’s first and last occurrences, grouped by class, each class shuffled with seed 0, taking one offset per class in turn;
remaining internal offsets, shuffled, in class 0.
Observation. Rows accepting earn zero credit but enter the class mean; incomplete rows are discarded (Algorithm C.1).
Algorithm C.1 OBSERVE: collect controlled evidence
Input: , oracle , candidate words , control , scheduled offsets, call limit
Output: Complete observation rows
Before a query would exceed calls, return .
1: empty list 2: for each scheduled pair of class and offset do 3: 4: if then 5: Query for each in order; the accepted words 6: 7: for each distinct length in do 8: 9: 10: Append to 11: return
Scoring. Let be the candidate order, its number of families, and . For nonempty , let be the rows of class , the observed classes, and . Define
The keeps credit positive even when every family earns it; the rank penalty vanishes after all internal offsets have complete rows. For , crediting alone at one of two class-0 rows gives weights ; crediting it alongside one other family at the sole class-1 row gives . Then
classes weigh equally despite unequal samples. If offsets remain unobserved, ; later candidates pay a larger penalty.
Confirmation. SITES scans crediting rows in input order, retaining one offset per run and up to four distinct surroundings. With fewer than two surroundings, it adds further runs to reach two sites where possible. With two or three sites, REFINESITES probes at most two occurrences with new surroundings, in input order, appending accepted sites up to four, without controls. REUSETESTS takes the first five of these insertions at the sites of , in order:
one site: 2, 4, 8, 16, and 32 copies there;
two sites: two copies at both together, then two at each alone, then four at each alone;
three or four sites: one copy at each site of every triple, in lexicographic order of indices in , then two copies at each site alone, then four at each alone.
Two words need at most confirmation calls, within the 16-call reserve; unspent observation calls are also available.
Tokenization
Contexts. At offset , let be its atoms to the left and right, , and the share of classified offsets within atoms, excluding , that are boundaries. Bucket as none, at most a third, at most two thirds, fewer than all, and all. Estimate uses these 14 contexts, read down each column:
6. 11.
7. 12.
8. 13.
9. 14.
10.
Out-of-range atoms, unknown verdicts, and empty density neighborhoods use markers. includes predictions and tentative pooled boundaries as well as settled verdicts.
Estimate. records settled offsets whose th context had key at settlement, of them boundaries. For the keys at , write and compute
Each rate is smoothed toward its predecessor with weight two; an unseen context leaves it unchanged. Initialize , giving . On settling verdict , first update and recompute the context keys and estimates from the current , , and weights. Take the log-loss gradient step , then update in each of the 14 entries. Clip probabilities to before log-odds, and log-odds to before .
Information. Write . Under the estimates, predicting at or skips queries worth at most bits. A pool triggered by has estimated acceptance probability in , since the preceding product exceeds and each pooled estimate is at least . Its estimated yield is therefore at least bits.
Pooling. Under factorization (§ 4.3), a rejected pool contains a non-boundary. TestPool maintains such a set , splitting by doubt, . It queries the shortest proper prefix holding at least half the doubt, or all but the last offset if no proper prefix does. After an accepted prefix, the suffix still contains a non-boundary.
For estimates , the fourth offset triggers a query (product ). The shortest prefix holding half the doubt comprises the first three offsets. Rejecting the pool and accepting that prefix classifies three boundaries and one non-boundary in two queries.
Query bound. Since each pooled estimate is below and , pools hold at most 35 offsets. Each outer iteration settles at least one offset using one pool test and at most 34 split queries. Individual probes also settle an offset, giving at most queries for .
Algorithm C.2 TestPool: test the pool
Input: Pool with estimates , verdict map
while is nonempty do
, and empty
if accepts with inserted at every offset of then
for each
else
while do
Split by half the doubt, as above
if accepts with at every offset of then
for each , and
else
Prepend to , and
for the offset left in
Pair Learning
Hypotheses. Enumerate single pairs by occurrence-count classes . For families, split each non-blank token at every inner position and group prefixes, or suffixes, sharing at least two nonempty names.
Candidate intervals. Assign each position to its innermost strictly enclosing admitted interval, or to the outside region; an interval’s own delimiters belong to its surrounding region. Symmetric pairing also starts at the second occurrence when a region has an odd count, allowing a stray occurrence, and drops intervals strictly nested in one with an earlier start.
Balance prior. For openings, closings, and unmatched closings, a uniform shuffle leaves more than closings unmatched exactly when its walk ( per opening, per closing) reaches . Reflecting up to the first visit there gives a bijection to shuffles with openings and closings, of which there are . Hence
with out-of-range binomial coefficients zero. Families sum over names, using their counts and unmatched closings on the shared stack. This sum is heuristic: one name’s stray delimiters can block another’s matches.
Parity prior. For a symmetric hypothesis occurring in regions, of them odd, independent region parities with probability give
The cap of § 4.4 equals .
Ranking bounds. Scoring scans occurrences, so visits count-class pairs and families by decreasing upper bounds on their priors:
For counts , the smallest feasible is with openings, or with openings; either gives . Since decreases with , this bounds both orientations. The family bound follows from the cap and . A min-heap retains the best hypotheses, replacing only on strict improvement; stop when the next bound falls below its minimum. Final ties follow discovery order. Symmetric hypotheses are all scored.
Sensitivity. Sensitive duplicates each distinct delimiter of one representative pair at its occurrence nearest a multi-atom token, measuring distance in token positions. Ties, or absence of multi-atom tokens, select the earliest occurrence. Multi-atom tokens mark restrictive surroundings. Tests are individual and may use unrelated occurrences.
Confirmation. Coupled queries controls only after a paired edit is accepted, the second only if the first is rejected. In the empty-or-delete row, deletion is tried only if emptying is rejected. This costs at most three queries per row, four for empty-or-delete, and ten per interval. Test’s context is an interval’s tokens plus one on either side. Spread samples fractions 0, 1/2, 1/4, 3/4, . . . of the list length, the van der Corput binary-digit-reversal sequence, rounding down and stepping cyclically past used indices.
Algorithm C.3 Test: seek two coupling witnesses
Input: Compatible candidate intervals , patience
Output: true after two coupling witnesses, false otherwise
sorted by (length, position), retaining the first interval per context
Reorder with Spread(), and
for do
if Coupled() then
if then return true
if and then return false
return false
Query bound. Each of at most hypotheses uses at most two sensitivity queries and coupling queries. The cap gives , hence at most queries.
Supplementary Evaluation
Table Table D.1 decomposes the costs in Table 2; Tables D.2 and D.3 detail the budget sweep and exceptional admissions.
| Case | Input | Discovery Calls | Discovery Time | Tokenization Calls | Tokenization Time | Pair learning Calls | Pair learning Time | Laminar reduction Output | Laminar reduction Calls | Laminar reduction Time | Shrinking Output | Shrinking Calls | Shrinking Time |
| asn1 | |||||||||||||
| asn1-aah055-nested | 580 | 287 | 17 s | 125 | 8.4 s | 1 | 0.1 s | 116 | 26 | 1.6 s | 112 | 184 | 6.3 s |
| c | |||||||||||||
| 02 | 3,623 | 288 | 37 s | 606 | 81 s | 171 | 31 s | 570 | 1,701 | 4 m | 457 | 266 | 28 s |
| 10 | 3,071 | 290 | 33 s | 514 | 66 s | 194 | 32 s | 369 | 902 | 90 s | 281 | 226 | 25 s |
| tree-ssa-structalias_c_4773_96K | 97,658 | 289 | 22 s | 733 | 75 s | 101 | 11 s | 213 | 1,771 | 40 s | 151 | 129 | 1.5 s |
| tree-vect-transform_c_6496_55K | 55,923 | 288 | 12 s | 1,072 | 56 s | 117 | 6.2 s | 160 | 4,090 | 3 m | 114 | 91 | 1.7 s |
| fold-const_c_8943_23K | 23,171 | 289 | 12 s | 494 | 26 s | 119 | 5.3 s | 184 | 1,428 | 30 s | 101 | 117 | 1.2 s |
| recog_c_1990_63K | 63,509 | 289 | 13 s | 518 | 35 s | 82 | 5.9 s | 214 | 1,504 | 45 s | 138 | 140 | 1.5 s |
| simplify-rtx_c_4922_43K | 43,720 | 289 | 8.2 s | 453 | 19 s | 113 | 4.6 s | 214 | 2,034 | 58 s | 135 | 140 | 1.6 s |
| gimple_c_2343_122K | 124,593 | 288 | 24 s | 988 | 2 m | 83 | 9.2 s | 208 | 8,795 | 11 m | 142 | 148 | 4.7 s |
| emit-rtl_c_1950_75K | 76,263 | 289 | 16 s | 716 | 72 s | 93 | 9.9 s | 235 | 1,450 | 66 s | 155 | 142 | 2.0 s |
| ira-emit_c_371_17K | 16,424 | 289 | 8.4 s | 455 | 17 s | 118 | 4.4 s | 350 | 2,097 | 45 s | 199 | 151 | 2.5 s |
| crashjs | |||||||||||||
| 7 | 1,012 | 289 | 68 s | 332 | 61 s | 163 | 28 s | 230 | 830 | 2 m | 159 | 168 | 28 s |
| 10 | 830 | 289 | 63 s | 314 | 59 s | 144 | 26 s | 162 | 554 | 2 m | 113 | 140 | 25 s |
| commander-4 | 778 | 289 | 45 s | 371 | 62 s | 78 | 12 s | 244 | 524 | 81 s | 166 | 172 | 26 s |
| commander-31 | 1,055 | 289 | 46 s | 473 | 79 s | 111 | 17 s | 226 | 338 | 50 s | 156 | 160 | 25 s |
| javascript-algorithms-5 | 745 | 289 | 59 s | 342 | 61 s | 84 | 14 s | 327 | 552 | 92 s | 220 | 268 | 45 s |
| javascript-algorithms-14 | 814 | 289 | 58 s | 247 | 41 s | 71 | 12 s | 294 | 379 | 64 s | 252 | 247 | 91 s |
| moment-1 | 800 | 289 | 2 m | 325 | 2 m | 105 | 29 s | 187 | 653 | 4 m | 181 | 149 | 38 s |
| moment-17 | 1,340 | 289 | 2 m | 457 | 2 m | 136 | 46 s | 221 | 652 | 4 m | 188 | 234 | 62 s |
| express-1 | 644 | 289 | 64 s | 341 | 67 s | 69 | 14 s | 102 | 346 | 62 s | 98 | 137 | 24 s |
| express-48 | 903 | 289 | 60 s | 425 | 79 s | 149 | 32 s | 127 | 344 | 67 s | 117 | 129 | 23 s |
| graphviz | |||||||||||||
| issue-1436 | 165,583 | 289 | 98 s | 11,297 | 2.1 h | 158 | 80 s | 2,473 | 45,263 | 62 m | 2,270 | 933 | 35 s |
| issue-2723 | 2,141 | 289 | 16 s | 120 | 6.5 s | 119 | 5.9 s | 90 | 468 | 19 s | 90 | 15 | 0.3 s |
| lua | |||||||||||||
| luajit-913 | 1,248 | 289 | 15 s | 444 | 19 s | 151 | 4.3 s | 130 | 380 | 12 s | 72 | 61 | 1.7 s |
| luajit-1116 | 889 | 288 | 13 s | 96 | 4.1 s | 98 | 0.9 s | 391 | 1,841 | 39 s | 377 | 62 | 1.1 s |
| pdf-fuzzer-aah052 | 15,421 | 289 | 32 s | 226 | 24 s | 195 | 30 s | 118 | 679 | 31 s | 118 | 30 | 1.0 s |
| pdf-fuzzer-jch207 | 15,505 | 289 | 11 s | 12 | 1.4 s | 255 | 13 s | 7 | 116 | 3.6 s | 7 | 0 | 0.0 s |
| pdfimages-jch207-kw6 | 4,543 | 291 | 5.8 s | 480 | 10 s | 230 | 5.8 s | 3 | 106 | 2.0 s | 3 | 0 | 0.0 s |
| pdftoppm-aah052 | 15,495 | 291 | 15 s | 344 | 25 s | 192 | 22 s | 143 | 679 | 23 s | 139 | 70 | 1.7 s |
| pdftoppm-jch207 | 15,532 | 289 | 11 s | 313 | 14 s | 226 | 9.8 s | 806 | 816 | 19 s | 794 | 3,089 | 90 s |
| python | |||||||||||||
| ackermann | 483 | 288 | 30 s | 174 | 24 s | 35 | 3.3 s | 151 | 498 | 42 s | 123 | 118 | 8.7 s |
| alloc | 1,125 | 288 | 23 s | 350 | 32 s | 144 | 11 s | 400 | 1,268 | 97 s | 304 | 323 | 23 s |
| dict | 265 | 288 | 21 s | 129 | 11 s | 89 | 6.5 s | 136 | 610 | 44 s | 135 | 116 | 8.0 s |
| rmroref | 383 | 288 | 24 s | 194 | 17 s | 43 | 3.4 s | 205 | 354 | 26 s | 170 | 173 | 12 s |
| recursion | 212 | 288 | 23 s | 109 | 9.4 s | 63 | 5.2 s | 62 | 290 | 22 s | 59 | 65 | 4.7 s |
| smt | |||||||||||||
| btor2-bug-16966-2630 | 2,435 | 289 | 1.0 s | 161 | 0.8 s | 33 | 0.2 s | 1,096 | 7,882 | 41 s | 862 | 267 | 1.0 s |
| btor2-bug-21435-401 | 3,546 | 289 | 1.1 s | 190 | 1.2 s | 40 | 0.3 s | 314 | 8,688 | 47 s | 1,058 | 357 | 1.4 s |
| btor2-bug-16965-103 | 9,773 | 289 | 1.2 s | 220 | 1.9 s | 16 | 0.2 s | 1,853 | 30,317 | 3 m | 1,495 | 465 | 2.0 s |
| btor2-bug-19025-698 | 63,795 | 289 | 4.1 s | 265 | 9.6 s | 15 | 5.9 s | 3,689 | 183,766 | 55 m | 2,772 | 987 | 6.2 s |
| btor4-bug-29933-6674 | 95,337 | 289 | 3.3 s | 445 | 9.5 s | 142 | 28 s | 1,608 | 29,211 | 7 m | 1,364 | 438 | 1.7 s |
| btor4-bug-1428-13899 | 162,928 | 289 | 5.8 s | 270 | 13 s | 11 | 64 s | 844 | 143,766 | 66 m | 712 | 259 | 1.0 s |
| btor4-bug-29800-10218 | 224,151 | 289 | 8.0 s | 454 | 21 s | 118 | 3 m | 894 | 96,398 | 39 m | 708 | 324 | 1.2 s |
| smtlib384a04c00 | 43,696 | 289 | 15 s | 657 | 78 s | 51 | 7.7 s | 338 | 99 | 55 s | 172 | 104 | 6.0 s |
| smtlib46f14a | 43,323 | 289 | 14 s | 659 | 78 s | 78 | 12 s | 338 | 996 | 54 s | 172 | 104 | 6.0 s |
| smtlib957ea | 43,937 | 289 | 14 s | 679 | 80 s | 78 | 12 s | 288 | 701 | 40 s | 151 | 94 | 5.3 s |
| sql | |||||||||||||
| postgresql-18398 | 277 | 289 | 7.2 s | 98 | 2.9 s | 48 | 1.7 s | 192 | 251 | 6.4 s | 126 | 111 | 3.2 s |
| mysql-112460 | 538 | 288 | 21 s | 155 | 15 s | 101 | 14 s | 257 | 745 | 39 s | 208 | 197 | 18 s |
| sqlite-b794e4595 | 503 | 288 | 4.0 s | 150 | 2.1 s | 85 | 1.2 s | 247 | 1,625 | 23 s | 233 | 151 | 2.1 s |
| sqlflex-sqlite-79 | 128 | 289 | 3.8 s | 74 | 1.0 s | 25 | 0.4 s | 71 | 118 | 1.6 s | 64 | 73 | 1.0 s |
| sqlflex-sqlite-165 | 163 | 288 | 3.8 s | 74 | 1.0 s | 20 | 0.3 s | 39 | 81 | 1.1 s | 38 | 40 | 0.6 s |
Table D.1. Per-input stage costs on the 75 returned-word inputs. Sizes are in bytes; outputs exclude whitespace. Calls and times are per stage; Table 2 sums all five.
| Case | Input | Discovery Calls | Discovery Time | Tokenization Calls | Tokenization Time | Pair learning Calls | Pair learning Time | Pair learning Output | Laminar reduction Calls | Laminar reduction Time | Laminar reduction Output | Shrinking Calls | Shrinking Time |
| sqlflex-sqlite-256 | 104 | 289 | 3.9 s | 59 | 0.8 s | 20 | 0.3 s | 69 | 113 | 1.6 s | 69 | 73 | 1.1 s |
| sqlflex-sqlite-622 | 53 | 289 | 3.8 s | 35 | 0.5 s | 11 | 0.2 s | 37 | 62 | 0.9 s | 36 | 35 | 0.5 s |
| sqlflex-sqlite-686 | 179 | 289 | 3.8 s | 95 | 1.3 s | 14 | 0.2 s | 58 | 179 | 2.4 s | 58 | 63 | 0.9 s |
| sqlflex-sqlite-808 | 51 | 289 | 3.8 s | 39 | 0.6 s | 9 | 0.2 s | 37 | 58 | 0.8 s | 36 | 35 | 0.5 s |
| sqlflex-sqlite-909 | 144 | 289 | 3.9 s | 83 | 1.2 s | 24 | 0.4 s | 84 | 221 | 3.0 s | 83 | 74 | 1.0 s |
| 1.2 | 3,974 | 289 | 22 s | 505 | 30 s | 77 | 11 s | 66 | 371 | 19 s | 66 | 80 | 4.1 s |
| 3.2 | 3,835 | 289 | 23 s | 505 | 35 s | 64 | 11 s | 157 | 545 | 32 s | 149 | 177 | 5.9 s |
| 4.1 | 3,933 | 289 | 23 s | 533 | 33 s | 64 | 11 s | 150 | 1,292 | 58 s | 140 | 130 | 5.9 s |
| 5.2 | 4,052 | 289 | 20 s | 501 | 30 s | 82 | 12 s | 131 | 540 | 27 s | 130 | 159 | 6.9 s |
| 071d221-1 | 101,759 | 289 | 42 s | 3,452 | 6 m | 29 | 16 s | 15 | 106 | 14 s | 15 | 11 | 4.1 s |
| 2d4ec80-1 | 108,560 | 289 | 19 s | 3,198 | 99 s | 32 | 10 s | 63 | 663 | 39 s | 63 | 39 | 3.6 s |
| 327c8af-1 | 103,527 | 289 | 27 s | 3,282 | 3 m | 40 | 15 s | 60 | 513 | 36 s | 60 | 44 | 4.4 s |
| 4c99b96-1 | 104,930 | 289 | 84 s | 3,352 | 11 m | 35 | 23 s | 66 | 252 | 33 s | 62 | 65 | 4.1 s |
| 8ede045-1 | 106,398 | 288 | 24 s | 3,095 | 2 m | 37 | 13 s | 70 | 602 | 37 s | 60 | 43 | 5.5 s |
| f053486-1 | 109,614 | 289 | 74 s | 4,727 | 12 m | 24 | 15 s | 33 | 157 | 18 s | 33 | 33 | 4.3 s |
| 9J7A | 16 | 85 | 0.2 s | 13 | 0.0 s | 2 | 0.0 s | 11 | 30 | 0.1 s | 11 | 8 | 0.0 s |
| 9FMG | 36 | 288 | 0.5 s | 17 | 0.0 s | 10 | 0.0 s | 15 | 69 | 0.1 s | 15 | 12 | 0.0 s |
| G4RS | 177 | 290 | 0.6 s | 60 | 0.1 s | 9 | 0.0 s | 153 | 35 | 0.1 s | 153 | 288 | 0.6 s |
| FBC9 | 148 | 288 | 0.5 s | 82 | 0.2 s | 9 | 0.0 s | 130 | 65 | 0.1 s | 130 | 258 | 0.5 s |
| 6JQW | 44 | 288 | 0.5 s | 37 | 0.1 s | 0 | 0.0 s | 21 | 24 | 0.0 s | 21 | 35 | 0.1 s |
| 96L6 | 63 | 289 | 0.5 s | 32 | 0.1 s | 0 | 0.0 s | 46 | 6 | 0.0 s | 46 | 88 | 0.2 s |
| 3GZX | 108 | 289 | 0.5 s | 50 | 0.1 s | 27 | 0.1 s | 94 | 39 | 0.1 s | 94 | 130 | 0.3 s |
| ZH7C | 16 | 98 | 0.2 s | 11 | 0.0 s | 0 | 0.0 s | 10 | 21 | 0.0 s | 10 | 6 | 0.0 s |
| 6FWR | 20 | 151 | 0.3 s | 17 | 0.0 s | 0 | 0.0 s | 10 | 9 | 0.0 s | 9 | 25 | 0.1 s |
| NAT4 | 86 | 288 | 0.5 s | 23 | 0.1 s | 61 | 0.1 s | 35 | 193 | 0.4 s | 35 | 17 | 0.0 s |
Table D.1 (PDF p. 31). Per-input stage costs on the 75 returned-word inputs (continued). Sizes are in bytes; outputs exclude whitespace. Calls and times are per stage.
Discovery budget. Each family contributes its smallest and largest inputs and any with a minority found/abstained outcome in the main run: 37 inputs, 20 text and 17 binary. Only the budget varies; seed 0 and the 16-call confirmation reserve are fixed. Table D.2 gives the tested grid behind the thresholds in § 7.3. At 50 and 100 calls, C’s 10 and PDF’s pdftoppm-jch207 abstain. At 600, only asn1-aah055-nested differs from the main run, returning four zero bytes instead of its 10-byte word: more budget need not preserve the choice.
| Budget | Text | Binary | Same |
| 50 | 18/20 | 0/17 | 34/37 |
| 100 | 18/20 | 0/17 | 34/37 |
| 200 | 20/20 | 0/17 | 36/37 |
| 300 | 20/20 | 1/17 | 37/37 |
| 400 | 20/20 | 1/17 | 37/37 |
| 600 | 20/20 | 1/17 | 36/37 |
Table D.2. Discovery budget sweep. Text and Binary count inputs returning a word. Same counts identical words or abstentions to the main run.
| Family | Input | Open | Close |
| c | recog_c_1990_63K | * | * |
| c | simplify-rtx_c_4922_43K | = | = |
| python | ackermann | − | ans |
| python | mroref | : | ' |
| smt | btor2-bug-21435-401 | ite | #b1 |
| sql | sqlflex-sqlite-909 | rt0 | |
| yaml | NAT4 | \n | \n |
Table D.3. Admitted pairs other than format delimiters and conditional operators. Token spellings are literal; \n denotes a newline.
Output size against input size. Figures D.1 and D.2 plot output size against input size, for drdd and AutoDiDact and for AutoDiDact and the format-aware tools. drdd’s outputs grow almost in step with the input, to a median of 18,345 bytes on the 26 inputs of at least 10 KiB. On the same inputs, AutoDiDact’s outputs have a median of 141 bytes, close to C-Reduce’s 157. HDD’s median is 149 bytes on the 18 of these inputs it covers.
Oracle calls against input size. Figures D.3 and D.4 plot oracle calls against input size for the same reducers. drdd’s calls grow with the input, to a median of about 108,000 on the 26 inputs of at least 10 KiB. On the same inputs, AutoDiDact’s calls, inference included, have a median of about 3,900, below C-Reduce’s 8,750. HDD’s median is 945 on the 18 of these inputs it covers.

Figure D.1. Output size against input size for drdd and AutoDiDact on the 75 returned-word inputs, in non-whitespace kB. drdd’s outputs grow with the input, and AutoDiDact’s stay flat. Marks distinguish families, and the dashed diagonal marks no reduction.

Figure D.2. Output size against input size for AutoDiDact, HDD, and C-Reduce, on the axes of Figure D.1. All three stay flat, except C-Reduce on XML.

Figure D.3. Oracle calls against input size for drdd and AutoDiDact on the 75 returned-word inputs. AutoDiDact’s calls include its inference. drdd’s calls grow with the input, and AutoDiDact’s stay low except on five SMT inputs and one Graphviz input.

Figure D.4. Oracle calls against input size for AutoDiDact, HDD, and C-Reduce, on the axes of Figure D.3. HDD makes fewer calls than AutoDiDact on 44 of its 50 inputs, and AutoDiDact fewer than C-Reduce on 59 of 75.
References
- [1]Alfred V. Aho and Thomas G. Peterson. 1972. A Minimum Distance Error-Correcting Parser for Context-Free Languages. SIAM J. Comput. 1, 4 (1972), 305–312. doi:10.1137/0201022DOI
- [2]Junwen An, Kabilan Mahathevan, and Manuel Rigger. 2026. Artifact for Paper “Dialect-Agnostic SQL Parsing via LLM-Based Segmentation”. Zenodo. doi:10.5281/zenodo.18975512DOI
- [3]ANTLR grammars-v4 contributors. 2025. grammars-v4: Grammars Written for ANTLR 4. https://github.com/antlr/grammars-v4/tree/82740f3f1031d56a1141ff4a8ac098aff6644181 Pinned revision used by the HDD baseline.
- [4]Mohammad Rifaat Arefin, Suraj Shetiya, Zili Wang, and Christoph Csallner. 2024. Fast Deterministic Black-box Context-free Grammar Inference. In Proc. Int. Conf. Softw. Eng. (ICSE). ACM. doi:10.1145/3597503.3639214
- [5]Arturs Backurs and Krzysztof Onak. 2016. Fast Algorithms for Parsing Sequences of Parentheses with Few Errors. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). 477–488. doi:10.1145/2902251.2902304DOI
- [6]Osbert Bastani, Rahul Sharma, Alex Aiken, and Percy Liang. 2017. Synthesizing Program Input Grammars. In Proc. ACM SIGPLAN Conf. Program. Lang. Design Implement. (PLDI). ACM, 95–110. doi:10.1145/3062341.3062349DOI
- [7]Rudi Cilibrasi and Paul M. B. Vitányi. 2005. Clustering by Compression. IEEE Transactions on Information Theory 51, 4 (2005), 1523–1545. doi:10.1109/TIT.2005.844059DOI
- [8]Robert Dorfman. 1943. The Detection of Defective Members of Large Populations. The Annals of Mathematical Statistics 14, 4 (1943), 436–440. doi:10.1214/aoms/1177731363DOI
- [9]Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. 2020. AFL++: Combining Incremental Steps of Fuzzing Research. In 14th USENIX Workshop on Offensive Technologies (WOOT 20). USENIX Association.
- [10]Rahul Gopinath, Björn Mathis, and Andreas Zeller. 2020. Mining Input Grammars from Dynamic Control Flow. In Proceedings of the ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE). https://publications.cispa.saarland/3101/DOI
- [11]Ahmad Hazimeh, Adrian Herrera, and Mathias Payer. 2020. Magma: A Ground-Truth Fuzzing Benchmark. Proc. ACM Meas. Anal. Comput. Syst. 4, 3 (2020), 49:1–49:29. doi:10.1145/3428334DOI
- [12]Satia Herfert, Jibesh Patra, and Michael Pradel. 2017. Automatically Reducing Tree-Structured Test Inputs. In Proc. IEEE/ACM Int. Conf. Automated Softw. Eng. (ASE). IEEE. doi:10.1109/ASE.2017.8115697DOI
- [13]Renáta Hodován and Ákos Kiss. [n. d.]. Picireny: Hierarchical Delta Debugging Framework. https://github.com/renatahodovan/picireny
- [14]Renáta Hodován and Ákos Kiss. 2016. Modernizing Hierarchical Delta Debugging. In Proc. Int. Workshop Automating Test Case Design, Selection, and Evaluation (A-TEST). ACM, 31–37. doi:10.1145/2994291.2994296DOI
- [15]Xiaodong Jia and Gang Tan. 2024. V-Star: Learning Visibly Pushdown Grammars from Program Inputs. Proc. ACM Program. Lang. 8, PLDI (2024).DOI
- [16]Bernhard Korte and Jens Vygen. 2018. Combinatorial Optimization: Theory and Algorithms (6 ed.). Algorithms and Combinatorics, Vol. 21. Springer. doi:10.1007/978-3-662-56039-6DOI
- [17]Gereon Kremer, Aina Niemetz, and Mathias Preiner. 2021. ddSMT 2.0: Better Delta Debugging for the SMT-LIB v2 Language and Friends. Zenodo. doi:10.5281/zenodo.4721925 Artifact, version 1.DOI
- [18]P. Kreutzer, T. Kunze, and M. Philippsen. 2021. Test Case Reduction: A Framework, Benchmark, and Comparative Study. In Proc. IEEE Int. Conf. Softw. Maintenance Evol. (ICSME). IEEE, 58–69. doi:10.1109/ICSME52107.2021.00012DOI
- [19]Neil Kulkarni, Caroline Lemieux, and Koushik Sen. 2021. Learning Highly Recursive Input Grammars. In Proc. IEEE/ACM Int. Conf. Automated Softw. Eng. (ASE). IEEE. https://www.carolinemieux.com/arvada_ase21.pdfarxiv.org/abs/2108.13340
- [20]Aarush Khumbhkar, Feiyang Chen, Danushka Liyanage, Xi Wu, Mohammad Amin Alipour, and Rahul Gopinath. 2026. Dr. DD: 1-Minimal Isolation of Failure Causes via Deferred Restarts. In 2026 IEEE International Symposium on Software Reliability Engineering (ISSRE). IEEE.
- [21]Feifei Li, Xiao Chen, Xiaoyou Sun, Xi Xiao, Shaohua Wang, Yong Ding, Sheng Wen, and Qing Li. 2026. Context-Free Grammar Inference for Complex Programming Languages in Black Box Settings. In Proc. Int. Conf. Softw. Eng. (ICSE). ACM. doi:10.1145/3744916.3773147DOI
- [22]Feifei Li, Xiao Chen, Xi Xiao, Xiaoyou Sun, Chuan Chen, Shaohua Wang, and Jitao Han. 2024. Incremental Context-free Grammar Inference in Black Box Settings. In Proc. IEEE/ACM Int. Conf. Automated Softw. Eng. (ASE). ACM, 1171–1182. doi:10.1145/3691620.3695494DOI
- [23]LLVM Project. [n. d.]. libFuzzer: A Library for Coverage-Guided Fuzz Testing. https://llvm.org/docs/LibFuzzer.html
- [24]David R. MacIver. [n. d.]. Shrink Ray: A Modern Multiformat Test-Case Reducer. https://github.com/DRMacIver/shrinkray
- [25]Jonathan Metzman, László Szekeres, Laurent Simon, Read Sprabery, and Abhishek Arya. 2021. FuzzBench: An Open Fuzzer Benchmarking Platform and Service. In Proc. ACM Joint Eur. Softw. Eng. Conf. Symp. Found. Softw. Eng. (ESEC/FSE). ACM, 1393–1403. doi:10.1145/3468264.3473932DOI
- [26]Ghassan Misherghi and Zhendong Su. 2006. HDD: Hierarchical Delta Debugging. In Proc. Int. Conf. Softw. Eng. (ICSE). ACM, 142–151. doi:10.1145/1134285.1134307DOI
- [27]Falcon Monot, Sergey Bratus, Sven M. Hallberg, and Meredith L. Patterson. 2016. The Seven Turrets of Babel: A Taxonomy of LangSec Errors and How to Expunge Them. In IEEE Cybersecurity Development (SecDev). 45–52. doi:10.1109/SecDev.2016.019
- [28]Philip Oliver, Jens Dietrich, Craig Anslow, and Michael Homer. 2024. Dataset for CrashJS: A NodeJS Benchmark for Automated Crash Reproduction. Zenodo. doi:10.5281/zenodo.10530515arxiv.org/abs/2405.05541
- [29]Jihyeok Park, Seungmin An, Dongyun Gou, Gyeongwon Kim, and Sukyoung Ryu. 2021. JEST: N+1-Version Differential Testing of Both JavaScript Engines and Specification. In Proceedings of the 43rd International Conference on Software Engineering (ICSE). 13–24. doi:10.1109/ICSE43902.2021.00015DOI
- [30]Perl 5 Porters. 2025. perlfaq7: Perl Language Issues. https://perldoc.perl.org/perlfaq7#Can-I-get-a-BNF/yacc/RE-for-the-Perl-language? Perl 5.20250619; “Can I get a BNF/yacc/RE for the Perl language?”.
- [31]John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang. 2012. Test-Case Reduction for C Compiler Bugs. In Proc. ACM SIGPLAN Conf. Program. Lang. Des. Implement. (PLDI). ACM, 335–346. doi:10.1145/2254064.2254104DOI
- [32]Kostya Serebryany. 2017. OSS-Fuzz: Google’s Continuous Fuzzing Service for Open Source Software. Invited talk, 26th USENIX Security Symposium.
- [33]Chengnian Sun, Yuanbo Li, Qirun Zhang, Tianxiao Gu, and Zhendong Su. 2018. Perses: Syntax-Guided Program Reduction. In Proc. Int. Conf. Softw. Eng. (ICSE). ACM, 361–371. doi:10.1145/3180155.3180236DOI
- [34]Dániel Vince, Renáta Hodován, Daniella Bársony, and Ákos Kiss. 2021. Extending Hierarchical Delta Debugging with Hoisting. In Proc. IEEE/ACM Int. Conf. Automation of Software Test (AST). IEEE.
- [35]Guancheng Wang, Ruobing Shen, Junjie Chen, Yingfei Xiong, and Lu Zhang. 2021. Probabilistic Delta Debugging. In Proc. ACM Joint Eur. Softw. Eng. Conf. Symp. Found. Softw. Eng. (ESEC/FSE). ACM, 881–892. doi:10.1145/3468264.3468625DOI
- [36]Zhenyang Xu, Yongqiang Tian, Mengxiao Zhang, Jiarui Zhang, Puzhuo Liu, Yu Jiang, and Chengnian Sun. 2025. T-Rec: Fine-Grained Language-Agnostic Program Reduction Guided by Lexical Syntax. ACM Trans. Softw. Eng. Methodol. 34, 2 (2025), 1–31. doi:10.1145/3690631DOI
- [37]YAML Test Suite contributors. 2022. YAML Test Suite. https://github.com/yaml/yaml-test-suite/tree/data-2022-01-17 Release data-2022-01-17.
- [38]Boyang Yang, Luyao Ren, Xin Yin, Jiadong Ren, Haoye Tian, and Shunfu Jin. 2025. Input Reduction Enhanced LLM-based Program Repair. arXiv:2507.15251. doi:10.48550/arXiv.2507.15251arxiv.org/abs/2507.15251
- [39]Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and Understanding Bugs in C Compilers. In Proc. ACM SIGPLAN Conf. Program. Lang. Design Implement. (PLDI). ACM, 283–294. doi:10.1145/1993498.1993532DOI
- [40]Michal Zalewski. 2014. American Fuzzy Lop. https://lcamtuf.coredump.cx/afl/
- [41]Andreas Zeller and Ralf Hildebrandt. 2002. Simplifying and Isolating Failure-Inducing Input. IEEE Trans. Softw. Eng. 28, 2 (2002), 183–200. doi:10.1109/32.988498DOI
- [42]Mengxiao Zhang, Yongqiang Tian, Zhenyang Xu, Yiwen Dong, Shin Hwei Tan, and Chengnian Sun. 2024. LPR: Large Language Models-Aided Program Reduction. In Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2024). doi:10.1145/3650212.3652126DOI
- [43]Mengxiao Zhang, Zhenyang Xu, Yongqiang Tian, Xinru Cheng, and Chengnian Sun. 2025. Artifact for “Toward a Better Understanding of Probabilistic Delta Debugging”. Zenodo. doi:10.5281/zenodo.14854239 Version 3.arxiv.org/abs/2408.04735