AutomatonQuery.ramBytesUsed() is frozen at construction, so a wildcard or regex query that runs on an NFA under-reports its heap and a query cache can far exceed its RAM budget

AutomatonQuery implements Accountable, but it computes ramBytesUsed() once, in its constructor, and stores the sum in a final field (private final long ramBytesUsed; // cache). When the automaton is not deterministic, its CompiledAutomaton runs it with an NFARunAutomaton, which determinizes lazily and keeps every DFA state it builds for the life of the query. The NFA's own estimate and CompiledAutomaton.ramBytesUsed() follow that growth; the query's stored value does not. On main, WildcardQuery(Term) and RegexpQuery(Term) no longer determinize (#15939, #15961), so the default constructors take this path: after one count over 1,024 terms, WildcardQuery(*a?????????) reports 5,674 bytes while it holds 205,216 (36x); on a 20,000-document field *a???????????? reports 6,714 for 2,081,152 (310x). LRUQueryCache charges a cached query exactly this value, so with a 1 MiB budget 4 cached wildcard filters retain 7,399,536 bytes while the cache accounts 37,368 and evicts nothing. Search hits are always correct. Releases 10.0.0 to 10.6.0 are affected through the opt-in NFA paths (an AutomatonQuery over a non-determinized automaton, RegexpQuery(..., doDeterminization=false)); 9.x is not.

1. Construction. AutomatonQuery.java:93-105: the constructor builds compiled = new CompiledAutomaton(automaton, false, true, isBinary) (:99) and stores BASE_RAM_BYTES + term.ramBytesUsed() + automatonBytes + compiled.ramBytesUsed() in the final field ramBytesUsed (:57, commented "// cache"; :102-104). ramBytesUsed() returns the field (:170-173).
2. NFA execution. CompiledAutomaton.java:253-257: if neither the automaton nor its UTF-8 form is deterministic, it keeps no DFA and creates new NFARunAutomaton(binary, 0x100); its javadoc says such an automaton "will be executed using NFARunAutomaton" and still calls the class "Immutable" (:36-40).
3. The states grow during the search. NFARunAutomaton.java:28-31: "It will lazily determinize on-demand, memorizing the generated DFA states that has been explored." New states go into dStateToOrd and dStates under stateRegistryLock (:49-51, findDState :159-177); each state's transitions fill in as terms are stepped (:309-332). Nothing drops them while the query lives.
4. Who counts them. NFARunAutomaton.ramBytesUsed() (:260-268) and CompiledAutomaton.ramBytesUsed() (:554-561) are live. AutomatonQuery read the compiled estimate once, when the NFA had one state.
5. The default path on main. WildcardQuery.java:49-60 passes toAutomaton(term) (:67-101, a concatenation, no determinize) to AutomatonQuery; RegexpQuery.java:54-56, :90-101 passes new RegExp(...).toAutomaton(provider). The classic query parser builds both (QueryParserBase.java:512, :579).
6. The cache. LRUQueryCache.java:465-471 charges RamUsageEstimator.sizeOf(query, 32), which is ramBytesUsed() for an Accountable (RamUsageEstimator.java:378-386); for a filter the key is the constant-score wrapper, whose value is an object header and a reference (16 bytes here) plus the wrapped query's (AbstractMultiTermQueryConstantScoreWrapper.java:52-56). The DocIdSet is built first, so the NFA has already run on that segment (LRUQueryCache.java:609-610); the query is then sized once, at its first reference (:990-999, :1110-1121). UsageTrackingQueryCachingPolicy.java:45-54, :122-125: a MultiTermQuery is cached after 2 uses.

Same 1,024-term index as the repro, one count, retained heap measured with the test framework's RamUsageTester:

The DFA is accounted to within 182 bytes (about 0.02%). The defect is the accounting, not extra memory: here the lazy NFA holds less than the full DFA would.

On the study's field of 20,000 documents with random 20-letter a/b terms (19,809 distinct), after one count: *a???? reports 3,890 and retains 18,560; *a????????? 5,674 and 465,552; *a???????????? 6,714 and 2,081,152; *a??????????????? 7,810 and 12,744,056. A non-leading pattern, a*b??????????, reproduces too: 6,442 reported vs 583,008 retained on the same field (the study's refute-lens reviewer saw 6,442 vs 1,025,888 on its own index of 12,000 random 18-letter terms).

Cache: that field in one segment, new LRUQueryCache(1000, 1 MiB), the default UsageTrackingQueryCachingPolicy, and 4 patterns (*a????????????, *b????????????, *a???????????b, *b???????????a) each sent 3 times as a fresh ConstantScoreQuery(new WildcardQuery(...)): the cache accounts 37,368 bytes in total while its 4 cached query keys retain 7,399,536 bytes (7.1x the budget). Fresh per-request queries share one key on main because #15961 gave NFA-backed automata value equality (NFARunAutomaton.java:270-281).

• Who, on main (unreleased 11.0). Default WildcardQuery/RegexpQuery objects for non-deterministic patterns (a * or .* followed by more pattern), used as filters or counts, with an application-installed LRUQueryCache. Caching is off by default on main (IndexSearcher.java:82-84, #14187); MIGRATE.md shows how to turn it back on (lucene/MIGRATE.md:227-236). By default the cache only caches on segments of 10,000+ documents (LRUQueryCache.java:251-253).
• Who, on 10.0.0 to 10.6.0. Only callers that opt into NFA execution: new AutomatonQuery(term, automaton) over an automaton they did not determinize (10.0 stopped determinizing behind the scenes, lucene/MIGRATE.md:922-926), or RegexpQuery(..., doDeterminization=false) (#12767). The default IndexSearcher cache is on there (LRUQueryCache(1000, min(32 MB, heap / 20)), 10.6.0 IndexSearcher.java:95-100), but NFA-backed queries compare by identity, so the overrun needs the application to reuse the same query instance.
• What happens. The cache's byte budget no longer bounds the heap these keys actually retain: the cache keeps the bytes it records under maxRamBytesUsed, but for these keys those are construction-time values, so in the runs shown only maxSize (1,000 entries by default) limits them. Any other reader of ramBytesUsed() after a search gets the stale value too.
• How much. It grows with the pattern and the field: about 1.5x to 2x more retained per extra ? on the study's field (18.6 KB for *a????, 2.1 MB for *a????????????, 12.7 MB for *a???????????????), so short patterns leave little unaccounted heap. Main also runs, as an NFA with no work limit, patterns whose determinization with the default limit (the one 10.x's WildcardQuery(Term) applied up front) throws TooComplexToDeterminizeException: for one 16-? pattern on 100,000 documents the study saw the compiled automaton count 39 MB while the query reported 8,162 bytes (run on main, not on a 10.x release; not re-measured).
• What it does not do. No hit is wrong; nothing is bypassed or exposed. No OutOfMemoryError run was made.
• How likely: rare. It takes long patterns on fields with many distinct terms, repeated often enough to be cached, with a cache installed (main) or an opt-in NFA API and reused instances (10.x).

The assertion is the lower bound Lucene's own formula implies: the query holds its CompiledAutomaton, and its value is defined as a fixed part plus compiled.ramBytesUsed(). It needs no tolerance and no outside measurement. The retained sizes on this page come from separate checks with RamUsageTester, not from the repro.

Release jars: the test passes on 10.5.2 and 10.6.0, where WildcardQuery(Term) is determinized up front. To run it on the released versions, replace the WildcardQuery line with new AutomatonQuery(new Term("f", ".*a.{9}"), new RegExp(".*a.{9}").toAutomaton()): that fails on main (5,666 vs 273,273), 10.5.2 and 10.6.0 (5,674 vs 273,281). Use one form or the other, not both; the swap also changes the declared type to AutomatonQuery and imports org.apache.lucene.util.automaton.RegExp.

Regression test: this same test; it passes with the recommended fix and fits as one more method in TestAutomatonQuery.

cp $REPRO/TestAutomatonQueryRamBytesUsedAfterSearch.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests TestAutomatonQueryRamBytesUsedAfterSearch -Ptests.seed=DEADBEEF
# the same result with -Ptests.asserts=false

# gradle, stock 645d4fe14a20, -Ptests.seed=DEADBEEF (assertions on; the same with -Ptests.asserts=false)
TestAutomatonQueryRamBytesUsedAfterSearch > testRamBytesUsedCoversCompiledAutomatonAfterSearch FAILED
    java.lang.AssertionError: expected WildcardQuery.ramBytesUsed() >= its compiled automaton's 273273 after one search, but was 5674
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:CCE427083B0F174A]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.search.TestAutomatonQueryRamBytesUsedAfterSearch.testRamBytesUsedCoversCompiledAutomatonAfterSearch(TestAutomatonQueryRamBytesUsedAfterSearch.java:50)

# with the recommended fix: 1 test, 0 failures (assertions on and off)

• The contract. Accountable.java:34-40: "Returns an estimate of the JVM heap memory used by this object in bytes." LRUQueryCache.java:60-62: it evicts "in order to remain under a given maximum size and number of bytes used".
• The field predates NFA execution. LUCENE-8855 (a76c962ee61, 2019, #9898) cached the value for "finalized" queries to avoid recomputing it, when a CompiledAutomaton was always a DFA. LUCENE-10010 (#225, c972c6a7754, 2021) made the compiled form grow after construction; the field was not revisited.
• Upstream wants the states counted. On #13715 Robert Muir listed "ramBytesUsed doesn't consider nfaRunAutomaton" as a problem, and Patrick Zhai, the NFA's author, noted that the NFA "will remember all the states that has been determinized". #13741 then made NFARunAutomaton and CompiledAutomaton count them live; only the outer AutomatonQuery copy stayed frozen.
• Smaller errors here were bugs. #16389/#16390 (a double count in this method, fixed in 10.6.0; "ramBytesUsed() feeds LRUQueryCache eviction decisions"); #16046 (an 18-35% over-count in CompiledAutomaton.ramBytesUsed()).
• Upstream tests. TestAutomatonQuery.java:289-303 holds the value within 10% of RamUsageTester, TestNFARunAutomaton.java:46-53 within 30%, on fresh objects only; the helper at TestAutomatonQuery.java:305-320 defines the value as shallow size + term + q.getCompiled().ramBytesUsed(), the relation the repro checks after a search.
• Precedent. LUCENE-9350 (#10390) stopped FuzzyQuery from keeping automata on the query because they "can end up blowing up query caches"; #15097/#15124 and #16405/#16406 fixed other cache under-counts.

The strongest case: ramBytesUsed() is only "an estimate"; Accountable is @lucene.internal, and AutomatonQuery, CompiledAutomaton and LRUQueryCache are @lucene.experimental; the field is labelled "// cache" on purpose, and LRUQueryCache itself sizes a query only once (LRUQueryCache.java:973-999), so both treat a query's size as fixed; the NFARunAutomaton javadoc documents the growth; the WildcardQuery javadoc warns against a leading *; caching is off by default on main; on #15939 Robert Muir wrote that RegexpQuery "is convenience for a one-off" and that a heavily reused pattern should use AutomatonQuery; and on #16031 (closed unmerged) a contributor argued that FuzzyQuery#ramBytesUsed should return "a stable value" rather than "jump from 0 to N after the first execution".

Why it fails: keeping the states is intended; nothing in the code, the docs or the history says under-reporting them is, and upstream already made the inner estimates live (#13741). The "// cache" was right when written and went stale with #225. The cache's one-time sizing is no excuse: the DocIdSet is built before the key is sized (LRUQueryCache.java:609-610), so a live value would cover the first segment. The leading-* warning is about speed, and a non-leading pattern and the opt-in RegExp path reproduce. The "one-off" remark is about DFA versus NFA speed, while here the reuse comes from Lucene's own cache, which on main shares one key across fresh queries. #16031 concerns a query that holds no automaton and was not merged. No reviewer found the intended-behaviour case convincing: every review that rated its strength called it moderate, and the devil's-advocate review concluded with high confidence that the stale value is not intended.

Option A was built and run through gradle. B (bound the NFA's state cache) and C (do not keep the states on the query) change the design and cap what a query can hold; D (re-size cached keys) closes the cache-side gap A leaves. None of B-D was run. Workarounds that need no fix: determinize patterns yourself and use AutomatonQuery (MIGRATE.md's recipe, which also restores a work limit), keep MultiTermQuery filters out of the cache with a custom QueryCachingPolicy, or run without a query cache (the default on main).

AutomatonQuery keeps BASE_RAM_BYTES + term + automaton (unless shared) in a field and adds compiled.ramBytesUsed() on every call. NFARunAutomaton.ramBytesUsed() takes stateRegistryLock, which already guards its state map, so a live read cannot iterate dStateToOrd while another thread adds a state. 2 files, +15/-10.

// AutomatonQuery
private final long fixedRamBytesUsed; // BASE_RAM_BYTES + term + automaton (unless shared)
public long ramBytesUsed() {
  return fixedRamBytesUsed + compiled.ramBytesUsed();
}

// NFARunAutomaton
public long ramBytesUsed() {
  synchronized (stateRegistryLock) {
    return BASE_RAM_BYTES + ... + RamUsageEstimator.sizeOfMap(dStateToOrd) + ...;
  }
}

Trade-offs

• Why the lock. RamUsageEstimator.sizeOfMap iterates the HashMap (RamUsageEstimator.java:260-278), findDState adds to it under stateRegistryLock (NFARunAutomaton.java:163-176), and the class is documented as safe for concurrent stepping (:29-31). Inside Lucene nothing reads the NFA's estimate during a search today; with a live query value the cache would, while other slices of the same query may still be stepping. The study's one-method sketch lacks this part.
• Cache gap. LRUQueryCache still sizes a query once, at its first reference (LRUQueryCache.java:990-999): the first segment's states are counted, since they are built before the key is sized; states built later, on other segments or by later searches, are not.
• Cost. A live read is O(number of DFA states) and blocks stepping on that query meanwhile; the cache does it once per admitted query.
• Javadoc. CompiledAutomaton's "Immutable" (CompiledAutomaton.java:37) could be reworded in the same change.

What the checks validated

Applied to a scratch worktree of 645d4fe14a20 and run through gradle with OpenJDK 25.0.3, seed DEADBEEF (2026-10-31; the worktree was removed afterwards):

• stock: the minimal test fails with assertions on and off;
• with the fix: the minimal test passes with assertions on and off;
• the study's 2-test class (the value at least half of what RamUsageTester measures after a search, and the 1 MiB LRUQueryCache budget test) passes 2/2 with assertions on and off;
• the closest suites, TestAutomatonQuery, TestAutomatonQueryUnicode, TestLRUQueryCache, TestWildcardQuery, TestRegexpQuery and all of org.apache.lucene.util.automaton.*: 20 classes, 312 tests, 0 failures, 5 skipped;
• :lucene:core:checkGoogleJavaFormat, ecjLintMain and forbiddenApisMain pass;
• with the lock-free one-method version the minimal-case query reports 273,778 bytes after the count against 205,216 measured; the lock does not change the value.

Not run: a concurrent search through a cache, a multi-segment cache test, benchmarks.

On #225 Patrick Zhai called a limit on "the number of state that NFA can cache" "a feature not implemented yet". A bound (stop caching, or drop states, past a size) caps what one query can hold whatever the accounting does.

Trade-offs

It also limits patterns whose determinization exceeds the default work limit (the limit 10.x's WildcardQuery(Term) applied up front), which main now runs as an NFA without one. A larger design change with performance trade-offs (re-stepping without cached states). Not run.

Hold the lazily built states per search or per segment instead of on the CompiledAutomaton, as LUCENE-9350 did for FuzzyQuery's automata.

Trade-offs

The query's size then stays fixed and the existing value becomes right, but every search rebuilds its states. Not run.

LRUQueryCache could refresh a query's bytes when another segment's entry for it is added, so growth after admission is charged.

Trade-offs

Closes the gap option A leaves, but touches the per-distinct-query accounting #16657 just restructured (LRUQueryCache.java:465-467, :973-999). Not run.

Method: semi-formal (the hunt's tier for systematic checks against an independent measurement). The unit did bounded-exhaustive translation validation of NFA versus DFA execution of WildcardQuery and RegexpQuery against a reference semantics; the lazily built DFA-state cache is the only mutable part of a CompiledAutomaton.

• Signal. For *a???? to *a??????????????? on a 20,000-document field, RamUsageTester.ramUsed(query) grew from a few KB to 18.6 KB-12.7 MB after one search while ramBytesUsed() stayed at 3.9-7.8 KB.
• Confirmation. A 2-test JUnit on the stock main jars (the value, and an LRUQueryCache budget under the default caching policy) failed with assertions on and off; independent verifiers, cross-model reviews from another model family (OpenAI GPT-5.6) and an adjudication confirmed it, and a 2026-10-29 minimization cut the repro to the one test above.