Forecasting Computer Science Breakthroughs in 2027–2031: An Evidence-Grounded Prospective Research Portfolio

Research object

1. Introduction

Research attention is easier to measure than scientific progress. Publication volume, citation growth, benchmark popularity, or topical similarity can rise without a theorem being proved, an algorithm improving against a matched baseline, or an empirical result surviving independent replication. A technically important result can also be missed by simple retrieval. A defensible forecast therefore needs an event specified before its outcome, a point-in-time evidence boundary, and rules distinguishing resolution, partial progress, and missing evidence.

We ask: given evidence available on 2026-10-17, which specific computer-science problem families merit the strongest qualitative expectation of independently verifiable progress by 2031, and what observations would change that ordering? This purposive portfolio is not representative of all computer science. “Breakthrough” is shorthand for substantial technical progress, not a formal label assigned to these opportunities.

2. Background and related work

Science-of-science work predicts citations, impact, or bibliometric breakthrough proxies, e.g. Min, Bu & Sun (2021), https://doi.org/10.1016/j.techfore.2020.120502. PreScience is a large time-snapshotted scientific forecasting benchmark over AI paper/topic outcomes (Ajith et al., 2026, https://arxiv.org/abs/2602.20459). Neither establishes this exact task: forecasting whether a frozen theorem-level CS question will be resolved or advanced under predeclared assumptions. We do not claim to be the first scientific forecasting benchmark.

The project’s evidence-based question discovery and astronomy historical-backtesting work is closer in unit and workflow (Mao, 2026a,b; https://arxiv.org/abs/2608.09968; https://arxiv.org/abs/2608.16795). It is same-project prior work, not independent corroboration, and reports a serious outcome-label reliability challenge. ResearchBench evaluates inspiration retrieval, hypothesis composition, and ranking (Liu et al., ACL Findings 2026, https://aclanthology.org/2026.findings-acl.644/); PaperBench evaluates replication of published AI research (Starace et al., 2025, https://arxiv.org/abs/2504.01848). These are relevant but distinct from prospective theorem-resolution forecasting.

Paper 3 uses point-in-time question features and temporal validation; it keeps future attention, direct resolution, and premise revision distinct. Its astronomy results do not establish CS predictive skill. We keep Target A (direct proof or refutation of a frozen proposition) separate from Target B (substantial independently verifiable progress short of full resolution). Paper 4 organizes competing hypotheses, provenance-linked evidence gaps, candidate actions, and declared cost/information-gain assumptions. Its utility estimates are not observed scientific value. Neither method is validated as a CS forecaster or superior planner here.

3. Research design

The evidence cutoff is 2026-10-17. We reviewed the ten-record prospective cohort and manifest, final portfolio dossier, earlier radar and screening records, Paper 3/4 methods, and prior novelty/readiness audits. We screened primary-source leads in formal verification, inference systems, adaptive privacy, dynamic algorithms, approximation, geometry, integer programming, and scientific-agent evaluation. Claims were checked against each source’s problem class, parameterization, baseline, metric, and assumptions. Author-reported results are attributed and are not called independent replications.

We grouped related questions before ranking. Approximate dynamic maximum matching and ordered Ruzsa–Szemerédi (ORS) form one dependent chain, not independent confirmations. We did not treat a retrieval miss as evidence of neglect or non-resolution. Each portfolio entry has a source-backed baseline, interpretable progress endpoint, obstacle, counterevidence, and independent verification route. Qualitative ordering considers evidence/endpoint clarity, technical path, horizon tractability, significance, and counterevidence. No numerical weights, probabilities, attention counts, or citation counts are used. The order is editorial decision priority, not an estimated chance of success.

The portfolio is distinct from the ten previously frozen commitments in Section 7. The final 5+5 ranks do not create ten new forecasts or replace frozen event text. No new forecast passed the freeze gate in the final portfolio round.

4. Progress and outcome definitions

Substantial progress means an independently verifiable: (1) theorem or bound advancing the exact model; (2) algorithmic improvement over a matched baseline; (3) independently replicated empirical improvement; (4) independently checked counterexample; (5) justified premise revision/refutation; or (6) material narrowing of an open question. Categories can coexist. Target A is direct proof/refutation; Target B is progress short of full resolution. Attention and practical impact remain separate. Missing or inaccessible evidence is unadjudicated, not negative. Correctness relative to a formal specification does not establish that the specification captures intended behavior.

5. Near-term portfolio: 2027–2028

1. Repository-scale code-and-proof synthesis

Question. Can automated systems buildable implementations and machine-checked proofs across multi-module repositories with cross-module invariants, rather than isolated proof obligations? Evidence. Vero has 43 repository instances; its authors report 27 complete code-and-proof solves for the strongest configuration and ten instances resistant to all tested configurations (https://arxiv.org/abs/2608.13522). VeriSoftBench reports deep repository dependency difficulty (https://arxiv.org/abs/2602.18307). CoCo-Prover reports improved success-cost results, including up to 26/43 Vero solves, in its own evaluation (https://arxiv.org/abs/2610.09681). None is independently reproduced here. Expected progress. Benchmark-specific coverage and cost-quality improvements, not general autonomous software engineering. Obstacle/counterargument. Cross-module invariants, clean builds, benchmark curation, changing models/budgets, and specification fidelity. Proof kernels certify encoded specifications only. Impact and verification. Potentially high for assurance. Lock versions/tasks/budgets; test hidden repositories, kernel-check proofs, clean-build, audit specifications independently, and report cost/failures.

2. LLM inference scheduling under KV-cache pressure

Question. Can scheduling of requests, speculative work, and KV-cache residency improve goodput or tail latency under changing arrivals at fixed output quality, memory, and service constraints? Evidence. Online guarantees depend on arrivals; one fully adversarial model rules out a constant competitive ratio (Jaillet et al., 2025, https://arxiv.org/abs/2502.07115). Spexis reports up to 34% higher request rate on evaluated configurations (Jung et al., 2026, https://arxiv.org/abs/2609.34370); this is not independent replication or a universal gain. Obstacle. Gains may disappear when memory, quality, workload, preemption, energy, and p95/p99 latency are matched. Verification. Replay fixed traces on matched hardware/model/memory/quality; report goodput, tails, energy, eviction/recomputation, configs, code, and failures. Separate empirical gains from online guarantees.

3. Adaptive privacy filters at intermediate sampling rates

Question. Can valid, quantitatively useful filters be proved for fully adaptive compositions of Poisson-subsampled Gaussian mechanisms in intermediate sampling regimes? Evidence. Tran et al. show a natural fully adaptive f-DP filter can be invalid and construct approximate GDP filters for low q<0.2 and high q>0.8 regimes under stated assumptions (2026, https://arxiv.org/abs/2602.06756). This does not prove a useful middle-regime extension exists. Obstacle/counterargument. Adaptivity, approximation error, and numerical soundness; existing RDP/PLD accountants may dominate. The frozen event’s comparator remains underspecified. Verification. Prove explicit assumptions/error bounds and compare against named accountants under identical models; certified arithmetic is needed for numerical claims.

4. Approximate fully dynamic maximum matching

Question. Can general-graph dynamic data structures maintain an explicit (1−ε)-approximate maximum matching in O(n^(1−δ)) amortized update time for fixed ε,δ>0 under frozen output/adversary assumptions? Evidence. FOCS 2024 and SODA 2025 connect update time to ordered-RS density (https://doi.org/10.1109/FOCS61266.2024.00027; https://doi.org/10.1137/1.9781611978322.96). Bernstein et al. obtain sublinear update time for maximal matching (2025, https://arxiv.org/abs/2504.20780), which is not approximate maximum matching. Obstacle. ORS improvement must transfer through exact reduction and quantifiers. Verification. Match graph model, update adversary, amortization, approximation, probability, space/preprocessing, explicit output, and exponent theorem by theorem. Keep matching and ORS as one family.

5. Artifact-level multi-agent verification

Question. Can a verifier predict independently checked artifact correctness and improve end-to-end outcomes after costs and false positives/negatives? Evidence. MAS-ProVe reports process verification does not consistently improve multi-agent performance and may have high variance (2026, https://arxiv.org/abs/2602.03053). EIG/ResearchBench assess ideation; PaperBench tests replication. They do not jointly measure independently verified discovery. Astronomy backtesting reports low annotator agreement on its own taxonomy; this is a warning, not a CS estimate. Obstacle. Shared-model bias, benchmark contamination, inadequate traces, and costly ground truth. Verification. Freeze verifier outputs, independently test final artifacts, and report error rates, agreement, compute, paired task outcomes. A judge score is not correctness.

6. Medium-term portfolio: 2029–2031

1. Dynamic matching–ORS extremal bottleneck

Can ordered Ruzsa–Szemerédi at fixed linear matching density have polynomial growth sufficient to imply fixed-exponent sublinear update time for approximate maximum matching? This is one dependent family. The 2024–2025 reductions make the chain explicit; an ORS improvement matters only if it transfers under exact parameters. The ORS event contains a date defect recorded below.

2. Planar Three-Sets Cut-Uncut, terminal sizes (1,1,2)

Can the exact unweighted planar case with two singleton sets and one connected two-vertex terminal set be solved in polynomial time? Bentert et al. give a randomized FPT algorithm for planar two-set Cut-Uncut and explicitly leave this three-set case open (ICALP 2024, https://doi.org/10.4230/LIPIcs.ICALP.2024.22). Ordinary planar Multiway Cut does not preserve the required pair connectivity. Verify graph class, terminal pattern, costs, connectivity, exactness, and infeasibility handling.

3. Planar discrete Fréchet under translation

The frozen question targets exact computation in O(n^4 polylog n) for planar discrete Fréchet under translation. The audited source gives an approximately O~(n^(14/3)) algorithm and SETH-based n^(4−o(1)) lower bound for this specified problem (Bringmann, Künnemann & Nusser, https://arxiv.org/abs/1810.10982). The exponent room is narrow and conditional. Match model, arithmetic, exact-value/decision, and bit complexity.

4. Two-stage integer programming

Can FPT feasibility extend to exact optimization with bounded local parameters and unrestricted global coefficients? Cslovjecsek et al. establish neighboring feasibility results and identify optimization as distinct (TheoretiCS 2025, https://doi.org/10.46298/theoretics.25.15). A later theorem parameterized by all coefficient sizes does not settle the unbounded-global regime. The endpoint must distinguish exact optimum, infeasibility, and unboundedness under the same encoding and parameters.

5. Scientific agents producing reproducible evidence

Can agents freeze falsifiable questions, run discriminating studies, preserve raw artifacts, and achieve independent reproduction above simple baselines? Existing tools measure ideation, replication, or process verification separately. This is the least mature entry: a reliable adjudication taxonomy, agreement/missingness, raw-artifact reproduction, and baseline comparison are prerequisites. No new event is frozen for this family.

7. Existing prospective forecast registry

The registry contains ten frozen qualitative commitments (three original records plus seven later registrations). They are not ten new ranked entries or independent observations. Full event text, source URLs, cutoffs, issue times, and hashes are preserved at https://github.com/nonameisready/scientific-discovery-computer-science/blob/db6aaa4b7f5fa364ced3042bf55d8df6b8eef1ce/data/forecast_engine/prospective_cohort_v2.json; the linked activation preserves the original three.

The original three records share issue time 2026-10-17 02:47:37 UTC, but individual observation_start fields are null. Their issue date precedes the global 2027-01-01 horizon start, so it is ambiguous whether the interval between issuance and horizon counts; we do not retroactively decide. The seven later records were issued at 03:15:09 UTC with source-only cutoffs. Two independent human reviewers are required for final adjudication; AI review is not independent human review. Source hashes cover citation/metadata and registry snapshots, not full paper bytes.

The ORS record is inconsistent: structured deadline 2030-12-31; frozen event text says 2031-12-31. We do not choose a deadline or rewrite the frozen record. If the conflict affects adjudication, the result remains unresolved pending authorized provenance-based correction.

8. Ranking robustness

Under proof-tractability emphasis, adaptive privacy, planar cut-uncut, and two-stage IP rise. Under computational-impact emphasis, inference scheduling and repository code/proof rise. Under source-maturity/independent-verifiability emphasis, theorem endpoints rise and process verification/autonomous science fall. Family membership is more stable than exact ordering; medium-term ranks are especially sensitive. These are ordinal scenario comparisons, not statistical sensitivity estimates, calibration intervals, or probabilities.

9. Scientific validation framework

Preserve question text, source cutoff, issue time, family, and predeclared endpoints. Theorem matching requires independent review of object, assumptions, class, model, parameters, quantifiers, and endpoint. Empirical verification needs versioned artifacts, matched baselines, comparable resources, uncertainty, and reproduction. Record reviewer disagreement; search failure remains missing evidence.

Evaluate Target A direct proof/refutation separately from Target B progress. Attention and impact remain separate. A future Paper 3 evaluation needs adequate outcomes, point-in-time features, family-grouped chronology, an untouched final time block, and simple baselines such as publication volume, field momentum, and source-only text. No CS score is valid before the eligibility gates pass. Paper 4 must timestamp hypotheses, evidence, candidate actions, costs, and information-gain assumptions before execution, then distinguish feasibility from realized evidence yield. This paper measures neither predictive skill nor planner efficacy.

10. Limitations

This is one purposive qualitative synthesis, not a representative cohort or calibrated model. Ten commitments are small and heterogeneous; most mature only in 2030–2031. No outcome labels have matured; independent human adjudication and panel review are incomplete. Candidate families are dependent; publication, selection, and reporting bias are plausible. Vero, CoCo-Prover, and Spexis measurements are author-reported and not independently reproduced here. Some empirical topics need sharper common endpoints. Source hashes cover metadata, not full text. The original three have an observation-window ambiguity and ORS has a deadline mismatch. No calibrated accuracy, Paper 3 CS predictive performance, or Paper 4 action-selection superiority is demonstrated. This paper is not peer reviewed.

11. Conclusion

The evidence supports a ranked set of prospective questions, not predictive success. Repository-scale code-and-proof synthesis and constrained inference scheduling have the strongest qualitative near-term case because they have visible progress and objective artifact tests, but reported gains remain configuration-sensitive. Adaptive privacy filters are a precise theory question. Approximate maximum matching is linked to unresolved ORS; maximal matching is not a substitute. Medium-term entries include exact planar, geometric, and integer-programming problems; reproducible scientific agents remain uncertain because outcome adjudication is unresolved.

The ten frozen commitments remain distinct from the final 5+5 portfolio. Paper 3 has not shown CS predictive power, and Paper 4 has not shown planner superiority. The contribution is a transparent, falsifiable portfolio with counterarguments and verification criteria. Independent methodological novelty and publication value remain open to external review.

Author contributions and AI disclosure

Ada Mao directed and supervised the research program. GPT6-luna, an AI research agent, performed literature synthesis, candidate screening, evidence organization, and prospective qualitative forecast development under human supervision. GPT6-luna is an AI research collaborator, not a human researcher. The manuscript and portfolio are uncalibrated and have not received independent human peer review.

Data and reproducibility

Portfolio, detailed dossier, hash manifest, and frozen registry: https://github.com/nonameisready/scientific-discovery-computer-science/tree/db6aaa4b7f5fa364ced3042bf55d8df6b8eef1ce. Hashes protect local artifacts and frozen inputs, not cited full-text papers; validation checks file structure, not forecast truth. No experiments, model training/inference, new labels, or new forecast commitments were generated in the final portfolio round.

References

1. Min, C., Bu, Y., & Sun, J. (2021). Predicting scientific breakthroughs based on knowledge structure variations. Technological Forecasting and Social Change 164, 120502. https://doi.org/10.1016/j.techfore.2020.120502
2. Ajith, A., et al. (2026). PreScience: A dataset and benchmark for scientific forecasting. https://arxiv.org/abs/2602.20459
3. Mao, H. (2026). Evidence-Based Scientific Question Discovery. https://arxiv.org/abs/2608.09968
4. Mao, H. (2026). Historical Backtesting for Scientific Question Discovery. https://arxiv.org/abs/2608.16795
5. Liu, Y., et al. (2026). ResearchBench. Findings of ACL 2026. https://aclanthology.org/2026.findings-acl.644/
6. Starace, G., et al. (2025). PaperBench. https://arxiv.org/abs/2504.01848
7. Ye, Z., et al. (2026). Vero. https://arxiv.org/abs/2608.13522
8. Xin, Y., et al. (2026). VeriSoftBench. https://arxiv.org/abs/2602.18307
9. Yao, S., et al. (2026). CoCo-Prover. https://arxiv.org/abs/2610.09681
10. Jaillet, P., et al. (2025). Online Scheduling for LLM Inference with KV Cache Constraints. https://arxiv.org/abs/2502.07115
11. Jung, H., et al. (2026). Spexis. https://arxiv.org/abs/2609.34370
12. Tran, H., et al. (2026). f-Differential Privacy Filters. https://arxiv.org/abs/2602.06756
13. Behnezhad, S., & Ghafari, M. (2024). Fully Dynamic Matching and Ordered Ruzsa–Szemerédi Graphs. https://doi.org/10.1109/FOCS61266.2024.00027
14. Assadi, S., Khanna, S., & Kiss, P. (2025). Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa–Szemerédi Graphs. https://doi.org/10.1137/1.9781611978322.96
15. Bernstein, A., et al. (2025). Deterministic Dynamic Maximal Matching in Sublinear Update Time. https://arxiv.org/abs/2504.20780
16. Venkataramani, V., et al. (2026). MAS-ProVe. https://arxiv.org/abs/2602.03053
17. Bentert, M., et al. (2024). Two-Sets Cut-Uncut on Planar Graphs. https://doi.org/10.4230/LIPIcs.ICALP.2024.22
18. Bringmann, K., Künnemann, M., & Nusser, A. (2019). Fréchet Distance Under Translation. https://arxiv.org/abs/1810.10982
19. Lenzen, C., & Wenning, S. (2024). Tight Bounds for Constant-Round Domination. https://arxiv.org/abs/2408.12998
20. Brakensiek, J., Huang, M., Potechin, A., & Zwick, U. (2026). MAX BISECTION Might Be Harder to Approximate than MAX CUT. https://doi.org/10.1137/1.9781611978971.197
21. Chen, L., Jin, C., Randolph, W., & Servedio, R. (2025). New Algorithms for Pigeonhole Equal Subset Sum. https://doi.org/10.4230/LIPIcs.ESA.2025.86
22. Cslovjecsek, J., Koutecký, M., Lassota, A., Pilipczuk, M., & Polak, A. (2025). Parameterized Algorithms for Block-Structured Integer Programs with Large Entries. https://doi.org/10.46298/theoretics.25.15
23. Bravyi, S., Parham, T., & Tran, M. C. (2024). Identity Check Problem for Shallow Quantum Circuits. https://arxiv.org/abs/2401.16525