Chain-of-Experience: The Notebook Stays Open

Paper: 2608.18027 Authors: Haoqin Tu, Yunhao Fang, Yizhong Wang, Cihang Xie, Shen Yan Categories: cs.CL

The Gap

Test-time scaling has split into three camps, and none of them keeps the thing this paper cares about.

The first is parallel search: Tree-of-Thoughts, majority voting, best-of-n with a process or outcome verifier. Sample many candidates, pick the good one. The generation traces are rich — dozens of attempts, each with a verifier’s opinion attached — and then they get collapsed into a single answer and deleted. The next problem starts from a blank slate.

The second is self-refinement: Self-Refine, Reflexion, Self-Debug. These do loop, and they do keep the trail inside one context. But the literature around them is narrow in a specific way: usually one feedback source, a handful of iterations, models from two generations ago, and no cost accounting. Nobody had asked what happens when you run the loop twenty times, on GPT-5 and Claude 4.5 Sonnet, with the feedback channel as a controlled variable.

The third is cross-task memory: Dynamic CheatSheet, Agentic Context Engineering, ReasoningBank. Solve a problem, distill the strategy into a persistent note, carry the note to the next problem. This preserves experience — but only in compressed form, and only between problems. Inside the current problem you are still a one-shot solver.

The gap sits at the intersection: same-task, uncompressed, feedback-varied, at scale, with the bill attached. That is what CoE measures.

[PROBLEM] every inference is an isolated event; the model
          restarts each problem with zero accumulated insight
     |
     +-----------------+------------------+
     v                 v                  v
[parallel search] [self-refinement]  [cross-task memory]
 trail collapsed   loops, but tested   carries a *summary*
 to one answer,    with 1-2 feedback   between problems;
 then discarded    types, few rounds,  inside a problem you
                   old models, no      are still one-shot
                   cost accounting
     |                 |                  |
     +-----------------+------------------+
                       v
[ASSUMPTION] the unit of experience is the *entire* solving
             history -- every attempt AND every environment
             response -- and feedback richness is the knob
                       |
                       v
[METHOD] CoE: a_t ~ P(a_t | Q, (a_0,f_0), ..., (a_(t-1),f_(t-1)))
         feedback spectrum: none / model / executor / correctness
         8 LLMs x 6 benchmarks x 20 iterations, tokens and
         dollars logged alongside accuracy
                       |
                       v
[EVIDENCE] averaged over 6 benchmarks: ICL 62.1, DC 62.7,
           ACE 64.0, no-feedback CoE 66.8, self feedback 71.0,
           best feedback 79.3.  +5.6% at 19% lower API cost.
           Gains saturate early: 16.7% in rounds 1-20 vs 2.2%
           in rounds 21-50 on AIME 2025.
                       |
                       v
[CONCLUSION] same-task uncompressed experience beats cross-task
             memory distillation, and compressing the trail
             (DC, SimpleMem) actively hurts

The Increment

One sentence: Before, “test-time learning” meant either sampling in parallel and throwing the attempts away, or distilling them into a cheat sheet for other problems; after, it means keeping the raw attempt-and-feedback trail open inside the current problem, and the paper puts a number on what each kind of feedback is worth and what it costs.

Core Mechanism

The formalism is deliberately thin. Standard QA samples A ~ P(A | Q). CoE introduces a feedback variable drawn from the environment, f ~ P'(F | Q, A), and turns the single turn into a sequential decision process where the t-th action conditions on everything that came before:

a_t ~ P(a_t | Q, (a_0,f_0), (a_1,f_1), ..., (a_(t-1),f_(t-1)))

That’s it. There is no training, no parameter update, no retrieval index. The “learning” lives entirely in a context window that grows by one attempt-plus-verdict per round. The paper’s contribution is not this equation — it’s what happens when you sweep the environment P' across four settings and run the loop long enough to see it saturate.

The four feedback types form a richness spectrum. None sets f_i empty: the model re-reads its own previous attempts and nothing else, so any improvement is pure self-reflection. Model feedback runs an auxiliary LLM as critic, producing prose critiques — usually the same model judging itself. Execution feedback runs the candidate in an interpreter and returns stack traces, error messages, and public test-case outcomes; a stripped binary executor variant returns only pass/fail, which turns out to matter a lot. Correctness feedback is an oracle bit, f_i = 1[a_i is correct], which the paper is upfront about being unrealistic and includes as an upper bound.

The critical design choice — and the one that produces the paper’s most interesting negative result — is that nothing is ever summarized. The context at round 19 contains all nineteen prior attempts verbatim, alongside all nineteen verdicts. When the authors bolt Dynamic CheatSheet or SimpleMem onto the loop to compress that trail within the same task, performance drops: on AIME 2025, plain self-feedback gets 60.0% while +DC gets 50.0% and +SimpleMem 56.7%. Compression is not free storage optimization; it deletes the intermediate reasoning that the next attempt needed.

  one problem Q, iterations t = 0 .. 19

  +----------------------------------------------------------+
  |  CONTEXT at iteration t                                   |
  |    Q                                     the question     |
  |    (a_0, f_0)                            attempt+verdict  |
  |    (a_1, f_1)                                             |
  |     ...                                  full trail,      |
  |    (a_(t-1), f_(t-1))                    uncompressed     |
  +----------------------------------------------------------+
              |
              v
        [ model M ]  ==>  a_t
              |
              v
        [  env  E  ]  ==>  f_t         the pair (a_t, f_t) is
              |                        appended, never summarized
              +---------------------------> back to CONTEXT

  the environment E, four instantiations, by richness:

    none         f = (empty)          re-read your own attempts
    model        f = M_fb(Q, a)       a critic LLM writes prose
    executor     f = run(Q, a)        traces + public test pass
                 (binary variant:     rate  ... or just one bit
                  pass/fail only)
    correctness  f = 1[a is correct]  oracle; upper bound only

  richness matters: on LiveBench (Code), full executor 78.1%
  vs binary executor 71.9% -- same signal source, 6 points
  of difference purely from how much of it you pass through

The metaphor: a lab notebook and four kinds of supervisor. You are a grad student given one experiment to get right. Each attempt is a page in your notebook. The supervisor sits across the bench and says something after each run. The notebook stays open — you can see every previous page whenever you write a new one.

The four supervisors are the four feedback types. The empty chair says nothing; you improve only by re-reading your own pages and noticing you contradicted yourself on page three. The colleague reads your writeup and tells you in words what looks wrong — sometimes insightful, sometimes confidently mistaken, but always phrased in the same language you think in. The instrument doesn’t talk; it either produces a reading or throws an error, and the error message is often more useful than any colleague’s opinion. The professor who already knows the answer just says “no” — maximum reliability, zero diagnostic content, and the reason the paper flags it as unrealistic.

Now the results become intuitive. The colleague beats the empty chair because language-level critique is contextually aligned with how you reason (the paper measures this: model-generated feedback drives a higher proportion of feedback-attributable fixes, 58.7% vs 41.1%). The instrument beats the colleague on code because reality doesn’t hallucinate. The professor’s single bit wins on accuracy but tells you nothing about why — which is exactly why combining professor and colleague works better than either alone (dual feedback hits 76.7% on AIME against 70.0% correctness-only and 60.0% model-only).

And the memory ablation: Dynamic CheatSheet is ripping the pages out and keeping an index card. You save shelf space and lose the failed derivation you were about to need.

One more thing the metaphor gets right. The paper grades by best page in the notebook, not last page. Hold that thought.

Key Concepts

• Same-task vs cross-task experience: These sound like variants of one idea and behave completely differently. Cross-task experience is what a textbook gives you — general strategy abstracted away from any particular problem. Same-task experience is what your last three wrong answers to this problem give you: not a strategy, a map of the specific holes you keep falling into. The paper’s cleanest empirical result is that on modern reasoning models the textbook is nearly worthless — ICL at 62.1%, DC at 62.7%, ACE at 64.0%, all below a plain no-feedback CoE loop at 66.8% — while the hole-map is worth 4-13 points. The plausible reason: strong reasoning models already know the general strategies. What they lack is knowledge of their own specific failures a minute ago.

• Feedback richness vs feedback reliability: Two independent axes that people routinely conflate. A stack trace is rich (tells you where and why) and reliable (reality generated it). An oracle bit is maximally reliable and minimally rich. An LLM critic is rich and unreliable. The paper separates these cleanly with the binary-executor arm — same reliable source, richness thrown away, 6 points lost on LiveBench (Code) — and with the cross-model feedback study, where GPT-5 mini as a judge for GPT-5 works on AIME 2025 (94.4% via model feedback vs 93.0% via correctness) but fails on the harder OmniMath (74.5% vs 82.8%), because the judge’s own base ability on the task is the ceiling on how reliable its feedback can be. Practical rule that falls out: model-as-judge is deployable only when the judge is strong on the specific task, not strong in general.

• Improving capability, and the ceiling problem it tries to dodge: The paper defines a model’s improving capability as (S_max - S_base) / (1 - S_base) — gain achieved, divided by gain available. The normalization exists because a model at 90% can only gain 10 points while a model at 50% has 50 available, so raw gain would trivially favor weak models. With that correction the finding is that stronger models still improve more, average Pearson r = 0.50 across six benchmarks. Worth knowing what that average hides: r = 0.97 and 0.83 on the two coding tasks, but 0.33 and 0.24 on AIME and OmniMath, over seven or eight model points each. The coding correlations are real; the math ones are noise-compatible.

Framework Shift

Before (mainstream test-time scaling):   After (CoE):

  Q --> [ a1 a2 a3 ... ak ] parallel       Q --> a0 --> f0
              |                                   |
        verifier / vote                           v
              |                            Q,(a0,f0) --> a1 --> f1
              v                                   |
         one answer                               v
              |                            Q,(a0,f0),(a1,f1) --> a2
              v                                   |
     the whole trail is                          ...
     thrown away
                                           the trail *is* the state
  or, cross-task memory:                   no summarize step,
     solve P1 --> summarize --> card       nothing thrown out
     solve P2 --> summarize --> card
              |                            improvement source:
     P3 reads only the cards,              your own last k errors
     never the raw attempts                on *this* problem

  improvement source:                      cost is measured, not
  other problems' strategies               assumed: dollars and
                                           tokens reported per arm

From experience-as-strategy to experience-as-error-log, the core shift is that for a strong reasoning model the useful thing to remember is not what generally works, but what specifically just failed.

Expert Assessment

Problem choice: Real, and well-timed. The “era of experience” framing is fashionable, which usually predicts a wave of thin papers, and this one avoids that by being a measurement paper rather than a method paper. The finding that DC/ACE/ICL all underperform a plain iteration loop on GPT-5-class models is genuinely useful negative evidence — a lot of infrastructure is currently being built on the assumption that cross-task memory is the win, and this suggests the returns evaporate as base models get stronger. The counterweight: CoE is not a new mechanism. Reflexion, Self-Refine and Self-Debug are all special cases, and the paper says so. Naming the union “Chain-of-Experience” and adding it to the Chain-of-X pile is branding, not contribution. The contribution is the matrix.

Method maturity: The design is appropriately boring — no training, no scaffolding, a formalism you could write on a napkin — and that is the right choice for a study whose job is to isolate feedback type as a variable. The binary-vs-full executor arm is the sharpest piece of experimental design in the paper, because it varies richness while holding reliability fixed. The cross-model feedback study is the second best. What I miss is a stopping rule. Every arm runs a fixed 20 iterations, which means CoE as described is not a deployable procedure — a real system needs to know when to stop, and the paper’s own finding that gains saturate around round 20 makes an adaptive rule both necessary and easy to design. It was left on the table.

Experimental integrity: The reporting is above average — three runs with standard deviations, dollars and tokens per arm, a negative result on BrowseComp-Plus where self-feedback actively hurts because the task needs external knowledge, and a human-validated attribution study (6,630 flips, Cohen’s kappa 0.768) that most papers would not have bothered with. Two real problems, though. First, accuracy is reported as best over 20 iterations — the max along the trajectory. Combined with correctness feedback, which is an oracle bit, this is uncomfortably close to a definition of pass@20: keep guessing, the oracle tells you when to stop, report the hit. The paper is transparent that correctness feedback is an upper bound, but the abstract’s headline gains are not always cleanly separated by arm, and the honest self-feedback numbers (the deployable ones) are the smaller ones. Second, the “higher accuracy per token” claim does not survive contact with the paper’s own Table 5: on AIME 2025, correctness feedback gets 84.6% for 108.7K tokens while Dynamic CheatSheet gets 74.7% for 11.2K — ten points for ten times the tokens. Per token, DC wins decisively. The appendix states the defensible version (“comparable token counts to other multi-round methods”); the abstract states the indefensible one. The cost story that does hold up is the interesting one and it’s separate: feedback makes models less verbose, which is why self-feedback can beat no-feedback CoE on both accuracy and dollars simultaneously.

Writing quality: Serviceable, occasionally rushed — typos in the prose, figure axes that survived the PDF extraction badly, and a section 5 that crams four distinct ablations into two pages. The section I would rewrite is the efficiency claim, because it is the one place where the framing outruns the data and it would cost nothing to fix: separate accuracy-per-token from accuracy-per-dollar, report both against single-round baselines as well as multi-round ones, and let the verbosity finding stand on its own. It’s a better result than the one being claimed.

Verdict: weak accept — a careful, well-instrumented study with several transferable negative results, held back by a headline metric (best-over-20 with an oracle verifier) and an efficiency claim that both flatter the method more than the underlying data does.

Takeaways

• Do not compress a within-task trail. This is the most immediately actionable finding. If your agent is retrying the same task, resist the urge to summarize prior attempts to save context — DC and SimpleMem both lost points against passing the raw trail. Summarization is a lossy operation and the thing it deletes first is intermediate reasoning, which is exactly what the retry needs. Compress across tasks if you must; never within one.
• Separate feedback richness from feedback reliability when you design a signal. The binary-vs-full executor gap (71.9% vs 78.1% on LiveBench Code) says you can leave six points on the floor purely by truncating a signal you already computed. If you’re piping CI output into an agent loop, pipe the stack trace, not the exit code.
• Model-as-judge has a competence threshold, not a quality dial. GPT-5 mini judging GPT-5 helps on AIME and hurts on OmniMath. The predictor is the judge’s own base accuracy on that task. Before deploying a critic model, benchmark it as a solver on the same distribution — if it can’t solve, it probably can’t judge.
• Combine one rich channel with one reliable channel. Dual feedback (critic prose + oracle bit) beat both singles where the task had headroom, and stopped helping on the task where the reliable channel was already dominant. The design rule: add a second channel only if it supplies the axis the first one lacks.
• Budget short loops. Most of the gain lands in the first handful of iterations and 21-50 buys almost nothing (2.2% on AIME, 3.5% on OmniMath). If you’re building this, spend the engineering on a stopping rule rather than on a longer loop.
• A caveat to steal along with the ideas: when you evaluate your own iterative agent, report last-iteration accuracy, not best-iteration. Best-over-k with a verifier in the loop measures your verifier, not your agent.