interim_report.tex

\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{booktabs}
\usepackage{hyperref}
\usepackage{natbib}
\usepackage{graphicx}
\usepackage{amsmath}

\title{Memory-Augmented Recursive Language Models\\
\large COMS 6998: Continual Learning and Memory Models: Interim Report}
\author{Maksym Bondarenko \and Tevin Kim \and Justin Hou \and Phillip Yan}
\date{March 27, 2026}

\begin{document}
\maketitle

\section{Introduction}

Recursive Language Models (RLMs) \citep{zhang2026rlm} are a recent inference-time paradigm for scaling LLM context processing. Rather than feeding an entire long prompt into the model's context window, RLMs externalize the prompt as a variable in a Python REPL environment and let the LLM programmatically examine, decompose, and recursively call itself over slices of the input. The authors report performance on inputs up to 100$\times$ beyond model context windows across several long-context benchmarks.

However, RLMs are fundamentally \textbf{stateless} across recursive calls: each sub-call (\texttt{llm\_query}) receives only the prompt string passed by the parent model's code, with no memory of what previous calls discovered. Our project investigates whether augmenting RLMs with an explicit persistent memory mechanism (particularly learned knowledge graphs following the Graphiti approach \citep{ranade2025graphiti}) can improve performance on tasks requiring reasoning across distributed context.

In this interim report, we present: (1) a replication study of vanilla RLM on two benchmarks, (2) preliminary results on a self-consistency (majority-vote) variant, (3) a critical analysis of the RLM paper's benchmark choices, and (4) our plan for the remaining project phases.

\section{Literature Review}

\textbf{Long-context LLM approaches.} Extending LLM effective context has been approached from several directions. Retrieval-Augmented Generation (RAG) \citep{lewis2020rag} externalizes memory into a vector index, retrieving relevant passages at inference time. While practical, RAG is limited by retrieval granularity and its inability to represent relational structure. Long-context attention models \citep{press2022alibi} push the context window directly but face quadratic attention costs and empirical degradation at extreme lengths. State space models such as Mamba \citep{gu2023mamba} offer linear-time alternatives but compress context into a fixed-size latent state, losing fine-grained information.

\textbf{Recursive Language Models.} RLMs \citep{zhang2026rlm} represent a fundamentally different paradigm: the model decomposes the task recursively, calling itself on sub-problems and aggregating results in code. This yields effective context well beyond direct attention limits. The key architecture consists of a ``parent'' LLM that generates Python code in a REPL environment, with access to \texttt{llm\_query()} for sub-LM calls and \texttt{llm\_query\_batched()} for concurrent batch calls. The paper reports strong results using GPT-5 as the parent model and GPT-5-mini for sub-calls, with max recursion depth of 1.

\textbf{Self-consistency.} \citet{wang2023selfconsistency} showed that sampling multiple reasoning paths and taking the majority vote significantly improves LLM accuracy on reasoning tasks. We investigate applying this principle to RLM sub-calls, where each \texttt{llm\_query} classification is run $N$ times with majority voting to reduce individual classification errors.

\textbf{Memory-augmented LLMs.} Mem0 \citep{chhikara2025mem0} builds production-ready memory layers for AI agents. Graphiti \citep{ranade2025graphiti} maintains a temporally-aware relational knowledge graph that persists across interactions. MemWalker \citep{chen2023memwalker} constructs tree-like data structures for navigating long contexts. Our work is most closely related to Graphiti, as we propose injecting a persistent graph memory accessible to all RLM sub-calls.

\section{Experimental Setup}

\subsection{Models and Configuration}

All experiments use the same configuration as the RLM paper: GPT-5 as the parent (root) model, GPT-5-mini for sub-calls (\texttt{llm\_query}), max recursion depth of 1, and max iterations of 15.

\subsection{Benchmarks}

We evaluate on two benchmarks chosen to test different aspects of RLM:

\textbf{OOLONG-synth} \citep{bertsch2025oolong}: A long-context information aggregation benchmark. Each task presents a context window of news articles (without labels) and asks aggregate questions such as ``how many data points should be classified as Sci/Tech?'' The model must independently classify each article and count. Scoring uses $0.75^{|\text{error}|}$ for numeric answers (partial credit) and exact match for label answers. We use the agnews split at 16K tokens from HuggingFace.

\textbf{MuSiQue} \citep{trivedi2022musique}: A multi-hop question answering benchmark requiring chaining facts across multiple paragraphs. Each question requires 2--4 reasoning hops (e.g., ``Who is the spouse of the Green performer?'' requires identifying the performer of ``Green,'' then finding their spouse). Scoring uses Exact Match (EM) and token-level F1. We test on 5 two-hop tasks with 20 distractor paragraphs each.

\subsection{Majority-Vote Variant}

We implement a self-consistency variant by subclassing the RLM's \texttt{LocalREPL} environment. Our \texttt{MajorityVoteREPL} transparently overrides \texttt{\_llm\_query} and \texttt{\_llm\_query\_batched} so that each sub-call is executed $N=3$ times and the most common response is returned. The parent model's behavior is completely unchanged. It generates the same code, uses the same system prompt, and calls the same functions. The voting is transparent at the engine level.

\section{Results}

\subsection{OOLONG-synth (agnews, 16K tokens, numeric tasks)}

\begin{table}[h]
\centering
\begin{tabular}{lcc}
\toprule
\textbf{Method} & \textbf{Avg Score} & \textbf{Avg Time} \\
\midrule
Vanilla GPT-5 & 0.711 & 73.9s \\
RLM (GPT-5 + GPT-5-mini) & \textbf{0.756} & 315.2s \\
RLM + Majority Vote $\times$3 & 0.500 & 946.9s \\
\bottomrule
\end{tabular}
\caption{OOLONG-synth results on agnews numeric tasks at 16K tokens ($n=2$ tasks). Scoring: $0.75^{|\text{predicted} - \text{gold}|}$.}
\label{tab:oolong}
\end{table}

At 16K tokens ($\sim$183 articles), vanilla GPT-5 and RLM perform comparably. With only $n=2$ tasks, the score differences (0.711 vs.\ 0.756) are within stochastic variance (RLM trajectories are highly non-deterministic, as the parent may chunk differently, use different classification prompts, or make different aggregation decisions across runs). We do not draw conclusions about relative performance at this context length. The RLM paper reports that RLM's advantage over vanilla emerges primarily at 32K+ tokens, where vanilla GPT-5 begins to degrade.

The majority-vote variant performed worse, predicting 42 instead of the gold answer of 28 for one task. This suggests the classification errors are systematic (the model consistently misclassifies certain boundary articles), so voting amplifies rather than corrects the bias.

\textbf{Cost and time are significant barriers to larger-scale evaluation.} RLM is 4--5$\times$ slower and $\sim$3$\times$ more expensive than vanilla per task. Majority-vote RLM is 13$\times$ slower and $\sim$9$\times$ more expensive. At the paper's benchmark scale (50 tasks at 131K tokens), a full RLM evaluation would cost $\sim$\$22 and take several hours. Majority-vote at the same scale would cost $\sim$\$60+. These costs limited our ability to run larger sample sizes and precluded evaluation at the 131K context lengths where the paper reports its strongest results.

\subsection{MuSiQue (2-hop, 20 paragraphs)}

\begin{table}[h]
\centering
\begin{tabular}{lccc}
\toprule
\textbf{Method} & \textbf{EM} & \textbf{Avg F1} & \textbf{Avg Time} \\
\midrule
Vanilla GPT-5 & \textbf{0.800} (4/5) & \textbf{0.933} & 13.85s \\
RLM (GPT-5 + GPT-5-mini) & 0.600 (3/5) & 0.600 & 195.87s \\
\bottomrule
\end{tabular}
\caption{MuSiQue results on 5 two-hop tasks with 20 paragraphs each.}
\label{tab:musique}
\end{table}

\begin{table}[h]
\centering
\small
\begin{tabular}{clcc}
\toprule
\textbf{Task} & \textbf{Question} & \textbf{Vanilla EM} & \textbf{RLM EM} \\
\midrule
1 & Who is the spouse of the Green performer? & 1 & 0 \\
2 & Who founded the company that distributed UHF? & 1 & 1 \\
3 & What admin.\ entity is Ciudad Deportiva's owner located in? & 1 & 1 \\
4 & Where is Ulrich Walter's employer headquartered? & 0 & 0 \\
5 & Which company owns the manufacturer of Learjet 60? & 1 & 1 \\
\bottomrule
\end{tabular}
\caption{Per-task MuSiQue breakdown.}
\label{tab:musique-tasks}
\end{table}

Vanilla GPT-5 outperforms RLM on multi-hop QA. With only 20 paragraphs ($\sim$2K tokens of context), the full text fits easily within GPT-5's context window, making RLM's decomposition overhead pure cost with no benefit. RLM failed Task~1 completely; it could not chain the two hops (identifying the performer of ``Green'' and then finding their spouse) through its sub-call architecture. The stateless sub-calls each received isolated paragraphs and could not reason across them. RLM was 14$\times$ slower on average (196s vs.\ 14s).

\subsection{Cost Analysis}

\begin{table}[h]
\centering
\begin{tabular}{lccc}
\toprule
\textbf{Experiment} & \textbf{Vanilla} & \textbf{RLM} & \textbf{RLM Majority} \\
\midrule
OOLONG 16K (2 tasks) & $\sim$\$0.20 & $\sim$\$0.60 & $\sim$\$1.80 \\
MuSiQue (5 tasks) & $\sim$\$0.05 & $\sim$\$1.50 & N/A \\
\bottomrule
\end{tabular}
\caption{Estimated API costs per experiment.}
\label{tab:cost}
\end{table}

RLM is 3--30$\times$ more expensive than vanilla depending on task complexity. Majority voting triples the sub-call cost.

\section{Analysis and Key Findings}

\subsection{RLM's Strengths are Task-Dependent}

Our experiments across two benchmarks suggest that RLM's effectiveness depends heavily on task structure:

\begin{enumerate}
    \item \textbf{OOLONG suits RLM's decompose-and-aggregate pattern.} The task structure (classify each item independently, count in code) maps directly to what RLMs are designed for. At 16K tokens, vanilla GPT-5 and RLM perform comparably (both within the model's context window). The RLM paper reports clear advantages at 32K+ tokens where vanilla degrades, a regime we could not fully test due to cost constraints. Our limited 16K results are consistent with the paper's finding that RLM's advantage grows with context length.

    \item \textbf{Multi-hop QA exposes RLM's statelessness.} On MuSiQue, where answering requires chaining facts across paragraphs (not independently classifying items), RLM performs worse than vanilla. The stateless sub-calls cannot share discoveries, making multi-hop reasoning difficult. This is a structural limitation, not a context-length issue.

    \item \textbf{RLM trajectories are highly stochastic.} We observed significant run-to-run variance in RLM's behavior: the parent model may chunk the context differently, write different classification prompts, or use different aggregation strategies. With our limited sample sizes ($n=2$ for OOLONG, $n=5$ for MuSiQue), individual task results should be interpreted as illustrative rather than statistically conclusive. Larger-scale evaluation is needed but was constrained by API costs (\$0.30--\$1.50 per RLM task) and runtime (3--10 minutes per task).
\end{enumerate}

\subsection{Self-Consistency Does Not Trivially Help}

Our majority-vote experiment showed that running each sub-call 3$\times$ and voting does not improve accuracy when classification errors are systematic rather than random. The model consistently misclassified certain boundary articles (e.g., tech companies' business news classified as Sci/Tech), so voting amplified the error. This suggests that improving RLM sub-call accuracy requires better prompting or stronger child models, not simple repetition.

\subsection{The Statelessness Problem}

The MuSiQue results directly motivate our proposed memory augmentation. In Task~1 (``Who is the spouse of the Green performer?''), the RLM needed to: (1) find that Steve Hillage is the performer of ``Green,'' and (2) find Steve Hillage's spouse. With stateless sub-calls, the result of hop~1 cannot inform hop~2 unless the parent explicitly orchestrates this, which it failed to do. A persistent memory layer where sub-calls can write and read shared state would directly address this limitation.

\section{Remaining Work}

\subsection{Phase 2: Memory-Augmented RLM (Weeks 5--9)}

\begin{enumerate}
    \item \textbf{Implement memory layer.} Inject \texttt{memory\_write(key, value)} and \texttt{memory\_read(query)} as custom REPL tools, backed by three memory substrates:
    \begin{itemize}
        \item Flat key-value store (baseline)
        \item Vector store / RAG (semantic similarity retrieval)
        \item Knowledge graph via Graphiti \citep{ranade2025graphiti} (relational, temporally-aware)
    \end{itemize}

    \item \textbf{Benchmark memory-augmented RLM} on OOLONG at 131K tokens (where vanilla GPT-5 degrades), MuSiQue (where statelessness clearly hurts), and InfiniteBench En.MC/QA (novel-length holistic comprehension).

    \item \textbf{Ablations.} Compare memory types, vary number of sub-calls, test with/without memory on each benchmark to isolate the contribution of persistent state.
\end{enumerate}

\subsection{Phase 3: Analysis and Write-up (Weeks 10--12)}

\begin{enumerate}
    \setcounter{enumi}{3}
    \item \textbf{Characterize when memory helps vs.\ hurts.} We hypothesize memory helps on tasks requiring cross-chunk reasoning (MuSiQue, entity tracking) but adds overhead on independently-decomposable tasks (OOLONG counting).

    \item \textbf{Final report} with quantitative comparison across all configurations.
\end{enumerate}

\bibliographystyle{plainnat}
\begin{thebibliography}{10}

\bibitem[Zhang et~al.(2026)]{zhang2026rlm}
Alex~L. Zhang, Tim Kraska, and Omar Khattab.
\newblock Recursive Language Models.
\newblock \emph{arXiv preprint arXiv:2512.24601}, 2026.

\bibitem[Ranade et~al.(2025)]{ranade2025graphiti}
Prasad Ranade et~al.
\newblock Graphiti: Building Real-Time Knowledge Graphs with LLM-Derived Triples.
\newblock Zep AI, 2025.

\bibitem[Lewis et~al.(2020)]{lewis2020rag}
Patrick Lewis et~al.
\newblock Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks.
\newblock In \emph{NeurIPS}, 2020.

\bibitem[Press et~al.(2022)]{press2022alibi}
Ofir Press, Noah~A. Smith, and Mike Lewis.
\newblock Train Short, Test Long: Attention with Linear Biases Enables Input Length Generalization.
\newblock In \emph{ICLR}, 2022.

\bibitem[Gu and Dao(2023)]{gu2023mamba}
Albert Gu and Tri Dao.
\newblock Mamba: Linear-Time Sequence Modeling with Selective State Spaces.
\newblock \emph{arXiv preprint arXiv:2312.00752}, 2023.

\bibitem[Wang et~al.(2023)]{wang2023selfconsistency}
Xuezhi Wang et~al.
\newblock Self-Consistency Improves Chain of Thought Reasoning in Language Models.
\newblock In \emph{ICLR}, 2023.

\bibitem[Chhikara et~al.(2025)]{chhikara2025mem0}
Prateek Chhikara et~al.
\newblock Mem0: Building Production-Ready AI Agents with Scalable Long-Term Memory.
\newblock \emph{arXiv preprint arXiv:2504.19413}, 2025.

\bibitem[Chen et~al.(2023)]{chen2023memwalker}
Howard Chen et~al.
\newblock Walking Down the Memory Maze: Beyond Context Limit through Interactive Reading.
\newblock \emph{arXiv preprint arXiv:2310.05029}, 2023.

\bibitem[Bertsch et~al.(2025)]{bertsch2025oolong}
Amanda Bertsch et~al.
\newblock Oolong: Evaluating Long Context Reasoning and Aggregation Capabilities.
\newblock \emph{arXiv preprint arXiv:2511.02817}, 2025.

\bibitem[Trivedi et~al.(2022)]{trivedi2022musique}
Harsh Trivedi et~al.
\newblock MuSiQue: Multi-hop Questions via Single-hop Question Composition.
\newblock \emph{TACL}, 2022.

\end{thebibliography}

\end{document}