fix(memory): avoid silent memory loss when LLM prose contains braces before JSON - #5999

All committers have signed the CLA.

Thanks for tracking this down and writing it up so clearly — the repro in the issue is exact and this is a real fix for a real bug. I pulled the branch, ran the new tests, then reverted just the utils.py hunk (keeping your tests) to make sure they actually exercise the bug rather than just asserting mocked behavior: pre-fix, test_chatty_prose_with_braces_before_json and test_chatty_prose_with_braces both fail with genuine JSONDecodeErrors (2 failed, 22 passed); with the fix restored, all 24 pass. Good, targeted regression tests — appreciate that you also added the "braces inside a JSON string value" guard case, since a naive brace-counter without string-awareness would've broken on that.

One thing stops me from merging as-is though: the new _first_parseable_json_object scan is worst-case quadratic, and the worst case sits right in the domain this PR is fixing. For every { it finds, it restarts a fresh forward scan tracking brace depth; if a long run of { never balances back to depth 0 before the real JSON shows up (truncated output from hitting max_tokens mid code-block/JSON, or a model that likes {{ }} templating syntax), every one of those positions triggers another near-full-length rescan. I timed it directly:

n=1,000 unbalanced '{' before the real JSON  -> 0.01s
n=5,000                                       -> 0.26s
n=20,000                                      -> 4.0s
n=50,000                                      -> 25.2s

That's clean O(n^2) scaling. Our default max_tokens is 2000 (~8-10K chars of output), so we're already at roughly a second in the worst case at the default, and anyone who bumps max_tokens for a chatty local model (exactly the audience this PR is for) can push this into tens of seconds to minutes with zero warning, on the shared extract_json path every backend uses. It's worse on the async side too — the AsyncMemory call site calls this synchronously (not wrapped in asyncio.to_thread like the DB save right next to it in the same function), so a slow parse there stalls the whole event loop, not just the one request.

To be clear, I don't think this needs a rewrite — the three-tier fallback shape (new scan -> old naive span -> as-is) is the right, minimal design and I'd keep it exactly as is. The fix is narrower than it sounds: restructure the scan into a single linear pass that only opens a new "candidate start" when depth is back at 0, and on a failed parse of a completed span, keep going in the same pass instead of restarting from start + 1. That gets you O(n) instead of O(n^2) with roughly the same amount of code. Alternatively, if that feels like more surgery than you want right now, a cheap cap on how many candidate starts (or how much text) the scan will try before giving up and falling through to the existing naive-span fallback would also close the gap.

Small non-blocking nit while I was poking at edge cases: when the prose contains more than one syntactically-valid JSON object (e.g. an example blob mentioned before the real one), the scan returns the first valid one, which isn't necessarily the intended one. In practice this is harmless for our actual call sites since they do .get("memory", []) and a wrong-but-valid object without that key just degrades to "nothing extracted," same as the old failure mode — so not asking for anything here, just flagging it in case it matters for other future callers of extract_json.

Once the quadratic-scan bit is addressed I'm happy to get this merged — the core logic and tests are solid.

Thanks for the thorough review and for actually pulling the branch and benchmarking the worst case; the O(n^2) call is spot on and the failure mode you describe (a long run of unbalanced braces from truncated output or {{ }} templating) is exactly the chatty-local-model domain this fix is for, so it should not be the thing that regresses perf.

I restructured _first_parseable_json_object along the lines you suggested, keeping the three-tier fallback shape unchanged. It is now a single linear pass: a candidate span opens only when depth returns to 0, and a completed top-level {...} span that fails to parse lets the scan continue in the same pass instead of restarting from start + 1. Non-overlapping top-level spans mean the total json.loads work is bounded by the input length too, so the whole thing is O(n). Your 50k-brace case goes from ~25s to ~2ms; 200k is ~9ms.

I also added a regression guard (test_many_unbalanced_braces_stays_linear) that runs 50k unbalanced braces through extract_json with a generous 2s bound, so a future reintroduction of the quadratic rescan fails the suite by a wide margin without being flaky on slow CI. Existing tests still pass (25 total).

On the async point: since the root cause was the slow parse itself, the linear pass removes the event-loop stall you flagged at the AsyncMemory call site. Wrapping that specific call in asyncio.to_thread like the neighboring DB save is a reasonable separate hardening, but I have left it out of this PR to keep the change scoped to the parser.

On the multiple-valid-objects nit: behavior is unchanged (first valid top-level object wins), and as you note the .get("memory", []) call sites degrade to "nothing extracted" for a wrong-but-valid object, same as the old failure mode. Happy to revisit if a future caller needs stricter selection, but I have not changed it here.

Verified against e19f487 (new head).

The O(n²) scan is fixed — confirmed independently, not just from your numbers: 50k unbalanced braces runs in ~1ms here (was ~25s at f3ec271), test_many_unbalanced_braces_stays_linear (tests/test_chatty_llm_parsing.py:120) passes along with the other 24, ruff is clean, and the broader suite (test_chatty_llm_parsing.py + test_main.py + tests/memory/test_memory_utils.py, 83 tests) is green. The single-pass shape is the right call and the docstring at utils.py:132 explains it well.

One new issue from the rewrite: _first_parseable_json_object (utils.py:144-174) now uses a single running depth/start pair, and start only gets rewritten when depth == 0 (line 160). If the prose has one unmatched { before the real JSON, depth never returns to 0 again for the rest of the text, so the real object is never found and extract_json falls through to the old naive span — reproducing the original #5998 failure mode, just triggered by an unmatched brace instead of any brace:

text = 'Sure, I will fill in {the blank with details later. Here is the extracted JSON: {"memory": [{"id": "0", "text": "likes travel", "event": "ADD"}]}'
_first_parseable_json_object(text)  # -> None
extract_json(text)                  # -> falls to naive span -> JSONDecodeError when parsed

Checked this isn't pre-existing: the f3ec271 nested-loop version handles this exact input correctly (each candidate start got its own fresh depth counter, so an earlier dead end didn't block a later one). It's also not just a synthetic string — the PR's own 50k-brace benchmark input, with a real memory object appended after the braces, fails to parse on the new code too. test_many_unbalanced_braces_stays_linear doesn't catch this because it only covers "unbalanced braces, no real JSON anywhere" — a different case from "unbalanced braces, then a real JSON."

Given the audience is chatty/small local models, a model rambling or sketching notation with an unmatched { before the real answer seems at least as likely as a neatly matched pair, so I'd treat this as blocking rather than a nit.

For a fix: a single global depth counter can't distinguish "no JSON exists" from "an earlier unmatched { is blocking a later, well-formed object" — both look identical (depth never hits 0). You'll likely need to track more than one pending candidate start (e.g. a small stack of open positions, or resync start to the newest { once a run of unmatched opens with no interleaved close gets long enough) so a stray brace can't permanently pin the scan, while keeping the happy path linear. Also asking for a regression test that pairs an unmatched brace with a real trailing JSON object — that's the gap in the current suite.

Everything else from last round still holds: the multi-object nit is fine as a non-blocking note, and leaving the async call site unwrapped is reasonable now that the parse itself is fast.

Great catch, and thank you for verifying it independently down to the exact repro. You're right that a single running depth counter fundamentally can't tell "no JSON exists" from "an earlier unmatched brace is pinning the scan," and that the chatty/small-model audience makes a stray { before the answer entirely plausible. Agreed it's blocking, not a nit.

Rather than track a stack of pending starts by hand, I switched _first_parseable_json_object to decode each candidate { with json.JSONDecoder().raw_decode, which consumes exactly one value and fails fast on a non-JSON start. An earlier dead-end brace (your {the blank... case, or the plausible-but-invalid {"a" garbage ...) no longer blocks a later well-formed object, because each { is attempted independently.

To keep it linear, I only attempt positions that can actually begin an object: the next non-whitespace char must be " or }. That matters because calling raw_decode at all 50k braces was itself slow (~900ms from the per-attempt exception overhead), even though it was no longer quadratic. With the filter, a run of {{{... costs O(1) per brace and only real candidates hit raw_decode. Measurements here:

• your blocking repro now returns the memory object correctly
• {"a" garbage {"memory": [...]} (plausible-but-invalid outer) also resolves to the real object
• 50k unmatched braces followed by a real object: ~4ms, object found
• 50k unmatched braces with no JSON: ~4ms, returns None
• the happy path still returns the outer object (raw_decode reads the whole value, not the first inner one)

For the test gap you flagged, I added regression tests that pair an unmatched brace with a real trailing object, in both TestExtractJson and TestFallbackChain, plus a 50k-brace-then-real-object linearity test. All three fail on the previous single-depth version and pass now; the full suite you referenced (test_chatty_llm_parsing.py + test_main.py + tests/memory/test_memory_utils.py) stays green at 86, and ruff is clean.

Left the multi-object and async-call-site notes as-is per your last round. Pushed as 3cdc9c7.

Verified against 3cdc9c7a273 (new head).

The flagged bug is fixed. The single running depth counter is gone — _first_parseable_json_object now tries json.JSONDecoder.raw_decode at each candidate { independently, so one dead-end brace can no longer block a later valid object. Confirmed with a real red/green cycle: swapped just utils.py back to the previous head in a worktree, the three new regression tests failed as expected (test_unmatched_brace_before_real_json, test_many_unbalanced_braces_then_real_json_stays_linear, test_unmatched_brace_before_json); restored to this head, all 28 tests in test_chatty_llm_parsing.py pass, and last round's exact repro now resolves to the real memory object. Broader sweep (test_chatty_llm_parsing.py + test_main.py + tests/memory/test_memory_utils.py) is 86 passed, ruff clean.

New finding, and it's the same failure class the last two rounds each hit in this same function, just moved again: the 'next char after { must be " or }' prefilter keeps bare-brace runs O(1), but once a candidate passes it, each failed raw_decode still raises a JSONDecodeError, and building that exception's line/column info rescans the string from position 0 every time — repeating that at every {"-prefixed candidate, with the scan position growing each time, is quadratic. Measured directly on this head: a flat 75,000-char brace run is 3.6ms; a 75,000-char nested/truncated run ('{"a":'*15000, the shape of a small local model stuck repeating a key fragment) is 4.1s — about 1000x slower at the same length. That's reachable on the async path: _add_to_vector_store's async version threads the LLM call itself via asyncio.to_thread, but calls extract_json inline right after, unthreaded, so a multi-second parse stalls the event loop for every concurrent request — the same risk category this function's previous rewrite already fixed once for a different shape. It's also not confined to memory extraction: extract_json is the fallback parser in 13 LLM-provider paths and 4 vector-store paths, so the same input shape is reachable well beyond Memory.add. To be fair to the fix: this is a narrower, more synthetic trigger than the prose case above (needs many repeated {"-shaped fragments with no closing quote anywhere), so it's a hardening gap rather than a repeat of the original data-loss bug.

Fix direction: a cumulative scan budget (cap total characters fed to raw_decode across all candidates, or cap attempt count) falling through to the naive span once exhausted, same shape as the existing prefilter but bounding total work instead of per-candidate work, plus a regression test using a nested/truncated shape rather than only flat brace runs.

This is the third rewrite of this function in one PR cycle, and each round has traded one failure mode for another in the same spot. I'd rather have a maintainer look at the shape of the fix here than ask for a fourth quick patch today — the bound above should be a small, contained change on top of what's here now.

You're right, and thank you for the precise shape. Reproduced here: flat 75k braces is ~7ms, but '{"a":' * 15000 is ~7.5s on my machine — every candidate passes the object-start prefilter and raw_decode walks to end-of-text before failing on the unterminated string. My adversarial testing covered valid objects and bare-brace runs but not truncated key fragments, which is exactly the gap. Point taken as well on this being the third relocation of the same failure class in one function; pausing for a maintainer on the shape of the fix is the right call and I won't push another same-day patch.

So it's concrete for that discussion, I implemented the bound you sketched locally (holding it unpushed until you or a maintainer confirm the direction):

• cumulative scan budget of 2 * len(text) characters across all raw_decode attempts, charged per failed attempt as max(JSONDecodeError.pos - idx, 1). Cheap prose rejections ('{about travel}') charge ~1, so multi-candidate recovery is unaffected; an unterminated string that scanned to EOF charges the remaining text, so the truncated shape exhausts the budget after ~2 attempts
• a belt-and-braces attempt cap (100) in case an error shape reports a small pos after a long scan
• on exhaustion, return None so extract_json falls through to the existing naive-span fallback, i.e. the pre-PR behavior floor you described

Measured on that local patch: truncated 75k goes 7.5s -> ~3ms, a 300k variant stays ~12ms (linear), flat brace runs unchanged, and both prior rounds' repros plus the valid-object fuzz (2000 cases, zero real objects skipped) still pass. Added the regression tests you asked for: the truncated shape alone and the truncated shape followed by a real object, both red on the current head 3cdc9c7 and green with the bound; the dependent suite is 235 passed with ruff clean.

Happy to push that as-is, adjust the budget/cap constants, or take a different shape entirely if a maintainer prefers something else here — whatever pace works for you.

Small correction to my last comment: the patch ended up pushed (631e548) rather than held back as I said. Apologies for the mixed signal there — it's the same commit and numbers I described (truncated 75k: 7.5s -> ~3ms, budget-based, falls through to the naive span on exhaustion, 235 dependent tests + the fuzz battery green). Still very much open to you or a maintainer wanting a different shape here; happy to adjust or revert if so.

Verified against 631e5481 (new head).

The O(n²) blowup from 3cdc9c7a2 is fixed as a mechanism — confirmed independently: '{"a":' * 15000 runs in single-digit milliseconds now instead of several seconds, matches the numbers you reported.

Two new issues, both confirmed by running the code, not just reading it.

1. The budget/attempt-cap gives up before finding real, valid JSON that exists later in the text — a new, easier-to-trigger recurrence of #5998.

_first_parseable_json_object charges the scan budget by err.pos - idx. For a truncated candidate like {"a":{"a":..., raw_decode doesn't fail until it scans to end-of-text, so err.pos lands near len(text) on nearly every attempt — the budget survives about 2 such attempts before it's gone, not O(n) of them. Repro:

'{"a":' * 3 + ' {"memory": [{"id": "0", "text": "ok", "event": "ADD"}]}'

15 characters of prose before the real object, and _first_parseable_json_object returns None. The naive-span fallback isn't valid JSON, json.loads raises in main.py:927/:2551, and the outer except Exception silently drops the memory — same failure class the PR closes, new trigger, well short of the 15000-scale the new tests use.

Second, independent trigger: attempts_left = 100 is a pure count cliff, unrelated to actual cost. '{"a"}' * 100 + ' {"memory": ...}' (100 cheap ~5-char rejects, budget barely touched) returns None; 99 decoys finds the object fine. Neither new test exercises this path — both exhaust via the budget in 3 attempts, never near 100.

2. test_truncated_key_fragments_stay_linear and test_truncated_fragments_then_real_json_bounded fail outright — uncaught RecursionError — on Python 3.10, 3.11, and 3.12 (all three of this repo's CI-tested versions).

$ hatch -e dev_py_3_12 run pytest tests/test_chatty_llm_parsing.py tests/test_main.py tests/memory/test_memory_utils.py -v --tb=short
FAILED ...test_truncated_key_fragments_stay_linear
FAILED ...test_truncated_fragments_then_real_json_bounded
2 failed, 86 passed in 9.05s

raw_decode on '{"a":' * 15000 recurses through the nested-looking structure and hits the default recursion limit (1000) before it ever raises the json.JSONDecodeError the loop's except clause is written to catch. Confirmed the same crash on dev_py_3_10 and dev_py_3_11, and outside pytest entirely with a standalone script. This traces back to a latent issue in round 3's raw_decode-per-candidate design (identical crash on 3cdc9c7a2, and it happens on attempt #1, before any budget bookkeeping runs) — but these two new tests are the first in this PR to exercise a deeply-nested shape at this scale, and they don't pass in CI as committed. Whatever ran the "7.5s -> ~3ms" / "235 passed" numbers was very likely a newer ambient Python (3.13+) — this doesn't reproduce there, only on 3.10-3.12.

Both issues are real regardless of the fuzz battery: a 2000-case random fuzzer isn't likely to land on the exact n=3-fragment or n=100-decoy cliffs, or on the specific nesting depth that recurses — these are narrow, deterministic triggers, not something coverage-by-volume reliably catches.

Fix direction: the round-3 design (independent per-candidate raw_decode) is sound; the budget/cap layered on top of it this round isn't. More promising than tuning the current constants:

• Scan candidates from the end of the text backward (text.rfind("{")) rather than forward — every case in this PR's own tests, and the real-world shape motivating it, is junk-then-JSON, so the real object is the first candidate tried and the budget is never touched for the realistic case.
• Catch RecursionError alongside JSONDecodeError (or pre-check nesting depth) so a pathological candidate degrades to "reject and move on" instead of an expensive unwind.
• Add a test that calls json.loads() on the recovered result and checks it's the actual memory object, not just that the naive-fallback-span mechanism fired — the current bounded-budget test would pass even if recovery were completely broken.

Not asking for anything on the pre-existing first-candidate-wins behavior or the un-threaded async parse site — both unchanged from what you left as-is last round.

Thanks — both repros confirmed and both are covered now. I took your backward-scan suggestion with one adjustment: naively returning the first parse from the end gives the innermost trailing object (the last { is usually a nested memory item, not the envelope), so the scan keeps walking left and adopts any candidate whose parse ends later, i.e. an enclosing object. Junk candidates don't stop the walk, so a stray {" inside a string value can't shadow the envelope either.

RecursionError is now caught per candidate — that was the crash you saw on 3.10-3.12; my earlier numbers were indeed from a newer ambient Python, apologies. This round everything below was run with 3.10, 3.11 and 3.12 explicitly: full test set (the three files you ran) 92 passed on each; your 3-fragment and 100-decoy repros recover the object in ~0.02-0.2 ms; all-junk '{"a":' * 15000 stays bounded at ~14-20 ms; same junk followed by a real object now genuinely recovers it (~14 ms) instead of falling through to the invalid naive span — with a test asserting the recovered text parses to the exact memory object, per your third point.

The attempt cap is gone; the budget now charges only failed decodes by characters actually scanned, and since the backward scan adopts the payload before touching the junk, exhausting it can't lose a found object. One deliberate semantic change to flag: with several disjoint objects the last one wins now (previously the first) — documented with a test, since prose-quoted examples precede the actual payload.

Verified against a8a27a4e (one commit past 631e5481).

Both Criticals from last round are genuinely fixed: the uncaught RecursionError on the '{"a":' * 15000 test now returns None cleanly (except RecursionError at utils.py:186-187, confirmed by re-running that exact repro — no crash), and the flat 100-attempt cap that caused silent loss independent of actual cost is gone (attempts_left no longer exists in the function). Good progress.

The backward-scan rewrite in this commit introduces two new issues, independently reproduced and skeptic-verified.

Needs Human Review

Why: two new Critical-caliber findings, and this is round 4 of re-review on this PR — another round of mechanical nitpicks isn't the right next step. One of the two needs a product decision, not another patch.

Pay attention to

• mem0/memory/utils.py:169-191 — "last disjoint object wins" (tracking best_end across the whole backward walk) relocates extract_json silently drops memories when an LLM wraps JSON in prose containing braces #5998's silent-loss bug to the opposite ordering: real answer first, any other valid {...} later in the text, and the trailing one now wins silently. Confirmed via git show 631e5481:mem0/memory/utils.py that the old code got this exact input right — this is a genuine regression, not pre-existing. There's no direction-only fix here: the red-green proof shows the old code fails the mirror case (decoy first, real answer last — test_multiple_disjoint_objects_last_wins, this PR's own test) for the same structural reason. "First wins" and "last wins" are symmetric bets; neither is universally correct without a real disambiguating signal (e.g. the caller's expected "memory" key, which main.py:925/2549 has and the generic extractor doesn't).
• mem0/memory/utils.py:169-188 — the scan budget is only decremented on failed raw_decode attempts (lines 184-187), never on successful ones. Deeply-nested but well-formed JSON ('{"a": ' * n + '1' + '}' * n) makes every candidate succeed, so the budget never throttles: measured 110ms/627ms/2.6s/10s/39.4s for n=2000/4000/8000/16000/32000, clean O(n²) (the prior commit's own code stays under 3ms flat on the same inputs). This is on the literal Memory.add parsing path, unwrapped in the async caller (blocks the event loop), and unconditionally across all 17 non-main.py callers of extract_json too (vector store metadata, LLM tool-call args) — none of which has the "chatty prose" shape this fix targets.

Findings

Critical

1. Silent wrong-object return when the real answer appears before a later, unrelated valid {...} fragment — zero exception, zero log line, in both the sync (main.py:919-931) and async (main.py:2543-2555) callers.
2. O(n²) blowup on well-formed deeply-nested JSON, caused by the budget only charging failures — reopens the exact hot-path issue e19f48767/631e5481 were written to close.

Important
3. All 13 new tests with a "real + junk" pairing put the junk before the real object — none tests the reverse, so the suite can't catch #1.
4. 17 files / 24 call sites beyond main.py use extract_json with zero test coverage of the new logic.
5. The RecursionError regression-guard test targets a ~15,000-level threshold; actual crash threshold is ~150,000 (~10x higher) — doesn't exercise what it claims to.
6. TS's extractJson (mem0-ts/src/oss/src/prompts/index.ts:901-978) solves the same problem with an unrelated algorithm (forward scan, first-wins, no budget) — not a blocker here (TS already has its own fix under #4737), worth a follow-up issue.

Evidence

• CI: only license/cla (pass), no red required checks.
• Red-green (this cycle's own tests): swapped in 631e5481's utils.py, ran tests/test_chatty_llm_parsing.py unmodified → 5 failed, 29 passed (2x RecursionError, 2x JSONDecodeError, 1x wrong-object assertion on test_multiple_disjoint_objects_last_wins). Restored current head → 34 passed.
• O(n²): reproduced independently three times (orchestrator, two lenses/skeptics) with closely matching numbers; one-shot json.loads() on the same input is ~2400x faster than the function.
• Silent-loss regression: reproduced against current head, then against 631e5481 via git show (no checkout) — old SHA handles the same input correctly, confirming this is new.
• Linked issue: extract_json silently drops memories when an LLM wraps JSON in prose containing braces #5998 confirmed still OPEN.
• Cross-package: TS already fixed its own version under openclaw-mem0 / mem0ai OSS: Failed to parse memory actions from LLM response when using OpenRouter (gpt-4o-mini) #4737 independently; no gap left open by this PR either way.
• Could NOT verify: real-world frequency of the mirror-ordering trigger in production LLM output (no telemetry) — flagged as plausible by shape, not measured in the wild.

Assessment

Ready to merge: No — maintainer judgment required. The one thing to decide with the contributor: whether guessing a direction on multiple disjoint valid JSON objects is the right approach at all, or whether the extractor should refuse to guess (fall through to the existing naive-span fallback) when it finds more than one fully-valid disjoint candidate — that call likely resolves the ordering ambiguity and clarifies whether the O(n²) fix (budget should charge successes too, straightforward on its own) still needs its current shape. Est. human time: ~15 min.